James Pine Has A Blog

Previously I wrote about a board game our daughter enjoys playing, Hi Ho! Cherry-O. One of the things that makes it somewhat uninteresting to adults is the lack of any applicable strategy; luck completely determines the outcome. Another game she enjoys is The Sneaky Snacky Squirrel. While luck determines much of the outcome, there are also two opportunities to strategize, when the result of a spin allows one to:

1. Pick 1 or 2 acorns of needed color(s).
2. Steal an acorn of a needed color from another player.

Our daughter understands what colors she needs to pick but not that there might be a better strategy than just picking her favorite color or always picking from mama’s log. When playing with her it’s also difficult to test if a non-naive strategy actually matters since she doesn’t appreciate it when people take acorns from her (unless there’s no other option). It’s also difficult to round up other adults to play a bunch of rounds of the game…so once again a simulator is the best option.

For the picking strategy, instead of just picking any color acorn(s) needed, it might be more advantageous to pick the color(s) that the most people already have. That way if another player has an opportunity to steal, it’s less likely they’ll be able to steal from you.

For the stealing strategy, instead of just picking any color acorn needed from any player, it again might be more advantageous to pick the color that the most people have, from the player with the most acorns. That way again if another player has an opportunity to steal, it’s less likely they’ll be able to steal from you and you’ll make it take longer for the player closest to winning to win.

In order to do this I created 4 “strategies”, 2 for picking: BasicPickStrategy and PickColorsLeastLikelyToBeStolenStrategy and then 2 for stealing: BasicStealStrategy and StealColorsLeastLikelyToBeStolenStrategy. Each player needs one of each strategy, which conveniently results in 4 players to cover all possible combinations:

• Player 0: BasicPickStrategy, BasicStealStrategy
• Player 1: BasicPickStrategy, StealColorsLeastLikelyToBeStolenStrategy
• Player 2: PickColorsLeastLikelyToBeStolenStrategy, BasicStealStrategy
• Player 3: PickColorsLeastLikelyToBeStolenStrategy, StealColorsLeastLikelyToBeStolenStrategy

I then had the program play 1,000,000 games between the 4 players, randomizing the order of the players:
$ ./sneaky_snacky_squirrel.py 1000000

The output was:
mean,std,wins
22.121029,8.412456,Counter({3: 296961, 1: 289553, 0: 207117, 2: 206369})

That means on average it took 22.1 turns with a standard deviation of 8.4 to complete a game and Player 3 won 29.7% of the time, Player 1 won 29.0% of the time, Player 0 won 20.7% of the time and Player 2 won 20.6% of the time. So it seems that a non-naive stealing strategy makes the most difference and a non-naive picking strategy also has a small positive effect. There are certainly other strategies, if you’d like to try them just add a new strategy to the code below. I’ve also posted unit tests so you can be more confident things are augmented properly.

#!/usr/bin/python

import itertools
import random
import sys
from collections import Counter
from collections import defaultdict
from math import sqrt


class Color(object):
  """Enumeration of all possible colors"""
  COLORS = set(range(0, 5))
  BLUE, GREEN, PURPLE, RED, YELLOW = COLORS


class SpinResult(object):
  """Enumeration of all possible spin results."""
  RESULTS = set(range(0, 10))
  BLUE, GREEN, PURPLE, RED, YELLOW, WIND, PICK_ONE, PICK_TWO, STEAL, SLEEP = (
      RESULTS)


def GetColorCounts(player, all_players):
  """Count all the colors all the other players have.

  Args:
    player: The player to exclude from the counts.
    all_players: All the players in the game.

  Returns:
    A dict of color->count.
  """
  color_counts = defaultdict(int)
  for other_player in all_players:
    if player == other_player:
      continue  # Don't count player's colors.
    for color in other_player.log:
      color_counts[color] += 1
  return color_counts


class BasicPickStrategy(object):
  """A naive acorn picking strategy."""

  def __init__(self, all_players):
    """Constructor.
  
    Args:
      all_players: A list of all Player objects playing the game.
    """
    self.all_players = all_players

  def pick(self, player, num_acorns=1):
    """Pick the first acorn color needed.
    
    Args:
      num_acorns: The number of acorns to pick.
    """
    if player.filled_log():
      return
    available_colors = Color.COLORS.difference(player.log)
    while num_acorns > 0 and available_colors:
      player.log.add(available_colors.pop())
      num_acorns -= 1


