MonteCarloSimpleAI.java

package AIs;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Random;
import Game.AI;

/*
    The MIT License (MIT)
    
    Copyright (c) 2015 wallstop
    
    Permission is hereby granted, free of charge, to any person obtaining a copy
    of this software and associated documentation files (the "Software"), to deal
    in the Software without restriction, including without limitation the rights
    to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
    copies of the Software, and to permit persons to whom the Software is
    furnished to do so, subject to the following conditions:
    
    The above copyright notice and this permission notice shall be included in
    all copies or substantial portions of the Software.
    
    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
    IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
    FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
    AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
    LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
    OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
    THE SOFTWARE.
*/

/* 
 * A simple AI that plays out a large number of games, picking the moves that 
 * result in the highest percentage chance of it winning (from it's simulation's 
 * perspective) 
 */
public final class MonteCarloSimpleAI extends AI
{
    // Wish these values were provided to us, or better yet, provided through abstractions
    // Why isn't the board well defined?
    private static final int SELF_VALUE = 1;
    private static final int ADVERSARY_VALUE = -1;
    private static final int CONSECUTIVE_MOVES_TO_WIN = 4;
    /*
     * We're given a 10 second window to compute our moves - maximum time to
     * spend on a move + a grace period to make sure our work is deemed
     * "within the bounds"
     */
    private static final long MAX_COMPUTATION_TIME_MILLISECONDS = 900;
    private static final Random RGEN = new Random();

    /**
     * Simple Direction class used for navigating 2d grid-space. These
     * Directions correspond to the arrays above which can be used to navigate
     * space easily
     */
    public static final class Direction
    {
        private static final int[] X_DIR = { 0, 1, 1, 1, 0, -1, -1, -1 };
        private static final int[] Y_DIR = { 1, 1, 0, -1, -1, -1, 0, 1 };

        public static enum State
        {
            DIRECTION_NORTH, DIRECTION_NORTH_EAST, DIRECTION_EAST, DIRECTION_SOUTH_EAST, DIRECTION_SOUTH, DIRECTION_SOUTH_WEST, DIRECTION_WEST, DIRECTION_NORTH_WEST
        }

        private final State state_;
        public static final Direction NORTH = new Direction(State.DIRECTION_NORTH);
        public static final Direction NORTH_EAST = new Direction(State.DIRECTION_NORTH_EAST);
        public static final Direction EAST = new Direction(State.DIRECTION_EAST);
        public static final Direction SOUTH_EAST = new Direction(State.DIRECTION_SOUTH_EAST);
        public static final Direction SOUTH = new Direction(State.DIRECTION_SOUTH);
        public static final Direction SOUTH_WEST = new Direction(State.DIRECTION_SOUTH_WEST);
        public static final Direction WEST = new Direction(State.DIRECTION_WEST);
        public static final Direction NORTH_WEST = new Direction(State.DIRECTION_NORTH_WEST);

        /*
         * Assuming directions are a never-ending line, this enumerationprovides
         * the unique ones (ie, North is on the same line as South, soonly one
         * will be in this enumeration)
         * 
         * Note: This needs to be declared after the NORTH, NORTH_EAST, etc
         * Direction declarations or it will be filled with null values.
         */
        public static final Direction[] ITERABLE_DIRECTIONS = { Direction.NORTH,
                Direction.NORTH_EAST, Direction.EAST, Direction.SOUTH_EAST };

        private Direction(State state)
        {
            state_ = state;
        }

        /* The X value for the Unit Vector representing this Direction */
        public int getX()
        {
            return X_DIR[state_.ordinal()];
        }

        /* The Y value for the Unit Vector representing this Direction */
        public int getY()
        {
            return Y_DIR[state_.ordinal()];
        }

        public Direction opposite()
        {
            switch(state_)
            {
            case DIRECTION_NORTH:
                return SOUTH;
            case DIRECTION_NORTH_EAST:
                return SOUTH_WEST;
            case DIRECTION_EAST:
                return WEST;
            case DIRECTION_SOUTH_EAST:
                return NORTH_WEST;
            case DIRECTION_SOUTH:
                return NORTH;
            case DIRECTION_SOUTH_WEST:
                return NORTH_EAST;
            case DIRECTION_WEST:
                return EAST;
            case DIRECTION_NORTH_WEST:
                return SOUTH_EAST;
            default:
                return null;
            }
        }

