# How many spins does it take to complete a game of Hi Ho! Cherry-O?

I recently picked up this game for my 2-year-old daughter, who is learning how to count. I find this game fairly infuriating to play by the actual rules. It contains a spinner with the 7 following outcomes:

• Gain 1 Cherry
• Gain 2 Cherries
• Gain 3 Cherries
• Gain 4 Cherries
• Lose 2 Cherries (x2)
• Lose all Cherries

Play is to 10 Cherries.

Question: On average, how many spins will it take to finish the game?

(Edit: I had another question about "expected # of Cherries gained from a spin," but it turns out to be rather difficult to define due to that pesky "lose all your Cherries" option.)

• Might actually be better suited to math.stackexchange.com. But, the lose all cherries option might make the questions needing more clarification. For instance, is the expected number even well defined? – Aryabhata Jun 20 '11 at 6:49
• FYI, this is a question about probability, not statistics. I've re-tagged. – Adam Wuerl Jun 20 '11 at 13:23
• @Aryabhata By "for a given spin" I meant: "I have 3 Cherries - how many would I expect to gain?" This should be well defined for all Cherry counts 0-9. – Mag Roader Jun 20 '11 at 14:26
• Can you clarify your request for expected # of cherries? I don't think it's quite defined enough to give a mathematically precise answer. As you note, the expected value is heavily dependent on the number of cherries pre-spin. Averaging together these expected values wouldn't be useful, IMHO. A table of expected cherries as a function of cherries could be tabulated, but that would be heavily influenced (in a non-helpful way) by the possibility of losing all. I think much more useful would be the average change if you don't lose them all, as a function of # of cherries pre-spin. – Adam Wuerl Jun 20 '11 at 15:19
• I don't know that this is easy to verify, but each of the seven outcomes is equally likely (same width on the spinner), right? – Dave DuPlantis Jun 20 '11 at 20:53

Looking at the work that's been done so far, it seemed to me that this is basically just a Markov chain, and in looking for ways to calculate Markov chains, I found that someone has been there and done that.

The data from his work matches the simulations here, which should be no surprise given that the rules are very easy to code:

``````Minimum game length: 3
Expected game length: 15.8
Maximum game length: Unbounded
50th percentile (median): 12
95th percentile: 40
25th percentile: 7
75th percentile: 21
``````

He also posts the Matlab code that he used to calculate the chain ... it's actually pretty simple, comparatively speaking.

The Markov chain transition matrix shown below lists the probabilities of transitioning from one state (i.e. number of cherries pre-spin) to another (number of cherries post-spin).

``````          # of cherries after spin
0   1   2   3   4   5   6   7   8   9  10
--------------------------------------------
0 | 3/7 1/7 1/7 1/7 1/7  0   0   0   0   0   0
1 | 3/7  0  1/7 1/7 1/7 1/7  0   0   0   0   0
# 2 | 3/7  0   0  1/7 1/7 1/7 1/7  0   0   0   0
3 | 1/7 2/7  0   0  1/7 1/7 1/7 1/7  0   0   0
b 4 | 1/7  0  2/7  0   0  1/7 1/7 1/7 1/7  0   0
e 5 | 1/7  0   0  2/7  0   0  1/7 1/7 1/7 1/7  0
f 6 | 1/7  0   0   0  2/7  0   0  1/7 1/7 1/7 1/7
o 7 | 1/7  0   0   0   0  2/7  0   0  1/7 1/7 2/7
r 8 | 1/7  0   0   0   0   0  2/7  0   0  1/7 3/7
e 9 | 1/7  0   0   0   0   0   0  2/7  0   0  3/7
10 |  0   0   0   0   0   0   0   0   0   0   0
``````
• +1 for Markov chains, which is really the only way to analytically model this type of problem, and for finding prior art. I notice everyone else with a correct answer used a Monte Carlo simulation that they had to code up themselves. I wonder what was the fastest, C, Python, or Google. :) – Adam Wuerl Jun 21 '11 at 2:51
• Good call on finding the paper. I was just about to try and invert the 10x10 matrix. – ICR Jun 21 '11 at 7:59

