Skip to content

Instantly share code, notes, and snippets.

@dobrokot
Created May 9, 2012 12:17
Show Gist options
  • Save dobrokot/2644098 to your computer and use it in GitHub Desktop.
Save dobrokot/2644098 to your computer and use it in GitHub Desktop.
knight random walk
# Ivan Dobrokotov, dobrokot 'at' gmail.com
def calc_moves(x, y):
result = []
for dx, dy in [(1, 2), (2, 1), (-1, 2), (-2, 1), (-1, -2), (-2, -1), (1, -2), (2, -1)]:
nx, ny = (x + dx, y+dy)
if 0 <= nx < 8 and 0 <= ny < 8:
result.append((nx, ny))
return result
probability_field = [
[1,0,0,0, 0,0,0,0],
[0,0,0,0, 0,0,0,0],
[0,0,0,0, 0,0,0,0],
[0,0,0,0, 0,0,0,0],
[0,0,0,0, 0,0,0,0],
[0,0,0,0, 0,0,0,0],
[0,0,0,0, 0,0,0,0],
[0,0,0,0, 0,0,0,0],
];
def simulation_step(probability_field):
probability_field_2 = [ ([0] * 8) for i in xrange(8) ]
for x in xrange(8):
for y in xrange(8):
moves = calc_moves(x, y)
for x2, y2 in moves:
probability_field_2[y2][x2] += probability_field[y][x] * (1.0 / len(moves))
return probability_field_2
expectation_of_moves = 0.0
for i_move in xrange(1, 10000):
probability_field = simulation_step(probability_field)
expectation_of_moves += probability_field[0][0] * i_move
probability_field[0][0] = 0 #remove future, where knight was in [0][0] corner.
print expectation_of_moves
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment