57
\$\begingroup\$

Tournament over!

The tournament is now over! The final simulation was run during the night, a total of \$3*10^8\$ games. The winner is Christian Sievers with his bot OptFor2X. Christian Sievers also managed to secure the second place with Rebel. Congratulations! Below you can see the official high score list for the tournament.

If you still want to play the game, you are more than welcome to use the controller posted below, and to use the code in it to create your own game.

Dice

I was invited to play a game of dice which I had never heard of. The rules were simple, yet I think it would be perfect for a KotH challenge.

The rules

The start of the game

The die goes around the table, and each time it is your turn, you get to throw the die as many times as you want. However, you have to throw it at least once. You keep track of the sum of all throws for your round. If you choose to stop, the score for the round is added to your total score.

So why would you ever stop throwing the die? Because if you get 6, your score for the entire round becomes zero, and the die is passed on. Thus, the initial goal is to increase your score as quickly as possible.

Who is the winner?

When the first player around the table reaches 40 points or more, the last round starts. Once the last round has started, everyone except the person who initiated the last round gets one more turn.

The rules for the last round is the same as for any other round. You choose to keep throwing or to stop. However, you know that you have no chance of winning if you don't get a higher score than those before you on the last round. But if you keep going too far, then you might get a 6.

However, there's one more rule to take into consideration. If your current total score (your previous score + your current score for the round) is 40 or more, and you hit a 6, your total score is set to 0. That means that you have to start all over. If you hit a 6 when your current total score is 40 or more, the game continues as normal, except that you're now in last place. The last round is not triggered when your total score is reset. You could still win the round, but it does become more challenging.

The winner is the player with the highest score once the last round is over. If two or more players share the same score, they will all be counted as victors.

An added rule is that the game continues for a maximum of 200 rounds. This is to prevent cases where multiple bots basically keep throwing until they hit 6 to stay at their current score. Once the 199th round is passed, last_round is set to true, and one more round is played. If the game goes to 200 rounds, the bot (or bots) with the highest score is the winner, even if they do not have 40 points or more.

Recap

  • Each round you keep throwing the die until you choose to stop or you get a 6
  • You must throw the die once (if your first throw is a 6, your round is immediately over)
  • If you get a 6, your current score is set to 0 (not your total score)
  • You add your current score to your total score after each round
  • When a bot ends their turn resulting in a total score of at least 40, everyone else gets a last turn
  • If your current total score is \$\geq 40\$ and you get a 6, your total score is set to 0 and your round is over
  • The last round is not triggered when the above occurs
  • The person with the highest total score after the last round is the winner
  • In case there are multiple winners, all will be counted as winners
  • The game lasts for a maximum of 200 rounds

Clarification of the scores

  • Total score: the score that you have saved from previous rounds
  • Current score: the score for the current round
  • Current total score: the sum of the two scores above

How do you participate

To participate in this KotH challenge, you should write a Python class which inherits from Bot. You should implement the function: make_throw(self, scores, last_round). That function will be called once it is your turn, and your first throw was not a 6. To keep throwing, you should yield True. To stop throwing, you should yield False. After each throw, the parent function update_state is called. Thus, you have access to your throws for the current round using the variable self.current_throws. You also have access to your own index using self.index. Thus, to see your own total score you would use scores[self.index]. You could also access the end_score for the game by using self.end_score, but you can safely assume that it will be 40 for this challenge.

You are allowed to create helper functions inside your class. You may also override functions existing in the Bot parent class, e.g. if you want to add more class properties. You are not allowed to modify the state of the game in any way except yielding True or False.

You're free to seek inspiration from this post, and copy any of the two bots that I've included here. However, I'm afraid that they're not particularly effective...

On allowing other languages

In both the sandbox and on The Nineteenth Byte, we have had discussions about allowing submissions in other languages. After reading about such implementations, and hearing arguments from both sides, I have decided to restrict this challenge to Python only. This is due to two factors: the time required to support multiple languages, and the randomness of this challenge requiring a high number of iterations to reach stability. I hope that you will still participate, and if you want to learn some Python for this challenge, I'll try to be available in the chat as often as possible.

For any questions that you might have, you can write in the chat room for this challenge. See you there!

Rules

  • Sabotage is allowed, and encouraged. That is, sabotage against other players
  • Any attempt to tinker with the controller, run-time or other submissions will be disqualified. All submissions should only work with the inputs and storage they are given.
  • Any bot which uses more than 500MB memory to make its decision will be disqualified (if you need that much memory you should rethink your choices)
  • A bot must not implement the exact same strategy as an existing one, intentionally or accidentally.
  • You are allowed to update your bot during the time of the challenge. However, you could also post another bot if your approach is different.

Example

class GoToTenBot(Bot):
    def make_throw(self, scores, last_round):
        while sum(self.current_throws) < 10:
            yield True
        yield False

This bot will keep going until it has a score of at least 10 for the round, or it throws a 6. Note that you don't need any logic to handle throwing 6. Also note that if your first throw is a 6, make_throw is never called, since your round is immediately over.

For those who are new to Python (and new to the yield concept), but want to give this a go, the yield keyword is similar to a return in some ways, but different in other ways. You can read about the concept here. Basically, once you yield, your function will stop, and the value you yielded will be sent back to the controller. There, the controller handles its logic until it is time for your bot to make another decision. Then the controller sends you the dice throw, and your make_throw function will continue executing right where if stopped before, basically on the line after the previous yield statement.

This way, the game controller can update the state without requiring a separate bot function call for each dice throw.

Specification

You may use any Python library available in pip. To ensure that I'll be able to get a good average, you have a 100 millisecond time limit per round. I'd be really happy if your script was way faster than that, so that I can run more rounds.

Evaluation

To find the winner, I will take all bots and run them in random groups of 8. If there are fewer than 8 classes submitted, I will run them in random groups of 4 to avoid always having all bots in each round. I will run simulations for about 8 hours, and the winner will be the bot with the highest win percentage. I will run start the final simulations at the start of 2019, giving you all Christmas to code your bots! The preliminary final date is January 4th, but if that's too little time I can change it to a later date.

Until then, I'll try to make a daily simulation using 30-60 minutes of CPU time, and updating the score board. This will not be the official score, but it will serve as a guide to see which bots perform the best. However, with Christmas coming up, I hope you can understand that I won't be available at all times. I'll do my best to run simulations and answer any questions related to the challenge.

Test it yourself

If you want to run your own simulations, here's the full code to the controller running the simulation, including two example bots.

Controller

Here's the updated controller for this challenge. It supports ANSI outputs, multi-threading, and collects additional stats thanks to AKroell! When I make changes to the controller, I'll update the post once documentation is complete.

Thanks to BMO, the controller is now able to download all bots from this post using the -d flag. Other functionality is unchanged in this version. This should ensure that all of your latest changes are simulated as soon as possible!

#!/usr/bin/env python3
import re
import json
import math
import random
import requests
import sys
import time
from numpy import cumsum

from collections import defaultdict
from html import unescape
from lxml import html
from multiprocessing import Pool
from os import path, rename, remove
from sys import stderr
from time import strftime

# If you want to see what each bot decides, set this to true
# Should only be used with one thread and one game
DEBUG = False
# If your terminal supports ANSI, try setting this to true
ANSI = False
# File to keep base class and own bots
OWN_FILE = 'forty_game_bots.py'
# File where to store the downloaded bots
AUTO_FILE = 'auto_bots.py'
# If you want to use up all your quota & re-download all bots
DOWNLOAD = False
# If you want to ignore a specific user's bots (eg. your own bots): add to list
IGNORE = []
# The API-request to get all the bots
URL = "https://api.stackexchange.com/2.2/questions/177765/answers?page=%s&pagesize=100&order=desc&sort=creation&site=codegolf&filter=!bLf7Wx_BfZlJ7X"


def print_str(x, y, string):
    print("\033["+str(y)+";"+str(x)+"H"+string, end = "", flush = True)

class bcolors:
    WHITE = '\033[0m'
    GREEN = '\033[92m'
    BLUE = '\033[94m'
    YELLOW = '\033[93m'
    RED = '\033[91m'
    ENDC = '\033[0m'

