What is the Probability that a Knight stays on chessboard after N hops?

Say a $8 \times 8$ chessboard as per picture.

A position is represented here by co-ordinates $(x,y)$.

A move is aslo considered as valid, where the Knight lands outside the chessboard [ For eg. from $(3,2)$ towards $(3,1)$ but ends up outside chess-board. ]

But once outside, it can't come back.

Question:

Knight starts from $(0,0)$. What is the Probability that a Knight stays on chessboard after N hops?

Expected Solution:

I don't want exact result like $\frac{12}{64}$ but need your help on

a. the thought/procedure/methodology to find it with

b. A concluding formulae in terms of permutation/combination,

Well my thought:

1. After $(N-1)$th move, if the Kngiht is between $(x,y)$ where $3 \le x \le 6$ and $3 \le y \le 6$ then next move i.e $n$th move must ensure the knight will be within chessboard. Might be my thought is entirely wrong as it tries to find "must be within chessboard"

2. In any $5 \times 5$ sub part with Knight in middle, it has $8$ possible moves. If initial position is $(0,0)$ out of those $8$ it has choice of $2$ only satisfying "within chessboard" constraint. Next move I am lost! Please help me think .

3. Why cant we treat it like:

  a. The question is valid only if N-1 moves already done with the Knight on board.

b. Now to find Nth move s.t Knight hops out of board - say probability P(out)

c. 1 - P(out) now gives the answer


{ In Case b above we can use some stats like the following:

    Legal moves -> L      Illegal moves -> I
1. for 16 positions enclosed by {3c - 3f - 6c -6f} : 16 x 8 L
2. for each 4 positions {2b,2g,7b,7g} : 4L, 4I  =>  16L , 16I
3. for each 16 positions  {7c-7f ,  2c-2f, 3b-6b, 3g-6g } : 6L,2I => 96L,32I
4. for each 4 corners: 2L,6I => 8L, 24I
5. for each 8 positions {7a,8b , 8g,7h , 2h,1g , 1b,2a} : 3L,5I => 24L,40I
6. for each 16 positions  {3a-6a ,  3h-6h, 8c-8f, 1c-1f } : 4L,4I => 64L,64I


}

• Post your thoughts anyways. We promise we won't be confused or otherwise biased. =] – Adriano Aug 10 '13 at 4:53
• @Adriano You didn't help me in any way though – Arnab Dutta Aug 10 '13 at 7:09
• @user:510889 Awaiting for better easy way – Arnab Dutta Aug 10 '13 at 10:59
• @user:33337 Awaiting for better easy way – Arnab Dutta Aug 10 '13 at 11:00
• @user:39174 Awaiting for better easy way – Arnab Dutta Aug 10 '13 at 11:00

The problem is a Markov chain, and we can attack it with linear algebra!

First, we can simplify the problem by exploiting the symmetry of both the knight's movement and the chessboard. Let's add the following rule:

• After every move, the knight is reflected across the horizontal, vertical, and diagonal axes of symmetry, until it rests in the upper-left triangle of $10$ squares.

In other words, the legal positions are 1a, 1b, 1c, 1d, 2b, 2c, 2d, 3c, 3d, and 4d. You can visualize these positions as occupying one of the $8$ triangles in this diagram:

Now, there are $11$ positions that the knight can occupy after a move: the $10$ positions just named, and $1$ position representing not-on-the-board. For $i,j\in[1,11]$, let $P_{i,j}$ be the probability of transitioning from $i$ to $j$. There are $11\times11=121$ probabilities to calculate, and I suspect that this part must be done by hand.

Now we have an $11\times11$ square matrix $P$. For all $n$, the matrix power $P^n$ is the transition matrix for $n$ moves! So, let's arbitrarily index the initial square as $i=1$ and the off-the-board position as $j=11$. Then the probability of leaving the board after $n$ moves is $(P^n)_{1,11}$, and the probability of staying on the board is: $$1-(P^n)_{1,11}$$ That's as far as I can take you. You could express this formula more explicitly by calculating $P$ and then finding its Jordan normal form. Then you'll have a formula for the powers $P^n$, and you can pull out whatever matrix element you want. If you've seen the explicit formula for the Fibonacci numbers, it's the same principle, but with a larger matrix!

