Es ist Weihnachten im Juli. Was gibt es Schöneres, als ein virtuelles Geschenk für weiße Elefanten auszutauschen?

Für diese King of the Hill-Herausforderung musst du einen Bot erstellen, der in einer White Elephant-Tausch- Simulation mitspielt und versucht, das bestmögliche Geschenk zu erhalten.

Spielregeln

• Das Spiel wird über viele Runden gespielt, die jeweils aus einer variablen Anzahl von Runden bestehen.
• Rundenaufbau : Es gibt so viele Geschenke, wie Spieler im Spiel sind, wobei jeder Wert zufällig gleichmäßig im Bereich [0 ... 1] bewertet wird, wobei dieser Wert unbekannt ist, bis das Geschenk "geöffnet" wird. Die Spieler werden in zufälliger Reihenfolge in eine Warteschlange eingereiht. Der erste Spieler wird von vorne in die Warteschlange gestellt.
• Wenn ein Spieler an der Reihe ist, kann er entweder ein Geschenk öffnen oder das Geschenk eines anderen Spielers stehlen und an den Spieler übergeben, dessen Geschenk gestohlen wurde.
  • Jedes Geschenk kann bis zu dreimal gestohlen werden.
  • Sie können nicht von dem Spieler stehlen, der gerade von Ihnen gestohlen hat.
  • Jeder Spieler kann jeweils nur ein Geschenk haben.
• Nachdem ein Geschenk geöffnet wurde, geht das Spiel zum nächsten Spieler über, der von der Vorderseite der Warteschlange aus erscheint. Dies ist der nächste Spieler in der Zugreihenfolge, der noch keinen Zug hatte.
• Round End : Wenn alle Geschenke geöffnet worden sind, endet die Runde, und der Wert der von jedem Spieler gehalten vorhanden hinzugefügt werden diesen Spieler Score. Es beginnt eine neue Runde, in der jeder Spieler kein Geschenk mehr hat und die Spielerreihenfolge gemischt wird.
• Spielende : Das Spiel endet , wenn mindestens ein Spieler bei erzielt hat 100 500 Punkte, mit einem Sieg mit dem höchsten Gesamtwert von Geschenken an den Spieler vergeben.

Codierung

Alle Einsendungen sollten mit Python 3.7 kompatibel sein. Sie müssen eine Klasse schreiben, von der direkt geerbt wird WhiteElephantBot. Zum Beispiel:

class FooBot(WhiteElephantBot):
    # Your implementation here

Sie können eine __init__Methode (die ein Argument nameakzeptiert) in Ihrer Bot-Klasse angeben, die aufgerufen werden muss super().__init__(name). Ihre Klasse muss über eine take_turnMethode verfügen , die die folgenden Argumente in dieser Reihenfolge erwartet:

• players: Die Liste der Spielernamen aller Spieler, die noch keine Geschenke haben.
• presents: Ein Wörterbuch, das Spielernamen auf 2 Tupel abbildet, die den aktuellen Wert dieses Spielers und die Häufigkeit des Diebstahls enthalten. Dies schließt nur andere Spieler ein, die gerade Geschenke in der Hand haben.
• just_stole: Wenn die letzte Aktion ein Diebstahl war, ist dies der Name des Spielers, der gerade gestohlen hat. Wenn nicht, wird es sein None.

Jedes Argument ist unveränderlich oder ein neues Objekt, sodass eine Mutation keinen Einfluss auf das Spiel hat. Sie können eine Kopie aller Argumente aufbewahren, wenn Sie dies wünschen.

Ein Beispielwert für presents:

{
    'Alice':   (0.35, 0),
    'Bob':     (0.81, 2),
    'Charlie': (0.57, 1)
}

Ihre take_turnMethode sollte den Namen des Spielers zurückgeben, den Sie stehlen oder Noneein Geschenk öffnen möchten . Wenn es eine Ausnahme auslöst, etwas anderes als ein stroder Noneoder den Namen eines Spielers zurückgibt, von dem Sie nicht stehlen können, öffnen Sie standardmäßig ein Geschenk.

