8
$\begingroup$

There is a player who controls only a queen, while his opponent controls a knight. Both pieces start from opposite corners of the board. The aim is to kill the knight, without having your queen killed. The board is square, of side $n$.

Case I: The opponent only knows that he should
(a) kill the queen on his current move, if possible
(b) escape to a slot where he can't be killed on the immediate next move
(c) move randomly to any one of the 'safe' slots, as in (b)

Case II: The opponent is a perfect player, and can look into infinite depth and all possible scenarios of the game.

What is the maximum board size for which the queen is 'guaranteed' to win, in Case I and in Case II?

Notes:
1. In Case I, since moves are random, it is possible that if you can keep coming back to the same position, the knight will eventually make a bad move.
2. 'randomly' means that all 'safe' moves have equal probability, but as the queen's win needs to be guaranteed, this should not affect the answer.
3. There is no limit on moves, time, etc. and no possibility of a draw. 4. The knight always starts.

Since this got answered so quickly, let me make a harder version: The knight is allowed to decide the initial placement of the queen as well as itself. Rest of the question is same.

$\endgroup$
  • 9
    $\begingroup$ If I start, size of the board doesn't matter, my queen will kill the knight on the first turn $\endgroup$ – Novarg Feb 10 '15 at 14:48
  • $\begingroup$ I don't think Case I and Case II are distinct; always beating a random strategy is equivalent to beating every strategy, which is equivalent to beating the optimal strategy. $\endgroup$ – Milo Brandt Feb 11 '15 at 0:15
  • $\begingroup$ @Meelo I had asked separately because I was not sure if an optimal strategy can be defeated. $\endgroup$ – ghosts_in_the_code Feb 11 '15 at 9:35
  • 2
    $\begingroup$ @Meelo: If one interprets "guaranteed win" as "the probability of not winning within N moves approaches zero as N approaches infinity", then one may have a guaranteed win against a random opponent without having a win against an optimal opponent. $\endgroup$ – supercat Jun 19 '15 at 16:29
14
$\begingroup$

For the updated version, I'll assume that after the placement of the pieces, the queen moves first. (Otherwise the knight could arrange things so that the queen is captured on the first move.)

In this situation, the queen will still always win.

Wherever the two pieces start, the queen can get to a space adjacent to the knight in no more than 3 moves. First, move to the same row as the knight. (Or the same column, but we can say row without loss of generality.) The knight's possible moves put it either 1 or 2 rows away. If it moves by one row, the queen moves to the space adjacent. If it moves two rows, the queen moves to be in the same column. Now, if the knight moves one column to the side, the queen can move vertically to an adjacent space. If the knight moves two columns to the side, the queen can move diagonally to an adjacent space.

So, now we have the queen vertically adjacent to the knight, which leaves the knight with two possible moves, as shown:

..o.o..
.x...x.
...N...
.x.Q.x.
..x.x..

The o's represent possible moves. Whichever space the knight moves to, let the queen move one space diagonally to be in the same column. Then we get this:

..o.o..
.o...o.
...N...
.o...o.
..xQx..

For any of the four lower spaces, the queen can move either horizontally or vertically to be one space below the knight, returning to the first setup, but one row higher. So, suppose that the knight takes one of the moves that take it two spaces up. If the queen moves diagonally up to match again, we get:

..o.o..
.o...o.
...N...
.x...x.
..x.x..
...Q...

Again, the leftmost and rightmost moves allow a diagonal move from the queen to return to a previous state. So, let us suppose that the knight moves farther up again. Then let the queen move vertically 4 spaces, to be diagonally adjacent to the knight.

...x.o..
..o...x.
....N...
..xQ..x.
...x.o..
........

Now the knight has three available moves, but for any of them, the queen can follow up with a diagonal move to be one space below, returning to the first configuration. Even if the knight moves down, this was preceded by three moves up, so the knight has moved up the board overall. The queen can continue forcing the knight in one direction like this until they reach the edge of the board, which further restricts the knight's moves and allows the queen to capture.

$\endgroup$
  • 1
    $\begingroup$ Yeah, on a finite board, it seems the knight can't do it. On an infinite board, it can go forever. $\endgroup$ – yo' Feb 10 '15 at 17:50
  • $\begingroup$ Can you elaborate on "From there, the queen can pin the knight to an edge of the board and capture it"? $\endgroup$ – Julian Rosen Feb 10 '15 at 18:13
  • $\begingroup$ @JulianRosen I edited quite a bit. Does this explain things well enough? $\endgroup$ – KSmarts Feb 10 '15 at 18:44
  • $\begingroup$ Yes, that explains it. $\endgroup$ – Julian Rosen Feb 10 '15 at 18:55
14
$\begingroup$

The queen can always win. If the queen goes first, obviously it will win (just take the knight). If the knight goes first, there are only 2 places to go (mirrored, so effectively the same):

- - - - - +
. . . . . |
. . K . . |
. . . . . |
. . . . . |

All the queen has to do is move:

- - - - - +
. . . . . |
. . K . . |
. . Q . . |
. . . . . |

All the places the knight can go are:

- - - - - +
x . . . x |
. . K . . |
x . Q . x |
. x . x . |

Which are all in the queen's sight.

Now, let's say they start on adjacent corners (K in top right).

- - - - - - + -> - - - - - - + or - - - - - - +
. . Q . . . |    . . . . . . |    . . . . . . |
. . . K . . |    . . . . . . |    . . . . . . |
. . . . . . |    Q K . . . . |    . . . . . . |
. . . . . . |    . . . . . . |    . . Q . K . |

or

- - - - - +    - - - - - +
. Q . . . |    . . . . . |
. . . . . |    . . . . . |
. . . K . |    . . . . . |
. . . . . |    . . . . . |
. . . . . |    . Q K . . |

Either way, the Queen has now pinned the knight against an edge and can eventually reach the original scenario.

$\endgroup$
9
$\begingroup$

Let's assume that opponent's Knight stands on A1, then my queen will be on {last letter}{last number}

For both cases:

I will always win in max 2 turns on any board size:
If I start: my queen will immediately kill the knight
If opponent starts: he can only move to B3 or C2. Then I would move my queen to C3. At this moment Knight is under attack of my queen and he only has following moves:
option 1
option 2
No matter where he moves, my queen will always kill him on her second move

For the updated question:

If Knight starts, game is over(unless it's a very kind Knight who didn't place himself to immediately kill the queen).
If queen starts, first move will be to get to the same line/column as the knight. Then knight can move either 1 or 2 lines/columns away from the queen. Next step of my queen would be to move as close to the knight as possible. There are 2 possibilities(actually 8, but other 6 are the same, just turned around):
possibility 1 possibility 2
In both cases, yellow are the ones where knight can go and won't immediately be killed by the queen. But possibility 1 will only happen once, due to the fact that queen can get to adjacent square in her next move, no matter where knight goes.
And then it will just be a chase to get the knight. No matter what happens, eventually the queen will kill the knight

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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