Return to 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

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

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.

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

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.

Now to take the question a different direction, suppose that we set $m = n$ and $u,v$ 'small' relative to $n$, say $u, v \leq n/3$. 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?

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.

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.