Ihr Konstruktor wird zu Beginn jeder Runde aufgerufen, sodass Sie sich nicht von Runde zu Runde an den Status erinnern können.

Durch das Erben von WhiteElephantBothaben Sie Zugriff auf eine steal_targetsMethode, die das Präsensdiktat aufnimmt und just_stoleeine Liste der Namen der Spieler zurückgibt, von denen Sie stehlen können.

Alle Module, die Ihr Skript benötigt, müssen oben in Ihrem Eintrag importiert werden.

Testfahrer

Den Testfahrer finden Sie hier . Sie müssen from white_elephant import WhiteElephantBotin Ihrer Antwort nicht enthalten sein, dies muss jedoch von einem lokalen Modul durchgeführt werden.

Baseline Wettbewerber

• Zufällig : Wählt zufällig aus, ob ein neues Geschenk geöffnet oder gestohlen werden soll, wobei das gestohlene Ziel gleichmäßig zufällig ausgewählt wird.
• Gierig : Stehlen Sie das wertvollste Geschenk, das gestohlen werden kann. Wenn keine Geschenke gestohlen werden können, öffnen Sie ein Geschenk.
• Schön : Öffnet immer ein neues Geschenk. Stiehlt niemals.

Zusätzliche Regeln

• Es liegt in Ihrer Verantwortung, alle Ausnahmen abzufangen. Wenn Ihre Klasse eine Ausnahme nicht abfängt, wird sie disqualifiziert. Bitte fangen Sie auch keine KeyboardInterrupts.
• Verwenden Sie keine Dateien oder andere Methoden, um die Unfähigkeit zu umgehen, den Status zwischen Spielen zu speichern. Sie können beispielsweise einen neuronalen Netzwerkstatus nicht während der Ausführung in einer Datei speichern.
• Ihr Bot muss im Klassencode und den zugehörigen Konstanten enthalten sein.
• Sie dürfen nur Standard-Bibliotheksimporte verwenden.
• Es gibt keine strengen Leistungsanforderungen. Seien Sie vernünftig und umsichtig. Wenn die Leistung zum Problem wird, behalte ich mir das Recht vor, Fristen hinzuzufügen.
• Ein Eintrag pro Person. Wenn Sie mehr als einen Eintrag einreichen, können Ihre Bots möglicherweise nicht zusammenarbeiten. Ich werde vorerst mehrere Einträge pro Person zulassen, aber ich kann es später wieder zulassen, wenn es zu einem Problem wird.
• Dies ist ein offener Wettbewerb ohne eindeutiges Enddatum. Es wird jedes Mal wiederholt, wenn sich wesentliche Änderungen ergeben haben.

EDIT1: Die Siegpunktzahl wurde von 100 auf 500 geändert, damit die Platzierungen konsistenter sind. Der Testfahrer hat einen neuen Bugfix und spiegelt auch die Änderungen der Siegpunkte wider.

EDIT2: Erläuterung zu erforderlichen Importen.

Bestenliste (Stand: 8. August 2018)

1. SampleBot (500.093)
2. LastMinuteBot (486.163)
3. RobinHood (463.160)
4. OddTodd (448.825)
5. GreedyBot (438.520)
6. SecondPlaceBot (430.598)
7. ThresholdBot (390.480)
8. Spieler (313.362)
9. NiceBot (275.536)
10. RandomBot (256.172)
11. GoodSamaritan (136.298)

LastMinuteBot

(Mit großem Dank an @Mnemonic für das Grundgerüst des Codes, da ich Python kaum kenne.)

class LastMinuteBot(WhiteElephantBot):
    def take_turn(self, players, presents, just_stole):
        targets = self.steal_targets(presents, just_stole)
        if len(targets) <= 1:
            return None

        target = None

        # If most of the presents are already distributed, try to steal an 
        #  un-restealable gift of high value
        if len(presents) > (len(players) + len(presents)) * 0.75:
            at_threshold = [t for t in targets if presents[t][1]==2 and presents[t][0]>=0.8]
            if at_threshold:
                target = max(at_threshold, key=lambda x: presents[x][0])

        # Otherwise, take the best available
        if not target:
            target = max(targets, key=lambda x: presents[x][0])

        return target if presents[target][0] > 0.5 else None

