White Elephant Exchange

Question

It's Christmas in July, so what better way to celebrate than a virtual white elephant gift exchange!

For this King of the Hill challenge, you must create a bot that plays in a White Elephant exchange simulation, trying to get the highest-valued present it can.

Game Rules

• The game will be played over many rounds, each made up of a variable number of turns.
• Round Setup: There will be as many presents as there are players in the game, each valued randomly uniformly in the range [0...1), with this value being unknown until the present is "opened". Players will be put in a random order in a queue. The first player will be popped from the front of the queue.
• When it is a player's turn, they may either open a present or steal another player's present, passing turn to the player whose present was stolen.
  • Each present may be stolen up to 3 times.
  • You cannot steal from the player that just stole from you.
  • Each player can only have one present at a time.
• After a present is opened, play advances to the next player popped from the front of the queue. This will be the next player in turn order who has not yet had a turn.
• Round End: When all presents have been opened, the round ends, and the value of the present held by each player is added to that player's score. A new round begins, with each player now holding no present and the player order shuffled.
• Game End: The game will end when at least one player has at scored 100 500 points, with victory being awarded to the player with the highest total value of presents.

Coding

All submissions should be compatible with Python 3.7. You must write a class that directly inherits from WhiteElephantBot. For instance:

class FooBot(WhiteElephantBot):
    # Your implementation here

You may provide an __init__ method (which takes one argument, name) in your bot class, which must call super().__init__(name). Your class must have a take_turn method expecting the following arguments in this order:

• players: The list of player names, in turn order, of all players that do not yet have presents.
• presents: A dictionary that maps player names to 2-tuples containing the present value held by that player and the number of times that present has been stolen. This will only include other players who are currently holding presents.
• just_stole: If the last action taken was a steal, this will be the name of the player who just stole. If not, it will be None.

Each argument will be immutable or a new object so that mutating any of them will not have an effect on the game. You may keep a copy of any of the arguments if you so desire.

An example value for presents:

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

Your take_turn method should return the name of the player you wish to steal from or None to open a present. If it raises an exception, returns something other than a str or None, or the name of a player you cannot steal from, you will open a present by default.

Your constructor will be called at the beginning of each round, so you do not get to remember state from round to round.

By inheriting from WhiteElephantBot, you will have access to a steal_targets method that will take the presents dict and just_stole and return a list of names of players you can steal from.

Any modules your script needs must be imported at the top of your entry.

Test Driver

The test driver can be found here. You do not need to include from white_elephant import WhiteElephantBot in your posted answer, however a local module will need to do that.

Baseline Competitors

• Random: Chooses randomly whether to open a new present or to steal, with the steal target chosen uniformly randomly.
• Greedy: steal the most valuable present that can be stolen. If no presents can be stolen, open a present.
• Nice: Always opens a new present. Never steals.

Additional Rules

• It is your responsibility to catch all exceptions. If your class fails to catch an exception, it will be disqualified. In addition, please do not catch KeyboardInterrupts.
• Do not use files or other methods to bypass the inability to save state between games. You may not, for instance, save a neural network state to a file mid-run.
• Your bot must be self-contained within class code and related constants.
• You may only use standard library imports.
• There is no strict performance requirement. Be reasonable and prudent. If performance becomes an issue, I reserve the right to add time limits.
• One entry per person. If you submit more than one entry, your bots may not work together. I'm going to allow multiple entries per person for now, though I may reban it later if it becomes a problem.
• This is an open competition with no distinct end date. It will be rerun any time I am able when there have been significant changes.

EDIT1: Changed winning score from 100 to 500 so that rankings are more consistent. The test driver has a new bugfix and also reflects the win score changes.

EDIT2: Clarifying note on required imports.

---

Leaderboard (as of Aug 8, 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. Gambler (313.362)
9. NiceBot (275.536)
10. RandomBot (256.172)
11. GoodSamaritan (136.298)

Answer 1

LastMinuteBot

(With big thanks to @Mnemonic for the skeleton of the code, since I barely know 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

Take advantage of the fact that gifts can't be stolen more than thrice, do the third stealing yourself if you find a high value gift and most presents have been opened.

Answer 2

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

Steals the best gift that he can, but doesn't want to be the second person to steal a gift, because if it gets stolen from him he can't get it back.

Answer 3

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

Everyone's going to be fighting for the most valuable gift. The next best gift is almost as good, but much less likely to be stolen.

Answer 4

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)

We don't really care about getting the best gift, just something good enough. So long as there's something worth stealing, we'll do it.

Answer 5

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]

Runs 2000 simulations with each player acting greedily and chooses the best action.

Answer 6

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

Steal from the rich who didn't earn their present

Answer 7

GoodSamaritan

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

Give unlucky people another chance at good fortune

Answer 8

Gambler

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

The Gambler is addicted, he tries to be the last player, then he gambles on a new present to beat all the other players.

Answer 9

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)

This bot does not try to get the best present possible, but tries to get a present that is valued >= (n-3)/n, where n is the number of presents. In most of the cases, there will be presents valued that much, and Top3Bot will try to get its hands on one of these, but he doesn't really care which of those he gets.