Random knight

A knight walks randomly on the standard chessboard. What is the proportion of time that it will spend at e4?

The answer (1/42) is not hard to get, but I’ll take the computational approach first (testing Scilab 5.5.0 beta 1, by the way). Begin by placing the knight at b1 and letting it make five random moves. This is the distribution of its position after five moves:

1 knight 5 moves
1 knight 5 moves

Unsurprisingly, half of the board is black; actually more than half because the knight can’t get to h8 in five moves. the other half isn’t — you can even get to h8 in five moves (want to find all possible ways to do this?).

After ten moves, the colors become more uniform.

1 knight 10 moves
1 knight 10 moves

After 200 (or any large even number) of moves, the distribution is little changed. But you may notice that it is centrally symmetric, while the previous one isn’t quite.

1 knight 200 moves
1 knight 200 moves

Let’s repeat the process beginning with two knights at b1 and g1. After five moves of each:

2 knights 5 moves
2 knights 5 moves

After ten moves:

2 knights 10 moves
2 knights 10 moves

After a large number of moves (does not matter, even or odd), the variety of colors is greatly reduced:

steady state distribution
steady state distribution

Indeed, this is the distribution which also describes the proportion of time that the knight (wherever it started) will spend at a given square Q.

Precisely, the proportion of time spent at Q is P(Q)=N(Q)/336 where N(Q) is the number of legal moves from Q. For the sixteen central squares P(Q) = 8/336 = 1/42, while for the corners we get 2/336 = 1/168.

Here is a quick argument to support the above. Let Q1 and Q2 be two squares such that the move from Q1 to Q2 is legal. The proportion of time that the knight makes this move is P(Q1)/N(Q1). Similarly, the time proportion of Q2-Q1 move is P(Q2)/N(Q2). Since the process is symmetric in time (we have a reversible Markov chain), P(Q1)/N(Q1)=P(Q2)/N(Q2). In other words, the ratio P/Q is the same for any two squares that are joined by a legal move; it follows that P/Q is the same for all cells. Finding the coefficient of proportionality is a matter of counting, since the sum of P(Q) over all Q is 1.

The Scilab code I wrote for this post is largely not knight-specific. The function update receives the initial distribution of a chess piece and the set of its legal moves. It computes the distribution after one random move.

function newState=update(state,moves)
    [maxK,n]=size(moves)
    [n,n]=size(state)
    newState=zeros(state)
    for i=1:n 
        for j=1:n
            neighborCount=0
            contribution=zeros(state)
            for k=1:maxK
                pos=[i,j]+moves(k,:)
                if (min(pos)>=1)&(max(pos)<=n) then
                   neighborCount=neighborCount+1
                   contribution(pos(1),pos(2))=state(i,j)
                end
            end
            newState=newState+contribution/neighborCount
        end
    end
endfunction

This set is given in the function knight which calls update iteratively.

function state=knight(state,iter)
    moves=[2 1;1 2;-2 1;1 -2;2 -1;-1 2;-2 -1;-1 -2]
    for i=1:iter
        state=update(state,moves)
    end
endfunction

For example, this is how I plotted the distribution after 10 random moves starting at b1:

initial = zeros(8,8)
initial(8,2)=1
state = knight(initial,10)
isoview(0,0,9,9)
Matplot(state*500)
f = gcf()
f.color_map = hotcolormap(32)

NB: getting the correct color representation of matrices from Matplot requires an up-to-date version of Scilab; in version 5.4.0 Matplot smoothens colors, producing intriguing but less informative images.

stars?
knight sky?

4 thoughts on “Random knight”

  1. h8 isn’t 100% black in your first picture, and rightfully so; it is possible to get from b1 to h8 in 5 moves. One way: b1-c3-d5-e7-g6-h8.

    1. Thanks for the correction; I’m going to blame this goof on the low-brightness setting of my screen.

    1. In this article, colors indicate the probability of landing at a given square after n steps. Black means probability 0, and the “hotter” the square appears, the greater the probability is. (I used hotcolormap in Scilab).

      The regulation chessboard is itself colored black and white: for example, b1 is white there. This is not to be confused with the colors indicating probability. The two kinds of colors are related. With every move, the knight changes the (chess) color of the square: it can go from white to black, but not from white to white. So, after an even number of moves (10 or 200) starting from b1, it will be in one of the squares colored white on the standard chessboard. The other squares, having probability 0, will be colored black — consistent with chess rules.

      By adding another knight beginning at g1 (which is black in chess), I balanced out the coverage of black and white squares, which led to the relatively uniform steady state distribution.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s