Suppose that a game is played on an $n \times n$ board as follows. There are two players, Player 1 has (only) $Q$ queens and Player 2 has only $K$ knights. Suppose that $Q, K \leq n/3$. The game is played as per usual in chess, with Player 1 going first. The objective is to capture all of the other players' pieces. Now we fix the initial configuration by placing the queens arbitrarily on the left most column, then place all of the knights on the right most column so that no knight and queen are initially on the same row. Now suppose that both players play with no strategy; that is, each player randomly chooses a legal move each turn with all legal moves having equal probability, and illegal moves (defined as a move that will cause the moving piece to be captured in the next move) with probability zero. Consider the random variable $X$ that satisfies $X = k$ if on the $k$th move Player 1 wins the game, and $X = -k$ if on the $k$th move Player 2 wins the game. Then what can we say about $X$? For example, does it have finite mean or variance? Is it possible to give an explicit distribution? Are there any existing probabilistic models that model its behaviour?

  • $\begingroup$ The $3 \times 3$ game with one $Q$ and $N$ in opposite corners should be amenable to analysis. Seems the $Q$ should have advantage on 1st move, and even more advantage on 2nd move. $\endgroup$ Dec 20, 2010 at 18:07

1 Answer 1


It is standard to show that $X$ has exponential decay: for any position, there is a fixed positive probability that the game will terminate within the next (say) 10n steps. In particular, all moments of $X$ are finite.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.