12
$\begingroup$

Alice and Bob play the following game on a standard $8\times8$ chessboard.

  • In the very beginning, Alice picks a square on the chessboard and places a knight on this square.
  • Then Bob and Alice alternate in moving the knight. Bob makes the first move. The knight moves in standard chess knight-move fashion, but it must never revisit a square that it has visited in an earlier move.
  • The game ends, once a player has no move left. This player wins the game.

Question: Which player is going to win this game? (As usual, we assume that Alice and Bob both use optimal strategies.)

$\endgroup$
  • $\begingroup$ Related. $\endgroup$ – xnor Nov 17 '15 at 23:52
  • 1
    $\begingroup$ Is there a clever solution to this puzzle? Or is it only doable by computer search? This question is fascinating, I would really love to know the best solution! $\endgroup$ – Mike Earnest Nov 22 '15 at 21:27
  • $\begingroup$ @MikeEarnest,@Sleafar, this question is a duplicate of math.stackexchange.com/questions/897092/… and as shown there, Bob has a winning strategy because the knight-graph has a perfect matching; the graph is bipartite and Bob keeps taking the other end-point of the edge in the perfect matching. $\endgroup$ – Aravind Dec 13 '15 at 15:02
  • 1
    $\begingroup$ @Aravind In the question you linked, you lose if you can't move. In this question, you win if you can't move. This question is not a duplicate, and the matching strategy doesn't work for this game. $\endgroup$ – Mike Earnest Dec 13 '15 at 17:41
  • $\begingroup$ Ah, missed that. $\endgroup$ – Aravind Dec 13 '15 at 17:58
9
$\begingroup$

The player who will win this game on an $8 \times 8$ board is:

Bob, assuming he has a computer and a few hours to calculate the variants (details below). It doesn't matter which square is chosen by Alice, because Bob has always a forced win. On smaller boards Alice has always at least one square which she can choose to win.

With the result known, maybe someone can come up with a solution that doesn't require an exhaustive search. But if the solution is not specific to an $8 \times 8$ board, it has to explain why Alice can win on smaller boards.

Computer based proof

I managed to significantly increase the speed of my previously posted program, so I was able to calculate the result for an $8 \times 8$ board. It's much bigger now, but I have added some comments this time. The speed up was achieved through following steps:

  • Mutlithreading: Usually pretty obvious, but I use it here only to calculate all starting positions in parallel. This doesn't complicate the code as much as other possibilities.
  • Precalculating possible moves: Also pretty obvious, not much to say here.
  • Sorting the possible moves: This was the most important point, and a huge speed up. The idea is, if we find a winning move for the current player, we don't need to check the other possible moves. The hard part is to find the right moves. I did it here by sorting the possible moves by the number of possible moves from their target square. So corner squares are preferred, squares in the center are searched last. The effect is huge, if you want to see it set the SIZE to 7 and reverse the sorting.

Despite the speed up, calculating the $8 \times 8$ results takes several hours. On a Core i5 I got the result for the first square (C1) after 1 h 38 m. Total runtime was about 8.5 hours.

Results for smaller boards

The result is that Alice always has a square where she can guarantee a win:

  • $3 \times 3$: any square except B2 (example win)
  • $4 \times 4$: any corner square (example win/loss)
  • $5 \times 5$: A1, C2 and any mirrored/rotated version of them (example win/loss)
  • $6 \times 6$: C2 and any mirrored/rotated version (example win/loss)
  • $7 \times 7$: any black square (example win/loss)

The code

import java.time.Duration;
import java.time.Instant;
import java.util.Arrays;

public class Main {
    private static final int SIZE = 6;
    private static final int[] ROW_OFFSET = new int[] { 2, 1, -1, -2, -2, -1, 1, 2 };
    private static final int[] COL_OFFSET = new int[] { 1, 2, 2, 1, -1, -2, -2, -1 };

    private static class Square {
        /** Usual naming: A1, B2, C3, ... */
        public final String name;
        /** Possible knight moves from this square. */
        public Square[] moves = new Square[0];
        /** Marks that this square was already used in the current variant. */
        public boolean used = false;

        public Square(int row, int col) {
            super();
            this.name = (char) ('A' + col) + "" + (1 + row);
        }

        /** Append a move to the array. */
        public void addMove(Square square) {
            int tmp = moves.length;
            moves = Arrays.copyOf(moves, tmp + 1);
            moves[tmp] = square;
        }
    }