class BasicStealStrategy(object):
  """A naive acorn stealing strategy."""

  def __init__(self, all_players):
    """Constructor.
  
    Args:
      all_players: A list of all Player objects playing the game.
    """
    self.all_players = all_players

  def steal(self, player):
    """Steal the first acorn color needed from the first viable player..
    
    Args:
      player: The player performing the steal.
    """
    if player.filled_log():
      return
    for other_player in self.all_players:
      if player == other_player:
        continue
      available_colors = other_player.log.difference(player.log)
      if available_colors:
        picked_color = available_colors.pop()
        player.log.add(picked_color)
        other_player.log.remove(picked_color)
        break


class PickColorsLeastLikelyToBeStolenStrategy(BasicPickStrategy):
  """A less naive acorn picking strategy."""

  def __init__(self, all_players):
    """Constructor.
  
    Args:
      all_players: A list of all Player objects playing the game.
    """
    BasicPickStrategy.__init__(self, all_players)

  def pick(self, player, num_acorns=1):
    """Pick the most prevalent color acorns; they're least likely to be stolen.
    
    Args:
      num_acorns: The number of acorns to pick.
    """
    if player.filled_log():
      return
    available_colors = Color.COLORS.difference(player.log)
    color_counts = GetColorCounts(player, self.all_players)
    # Pick the most prevalent color(s).
    for color in sorted(color_counts, key=color_counts.get, reverse=True):
      if num_acorns > 0 and color in available_colors:
        player.log.add(color)
        available_colors.remove(color)
        num_acorns -= 1
    # If colors owned by other players are exhasted, pick any needed colors.
    while num_acorns > 0 and available_colors:
      player.log.add(available_colors.pop())
      num_acorns -= 1


class StealColorsLeastLikelyToBeStolenStrategy(BasicStealStrategy):
  """A less naive acorn stealing strategy."""

  def __init__(self, all_players):
    """Constructor.
  
    Args:
      all_players: A list of all Player objects playing the game.
    """
    BasicStealStrategy.__init__(self, all_players)

  def steal(self, player):
    """Steal most prevalent color acorn from the player with the most acorns.
    
    Args:
      player: The player performing the steal.
    """
    if player.filled_log():
      return
    available_colors = Color.COLORS.difference(player.log)
    color_counts = GetColorCounts(player, self.all_players)
    players = sorted(self.all_players, key=lambda p: len(p.log),
        reverse=True)
    for color in sorted(color_counts, key=color_counts.get, reverse=True):
      if color in available_colors:
        player.log.add(color)
        for p in players:
          if color in p.log:
            p.log.remove(color)
            break


class Player(object):
  """Represents a player."""

  def __init__(self, pick_strategy_cls, steal_strategy_cls, number):
    """Constructor.
  
    Args:
      pick_strategy_cls: A class to use for picking acorns.
      steal_strategy_cls: A class to use for stealing acorns.
      number: A unique identifier.
    """
    self.log = set()
    self.pick_strategy_cls = pick_strategy_cls
    self.steal_strategy_cls = steal_strategy_cls
    self.pick_strategy = None
    self.steal_strategy = None
    self.number = number

  def reset(self, all_players):
    """Reset the state of the player.

    Args:
      all_players: A list of Player objects playing the game.
    """
    self.log = set()
    self.pick_strategy = self.pick_strategy_cls(all_players)
    self.steal_strategy = self.steal_strategy_cls(all_players)

  def filled_log(self):
    """Returns True if the player has filled their log, otherwise False."""
    return len(self.log) == len(Color.COLORS)

  def spin(self, value):
    """Process a spin of the wheel.

    Args:
      value: The value of the spin.

    Returns:
      The spun value.
    """
    if value < len(Color.COLORS):
      # Add the selected colored acorn to player's log.
      self.log.add(value)
    elif value == SpinResult.WIND:  # Lose all acorns.
      self.log = set()
    elif value == SpinResult.PICK_ONE:  # Pick any colored acorn.
      self.pick_strategy.pick(self)
    elif value == SpinResult.PICK_TWO:  # Pick any 2 colored acorn.
      self.pick_strategy.pick(self, 2)
    elif value == SpinResult.STEAL:  # Steal an acorn from any other player.
      self.steal_strategy.steal(self)
    elif value == SpinResult.SLEEP: # Skip player's turn.
      pass
    return value

  def __str__(self):
    return  '[%d, %s, %s]' % (self.number, self.pick_strategy_cls.__name__,
        self.steal_strategy_cls.__name__)