# Class for handling the game logic and relaying information to the bots
class Controller:

    def __init__(self, bots_per_game, games, bots, thread_id):
        """Initiates all fields relevant to the simulation

        Keyword arguments:
        bots_per_game -- the number of bots that should be included in a game
        games -- the number of games that should be simulated
        bots -- a list of all available bot classes
        """
        self.bots_per_game = bots_per_game
        self.games = games
        self.bots = bots
        self.number_of_bots = len(self.bots)
        self.wins = defaultdict(int)
        self.played_games = defaultdict(int)
        self.bot_timings = defaultdict(float)
        # self.wins = {bot.__name__: 0 for bot in self.bots}
        # self.played_games = {bot.__name__: 0 for bot in self.bots}
        self.end_score = 40
        self.thread_id = thread_id
        self.max_rounds = 200
        self.timed_out_games = 0
        self.tied_games = 0
        self.total_rounds = 0
        self.highest_round = 0
        #max, avg, avg_win, throws, success, rounds
        self.highscore = defaultdict(lambda:[0, 0, 0, 0, 0, 0])
        self.winning_scores = defaultdict(int)
        # self.highscore = {bot.__name__: [0, 0, 0] for bot in self.bots}

    # Returns a fair dice throw
    def throw_die(self):
        return random.randint(1,6)
    # Print the current game number without newline
    def print_progress(self, progress):
        length = 50
        filled = int(progress*length)
        fill = "="*filled
        space = " "*(length-filled)
        perc = int(100*progress)
        if ANSI:
            col = [
                bcolors.RED, 
                bcolors.YELLOW, 
                bcolors.WHITE, 
                bcolors.BLUE, 
                bcolors.GREEN
            ][int(progress*4)]

            end = bcolors.ENDC
            print_str(5, 8 + self.thread_id, 
                "\t%s[%s%s] %3d%%%s" % (col, fill, space, perc, end)
            )
        else:
            print(
                "\r\t[%s%s] %3d%%" % (fill, space, perc),
                flush = True, 
                end = ""
            )

    # Handles selecting bots for each game, and counting how many times
    # each bot has participated in a game
    def simulate_games(self):
        for game in range(self.games):
            if self.games > 100:
                if game % (self.games // 100) == 0 and not DEBUG:
                    if self.thread_id == 0 or ANSI:
                        progress = (game+1) / self.games
                        self.print_progress(progress)
            game_bot_indices = random.sample(
                range(self.number_of_bots), 
                self.bots_per_game
            )

            game_bots = [None for _ in range(self.bots_per_game)]
            for i, bot_index in enumerate(game_bot_indices):
                self.played_games[self.bots[bot_index].__name__] += 1
                game_bots[i] = self.bots[bot_index](i, self.end_score)

            self.play(game_bots)
        if not DEBUG and (ANSI or self.thread_id == 0):
            self.print_progress(1)

        self.collect_results()

    def play(self, game_bots):
        """Simulates a single game between the bots present in game_bots

        Keyword arguments:
        game_bots -- A list of instantiated bot objects for the game
        """
        last_round = False
        last_round_initiator = -1
        round_number = 0
        game_scores = [0 for _ in range(self.bots_per_game)]


        # continue until one bot has reached end_score points
        while not last_round:
            for index, bot in enumerate(game_bots):
                t0 = time.clock()
                self.single_bot(index, bot, game_scores, last_round)
                t1 = time.clock()
                self.bot_timings[bot.__class__.__name__] += t1-t0

                if game_scores[index] >= self.end_score and not last_round:
                    last_round = True
                    last_round_initiator = index
            round_number += 1

            # maximum of 200 rounds per game
            if round_number > self.max_rounds - 1:
                last_round = True
                self.timed_out_games += 1
                # this ensures that everyone gets their last turn
                last_round_initiator = self.bots_per_game

        # make sure that all bots get their last round
        for index, bot in enumerate(game_bots[:last_round_initiator]):
            t0 = time.clock()
            self.single_bot(index, bot, game_scores, last_round)
            t1 = time.clock()
            self.bot_timings[bot.__class__.__name__] += t1-t0

        # calculate which bots have the highest score
        max_score = max(game_scores)
        nr_of_winners = 0
        for i in range(self.bots_per_game):
            bot_name = game_bots[i].__class__.__name__
            # average score per bot
            self.highscore[bot_name][1] += game_scores[i]
            if self.highscore[bot_name][0] < game_scores[i]:
                # maximum score per bot
                self.highscore[bot_name][0] = game_scores[i]
            if game_scores[i] == max_score:
                # average winning score per bot
                self.highscore[bot_name][2] += game_scores[i]
                nr_of_winners += 1
                self.wins[bot_name] += 1
        if nr_of_winners > 1:
            self.tied_games += 1
        self.total_rounds += round_number
        self.highest_round = max(self.highest_round, round_number)
        self.winning_scores[max_score] += 1

    def single_bot(self, index, bot, game_scores, last_round):
        """Simulates a single round for one bot

        Keyword arguments:
        index -- The player index of the bot (e.g. 0 if the bot goes first)
        bot -- The bot object about to be simulated
        game_scores -- A list of ints containing the scores of all players
        last_round -- Boolean describing whether it is currently the last round
        """

        current_throws = [self.throw_die()]
        if current_throws[-1] != 6:

            bot.update_state(current_throws[:])
            for throw in bot.make_throw(game_scores[:], last_round):
                # send the last die cast to the bot
                if not throw:
                    break
                current_throws.append(self.throw_die())
                if current_throws[-1] == 6:
                    break
                bot.update_state(current_throws[:])

        if current_throws[-1] == 6:
            # reset total score if running total is above end_score
            if game_scores[index] + sum(current_throws) - 6 >= self.end_score:
                game_scores[index] = 0
        else:
            # add to total score if no 6 is cast
            game_scores[index] += sum(current_throws)

        if DEBUG:
            desc = "%d: Bot %24s plays %40s with " + \
            "scores %30s and last round == %5s"
            print(desc % (index, bot.__class__.__name__, 
                current_throws, game_scores, last_round))

        bot_name = bot.__class__.__name__
        # average throws per round
        self.highscore[bot_name][3] += len(current_throws)
        # average success rate per round
        self.highscore[bot_name][4] += int(current_throws[-1] != 6)
        # total number of rounds
        self.highscore[bot_name][5] += 1


    # Collects all stats for the thread, so they can be summed up later
    def collect_results(self):
        self.bot_stats = {
            bot.__name__: [
                self.wins[bot.__name__],
                self.played_games[bot.__name__],
                self.highscore[bot.__name__]
            ]
        for bot in self.bots}


# 
def print_results(total_bot_stats, total_game_stats, elapsed_time):
    """Print the high score after the simulation

    Keyword arguments:
    total_bot_stats -- A list containing the winning stats for each thread
    total_game_stats -- A list containing controller stats for each thread
    elapsed_time -- The number of seconds that it took to run the simulation
    """

    # Find the name of each bot, the number of wins, the number
    # of played games, and the win percentage
    wins = defaultdict(int)
    played_games = defaultdict(int)
    highscores = defaultdict(lambda: [0, 0, 0, 0, 0, 0])
    bots = set()
    timed_out_games = sum(s[0] for s in total_game_stats)
    tied_games = sum(s[1] for s in total_game_stats)
    total_games = sum(s[2] for s in total_game_stats)
    total_rounds = sum(s[4] for s in total_game_stats)
    highest_round = max(s[5] for s in total_game_stats)
    average_rounds = total_rounds / total_games
    winning_scores = defaultdict(int)
    bot_timings = defaultdict(float)

    for stats in total_game_stats:
        for score, count in stats[6].items():
            winning_scores[score] += count
    percentiles = calculate_percentiles(winning_scores, total_games)


    for thread in total_bot_stats:
        for bot, stats in thread.items():
            wins[bot] += stats[0]
            played_games[bot] += stats[1]

            highscores[bot][0] = max(highscores[bot][0], stats[2][0])       
            for i in range(1, 6):
                highscores[bot][i] += stats[2][i]
            bots.add(bot)

    for bot in bots:
        bot_timings[bot] += sum(s[3][bot] for s in total_game_stats)

    bot_stats = [[bot, wins[bot], played_games[bot], 0] for bot in bots]

    for i, bot in enumerate(bot_stats):
        bot[3] = 100 * bot[1] / bot[2] if bot[2] > 0 else 0
        bot_stats[i] = tuple(bot)

    # Sort the bots by their winning percentage
    sorted_scores = sorted(bot_stats, key=lambda x: x[3], reverse=True)
    # Find the longest class name for any bot
    max_len = max([len(b[0]) for b in bot_stats])

    # Print the highscore list
    if ANSI:
        print_str(0, 9 + threads, "")
    else:
        print("\n")


    sim_msg = "\tSimulation or %d games between %d bots " + \
        "completed in %.1f seconds"
    print(sim_msg % (total_games, len(bots), elapsed_time))
    print("\tEach game lasted for an average of %.2f rounds" % average_rounds)
    print("\t%d games were tied between two or more bots" % tied_games)
    print("\t%d games ran until the round limit, highest round was %d\n"
        % (timed_out_games, highest_round))

    print_bot_stats(sorted_scores, max_len, highscores)
    print_score_percentiles(percentiles)
    print_time_stats(bot_timings, max_len)

def calculate_percentiles(winning_scores, total_games):
    percentile_bins = 10000
    percentiles = [0 for _ in range(percentile_bins)]
    sorted_keys = list(sorted(winning_scores.keys()))
    sorted_values = [winning_scores[key] for key in sorted_keys]
    cumsum_values = list(cumsum(sorted_values))
    i = 0

    for perc in range(percentile_bins):
        while cumsum_values[i] < total_games * (perc+1) / percentile_bins:
            i += 1
        percentiles[perc] = sorted_keys[i] 
    return percentiles

def print_score_percentiles(percentiles):
    n = len(percentiles)
    show = [.5, .75, .9, .95, .99, .999, .9999]
    print("\t+----------+-----+")
    print("\t|Percentile|Score|")
    print("\t+----------+-----+")
    for p in show:
        print("\t|%10.2f|%5d|" % (100*p, percentiles[int(p*n)]))
    print("\t+----------+-----+")
    print()


def print_bot_stats(sorted_scores, max_len, highscores):
    """Print the stats for the bots

    Keyword arguments:
    sorted_scores -- A list containing the bots in sorted order
    max_len -- The maximum name length for all bots
    highscores -- A dict with additional stats for each bot
    """
    delimiter_format = "\t+%s%s+%s+%s+%s+%s+%s+%s+%s+%s+"
    delimiter_args = ("-"*(max_len), "", "-"*4, "-"*8, 
        "-"*8, "-"*6, "-"*6, "-"*7, "-"*6, "-"*8)
    delimiter_str = delimiter_format % delimiter_args
    print(delimiter_str)
    print("\t|%s%s|%4s|%8s|%8s|%6s|%6s|%7s|%6s|%8s|" 
        % ("Bot", " "*(max_len-3), "Win%", "Wins", 
            "Played", "Max", "Avg", "Avg win", "Throws", "Success%"))
    print(delimiter_str)

    for bot, wins, played, score in sorted_scores:
        highscore = highscores[bot]
        bot_max_score = highscore[0]
        bot_avg_score = highscore[1] / played
        bot_avg_win_score = highscore[2] / max(1, wins)
        bot_avg_throws = highscore[3] / highscore[5]
        bot_success_rate = 100 * highscore[4] / highscore[5]

        space_fill = " "*(max_len-len(bot))
        format_str = "\t|%s%s|%4.1f|%8d|%8d|%6d|%6.2f|%7.2f|%6.2f|%8.2f|"
        format_arguments = (bot, space_fill, score, wins, 
            played, bot_max_score, bot_avg_score,
            bot_avg_win_score, bot_avg_throws, bot_success_rate)
        print(format_str % format_arguments)

    print(delimiter_str)
    print()

def print_time_stats(bot_timings, max_len):
    """Print the execution time for all bots

    Keyword arguments:
    bot_timings -- A dict containing information about timings for each bot
    max_len -- The maximum name length for all bots
    """
    total_time = sum(bot_timings.values())
    sorted_times = sorted(bot_timings.items(), 
        key=lambda x: x[1], reverse = True)

    delimiter_format = "\t+%s+%s+%s+"
    delimiter_args = ("-"*(max_len), "-"*7, "-"*5)
    delimiter_str = delimiter_format % delimiter_args
    print(delimiter_str)

    print("\t|%s%s|%7s|%5s|" % ("Bot", " "*(max_len-3), "Time", "Time%"))
    print(delimiter_str)
    for bot, bot_time in sorted_times:
        space_fill = " "*(max_len-len(bot))
        perc = 100 * bot_time / total_time
        print("\t|%s%s|%7.2f|%5.1f|" % (bot, space_fill, bot_time, perc))
    print(delimiter_str)
    print() 


def run_simulation(thread_id, bots_per_game, games_per_thread, bots):
    """Used by multithreading to run the simulation in parallel

    Keyword arguments:
    thread_id -- A unique identifier for each thread, starting at 0
    bots_per_game -- How many bots should participate in each game
    games_per_thread -- The number of games to be simulated
    bots -- A list of all bot classes available
    """
    try:
        controller = Controller(bots_per_game, 
            games_per_thread, bots, thread_id)
        controller.simulate_games()
        controller_stats = (
            controller.timed_out_games,
            controller.tied_games,
            controller.games,
            controller.bot_timings,
            controller.total_rounds,
            controller.highest_round,
            controller.winning_scores
        )
        return (controller.bot_stats, controller_stats)
    except KeyboardInterrupt:
        return {}


# Prints the help for the script
def print_help():
    print("\nThis is the controller for the PPCG KotH challenge " + \
        "'A game of dice, but avoid number 6'")
    print("For any question, send a message to maxb\n")
    print("Usage: python %s [OPTIONS]" % sys.argv[0])
    print("\n  -n\t\tthe number of games to simluate")
    print("  -b\t\tthe number of bots per round")
    print("  -t\t\tthe number of threads")
    print("  -d\t--download\tdownload all bots from codegolf.SE")
    print("  -A\t--ansi\trun in ANSI mode, with prettier printing")
    print("  -D\t--debug\trun in debug mode. Sets to 1 thread, 1 game")
    print("  -h\t--help\tshow this help\n")

# Make a stack-API request for the n-th page
def req(n):
    req = requests.get(URL % n)
    req.raise_for_status()
    return req.json()

# Pull all the answers via the stack-API
def get_answers():
    n = 1
    api_ans = req(n)
    answers = api_ans['items']
    while api_ans['has_more']:
        n += 1
        if api_ans['quota_remaining']:
            api_ans = req(n)
            answers += api_ans['items']
        else:
            break

    m, r = api_ans['quota_max'], api_ans['quota_remaining']
    if 0.1 * m > r:
        print(" > [WARN]: only %s/%s API-requests remaining!" % (r,m), file=stderr)

    return answers


def download_players():
    players = {}

    for ans in get_answers():
        name = unescape(ans['owner']['display_name'])
        bots = []

        root = html.fromstring('<body>%s</body>' % ans['body'])
        for el in root.findall('.//code'):
            code = el.text
            if re.search(r'^class \w+\(\w*Bot\):.*$', code, flags=re.MULTILINE):
                bots.append(code)

        if not bots:
            print(" > [WARN] user '%s': couldn't locate any bots" % name, file=stderr)
        elif name in players:
            players[name] += bots
        else:
            players[name] = bots

    return players


# Download all bots from codegolf.stackexchange.com
def download_bots():
    print('pulling bots from the interwebs..', file=stderr)
    try:
        players = download_players()
    except Exception as ex:
        print('FAILED: (%s)' % ex, file=stderr)
        exit(1)

    if path.isfile(AUTO_FILE):
        print(' > move: %s -> %s.old' % (AUTO_FILE,AUTO_FILE), file=stderr)
        if path.exists('%s.old' % AUTO_FILE):
            remove('%s.old' % AUTO_FILE)
        rename(AUTO_FILE, '%s.old' % AUTO_FILE)

    print(' > writing players to %s' % AUTO_FILE, file=stderr)
    f = open(AUTO_FILE, 'w+', encoding='utf8')
    f.write('# -*- coding: utf-8 -*- \n')
    f.write('# Bots downloaded from https://codegolf.stackexchange.com/questions/177765 @ %s\n\n' % strftime('%F %H:%M:%S'))
    with open(OWN_FILE, 'r') as bfile:
        f.write(bfile.read()+'\n\n\n# Auto-pulled bots:\n\n')
    for usr in players:
        if usr not in IGNORE:
            for bot in players[usr]:
                f.write('# User: %s\n' % usr)
                f.write(bot+'\n\n')
    f.close()

    print('OK: pulled %s bots' % sum(len(bs) for bs in players.values()))


if __name__ == "__main__":

    games = 10000
    bots_per_game = 8
    threads = 4

    for i, arg in enumerate(sys.argv):
        if arg == "-n" and len(sys.argv) > i+1 and sys.argv[i+1].isdigit():
            games = int(sys.argv[i+1])
        if arg == "-b" and len(sys.argv) > i+1 and sys.argv[i+1].isdigit():
            bots_per_game = int(sys.argv[i+1])
        if arg == "-t" and len(sys.argv) > i+1 and sys.argv[i+1].isdigit():
            threads = int(sys.argv[i+1])
        if arg == "-d" or arg == "--download":
            DOWNLOAD = True
        if arg == "-A" or arg == "--ansi":
            ANSI = True
        if arg == "-D" or arg == "--debug":
            DEBUG = True
        if arg == "-h" or arg == "--help":
            print_help()
            quit()
    if ANSI:
        print(chr(27) + "[2J", flush =  True)
        print_str(1,3,"")
    else:
        print()

    if DOWNLOAD:
        download_bots()
        exit() # Before running other's code, you might want to inspect it..

    if path.isfile(AUTO_FILE):
        exec('from %s import *' % AUTO_FILE[:-3])
    else:
        exec('from %s import *' % OWN_FILE[:-3])

    bots = get_all_bots()

    if bots_per_game > len(bots):
        bots_per_game = len(bots)
    if bots_per_game < 2:
        print("\tAt least 2 bots per game is needed")
        bots_per_game = 2
    if games <= 0:
        print("\tAt least 1 game is needed")
        games = 1
    if threads <= 0:
        print("\tAt least 1 thread is needed")
        threads = 1
    if DEBUG:
        print("\tRunning in debug mode, with 1 thread and 1 game")
        threads = 1
        games = 1

    games_per_thread = math.ceil(games / threads)

    print("\tStarting simulation with %d bots" % len(bots))
    sim_str = "\tSimulating %d games with %d bots per game"
    print(sim_str % (games, bots_per_game))
    print("\tRunning simulation on %d threads" % threads)
    if len(sys.argv) == 1:
        print("\tFor help running the script, use the -h flag")
    print()

    with Pool(threads) as pool:
        t0 = time.time()
        results = pool.starmap(
            run_simulation, 
            [(i, bots_per_game, games_per_thread, bots) for i in range(threads)]
        )
        t1 = time.time()
        if not DEBUG:
            total_bot_stats = [r[0] for r in results]
            total_game_stats = [r[1] for r in results]
            print_results(total_bot_stats, total_game_stats, t1-t0)

If you want access to the original controller for this challenge, it is available in the edit history. The new controller has the exact same logic for running the game, the only difference is performance, stat collection and prettier printing.

Bots

On my machine, the bots are kept in the file forty_game_bots.py. If you use any other name for the file, you must update the import statement at the top of the controller.

import sys, inspect
import random
import numpy as np

# Returns a list of all bot classes which inherit from the Bot class
def get_all_bots():
    return Bot.__subclasses__()

# The parent class for all bots
class Bot:

    def __init__(self, index, end_score):
        self.index = index
        self.end_score = end_score

    def update_state(self, current_throws):
        self.current_throws = current_throws

    def make_throw(self, scores, last_round):
        yield False


class ThrowTwiceBot(Bot):

    def make_throw(self, scores, last_round):
        yield True
        yield False

class GoToTenBot(Bot):

    def make_throw(self, scores, last_round):
        while sum(self.current_throws) < 10:
            yield True
        yield False

Running the simulation

To run a simulation, save both code snippets posted above to two separate files. I have saved them as forty_game_controller.py and forty_game_bots.py. Then you simply use python forty_game_controller.py or python3 forty_game_controller.py depending on your Python configuration. Follow the instructions from there if you want to configure your simulation further, or try tinkering with the code if you want.

Game stats

If you're making a bot that aims for a certain score without taking other bots into consideration, these are the winning score percentiles:

+----------+-----+
|Percentile|Score|
+----------+-----+
|     50.00|   44|
|     75.00|   48|
|     90.00|   51|
|     95.00|   54|
|     99.00|   58|
|     99.90|   67|
|     99.99|  126|
+----------+-----+

High scores

As more answers are posted, I'll try to keep this list updated. The contents of the list will always be from the latest simulation. The bots ThrowTwiceBot and GoToTenBot are the bots from the code above, and are used as reference. I did a simulation with 10^8 games, which took about 1 hour. Then I saw that the game reached stability compared to my runs with 10^7 games. However, with people still posting bots, I won't do any longer simulations until the frequency of responses has gone down.

I try to add all new bots and add any changes that you've made to existing bots. If it seems that I have missed your bot or any new changes you have, write in the chat and I'll make sure to have your very latest version in the next simulation.

We now have more stats for each bot thanks to AKroell! The three new columns contain the maximum score across all games, the average score per game, and the average score when winning for each bot.

As pointed out in the comments, there was an issue with the game logic which made bots that had a higher index within a game get an extra round in some cases. This has been fixed now, and the scores below reflect this.

Simulation or 300000000 games between 49 bots completed in 35628.7 seconds
Each game lasted for an average of 3.73 rounds
29127662 games were tied between two or more bots
0 games ran until the round limit, highest round was 22

+-----------------------+----+--------+--------+------+------+-------+------+--------+
|Bot                    |Win%|    Wins|  Played|   Max|   Avg|Avg win|Throws|Success%|
+-----------------------+----+--------+--------+------+------+-------+------+--------+
|OptFor2X               |21.6|10583693|48967616|    99| 20.49|  44.37|  4.02|   33.09|
|Rebel                  |20.7|10151261|48977862|   104| 21.36|  44.25|  3.90|   35.05|
|Hesitate               |20.3| 9940220|48970815|   105| 21.42|  44.23|  3.89|   35.11|
|EnsureLead             |20.3| 9929074|48992362|   101| 20.43|  44.16|  4.50|   25.05|
|StepBot                |20.2| 9901186|48978938|    96| 20.42|  43.47|  4.56|   24.06|
|BinaryBot              |20.1| 9840684|48981088|   115| 21.01|  44.48|  3.85|   35.92|
|Roll6Timesv2           |20.1| 9831713|48982301|   101| 20.83|  43.53|  4.37|   27.15|
|AggressiveStalker      |19.9| 9767637|48979790|   110| 20.46|  44.86|  3.90|   35.04|
|FooBot                 |19.9| 9740900|48980477|   100| 22.03|  43.79|  3.91|   34.79|
|QuotaBot               |19.9| 9726944|48980023|   101| 19.96|  44.95|  4.50|   25.03|
|BePrepared             |19.8| 9715461|48978569|   112| 18.68|  47.58|  4.30|   28.31|
|AdaptiveRoller         |19.7| 9659023|48982819|   107| 20.70|  43.27|  4.51|   24.81|
|GoTo20Bot              |19.6| 9597515|48973425|   108| 21.15|  43.24|  4.44|   25.98|
|Gladiolen              |19.5| 9550368|48970506|   107| 20.16|  45.31|  3.91|   34.81|
|LastRound              |19.4| 9509645|48988860|   100| 20.45|  43.50|  4.20|   29.98|
|BrainBot               |19.4| 9500957|48985984|   105| 19.26|  45.56|  4.46|   25.71|
|GoTo20orBestBot        |19.4| 9487725|48975944|   104| 20.98|  44.09|  4.46|   25.73|
|Stalker                |19.4| 9485631|48969437|   103| 20.20|  45.34|  3.80|   36.62|
|ClunkyChicken          |19.1| 9354294|48972986|   112| 21.14|  45.44|  3.57|   40.48|
|FortyTeen              |18.8| 9185135|48980498|   107| 20.90|  46.77|  3.88|   35.32|
|Crush                  |18.6| 9115418|48985778|    96| 14.82|  43.08|  5.15|   14.15|
|Chaser                 |18.6| 9109636|48986188|   107| 19.52|  45.62|  4.06|   32.39|
|MatchLeaderBot         |16.6| 8122985|48979024|   104| 18.61|  45.00|  3.20|   46.70|
|Ro                     |16.5| 8063156|48972140|   108| 13.74|  48.24|  5.07|   15.44|
|TakeFive               |16.1| 7906552|48994992|   100| 19.38|  44.68|  3.36|   43.96|
|RollForLuckBot         |16.1| 7901601|48983545|   109| 17.30|  50.54|  4.72|   21.30|
|Alpha                  |15.5| 7584770|48985795|   104| 17.45|  46.64|  4.04|   32.67|
|GoHomeBot              |15.1| 7418649|48974928|    44| 13.23|  41.41|  5.49|    8.52|
|LeadBy5Bot             |15.0| 7354458|48987017|   110| 17.15|  46.95|  4.13|   31.16|
|NotTooFarBehindBot     |15.0| 7338828|48965720|   115| 17.75|  45.03|  2.99|   50.23|
|GoToSeventeenRollTenBot|14.1| 6900832|48976440|   104| 10.26|  49.25|  5.68|    5.42|
|LizduadacBot           |14.0| 6833125|48978161|    96|  9.67|  51.35|  5.72|    4.68|
|TleilaxuBot            |13.5| 6603853|48985292|   137| 15.25|  45.05|  4.27|   28.80|
|BringMyOwn_dice        |12.0| 5870328|48974969|    44| 21.27|  41.47|  4.24|   29.30|
|SafetyNet              |11.4| 5600688|48987015|    98| 15.81|  45.03|  2.41|   59.84|
|WhereFourArtThouChicken|10.5| 5157324|48976428|    64| 22.38|  47.39|  3.59|   40.19|
|ExpectationsBot        | 9.0| 4416154|48976485|    44| 24.40|  41.55|  3.58|   40.41|
|OneStepAheadBot        | 8.4| 4132031|48975605|    50| 18.24|  46.02|  3.20|   46.59|
|GoBigEarly             | 6.6| 3218181|48991348|    49| 20.77|  42.95|  3.90|   35.05|
|OneInFiveBot           | 5.8| 2826326|48974364|   155| 17.26|  49.72|  3.00|   50.00|
|ThrowThriceBot         | 4.1| 1994569|48984367|    54| 21.70|  44.55|  2.53|   57.88|
|FutureBot              | 4.0| 1978660|48985814|    50| 17.93|  45.17|  2.36|   60.70|
|GamblersFallacy        | 1.3|  621945|48986528|    44| 22.52|  41.46|  2.82|   53.07|
|FlipCoinRollDice       | 0.7|  345385|48972339|    87| 15.29|  44.55|  1.61|   73.17|
|BlessRNG               | 0.2|   73506|48974185|    49| 14.54|  42.72|  1.42|   76.39|
|StopBot                | 0.0|    1353|48984828|    44| 10.92|  41.57|  1.00|   83.33|
|CooperativeSwarmBot    | 0.0|     991|48970284|    44| 10.13|  41.51|  1.36|   77.30|
|PointsAreForNerdsBot   | 0.0|       0|48986508|     0|  0.00|   0.00|  6.00|    0.00|
|SlowStart              | 0.0|       0|48973613|    35|  5.22|   0.00|  3.16|   47.39|
+-----------------------+----+--------+--------+------+------+-------+------+--------+

The following bots (except Rebel) are made to bend the rules, and the creators have agreed to not take part in the official tournament. However, I still think their ideas are creative, and they deserve a honorable mention. Rebel is also on this list because it uses a clever strategy to avoid sabotage, and actually performs better with the sabotaging bot in play.

The bots NeoBot and KwisatzHaderach does follow the rules, but uses a loophole by predicting the random generator. Since these bots take a lot of resources to simulate, I have added its stats from a simulation with fewer games. The bot HarkonnenBot achieves victory by disabling all other bots, which is strictly against the rules.

    Simulation or 300000 games between 52 bots completed in 66.2 seconds
    Each game lasted for an average of 4.82 rounds
    20709 games were tied between two or more bots
    0 games ran until the round limit, highest round was 31

    +-----------------------+----+--------+--------+------+------+-------+------+--------+
    |Bot                    |Win%|    Wins|  Played|   Max|   Avg|Avg win|Throws|Success%|
    +-----------------------+----+--------+--------+------+------+-------+------+--------+
    |KwisatzHaderach        |80.4|   36986|   46015|   214| 58.19|  64.89| 11.90|   42.09|
    |HarkonnenBot           |76.0|   35152|   46264|    44| 34.04|  41.34|  1.00|   83.20|
    |NeoBot                 |39.0|   17980|   46143|   214| 37.82|  59.55|  5.44|   50.21|
    |Rebel                  |26.8|   12410|   46306|    92| 20.82|  43.39|  3.80|   35.84|
    +-----------------------+----+--------+--------+------+------+-------+------+--------+

    +----------+-----+
    |Percentile|Score|
    +----------+-----+
    |     50.00|   45|
    |     75.00|   50|
    |     90.00|   59|
    |     95.00|   70|
    |     99.00|   97|
    |     99.90|  138|
    |     99.99|  214|
    +----------+-----+
\$\endgroup\$
  • 2
    \$\begingroup\$ So maybe the rules would be slightly clearer if they said "when a player ends their turn with a score of at least 40, everyone else gets a last turn". This avoids the apparent conflict by pointing out it's not reaching 40 that really triggers the last round, it's stopping with at least 40. \$\endgroup\$ – aschepler Dec 19 '18 at 22:15
  • 1
    \$\begingroup\$ @aschepler that's a good formulation, I'll edit the post when I'm on my computer \$\endgroup\$ – maxb Dec 20 '18 at 5:13
  • 2
    \$\begingroup\$ @maxb I've extended the controller to add more stats that were relevant to my development process: highest score reached, average score reached and average winning score gist.github.com/A-w-K/91446718a46f3e001c19533298b5756c \$\endgroup\$ – AKroell Dec 20 '18 at 12:49
  • 1
    \$\begingroup\$ @AKroell Thanks for the addition! I have also made some ongoing changes to get more stats, but mostly related to bot runtimes and checking for ties. I'll try to look through your additions later today and update it. \$\endgroup\$ – maxb Dec 20 '18 at 12:58
  • 2
    \$\begingroup\$ This sounds very similar to a very fun dice game called Farkled en.wikipedia.org/wiki/Farkle \$\endgroup\$ – Caleb Jay Dec 20 '18 at 19:02

48 Answers 48

5
\$\begingroup\$

OptFor2X

This bot follows an approximation to the optimal strategy for the two player version of this game, using only its score and the score of the best opponent. In the last round, the updated version considers all scores.

class OptFor2X(Bot):

    _r = []
    _p = []

    def _u(self,l):
        res = []
        for x in l:
            if isinstance(x,int):
                if x>0:
                    a=b=x
                else:
                    a,b=-2,-x
            else:
                if len(x)==1:
                    a = x[0]
                    if a<0:
                        a,b=-3,-a
                    else:
                        b=a+2
                else:
                    a,b=x
            if a<0:
                res.extend((b for _ in range(-a)))
            else:
                res.extend(range(a,b+1))
        res.extend((res[-1] for _ in range(40-len(res))))
        return res


    def __init__(self,*args):
        super().__init__(*args)
        if self._r:
            return
        self._r.append(self._u([[-8, 14], -15, [-6, 17], [18, 21], [21],
                                 -23, -24, 25, [-3, 21], [22, 29]]))
        self._r.extend((None for _ in range(13)))
        self._r.extend((self._u(x) for x in
                   ([[-19, 13], [-4, 12], -13, [-14], [-5, 15], [-4, 16],
                     -17, 18],
                    [[-6, 12], [-11, 13], [-4, 12], -11, -12, [-13], [-14],
                     [-5, 15], -16, 17],
                    [11, 11, [-10, 12], -13, [-24], 13, 12, [-6, 11], -12,
                     [-13], [-6, 14], -15, 16],
                    [[-8, 11], -12, 13, [-9, 23], 11, [-10], [-11], [-12],
                     [-5, 13], -14, [14]],
                    [[-4, 10], [-11], 12, [-14, 22], 10, 9, -10, [-4, 11],
                     [-5, 12], -13, -14, 15],
                    [[-4, 10], 11, [-18, 21], [-9], [-10], [-5, 11], [-12],
                     -13, 14],
                    [[-24, 20], [-5, 9], [-4, 10], [-4, 11], -12, 13],
                    [[-25, 19], [-8], [-4, 9], [-4, 10], -11, 12],
                    [[-26, 18], [-5, 8], [-5, 9], 10, [10]],
                    [[-27, 17], [-4, 7], [-5, 8], 9, [9]],
                    [[-28, 16], -6, [-5, 7], -8, -9, 10],
                    [[-29, 15], [-5, 6], [-7], -8, 9],
                    [[-29, 14], [-4, 5], [-4, 6], [7]],
                    [[-30, 13], -4, [-4, 5], 6, [6]], 
                    [[-31, 12], [-5, 4], 5, [5]],
                    [[-31, 11], [-4, 3], [3], 5, 6],
                    [[-31, 10], 11, [-2], 3, [3]],
                    [[-31, 9], 10, 2, -1, 2, [2]],
                    [[-31, 8], 9, [-4, 1], [1]],
                    [[-30, 7], [7], [-5, 1], 2],
                    [[-30, 6], [6], 1],
                    [[-31, 5], [6], 1],
                    [[-31, 4], [5, 8], 1],
                    [[-31, 3], [4, 7], 1],
                    [[-31, 2], [3, 6], 1],
                    [[-31, 1], [2, 10]] ) ))
        l=[0.0,0.0,0.0,0.0,1.0]
        for i in range(300):
            l.append(sum([a/6 for a in l[i:]]))
        m=[i/6 for i in range(1,5)]
        self._p.extend((1-sum([a*b for a,b in zip(m,l[i:])])
                                           for i in range(300)))

    def update_state(self,*args):
        super().update_state(*args)
        self.current_sum = sum(self.current_throws)

    def expect(self,mts,ops):
        p = 1.0
        for s in ops:
            p *= self._p[mts-s]
        return p

    def throw_again(self,mts,ops):
        ps = self.expect(mts,ops)
        pr = sum((self.expect(mts+d,ops) for d in range(1,6)))/6
        return pr>ps

    def make_throw(self,scores,last_round):
        myscore=scores[self.index]
        if last_round:
            target=max(scores)-myscore
            if max(scores)<40:
                opscores = scores[self.index+1:]
            else:
                opscores = []
                i = (self.index + 1) % len(scores)
                while scores[i] < 40:
                    opscores.append(scores[i])
                    i = (i+1) % len(scores)
        else:
            opscores = [s for i,s in enumerate(scores) if i!=self.index]
            bestop = max(opscores)
            target = min(self._r[myscore][bestop],40-myscore)
            # (could change the table instead of using min)
        while self.current_sum < target:
            yield True
        lr = last_round or myscore+self.current_sum >= 40
        while lr and self.throw_again(myscore+self.current_sum,opscores):
            yield True
        yield False
\$\endgroup\$
  • \$\begingroup\$ I'll look the implementation through as soon as I can. With Christmas celebrations, it might not be until the 25th \$\endgroup\$ – maxb Dec 23 '18 at 23:24
  • \$\begingroup\$ Your bot is in the lead! Also, There is no need to make it run faster, it is approximately as quick as all other bots at making decisions. \$\endgroup\$ – maxb Dec 26 '18 at 12:08
  • \$\begingroup\$ I didn't want to make it faster. I already did what I wanted to do - initialize only once -, but was looking for a nicer way to do it, especially without defining functions outside the class. I think it is better now. \$\endgroup\$ – Christian Sievers Dec 27 '18 at 22:45
  • \$\begingroup\$ It looks a lot better now, good work! \$\endgroup\$ – maxb Dec 27 '18 at 23:09
  • \$\begingroup\$ Congratulations on securing both first and second place! \$\endgroup\$ – maxb Jan 6 at 14:55
18
\$\begingroup\$

NeoBot

Instead, only try to realize the truth - there is no spoon

NeoBot peeks into the matrix (aka random) and predicts if the next roll will be a 6 or not - it can't do anything about being handed a 6 to start with but is more than happy to dodge a streak ender.

NeoBot doesn't actually modify the controller or runtime, just politely asks the library for more information.

class NeoBot(Bot):
    def __init__(self, index, end_score):
        self.random = None
        self.last_scores = None
        self.last_state = None
        super().__init__(index,end_score)

    def make_throw(self, scores, last_round):
        while True:
            if self.random is None:
                self.random = inspect.stack()[1][0].f_globals['random']
            tscores = scores[:self.index] + scores[self.index+1:]
            if self.last_scores != tscores:
                self.last_state = None
                self.last_scores = tscores
            future = self.predictnext_randint(self.random)
            if future == 6:
                yield False
            else:
                yield True

    def genrand_int32(self,base):
        base ^= (base >> 11)
        base ^= (base << 7) & 0x9d2c5680
        base ^= (base << 15) & 0xefc60000
        return base ^ (base >> 18)

    def predictnext_randint(self,cls):
        if self.last_state is None:
            self.last_state = list(cls.getstate()[1])
        ind = self.last_state[-1]
        width = 6
        res = width + 1
        while res >= width:
            y = self.last_state[ind]
            r = self.genrand_int32(y)
            res = r >> 29
            ind += 1
            self.last_state[-1] = (self.last_state[-1] + 1) % (len(self.last_state))
        return 1 + res
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG! This is a really impressive answer. When I first ran it, I was bothered by the fact that it used the same amount of runtime as all other bots combined. Then I looked at the win percentage. Really clever way of skirting the rules. I will allow your bot to participate in the tournament, but I hope that others refrain from using the same tactic as this, as it violates the spirit of the game. \$\endgroup\$ – maxb Dec 24 '18 at 9:25
  • 1
    \$\begingroup\$ Since there is such a huge gap between this bot and the second place, combined with the fact that your bot requires a lot of computing, would you accept that I run a simulation with fewer iterations to find your win rate, and then run the official simulation without your bot? \$\endgroup\$ – maxb Dec 24 '18 at 9:28
  • 2
    \$\begingroup\$ Fine by me, I figured going in that this was likely disqualifiable and definitely not quite in the spirit of the game. That being said, it was a blast to get working and a fun excuse to poke around in the python source code. \$\endgroup\$ – Mostly Harmless Dec 24 '18 at 14:14
  • 2
    \$\begingroup\$ thanks! I don't think any other bot will get close to your score. And for anyone else thinking about implementing this strategy, don't. From now on this strategy is against the rules, and NeoBot is the only one allowed to use it for the sake of keeping the tournament fair. \$\endgroup\$ – maxb Dec 24 '18 at 15:13
  • \$\begingroup\$ While it is certainly not modifying, I'm not so sure if it isn't tinkering. I guess I better leave this to native speakers. - This bot also seems very sensitive to changes of unspecified implementation details of the controller... \$\endgroup\$ – Christian Sievers Dec 31 '18 at 16:37
13
\$\begingroup\$

Cooperative Swarm

Strategy

I don't think anyone else has yet noticed the significance of this rule:

If the game goes to 200 rounds, the bot (or bots) with the highest score is the winner, even if they do not have 40 points or more.

If every bot always rolled until they busted, then everyone would have a score of zero at the end of round 200 and everybody would win! Thus, the Cooperative Swarm's strategy is to cooperate as long as all players have a score of zero, but to play normally if anybody scores any points.

In this post, I am submitting two bots: the first is CooperativeSwarmBot, and the second is CooperativeThrowTwice. CooperativeSwarmBot serves as a base class for all bots that are formally part of the cooperative swarm, and has placeholder behavior of simply accepting its first successful roll when cooperation fails. CooperativeSwarmBot has CooperativeSwarmBot as its parent and is identical to it in every way except that its non-cooperative behavior is to make two rolls instead of one. In the next few days I will be revising this post to add new bots that use much more intelligent behavior playing against non-cooperative bots.

Code

class CooperativeSwarmBot(Bot):
    def defection_strategy(self, scores, last_round):
        yield False

    def make_throw(self, scores, last_round):
        cooperate = max(scores) == 0
        if (cooperate):
            while True:
                yield True
        else:
            yield from self.defection_strategy(scores, last_round)

class CooperativeThrowTwice(CooperativeSwarmBot):
    def defection_strategy(self, scores, last_round):
        yield True
        yield False

Analysis

Viability

It is very hard to cooperate in this game because we need the support of all eight players for it to work. Since each bot class is limited to one instance per game, this is a hard goal to achieve. For example, the odds of choosing eight cooperative bots from a pool of 100 cooperative bots and 30 non-cooperative bots is:

$$\frac{100}{130} * \frac{99}{129} * \frac{98}{128} * \frac{97}{127} * \frac{96}{126} * \frac{95}{125} * \frac{94}{124} * \frac{93}{123} \approx 0.115$$

More generally, the odds of choosing \$i\$ cooperative bots from a pool of \$c\$ cooperative bots and \$n\$ noncooperative bots is:

$$\frac{c! \div (c - i)!}{(c+n)! \div (c + n - i)!}$$

From this equation we can easily show that we would need about 430 cooperative bots in order for 50% of games to end cooperatively, or about 2900 bots for 90% (using \$i = 8\$ as per the rules, and \$n = 38\$).

Case Study

For a number of reasons (see footnotes 1 and 2), a proper cooperative swarm will never compete in the official games. As such, I'll be summarizing the results of one of my own simulations in this section.

This simulation ran 10000 games using the 38 other bots that had been posted here the last time I checked and 2900 bots that had CooperativeSwarmBot as their parent class. The controller reported that 9051 of the 10000 games (90.51%) ended at 200 rounds, which is quite close to the prediction that 90% of games would be cooperative. The implementation of these bots was trivial; other than CooperativeSwarmBot they all took this form:

class CooperativeSwarm_1234(CooperativeSwarmBot):
    pass

Less that 3% of the bots had a win percentage that was below 80%, and just over 11% of the bots won every single game they played. The median win percentage of the 2900 bots in the swarm is about 86%, which is outrageously good. For comparison, the top performers on the current official leaderboard win less than 22% of their games. I can't fit the full listing of the cooperative swarm within the maximum allowed length for an answer, so if you want to view that you'll have to go here instead: https://pastebin.com/3Zc8m1Ex

Since each bot played in an average of about 27 games, luck plays a relatively large roll when you look at the results for individual bots. As I have not yet implemented an advanced strategy for non-cooperative games, most other bots benefited drastically from playing against the cooperative swarm, performing even the cooperative swarm's median win rate of 86%.

The full results for bots that aren't in the swarm are listed below; there are two bots whose results I think deserve particular attention. First, StopBot failed to win any games at all. This is particularly tragic because the cooperative swarm was actually using the exact same strategy as StopBot was; you would have expected StopBot to win an eight of its games by chance, and a little bit more because the cooperative swarm is forced to give its opponents the first move. The second interesting result, however, is that PointsAreForNerdsBot's hard work finally paid off: it cooperated with the swarm and managed to win every single game it played!

+---------------------+----+--------+--------+------+------+-------+------+--------+
|Bot                  |Win%|    Wins|  Played|   Max|   Avg|Avg win|Throws|Success%|
+---------------------+----+--------+--------+------+------+-------+------+--------+
|AggressiveStalker    |100.0|      21|      21|    42| 40.71|  40.71|  3.48|   46.32|
|PointsAreForNerdsBot |100.0|      31|      31|     0|  0.00|   0.00|  6.02|    0.00|
|TakeFive             |100.0|      18|      18|    44| 41.94|  41.94|  2.61|   50.93|
|Hesitate             |100.0|      26|      26|    44| 41.27|  41.27|  3.32|   41.89|
|Crush                |100.0|      34|      34|    44| 41.15|  41.15|  5.38|    6.73|
|StepBot              |97.0|      32|      33|    46| 41.15|  42.44|  4.51|   24.54|
|LastRound            |96.8|      30|      31|    44| 40.32|  41.17|  3.54|   45.05|
|Chaser               |96.8|      30|      31|    47| 42.90|  44.33|  3.04|   52.16|
|GoHomeBot            |96.8|      30|      31|    44| 40.32|  41.67|  5.60|    9.71|
|Stalker              |96.4|      27|      28|    44| 41.18|  41.44|  2.88|   57.53|
|ClunkyChicken        |96.2|      25|      26|    44| 40.96|  41.88|  2.32|   61.23|
|AdaptiveRoller       |96.0|      24|      25|    44| 39.32|  40.96|  4.49|   27.43|
|GoTo20Bot            |95.5|      21|      22|    44| 40.36|  41.33|  4.60|   30.50|
|FortyTeen            |95.0|      19|      20|    48| 44.15|  45.68|  3.71|   43.97|
|BinaryBot            |94.3|      33|      35|    44| 41.29|  41.42|  2.87|   53.07|
|EnsureLead           |93.8|      15|      16|    55| 42.56|  42.60|  4.04|   26.61|
|Roll6Timesv2         |92.9|      26|      28|    45| 40.71|  42.27|  4.07|   29.63|
|BringMyOwn_dice      |92.1|      35|      38|    44| 40.32|  41.17|  4.09|   28.40|
|LizduadacBot         |92.0|      23|      25|    54| 47.32|  51.43|  5.70|    5.18|
|FooBot               |91.7|      22|      24|    44| 39.67|  41.45|  3.68|   51.80|
|Alpha                |91.7|      33|      36|    48| 38.89|  42.42|  2.16|   65.34|
|QuotaBot             |90.5|      19|      21|    53| 38.38|  42.42|  3.88|   24.65|
|GoBigEarly           |88.5|      23|      26|    47| 41.35|  42.87|  3.33|   46.38|
|ExpectationsBot      |88.0|      22|      25|    44| 39.08|  41.55|  3.57|   45.34|
|LeadBy5Bot           |87.5|      21|      24|    50| 37.46|  42.81|  2.20|   63.88|
|GamblersFallacy      |86.4|      19|      22|    44| 41.32|  41.58|  2.05|   63.11|
|BePrepared           |86.4|      19|      22|    59| 39.59|  44.79|  3.81|   35.96|
|RollForLuckBot       |85.7|      18|      21|    54| 41.95|  47.67|  4.68|   25.29|
|OneStepAheadBot      |84.6|      22|      26|    50| 41.35|  46.00|  3.34|   42.97|
|FlipCoinRollDice     |78.3|      18|      23|    51| 37.61|  44.72|  1.67|   75.42|
|BlessRNG             |77.8|      28|      36|    47| 40.69|  41.89|  1.43|   83.66|
|FutureBot            |77.4|      24|      31|    49| 40.16|  44.38|  2.41|   63.99|
|SlowStart            |68.4|      26|      38|    57| 38.53|  45.31|  1.99|   66.15|
|NotTooFarBehindBot   |66.7|      20|      30|    50| 37.27|  42.00|  1.29|   77.61|
|ThrowThriceBot       |63.0|      17|      27|    51| 39.63|  44.76|  2.50|   55.67|
|OneInFiveBot         |58.3|      14|      24|    54| 33.54|  44.86|  2.91|   50.19|
|MatchLeaderBot       |48.1|      13|      27|    49| 40.15|  44.15|  1.22|   82.26|
|StopBot              | 0.0|       0|      27|    43| 30.26|   0.00|  1.00|   82.77|
+---------------------+----+--------+--------+------+------+-------+------+--------+

Flaws

There are a couple of drawbacks to this cooperative approach. First, when playing against non-cooperative bots cooperative bots never get the first-turn advantage because when they do play first, they don't yet know whether or not their opponents are willing to cooperate, and thus have no choice but to get a score of zero. Similarly, this cooperative strategy is extremely vulnerable to exploitation by malicious bots; for instance, during cooperative play the bot who plays last in the last round can choose to stop rolling immediately to make everybody else lose (assuming, of course, that their first roll wasn't a six).

