**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.htmI 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