def play(players):
  """Plays a single game.

  Args:
    players: List of players playing the game.

  Returns:
    The number of spins performed to complete the game and the winning player.
  """
  num_spins = 0
  for player in players:
    player.reset(players)
  game_over = False
  winner = None
  while not game_over:
    for player in players:
      value = player.spin(random.randint(0, 9))
      num_spins += 1
      game_over = player.filled_log()
      if game_over:
        winner = player
        break

  return num_spins, winner


def mean(data):
  """Compute the mean of data."""
  n = len(data)
  return sum(data) / float(n)


def stddev(data):
  """Compute the standard deviation of data."""
  c = mean(data)
  ssd = sum((x - c) ** 2 for x in data)
  v = ssd / (len(data) - 1)
  return sqrt(v)


def trials(players, num_games):
  """Play games and compute basic statistics.
  
  Args:
    players: A list of Player objects playing the game.
    num_games: The number of games to play when computing statistics.

  Returns:
    Mean number and standard deviation of spins needed to finish a game.
  """
  game_result = []  # (number of_spins, winning player #)
  while num_games > 0:
    random.shuffle(players)
    game_result.append(play(players))
    num_games -= 1
  spin_results = [x[0] for x in game_result]
  winners = [x[1].number for x in game_result]
  return (mean(spin_results), stddev(spin_results), Counter(winners))


if __name__ == '__main__':
  """Play a bunch of games and output the results."""
  num_games = int(sys.argv[1])
  pick_strategies = [BasicPickStrategy, PickColorsLeastLikelyToBeStolenStrategy]
  steal_strategies = [BasicStealStrategy,
      StealColorsLeastLikelyToBeStolenStrategy]
  strategy_combinations = list(
      itertools.product(pick_strategies, steal_strategies))
  players = []
  for i, strategies in enumerate(strategy_combinations):
    players.append(Player(strategies[0], strategies[1], i))
  mean_spins, stddev_spins, win_counts = trials(players, num_games)
  print 'mean,std,wins'
  print '%f,%f,%s' % (mean_spins, stddev_spins, win_counts)

Here are some unit tests:

#!/usr/bin/python

import random
import unittest

from sneaky_snacky_squirrel import BasicPickStrategy
from sneaky_snacky_squirrel import BasicStealStrategy
from sneaky_snacky_squirrel import Color
from sneaky_snacky_squirrel import PickColorsLeastLikelyToBeStolenStrategy
from sneaky_snacky_squirrel import Player
from sneaky_snacky_squirrel import SpinResult


class FakePickStrategy(object):

  def __init__(self, all_players):
    self.pick_called_with = (None, None)

  def pick(self, player, num_acorns=1):
    self.pick_called_with = (player, num_acorns)


class FakeStealStrategy(object):

  def __init__(self, all_players):
    self.steal_called_with = None

  def steal(self, player):
    self.steal_called_with = player


class TestPickColorsLeastLikelyToBeStolenStrategy(unittest.TestCase):

  def setUp(self):
    self.players = set()
    self.player_1 = Player(PickColorsLeastLikelyToBeStolenStrategy,
      FakeStealStrategy, 1)
    self.player_2 = Player(PickColorsLeastLikelyToBeStolenStrategy,
      FakePickStrategy, 2)
    self.player_3 = Player(PickColorsLeastLikelyToBeStolenStrategy,
      FakePickStrategy, 3)
    self.players.add(self.player_1)
    self.players.add(self.player_2)
    self.players.add(self.player_3)
    self.player_1.reset(self.players)
    self.player_2.reset(self.players)
    self.player_3.reset(self.players)

  def testPick(self):
    random_color = random.randint(0, len(Color.COLORS) - 1)
    self.player_2.log.add(random_color)
    self.player_3.log.add(random_color)
    random_color_1 = None
    while True:
      random_color_1 = random.randint(0, len(Color.COLORS) - 1)
      if random_color_1 != random_color:
        self.player_2.log.add(random_color_1)
        break
    self.player_1.pick_strategy.pick(self.player_1)
    self.assertEqual(1, len(self.player_1.log))
    self.assertTrue(random_color in self.player_1.log)
    self.player_1.spin(SpinResult.WIND)
    self.assertEqual(0, len(self.player_1.log))
    self.player_1.pick_strategy.pick(self.player_1, num_acorns=2)
    self.assertEqual(2, len(self.player_1.log))
    self.assertTrue(random_color in self.player_1.log)
    self.assertTrue(random_color_1 in self.player_1.log)