        public State state()
        {
            return state_;
        }
    }

    // Why are the Players magic constants hidden in the GameAutomator class?
    private static enum Player
    {
        SELF, ADVERSARY;

        public Player getNextPlayer()
        {
            switch(this)
            {
            case SELF:
                return ADVERSARY;
            case ADVERSARY:
                return SELF;
            }
            throw new IllegalArgumentException("Unknown player " + this);
        }

        public static Player playerFor(final int value)
        {
            switch(value)
            {
            case SELF_VALUE:
                return SELF;
            case ADVERSARY_VALUE:
                return ADVERSARY;
            }
            throw new IllegalArgumentException(value + " doesn't correspond to a player");
        }

        public static boolean isValidPlayerValue(final int value)
        {
            return value == SELF_VALUE || value == ADVERSARY_VALUE;
        }
    }

    private static final class ConnectFourMove
    {
        private final int column_;
        private final Player player_;

        public ConnectFourMove(final int column, final Player player)
        {
            column_ = column;
            player_ = player;
        }

        public int getColumn()
        {
            return column_;
        }

        public Player getPlayer()
        {
            return player_;
        }

        @Override
        public boolean equals(Object other)
        {
            if(other == null || !(other instanceof ConnectFourMove))
            {
                return false;
            }
            if(other == this)
            {
                return true;
            }

            ConnectFourMove rhs = (ConnectFourMove) other;
            return Objects.equals(column_, rhs.column_) && Objects.equals(player_, rhs.player_);
        }

        @Override
        public int hashCode()
        {
            return Objects.hash(column_, player_);
        }

        @Override
        public String toString()
        {
            return String.format("%s", player_);
        }
    }

    private static final class ConnectFourGameBoard
    {
        private final List<List<ConnectFourMove>> board_;
        private final int boardHeight_;

        public ConnectFourGameBoard(final int[][] board)
        {
            final int originalWidth = board.length;
            final int originalHeight = board[0].length;
            board_ = new ArrayList<List<ConnectFourMove>>(originalHeight);
            boardHeight_ = originalWidth;
            for(int i = 0; i < originalHeight; ++i)
            {
                // Initialze our arraylists
                board_.add(new ArrayList<ConnectFourMove>(originalWidth));
            }

            /*
             * The array passed in is in a very strange orientation.
             * Essentially, the moves are at the "ends" of the array.
             * Additionally, the array is tilted sideways (you access it
             * [y][x]). This makes for all sorts of a mess. We need to both flip
             * it and walk backwards (from the extends towards 0) if we want a
             * proper state representation.
             */
            for(int i = originalWidth - 1; i >= 0; --i)
            {
                for(int j = 0; j < originalHeight; ++j)
                {
                    final int value = board[i][j];
                    if(!Player.isValidPlayerValue(value))
                    {
                        continue;
                    }

                    final Player player = Player.playerFor(value);
                    final ConnectFourMove move = new ConnectFourMove(j, player);
                    applyMove(move);
                }
            }
        }

        public ConnectFourGameBoard(final ConnectFourGameBoard other)
        {
            boardHeight_ = other.boardHeight_;
            board_ = new ArrayList<List<ConnectFourMove>>(boardHeight_);
            for(final List<ConnectFourMove> column : other.board_)
            {
                board_.add(new ArrayList<ConnectFourMove>(column));
            }
        }

        // Assumes the column is valid
        public boolean isValidMove(final int column)
        {
            final List<ConnectFourMove> moves = board_.get(column);
            return moves.size() < boardHeight_;
        }

        /*
         * Doesn't check for validity of input. We can assume that since we're
         * determining things, the game hasn't been won yet. Therefore, we
         * simply only have to check to see if this move is the winning move.
         * 
         */
        public void applyMove(final ConnectFourMove move)
        {
            final int column = move.getColumn();
            final List<ConnectFourMove> moves = board_.get(column);
            moves.add(move);
        }

