Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  Joseph O'Rourke Dec 20 '10 at 18:07

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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