The mathematics to take into account the fact it cuts off at 0 and 10 (i.e. spinning -2 when you are on 1 will leave you on 0, not -1) and the "loose all" result are quite complex.

Instead I've opted for a simulation. This was run with 10,000,000 simulations, which should be more than enough to get a good result.

Here is a histogram of the result. The x-axis shows the number of spins, while the y-axis shows the number of results in the simulation that took that number of spins. The average (mean), shown by the red line, is 15.8.

Here is the C# code I used to generate the results.

``````using System;
using System.Linq;
using System.Collections.Generic;

public static class CherryO {
private static Random rng = new Random();

const int NumRuns = 10000000;
const int NumSquares = 10;

public static void Main() {
int total = 0;
Dictionary<int, int> totalTurns = new Dictionary<int, int>();

for (int i = 0; i < NumRuns; i += 1) {
int turns = GetNumTurns(NumSquares);
total += turns;
if (!totalTurns.ContainsKey(turns)) {
} else {
totalTurns[turns] += 1;
}
}

int max = totalTurns.Keys.Max();
for (int i = 0; i <= max; i += 1) {
if (!totalTurns.ContainsKey(i)) {
}
Console.Write("{0} ", i);
}

Console.WriteLine();

var list = from kvPair in totalTurns
orderby kvPair.Value
select kvPair.Key;
foreach (int i in list) {
Console.Write("{0} ", i);
}

Console.WriteLine((double)total / NumRuns);
}

public static int GetNumTurns(int target) {
int position = 0;
int turns = 0;

while (true) {
int spin = GetSpin();
turns += 1;

if (spin == 0) {
position = 0;
} else {
position += spin;
}

if (position >= target) {
return turns;
}

if (position < 0) {
position = 0;
}
}
}

public static int GetSpin() {
int result = rng.Next(0, 7);

if (result == 5 || result == 6) {
return -2;
}

return result;
}
}
``````
• This is a good way to show the answer to part 2, now we just need a simulation for part 1. – Lance Roberts Jun 20 '11 at 13:57
• It looks like your mean is actually the expected value multiplied by 100. – Lance Roberts Jun 20 '11 at 16:07

I wrote something to enumerate the relevant states and then print out the probabilities it found that way. Somehow a simulation felt like a cop-out to me :)

I believe this game is for more than one player? And it ends when ANY player gets 10 cherries, right? The code and results below assume that. For the two-player case, I got a mean end turn of around 9.56. Since I was counting turns as every player spinning once, that's two spins per turn, so let's say that in the mean case, it takes between 19 and 20 spins for the game to end when two people are playing. It looks like the median is lower: about 15 spins, so half of the two-player games should end on or before the 15th spin.

The original question makes it sound like the one-player case is what was being considered so here is the info for that one. For one player: the mean game length is 15.8 spins and the median game length is between 11 and 12 turns (half end on or before 11, half on or after 12 spins).

Here is the code to generate the data used above. Warning: It gets really slow as you add players (exponential runtime in number of players, but only quadratic in terms of the number of turns). You can change the values of turn_cap and num_players at the top of the file to match what you want to find out. It only enumerates up to turn_cap, because you probably don't care beyond that. Games that end later ARE still taken into account, it just doesn't spit out data for them.

(Python 2.5):

``````from copy import deepcopy
from sys import stdout
num_players = 2
turn_cap = 50 # I assume everybody is sick of it by this point
print_merges = False
print_num_states = False
print_turn_progress = True
ignore_score_of_finished_games = True

