Solver.java

import java.util.List;
import java.util.ArrayList;

public class Solver {
    private static final int MAX_DEPTH = Position.WIDTH * Position.HEIGHT;
    private long nodes = 0;
    private int[] columnOrder = new int[Position.WIDTH];
    private TranspositionTable transpositionTable = new TranspositionTable(8388593);
    private final int[][] killerMoves = new int[MAX_DEPTH][2];
    private final int[] history = new int[Position.WIDTH];

    public Solver() {
        reset();

        for (int i = 0; i < Position.WIDTH; i++) {
            columnOrder[i] = Position.WIDTH / 2 + (1 - 2 * (i % 2)) * (i + 1) / 2;
        }
    }

    private int negamax(Position pos, int alpha, int beta, int depth) {
        assert alpha < beta;
        nodes++;

        if (pos.getMoves() == Position.WIDTH * Position.HEIGHT) {
            return 0;
        }

        for (int x = 0; x < Position.WIDTH; x++) {
            if (pos.playable(x) && pos.winsByPlaying(x)) {
                return (Position.WIDTH * Position.HEIGHT + 1 - pos.getMoves()) / 2;
            }
        }

        List<Integer> safe = new ArrayList<>();
        Position.State root = pos.save();
        for (int x = 0; x < Position.WIDTH; x++) {
            if (!pos.playable(x))
                continue;
            pos.restore(root);
            pos.play(x);
            boolean oppWins = false;
            for (int y = 0; y < Position.WIDTH; y++) {
                if (pos.playable(y) && pos.winsByPlaying(y)) {
                    oppWins = true;
                    break;
                }
            }
            if (!oppWins)
                safe.add(x);
        }
        pos.restore(root);
        if (safe.size() == 1) {
            Position.State s2 = pos.save();
            pos.play(safe.get(0));
            int score = -negamax(pos, -beta, -alpha, depth + 1);
            pos.restore(s2);
            return score;
        }

        int max = (Position.WIDTH * Position.HEIGHT - 1 - pos.getMoves()) / 2;
        int val = transpositionTable.get(Math.min(pos.key(), pos.mirrorKey()));
        int range = Position.MAX_SCORE - Position.MIN_SCORE + 1;
        if (val != 0) {
            if (val > range) {
                int lb = val + 2 * Position.MIN_SCORE - Position.MAX_SCORE - 2;
                if (alpha < lb) {
                    alpha = lb;
                    if (alpha >= beta) {
                        return alpha;
                    }
                }
            } else {
                int ub = val + Position.MIN_SCORE - 1;
                if (beta > ub) {
                    beta = ub;
                    if (alpha >= beta) {
                        return beta;
                    }
                }
            }
        }

        if (beta > max) {
            beta = max;
            if (alpha >= beta) {
                return beta;
            }
        }

        int[] moves = new int[Position.WIDTH];
        boolean[] used = new boolean[Position.WIDTH];
        int mcount = 0;
        for (int k = 0; k < 2; k++) {
            int km = killerMoves[depth][k];
            if (km >= 0 && pos.playable(km) && !used[km]) {
                moves[mcount++] = km;
                used[km] = true;
            }
        }
        int[] rest = new int[Position.WIDTH];
        int rcount = 0;
        for (int col : columnOrder) {
            if (pos.playable(col) && !used[col])
                rest[rcount++] = col;
        }
        for (int i = 1; i < rcount; i++) {
            int keyCol = rest[i], j = i - 1;
            while (j >= 0 && history[rest[j]] < history[keyCol]) {
                rest[j + 1] = rest[j];
                j--;
            }
            rest[j + 1] = keyCol;
        }
        for (int i = 0; i < rcount; i++)
            moves[mcount++] = rest[i];

        for (int xi = 0; xi < mcount; xi++) {
            int col = moves[xi];
            long key0 = pos.key();
            Position.State snapshot = pos.save();
            pos.play(col);
            int score;
            if (xi == 0) {
                score = -negamax(pos, -beta, -alpha, depth + 1);
            } else {
                score = -negamax(pos, -alpha - 1, -alpha, depth + 1);
                if (score > alpha && score < beta) {
                    score = -negamax(pos, -beta, -alpha, depth + 1);
                }
            }
            pos.restore(snapshot);
            if (score >= beta) {
                killerMoves[depth][1] = killerMoves[depth][0];
                killerMoves[depth][0] = col;
                history[col]++;
                int lowerVal = score + Position.MAX_SCORE - 2 * Position.MIN_SCORE + 2;
                transpositionTable.put(Math.min(key0, pos.mirrorKey()), (byte) lowerVal,
                        (byte) (Position.WIDTH * Position.HEIGHT - depth), TranspositionTable.BOUND_LOWER);
                return score;
            }
            if (score > alpha) {
                history[col] += depth;
                alpha = score;
            }
        }

        // final cache store with symmetry
        transpositionTable.put(Math.min(pos.key(), pos.mirrorKey()),
                (byte) (alpha - Position.MIN_SCORE + 1),
                (byte) (Position.WIDTH * Position.HEIGHT - depth), TranspositionTable.BOUND_EXACT);
        return alpha;
    }

    public int solve(Position pos) {
        nodes = 0;
        int bestScore = 0;
        int fullAlpha = -Position.WIDTH * Position.HEIGHT / 2;
        int fullBeta = Position.WIDTH * Position.HEIGHT / 2;
        int aspDelta = 2;
        for (int iter = 1; iter <= MAX_DEPTH; iter++) {
            int alpha = bestScore - aspDelta;
            int beta = bestScore + aspDelta;
            int score = negamax(pos, alpha, beta, 0);
            if (score <= alpha || score >= beta) {
                score = negamax(pos, fullAlpha, fullBeta, 0);
            }
            bestScore = score;
        }
        return bestScore;
    }

    public long getNodes() {
        return nodes;
    }

    public void reset() {
        nodes = 0;
        transpositionTable.reset();
    }
}

class Timer {
    private long start;

    public Timer() {
        start = System.nanoTime();
    }

    public long elapsed() {
        return System.nanoTime() - start;
    }
}