Сейчас июльское Рождество, так что лучший способ отпраздновать, чем обмен подарками виртуальных белых слонов!

Для этого задания «Король горы» вы должны создать бота, который будет играть в симуляцию обмена «Белый слон» , пытаясь получить самый ценный подарок, какой только может.

Правила игры

• Игра будет проходить в течение многих раундов, каждый из которых состоит из переменного числа ходов.
• Настройка раунда : будет столько же подарков, сколько игроков в игре, каждый из которых оценивается случайным образом равномерно в диапазоне [0 ... 1), причем это значение остается неизвестным до тех пор, пока подарок не будет «открыт». Игроки будут выставлены в случайном порядке в очереди. Первый игрок будет выталкиваться из передней части очереди.
• Когда наступает ход игрока, они могут либо открыть подарок, либо украсть подарок другого игрока, передав ход игроку, чей подарок был украден.
  • Каждый подарок может быть украден до 3 раз.
  • Вы не можете украсть у игрока, который только что украл у вас.
  • Каждый игрок может иметь только один подарок за раз.
• После того, как подарок открыт, игра переходит к следующему игроку, выскочившему из передней части очереди. Это будет следующий игрок в очереди, который еще не имел хода.
• Конец раунда : когда все подарки открыты, раунд заканчивается, и ценность подарка каждого игрока прибавляется к счету этого игрока. Начинается новый раунд, каждый игрок теперь не имеет подарка, а порядок игроков перетасовывается.
• Конец игры : игра заканчивается, когда хотя бы один игрок набрал 100 500 очков, победа присуждается игроку с наибольшей общей суммой подарков.

кодирование

Все материалы должны быть совместимы с Python 3.7. Вы должны написать класс, который напрямую наследует от WhiteElephantBot. Например:

class FooBot(WhiteElephantBot):
    # Your implementation here

Вы можете предоставить __init__метод (который принимает один аргумент name) в своем классе бота, который должен вызвать super().__init__(name). Ваш класс должен иметь take_turnметод, ожидающий следующие аргументы в следующем порядке:

• players: Список имен игроков, в порядке очереди, всех игроков, у которых еще нет подарков.
• presents: Словарь, который отображает имена игроков в 2 кортежа, в которых содержится текущая стоимость, удерживаемая этим игроком, и количество раз, когда он был украден. Это будет включать только других игроков, которые в настоящее время держат подарки.
• just_stole: Если последним предпринятым действием была кража, это будет имя игрока, который только что украл. Если нет, то будет None.

Каждый аргумент будет неизменным или новым объектом, так что изменение любого из них не повлияет на игру. Вы можете оставить копию любого из аргументов, если пожелаете.

Пример значения для presents:

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

Ваш take_turnметод должен вернуть имя игрока, у которого вы хотите украсть или Noneоткрыть подарок. Если оно вызывает исключение, возвращает что-то, отличное от strили или None, или имя игрока, у которого вы не можете украсть, вы по умолчанию откроете подарок.

Ваш конструктор будет вызываться в начале каждого раунда, поэтому вы не сможете запомнить состояние от раунда к раунду.

Унаследовав от WhiteElephantBot, вы получите доступ к steal_targetsметоду, который будет принимать настоящие подарки just_stoleи возвращать список имен игроков, у которых вы можете украсть.

Любые модули, которые нужны вашему скрипту, должны быть импортированы вверху вашей записи.

Тест Драйвер

Тестовый драйвер можно найти здесь . Вам не нужно включать from white_elephant import WhiteElephantBotв свой опубликованный ответ, однако для этого потребуется локальный модуль.

Базовые конкуренты

• Случайно : случайным образом выбирает, открывать ли новый подарок или красть, при этом цель по краже выбирается случайным образом.
• Жадность : укради самый ценный подарок, который можно украсть. Если подарки не могут быть украдены, откройте подарок.
• Приятно : всегда открывает новый подарок. Никогда не крадет.

Дополнительные правила

• Это ваша ответственность, чтобы поймать все исключения. Если вашему классу не удается поймать исключение, оно будет дисквалифицировано. Кроме того, пожалуйста, не ловите KeyboardInterrupts.
• Не используйте файлы или другие методы, чтобы обойти невозможность сохранения состояния между играми. Вы не можете, например, сохранить состояние нейронной сети в файл промежуточного уровня.
• Ваш бот должен быть автономным в коде класса и связанных с ним констант.
• Вы можете использовать только стандартные библиотеки импорта.
• Нет строгих требований к производительности. Будьте разумны и разумны. Если производительность становится проблемой, я оставляю за собой право добавлять ограничения по времени.
• Одна запись на человека. Если вы отправите более одной записи, ваши боты могут не работать вместе. Я собираюсь разрешить несколько записей на человека на данный момент, хотя я могу отобрать его позже, если это станет проблемой.
• Это открытый конкурс без определенной даты окончания. Он будет перезапущен всякий раз, когда я смогу, когда произошли значительные изменения.

РЕДАКТИРОВАТЬ1: победный счет изменен со 100 до 500, чтобы рейтинг был более последовательным. Тестовый драйвер имеет новое исправление, а также отражает изменения в счете победителя.

РЕДАКТИРОВАТЬ 2: Пояснительная записка о необходимом импорте.

Таблица лидеров (по состоянию на 8 августа 2018 г.)

1. SampleBot (500.093)
2. LastMinuteBot (486,163)
3. РобинХуд (463.160)
4. OddTodd (448,825)
5. GreedyBot (438,520)
6. SecondPlaceBot (430.598)
7. ThresholdBot (390,480)
8. Игрок (313.362)
9. NiceBot (275,536)
10. RandomBot (256.172)
11. Добрый Самаритянин (136.298)

LastMinuteBot

(Большое спасибо @Mnemonic за скелет кода, так как я почти не знаю 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

Воспользуйтесь тем фактом, что подарки не могут быть украдены более трех раз, сделайте третье воровство самостоятельно, если найдете дорогой подарок, и большинство подарков было открыто.

Странный тодд

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

Похищает лучший подарок, который он может, но не хочет быть вторым человеком, который украл подарок, потому что, если он украден у него, он не сможет вернуть его.

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

Все будут бороться за самый ценный подарок. Следующий лучший подарок почти так же хорош, но гораздо реже будет украден.

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)

Нас не волнует получение лучшего подарка, просто достаточно хорошего . Пока что-то стоит воровать, мы это сделаем.

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]

Запускает 2000 симуляций с каждым жадным игроком и выбирает лучшее действие.

Робин Гуд

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

Украсть у богатых, которые не заслужили их подарок

Добрый самаритянин

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

Дайте незадачливым людям еще один шанс на удачу

Азартный игрок

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

Игрок зависим, он пытается быть последним игроком, а затем разыгрывает новый подарок, чтобы выиграть у всех остальных игроков.

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)

Этот бот не пытается получить лучший возможный подарок, но пытается получить подарок, который ценится> = (n-3) / n, где n - количество подарков. В большинстве случаев будут цениться подарки, и Top3Bot попытается достать один из них, но ему все равно, кто из них получит.