During this seminar we will immulate the random walk on knight's network, which you should build in the first place.
Consider $n \times n$ chessboard with a single knight on it. <br>
Construct a network with all knight's possible moves. In this network each node represents chessboard locations and an edge between two locations appears if knight is admitted to move from one to another.
Implement simulation of knight random walk on chessboard
import numpy as np
import matplotlib.pyplot as plt
from numpy.random import choice, rand
import networkx as nx
%matplotlib inline
def GenKnightNetwork(boardSize):
G = nx.Graph()
pos = {}
for row in xrange(boardSize):
for col in xrange(boardSize):
nodeId = row + col*boardSize
pos[nodeId] = np.array([1.0*row/boardSize, 1.0*col/boardSize])
newPos = GetLegalMoves(row, col, boardSize)
for e in newPos:
nid = e[0] + e[1]*boardSize
G.add_edge(nodeId, nid)
return G, pos
def GetLegalMoves(x,y,boardSize):
newMoves = []
moveOffsets = [(-1,-2),(-1,2),(-2,-1),(-2,1),
( 1,-2),( 1,2),( 2,-1),( 2,1)]
for i in moveOffsets:
newX = x + i[0]
newY = y + i[1]
if isLegalCoord(newX,boardSize) and \
isLegalCoord(newY,boardSize):
newMoves.append((newX,newY))
return newMoves
def isLegalCoord(x,boardSize):
if x >= 0 and x < boardSize:
return True
else:
return False
boardSize = 8
(G,pos) = GenKnightNetwork(boardSize)
nx.draw(G, pos)
def RandomWalk(G, xi, n, till_first_return = False):
nodeSeq = []
nodeSeq.append(xi)
if till_first_return:
xInit = xi
while True:
neig = np.array(G.neighbors(xi))
xi = choice(G.neighbors(xi),1)[0]
nodeSeq.append(xi)
if xi == xInit:
return nodeSeq
else:
for i in xrange(n):
neig = np.array(G.neighbors(xi))
xi = choice(G.neighbors(xi),1)[0]
nodeSeq.append(xi)
return nodeSeq
nodeSeq = RandomWalk(G, 0, 100)
edgeSeq = [(nodeSeq[i-1], nodeSeq[i]) for i in xrange(1,len(nodeSeq))]
nodeSeq = RandomWalk(G, 0, 100, True)
edgeSeq = [(nodeSeq[i-1], nodeSeq[i]) for i in xrange(1,len(nodeSeq))]
nx.draw(G, pos)
nx.draw(G, pos, edgelist = edgeSeq, edge_color='blue', width=2)
nodeSeq = []
for xi in xrange(G.number_of_nodes()):
nodeSeq.append(RandomWalk(G, xi, 1000))
h = plt.hist(nodeSeq, bins = G.number_of_nodes())
plt.bar(range(0,64), G.degree().values())
<Container object of 64 artists>
returnTime = []
for i in xrange(1000):
returnTime.append(len(RandomWalk(G, 27, 0, True)))
plt.boxplot(returnTime)
{'boxes': [<matplotlib.lines.Line2D at 0x7f58fe270650>], 'caps': [<matplotlib.lines.Line2D at 0x7f58fe265990>, <matplotlib.lines.Line2D at 0x7f58fe265fd0>], 'fliers': [<matplotlib.lines.Line2D at 0x7f58fe279310>, <matplotlib.lines.Line2D at 0x7f58fe279910>], 'medians': [<matplotlib.lines.Line2D at 0x7f58fe270c90>], 'whiskers': [<matplotlib.lines.Line2D at 0x7f58fe265050>, <matplotlib.lines.Line2D at 0x7f58fe2652d0>]}