James Pine Has A Blog

As our daughter approaches 3 years old she has begun to play some simple board games, one of which is Hi Ho! Cherry-O. While playing it recently my wife lamented that the game was taking forever to end. The analysis in the Wikipedia page is for a single player, but the majority of the time 2-4 players are present. It wasn’t obvious to me how to easily extend the Markov chain for a multi-player game. Does one add a 3rd dimension with 1 slice of the transition matrix per player? So instead I wrote a little Python program to play lots of games and compute the mean and standard deviation (it’s at the end of the post).

I then ran 10,000 simulations each for games of 2-4 players with 10 fruits per tree:

$ for i in 2 3 4; do ./hi-ho-cherry-o.py $i 10 10000; done
players,spins,stddev
2,18.619100,12.388267
3,21.197900,12.418629
4,24.335700,12.889896

It’s interesting that the minimum number of spins necessary to win with a single player is 3 and the number of additional spins necessary for a game to end when adding a player is ~3. Now we know 90% of the games we play with our daughter will take fewer than 40 spins, which is comforting. Though it’s scary to think that 1% of the time a game will take 70 or more!

#!/usr/bin/python

import random
import sys
from math import sqrt


def pick(num_fruit, max_num_fruit, player, players):
  """Execute a turn by picking fruit; modifies the game state.

  Args:
    num_fruit: If positive, it's as if the player is picking
      fruit from their tree and placing it in their basket. If
      negative, it's as if the player is putting fruit back
      into their tree from their basket.
    max_num_fruit: The maximum amount of fruit in a tree.
    player: The index of the player who's picking.
    players: The list of players in the game.

  Returns: The amount of fruit left in the player's tree.
  """
  new_num_fruit = players[player] - num_fruit

  # Can't pick more fruit than exist in the tree.
  new_num_fruit = max(new_num_fruit, 0)

  # Can't put back more fruit than fits in the tree.
  new_num_fruit = min(new_num_fruit, max_num_fruit)

  players[player] = new_num_fruit
  return new_num_fruit


def spin(max_num_fruit):
  """Execute a spin of the wheel.

  There are 7 possibilities, each with equal probability:
    Pick 1-4 fruit from a tree and place in a basket.
    Put 2 fruit back in the tree (landed on bird or dog).
    Put all fruit back in the tree (broken basket).

  Args:
    max_num_fruit: The maximum amount of fruit in a tree.

  Returns: Number of fruit to move. Positive indicates pick
    from the tree, negative indicates put back into the tree.
  """
  temp = random.randint(1, 7)
  if temp < 5:
    return temp
  elif temp < 7:
    return -2
  else:
    return max_num_fruit * -1


def play(players, max_num_fruit):
  """Plays a complete game.

  Args:
    players: A list of players taking part in the game.
    max_num_fruit: The maximum amount of fruit in a tree.

  Returns: The number of spins needed to complete the game.
  """
  num_spins = 0
  keep_playing = True
  num_players = len(players)
  while keep_playing:
    for i in xrange(num_players):
      num_spins += 1
      num_fruit_to_pick = spin(max_num_fruit)
      new_num_fruit = pick(
          num_fruit_to_pick, max_num_fruit, i, players)
      if new_num_fruit == 0:
        keep_playing = False
        break
  return num_spins


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(num_players, num_fruit, num_games):
  """Play games and compute basic statistics.
  
  Args:
    num_players: The number of players playing the game.
    num_fruit: The amount of fruit in each players tree.
    num_games: The number of games to play.

  Returns: Mean number and standard deviation of spins
    needed to finish a game.
  """
  spins_per_game = []
  while num_games > 0:
    players = [num_fruit] * num_players
    spins_per_game.append(play(players, num_fruit))
    num_games -= 1
  return (mean(spins_per_game), stddev(spins_per_game))


if __name__ == '__main__':
  num_players, num_fruit, num_games = map(int, sys.argv[1:4])
  mean_spins, stddev_spins = trials(
      num_players, num_fruit, num_games)
  print '%d,%f,%f' % (num_players, mean_spins, stddev_spins)