import numpy as np | |
from numpy.linalg import matrix_power | |
from matplotlib import pyplot as plt | |
import seaborn as sns | |
SIZE = 100 | |
M = np.zeros((SIZE, SIZE)) | |
# encoding rolls of die | |
for y in xrange(SIZE): | |
if y <= (SIZE - 6 - 1): | |
M[y, np.arange(y+1, y+7)] = 1 | |
elif y == SIZE - 1: # end, absorbing state | |
M[y, SIZE-1] = 6 | |
else: | |
# this should be checked more carefully. This is the "bounce-off" behaviour. | |
M[y, (y+1):] = 1 | |
M[y, (SIZE-(6 - (SIZE-y-2))):SIZE-1] += 1 | |
def slip_effect(M, start_node, end_node): | |
""" | |
Ex: if am in position 1, and then roll a 2, I should temporarily be on position 3 before | |
slipping to position 13. Thus everywhere that _should_ have landed me on position 3 | |
should instead be moved to position 13, and all position 3s should be erased. | |
""" | |
ix, = np.where(M[:, start_node]) | |
M[ix, end_node] += M[ix, start_node] | |
M[:, start_node] = 0 | |
return M | |
# encoding of snakes | |
M = slip_effect(M, 16, 6) | |
M = slip_effect(M, 86, 23) | |
M = slip_effect(M, 98, 77) | |
M = slip_effect(M, 63, 59) | |
M = slip_effect(M, 61, 18) | |
M = slip_effect(M, 94, 74) | |
M = slip_effect(M, 92, 72) | |
M = slip_effect(M, 53, 33) | |
# encoding of ladders | |
M = slip_effect(M, 3, 13) | |
M = slip_effect(M, 8, 30) | |
M = slip_effect(M, 19, 37) | |
M = slip_effect(M, 27, 83) | |
M = slip_effect(M, 39, 59) | |
M = slip_effect(M, 50, 66) | |
M = slip_effect(M, 62, 80) | |
M = slip_effect(M, 70, 90) | |
M = M/6.0 | |
# check for first "win" in 7 moves - note my initial state is technically move 2, hence the off-by-one. | |
for n in xrange(1, 6): | |
assert matrix_power(M, n)[0, SIZE-1] == 0 | |
M_6 = matrix_power(M, 6) | |
assert M_6[0, SIZE-1] > 0 | |
# what is the probability of this event? | |
M[0,SIZE-1] # 0.0135% | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment