A MATHEMATICAL ANALYSIS OF THE CHILDREN'S GAME, HI-HO CHERRY-O
Game synopsis:
Players alternate turns and activities of each player are independent
of each other.
Each player begins with a tree full of 10 cherries, and an empty bucket.
A turn consists of spinning a spinner and taking the action specified.
Game ends when one player has an empty tree (and full bucket).
The spinner is divided into seven equal arcs, and a player's action
depends on which arc is randomly selected:
1 cherry : pick one cherry off the tree & put in bucket
2 cherries: pick two
3 cherries: pick three
4 cherries: pick four
Bird: take one cherry out of bucket and put back on tree
Dog : take one cherry out of bucket and put on tree
Spilled bucket: put all cherries in bucket back on tree
Actually I have conflicting memories of the "Bird" and "Dog" cases,
so I will do the analyses under three interpretations of the rules:
a) Bird = Dog = move one cherry from bucket to tree
b) Bird = Dog = move two cherries from bucket to tree
c) Bird = move one cherry back; Dog = move two cherries back.
In any case, each player's status at any point in the game is completely
tracked by the number of cherries still on his or her tree.
Let's suppose a player is playing alone and watch what happens. There
are 11 possible states for the game this way, the last meaning "Game over".
We label the states so state #1 is the starting position, and more generally
when the number of cherries is i we will say we are in state 11-i
(including when i=0, so that we are in the "Game over" state.)
There is at each turn a probability P[i,j] of moving from state i to
state j . We can set these up in an array. Here it is in Maple
N:=11: # Number of states.
P:=matrix(N,N,[0$(N^2)]):
P[N,N]:=1: # When you're at "Game over", the game is really over!
# Now the game rules tell us how to fill in each column:
#
b:=1: # 1 or 2 -- then number of cherries lost to a bird. Likewise
d:=1: # 1 or 2 -- then number of cherries lost to a dog.
for n to N-1 do # n = state number; i = number of cherries on tree.
i:=11-n :
nexts := [seq(max(0,i-k), k=1..4), min(10,i+b), min(10,i+d), 10]:
for s in nexts do
if s=0 then P[N,n]:=P[N,n]+1/7
else m:=11-s: P[m,n]:=P[m,n]+1/7:
fi:
od:
od:
print(P);
[3/7 , 3/7 , 1/7 , 1/7 , 1/7 , 1/7 , 1/7 , 1/7 , 1/7 , 1/7 , 0]
[ ]
[1/7 , 0 , 2/7 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0]
[ ]
[1/7 , 1/7 , 0 , 2/7 , 0 , 0 , 0 , 0 , 0 , 0 , 0]
[ ]
[1/7 , 1/7 , 1/7 , 0 , 2/7 , 0 , 0 , 0 , 0 , 0 , 0]
[ ]
[1/7 , 1/7 , 1/7 , 1/7 , 0 , 2/7 , 0 , 0 , 0 , 0 , 0]
[ ]
[0 , 1/7 , 1/7 , 1/7 , 1/7 , 0 , 2/7 , 0 , 0 , 0 , 0]
[ ]
[0 , 0 , 1/7 , 1/7 , 1/7 , 1/7 , 0 , 2/7 , 0 , 0 , 0]
[ ]
[0 , 0 , 0 , 1/7 , 1/7 , 1/7 , 1/7 , 0 , 2/7 , 0 , 0]
[ ]
[0 , 0 , 0 , 0 , 1/7 , 1/7 , 1/7 , 1/7 , 0 , 2/7 , 0]
[ ]
[0 , 0 , 0 , 0 , 0 , 1/7 , 1/7 , 1/7 , 1/7 , 0 , 0]
[ ]
[0 , 0 , 0 , 0 , 0 , 0 , 1/7 , 2/7 , 3/7 , 4/7 , 1]
Now let V_n be the vector whose i-th entry shows the probability
of being in state i after n moves. Thus V0 = [1,0,0,0,0,0,0,0,0,0,0]
and V_n = P V_{n-1} for n = 1, 2, 3, ... (Thus V_n = P^n V_0 .)
V0:=vector(N,[1, 0$(N-1)]):
for n from 1 to 200 do V||n:=evalm(P &* V||(n-1)):lprint(n):od:
Well, now, what would be like to know?
We can calculate e.g. V32, which is numerically about
lprint(seq(evalf(V32[i]),i=1..N));
[.01395928618, .003617465889, .004456120435, .005298595646,
.005733821713, .004460388246, .004547461514, .004401261895,
.003893415811, .002736647307, .9468955354]
and so we know that there is about a 95% chance that the game is
over by then; in 1.4% of the games the tree is full again at that time.
Etc. This is just a typical data point. Let's see some others:
for i to 20 do
lprint(i, evalf(V||i [N]), evalf(V||i [N] - V||(i-1) [N])):od:
for i in [30, 40, 50, 100, 150, 200] do
lprint(i, evalf(V||i [N]), evalf(V||i [N] - V||(i-1) [N])):od:
2, 0., 0.
3, .2915451895e-1, .2915451895e-1
4, .9412744690e-1, .6497292795e-1
5, .1723686559, .7824120902e-1
6, .2503718689, .7800321295e-1
7, .3228477444, .7247587558e-1
8, .3886102920, .6576254757e-1
9, .4479401309, .5932983884e-1
10, .5014382375, .5349810666e-1
11, .5497130643, .4827482678e-1
12, .5932979847, .4358492041e-1
13, .6326596832, .3936169855e-1
14, .6682110427, .3555135950e-1
15, .7003218107, .3211076796e-1
16, .7293250430, .2900323229e-1
17, .7555213977, .2619635472e-1
18, .7791824649, .2366106714e-1
19, .8005535835, .2137111865e-1
20, .8198563690, .1930278548e-1
30, .9349052924, .6975040366e-2
40, .9764780971, .2520423368e-2
50, .9915003856, .9107522856e-3
100, .9999476360, .5610920702e-5
150, .9999996774, .3456750164e-7
200, .9999999980, .2129618708e-9
So :
the earliest a person can win is after the third move;
there is no maximum game length, though only 1 game in 19,097 is still
going after the 100th move;
the median length of a 1-person game is 10 moves (i.e. 50% of the
games have finished by then);
the mode length is 5 (more people -- about 7.824% -- win on the fifth move
than at any other time).
To compute the mean game length we need to sum this total:
0% of games win on 2nd move
2.915% won on 3rd move
6.497% won on 4th move
etc.; (0)(2) + (0.02915)(3) + ... = about 13.44569237 :
evalf( add( i*(V||i [N] - V||(i-1) [N]), i = 1 .. 200 ));
I will now compute this value precisely:
We can now duplicate the ideas we have used once before to analyze
Chutes and Ladders (repeated verbatim).
Note in particular that if U = [0,0,0,0,0,0,0,0,0,0,1]' then U' V_n is the
probability (V_n)[N] that the piece is in state 0 after n moves; thus the
probability that the marker reaches state 0 precisely on the n-th move
is U'(P^n - P^{n-1}) V_0. Therefore, we may calculate the expected
number of moves after which the marker (first) reaches state 0 as
the sum sum( n U'(P^n - P^{n-1}) V_0 , n >= 1 ) .
OK, This is an infinite sum, which we must treat as a limit of the partial sums
sum( n U'(P^n - P^{n-1}) V_0 , 1 <= n <= K )
= U' sum( n (P^n - P^{n-1}) , 1 <= n <= K ) V_0
= U' [ - I - sum( P^n , 1 <= n <= K-1 ) + K P^K ] V_0
Unfortunately, K P^K does not converge to zero. But if we let J be
the 11x11 matrix with all columns equal to U and let Q = P - J,
then we observe Q J = P J - J^2 = J - J = 0 and J Q = J P - J^2 = J - J = 0
so that P^n = (Q + J)^n = Q^n + J^n = Q^n + J for n > 0. Thus
P^n - P^{n-1} = Q^n - Q^{n-1} for n > 1, and equals Q - I when n=1.
Therefore, we have essentially the same expansion as above,
= U' [ J - I - sum( Q^n , 1 <= n <= K-1 ) + K Q^K ] V_0
except that now the series converges; Q has no eigenvalues of norm 1 or more.
Indeed, if we let X = [ I + sum( Q^n , 1 <= n <= K-1 ) - K Q^K ] V_0,
so that we are seeking U' ( J V_0 - X ) = 1 - U' X, then we find
(I - Q)X = [ (I - Q^K) - K(I-Q)Q^K ] V_0
= [ I - Q^K(I + K(I-Q)) ] V_0 --> V_0
so we may compute our X as the solution to (I - Q) X = V_0.
As above, the expected number of games will be 1 - U' X .
I get the answer to be 525338478/39071135 (about 13.44569279, in
agreement with our previously-computed numerical answer) using Maple:
U:=[0$(N-1),1]:
J:=transpose( matrix(N,N, [seq(U,i=1..N)] ) ):
Q:=evalm( P - J ):
eye:=matrix(N,N,[0$(N^2)]): for i to N do eye[i,i]:=1:od:
X:=linsolve( evalm( eye - Q ), V0 ):
1 - X[N] ; lprint(%);evalf(%);
When we set d:=2 instead (with, still, b:=1) we get slightly
different answers:
the earliest a person can win is still after the third move;
there is still no maximum game length, though the 100+ move games are
a bit more common (1 in 6472).
the median length of a 1-person game is up to 11 moves
the mode length is still 5, but it's a bit rarer (happens 7.16% of the time)
the mean length is up to 1179248/80915 = 14.5739109
When we raise b:=2 as well, the games are a bit longer yet:
the earliest a person can win is still after the third move;
there is still no maximum game length, though the 100+ move games are
still more common (1 in 2546).
the median length of a 1-person game is up again to 12 moves
the mode length is still 5, but it's a bit rarer yet (only 6.54% of the time)
the mean length is up to 494813746/31313403 = 15.8019793
==============================================================================
What about 2-person games?
Here it helps to think about the circles standing in line waiting to spin.
A _turn_ now consists of the first player in line spinning and taking
the required action, then moving to the end of the line of players. (No
other players change their state.)
In other words, if player #1 was in state i1 and moves to state i1',
with player #2 in state i2 and so on, then we say the whole game
has moved from state (i1, i2, ..., i_n) to state (i2, i3, ..., i_n, i1').
We can make the transition matrix which represents this. For example when
there are two players only, we will describe a matrix with 101 entries:
each combination of 1 through 10 cherries per player, plus a "game over" state.
When the player "at bat" has i cherries on the tree and the other player
has j cherries on the tree, then we will encode this as state
(11-i) + 10*(11-j - 1) = 111 - i - 10*j
(so that in particular we start at state #1.) We will add a 101st state
to represent "game over". We know there are at most seven possible states
to which we can move after one spin: from (i,j) to (j, i') pairs of
cherries, where i' is one of
i-1, i-2, i-3, i-4, as long as these is at least 1 cherry left on the tree
i+b, i+d, as long as these are at most 10
10
or else we will move to the 101st state. Then we can compute the
transition matrix with just some minor modifications of the previous steps:
merge:=proc(i,j) 111-i-10*j: end:
split:=proc(n) m:= ((n-1) mod 10) + 1: i:=11-m: j:=10-(n-11+i)/10: [i,j]: end:
N:=101:
P:=matrix(N,N,[0$(N^2)]):
P[N,N]:=1: # When you're at "Game over", the game is really over!
#
b:=1: # 1 or 2 -- then number of cherries lost to a bird. Likewise
d:=1: # 1 or 2 -- then number of cherries lost to a dog.
for n to N-1 do # n = state number; i,j = numbers of cherries on trees.
ij:=split(n): i:=ij[1]: j:=ij[2]:
nexts := [seq(max(0,i-k), k=1..4), min(10,i+b), min(10,i+d), 10]:
for s in nexts do
if s=0 then P[N,n]:=P[N,n]+1/7
else m:=merge(j,s): P[m,n]:=P[m,n]+1/7:
fi:
od:
od:
So now we have our usual kind of transition matrix to play with.
We can repeat verbatim the Maple commands shown above (which now deal
with vectors and matrices of size N = 101). For example, we can see how
many games have finished by, or exactly on, the i-th spin:
1, 0., 0.
2, 0., 0.
3, 0., 0.
4, 0., 0.
5, .2915451895e-1, .2915451895e-1
6, .5745905193e-1, .2830453298e-1
7, .1205377254, .6307867349e-1
8, .1793949175, .5885719212e-1
9, .2502714813, .7087656377e-1
10, .3150263583, .6475487698e-1
11, .3795842623, .6455790397e-1
12, .4380576650, .5847340274e-1
13, .4923876202, .5432995516e-1
14, .5414648228, .4907720262e-1
15, .5859960802, .4453125742e-1
16, .6262026250, .4020654476e-1
17, .6624762778, .3627365284e-1
18, .6952299009, .3275362307e-1
19, .7247640586, .2953415776e-1
20, .7514361690, .2667211035e-1
30, .9101929829, .9622896800e-2
40, .9675482722, .3477273865e-2
50, .9882736031, .1256509087e-2
100, .9999277566, .7741043265e-5
150, .9999995549, .4769066254e-7
200, .9999999973, .2938104356e-9
So :
the earliest a person can win is after the fifth spin (which would be
player #1's third move, consistent with our findings in the 1-player case)>
there is no maximum game length, though only 1 game in 364,698,375 is still
going after the second player's 100th spin. (THis is much higher than
in the 1-player case -- the game only continues this long if BOTH players
have been extremely unlucky) Indeed, this number is very nearly 19097^2.
Perhaps a better comparison is to the 100th move (i.e. after each player
has had only 50 spins); about 1 in 13,842 games is still running then.
the median length of a 1-person game is 14 spins (i.e. 50% of the
games have finished by then);
the mode length is 9 (more games -- about 7.087% -- are won on the ninth spin
than at any other time). Note that this is the 5th spin for the first
player, again giving a situation comparable to the 1-player case.
The mean number of spins necessary to complete a 2-player game is
calculated exactly as before but gives the answer
102376 3300308288 6543999399 5444911935 0057552544 3302612819
0949606069 3624733325 8826563329/
6215 9223928511 6137040470 3239244450 1975607903 5697834641
5957226811 6177902491 8117082495
which is about 16.47001419. This is more than with just one player,
but not as much more as I would have thought: this means an average
of only 8.235 spins per player, which is much less than with one
player playing alone. (Of course it makes sense that as two players
essentially play simultaneous games, it will take less long for
_just one_ of them to reach the end.)
We can compute the percentage of games won by the first player;
these are the games that complete after exactly an odd number of turns.
In the notation above, this would be the limit of the partial sums
sum( U' (P^{2n+1} - P^{2n}) V_0 , 0 <= n <= K )
sum( U' (Q^{2n+1} - Q^{2n}) V_0 , 0 <= n <= K ) + J V_0
= U' (Q-I) sum( (Q^2)^n, 0 <= n <= K ) V_0 + 1
and if we multiply that last sum by ( I - Q^2 ) we get I - (Q^2)^(K+1),
which converges to I ; that is, if we call that sum S then
( I - Q^2 ) S V_0 = V_0, so that S V_0 is the solution to the
linear equation (I-Q^2) X = V_0. In Maple:
U:=[0$(N-1),1]:
J:=transpose( matrix(N,N, [seq(U,i=1..N)] ) ):
Q:=evalm( P - J ):
eye:=matrix(N,N,[0$(N^2)]): for i to N do eye[i,i]:=1:od:
X:=linsolve( evalm( eye - Q&*Q ), V0 ):
evalm( (Q-eye) &* X ):
1 + %[N]; lprint(%);evalf(%);
I get
361 2803265966 7916962871 5030950042 6347842588 2967455399
8445026917 4613353824 7175129401/
690 8648284746 4512469251 6068203262 5115079211 7696150054
2794870122 0694582846 2133116969
which is about 0.5229392375. That leaves about 47% of the games
to be won by player #2, so we can see the advantage to player #1.
(We can also calculate the fraction won by player #2 as
sum( U' (P^{2n+2} - P^{2n+1}) V_0 , 0 <= n <= K )
sum( U' (Q^{2n+2} - Q^{2n+1}) V_0 , 0 <= n <= K )
= U' Q (Q-I) sum( (Q^2)^n, 0 <= n <= K ) V_0
that is, a simple multiplication by Q to adujst the computation near the end.)
When the Bird/Dog rules are changed to "1 (resp. 2) lost cherries",
the games take a little longer.
the earliest a person can win is still after the fifth spin, and of course
there is still no maximum game length.
the median length of a 1-person game is still 14 spins, though only
just 50.96% of games will be done by then.
the mode length is 9 but now that happens only about 6.51% of the time.
the mean length has risen to 17.51246384 moves, or more accuratly
714073 4437034168 9607558230 8135751408 3360981234 9211822772 5838704947/
40775 1559228985 1324123218 8673369464 3759323851 6592960933 9430402840
Player #1's advantage shrinks as the games grow longer; advantage to #1 is
539413 7563011345 3455127188 7233922690 4766059646 5659757150 2498219263/
1035957 0489660118 0574019180 8757569843 5210238799 9405068010 3180591208
i.e., player #1 wins about 52.07 % of the games.
If birds and dogs both cost us 2 cherries per visit, then the games are a
bit longer yet. Only 47.9% of the games are finished by spin #14, and the
median game length is 15 now. The most common games is still 9 moves.
The mean game is now about 18.65236229 moves:
92155 9322253511 9412926439 4445433491 7976218239 9227400213
7058002197 8029593448 6614085993/
4940 7110374943 1758376302 2429904171 4990573044 0531713137
3686781073 4371028840 7904907331
Advantage to player #1 has dropped to winning 51.87% of the games:
24652 1090214586 6808095560 9705710867 6091028723 5246875484
3225082426 1303457176 3311980787/
47524 8432953085 1351287704 8885228350 0114570208 7240400166
4885740105 3288084321 6525777695
I should probably remark that, mathematically speaking, the game is
easier to analyze when we define "game" to mean that BOTH players
have emptied their tree. For then the transition matrix P is
the Kronecker product P1\tensor P1 of the transition matrix P1
for the one-player game. Obviously games will tend to take longer
when play must continue past the first empty tree.
==============================================================================
What about 3-player games?
Here we need no new concepts but maybe more computing power...
A state is represented by one of the 1000 combinations (i,j,k) of
cherries in the trees, togther with an additional "game over" state.
A spin will move us from a state (i,j,k) to a state (j,k,i').
We can enumerate the states, sending (i,j,k) to the number
1+(10-i) + 10*(10-j) + 100*(10-k) = 1111 - i - 10*j - 100*k
In Maple:
merge:=proc(i,j,k) 1111-i-10*j-100*k: end:
xmod:=proc(a) ( (a-1) mod 10 )+1 : end: # need 10 mod 10 to be 10, not 0
split:=proc(n)
i:= xmod((111-n)) : # i:=11-m: lprint(i);
j:= xmod((111-n-i)/10): # j:=11-p: lprint(j);
k:= xmod((111-n-i-10*j)/100): # k:=11-q: lprint(k);
[i,j,k]: end:
N:=1001:
P:=matrix(N,N,[0$(N^2)]):
P[N,N]:=1: # When you're at "Game over", the game is really over!
b:=1: # 1 or 2 -- then number of cherries lost to a bird. Likewise
d:=1: # 1 or 2 -- then number of cherries lost to a dog.
for n to N-1 do # n = state number; i,j = numbers of cherries on trees.
ij:=split(n): i:=ij[1]: j:=[seq(ij[k],k=2..nops(ij))]:
nexts := [seq(max(0,i-k), k=1..4), min(10,i+b), min(10,i+d), 10]:
for s in nexts do
if s=0 then P[N,n]:=P[N,n]+1/7
else m:=merge(op(j),s): P[m,n]:=P[m,n]+1/7:
fi:
od:
od:
V0:=vector(N,[1, 0$(N-1)]):
for n from 1 to 20 do V||n:=evalm(P &* V||(n-1)):lprint(n):od:
for i to 20 do
lprint(i, evalf(V||i [N]), evalf(V||i [N] - V||(i-1) [N])):od:
# gives min, median, mode game length
U:=[0$(N-1),1]:
J:=transpose( matrix(N,N, [seq(U,i=1..N)] ) ):
Q:=evalm( P - J ):
eye:=matrix(N,N,[0$(N^2)]): for i to N do eye[i,i]:=1:od:
#mean game length:
X:=linsolve( evalm( eye - Q ), V0 ):
1 - X[N] ; lprint(%);evalf(%);
422278199 7581298198 8434657044 2394599485 9724142576 7699310652
5863707749 2571411650 1700086719 3590224343 4640919930 9016366046
7026331172 5092814245 3744581508 4812758611 5705085357 3404743787
8553129087 3137991729 3186141930 5491639147 7237089749 5179352257
3440665030 0047398393 0936577027 5708448001 6237711423 5300426920
6639444753 1417163432 7242767236 9835587545 4693242651 2274582512
4608587496 1391920255 9661215707 0913756750 5281956294 2537164568
2633460823 1379771776 9292089865 9257776457 5560874121 8491037240
2728679754 2320188739 5922134867 5120331236 3179566205 0091653534/
21749201 6406249888 6326351228 1996817576 9185836971 8217589189
0900218475 2872706056 8290430746 2041448930 0335126794 5975382968
6103455840 4074954082 4065710214 7914084212 1802578803 0909061313
7919109035 7226956837 9558997391 5703003632 5339797082 8827935078
7977120741 7663419739 5974560496 9717434943 0624594114 5792906483
5228485381 8370015027 2223852327 8833868609 6106604985 5973576811
7110896753 0766152608 2615392948 2661387530 2361928575 9347884469
0110338951 2571810560 1800075075 3139545259 9921702091 5720043880
2174724870 5180151054 3912259727 4089417775 7606082056 2856913305
19.41580232
Following the previous trend, this is an increase in total spins but
a decrease in spins-per-person. (Presumably the trend will continue: given
thousands of players playing together, it is reasonable to expect that one
of them will win on his or her third spin, so that the spins-per-person
will drop to around 2.5.)
It took Maple several hours to compute that linsolve() command.
That numerator has 539 digits.
Games won by player #k:
sum( U' (P^{3n+k} - P^{3n+(k-1)}) V_0 , 0 <= n <= K )
sum( U' (Q^{3n+k} - Q^{3n+(k-1)}) V_0 , 0 <= n <= K ) [ + J V_0 for k=0 ]
= U' Q^{k-1} (Q-I) sum( (Q^3)^n, 0 <= n <= K ) V_0 [ + 1 for k=0 ]
#Why solve (I-Q^3)X=V0 and then compute X1=(Q-I)X ? That makes X1
#be the solution to (I+Q+Q^2)X1=(-V0).
#
#A:=evalm( eye - Q&*Q&*Q ):
#st:=time(); X:=linsolve( A, V0 ): et:=time-st();
#X1:=evalm( (Q-eye) &* X ):
#
st:=time(); B:=evalm( eye + Q + Q&*Q ): et:=time - st();
st:=time(); X1:=linsolve( B, -V0 ): et2:=time - st();
#For player #1
1 + X1[N]; lprint(%);evalf(%);
#For player #2
X2:=evalm( Q &* X2 ): X2[N]; lprint(%);evalf(%);
#For player #3
X3:=evalm( Q &* X2 ): X3[N]; lprint(%);evalf(%);