AI ex for Wesley

PickNextMoveMatthewLongley.java

// Name:   Matthew Longley
// Due:    2012/04/18
// Course: COMP 3715-001
// Asg:    Game project

public class PickNextMoveMatthewLongley implements PickNextMove
{
    // Nested class - ChoiceTree
    // Description: Represents a search tree for the game
    // Members:
    // root - root of the tree
    // meStart - the initial state of the maximizing player
    // oppStart - the initial state of the minimizing player
    private class ChoiceTree
    {
        // Nested nested class - ChoiceTreeNode
        // Description: Represents a single node on the tree
        // Members:
        // boardState - the state of the board at this node
        // myState - the state of the maximizing player at this node
        // oppState - the state of the minimizing player at this node
        // moveMade - the last move made to reach this node
        // playedByMe - did the maximizing player's move produce this node?
        // isLeaf - is this node a leaf?
        // nextNodes - children of this node
        // nodeValue - value of this node
        // minMaxIndex - index of the optimal child-node from a minimax search
        private class ChoiceTreeNode
        {
            public Board boardState;
            public Player myState;
            public Player oppState;
            public Move moveMade;
            public boolean playedByMe;
            public boolean isLeaf;
            public ChoiceTreeNode[] nextNodes;
            public int nodeValue;
            public int minMaxIndex;

            public ChoiceTreeNode(Board b, Player m, Player o, Move mm, boolean pbm)
            {
                boardState = b;
                myState = m;
                oppState = o;
                moveMade = mm;
                playedByMe = pbm;
                nextNodes = new ChoiceTreeNode[(Board.allmoves).size()];
                minMaxIndex = -1;

                // If this node represents the end of the game, the node
                // value is 999 if the maximizing player wins, and -999
                // if the minimizing player wins.
                // Otherwise, the node value is the difference of the two
                // players' current scores.
                if(b.isFinal()){
                    if(m.finalScore() > o.finalScore())
                        nodeValue = 999;
                    else if(m.finalScore() == 70)
                        nodeValue = 999;
                    else
                        nodeValue = -999;
                } else {
                    nodeValue = m.getScore() - o.getScore();
                }
            }
        }

        private ChoiceTreeNode root;
        private Player meStart;
        private Player oppStart;

        // ChoiceTree constructor creates the root node
        public ChoiceTree(Board b, Player me, Player opp)
        {
            int i = 0;
            root = new ChoiceTreeNode(b, me, opp, null, false);
            meStart = me;
            oppStart = opp;
        }

        // population function - recursively populates the search tree #levels deep
        private void choiceTreePopulate(ChoiceTreeNode node, int levels)
        {
            int i;

            node.isLeaf = true;

            if(levels == 0){
                return;
            }

            for(i = 0; i < (Board.allmoves).size(); i++){
                if((node.boardState).isValidMove((Board.allmoves).get(i)) && !((node.boardState).isFinal())){
                    if(node.playedByMe){
                        (node.nextNodes)[i] = new ChoiceTreeNode((node.boardState).nextMove((Board.allmoves).get(i)),
                                                                 node.myState,
                                                                 (node.oppState).addScore((node.boardState).nextScore((Board.allmoves).get(i))),
                                                                 (Board.allmoves).get(i),
                                                                 false);
                    } else {
                        (node.nextNodes)[i] = new ChoiceTreeNode((node.boardState).nextMove((Board.allmoves).get(i)),
                                                                 (node.myState).addScore((node.boardState).nextScore((Board.allmoves).get(i))),
                                                                 node.oppState,
                                                                 (Board.allmoves).get(i),
                                                                 true);
                    }
                    node.isLeaf = false;
                } else {
                    (node.nextNodes)[i] = null;
                }
            }

            for(i = 0; i < (node.nextNodes).length; i++)
                if((node.nextNodes)[i] != null)
                    choiceTreePopulate((node.nextNodes)[i], levels - 1);
        }

        // Begins the tree population routine
        public void choiceTreeGrow(int levels)
        {
            choiceTreePopulate(root, levels);
        }

