Analysis of CandyLand.

NOTE With little variation this analysis can be used for "Hi-Ho Cherry-O" too. (That being a smaller game, we can carry out the multi-player analogues.)

It has been a couple of decades since I played this game with my own kids so I am indebted to Lou Scheffer for writing me to say he had done an analysis, which is available at

   http://www.lscheffer.com/CandyLand.htm
I am using his description of the game and the picture of the game board he provided. I didn't read through his C code but it looks like I am mostly recreating his ideas. Here's the summary of my analysis, and some Maple code.

I give below an exact expression for the expected number of turns for one player to finish (about 39.2). The minimal game length is 4 turns; the mode is 17 turns (2.3% of all games); the median is 32 turns; the mean (39.2) is higher because the distribution of game lengths has a long tail -- one game out of 200 is still unfinished after 150 turns, and there is no theoretical maximum length at all.

Scheffer's analysis does not give the exact fraction for the expected one-person game length, but provides decimal estimates for the expected lengths not only for one-player games but for multiple-player games as well. He's also got pictures, etc.

Here's how I computed the numbers I did, using Maple for symbolics processing.

In addition to the "Start" space (cell #0), there appear to be 134 locations
where the players' pieces can land: a regular repetition of the colors
Red Violet Yellow Blue Tan Green, with a Pink cell interspersed to
become cells numbered:
  9 (Plumpy)
 18 (Mr. Mint)
 43 (Jolly)
 75 (Gramma Nut)
 96 (Princess Lolly)
104 (Queen Frostine)

In addition, some cells are "sticky":
 48 (Yellow)
 86 (Blue)
121 (Red)

There are "bridges" linking cells 5 and 59, and  34 and 47.

[Note: in the Maple code below, the row- and column- numbering starts at 1,
so those indices are greater by 1 than the cell numbers shown above.]

I will assume that when the forced location is past the end of the
trail, the player goes to the last cell #134 and wins.


The play of the game is completely determined by the order of the
cards at the start of the game (though I guess if the pile of cards
is exhausted before a player wins, then one could shuffle the cards
before restarting). However, for ease of analysis I will assume the
cards are reshuffled _after each card is drawn_. Thus in my analysis
there is a chance that two players will each be immediately transported
to cell #8 (by drawing the "Plumpy" card) even though in the real
game the second player is assured that this cannot happen as soon
as the first player has fallen victim.

I will follow Scheffer's assumed distribution of the cards: 66 total
cards, making the probabilities on each turn be:
  8/66  of moving to the next Red square
  8/66  of moving to the next Violet square 
...
  2/66  of moving to the second Red square from present location
...
  1/66  of moving to cell #8
  1/66  of moving to cell #17, etc.
When the forced location is the bottom of one of the two "bridges" we
replace the destination with the one at the top of the bridge (that is,
no one is ever really at cells #5 or #34.) 

With this small variation of the rules, the game becomes one of motion
around a Markov process with 135 cells (counting Start), starting with 
a 100% likelihood of being in cell #0.

Rather than type in the 135^2 entries of the transition matrix  P, I can
have Maple type them in. Start with 21 cyles of regular colors, add
2/6 of another cycle, intersperse the pinks, remove the bridge bottoms,
and make the stickies special. Details are below.

With the transition matrix  P  in hand, we can duplicate the ideas we
have used once before to analyze  Chutes and Ladders (repeated verbatim).

Let  V_n  be the vector whose  i-th coordinate is the probability
that the marker is in state  i  after  n  moves. (Note that we start
our enumeration with state  0, so that e.g.  V_0 = [1, 0, ..., 0]' ,
where the dash indicates transpose.) Then we have  V_n = P V_{n-1} = P^n V_0.

Note in particular that if  U = [0, ..., 0, 1]'  then  U' V_n  is the
probability that the piece is in state 134 after  n   moves; thus the
probability that the marker reaches state 134 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 134 as
the sum    sum( n U'(P^n - P^{n-1}) V_0 , n >= 1 )  . It is possible to
estimate this numerically, since for large  n  the multiplier of  n
decreases as  a b^n  for some  b < 1. Rather than show these estimates, 
we use some algebraic feats to get the exact value. (These are quite close
to the values Scheffer has obtained numerically.)


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 <= N )
   = U' sum( n (P^n - P^{n-1}) , 1 <= n <= N )  V_0
   = U' [ - I - sum( P^n , 1 <= n <= N-1 ) + N P^N ]  V_0

Unfortunately,  N P^N  does not converge to zero. But if we let  J  be
the 135x135 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 <= N-1 ) + N Q^N ]  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 <= N-1 ) - N Q^N ]  V_0, 
so that we are seeking  U' ( J V_0 - X ) = 1 - U' X,  then we find  
  (I - Q)X = [ (I - Q^N) - N(I-Q)Q^N ] V_0
           = [ I - Q^N(I + N(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

851001958949056946439108086696111931381783228154211217851493370896287227715513\
700362911807021345921059784443552747964167288130905022340827130121051433352370\
58223704797492635000525593595263/
217308053771771717982809395842849762095874047768044784939051871967672048447381\
766135315767713219490165900572111150753007023779858130453906451821772799887787\
3988212783989568261314165080690

moves, which is approximately 39.2. 



           #####  Maple Code Follows... #####

CELLS:=[seq( op([R,V,Y,B,T,G]), i=1..21), R, V]:
ACELLS:=[            Start,
 seq(CELLS[i],i= 1.. 8), P,
 seq(CELLS[i],i= 9..16), P,
 seq(CELLS[i],i=17..40), P,
 seq(CELLS[i],i=41..71), P,
 seq(CELLS[i],i=72..91), P,
 seq(CELLS[i],i=92..98), P,
 seq(CELLS[i],i=99..128)   ]:  #

#Form and initialize transition matrix:
P:=matrix(135,135):  for i to 135 do for j to 135 do P[i,j]:=0: od:od:

for j to 135 do  #figure out the transition probabilities from cell j
  for color in [R,V,Y,B,T,G] do
    found:=0:
    for i from j+1 to 135 do
       if ACELLS[i]=color then 
          if found=1 then found:=2: P[i,j]:=P[i,j]+2/66: fi:
          if found=0 then found:=1: P[i,j]:=P[i,j]+8/66: fi:
       fi:
    od: 
    if found=1 then P[135,j]:=P[135,j]+2/66: fi:
    if found=0 then P[135,j]:=P[135,j]+10/66: fi:
  od:
  for i in [10, 19, 44, 76, 97, 105] do P[i,j]:=P[i,j]+1/66: od:
  #bridges:
  P[60,j]:=P[60,j]+P[6,j]: P[6,j]:=0:    P[48,j]:=P[48,j]+P[35,j]: P[35,j]:=0:
od:

#stickies:
for j in [49,87,122] do
  for i to 135 do P[i,j]:=0: od:
  P[j,j]:= 56/66: P[j+6,j]:=8/66: k:=12:if j=87 then k:=k+1:fi: P[j+k,j]:=2/66:
od:

#We decree the last cell to be an absorbing state:
for i to 134 do P[i,135]:=0:od:  P[135,135]:=1:

#Check:
for j to 135 do if add(P[i,j],i=1..135)<>1 then lprint(j) fi:od:             


#Now let's compute the average length of a game, using the theory above.
Q:=matrix(135,135):
 for i to 134 do for j to 135 do Q[i,j]:=P[i,j]:od:od:
 for j to 135 do Q[135,j]:=P[135,j]-1:od:
R:=matrix(135,135);
 for i to 135 do for j to 135 do R[i,j]:=-Q[i,j]:od:od:
 for i to 135 do R[i,i]:=1 + R[i,i]:od:
ans:=linsolve(R,V0);
1-ans[135]; #shown above. This is approximately equal to 
evalf(%);
# 39.1610869536765400409618224660851252118349624755979116591 ...


#We can figure out numerically the vector of probabilities V_i that a player
#is in each cell after  i  moves. The initial distribution is

V0:=vector(135,[1.0,0$134]):

for i to 50 do V||i:=multiply(M, V||(i-1) ): od:

#So e.g. there is a 50.8% chance that the player has ended after 32 turns.
#That rises to 99.5% after 150 turns. About  2.281% of the games end on
#the 17th turn; that's the most common stopping moment. 



See also BoardGameGeek.com

Last modified 2006-07-20