# candyland

Simulation of Candyland.

```bash
cmake -S . -B build
cmake --build build
build/candyland
```

```text
games played:      1000000
empty BoW:         3576
longest game:      81 draws
shortest game:     6 draws
0: 0
1: 0
2: 0
3: 0
4: 0
5: 0
6: 1
7: 3
8: 7
9: 3574
10: 3614
11: 3613
12: 3643
13: 10184
14: 10299
15: 10262
16: 10404
17: 17088
18: 16974
19: 16956
20: 16844
21: 23717
22: 23445
23: 23407
24: 23483
25: 30464
26: 30845
27: 31288
28: 31744
29: 39905
30: 40433
31: 40487
32: 40780
33: 49513
34: 47433
35: 44947
36: 42120
37: 46855
38: 41381
39: 36060
40: 30942
41: 30580
42: 25088
43: 20294
44: 16686
45: 14923
46: 11439
47: 8954
48: 6960
49: 5660
50: 4349
51: 3151
52: 2490
53: 1718
54: 1417
55: 931
56: 712
57: 494
58: 368
59: 247
60: 229
61: 140
62: 104
63: 84
64: 68
65: 43
66: 44
67: 29
68: 18
69: 17
70: 10
71: 11
72: 10
73: 6
74: 3
75: 1
76: 3
77: 0
78: 1
79: 1
80: 1
81: 1
```

## Discussion

Our version of Candyland seems to have a key difference [rules I can find posted online](https://www.wikihow.com/Play-Candy-Land):

* Two players cannot occupy the same space. If you land on a space occupied by another player, move your piece to the next space of the same color.

This rule introduces a problem: what if there is no available space of the same color?
I decided that under such circumstances, the player does not move at all.

Furthermore, it appears there's some variety in board layout.
Here's ours, featuring two shortcuts and a split path:

![](board.jpg)

The simulation code has two interesting points of complexity:

### Handling the Split Path

The 83 board spaces are laid out in a 1D array.
It's appealing to just search forward from the player position to find the next space of the appropriate color, however, the forked path means this will occasionally produce an invalid move.
If the left branch (blue/green/purple) is stored before the right branch (yellow/orange/red), and a player on the left branch draws a red card, this would cause them to jump over to a space on the right branch.

To avoid this, each space also stores 1 or 2 following spaces: the forking space has two, and all other spaces have one.
Before a piece can be moved, this simple graph of spaces needs to be traversed to actually determine the pool of reachable spaces.

### Disallowing Shared Occupancy

The second source of complexity is disallowing two pieces from sharing a space on the board.

The basic logic is wrapped up in a function like this:
* Inputs: starting location, target color
* Output: ending location
* Examine all reachable spaces starting from  the start location
  * If the space is the target color, return its index unless it's already occupied.

In the case of landing on a shortcut, it takes sadvantage of the fact that both shortcuts on this board jump the player to the next space of the same color.
We just restart this logic from the shortcut start location with the same target color.

In the case of a candy card, we scan the whole board to look up the target space (since it might be behind the starting location).
Then, apply the move logic starting from immediately before the target space, targeting the next pink space.
This handles the case where the target space is occupied by a player, and needs to be skipped to land on the next pink space.

## Results

I ran 1,000,000 simulations

| Player Won | % Observed (raw) |
|-|-|
| 1 | 27.5% (274882) |
| 2 | 25.7% (257248) |
| 3 | 24.1% (240726) |
| 4 | 22.7% (227144) | 

Going first (i.e., being the youngest player) confers a 1.8pp advantage relative to the closest competition.
If you go last, you can expect to win only 22.7% of games.

Other statistics over 1M games:

| Stat | Value |
|-|-|
| Cards drawn | 31,659,948 |
| Backwards Moves | 940,653 (2.97% of draws) |
| Shortcuts Taken | 1,277,005 (4.03% of draws) | 
| Didn't move | 18 | 
| Empty Bag of Wonders | 3,576 |
| Landed on Another Player | 2,966,229 |

The longest observed game was 81 draws, and the shortest was 6.

![](histo.png)

The six turn game goes like this, and requires player 1 to do certain moves first.

1. Player 1 goes to ice cream
2. Player 2 goes to mint
3. ...
4. ...
5. Player 1 draws double red: first one takes him across the shortcut, second takes him to the red ahead of player 2.
6. Player 2 draws double red: lands on player 1 to skip to next red, second red takes him to the end.