def flatten(list_of_lists):
r"""helper for flattening a list of lists into a single list"""
return [item for sub_list in list_of_lists for item in sub_list]
def count(iterable,p=bool):
r"""return for how many items in iterable the predicate p evaluates to true"""
n = 0
for item in iterable:
if p(item):
n += 1
return n
def lists_the_same(l0,l1):
return len(l0)==len(l1) and \
all(l0[i]==l1[i] for i in range(len(l0)))
def split_list(items,p):
r"""split the list "items" into two lists based on a predicate "p"

returns a tuple. (items where the predicate is true, items where the predicate is false) """
for i in items:
if p(i):
good.append(i)
else:
class World:
def __init__(self, num_players=2, probability=1.0):
self.player_scores = [0 for x in range(num_players)]
self.probability = probability
self.turn_number = 0
self.ended_on_turn = None
self.num_players = num_players
def check_win(self):
if any(( (score>=10) for score in self.player_scores)):
self.ended_on_turn = self.turn_number
def gain_cherries(self, player_index, num_cherries):
self.player_scores[player_index] += num_cherries
self.check_win()
def lose_cherries(self, player_index, num_cherries):
self.player_scores[player_index] = max(0, self.player_scores[player_index] - num_cherries)
def lose_all_cherries(self, player_index):
self.player_scores[player_index] = 0
def run_turn(self):
r"""if not ended, it splits the world into 7 new worlds based on each player's spin"""
if None==self.ended_on_turn:
self.turn_number += 1
worlds = [self]
for i in range(self.num_players):
worlds = flatten([w.run_player_turn(i) for w in worlds])
return worlds
else:
return [self]
def run_player_turn(self, player_index):
new_worlds = [deepcopy(self) for i in range(7)]
for w in new_worlds:
w.probability = self.probability / 7.0
new_worlds.gain_cherries(player_index,1)
new_worlds.gain_cherries(player_index,2)
new_worlds.gain_cherries(player_index,3)
new_worlds.gain_cherries(player_index,4)
new_worlds.lose_cherries(player_index,2)
new_worlds.lose_cherries(player_index,2)
new_worlds.lose_all_cherries(player_index)
return new_worlds
def mergable(self, other):
if world_ended(self) and ignore_score_of_finished_games:
return ( (self.ended_on_turn == other.ended_on_turn) and
(self.num_players == other.num_players) )
else:
return ( lists_the_same(self.player_scores, other.player_scores) and
(self.turn_number == other.turn_number) and
(self.ended_on_turn == other.ended_on_turn) and
(self.num_players == other.num_players) )
def merge(self, other):
w = deepcopy(self)
w.probability += other.probability
return w
def __str__(self):
return ( str(self.player_scores) + ", " +
"p:" + str(self.probability) + ", " +
"ended on:" + str(self.ended_on_turn) + ", " )
def collapse_duplicate_worlds(world_list):
r"""look through the list of worlds, find ones that can be merged
and merge them, modifying the list in place"""
i0 = 0
while i0 < len(world_list):
i1 = len(world_list) - 1
while i1 > i0+1:
w0 = world_list[i0]
w1 = world_list[i1]
if w0.mergable(w1):
world_list[i0] = w0.merge(w1)
if print_merges:
print "merging",w0
print "with",w1
del world_list[i1]
i1 -=1
i0 += 1
def dump_stats(worlds):
print 'turn\tON\tBY'
p_on = [0.0 for i in range(turn_cap+1)]
p_by = [0.0 for i in range(turn_cap+1)]
for w in worlds:
if world_ended(w):
turn = w.ended_on_turn
p_on[turn] += w.probability
for i in range(turn, turn_cap+1):
p_by[i] += w.probability
for i in range(1,turn_cap+1):
print str(i)+'\t'+str(p_on[i])+'\t'+str(p_by[i])
def world_ended(w):
return None!=w.ended_on_turn
def main():
worlds = [World(num_players)]
finished_worlds = []
for i in range(turn_cap):
if print_turn_progress:
print "turn#:",i+1
worlds = flatten([w.run_turn() for w in worlds])
collapse_duplicate_worlds(worlds)
done, worlds = split_list(worlds,world_ended)
finished_worlds.extend(done)
if print_num_states:
print len(worlds),"unfinished world states"
print len(finished_worlds),"finished world states"
finished_worlds.extend(worlds)
dump_stats(finished_worlds)

