# Knights on a chess board

## The power and beauty of Markov Chains.

By Vamshi Jandhyala

November 19, 2020

## Problem

A white knight and a black knight are situated on diagonally opposite corners of a $3 \times 3$ square. In turn, starting with White, they move randomly until (inevitably) Black captures White. What is the expected number of Black moves to achieve capture?

## Solution

### Key Observations

- The complete
**state**of the game is determined by the position of the two knights on the board. - The next state of the game only depends on the current state.
- Multiple configurations(rotations, reflections) of the board can be collapsed into a single state.

This is essentially a **Markov Chain** problem.

### Board States

The diagram below illustrates all possible board states apart from the **absorbing** state

*State 1* is the initial state.

### State Transition Matrix

The state transition diagram for the game markov chain is shown below

*State 5* (where the black knight captures the white knight) is the absorbing state of the markov chain.

The transition matrix $\mathbf{Q}$ is given by

$$
\mathbf{Q} =
\begin{bmatrix}
0 & 0.5 & 0.5 & 0\

0.5 & 0 & 0 & 0.5 \

0.25 & 0 & 0 &0.5 \

0 & 0.25 & 0.5 &0
\end{bmatrix}
$$

### Fundamental matrix and expectation

For a Markov chain $\mathbf{P}$, the matrix $\mathbf{N} = (\mathbf{I} − \mathbf{Q})^{−1}$ is called the *fundamental matrix* for $\mathbf{P}$.

Let $t_i$ be the expected number of steps before the chain is absorbed, given that the chain starts in state $s_i$, and let $\mathbf{t}$ be the column vector whose $i^{th}$ entry is $t_i$. Then $\mathbf{t} = \mathbf{Nc}$, where $\mathbf{c}$ is a column vector all of whose entries are $1$.

We have

$$
\begin{align*}
\mathbf{Nc} &= (\mathbf{I - Q})^{-1}\mathbf{c} \

&= \begin{bmatrix}
1 & -0.5 & -0.5 & 0\

-0.5 & 1 & 0 & -0.5 \

-0.25 & 0 & 1 & -0.5 \

0 & -0.25 & -0.5 & 1
\end{bmatrix} ^{-1}
\begin{bmatrix}
1 \

1 \

1 \

1
\end{bmatrix} =
\begin{bmatrix}
8 \

8 \

6 \

6
\end{bmatrix}
\end{align*}
$$

Therefore, the expected number of steps taken by the black knight to capture the white knight from the initial configuration is $\mathbf{8}$.

## Computational Verification

```
from random import choice
transitions = {
(0,0):[(2,1),(1,2)],
(0,1):[(2,0),(2,2)],
(0,2):[(1,0),(2,1)],
(1,0):[(0,2),(2,2)],
(1,2):[(0,0),(2,0)],
(2,0):[(0,1),(1,2)],
(2,1):[(0,0),(0,2)],
(2,2):[(1,0),(0,1)]
}
runs = 100000
tl = 0
for _ in range(runs):
b, w = (0,0), (2,2)
l = 0
while True:
l += 1
w = choice(transitions[w])
b = choice(transitions[b])
if b == w:
break
tl += l
print(tl/runs)
```