    /** Create a new board with the given size. */
    private static Square[][] createBoard(int size) {
        Square[][] board = new Square[size][size];
        // Create all squares first, so that they can be referenced later.
        for (int row = 0; row < size; ++row) {
            for (int col = 0; col < size; ++col) {
                board[row][col] = new Square(row, col);
            }
        }
        // Precalculate all possible knight moves.
        for (int row = 0; row < size; ++row) {
            for (int col = 0; col < size; ++col) {
                for (int i = 0; i < ROW_OFFSET.length; ++i) {
                    int newRow = row + ROW_OFFSET[i];
                    int newCol = col + COL_OFFSET[i];
                    if (newRow >= 0 && newRow < size &&
                            newCol >= 0 && newCol < size) {
                        board[row][col].addMove(board[newRow][newCol]);
                    }
                }
            }
        }
        // Sort the possible moves by number of moves from the target square.
        for (int row = 0; row < size; ++row) {
            for (int col = 0; col < size; ++col) {
                Arrays.sort(board[row][col].moves, (o1, o2) ->
                        Integer.compare(o1.moves.length, o2.moves.length));
            }
        }
        return board;
    }

    /**
     * Determine the winner of current position.
     * @param player '0' for the first moving player (Bob), '1' for the second
     *               moving player (Alice).
     * @param square Target square of the last move, or square chosen by Alice
     *               to start.
     * @return Number of the player who will win the game.
     */
    private static int winner(int player, Square square) {
        // Mark target square as used.
        square.used = true;
        try {
            boolean movesLeft = false;
            // Recursively check all possible moves.
            for (Square newSquare : square.moves) {
                if (!newSquare.used) {
                    movesLeft = true;
                    if (winner(1 - player, newSquare) == player) {
                        // If the current move wins the game for current player,
                        // there is no need to look further.
                        return player;
                    }
                }
            }
            // No winning move found. If there are no moves left at all we win,
            // otherwise we loose.
            return movesLeft ? 1 - player : player;
        } finally {
            // Unmark target square before backtracking.
            square.used = false;
        }
    }

    public static void main(String[] args) {
        Instant begin = Instant.now();
        // Check all unique starting squares.
        for (int row = 0; row < (SIZE + 1) / 2; ++row) {
            for (int col = row; col < (SIZE + 1) / 2; ++col) {
                // Each square is checked by a separate thread, so each of them
                // need a new copy of the board.
                Square square = createBoard(SIZE)[row][col];
                new Thread() {
                    @Override
                    public void run() {
                        System.out.println(square.name + " " +
                                winner(0, square) + " " +
                                Duration.between(begin, Instant.now()));
                    }
                }.start();
            }
        }
    }
}
$\endgroup$
2
$\begingroup$

Edit: Just to be clear, the following argument does not work because of Tim Couwelier's comment.


The winner is

Alice by a strategy stealing argument.

Call the game where Alice starts in the corner and both players move optimally "the a1 game". If Alice wins the a1 game, then we are done. If Bob wins the a1 game, then have Alice start in a square that is a knights move away from a corner, and call this "the b3 game". In the b3 game, if she chooses, Alice can steal Bob's strategy from the a1 game. Every time Bob makes a move in the b3 game, Alice responds by making Bob's move from the a1 game.

The only difference between the two games is that in b3 game the corner square is a valid move. Notice if Bob does move to that corner square, this is an automatic win for Alice in the b3 game. If Bob somehow wins the b3 game without ever moving on that corner, then this would correspond to Alice winning the a1 game, since in the b3 game having an extra square Bob can move to makes it harder for Bob to win. Thus if the a1 game is a loss of Alice, the b3 game will be a win.

$\endgroup$
  • 4
    $\begingroup$ Might be my interpretation, but 'b3 to a1' as first move, does not imply you can just play the 'a1' game from there onwards. the b3 square may or may not have had a critical relevance in the a1 game.... then for a second I thought you meant 'b3 to a1' means the knight is stuck, thus forcing a win for one of them - but you could back out of the corner to c2 without any problem... $\endgroup$ – Tim Couwelier Nov 16 '15 at 15:47
  • $\begingroup$ @TimCouwelier: Good point -- can't believe I missed that! Thanks for spotting the error. $\endgroup$ – Tyler Seacrest Nov 16 '15 at 16:07
-2
$\begingroup$

Well, seemingly

Alice will win. The knight alternates color each move. Bob always has a square more, Alice has one down since she chooses the starting square, which she can't return to.

$\endgroup$
  • $\begingroup$ Why does Bob always have a square left? $\endgroup$ – Ivo Beckers Nov 16 '15 at 9:45
  • $\begingroup$ Alice places on white, there are 32 black squares left, giving Bob 32 moves, but only 31 moves available for Alice, moving onto white. She'll run out of moves quicker (assuming optimal strategy etc.) $\endgroup$ – JNF Nov 16 '15 at 9:53
  • $\begingroup$ Note also the misère winning condition. If Bob always has a move left, then Alice would win. $\endgroup$ – Tyler Seacrest Nov 16 '15 at 9:53
  • $\begingroup$ Oh, I got it backwards then.. $\endgroup$ – JNF Nov 16 '15 at 9:54
  • 5
    $\begingroup$ Sure there are 32 black squares but this doesn't mean that all are reachable. You assume that no matter how they play there is always a knight's tour $\endgroup$ – Ivo Beckers Nov 16 '15 at 10:12

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.