if "__main__"==__name__:
main()
``````
• I'm not sure what's wrong with your code, but it doesn't appear to be giving the right results. It sounds like you were attempting the same type of Markov chain approach mentioned in another answer. Perhaps the referenced paper can help. – Adam Wuerl Jun 21 '11 at 2:48
• How did you determine that I got the wrong results? Please note that the Markov Chain linked does not take into account that there are multiple players. Hi Ho! Cherry-O is a 2-4 player game. – ExciteMike Jun 21 '11 at 3:03
• You know what? Good point. The other simulations and the Markov chain example are all answering the question of how many spins it takes to amass 10 cherries, and now that I think about it, that is a totally different question than how many turns (i.e. each player spinning once) it takes to end the game. In fact, I think you're the only person to answer what is really the actual question being asked. I think we could validate your sim by running it with num_players = 1 and seeing if the results match the others. – Adam Wuerl Jun 21 '11 at 3:06
• Bug fix for the code above. Setting num_players up at the top wasn't being respected. The first line of main should be `worlds = [World(num_players)]` (I can't edit w/o losing the image because my reputation isn't high enough) – ExciteMike Jun 21 '11 at 3:56
• If you make the edit to the code and also put the link to the image in the body we'll edit the post for you. I'd recommend two runs: one for 1-player to prove your code matches the Markov result, and one for 2-player. – Adam Wuerl Jun 21 '11 at 4:00

This is actually a pretty interesting question. I also decided to write a simulation. The results are quite interesting, and tend to show a bit about how careful you have to be to get a good simulation. For those who care, here's a bit of code:

[Edit: replacing code due to stupid mistake]
[Edit2: added code to compute average gain per spin]

``````#include <iostream>
#include <time.h>
#include <vector>
#include <numeric>
#include <algorithm>
#include "bounded.h"

static const int win = 10;
static const int games = 20000000;
static const int init[] = { 1, 2, 3, 4, -2, -2, -10};

int rand_lim(int limit) {
int divisor = RAND_MAX/(limit+1);
int retval;

do {
retval = rand() / divisor;
} while (retval > limit);

return retval;
}

int main(){
srand(unsigned(time(NULL)));
std::vector<char> spin_vals(init, init+7);
std::vector<char> gains;

std::vector<char> spins;
unsigned total_spins = 0;

for (unsigned game=0; game<games; game++) {
unsigned current_spins = 0;
bounded<int, 0, win> current_game_val;
while (current_game_val != win) {
++total_spins;
++current_spins;
int current_spin = spin_vals[rand_lim(spin_vals.size()-1)];
int old_val = current_game_val;
current_game_val = current_game_val + current_spin;
gains.push_back(current_game_val - old_val);
}
spins.push_back(current_spins);
}

double mean_spins = (double)total_spins / games;

std::cout << "Mean spins/game: " << mean_spins << "\n";

std::vector<char>::iterator median = spins.begin()+games/2;

std::nth_element(spins.begin(), median, spins.end());

std::cout << "Median spins/game: " << (int)*median << "\n";

double total_gains = std::accumulate(gains.begin(), gains.end(), 0.0);

double mean_gain = total_gains / gains.size();

std::cout << "Mean gain per spin: " << mean_gain << "\n";

return 0;
}
``````

For output, I get:

Mean spins/game: 15.7967
Median spins/game: 12
Mean gain per spin: 0.633044

The gain per spin seems to fit with the number of spins per game -- if it takes ~16 spins to get to 10, then the average gain per spin should be ~10/16.

