Mathematical analysis of CandyLand (classic version)

Candyland is a simple game for kids.  Each player starts his or her token at the beginning of a colored path, and moves along it according to cards drawn.  The first to reach the end is the winner.  There are 3 kinds of cards
When you finish the move, there are again 3 possibilities
The official rules can be found here.
A picture of the board can be found here. (Higher resolution version)
The character squares are named Plumpy, Mr. Mint, Jolly, Gramma Nut, Princess Lolly, and Queen Frostine.
The shortcuts are called Rainbow Trail and Gumdrop Pass.
The sticky squares are named Gooey Gumdrops, Lost in Lollipop Woods, and Stuck in Molasses Swamp.
Signs on the game board are Gingerbread Plum Trees, Peppermint Forest, Gumdrop Mountains, and Peanut Brittle House.  Also printed on the board are Lord Licorice, Licorice Castle, Gloppy, the Ice Cream Sea, King Kandy, and Candy Castle.  None of these appear in the play of the game.
For more general information, visit the Wikipedipia page on Candyland.

Note that the official rules state there are 64 cards.  Since we have lost some (it's a kids game, after all), I counted what we have left.  It looks like there are 8 copies of each single color card (48 in all), 2 copies of each double card (12 in all) and 6 character cards.  However, this is 66 cards, not 64, and I don't know which 2 are left out (or if there are really 66 cards....).  I'm assuming 66 for now...

The first back-of-the-envelope analysis might go like this.  Ignore the pink squares (the ones with characters), the stuck squares, and the shortcut paths.   Assume the character cards average to 0 (they go back as much as they go forward).  Then 48/66 of the time, we will go forward from 1-6 squares, averaging 3.5 squares.  12/66 of the time, we will go forward 7-12 squares, averaging 9.5 squares.   So the average advance is 4.27 squares, and since the game is 134 squares long, we would expect an typical game to last about 32 moves.  As we will see this is not a bad first order result.

A true analysis would need to average over the 64! (or is it 66! ?) deck orderings.  This introduces a number of complex dependencies - for example, if player 1 gets a "Queen Frostine" in the first 32 cards, then the other players cannot do so.  But if the game exceeds one deck's worth of moves, then the deck is re-shuffled, and all cards are again possible for all players.  Instead I analyze a simpler variant where the deck is re-shuffled after every card is drawn.  This makes the analysis simple - after move N, there is some probability of being on each square, and every player's game is independent.   There are 18 possible card types (6 single color, 6 double color, 6 character), and each is drawn with probability proportional to how many of that type of card there are in the deck.  Thus we can compute the probability distribution at turn N+1.  We continue this until the odds of finishing are sufficiently high.   (There is no upper limit to the possible length of a game since character cards can (and often do) result in backward movement.

Here is a C++ program that computes the probability distribution after each turn, and computes a variety of statistics - the odds the game finishes on that turn, and by that turn, for 1-4  players.  The output is here. Some interesting results are:


1 player
2 players
3 players
4 players
Average game
39.13 cards
51.79 cards
63.51 cards
74.53 cards
Mode game (most common ending turn)
26 turns
16 turns
16 turns
15 turns
Median Game (half are longer)
32 turns =
32 cards
23 turns =
46 cards
19 turns =
57 cards
17 turns =
68 cards
Longish game (10% are longer)
73 cards
88 cards
102 cards
116 cards
Long game (one in a thousand are longer)
189 cards
204 cards
213 cards
232 cards

The official rules are very explicit that you can advance past the end purple square to win.  Many people, however, play that you must land exactly on the last purple square to win.  This change makes the game longer (and much more suspenseful) since it is possible (and common) to get a character card while waiting for the final purple.  The same program above, with the "-e" option (for exact) computes the evolution of this variant.  Here is a summary - note that this simple change makes all games about 30-40% longer.


1 player
2 players
3 players
4 players
Average game
55.96 cards
70.72 cards
75.7 cards
98.08 cards
Mode game (most common ending turn)
28 turns =
28 cards
26 turns =
52 cards
18 turns =
36 cards
17 turns =
68 cards
Median Game (half are longer)
44 cards
60 cards
75 cards
88 cards
Longish game (10% are longer)
109 cards
126 cards
141 cards
156 cards
Long game (one in a thousand are longer)
294 cards
312 cards
327 cards
344 cards

Since this game is longer, the advantage of going first is only 2.11% (in a 2 person game)

It's interesting that the mode drops suddenly between 2 and 3 players.  My intuitive explanation is this - usually during a game, you will suffer at least one serious setback.  Either you will get stuck (costing you 6+ turns on the average) or get sent backwards by a character card (more common in this varient since you need to wait near the end).  So the most common game length includes one setback.  However, if enough people play, the odds are good that someone will get through without a setback, and this becomes the most common game length with enough players.

Monte Carlo Analysis

Using the same transition tables as computed above, we can run Monte Carlo Analysis.  MOnte Carlo can handle 2 effects the analytic calculation does not.  First, a game really ends when the first player finishes, where the above analysis assumes each player plays an equal number of times.  Second there is the dependence introduced by the deck.  But first, I tried simulating the single player, independent draw game.  In this case the analytic and Monte Carlo should give the same results.   Below is a table showing the results of 100 runs of a million games each.  The result is the grand average of the 100 runs.  The plus and minus figures are purely formal errors obtained by comparing the results of the 100 runs.  To investigate the role of the random number generator, run Monte Carlo A  used the Linux function random() with the default configuration to get the random numbers.  Run Monte Carlo B used the function random() with a 256 byte internal state, which in theory should give better results.  Clearly the formal errors understate the true error, and probably the difference between runs A and B are a better estimate of the true errors than the formal errors of each run.   Nonetheless the results look reasonable.


Analytic
Monte Carlo A
Monte Carlo B
Average game
39.16 cards
39.178 ± 0.003
39.161 ± 0.003
Mode game (most common ending turn)
26 cards
25.79  ± 0.05
25.90  ± 0.05
Median Game (half are longer)
31.57 cards
31.659  ± 0.002 31.57  ± 0.002
Longish game (10% are longer)
72.40 cards
72.29  ± 0.008 72.91  ± 0.008
Long game (one in a thousand are longer)
188.8 cards
186.86 ± 0.07 184.80 ± 0.07

Now we run all cards drawn from a common deck, and the game terminates as soon as the first player reaches the final square.  The numbers are drawn from 10 runs of 1M trials each.  Once again the stated errors are formal and probably understate the true errors.



1 player
2 players
3 players
4 players
Average game
Analytic.
39.16 cards
51.79 cards
63.51 cards
74.53 cards
Monte Carlo
39.77 ± 0.004 50.64 ± 0.007 61.10 ± 0.10 70.91 ± 0.14
Mode game (most common ending turn)
Analytic
26 turns
16 turns
16 turns
15 turns
Monte Carlo
26.2 ± 0.2 31.2 ± 0.2 45.7 ± 0.3 57.8 ± 0.6
Median Game (half are longer)
Analytic
32 turns =
32 cards
23 turns =
46 cards
19 turns =
57 cards
17 turns =
68 cards
Monte Carlo
33.84 ± 0.007 45.84 ± 0.009 55.95 ± 0.015 65.61 ± 0.014
Longish game (10% are longer)
Analytic
73 cards
88 cards
102 cards
116 cards
Monte Carlo
71.11 ± 0.01 83.24 ± 0.025 95.93 ± 0.02 108.1 ± 0.03
Long game (one in a thousand are longer)
Analytic
189 cards
204 cards
213 cards
232 cards
Monte Carlo
162.1 ± 0.16 173.7 ± 0.16 186.8 ± 0.17 200.2 ± 0.16

In general these results make sense (or maybe I'm just rationalizing).  Very bad games are less likely, since you cannot get two 'Plumpy' cards in a row.  (The 'bad' cards are closer to the beginning than the 'good' cards are to the end, so the inability to get two bad cards outweighs the drawback of not getting two 'good cards').  For the average game, terminating as soon as the first player finished should help by about 0.5 card for the two player game, 1 card for the 3 player game, and 1.5 cards for the 4 player game.  This accounts for about half the differences - the rest is presumably due to the deck structure discussed above.


Future research possibilities:

Get a new copy of the Candyland game (classic version).  Count the cards of each type.  Assuming the rules are correct when they state 64 cards, two of the cards assumed in the above analysis are missing.  Update the calculations, both approximate and exact, with the correct card counts.

There is a newer, gentler Candyland game on the market.  You must ignore any backwards character moves, and there is a multi-colored square at the end to make it clear that you can go past the last purple.  (Is the game one square longer?).  Analyze this varient.

Figure out why Monte Carlo and analytic approaches give slightly different results in the independent draw, 1 player case, where they should agree.   This might be due to flaws in the random number generator in the Monte Carlo analysis (seems likely from the A vs B discrepancy above), or numerical errors in the analytical analysis, or a bug somewhere in the calculations.

Find out why results are so different from another published analysis.  http://www.namics.nysaes.cornell.edu/news15/cootie.html .  Somewhat surprising, to me, is that the two person is stated to last an average of 33 turns.  This is quite a bit different than the analysis above.  Different deck?  Different rules?  A bug?

Build a web site that allows you to enter how many cards of each type you have left in your set.  Then do the analysis for your particular instance of the game.

Back to LScheffer home page