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

Let $m,n,u,v \in \mathbb{N}$ be parameters with $m,n \geq 3$. Suppose two players play a game on a $m \times n$ chess board and we denote the squares of the board by the set of points $ (i,j) $ such that $1 \leq i \leq m, 1 \leq j \leq n $. Player 1 has $u$ queens, and player 2 has $v$ knights. The initial configuration is some given subset of the board where no piece is placed at a position that can be immediately attacked by another piece of the opposing player, and the player with at least one piece when the game terminates is the winner. Both players must make a move when it is their turn. The game terminates when either player captures all of the pieces of the opposing player. If Player 1 goes first, under what circumstances does either player have a winning strategy? What can be said about the probability as a function of the parameters given with both players playing optimally, that the game will terminate in finitely many steps?

I have obtained the result for $m = 3$ and arbitrary $n$ with $u= v = 1$. Ed Dean proved that Player 1 always has a winning strategy for arbitrary $m,n$ and $u = v = 1$ (see below), and he sketched a winning strategy for Player 1 in the $u = 1, v = 2$ case. He also gave an argument for the lack of a winning strategy for Player 1 for the $u = 1, v = 3$ case. All other cases are still unknown as of yet.

Edit: Previous suggestion on a way to show in the $u = v = 1$ case that the knight can avoid capture for sufficiently large m,n is removed.

Edit 2: Thanks to Ed Dean for resolving some cases, as indicated above.

Edit 3: Included a new question regarding a related probability distribution.

Edit 4: Moved edit 3 to a new question: A random variable in a game of knights and queens

share|improve this question
1  
You haven't told us what it means for a player to win this game. –  Gerry Myerson Dec 3 '10 at 5:38
    
"It is not too hard to see that the knight can always avoid capture if all possible knight moves are available to it at its initial position without stepping off the board." This doesn't seem right. For instance, suppose we're on a standard 8-by-8 board, with Player 1's queen starting on, say, g8, and Player 2's knight on c3; I believe this meets your initial constraints. Player 1 starts with Qc4, and will capture the knight by the third move. Am I missing something? –  Ed Dean Dec 3 '10 at 5:41
    
I wondered the same thing as Gerry, but have assumed victory means capturing all the other player's queens/knights. –  Ed Dean Dec 3 '10 at 5:42
    
To Ed Dean: You are right, I think the question is more subtle than that. In this case the knight is 'stuck' because it can be backed into a corner or edge right away, reducing the size of the board to the 3 x n type. I think some additional conditions may need to be placed to see if the knight can escape. –  Stanley Yao Xiao Dec 3 '10 at 5:53
    
In the u=v=1 case, Player 1 will in fact always win. Same for the u=1, v=2 case as well. Player 1 cannot always win the u=1, v=3 case, at least not on large enough boards. There's nothing all that deep behind these particular cases, but I'd be happy to explain them roughly in an answer if you like. As for the fully general case, I've not much of an idea what could be concluded, in the sense of giving a complete answer parametrized by u,v,m,n. –  Ed Dean Dec 3 '10 at 6:27

1 Answer 1

up vote 5 down vote accepted

Here's how White (my new name for Player 1) wins in the $u=v=1$ case. The idea is of course for White to force the knight to an edge, where it can then be summarily captured. WLOG let's force the knight to the lower edge (in my coordinate system, that'll be the edge given by $n=1$). It's enough to show that whenever the knight stands at a point $(a,b)$, we can force a situation where its next move will either allow it to be captured, or will place it on a square whose $n$ coordinate is $<b$; that $n$ coordinate can't decrease forever, so White wins.

So suppose the knight starts at $(a,b)$, and the queen starts at $(c,d)$. Here's a painfully explicit strategy which works uniformly.

In case $c\ne a\pm 1$, White plays the queen to $(c,b+2)$ (the fact that $c\ne a\pm 1$ guarantees Black can't capture here). Now four of Black's moves head towards the bottom, so those are no problem. The moves to $(a-1,b+2)$ and $(a+1,b+2)$ are open to capture, so those are out. Thus Black must move to $(a\pm 2,b+1)$. But now White plays to $(a\pm 2,b+2)$, and Black's only safe moves are to squares with an $n$ coordinate of $b-1$, and the knight has been pushed down, establishing all that we need.

In case $c=a\pm 1$, White moves to $(c,b+4)$. Black's only safe non-retreat is then to $(a\pm 2,b+1)$. White plays to $(a\pm 2,b+4)$. Black has four safe moves; two place it on the $b-1$ row, and we are done. The other two place it back on the $b$ row, but such that we are now back in the previous case, so done.


I'm actually not sure how to be fully explicit in the $u=1,v=2$ case, so I'll just explain it conceptually. Roughly, if the two knights are far enough apart, it's like they aren't even part of the same game, leaving us with successive instances of the winning $u=v=1$ case. (I know very little about combinatorial game theory, but this idea of breaking up games into component sub-games is common. You can see the idea, for example, in this paper by Noam Elkies on pawn endgames, and I feel like this is a big part of thinking in Go, where various regions are their own little battles.) The second knight is irrelevant, the queen picks off one, then the other. On the other hand, if the knights are close enough, the queen will be able to attack both at once, and moreover can arrange that with either side to move, leading to a capture of one knight and reduction to the $u=v=1$ case.


Finally, if $u=1,v=3$, here's an initial position of the knights which White can't win. Place them at $(a,b)$, $(a+2,b+1)$ and $(a+4,b+2)$. They all protect each other here, and no matter where White places the queen, one of the "outer" knights has a safe square to move to, and can then just move back on the next move.


Generally, if $v=u+1$, White will usually be able to at least force repeated even trades of a single queen for a single knight, reducing to the winning $u=1,v=2$ case; but with huge numbers of pieces I don't know how to solidly argue this. For arbitrary $u,v$, the space of possibilities is such that I have absolutely no idea what can be said in general.

share|improve this answer
    
It is funny that the lack of kings actually hurts the defending side in the u=1 v=2 case :) One can show that u=2 v=4 is a win for white as well, it is not hard to show that in this case you will be able to exchange a queen for 2 knights (this might not be true for larger quantities of knights). So the question becomes what is u=2 v=5 since your answer shows that u=2 v=6 is a draw if the knights have enough time to get organized. –  Orange Dec 30 '10 at 15:18

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.