Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.