        public boolean checkWinning(final ConnectFourMove move)
        {
            if(move == null)
            {
                return false;
            }

            final int x = move.getColumn();
            final int y = board_.get(x).size();

            boolean isWinning = false;
            for(final Direction direction : Direction.ITERABLE_DIRECTIONS)
            {
                isWinning = isWinning
                        || checkWinningAllDirections(x, y, direction, move.getPlayer());
            }

            return isWinning;
        }

        private boolean checkWinningAllDirections(final int x, final int y,
                final Direction direction, final Player player)
        {
            final int consecutiveLeftSpaces = checkWinningCertainDirection(x + direction.getX(), y
                    + direction.getY(), direction, player, 0);
            final int consecutiveRightSpaces = checkWinningCertainDirection(x
                    + direction.opposite().getX(), y + direction.opposite().getY(),
                    direction.opposite(), player, 0);
            return (consecutiveLeftSpaces + consecutiveRightSpaces + 1) >= CONSECUTIVE_MOVES_TO_WIN;
        }

        private int checkWinningCertainDirection(final int x, final int y,
                final Direction direction, final Player player, final int consecutiveMoves)
        {
            /*
             * Bail early - we've found four in a row (assumes this function is
             * called not counting the originating space
             */
            if(consecutiveMoves == (CONSECUTIVE_MOVES_TO_WIN - 1))
            {
                return consecutiveMoves;
            }
            // If we're in the board and found a matching player, recurse
            if(x >= 0 && x < board_.size() && board_.get(x).size() > y && y >= 0
                    && board_.get(x).get(y).getPlayer() == player)
                return checkWinningCertainDirection(x + direction.getX(), y + direction.getY(),
                        direction, player, consecutiveMoves + 1);
            return consecutiveMoves;
        }

        /*
         * Generates all possible moves for the player. Returns an empty List if
         * no moves are found.
         */
        public List<ConnectFourMove> determineAvailableMovesFor(final Player player)
        {
            final List<ConnectFourMove> availableMoves = new ArrayList<ConnectFourMove>(
                    board_.size());
            for(int i = 0; i < board_.size(); ++i)
            {
                if(!isValidMove(i))
                {
                    continue;
                }

                final ConnectFourMove move = new ConnectFourMove(i, player);
                availableMoves.add(move);
            }
            return availableMoves;
        }

        @Override
        public String toString()
        {
            StringBuilder boardBuilder = new StringBuilder();
            for(int j = boardHeight_; j >= 0; --j)
            {
                for(final List<ConnectFourMove> moves : board_)
                {
                    if(moves.size() <= j)
                    {
                        boardBuilder.append("  0");
                        continue;
                    }

                    ConnectFourMove move = moves.get(j);
                    if(move.getPlayer() == Player.SELF)
                    {
                        boardBuilder.append("  1");
                    }
                    else if(move.getPlayer() == Player.ADVERSARY)
                    {
                        boardBuilder.append(" -1");
                    }
                    else
                    {
                        throw new RuntimeException("Invalid board state");
                    }
                }
                boardBuilder.append("\n");
            }

            String board = boardBuilder.toString();
            return board;
        }
    }

    private static Map<ConnectFourMove, ChanceOfWinning> runMonteCarlo(
            final ConnectFourGameBoard gameBoard)
    {
        final long startTime = System.currentTimeMillis();
        final List<ConnectFourMove> availableMoves = gameBoard
                .determineAvailableMovesFor(Player.SELF);
        final Map<ConnectFourMove, ChanceOfWinning> chancesOfWinning = new HashMap<ConnectFourMove, ChanceOfWinning>(
                availableMoves.size());
        for(final ConnectFourMove move : availableMoves)
        {
            chancesOfWinning.put(move, new ChanceOfWinning());
        }

        while(System.currentTimeMillis() - startTime < MAX_COMPUTATION_TIME_MILLISECONDS)
        {
            final int moveIndex = RGEN.nextInt(availableMoves.size());
            final ConnectFourMove move = availableMoves.get(moveIndex);
            final ChanceOfWinning chance = chancesOfWinning.get(move);
            /*
             * Fast-fail if the move is a winning one. An optimization would be
             * to move this out of here, but if we already have a first-move
             * win, then we don't really have anything to optimize to begin with
             */
            if(gameBoard.checkWinning(move))
            {
                chance.increase();
                continue;
            }
            // Each simulation gets their own copy of the board.
            final ConnectFourGameBoard copyOfBoard = new ConnectFourGameBoard(gameBoard);
            final Player winner = determineWinnerOfAnArbitraryGame(copyOfBoard, move);
            if(winner == Player.SELF)
            { // We could choose == SELF or != ADVERSARY here, depending on
              // whether or not we want to WIN (== SELF) or simply NOT LOSE (!=
              // ADVERSARY)
                chance.increase();
            }
            else
            {
                chance.decrease();
            }
        }

        return chancesOfWinning;
    }