        // Performs a maximization on the given node
        private int choiceTreeMaxNode(ChoiceTreeNode node)
        {
            int i, max = -999, curr, nextIndex = -1;

            if(node.isLeaf)
                return node.nodeValue;

            for(i = 0; i < (node.nextNodes).length; i++){
                if((node.nextNodes)[i] != null){
                    curr = choiceTreeMinNode((node.nextNodes)[i]);
                    if(max < curr){
                        max = curr;
                        nextIndex = i;
                    }
                }
            }

            node.minMaxIndex = nextIndex;
            return max;
        }

        // Performs a minimization on the given node
        private int choiceTreeMinNode(ChoiceTreeNode node)
        {
            int i, min = 999, curr, nextIndex = -1;

            if(node.isLeaf)
                return node.nodeValue;

            for(i = 0; i < (node.nextNodes).length; i++){
                if((node.nextNodes)[i] != null){
                    curr = choiceTreeMaxNode((node.nextNodes)[i]);
                    if(min > curr){
                        min = curr;
                        nextIndex = i;
                    }
                }
            }

            node.minMaxIndex = nextIndex;
            return min;
        }

        // Begins minimax routine
        public Move choiceTreeSearch()
        {
            int i;
            choiceTreeMaxNode(root);
            if(root.minMaxIndex == -1)
                return null;
            return (Board.allmoves).get(root.minMaxIndex);
        }

    }

    // Method nextMove required by interface PickNextMove
    public Move nextMove(Board b, Player me, Player opp, MyTimer t)
    {
        int fullColumns = 0, i;
        Move rMove = null;

        // Because of how important negative scores are to the final
        // scoring, a greedy approach is prioritized when the player
        // does not have the minimum 3 to not have his score divided
        if(me.getNegScoreCount() < 3)
            rMove = negPriority(b);
        if(rMove != null)
            return rMove;

        // After the required number of negative scores have been
        // acquired, a minimax strategy is utilized to find the
        // best move. Since the search space decreases as columns
        // fill up, the depth to which the search tree is initially
        // populated increases as columns are filled.
        for(i = 0; i < ((Board.allmoves).size() / 2); i++)
            if(b.getCoin(i, 7) != ' ')
                fullColumns++;
        ChoiceTree cTree = new ChoiceTree(b, me, opp);
        cTree.choiceTreeGrow(4 + (fullColumns / 2));
        rMove = cTree.choiceTreeSearch();
        if(rMove != null)
            return rMove;

        // Finally, if the minimax search is inconclusive, a simple
        // greedy search is attempted.
        return finalGreedySearch(b);
    }

    // negPriority implements a simple greedy strategy for acquiring the
    // requisite negative scores. Black is slightly prioritized over white,
    // but the color with the most remaining coins is chosen.
    private Move negPriority(Board b)
    {
        int i;
        char colorToPlay;

        if(b.getBlackCoinLeft() < b.getWhiteCoinLeft())
            colorToPlay = 'w';
        else
            colorToPlay = 'b';

        for(i = 0; i < (Board.allmoves).size(); i++)
            if(b.nextScore((Board.allmoves).get(i)) == -5 && ((Board.allmoves).get(i)).getCoin() == colorToPlay)
                return (Board.allmoves).get(i);

        return null;
    }

    // finalGreedySearch performs a final greedy search of possible moves, and is intended
    // to be used when the minimax search is inconclusive. This method will play whatever
    // color has the most tokens remaining.
    private Move finalGreedySearch(Board b)
    {
        int max = -999, curr = -999, rIndex = 0, i;
        char colorToPlay;

        if(b.getBlackCoinLeft() >= b.getWhiteCoinLeft())
            colorToPlay = 'b';
        else
            colorToPlay = 'w';

        for(i = 0; i < (Board.allmoves).size(); i++){
            if((b.isValidMove((Board.allmoves).get(i)))  && ((Board.allmoves).get(i)).getCoin() == colorToPlay){
                curr = b.nextScore((Board.allmoves).get(i));
                if(curr > max){
                    max = curr;
                    rIndex = i;
                }
            }
        }

        return (Board.allmoves).get(rIndex);
    }
}