Knights on a chess board

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

1. The complete state of the game is determined by the position of the two knights on the board.
2. The next state of the game only depends on the current state.
3. 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)