Profitieren Sie von der Tatsache, dass Geschenke nur dreimal gestohlen werden können, und stehlen Sie sich das dritte Mal, wenn Sie ein hochwertiges Geschenk finden und die meisten Geschenke bereits geöffnet wurden.

Odd Todd

class OddTodd(WhiteElephantBot):
    def take_turn(self, players, presents, just_stole):

        targets = self.steal_targets(presents, just_stole)

        # if none to steal, pick present
        if len(targets) <= 1:
            return None

        # steals the best gift that he can, as long as he's the 1st/3rd steal
        targets = [t for t in targets if presents[t][1] % 2 == 0]
        if targets:
            return max(targets, key=lambda x:presents[x][0])

        else:
            return None

Stiehlt das beste Geschenk, das er kann, möchte aber nicht die zweite Person sein, die ein Geschenk stiehlt, denn wenn es ihm gestohlen wird, kann er es nicht zurückbekommen.

SecondPlaceBot

class SecondPlaceBot(WhiteElephantBot):
    def take_turn(self, players, presents, just_stole):
        targets = self.steal_targets(presents, just_stole)
        if len(targets) <= 1:
            return None

        # If most of the presents are already distributed, take the second best.
        if len(presents) > (len(players) + len(presents)) * 0.8:
            target = sorted(targets, key=lambda x: presents[x][0])[-2]
        # Otherwise, take the best and hope someone steals it later.
        else:
            target = max(targets, key=lambda x: presents[x][0])

        return target if presents[target][0] > 0.5 else None

Jeder wird für das wertvollste Geschenk kämpfen. Das nächstbeste Geschenk ist fast genauso gut, aber es ist viel weniger wahrscheinlich, dass es gestohlen wird.

ThresholdBot

import random

class ThresholdBot(WhiteElephantBot):
    def __init__(self, name):
        self.name = name
        # Choose a minimum value to be happy.
        self.goal = 1 - random.random() ** 2

    def take_turn(self, players, presents, just_stole):
        # Find who has a gift that's sufficiently valuable.
        targets = self.steal_targets(presents, just_stole)
        targets = [x for x in targets if presents[x][0] >= self.goal]
        targets = sorted(targets, key=lambda x: presents[x][0])

        if not targets:
            return None

        # Choose a target (biased toward the best gifts).
        weighted = []
        for i, target in enumerate(targets, 1):
            weighted += [target] * i ** 2
        return random.choice(weighted)

Es ist uns eigentlich egal, ob wir das Beste bekommen Geschenk bekommen, nur etwas, das gut genug ist . Solange es etwas gibt, das es wert ist, gestohlen zu werden, werden wir es tun.

SampleBot

import random

class SampleBot(WhiteElephantBot):
    def rollout(self, values, counts, just_stole, next_move):
        targets = set()
        move_chosen = False
        for i, (v, n) in enumerate(zip(values, counts)):
            if v and n < 3 and i != just_stole and i != 0:
                targets.add(i)
        for i in range(len(values)):
            if values[i]:
                break
            while True:
                if not targets:
                    break
                if move_chosen:
                    j = max(targets, key=lambda i: values[i])
                    if values[j] < 0.5:
                        break
                else:
                    move_chosen = True
                    if next_move is None:
                        break
                    j = next_move
                values[i] = values[j]
                counts[i] = counts[j] + 1
                values[j] = 0
                counts[j] = 0
                if just_stole is not None and counts[just_stole] < 3:
                    targets.add(just_stole)
                if j in targets:
                    targets.remove(j)
                just_stole = i
                i = j
            values[i] = random.random()
            for player in (just_stole, i):
                if player is not None and values[player] and counts[player] < 3:
                    targets.add(player)
        return values[0]
    def take_turn(self, players, presents, just_stole, n_rollouts=2000):
        names = [self.name] + players + list(presents.keys())
        values = [presents[name][0] if name in presents else None for name in names]
        counts = [presents[name][1] if name in presents else 0 for name in names]
        if just_stole is not None:
            just_stole = names.index(just_stole)
        targets = [None]
        for i, (v, n) in enumerate(zip(values, counts)):
            if v and n < 3 and i != just_stole and i != 0:
                targets.append(i)
        if len(targets) == 1:
            return targets[0]
        scores = [0. for _ in targets]
        n = n_rollouts // len(targets)
        for i, target in enumerate(targets):
            for _ in range(n):
                scores[i] += self.rollout(list(values), list(counts), just_stole, target) / float(n)
        target_index = targets[scores.index(max(scores))]
        if target_index is None:
            return None
        return names[target_index]