• Your "lose all" option is always -10 cherries. I think the line adding to current_game_val needs a max in there to ensure it doesn't go negative. – Mag Roader Jun 20 '11 at 18:49
• The distribution of the random number generator doesn't seem to be what causes the difference between our results. I've swapped in a cryptographic strength random number generator, as well as randomly ordered the sequence of the items chosen - it makes no difference. – ICR Jun 20 '11 at 18:51
• @Mag That's achieved by the bounded type. – ICR Jun 20 '11 at 18:51
• Shouldn't `rand_lim(spin_vals.size())` be `rand_lim(spin_vals.size() - 1)`? If I make that the results of your code matches with mine :) The reason it worked when you replaced it with `return rand() % limit` is that it should actually be `return rand() % (limit - 1)`, so both the errors cancelled each other out. – ICR Jun 20 '11 at 19:05
• @ICR: Yes, you're quite right, it should be. Posting corrected code now... – Jerry Coffin Jun 20 '11 at 19:17

The following calculations are based on having an equal probability of being at any particular number (0-9), when the spinner is spun.

The expected number of Cherries per spin can be calculated as follows:

``````Contributions of Spin (1/7 probability ea):

1:  (1*10)/10                  = 1
2:  (2*9+1)/10                 = 1.9
3:  (3*8+2+1)/10               = 2.7
4:  (4*7+3+2+1)/10             = 3.4
-2:  -(2*8+1+0)/10              = -1.7
-2:  -(2*8+1+0)/10              = -1.7
-all:  -(0+1+2+3+4+5+6+7+8+9)/10  = -4.5

Total = 1.1

Total/7 = 0.157143 <-- expected value
``````

So theoretically, the average game should take `10/0.157143 = 63.5` spins.

Note with much more precision, it comes out to `63.636363....` spins.

I've now run a simulation to figure out the probabilities for what your score is when you spin and get the `Lose All` result. I ran 3 10,000,000 simulations and averaged the results for the ALL, and 1 10,000,000 simulation for the others, so here are the new calculations:

``````Contributions of Spin (1/7 probability ea):

1:  (1*10)/10                  = 1
2:  (2*9*0.967145 +
1  *0.032855)/10          = 1.74415
3:  (3*8*0.923705 +
2  *0.043412 +
1  *0.032884)/10          = 2.22886
4:  (4*7*0.865895 +
3  *0.058240 +
2  *0.042263 +
1  *0.033602)/10          = 2.45379
-2: -(2*8*0.563137 +
1  *0.079143 +
0  *0.357720)/10          = -0.90893
-2: -(2*8*0.563137 +
1  *0.079143 +
0  *0.357720)/10          = -0.90893
-all:  -(0 * .358065 +
1 * .078969 +
2 * .092976 +
3 * .094948 +
4 * .107013 +
5 * .069808 +
6 * .064553 +
7 * .057246 +
8 * .042941 +
9 * .033480)             = -2.75975

Total = 2.84919

Total/7 = 0.40703 <-- expected value
``````

So theoretically, the average game should take `10/0.40703 = 24.56839` spins.

• It's also going to be slightly off because of the limits. +2 on 9 is going to make it to 10, and -2 on 1 is going to cap at 0. The effect of these are going to be pretty small though. – ICR Jun 20 '11 at 8:30
• Sorry, have to downvote just because the things not modeled (i.e. impact of lose all cherries and not being able to have negative cherries) make this result mathematically incorrect. – Adam Wuerl Jun 20 '11 at 13:29
• The probability of being on a particular number are far from being evenly distributed. They're going to be quite heavily skewed towards lower numbers. – ICR Jun 20 '11 at 18:08
• The probability of being on a particular square is dependant on how many spins have happened. It's trivial to calculate the probability of being on a given square after a given number of spins (enumerate all the combinations it takes to get there), but translating that into the probability of being on a given square regardless of the number of spins is difficult and I've not yet worked that out. – ICR Jun 20 '11 at 19:14
• @ICR, ok, updated to the next level. Note, I'm also getting the 15.8 - 15.9 when running simulations for length of game, so there may still be some probability thing we need to take into account. – Lance Roberts Jun 20 '11 at 20:48