W lipcu są święta, więc czy jest lepszy sposób na świętowanie niż wymiana prezentów z wirtualnym białym słoniem!

Aby podjąć wyzwanie King of the Hill, musisz stworzyć bota, który gra w symulacji wymiany Białego Słonia , starając się uzyskać jak najcenniejszy prezent.

Zasady gry

• Gra będzie się toczyć przez wiele rund, z których każda składa się ze zmiennej liczby tur.
• Konfiguracja rundy : w grze będzie tyle prezentów, ile jest graczy, każdy wyceniany losowo równomiernie w przedziale [0 ... 1), przy czym ta wartość jest nieznana do momentu „otwarcia” teraźniejszości. Gracze zostaną ułożeni w losowej kolejności w kolejce. Pierwszy gracz zostanie wyskakujący z przodu kolejki.
• Kiedy nadchodzi kolej gracza, może on albo otworzyć prezent, albo ukraść prezent innego gracza, przekazując kolejkę graczowi, którego prezent został skradziony.
  • Każdy prezent może zostać skradziony do 3 razy.
  • Nie możesz kraść od gracza, który właśnie cię ukradł.
  • Każdy gracz może mieć tylko jednego na raz.
• Po otwarciu prezentu postępy w grze do następnego gracza wyskakują z przodu kolejki. Będzie to następny gracz w kolejności, który nie miał jeszcze tury.
• Koniec rundy : Po otwarciu wszystkich prezentów runda się kończy, a wartość prezentu każdego gracza jest dodawana do wyniku tego gracza. Rozpoczyna się nowa runda, w której każdy gracz nie ma teraz prezentu, a kolejność graczy jest tasowana.
• Koniec gry : Gra zakończy się, gdy co najmniej jeden gracz uzyska 100 500 punktów, a zwycięstwo zostanie przyznane graczowi o najwyższej łącznej wartości prezentów.

Kodowanie

Wszystkie zgłoszenia powinny być zgodne z Python 3.7. Musisz napisać klasę, która bezpośrednio dziedziczy WhiteElephantBot. Na przykład:

class FooBot(WhiteElephantBot):
    # Your implementation here

Możesz podać __init__metodę (która wymaga jednego argumentu name) w swojej klasie botów, którą należy wywołać super().__init__(name). Twoja klasa musi mieć take_turnmetodę oczekującą następujących argumentów w tej kolejności:

• players: Lista nazwisk graczy w kolejności wszystkich graczy, którzy jeszcze nie mają prezentów.
• presents: Słownik, który odwzorowuje nazwy graczy na 2-krotki zawierające aktualną wartość posiadaną przez tego gracza i liczbę kradzieży tego prezentu. Dotyczy to tylko innych graczy, którzy obecnie trzymają prezenty.
• just_stole: Jeśli ostatnią podjętą akcją była kradzież, będzie to nazwa gracza, który właśnie ukradł. Jeśli nie, to będzie None.

Każdy argument będzie niezmienny lub nowy obiekt, więc mutowanie któregokolwiek z nich nie będzie miało wpływu na grę. Możesz zachować kopię dowolnego z argumentów, jeśli sobie tego życzysz.

Przykładowa wartość dla presents:

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

Twoja take_turnmetoda powinna zwrócić nazwę gracza, którego chcesz ukraść lub Noneotworzyć prezent. Jeśli zgłosi wyjątek, zwróci coś innego niż a strlub Nonenazwisko gracza, od którego nie możesz ukraść, domyślnie otworzysz prezent.

Twój konstruktor będzie wywoływany na początku każdej rundy, więc nie będziesz pamiętać stanu z rundy na rundę.

Dziedzicząc po WhiteElephantBot, będziesz miał dostęp do steal_targetsmetody, która zabierze prezent z dykt just_stolei zwróci listę nazwisk graczy, z których możesz ukraść.

Wszystkie moduły, których potrzebuje skrypt, muszą zostać zaimportowane u góry wpisu.

Kierowca testowy

Sterownik testowy można znaleźć tutaj . Nie musisz dołączać do from white_elephant import WhiteElephantBotopublikowanej odpowiedzi, jednak moduł lokalny będzie musiał to zrobić.