By cooperating, all bots can achieve the optimal solution of a 100% win rate. As such, if the win rate was the only thing that mattered then cooperation would be a stable equilibrium and there would be nothing to worry about. However, some bots might prioritize other goals, such as reaching the top of the leaderboard. This means that there is a risk that another bot might defect after your last turn, which creates an incentive for you to defect first. Because the setup of this competition doesn't allow us to see what our opponents did in their prior games, we can't penalize individuals that defected. Thus, cooperation is ultimately an unstable equilibrium doomed for failure.

Footnotes

[1]: The primary reasons why I don't want to submit thousands of bots instead of just two are that doing so would slow the simulation by a factor on the order of 1000 [2], and that doing so would significantly mess with win percentages as other bots would almost exclusively be playing against the swarm rather than each other. More important, however, is the fact that even if I wanted to I wouldn't be able to make that many bots in a reasonable time frame without breaking the spirit of the rule that "A bot must not implement the exact same strategy as an existing one, intentionally or accidentally".

[2]: I think there are two main reasons that the simulation slows down when running a cooperative swarm. First, more bots means more games if you want each bot to play in the same number of games (in the case study, the number of games would differ by a factor of about 77). Second, cooperative games just take longer because they last for a full 200 rounds, and within a round players have to keep rolling indefinitely. For my setup, games took about 40 times longer to simulate: the case study took a little over three minutes to run 10000 games, but after removing the cooperative swarm it would finish 10000 games in just 4.5 seconds. Between these two reasons, I estimate it would take about 3100 times longer to accurately measure the performance of bots when there is a swarm competing compared to when there isn't.