    /*
     * Given a GameBoard, runs a Monte Carlo simulation of some number of games.
     * Using the outcomes from this, determines which move presents the highest
     * probability to win and returns it. Assumes that the provided GameBoard is
     * non-null, is valid, and has moves left to make
     */
    private static ConnectFourMove determineBestMove(final ConnectFourGameBoard gameBoard)
    {
        final Map<ConnectFourMove, ChanceOfWinning> chancesOfWinning = runMonteCarlo(gameBoard);
        ConnectFourMove bestMove = null;
        for(final Map.Entry<ConnectFourMove, ChanceOfWinning> chance : chancesOfWinning.entrySet())
        {
            if(bestMove == null)
            {
                bestMove = chance.getKey();
                continue;
            }
            ChanceOfWinning currentChance = chance.getValue();
            ChanceOfWinning bestChance = chancesOfWinning.get(bestMove);
            if(bestChance.chance() < currentChance.chance())
            {
                bestMove = chance.getKey();
            }
        }

        return bestMove;
    }

    /*
     * Small helper class for computing probabilities of winning based on number
     * of games played & won
     */
    private static final class ChanceOfWinning
    {
        private long totalGames_ = 0;
        private long totalWins_ = 0;

        public void increase()
        {
            ++totalGames_;
            ++totalWins_;
        }

        public void decrease()
        {
            ++totalGames_;
        }

        public double chance()
        {
            if(totalWins_ == 0)
            {
                return 0.0;
            }
            return totalWins_ / (double) totalGames_;
        }

        @Override
        public String toString()
        {
            return String.format("Won: %d, Total: %d, Chance: %.2f", totalWins_, totalGames_,
                    chance());
        }
    }

    /*
     * Plays out a game using the provided gameboard (mutates the internal
     * state). Returns a valid Player representing the Player that won this
     * particular game or null if no Player won.
     */
    private static Player determineWinnerOfAnArbitraryGame(final ConnectFourGameBoard gameBoard,
            final ConnectFourMove givenMove)
    {
        gameBoard.applyMove(givenMove);

        final Player nextPlayer = givenMove.getPlayer().getNextPlayer();
        final List<ConnectFourMove> availableMoves = gameBoard
                .determineAvailableMovesFor(nextPlayer);
        if(availableMoves.isEmpty())
        {
            // No moves left? No one won :(
            return null;
        }
        /*
         * Assume that a sufficiently intelligent opponent (and ourself) will
         * always pick a winning move if available
         */
        for(final ConnectFourMove move : availableMoves)
        {
            // Always take optimal move
            if(gameBoard.checkWinning(move))
            {
                return nextPlayer;
            }
        }

        /*
         * No winning moves? Any move is as good as any other one, so just pick
         * one and keep playing
         */
        final int moveIndex = RGEN.nextInt(availableMoves.size());
        final ConnectFourMove move = availableMoves.get(moveIndex);
        return determineWinnerOfAnArbitraryGame(gameBoard, move);
    }

    @Override
    public int makeMove(int[][] board)
    {
        // Assumes that a move can be made and that board is non-null
        final ConnectFourGameBoard gameBoard = new ConnectFourGameBoard(board);
        final ConnectFourMove move = determineBestMove(gameBoard);
        return move.getColumn();
    }

}