Programming

Saturday, January 02, 2016

An Analysis of Snakes and Ladders

The childhood game of “Snakes and Ladders” involves players throwing a die and advancing the given number of places. If you land on a snake, you go down it, and if you land on ladder you go up. The winner is the first player to reach the finish square, but you need to get the exact number on the die to do that. Figure 1 shows my board, although many variations exist.

Figure 1: A board of Snakes and Ladders. (Image may be subject to copyright.) 

Although there are no decisions involved, there are still questions we can ask:

  • What’s the minimum number of throws to reach the finish (D)?
  • How many throws does it take on average to reach the finish (E)?
  • Who is ahead at any given time?
  • What's the probability of winning from given positions of the players (P)?
  • How big is the advantage of going first?

The minimum number of throws required to finish can thought of as a “minimum distance” D to the finish square (square 100), from any other square s on the board. This is expressed using the equations

     D(s) = 1 + min_i(D(destination(s,i))
     D(100) = 0

where destination(s, i) is the final square you land on (after moving up ladders or down snakes) if you roll an i at square s. The results are shown in the Appendix, and in Figure 2.

Figure 2: The minimum (D) and expected (E) number of throws remaining for each square.

For each square, there is an “expected number of throws” E required to reach the finish. If we calculate this number for each square on the board, we can see who's ahead, by seeing who is on the square with the lowest E.

E can be computed using:

     E(s) = 1 + sum_i E(destination(s,i))/6
     E(100) = 0

This results in a set of 101 linear equations which can be solved exactly (using a computer). From the starting position, the expected number of throws E is about 35.54 (for the board in Figure 1). Figure 2 shows the values of D and E for each square.

Although the distance to finish E gives an idea of who is winning, it doesn't tell you the actual probability P of winning. In the two-player case (where there are just 10000 possible game states), we can calculate the exact probability P of winning for each state by:

     P_wins(a, b) = sum_i (1-P_wins(b, destination(a, i)))/6
     P_wins(100, b) = 1

This basically says that your probability of winning is the weighted probability that your opponent doesn't win for all possible values of the dice.

This calculation yields a set of 10100 linear equations which can be solved exactly by a computer. This also gives the advantage of moving first, since P(0,0) ~= 0.509, so there is about a 0.9% advantage to going first.

We could try to extend this approach to more than two players, though to solve it exactly we would need a much larger state (100^n for n players), which doesn't scale.

The exact solution for P is not very wieldy (there are 10000 values), so we can attempt to approximate it. After a bit of experimenting, it turns out that the difference in expected throws remaining (delta E) gives a simple way to approximate the probability P of winning.

The following graph shows a plot of delta E and their probability P of winning a 2-player game. 

Figure 3: How E affects your chances of winning.

This shows a linear relationship, improving your chances of winning by about 2% for each unit of distance E between the two players. The graph actually looks like an S shape, so a gradient of 0.019 is used. The graph is asymmetrical, with a bias of 0.94% in favour of the player who acts first. The outliers below the graph are in the case where one of the players is lurking on square 99.

For example, if you are on square 11, and your opponent is on square 69, then the difference in E is 34.7 - 18.7 = 16. This equates to a 16*1.9 ~= a 30% advantage, so the probability of you winning is about 50-30 = 20%, and the probability of your opponent winning is about 50+30 = 80%. This could also be expressed as odds of 4:1 against.

Since there is a linear relationship between E and P, we can estimate P' = 1 - 0.019E. This gives you a simple way to assess your winning probability. This is shown in Figure 4.

Figure 4: The winning probability (P’) for each square, as well as “completion” as a proportion of the expected number of throws. Both of these quantities are linear transformations of E (see Figure 2).

In our previous example (where I am on square 11, and my opponent is on square 67), P'(11) = 33.9%, and P'(67) = 63.3%, so the difference in P' = 63.3-33.9 ~= 30%.  My odds of winning are about 50-30 = 20%. The exact odds of me winning are actually 24.1% if I go next, or 22.9% if my opponent goes next.

The completion % in Figure 4 shows that you are about half way when you are on square 75 or 89, and actually negative on squares 2 and 5 where you just missed some ladders.

Conclusion

This analysis has given the exact “value” of each square in terms of number of throws remaining, which gives a more accurate assessment of which player is in the lead, and more importantly, by how much. This method can be applied to any configuration of snakes and ladders.

For example with this board, you are never more than 7 throws away from a win, the advantage to the player acting next is 0.9%, and that the expected number of throws to finish is 35.54.

This also gives criteria for designing and evaluating new boards. There needs to be a sensible number of expected throws so that games are neither too long or too short, and enough snakes and ladders so that players can catch up and to add unpredictability and interest.

Obviously such an analysis is somewhat moot because there is no decision-making involved, and Snakes and Ladders not used as a basis for gambling.

Appendix

Calculated values (for the board in Figure 1). Square 0 is the starting position. C++ code use to generate the data in this article is here.

Square D E P'Completion
0
7
35.54
32.3
0
1
6
31.2
40.58
12.22
2
7
36.03
31.38
-1.367
3
6
35.45
32.47
0.2489
4
6
33.61
35.98
5.433
5
6
35.57
32.25
-0.08221
6
6
35.39
32.59
0.4261
7
6
35.18
32.98
1.01
8
6
34.96
33.41
1.642
9
5
32.01
39.03
9.946
10
7
35.17
33.01
1.045
11
6
34.72
33.87
2.319
12
6
34.31
34.65
3.476
13
6
33.94
35.36
4.512
14
6
33.61
35.98
5.433
15
6
33.06
37.03
6.982
16
6
35.39
32.59
0.4261
17
5
32
39.05
9.967
18
5
31.84
39.35
10.41
19
5
31.73
39.57
10.73
20
5
31.65
39.72
10.96
21
5
29.76
43.32
16.28
22
4
30.34
42.21
14.64
23
4
30.69
41.55
13.66
24
4
30.89
41.17
13.1
25
4
31.05
40.86
12.65
26
4
31.17
40.63
12.31
27
4
31.25
40.48
12.08
28
3
21
60
40.92
29
6
32.77
37.58
7.805
30
5
32.1
38.87
9.697
31
5
32.01
39.03
9.946
32
5
31.89
39.25
10.27
33
5
31.73
39.56
10.73
34
5
31.52
39.96
11.31
35
5
31.36
40.26
11.76
36
4
28.06
46.55
21.05
37
6
31.48
40.04
11.44
38
6
31.2
40.58
12.22
39
5
30.75
41.43
13.48
40
5
30.28
42.32
14.79
41
5
30.41
42.08
14.44
42
5
29.76
43.32
16.28
43
5
30.47
41.97
14.28
44
5
29.52
43.77
16.94
45
4
28.06
46.55
21.05
46
4
27.49
47.64
22.66
47
4
31.17
40.63
12.31
48
4
25.84
50.79
27.31
49
6
34.72
33.87
2.319
50
4
23.87
54.54
32.85
51
3
19.28
63.27
45.74
52
5
24.05
54.19
32.34
53
5
23.72
54.82
33.27
54
5
23.39
55.46
34.2
55
5
23.06
56.08
35.13
56
5
23.72
54.82
33.27
57
4
22.27
57.59
37.35
58
4
22.14
57.83
37.7
59
4
21.74
58.6
38.84
60
4
21.39
59.26
39.82
61
4
21.09
59.83
40.67
62
3
20.77
60.43
41.55
63
3
20.48
61
42.39
64
4
21.39
59.26
39.82
65
3
19.31
63.22
45.66
66
3
19.3
63.24
45.71
67
3
19.28
63.27
45.74
68
2
18.88
64.04
46.88
69
2
18.68
64.41
47.43
70
2
18.62
64.53
47.61
71
2
15.11
71.23
57.5
72
2
19.21
63.42
45.96
73
2
19.21
63.41
45.95
74
1
16.47
68.64
53.68
75
1
17.5
66.67
50.77
76
1
18.24
65.26
48.69
77
1
18.75
64.28
47.24
78
1
19.07
63.67
46.33
79
1
19.23
63.37
45.9
80
0
0
100
100
81
4
23.68
54.89
33.37
82
3
22.69
56.79
36.17
83
3
21.85
58.38
38.53
84
3
21
60
40.92
85
3
20.16
61.61
43.29
86
3
19.52
62.83
45.09
87
4
30.89
41.17
13.1
88
2
16.71
68.17
52.99
89
2
16.82
67.96
52.67
90
2
15.9
69.72
55.27
91
2
15.11
71.23
57.5
92
2
15.67
70.15
55.9
93
2
19.21
63.41
45.95
94
1
11.55
78
67.51
95
1
17.5
66.67
50.77
96
1
10.36
80.27
70.86
97
1
10.36
80.27
70.86
98
1
19.07
63.67
46.33
99
1
6
88.57
83.12
100
0
0
100
100

0 Comments:

Post a Comment

<< Home