CircleGame.java

package net.mathoverflow.test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

// https://mathoverflow.net/q/298443/70594
public class CircleGame {
	private static int n;
	// A 'board' is represented by an array of n numbers having one of the values below.
	// The first player is 'white', the second player 'black'.
	private static final short WHITE = 1, EMPTY = 0, BLACK = -1;

	public static void main(String[] args) throws Exception {
		// Determine the board size from the program argument
		n = Integer.parseInt(args[0]);
		if (n > 39) {
			// 3^40 > 2^63 (the size of a long) so the unique code generation might not be unique anymore.
			throw new Exception("Maximum board size is 39.");
		}

		// First, we need to determine which final positions are won for white and which aren't.
		// We are going to enumerate all final positions by first concentrating on the positions
		// of the white nodes.
		// We can assume WLOG White starts at 0; this is move 0.
		short[] initialBoard = new short[n];
		initialBoard[0] = WHITE;
		populateFullBoards(initialBoard, 0, (n - 1) / 2);

		List<short[]> newBoardsToConsider = new ArrayList<>();
		int move = n / 2;

		do {
			if (move == n / 2 && n % 2 == 0) {
				// Black is making the last move, skip the white part in the first loop
			} else {
				System.out.println(currentBoardsToConsider.size() + " positions losing for Black on move " + move);
				if (currentBoardsToConsider.isEmpty()) {
					break;
				}

				// White to move; currentBoardsToConsider contains positions which are losing for Black with Black to
				// move. Therefore, we need to look for boards where White can reach one of currentBoardsToConsider
				// with a single move.
				for (short[] board : currentBoardsToConsider) {
					for (int i = 1; i < n; i++) {
						if (board[i] != WHITE)
							continue;
						// White can win by moving to i as last move
						short[] newBoard = Arrays.copyOf(board, n);
						newBoard[i] = EMPTY;
						// Already known?
						long code = getUniqueCode(newBoard);
						if (results.containsKey(code))
							continue;
						results.put(getUniqueCode(newBoard), WHITE);
						newBoardsToConsider.add(newBoard);
					}
				}

				// Prepare Black's move
				currentBoardsToConsider = newBoardsToConsider;
				newBoardsToConsider = new ArrayList<>();
			}
			System.out.println(currentBoardsToConsider.size() + " positions winning for White on move " + move);
			if (currentBoardsToConsider.isEmpty()) {
				break;
			}

			// Black to move; currentBoardsToConsider contains positions which are losing for Black with White to
			// move. Therefore, we need to look for boards where Black can reach only these losing positions,
			// whatever they move.
			for (short[] board : currentBoardsToConsider) {
				for (int i = 1; i < n; i++) {
					if (board[i] != BLACK)
						continue;
					// Undo last move
					short[] newBoard = Arrays.copyOf(board, n);
					newBoard[i] = EMPTY;
					// Already known?
					long code = getUniqueCode(newBoard);
					if (results.containsKey(code))
						continue;
					// Try all black moves (except i which we already know loses)
					boolean isLosing = true;
					for (int j = 1; j < n; j++) {
						if (board[j] != EMPTY || j == i)
							continue;
						// Move to j
						short[] newNewBoard = Arrays.copyOf(newBoard, n);
						newNewBoard[j] = BLACK;
						Short result = results.get(getUniqueCode(newNewBoard));
						if (result == null || result != WHITE) {
							isLosing = false;
							break;
						}
					}

					// Losing?
					if (!isLosing)
						continue;
					results.put(code, WHITE);
					newBoardsToConsider.add(newBoard);
				}
			}

			// Prepare White's move
			currentBoardsToConsider = newBoardsToConsider;
			newBoardsToConsider = new ArrayList<>();
			move--;
		} while (move > 0);

		if (move == 0) {
			System.out.println(currentBoardsToConsider.size() + " positions losing for Black on move " + move);
		}
	}

	private static List<short[]> currentBoardsToConsider = new ArrayList<>();
	private static Map<Long, Short> results = new HashMap<>();

	private static long getUniqueCode(short[] board) {
		// For the unique code of the board, we add 1 to all board values and interpret the result as a ternary number
		// (node 0 is the lowest (i.e. '1') digit, node 1 is the '3' digit etc.).
		long power = 1, code = 0;
		for (int i = 0; i < n; i++) {
			code += power * (board[i] + 1);
			power *= 3;
		}
		return code;
	}

	private static void populateFullBoards(short[] board, int lastWhiteMove, int movesLeft) {
		if (movesLeft == 0) {
			// We've positioned all white nodes; the remaining are black nodes
			for (int i = 1; i < n; i++) {
				if (board[i] == EMPTY)
					board[i] = BLACK;
			}
			// Determine the result of the game
			short result = determineResult(board);
			if (result == WHITE) {
				currentBoardsToConsider.add(board);
			}
			results.put(getUniqueCode(board), result);
			return;
		}

		// Recursive part
		for (int i = lastWhiteMove + 1; i <= n - movesLeft; i++) {
			short[] newBoard = Arrays.copyOf(board, n);
			newBoard[i] = WHITE;
			populateFullBoards(newBoard, i, movesLeft - 1);
		}
	}

	private static short determineResult(short[] board) {
		int longestWhiteRun = 0;
		int longestBlackRun = 0;
		int currentRun = 1;
		short currentSide = WHITE;
		for (int i = 1; i < n; i++) {
			if (board[i] == currentSide) {
				currentRun++;
			} else {
				// Check if this run is the longest run (so far) for this side
				if (currentSide == WHITE && currentRun > longestWhiteRun) {
					longestWhiteRun = currentRun;
				}
				if (currentSide == BLACK && currentRun > longestBlackRun) {
					longestBlackRun = currentRun;
				}
				// Reset current run
				currentRun = 1;
				currentSide = board[i];
			}
		}
		// If the last node is black, the current run ends there
		if (currentSide == BLACK && currentRun > longestBlackRun) {
			longestBlackRun = currentRun;
		}

		// If not, the longest white run might stretch over the end of the array
		if (longestWhiteRun > longestBlackRun)
			return WHITE;
		if (currentSide == WHITE) {
			for (int i = 0; i < n; i++) {
				if (board[i] != WHITE)
					break;
				currentRun++;
				if (currentRun > longestBlackRun)
					return WHITE;
			}
			if (currentRun > longestWhiteRun) {
				longestWhiteRun = currentRun;
			}
		}
		return (longestBlackRun > longestWhiteRun) ? BLACK : EMPTY;
	}
}