LimitedValueUCTPlayer.java

package codecup2022.player;

import codecup2022.data.Board;
import codecup2022.data.Move;
import codecup2022.data.RolloutBoard;
import codecup2022.movegenerator.MoveGenerator;
import codecup2022.stopcriterion.IterationCount;
import codecup2022.stopcriterion.StopCriterion;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class LimitedValueUCTPlayer extends Player {

    private static final int MAX_ITERATIONS = 200_000;
    
    private final MoveGenerator generator;
    private final StopCriterion stop;
    private final int ucbLimit;
    private final double explorationWeight;
    private final double valueWeight;
    private final Random rand;

    public LimitedValueUCTPlayer(MoveGenerator generator, StopCriterion stop, int ucbLimit, double explorationWeight, double valueWeight, Random rand) {
        super(String.format("LimValUCT-%s-%s-%d-%.2f-%.2f", generator.name(), stop.name(), ucbLimit, explorationWeight, valueWeight));
        this.generator = generator;
        this.stop = stop;
        this.ucbLimit = ucbLimit;
        this.explorationWeight = explorationWeight;
        this.valueWeight = valueWeight;
        this.rand = rand;
    }

    private double[] sqrt = null;
    private double[] sqrtLog = null;

    @Override
    protected int selectMove() {
        stop.started();
        if (sqrt == null) {
            precomputeSquareRoots();
        }

        TreeNode root = new TreeNode(null, -1, 0, board, isBlue());
        int majority = (stop instanceof IterationCount ? ((IterationCount) stop).getMaxIterations() / 2 : MAX_ITERATIONS / 2);
        int maxExpandedTurn = board.getTurn();

        for (int i = 0; i < MAX_ITERATIONS && !stop.shouldStop(); i++) {
            TreeNode node = root;
            TreeNode firstMoveNode = null;
            Board b = new RolloutBoard(board);

            // Traverse the tree
            while (node.isFullyExpanded()) {
                node = node.selectMoveNode();
                b.applyMove(node.move);

                if (firstMoveNode == null) {
                    firstMoveNode = node;
                }
            }

            // Expand
            if (!node.isLeaf()) {
                node = node.expand(b);
            }

            maxExpandedTurn = Math.max(maxExpandedTurn, b.getTurn());

            // Play the rest of the game randomly
            int[] score = rollout(b);

            // Update nodes along the path we followed
            while (node != null) {
                node.updateValue(score);
                node = node.parent;
            }

            // No improvement possible?
            if (firstMoveNode != null && firstMoveNode.visits >= majority) {
                break;
            }
        }

        TreeNode result = root.mostVisitedChild();

        if (Player.SCORE) {
            System.err.printf("%s (%.2f, %d) D=%d%n", Move.toString(result.move), result.value, result.visits, maxExpandedTurn);
        }

        return result.move;
    }

    private int[] rollout(Board b) {
        int[] empty = b.emptySpaces();
        Move.shuffle(empty, rand);

        for (int i = 0; i < empty.length; i++) {
            b.applyMove(Move.setTile(empty[i], rand.nextInt(3)));
        }

        return new int[]{b.getScore(true), b.getScore(false)};
    }

    private void precomputeSquareRoots() {
        sqrt = new double[MAX_ITERATIONS + 1];
        sqrtLog = new double[MAX_ITERATIONS + 1];

        for (int i = 0; i <= MAX_ITERATIONS; i++) {
            sqrt[i] = Math.sqrt(i);
            sqrtLog[i] = Math.sqrt(explorationWeight * Math.log(i));
        }
    }

    private class TreeNode {

        final TreeNode parent;
        final int move;
        final int moveScoreDelta;
        final boolean blueToMove;
        final int[] possibleMoves;
        final List<TreeNode> children = new ArrayList<>();

        int unexpandedMoveCount;
        int visits = 0;
        double value = 0;

        private TreeNode(final TreeNode parent, final int move, final int moveScoreDelta, final Board b, final boolean blueToMove) {
            this.parent = parent;
            this.move = move;
            this.moveScoreDelta = moveScoreDelta;
            this.blueToMove = blueToMove;
            this.possibleMoves = generator.generateMoves(b);
            this.unexpandedMoveCount = possibleMoves.length;
        }

        private boolean isLeaf() {
            return possibleMoves.length == 0;
        }

        private boolean isFullyExpanded() {
            return unexpandedMoveCount == 0 && possibleMoves.length > 0;
        }

        private TreeNode expand(final Board b) {
            // Pick a random move
            final int moveIndex = rand.nextInt(unexpandedMoveCount);
            final int childMove = possibleMoves[moveIndex];

            // Compact possibleMoves so that the first unexpandedMoveCount moves are still unexpanded
            unexpandedMoveCount--;
            possibleMoves[moveIndex] = possibleMoves[unexpandedMoveCount];

            int scoreBefore = b.getScore(blueToMove);
            b.applyMove(childMove);
            int scoreDelta = b.getScore(blueToMove) - scoreBefore;

            final TreeNode child = new TreeNode(this, childMove, scoreDelta, b, !blueToMove);
            children.add(child);
            return child;
        }

        private TreeNode selectMoveNode() {
            if (visits < ucbLimit) {
                return randomChild();
            } else {
                return bestUCBChild();
            }
        }
        
        private TreeNode randomChild() {
            return children.get(rand.nextInt(children.size()));
        }

        private TreeNode bestUCBChild() {
            TreeNode best = null;
            double bestValue = Double.NEGATIVE_INFINITY;

            final double parentVisitFactor = sqrtLog[visits];

            for (final TreeNode child : children) {
                final double ucbValue = child.isLeaf() ? child.value : child.value + (valueWeight * child.moveScoreDelta + parentVisitFactor) / sqrt[child.visits];

                if (ucbValue > bestValue) {
                    bestValue = ucbValue;
                    best = child;
                }
            }

            return best;
        }

        private TreeNode mostVisitedChild() {
            TreeNode mostVisited = null;
            int mostVisits = -1;

            for (final TreeNode child : children) {
                if (child.visits > mostVisits) {
                    mostVisited = child;
                    mostVisits = child.visits;
                }
            }

            return mostVisited;
        }

        private void updateValue(final int score[]) {
            // This node's value is used by the parent to pick the best move
            // Therefore we should pick the score for our parent's color
            final int nodeScore = blueToMove ? score[1] : score[0];

            value = value * visits + nodeScore;
            visits++;
            value /= visits;
        }
    }
}