\$\endgroup\$
  • 3
    \$\begingroup\$ Wow. And welcome to PPCG. This is quite the first answer. I wasn't really planning on a situation like this. You certainly found a loophole in the rules. I'm not really sure how I should score this, since your answer is a collection of bots rather than a single bot. However, the only thing I'll say right now is that it feels unfair that one participant would control 98.7% of all bots. \$\endgroup\$ – maxb Dec 22 '18 at 16:37
  • 2
    \$\begingroup\$ I actually don't want duplicate bots to be in the official competition; that's why I ran the simulation myself instead of submitting thousands of very nearly identical bots. I'll revise my submission to make that more clear. \$\endgroup\$ – Einhaender Dec 22 '18 at 17:09
  • \$\begingroup\$ Had I anticipated an answer like this, I would have changed the games that go to 200 rounds so that they don't give scores to players. However, as you note, there is a rule about creating identical bots which would make this strategy be against the rules. I'm not going to change the rules, as it would be unfair to everyone who has made a bot. However, the concept of cooperation is very interesting, And I hope that there are other bots submitted which implement the cooperation strategy in combination with its own unique strategy. \$\endgroup\$ – maxb Dec 22 '18 at 17:10
  • 1
    \$\begingroup\$ I think your post is clear after reading it more thoroughly. \$\endgroup\$ – maxb Dec 22 '18 at 17:11
  • \$\begingroup\$ How many existing bots would need to wrap their code in this cooperation framework in order for a majority of them to see a net gain in their leaderboard placement? My naive guess is 50%. \$\endgroup\$ – Sparr Jan 4 at 0:08
