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.)
Answer
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();
}
}
}
}
No comments:
Post a Comment