Edit: You've commented that if the knight is in the center of the board, then it can't exit the board in $1$ move. This is a useful obvservation. If we index positions 3c, 3d, and 4d as $i=8,9,10$, then it tells us that $P_{8,11}=P_{9,11}=P_{10,11}=0$. So you see, the matrix $P$ can represent pretty much everything we know about the problem.

Another example of reading information from $P$: You have a rule that if the knight leaves the board, it can't come back. This translates to the statement that $P_{11,11}=1$, and for all $j<11$, $P_{11,j}=0$. Between this paragraph and the previous paragraph, we already know $14$ matrix elements. There are just $107$ more to calculate...

Edit 2: Another example. You commented that from the initial position, only $2$ out of $8$ possible moves stay on the board. That tells us that $P_{1,11}=3/4$. The knight can stay on the board by moving to 2c or 3b. In my scheme, 3b gets reflected back to 2c. So if we index 2c as $j=6$, then $P_{1,6}=1/4$. For all other $j$ besides $6$ and $11$, we have $P_{1,j}=0$. That's another $11$ matrix elements calculated; $96$ to go...

• I didn't get few things- 1. How can those 10 be legal positions if I start from (0,0) 2. I also dont know Jordan normal form + I think there is no such (x,y) which can have "1 position representing not-on-the-board" move Can you please explain in more layman terms? – Arnab Dutta Aug 10 '13 at 5:33
• @ArnabDutta 1. Sorry, I had to use the "1a, 1b, ..." notation to avoid confusion with the other numbers I was using. In my notation, the initial square is 1a. 2. Have you heard of diagonalizing a matrix? The Jordan form is a lot like diagonalization, but it works for a greater variety of matrices. Our matrix $P$ might actually be diagonalizable; I'm not sure. 3. The not-on-the-board position can be labeled however we like; it doesn't have to be assigned a row and column. That's because we don't care exactly where the knight leaves the board. – Chris Culter Aug 10 '13 at 5:39
• "11 positions that the knight can occupy after a move" - how is that possible? only 8 is possible max – Arnab Dutta Aug 10 '13 at 5:40
• @ArnabDutta Explicitly, the positions are 1a, 1b, 1c, 1d, 2b, 2c, 2d, 3c, 3d, 4d, and off-the-board. Does that make sense? If I didn't use symmetry to reduce the number of positions, then there would be $64+1=65$ positions, and we would have a $65\times65$ matrix with $4225$ entries. That would be harder to work with. – Chris Culter Aug 10 '13 at 5:41
• 1.If your initial start is 1a then Clearly 3b is a legal move. But your 10 positions don't have that - why? 2.What is your start position ? What do you meant by- "positions are 1a, 1b, 1c, 1d, 2b, 2c, 2d, 3c, 3d, 4d" ? Positions respect to what? How did you ended up to those 10 points ? – Arnab Dutta Aug 10 '13 at 5:59

As mentioned by Chris Culter, the computation is somewhat tedious. Following Chris and labeling the 64 fields so as to make the symmetries explicit, e.g:

$$0 \ \ 7 \ \ 6 \ \ 3 \ \ 3 \ \ 6 \ \ 7 \ \ 0 \\ 7 \ \ 9 \ \ 1 \ \ 5 \ \ 5 \ \ 1 \ \ 9 \ \ 7 \\ 6 \ \ 1 \ \ 8 \ \ 4 \ \ 4 \ \ 8 \ \ 1 \ \ 6 \\ 3 \ \ 5 \ \ 4 \ \ 2 \ \ 2 \ \ 4 \ \ 5 \ \ 3 \\ 3 \ \ 5 \ \ 4 \ \ 2 \ \ 2 \ \ 4 \ \ 5 \ \ 3 \\ 6 \ \ 1 \ \ 8 \ \ 4 \ \ 4 \ \ 8 \ \ 1 \ \ 6 \\ 7 \ \ 9 \ \ 1 \ \ 5 \ \ 5 \ \ 1 \ \ 9 \ \ 7 \\ 0 \ \ 7 \ \ 6 \ \ 3 \ \ 3 \ \ 6 \ \ 7 \ \ 0 \\$$ it follows that the probabilities for the knight at time step $n+1$ to be at each of the fields labeled with the numbers $0,1,2,..,9$ can be expressed via: $$\begin{pmatrix}p_0^{(n+1)}\\p_1^{(n+1)}\\p_2^{(n+1)}\\p_3^{(n+1)}\\p_4^{(n+1)}\\ p_5^{(n+1)}\\p_6^{(n+1)}\\p_7^{(n+1)}\\p_8^{(n+1)}\\p_9^{(n+1)}\end{pmatrix} = \frac{1}{8} \begin{pmatrix}0&1&0&0& 0 & 0 & 0 & 0 & 0 & 0\\ 1&0&1&1&1&1&1&0&0&0\\ 0&1&0&0&1&1&0&0&2&0\\ 0&1&0&0&1&0&0&0&1&1\\ 0&1&1&1&2&1&1&0&0&1\\ 0&1&1&0&1&0&1&1&1&0\\ 0&1&0&0&1&1&0&1&0&0\\ 0&0&0&0&0&1&1&0&1&0\\ 0&0&2&1&0&1&0&1&0&0\\ 0&0&0&1&1&0&0&0&0&0\end{pmatrix} \begin{pmatrix}p_0^{(n)}\\p_1^{(n)}\\p_2^{(n)}\\p_3^{(n)}\\p_4^{(n)}\\ p_5^{(n)}\\p_6^{(n)}\\p_7^{(n)}\\p_8^{(n)}\\p_9^{(n)}\end{pmatrix}$$