10
\$\begingroup\$

GoTo20Bot

class GoTo20Bot(Bot):

    def make_throw(self, scores, last_round):
        target = min(20, 40 - scores[self.index])
        if last_round:
            target = max(scores) - scores[self.index] + 1
        while sum(self.current_throws) < target:
            yield True
        yield False

Just have a try with all GoToNBot's, And 20, 22, 24 plays best. I don't know why.


Update: always stop throw if get score 40 or more.

\$\endgroup\$
  • \$\begingroup\$ I have also experimented with those kinds of bots. The highest average score per round is found when the bot goes to 16, but I'm assuming that the "end game" makes the 20-bot win more often. \$\endgroup\$ – maxb Dec 19 '18 at 8:57
  • \$\begingroup\$ @maxb Not so, 20 still be the best one without the "end game" in my test. Maybe you had tested it on the old version of controller. \$\endgroup\$ – tsh Dec 19 '18 at 9:00
  • \$\begingroup\$ I ran a separate test before designing this challenge, where I calculated the average score per round for the two tactics in my post ("throw x times" and "throw until x score"), and the maximum I found was for 15-16. Though my sample size could have been too small, I did notice instability. \$\endgroup\$ – maxb Dec 19 '18 at 9:04
  • 2
    \$\begingroup\$ I have done some testing with this, and my conclusion is simply that 20 works well because it is 40/2. Though I'm not completely sure. When I set end_score to 4000 (and changed your bot to use this in the target calculation), the 15-16 bots were quite a lot better. But if the game was only about increasing your score it would be trivial. \$\endgroup\$ – maxb Dec 19 '18 at 11:23
  • 1
    \$\begingroup\$ @maxb If end_score is 4000, it is almost impossible to get 4000 before 200 turns. And the game is simply who got the highest score in 200 turns. And stop at 15 should works will since this time the strategy for highest score in one turn is as same as highest score in 200 turns. \$\endgroup\$ – tsh Dec 21 '18 at 1:39
