Mathematical Analysis of Candyland

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

A card with a single colored square - move to the next square of that color
A card with two squares of the same color- move to the second square of that color
A character card - move to the square marked by that character

When you finish the move, there are again 3 possibilities

You land on a normal square, and await your next turn
You land on one of two 'shortcut' paths, and move to the end of the shortcut.
You land on a sticky square, and must remain there until you draw a card of the same color as the square

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:

You can win in just 4 turns - Queen Frostine, double purple, double purple, purple (and similar combinations). This only happens about 4 times in 100,000 games, though.
Most games with 1, 2, or 3 players will finish without reshuffling the deck.
Once in a thousand times, it will take you at least 204 turns to finish a 2 person game.
There is a 3.13% advantage to going first in a 2 person game.
It is possible to compute the expected game length of a 1 person game exactly. (The initial state and all transition probabilities are rational, and Dave Rusin's analysis shows the result is too. The right answer is: 85100195894905694643910808669611193138178322815421121785149337089628722771551370036291180702134592105978444355274796416728813090502234082713012105143335237058223704797492635000525593595263 / 2173080537717717179828093958428497620958740477680447849390518719676720484473817661353157677132194901659005721111507530070237798581304539064518217727998877873988212783989568261314165080690

	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
Average game	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
Mode game (most common ending turn)	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
Median Game (half are longer)	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
Longish game (10% are longer)	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
Long game (one in a thousand are longer)	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