É Natal em julho, então, que melhor maneira de comemorar do que uma troca virtual de presentes de elefante branco!

Para este desafio de King of the Hill, você deve criar um bot que seja reproduzido em uma simulação de troca de elefantes brancos , tentando obter o presente mais valorizado possível.

Regras do jogo

• O jogo será disputado em várias rodadas, cada uma composta por um número variável de turnos.
• Configuração da Rodada : Haverá tantos presentes quanto jogadores no jogo, cada um avaliado aleatoriamente de maneira uniforme no intervalo [0 ... 1), sendo esse valor desconhecido até que o presente seja "aberto". Os jogadores serão colocados em uma ordem aleatória em uma fila. O primeiro jogador será exibido na frente da fila.
• Quando é a vez de um jogador, ele pode abrir um presente ou roubar o presente de outro jogador, passando a vez para o jogador cujo presente foi roubado.
  • Cada presente pode ser roubado até 3 vezes.
  • Você não pode roubar do jogador que acabou de roubar de você.
  • Cada jogador pode ter apenas um presente de cada vez.
• Depois que um presente é aberto, o jogo avança para o próximo jogador exibido na frente da fila. Este será o próximo jogador na ordem do turno que ainda não teve um turno.
• Final da Rodada : Quando todos os presentes tiverem sido abertos, a rodada terminará e o valor do presente realizado por cada jogador será adicionado à pontuação desse jogador. Uma nova rodada começa, com cada jogador agora sem presente e a ordem do jogador embaralhada.
• Fim do Jogo : O jogo terminará quando pelo menos um jogador tiver marcado 100 500 pontos, com a vitória sendo concedida ao jogador com o maior valor total de presentes.

Codificação

Todos os envios devem ser compatíveis com o Python 3.7. Você deve escrever uma classe que herda diretamente de WhiteElephantBot. Por exemplo:

class FooBot(WhiteElephantBot):
    # Your implementation here

Você pode fornecer um __init__método (que usa um argumento name) em sua classe de bot, que deve ser chamado super().__init__(name). Sua classe deve ter um take_turnmétodo esperando os seguintes argumentos nesta ordem:

• players: A lista de nomes de jogadores, por ordem de turno, de todos os jogadores que ainda não têm presentes.
• presents: Um dicionário que mapeia nomes de jogadores para duas tuplas, contendo o valor presente mantido por esse jogador e o número de vezes que o presente foi roubado. Isso incluirá apenas outros jogadores que estão atualmente com presentes.
• just_stole: Se a última ação tomada foi um roubo, este será o nome do jogador que acabou de roubar. Caso contrário, será None.

Cada argumento será imutável ou um novo objeto, de modo que a mutação de qualquer um deles não terá efeito no jogo. Você pode manter uma cópia de qualquer um dos argumentos, se desejar.

Um valor de exemplo para presents:

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

Seu take_turnmétodo deve retornar o nome do jogador que você deseja roubar ou Noneabrir um presente. Se isso gerar uma exceção, retornar algo diferente de um strou None, ou o nome de um jogador do qual você não pode roubar, você abrirá um presente por padrão.

Seu construtor será chamado no início de cada rodada, para que você não se lembre do estado de rodada a rodada.

Ao herdar de WhiteElephantBot, você terá acesso a um steal_targetsmétodo que aceitará o ditado dos presentes just_stolee retornará uma lista de nomes de jogadores dos quais você pode roubar.

Quaisquer módulos necessários para o seu script devem ser importados na parte superior da sua entrada.

Test Driver

O driver de teste pode ser encontrado aqui . Você não precisa incluir from white_elephant import WhiteElephantBotna sua resposta postada, no entanto, um módulo local precisará fazer isso.

Concorrentes da linha de base

• Aleatório : escolhe aleatoriamente se deseja abrir um novo presente ou roubar, com o alvo roubado escolhido uniformemente aleatoriamente.
• Ganancioso : roube o presente mais valioso que pode ser roubado. Se nenhum presente puder ser roubado, abra um presente.
• Bom : sempre abre um novo presente. Nunca rouba.

Regras adicionais

• É sua responsabilidade capturar todas as exceções. Se sua classe falhar em capturar uma exceção, ela será desqualificada. Além disso, não pegue o KeyboardInterrupts.
• Não use arquivos ou outros métodos para ignorar a incapacidade de salvar o estado entre os jogos. Você não pode, por exemplo, salvar um estado de rede neural em um arquivo durante a execução.
• Seu bot deve estar independente do código da classe e das constantes relacionadas.
• Você só pode usar importações de bibliotecas padrão.
• Não há nenhum requisito estrito de desempenho. Seja razoável e prudente. Se o desempenho se tornar um problema, reservo-me o direito de adicionar limites de tempo.
• Uma entrada por pessoa. Se você enviar mais de uma entrada, seus bots podem não funcionar juntos. Por enquanto, vou permitir várias entradas por pessoa, embora possa rebanho mais tarde se isso se tornar um problema.
• Esta é uma competição aberta, sem data final distinta. Será executada novamente a qualquer momento quando houver alterações significativas.

EDIT1: alteração na pontuação vencedora de 100 para 500, para que as classificações sejam mais consistentes. O driver de teste possui uma nova correção de bug e também reflete as alterações na pontuação da vitória.

EDIT2: Nota esclarecedora sobre as importações necessárias.

Classificação (em 8 de agosto de 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. Jogador (313,362)
9. NiceBot (275.536)
10. RandomBot (256.172)
11. Bom samaritano (136.298)

LastMinuteBot

(Com muito obrigado a @Mnemonic pelo esqueleto do código, já que eu mal conheço Python.)

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

Aproveite o fato de que os presentes não podem ser roubados mais do que três vezes; faça o terceiro roubando a si mesmo se você encontrar um presente de alto valor e a maioria dos presentes tiver sido aberta.

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

Rouba o melhor presente que ele pode, mas não quer ser a segunda pessoa a roubar um presente, porque se for roubado dele, ele não poderá recuperá-lo.

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

Todo mundo vai estar lutando pelo presente mais valioso. O próximo melhor presente é quase tão bom, mas muito menos provável de ser roubado.

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)

Realmente não nos preocupamos em receber o melhor presente, apenas algo bom o suficiente . Enquanto houver algo que valha a pena roubar, faremos isso.

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]

Executa 2000 simulações com cada jogador agindo com avidez e escolhe a melhor ação.

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

Roubar dos ricos que não ganharam seu presente

Bom Samaritano

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

Dê às pessoas azaradas outra chance de boa sorte

Jogador

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

O jogador é viciado, ele tenta ser o último jogador e depois joga um novo presente para vencer todos os outros jogadores.

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)

Este bot não tenta obter o melhor presente possível, mas tenta obter um presente com o valor> = (n-3) / n, em que n é o número de presentes. Na maioria dos casos, haverá presentes com tanto valor, e o Top3Bot tentará colocar uma mão em um deles, mas ele realmente não se importa com quem recebe.