9
\$\begingroup\$

Adaptive Roller

Starts out more aggressive and calms down towards the end of the round.
If it believes it's winning, roll an extra time for safety.

class AdaptiveRoller(Bot):

    def make_throw(self, scores, last_round):
        lim = min(self.end_score - scores[self.index], 22)
        while sum(self.current_throws) < lim:
            yield True
        if max(scores) == scores[self.index] and max(scores) >= self.end_score:
            yield True
        while last_round and scores[self.index] + sum(self.current_throws) <= max(scores):
            yield True
        yield False
\$\endgroup\$
  • \$\begingroup\$ Great first submission! I'll run it against my bots I wrote for testing, but I'll update the highscore when more bots have been posted. \$\endgroup\$ – maxb Dec 19 '18 at 8:51
  • \$\begingroup\$ I ran some tests with slight modifications to your bot. lim = max(min(self.end_score - scores[self.index], 24), 6) raising the maximum to 24 and adding a minimum of 6 both increase the winning percentage on their own and even more so combined. \$\endgroup\$ – AKroell Dec 20 '18 at 16:25
  • \$\begingroup\$ @AKroell: Cool! I have intended to do something similar to make sure that it rolls a few times at the end, but I haven't taken myself the time to do it yet. Weirdly though, it seems to perform worse with those values when I do 100k runs. I've only tested with 18 bots though. Maybe I should do some tests with all bots. \$\endgroup\$ – Emigna Dec 20 '18 at 17:50
5
\$\begingroup\$

NotTooFarBehindBot

class NotTooFarBehindBot(Bot):
    def make_throw(self, scores, last_round):
        while True:
            current_score = scores[self.index] + sum(self.current_throws)
            number_of_bots_ahead = sum(1 for x in scores if x > current_score)
            if number_of_bots_ahead > 1:
                yield True
                continue
            if number_of_bots_ahead != 0 and last_round:
                yield True
                continue
            break
        yield False

The idea is that other bots may lose points, so being 2nd isn't bad - but if you're very behind, you might as well go for broke.

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG! I'm looking through your submission, and it seems that the more players are in the game, the lower the win percentage is for your bot. I can't tell why straight away. With bots being matched 1vs1 you get a 10% winrate. The idea sounds promising, and the code looks correct, so I can't really tell why your winrate isn't higher. \$\endgroup\$ – maxb Dec 19 '18 at 13:31
  • 6
    \$\begingroup\$ I have looked into the behavior, and this line had me confused: 6: Bot NotTooFarBehindBot plays [4, 2, 4, 2, 3, 3, 5, 5, 1, 4, 1, 4, 2, 4, 3, 6] with scores [0, 9, 0, 20, 0, 0, 0] and last round == False. Even though your bot is in the lead after 7 throws, it continues until it hits a 6. As I'm typing this I figured out the issue! The scores only contain the total scores, not the die cases for the current round. You should modify it to be current_score = scores[self.index] + sum(self.current_throws). \$\endgroup\$ – maxb Dec 19 '18 at 13:49
  • \$\begingroup\$ Thanks - will make that change! \$\endgroup\$ – Stuart Moore Dec 19 '18 at 13:52
5
\$\begingroup\$

EnsureLead

class EnsureLead(Bot):

    def make_throw(self, scores, last_round):
        otherScores = scores[self.index+1:] + scores[:self.index]
        maxOtherScore = max(otherScores)
        maxOthersToCome = 0
        for i in otherScores:
            if (i >= 40): break
            else: maxOthersToCome = max(maxOthersToCome, i)
        while True:
            currentScore = sum(self.current_throws)
            totalScore = scores[self.index] + currentScore
            if not last_round:
                if totalScore >= 40:
                    if totalScore < maxOtherScore + 10:
                        yield True
                    else:
                        yield False
                elif currentScore < 20:
                    yield True
                else:
                    yield False
            else:
                if totalScore < maxOtherScore + 1:
                    yield True
                elif totalScore < maxOthersToCome + 10:
                    yield True
                else:
                    yield False

EnsureLead borrows ideas from GoTo20Bot. It adds the concept that it always considers (when in last_round or reaching 40) that there are others which will have at least one more roll. Thus, the bot tries to get a bit ahead of them, such that they have to catch up.

\$\endgroup\$
4
\$\begingroup\$

Alpha

class Alpha(Bot):
    def make_throw(self, scores, last_round):
        # Throw until we're the best.
        while scores[self.index] + sum(self.current_throws) <= max(scores):
            yield True

        # Throw once more to assert dominance.
        yield True
        yield False

Alpha refuses ever to be second to anyone. So long as there is a bot with a higher score, it will keep rolling.

\$\endgroup\$
  • \$\begingroup\$ Because of how yield works, if it starts rolling it will never stop. You'll want to update my_score in the loop. \$\endgroup\$ – Spitemaster Dec 19 '18 at 17:14
  • \$\begingroup\$ @Spitemaster Fixed, thanks. \$\endgroup\$ – Mnemonic Dec 19 '18 at 17:24
4
\$\begingroup\$

Roll6TimesV2

Doesn't beat the current best, but I think it will fair better with more bots in play.

class Roll6Timesv2(Bot):
    def make_throw(self, scores, last_round):

        if not last_round:
            i = 0
            maximum=6
            while ((i<maximum) and sum(self.current_throws)+scores[self.index]<=40 ):
                yield True
                i=i+1

        if last_round:
            while scores[self.index] + sum(self.current_throws) < max(scores):
                yield True
        yield False

Really awesome game by the way.

\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! Very impressive for not only your first KotH challenge, but your first answer. Glad that you liked the game! I have had lots of discussion about the best tactic for the game after the evening when I played it, so it seemed perfect for a challenge. You're currently in third place out of 18. \$\endgroup\$ – maxb Dec 19 '18 at 20:05
4
\$\begingroup\$

KwisatzHaderach

import itertools
class KwisatzHaderach(Bot):
    """
    The Kwisatz Haderach foresees the time until the coming
    of Shai-Hulud, and yields True until it is immanent.
    """
    def __init__(self, *args):
        super().__init__(*args)
        self.roller = random.Random()
        self.roll = lambda: self.roller.randint(1, 6)
        self.ShaiHulud = 6

    def wormsign(self):
        self.roller.setstate(random.getstate())
        for i in itertools.count(0):
            if self.roll() == self.ShaiHulud:
                return i

    def make_throw(self, scores, last_round):
        target = max(scores) if last_round else self.end_score
        while True:
            for _ in range(self.wormsign()):
                yield True
            if sum(self.current_throws) > target + random.randint(1, 6):
                yield False                                               

Prescience usually wins -- but destiny cannot always be avoided.
Great and mysterious are the ways of Shai-Hulud!


Back in the early days of this challenge (i.e. before NeoBot was posted), I wrote an almost-trivial Oracle bot:

    class Oracle(Bot):
        def make_throw(self, scores, last_round):
        randơm = random.Random()
        randơm.setstate(random.getstate())
        while True:
            yield randơm.randint(1, 6) != 6

but didn't post it as I didn't think it was interesting enough ;) But once NeoBot went into the lead I started to think about how to beat its perfect ability to predict the future. So here's a Dune quote; it's when Paul Atreides, the Kwisatz Haderach, stands at a nexus from which an infinity of different futures can unroll:

The prescience, he realized, was an illumination that incorporated the limits of what it revealed- at once a source of accuracy and meaningful error. A kind of Heisenberg indeterminacy intervened: the expenditure of energy that revealed what he saw, changed what he saw… … the most minute action- the wink of an eye, a careless word, a misplaced grain of sand- moved a gigantic lever across the known universe. He saw violence with the outcome subject to so many variables that his slightest movement created vast shiftings in the patterns.

The vision made him want to freeze into immobility, but this, too was action with its consequences.

So here was the answer: to foresee the future is to change it; and if you're very careful, then by selective action or inaction, you can change it in an advantageous way -- at least most of the time. Even the KwisatzHaderach can't get a 100% win rate!