with $p_0^{(0)}=1/4$ and $p_i^{(0)}=0$ for all $i>0$.

The requested probability for the knight to be on the board after $n$ moves equals the sum $$4p_0^{(n)}+8p_1^{(n)}+4p_2^{(n)}+8p_3^{(n)} +8p_4^{(n)}+8p_5^{(n)}+8p_6^{(n)}+8p_7^{(n)}+4p_8^{(n)}+4p_9^{(n)}$$ For large $n$ this probability drops with each move by a factor equal to the largest eigenvalue of the above matrix.

• Can you please elaborate your statement- "the knight at time step n+1 to be at each of the fields labeled with the numbers 0,1,2,.." Also please explain $p_0^{(0)}=1/4$ I couldn't get that! – Arnab Dutta Aug 12 '13 at 16:55

From 0,0 allready 6 of the possible 8 moves end off board
Of the two remaining moves 2 out of the 8 end off board
That should give you allready a good indication how difficult it will be to keep the knight on the board.

Whatever method you use to get the exact solution (and I suspect it will involve getting the eigenvalues of an 11x11 matrix), consider using a spreadsheet to calculate the probabilities for small n, say n ≤ 10,000, and when you have done that, it lets you verify that your exact solution is actually correct.

If you follow the numbering in Johannes' answer, if after n moves you are at a position labelled 9 (for example), then after n+1 moves you will be at a position labelled 3 with probability 1/4, and at a position labelled 4 with probability 1/4 (and outside the board with probability 1/2). Do this for all positions, and you know how to calculate the probability for being at X after n+1 moves if you were at Y after n moves, for all X, Y. After 0 moves, you are at a position labelled 1 with probability 1.

To calculate the probability after N hops, we look at the POSITION(s) of the knight at N-1 hop. I think this was what the others were referring to as Markov chain.

For example, given a NxN board where N=3 and (let the number of hops to take be K) K = 2

When K = 1

we look at where the knight was it was at K-1, which is its initial position of (1,1).

Out of its 8 positions, the knight can go to 2 spots on the board (3, 2) and (2, 3).

This means that it will have 2/8 probability of staying on the board after 1 hop.

When K = 2

we look at where the knight was at K-1 (which is K=1).

We see that it could be at either (3, 2) or (2, 3) but not both.

For each spot, it has 2 spots it can take to stay on the board.

We calculate the probability 2/8 when the knight started at (3,2) and 2/8 when the knight started at (2, 3).

The probability that a knight stays on the board after K=2 hops is 2/8 * 2/8. (On that note, if they aren't of the same probability, say (3,2) has a probability of 2/8 and (2,3) has a probability of 3/8, the probability would be 2/8 * 3/8)

We multiply probabilities when we want events to occur simultaneously, or consecutively.

Hence, the result probability that a knight stays on the board for N=3, K=2 is 2/8 * 2/8.

I interpreted this from the following link. I too, wasn't sure how the probability was derived and this was the best resource that explained it in a simple way :) https://zxi.mytechroad.com/blog/dynamic-programming/688-knight-probability-in-chessboard/