## Hi Ho! Cherry-O

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