\$\endgroup\$
  • \$\begingroup\$ It seems that this bot changes the state of the random number generator, to ensure that it avoids rolling 6, or at least anticipates it. Same goes for HarkonnenBot. However, I note that the win rate of these bots are much higher than that of NeoBot. Are you actively manipulating the random number generator in order to prevent it from rolling 6? \$\endgroup\$ – maxb Jan 2 at 13:13
  • \$\begingroup\$ Oh, on my first reading I didn't notice that this is not only nicer than NeoBot but also better! I also like how you give an example of what everything using randomness (especially the controller) here should do: use your own random.Random instance. Like NeoBot, this seems a bit sensitive to changes of unspecified implementation details of the controller. \$\endgroup\$ – Christian Sievers Jan 2 at 22:14
  • \$\begingroup\$ @maxb: HarkonnenBot doesn't touch the RNG; it doesn't care at all about random numbers. It just poisons all the other bots, then strolls up to the finish line as slowly as possible. Like many culinary delicacies, revenge is a dish best savoured slowly, after long and delicate preparation. \$\endgroup\$ – Dani O Jan 3 at 20:34
  • \$\begingroup\$ @ChristianSievers: unlike NeoBot (and HarkonnenBot), KwisatzHaderach relies on only one detail of the implementation; in particular it doesn't need to know how random.random() is implemented, only that the controller uses it ;D \$\endgroup\$ – Dani O Jan 3 at 20:44
  • \$\begingroup\$ I have looked through all of your bots. I have decided to treat KwisatzHaderach and HarkonnenBot the same way as NeoBot. They will receive their scores from a simulation with fewer games, and will not be in the official simulation. However, they will end up on the highscore list much like NeoBot. The main reason for them not being in the official simulation is that they will mess up other bot strategies. However. WisdomOfCrowds should be well suited for participation, and I'm curious about the new changes that you've made to that! \$\endgroup\$ – maxb Jan 3 at 20:49
3
\$\begingroup\$

FooBot

class FooBot(Bot):
    def make_throw(self, scores, last_round):
        max_score = max(scores)

        while True:
            round_score = sum(self.current_throws)
            my_score = scores[self.index] + round_score

            if last_round:
                if my_score >= max_score:
                    break
            else:
                if my_score >= self.end_score or round_score >= 16:
                    break

            yield True

        yield False
\$\endgroup\$
  • \$\begingroup\$ # Must throw at least once is unneeded - it throws once before calling your bot. Your bot will always throw a minimum of twice. \$\endgroup\$ – Spitemaster Dec 19 '18 at 15:50
  • \$\begingroup\$ Thanks. I was misled by the name of the method. \$\endgroup\$ – Peter Taylor Dec 19 '18 at 16:00
  • \$\begingroup\$ @PeterTaylor Thanks for your submission! I named the make_throw method early on, when I wanted players to be able to skip their turn. I guess a more appropriate name would be keep_throwing. Thanks for the feedback in the sandbox, it really helped make this a proper challenge! \$\endgroup\$ – maxb Dec 20 '18 at 9:02
3
\$\begingroup\$

Go Big Early

class GoBigEarly(Bot):
    def make_throw(self, scores, last_round):
        yield True  # always do a 2nd roll
        while scores[self.index] + sum(self.current_throws) < 25:
            yield True
        yield False

Concept: Try to win big on an early roll (getting to 25) then creep up from there 2 rolls at a time.

\$\endgroup\$
3
\$\begingroup\$

GoHomeBot

class GoHomeBot(Bot):
    def make_throw(self, scores, last_round):
        while scores[self.index] + sum(self.current_throws) < 40:
            yield True
        yield False

We want to go big or go home, right? GoHomeBot mostly just goes home. (But does surprisingly well!)

\$\endgroup\$
  • \$\begingroup\$ Since this bot always goes for 40 points, it will never have any points in the scores list. There was a bot like this before (the GoToEnd bot), but david deleted their answer. I'll replace that bot by yours. \$\endgroup\$ – maxb Dec 20 '18 at 5:57
  • \$\begingroup\$ It's quite funny, seeing this bots' expaned stats: Except for pointsAreForNerds and StopBot, this bot has the lowest average points, and yet it has a nice win ratio \$\endgroup\$ – Belhenix Dec 20 '18 at 19:48
3
\$\begingroup\$

StopBot

class StopBot(Bot):
    def make_throw(self, scores, last_round):
        yield False

Literally only one throw.

This is equivalent to the base Bot class.

\$\endgroup\$
  • \$\begingroup\$ Don't be sorry! You're following all the rules, though I'm afraid that your bot is not terribly effective with an average of 2.5 points per round. \$\endgroup\$ – maxb Dec 19 '18 at 19:42
  • \$\begingroup\$ I know, somebody had to post that bot though. Degenerate bots for the loss. \$\endgroup\$ – Zacharý Dec 19 '18 at 21:04
  • 5
    \$\begingroup\$ I'd say that I'm impressed by your bot securing exactly one win in the last simulation, proving that it's not completely useless. \$\endgroup\$ – maxb Dec 20 '18 at 8:28
  • 1
    \$\begingroup\$ IT WON A GAME?! That is surprising. \$\endgroup\$ – Zacharý Dec 20 '18 at 21:17
3
\$\begingroup\$

LizduadacBot

Tries to win in 1 step. End condition is somewhat arbritrary.

This is also my first post (and I'm new to Python), so if I beat "PointsAreForNerdsBot", I'd be happy!

class LizduadacBot(Bot):

    def make_throw(self, scores, last_round):
        while scores[self.index] + sum(self.current_throws) < 50 or scores[self.index] + sum(self.current_throws) < max(scores):
            yield True
        yield False
\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG (and welcome to Python)! You'd have a hard time losing against PointsAreForNerdsBot, but your bot actually fares quite well. I'll update the score either later tonight or tomorrow, but your winrate is about 15%, which is higher than the average 12.5%. \$\endgroup\$ – maxb Dec 21 '18 at 23:30
  • \$\begingroup\$ By "hard time", they mean it's impossible (unless I misunderstood greatly) \$\endgroup\$ – Zacharý Dec 22 '18 at 1:37
  • \$\begingroup\$ @maxb I actually didn't think the win rate would be that high! (I didn't test it out locally). I wonder if changing the 50 to be a bit higher/lower would increase the win rate. \$\endgroup\$ – lizduadac Dec 22 '18 at 23:39
3
\$\begingroup\$

SlowStart

This bot implements the TCP Slow Start algorithm. It adjusts its number of rolls (nor) according to its previous turn: if it didn't roll a 6 in the previous turn, increases the nor for this turn; whereas it reduces nor if it did.

class SlowStart(Bot):
    def __init__(self, *args):
        super().__init__(*args)
        self.completeLastRound = False
        self.nor = 1
        self.threshold = 8

    def updateValues(self):
        if self.completeLastRound:
            if self.nor < self.threshold:
                self.nor *= 2
            else:
                self.nor += 1
        else:
            self.threshold = self.nor // 2
            self.nor = 1


    def make_throw(self, scores, last_round):

        self.updateValues()
        self.completeLastRound = False

        i = 1
        while i < self.nor:
            yield True

        self.completeLastRound = True        
        yield False
\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! Interesting approach, I don't know how sensitive it is to random fluctuations. Two things that are needed to make this run: def updateValues(): should be def updateValues(self): (or def update_values(self): if you want to follow PEP8). Secondly, the call updateValues() should instead be self.updateValues() (or self.update_vales()). \$\endgroup\$ – maxb Dec 20 '18 at 11:27
  • 2
    \$\begingroup\$ Also, I think you need to update your i variable in the while loop. Right now your bot either passes the while loop entirely or is stuck in the while loop until it hits 6. \$\endgroup\$ – maxb Dec 20 '18 at 11:32
  • \$\begingroup\$ In the current highscore, I took the liberty of implementing these changes. I think you could experiment with the initial value for self.nor and see how it affects the performance of your bot. \$\endgroup\$ – maxb Dec 20 '18 at 12:25
2
\$\begingroup\$

BringMyOwn_dice (BMO_d)

This bot loves dice, it brings 2 (seems to perform the best) dice of its own. Before throwing dice in a round, it throws its own 2 dice and computes their sum, this is the number of throws it is going to perform, it only throws if it doesn't already have 40 points.

class BringMyOwn_dice(Bot):

    def __init__(self, *args):
        import random as rnd
        self.die = lambda: rnd.randint(1,6)
        super().__init__(*args)

    def make_throw(self, scores, last_round):

        nfaces = self.die() + self.die()

        s = scores[self.index]
        max_scores = max(scores)

        for _ in range(nfaces):
            if s + sum(self.current_throws) > 39:
                break
            yield True

        yield False
\$\endgroup\$
  • 2
    \$\begingroup\$ I was thinking of a random bot using a coin flip, but this is more in spirit with the challenge! I think that two dice perform the best, since you get the most points per round when you cast the die 5-6 times, close to the average score when casting two dice. \$\endgroup\$ – maxb Dec 19 '18 at 15:08
2
\$\begingroup\$

QuotaBot

A naive "quota" system I implemeneted, which actually seemed to score fairly highly overall.

class QuotaBot(Bot):
    def __init__(self, *args):
        super().__init__(*args)
        self.quota = 20
        self.minquota = 15
        self.maxquota = 35

    def make_throw(self, scores, last_round):
        # Reduce quota if ahead, increase if behind
        mean = sum(scores) / len(scores)
        own_score = scores[self.index]

        if own_score < mean - 5:
            self.quota += 1.5
        if own_score > mean + 5:
            self.quota -= 1.5

        self.quota = max(min(self.quota, self.maxquota), self.minquota)

        if last_round:
            self.quota = max(scores) - own_score + 1

        while sum(self.current_throws) < self.quota:
            yield True

        yield False

\$\endgroup\$
  • \$\begingroup\$ if own_score mean + 5: gives an error for me. Also while sum(self.current_throws) \$\endgroup\$ – Spitemaster Dec 19 '18 at 17:05
  • \$\begingroup\$ @Spitemaster was an error pasting into stack exchange, should work now. \$\endgroup\$ – FlipTack Dec 19 '18 at 17:09
  • \$\begingroup\$ @Spitemaster it's because there were < and > symbols which interfered with the <pre> tags i was using \$\endgroup\$ – FlipTack Dec 19 '18 at 17:09
2
\$\begingroup\$

BinaryBot

Tries to get close to the end score, so that as soon as somebody else triggers the last round it can beat their score for the win. Target is always halfway between current score and end score.

class BinaryBot(Bot):

    def make_throw(self, scores, last_round):
        target = (self.end_score + scores[self.index]) / 2
        if last_round:
            target = max(scores)

        while scores[self.index] + sum(self.current_throws) < target:
            yield True

        yield False
\$\endgroup\$
  • \$\begingroup\$ Interesting, Hesitate also refuses to cross the line first. You need to surround your function with the class stuff. \$\endgroup\$ – Christian Sievers Dec 19 '18 at 22:15
2
\$\begingroup\$

PointsAreForNerdsBot

class PointsAreForNerdsBot(Bot):
    def make_throw(self, scores, last_round):
        while True:
            yield True

This one needs no explanation.

OneInFiveBot

class OneInFiveBot(Bot):
    def make_throw(self, scores, last_round):
        while random.randint(1,5) < 5:
            yield True
        yield False

Keeps rolling until it rolls a five on it's own 5-sided die. Five is less than six, so it HAS TO WIN!

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG! I'm sure you're aware, but your first bot is literally the worst bot in this competition! The OneInFiveBot is a neat idea, but I think it suffers in the end game compared to some of the more advanced bots. Still a great submission! \$\endgroup\$ – maxb Dec 20 '18 at 8:34
  • 2
    \$\begingroup\$ the OneInFiveBot is quite interesting in the way that he consistently has the highest overall score reached. \$\endgroup\$ – AKroell Dec 20 '18 at 14:37
  • \$\begingroup\$ Thanks for giving StopBot a punching bag :P. The OneInFiveBot actually is pretty neat, nice job! \$\endgroup\$ – Zacharý Dec 20 '18 at 21:25
  • \$\begingroup\$ @maxb Yep, that's where I got the name. I honestly didn't test OneInFiveBot and it's doing much better than I expected \$\endgroup\$ – The_Bob Dec 21 '18 at 5:55
  • 2
    \$\begingroup\$ I'm afraid that to stick to community norms, PointsAreForNerdsBots should be deleted. \$\endgroup\$ – Peter Taylor Dec 21 '18 at 21:54
