Knights on a Chessboard

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

The state of the game is determined by the position of the two knights. Configurations related by rotation or reflection collapse into a single equivalence class. The next state of the game depends only on the current state. This is a Markov chain problem.

With four transient states and one absorbing state (capture), the transition matrix $\mathbf{Q}$ on the transient block is

$$\mathbf{Q} \;=\; \begin{pmatrix} 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{pmatrix}.$$

The fundamental matrix $\mathbf{N} = (\mathbf{I} - \mathbf{Q})^{-1}$ gives the expected hitting times as $\mathbf{N} \mathbf{c}$, where $\mathbf{c}$ is the column of ones. Computing,

$$\mathbf{N} \mathbf{c} \;=\; \begin{pmatrix} 8 \\ 8 \\ 6 \\ 6 \end{pmatrix}.$$

Starting from the initial configuration (state 1), the expected number of moves to capture 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 = 100_000
total = 0
for _ in range(runs):
    b, w = (0, 0), (2, 2)
    steps = 0
    while True:
        steps += 1
        w = choice(transitions[w])
        b = choice(transitions[b])
        if b == w:
            break
    total += steps
print(total / runs)

The Monte Carlo estimate converges to $8.0$, matching the closed form.