class TestBasicPickStrategy(unittest.TestCase):

  def testPick(self):
    strategy = BasicPickStrategy(None)
    player = Player(None, None, None)
    self.assertEqual(0, len(player.log))
    strategy.pick(player)
    self.assertEqual(1, len(player.log))
    strategy.pick(player, num_acorns=4)
    self.assertEqual(5, len(player.log))
    strategy.pick(player)
    self.assertEqual(5, len(player.log))


class TestBasicStealStrategy(unittest.TestCase):

  def testSteal(self):
    self.players = set()
    self.player_1 = Player(FakePickStrategy, BasicStealStrategy, 1)
    self.player_2 = Player(FakePickStrategy, BasicStealStrategy, 2)
    self.players.add(self.player_1)
    self.players.add(self.player_2)
    self.player_1.reset(self.players)
    self.player_2.reset(self.players)
    self.player_1.steal_strategy.steal(self.player_1)
    self.assertEqual(0, len(self.player_1.log))
    self.assertEqual(0, len(self.player_2.log))
    random_color = random.randint(0, len(Color.COLORS) - 1)
    self.player_2.log.add(random_color)
    self.player_1.steal_strategy.steal(self.player_1)
    self.assertEqual(1, len(self.player_1.log))
    self.assertEqual(0, len(self.player_2.log))
    self.assertTrue(random_color in self.player_1.log)
    self.player_2.log.add(random_color)
    self.player_1.steal_strategy.steal(self.player_1)
    self.assertEqual(1, len(self.player_1.log))
    self.assertEqual(1, len(self.player_2.log))
    self.assertTrue(random_color in self.player_1.log)
    self.assertTrue(random_color in self.player_2.log)


class TestPlayer(unittest.TestCase):

  def setUp(self):
    self.player = Player(FakePickStrategy, FakeStealStrategy, 1)
    self.player.reset(None)

  def testFilledLog(self):
    self.player.log.add(Color.BLUE)
    self.assertFalse(self.player.filled_log())
    self.player.log.update(Color.COLORS)
    self.assertTrue(self.player.filled_log())
    self.assertEqual((None, None), self.player.pick_strategy.pick_called_with)
    self.assertIsNone(self.player.steal_strategy.steal_called_with)

  def testSpinSpecificColor(self):
    value = random.randint(0, len(Color.COLORS) - 1)
    self.player.spin(value)
    self.assertEqual(1, len(self.player.log))
    self.assertTrue(value in self.player.log)
    self.assertEqual((None, None), self.player.pick_strategy.pick_called_with)
    self.assertIsNone(self.player.steal_strategy.steal_called_with)

  def testSpinWind(self):
    self.player.log.add(random.randint(0, len(Color.COLORS) - 1))
    self.assertEqual(1, len(self.player.log))
    self.player.spin(SpinResult.WIND)
    self.assertEqual(0, len(self.player.log))
    self.player.log.update(Color.COLORS)
    self.assertEqual(len(Color.COLORS), len(self.player.log))
    self.player.spin(SpinResult.WIND)
    self.assertEqual(0, len(self.player.log))
    self.assertEqual((None, None), self.player.pick_strategy.pick_called_with)
    self.assertIsNone(self.player.steal_strategy.steal_called_with)

  def testSpinPickOneColor(self):
    self.player.spin(SpinResult.PICK_ONE)
    self.assertEqual(
        (self.player, 1), self.player.pick_strategy.pick_called_with)
    self.assertEqual(0, len(self.player.log))
    self.assertIsNone(self.player.steal_strategy.steal_called_with)

  def testSpinPickTwoColors(self):
    self.player.spin(SpinResult.PICK_TWO)
    self.assertEqual(
        (self.player, 2), self.player.pick_strategy.pick_called_with)
    self.assertEqual(0, len(self.player.log))
    self.assertIsNone(self.player.steal_strategy.steal_called_with)

  def testSpinSteal(self):
    self.player.spin(SpinResult.STEAL)
    self.assertEqual(self.player, self.player.steal_strategy.steal_called_with)
    self.assertEqual(0, len(self.player.log))
    self.assertEqual((None, None), self.player.pick_strategy.pick_called_with)

  def testSpinSleep(self):
    self.player.spin(SpinResult.SLEEP)
    self.assertEqual(0, len(self.player.log))
    self.assertEqual((None, None), self.player.pick_strategy.pick_called_with)
    self.assertIsNone(self.player.steal_strategy.steal_called_with)


if __name__ == '__main__':
  unittest.main()