Führt 2000 Simulationen durch, wobei jeder Spieler gierig handelt und die beste Aktion auswählt.

Robin Hood

class RobinHood(WhiteElephantBot):       
    def take_turn(self, players, presents, just_stole):
        #get the possible steal targets
        targets = self.steal_targets(presents, just_stole)
        #who stole his gift?
        targets = [x for x in targets if presents[x][1] > 0]
        #sort by value
        targets = sorted(targets, key=lambda x: presents[x][0])        
        #only steal back if it's worth it        
        targets = [x for x in targets if presents[x][0] > 0.5]

        if len(targets)>0:
           return targets.pop()

Stehlen Sie von den Reichen, die ihr Geschenk nicht verdient haben

Der gute Samariter

class GoodSamaritan(WhiteElephantBot):     
    def take_turn(self, players, presents, just_stole):  
        targets = self.steal_targets(presents, just_stole)

         #if only one player has a gift, don't steal it!
        if len(presents)<=1 or len(targets)==0:
             return None
        else:       
             #Steal the worst present  
             return min(targets, key=lambda x: presents[x][0])

Geben Sie unglücklichen Menschen eine weitere Chance auf Glück

Spieler

class Gambler(WhiteElephantBot):
    def take_turn(self, players, presents, just_stole):        
        #get the possible steal targets
        targets = self.steal_targets(presents, just_stole)        

        #last player 
        if len(players)==0:
            #lets gamble! Try and get the highest score
            return None

        #If you are not last, steal the best gift that can be restolen so maybe you can become the last player
        targets = [t for t in targets if presents[t][1]<2 ]
        if targets:
            return max(targets, key=lambda x: presents[x][0])   

Der Spieler ist süchtig, er versucht der letzte Spieler zu sein, dann setzt er auf ein neues Geschenk, um alle anderen Spieler zu besiegen.

Top3Bot

class Top3Bot(WhiteElephantBot):
    def __init__(self, name):
        super().__init__(name)
        self.firstturn = True

    def take_turn(self, players, presents, just_stole):
        if self.firstturn:
            num_presents = len(players) + len(presents) + 1
            self.value_limit = (num_presents - 3) / num_presents
            self.firstturn = False

        targets = self.steal_targets(presents, just_stole)

        if players:
            targets += None

        return max(
            targets,
            key=lambda name: self.steal_ranking(name, presents, len(players))
        )


    def steal_ranking(self, name, presents, presents_remaining):
        if name is None:
            return (0, 0)

        present_value = presents[name][0]
        num_steals = presents[name][1]
        if present_value >= self.value_limit:
            if num_steals == 2:
                return (5, present_value)
            elif  num_steals == 0:
                return (4, -presemt_value)
            elif num_steals == 1 and presents_remaining == 0:
                return (3, -present_value)
            else:
                return (-1, present_value)
        else:
            if num_steals < 2:
                return (2, present_value)
            else:
                return (-2, present_value)

Dieser Bot versucht nicht, das bestmögliche Geschenk zu bekommen, sondern versucht, ein Geschenk zu bekommen, das> = (n-3) / n ist, wobei n die Anzahl der Geschenke ist. In den meisten Fällen wird es Geschenke geben, die so viel wert sind, und Top3Bot wird versuchen, eines davon in die Hände zu bekommen, aber es ist ihm egal, welches davon er bekommt.