Created
July 10, 2023 07:13
-
-
Save SimonLammer/5f7c5fd4f9e60bba9fd13db0930ff83b to your computer and use it in GitHub Desktop.
Probability to win Snakes&Ladders after n rounds
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
snakes = { | |
17: 7, | |
54: 34, | |
62: 19, | |
64: 60, | |
87: 24, | |
93: 73, | |
95: 75, | |
99: 78, | |
} | |
ladders = { | |
4: 14, | |
9: 31, | |
20: 38, | |
25: 84, | |
40: 59, | |
51: 67, | |
63: 81, | |
71: 91, | |
} | |
if False: # ladders are snakes too | |
snakes |= {v:k for k,v in ladders.items()} | |
ladders = {} | |
print(f"{snakes=}") | |
print(f"{ladders=}") | |
board_size = 100 | |
die_min = 1 | |
die_max = 6 | |
m = matrix(QQ, board_size, board_size) | |
die_probability = 1/(die_max-die_min+1) | |
for i in range(board_size-1): | |
for j in range(die_min, die_max+1): | |
destination = i+j | |
if destination >= board_size: # overshoot back into the board | |
destination = board_size-(destination-board_size)-1 | |
m[i,destination] += die_probability | |
m[board_size-1,board_size-1] = 1 # Stay at finish once reached | |
for transportations in [snakes, ladders]: | |
for start, destination in transportations.items(): | |
for i in range(board_size): | |
m[i,destination-1] += m[i,start-1] | |
m[i,start-1] = 0 | |
start = vector(QQ, board_size) | |
start[0] = 1 | |
for i in (1, 2, 3, 5, 8, 13, 21, 30, 34, 55, 89, 100, 144, 233, 377, 610, 987, 1597, 2584): | |
state = (start * m ** i) | |
#print(f"{i:4d}: {state.numerical_approx(digits=2)}") | |
print(f"{i:4d}: {state[board_size-1].numerical_approx(digits=2)}") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Hardcore mode (ladders are snakes too):
snakes={17: 7, 54: 34, 62: 19, 64: 60, 87: 24, 93: 73, 95: 75, 99: 78, 14: 4, 31: 9, 38: 20, 84: 25, 59: 40, 67: 51, 81: 63, 91: 71}
ladders={}
1: 0.00
2: 0.00
3: 0.00
5: 0.00
8: 0.00
13: 0.00
21: 8.9e-6
30: 0.0046
34: 0.0096
55: 0.045
89: 0.10
100: 0.12
144: 0.19
233: 0.32
377: 0.48
610: 0.66
987: 0.83
1597: 0.95
2584: 0.99