A Game of Knights and Queens

Question

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

Answer 1

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.