knight random walk

knight_random_walk.py

# 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