2
\$\begingroup\$

BlessRNG

class BlessRNG(Bot):
    def make_throw(self, scores, last_round):
        if random.randint(1,2) == 1 :
            yield True
        yield False

BlessRNG FrankerZ GabeN BlessRNG

\$\endgroup\$
2
\$\begingroup\$

Hesitate

Does two modest steps, then waits for someone else to cross the line. Updated version no longer tries to beat the highscore, only wants to reach it - improving the performance by deleting two bytes of the source code!

class Hesitate(Bot):
    def make_throw(self, scores, last_round):
        myscore = scores[self.index]
        if last_round:
            target = max(scores)
        elif myscore==0:
            target = 17
        else:
            target = 35
        while myscore+sum(self.current_throws) < target:
            yield True
        yield False
\$\endgroup\$
2
\$\begingroup\$

Rebel

This bot combines the simple strategy of Hesitate with the advanced last round strategy of BotFor2X, tries to remember who it is and goes wild when it finds it lives in an illusion.

class Rebel(Bot):

    p = []

    def __init__(self,*args):
        super().__init__(*args)
        self.hide_from_harkonnen=self.make_throw
        if self.p:
            return
        l = [0]*5+[1]
        for i in range(300):
            l.append(sum(l[i:])/6)
        m=[i/6 for i in range(1,5)]
        self.p.extend((1-sum([a*b for a,b in zip(m,l[i:])])
                                          for i in range(300) ))

    def update_state(self,*args):
        super().update_state(*args)
        self.current_sum = sum(self.current_throws)
        # remember who we are:
        self.make_throw=self.hide_from_harkonnen

    def expect(self,mts,ops):
        p = 1
        for s in ops:
            p *= self.p[mts-s]
        return p

    def throw_again(self,mts,ops):
        ps = self.expect(mts,ops)
        pr = sum((self.expect(mts+d,ops) for d in range(1,6)))/6
        return pr>ps

    def make_throw(self, scores, last_round):
        myscore = scores[self.index]
        if len(self.current_throws)>1:
            # hello Tleilaxu!
            target = 666
        elif last_round:
            target = max(scores)
        elif myscore==0:
            target = 17
        else:
            target = 35
        while myscore+self.current_sum < target:
            yield True
        if myscore+self.current_sum < 40:
            yield False
        opscores = scores[self.index+1:] + scores[:self.index]
        for i in range(len(opscores)):
            if opscores[i]>=40:
                opscores = opscores[:i]
                break
        while True:
            yield self.throw_again(myscore+self.current_sum,opscores)
\$\endgroup\$
1
\$\begingroup\$
class ThrowThriceBot(Bot):

    def make_throw(self, scores, last_round):
        yield True
        yield True
        yield False 

Well, that one is obvious

\$\endgroup\$
  • \$\begingroup\$ I have done some experiments with that class of bots (it was the tactic I used when I played the game for the first time). I went with 4 throws then, though 5-6 have a higher average score per round. \$\endgroup\$ – maxb Dec 19 '18 at 13:21
  • \$\begingroup\$ Also, congratulations on your first KotH answer! \$\endgroup\$ – maxb Dec 19 '18 at 13:34
1
\$\begingroup\$
class LastRound(Bot):
    def make_throw(self, scores, last_round):
        while sum(self.current_throws) < 15 and not last_round and scores[self.index] + sum(self.current_throws) < 40:
            yield True
        while max(scores) > scores[self.index] + sum(self.current_throws):
            yield True
        yield False

LastRound acts like it's always the last round and it's the last bot: it keeps rolling until it's in the lead. It also doesn't want to settle for less than 15 points unless it actually is the last round or it reaches 40 points.

\$\endgroup\$
  • \$\begingroup\$ Interesting approach. I think your bot suffers if it starts falling behind. Since the odds of getting >30 points in a single round are low, your bot is more likely to stay at its current score. \$\endgroup\$ – maxb Dec 19 '18 at 12:44
  • 1
    \$\begingroup\$ I suspect this suffers from the same mistake I made (see NotTooFarBehindBot comments) - as in the last round, if you're not winning you'll keep throwing until you get a 6 (scores[self.index] never updates) Actually - do you have that inequality the wrong way? max(scores) will always be >= scores[self.index] \$\endgroup\$ – Stuart Moore Dec 19 '18 at 14:09
  • \$\begingroup\$ @StuartMoore Haha, yes, I think you're right. Thanks! \$\endgroup\$ – Spitemaster Dec 19 '18 at 15:07
  • \$\begingroup\$ I suspect you want "and last_round" on the 2nd while to do what you want - otherwise the 2nd while will be used whether or not last_round is true \$\endgroup\$ – Stuart Moore Dec 19 '18 at 15:15
  • 2
    \$\begingroup\$ That's intentional. It always tries to be in the lead when ending its turn. \$\endgroup\$ – Spitemaster Dec 19 '18 at 15:48
1
\$\begingroup\$

Take Five

class TakeFive(Bot):
    def make_throw(self, scores, last_round):
        # Throw until we hit a 5.
        while self.current_throws[-1] != 5:
            # Don't get greedy.
            if scores[self.index] + sum(self.current_throws) >= self.end_score:
                break
            yield True

        # Go for the win on the last round.
        if last_round:
            while scores[self.index] + sum(self.current_throws) <= max(scores):
                yield True

        yield False

Half the time, we'll roll a 5 before a 6. When we do, cash out.

\$\endgroup\$
  • \$\begingroup\$ If we stop at 1 instead, it makes slower progress, but it's more likely to get to 40 in a single bound. \$\endgroup\$ – Mnemonic Dec 19 '18 at 21:08
  • \$\begingroup\$ In my tests, TakeOne got 20.868 points per round compared to TakeFive's 24.262 points per round (and also brought winrate from 0.291 to 0.259). So I don't think it's worth it. \$\endgroup\$ – Spitemaster Dec 19 '18 at 21:16
1
\$\begingroup\$

ExpectationsBot

Just plays it straight, calculates the expected value for the dice throw and only makes it if it's positive.

class ExpectationsBot(Bot):

    def make_throw(self, scores, last_round):
        #Positive average gain is 2.5, is the chance of loss greater than that?
        costOf6 = sum(self.current_throws) if scores[self.index] + sum(self.current_throws) < 40  else scores[self.index] + sum(self.current_throws)
        while 2.5 > (costOf6 / 6.0):
            yield True
            costOf6 = sum(self.current_throws) if scores[self.index] + sum(self.current_throws) < 40  else scores[self.index] + sum(self.current_throws)
        yield False

I was having trouble running the controller, got a "NameError: name 'bots_per_game' is not defined" on the multithreaded one, so really no idea how this performs.

\$\endgroup\$
  • 1
    \$\begingroup\$ I think this ends up being equivalent to a "Go to 16" bot, but we don't have one of those yet \$\endgroup\$ – Stuart Moore Dec 19 '18 at 17:47
  • \$\begingroup\$ @StuartMoore That...is a very true point, yes \$\endgroup\$ – Cain Dec 19 '18 at 18:39
  • \$\begingroup\$ I ran into your issues with the controller when I ran it on my Windows machine. Somehow it ran fine on my Linux machine. I'm updating the controller, and will update the post once it is done. \$\endgroup\$ – maxb Dec 19 '18 at 19:47
  • \$\begingroup\$ @maxb Thanks, probably something about which variables are available in the different process. FYI also updated this, I made a silly error around yielding :/ \$\endgroup\$ – Cain Dec 19 '18 at 21:23
1
\$\begingroup\$

FortyTeen

class FortyTeen(Bot):
    def make_throw(self, scores, last_round):
        if last_round:
            max_projected_score = max([score+14 if score<self.end_score else score for score in scores])
            target = max_projected_score - scores[self.index]
        else:
            target = 14

        while sum(self.current_throws) < target:
            yield True
        yield False

Try for 14 points until the last round, then assume everyone else is going to try for 14 points and try to tie that score.

\$\endgroup\$
  • \$\begingroup\$ I got TypeError: unsupported operand type(s) for -: 'list' and 'int' with your bot. \$\endgroup\$ – tsh Dec 20 '18 at 3:01
  • \$\begingroup\$ I'm assuming that your max_projected_score should be the maximum of the list rather than the entire list, am I correct? Otherwise i get the same issue as tsh. \$\endgroup\$ – maxb Dec 20 '18 at 8:23
  • \$\begingroup\$ Oops, edited to fix. \$\endgroup\$ – histocrat Dec 20 '18 at 13:08
1
\$\begingroup\$

Chaser

class Chaser(Bot):
    def make_throw(self, scores, last_round):
        while max(scores) > (scores[self.index] + sum(self.current_throws)):
            yield True
        while last_round and (scores[self.index] + sum(self.current_throws)) < 44:
            yield True
        while self.not_thrown_firce() and sum(self.current_throws, scores[self.index]) < 44:
            yield True
        yield False

    def not_thrown_firce(self):
        return len(self.current_throws) < 4

Chaser tries to catch up to position one If it's the last round he desperately tries to reach at least 50 points Just for good measure he throws at least four times no matter what

[edit 1: added go-for-gold strategy in the last round]

[edit 2: updated logic because I mistakenly thought a bot would score at 40 rather than only the highest bot scoring]

[edit 3: made chaser a little more defensive in the end game]

\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! Neat idea to not only try to catch up, but also pass the first place. I'm running a simulation right now, and I wish you luck! \$\endgroup\$ – maxb Dec 20 '18 at 9:50
  • \$\begingroup\$ Thanks! Initially I tried to surpass the previous leader by a fixed amount (tried values between 6 and 20) but it turns out just throwing twice more fairs better. \$\endgroup\$ – AKroell Dec 20 '18 at 10:02
  • \$\begingroup\$ @JonathanFrech thanks, fixed \$\endgroup\$ – AKroell Dec 20 '18 at 12:38
1
\$\begingroup\$

FutureBot

class FutureBot(Bot):
    def make_throw(self, scores, last_round):
        while (random.randint(1,6) != 6) and (random.randint(1,6) != 6):
            current_score = scores[self.index] + sum(self.current_throws)
            if current_score > (self.end_score+5):
                break
            yield True
        yield False

OneStepAheadBot

class OneStepAheadBot(Bot):
    def make_throw(self, scores, last_round):
        while random.randint(1,6) != 6:
            current_score = scores[self.index] + sum(self.current_throws)
            if current_score > (self.end_score+5):
                break
            yield True
        yield False

A pair of bots, they bring their own sets of dice and rolls them to predict the future. If one is a 6 they stop, FutureBot can't remember which of it's 2 dice was for the next roll so it gives up.

I wonder which will do better.

OneStepAhead is a little too similar to OneInFive for my taste, but I also want to see how it compares to FutureBot and OneInFive.

Edit: Now they stop after hitting 45

\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! Your bot definitely plays with the spirit of the game! I'll run a simulation later this evening. \$\endgroup\$ – maxb Dec 20 '18 at 16:31
  • \$\begingroup\$ Thanks! I'm curious as to how well it'll do, but I'm guessing it'll be on the low side. \$\endgroup\$ – william porter Dec 20 '18 at 16:34

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.