Podstawowi konkurenci

• Losowo : Wybiera losowo, czy otworzyć nowy prezent, czy ukraść, a cel kradzieży wybierany jest losowo.
• Chciwy : ukraść najcenniejszy prezent, który można ukraść. Jeśli nie można ukraść prezentów, otwórz prezent.
• Fajnie : zawsze otwiera nowy prezent. Nigdy nie kradnie.

Dodatkowe zasady

• Twoim obowiązkiem jest uchwycić wszystkie wyjątki. Jeśli twoja klasa nie złapie wyjątku, zostanie zdyskwalifikowany. Ponadto nie wyłapuj Przerwania Keyboard.
• Nie używaj plików ani innych metod w celu ominięcia niemożności zapisania stanu między grami. Nie można na przykład zapisać stanu sieci neuronowej do pliku w trakcie uruchamiania.
• Twój bot musi być samowystarczalny w ramach kodu klasy i powiązanych stałych.
• Możesz używać tylko standardowych importów bibliotek.
• Nie ma ścisłych wymagań dotyczących wydajności. Bądź rozsądny i rozważny. Jeśli wydajność stanie się problemem, zastrzegam sobie prawo do dodania limitów czasowych.
• Jedno wejście na osobę. Jeśli prześlesz więcej niż jeden wpis, boty mogą nie działać razem. Na razie zezwalam na wiele wpisów na osobę, ale może później ponownie go odbanować, jeśli stanie się to problemem.
• To jest otwarty konkurs bez wyraźnej daty zakończenia. Zostanie ponownie uruchomiony za każdym razem, gdy będę w stanie, gdy nastąpią znaczące zmiany.

EDYCJA 1: Zmieniono zwycięski wynik ze 100 na 500, aby ranking był bardziej spójny. Sterownik testowy ma nową poprawkę błędów, a także odzwierciedla zmiany wyniku wygranej.

EDYCJA 2: Nota wyjaśniająca na temat wymaganego przywozu.

Tabela liderów (od 8 sierpnia 2018 r.)

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. Hazardzista (313.362)
9. NiceBot (275,536)
10. RandomBot (256.172)
11. GoodSamaritan (136.298)

LastMinuteBot

(Wielkie podziękowania dla @Mnemonic za szkielet kodu, ponieważ ledwo znam Pythona.)

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

Skorzystaj z faktu, że prezentów nie można skradzić więcej niż trzykrotnie, a następnie dokonaj trzeciego kradzieży, jeśli znajdziesz prezent o wysokiej wartości i większość prezentów została już otwarta.

Dziwny 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

Kradnie najlepszy prezent, jaki może, ale nie chce być drugą osobą, która może ukraść prezent, ponieważ jeśli zostanie mu skradziony, nie może go odzyskać.

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

Wszyscy będą walczyć o najcenniejszy prezent. Następny najlepszy prezent jest prawie tak samo dobry, ale znacznie mniej prawdopodobne, że zostanie skradziony.

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)

Tak naprawdę nie zależy nam na tym, aby otrzymać najlepszy prezent, wystarczy coś dobrego . Tak długo, jak jest coś wartego kradzieży, będziemy to robić.

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]

Uruchamia 2000 symulacji, w których każdy gracz zachowuje się zachłannie i wybiera najlepszą akcję.

RobinHood

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()

Kradnij bogatym, którzy nie zdobyli prezentu

Dobry Samarytanin

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])

Daj pechowcom kolejną szansę na szczęście

Gracz

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])   

Gracz jest uzależniony, stara się być ostatnim graczem, a potem gra o nowy prezent, aby pokonać wszystkich innych graczy.

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)

Ten bot nie próbuje uzyskać najlepszego możliwego prezentu, ale próbuje uzyskać prezent o wartości> = (n-3) / n, gdzie n jest liczbą prezentów. W większości przypadków będą prezenty cenione tak bardzo, a Top3Bot spróbuje zdobyć jeden z nich, ale tak naprawdę nie obchodzi go, który z nich dostanie.