alphabetabackgammonagent.java.bak

人工智能_bachgammonagent

/*
 * AlphaBetaBackgammonAgent.java
 * CMPT 310 - Assignment 2 - Part 2
 * The following file represents a program written in Java
 *  programming language. The file describes a class that is used to
 *  perform alphabeta search for backgammon game.
 */

//package bkgm;



import org.omg.CORBA.DATA_CONVERSION;
import org.w3c.dom.Text;
public class AlphaBetaBackgammonAgent extends BackgammonAgent {
    private Evaluation evaluation;
    private int otherPlayerNum; //stores the opponent number
    final int depthOfGameTree=3; //how deep down the rabbit hole do we go?, 3 for 2-ply
    private int highestLevelReached=0; //highest level of the tree reached so far for tree printing purposes
    String[] treeVisualisation;//to print out the tree
    final boolean PRINTTREE=false;//decide whether to print the tree
    final int MAXNODE = 0;
    final int MINCHANCENODE = 1;
    final int MINNODE = 2;
    final int MAXCHANCENODE = 3;
    final Float p1 = (new Float(2.0F/(new Float(Dice.DIE_MAX*Dice.DIE_MAX))));//for rolls like i,j, where i!=j
    final Float p2 = (new Float(1.0F/(new Float(Dice.DIE_MAX*Dice.DIE_MAX))));//for rolls with i=j
    private int currentDepth = 0;


    public AlphaBetaBackgammonAgent(int my_player_num) {
	super(my_player_num);
	evaluation = new NaiveEvaluation();
        otherPlayerNum = 1 - player_num; //set player number
    }

    public AlphaBetaBackgammonAgent(int my_player_num, Evaluation e) {
	super(my_player_num);
	evaluation = e;
        otherPlayerNum = 1 - player_num; //set player number
    }

    public Move chooseMove(BackgammonBoard b) {
        //required for tree graphing: highest level reached in the tree(lowest)
        highestLevelReached = 0;
        //initialize tree string
        treeVisualisation = new String[depthOfGameTree+2];
        for (int i=0; i<depthOfGameTree+2; i++)
            treeVisualisation[i] = new String();
        //receive the set of valid moves, get alphabeta to give index of the correct move to make
        MoveSet ms= b.getValidMoves(player_num);
        return ms.getMove(alphabeta(b, depthOfGameTree));
    }

    private int alphabeta(BackgammonBoard b, int depth){
        //Store return values(index and max) in DataContainer
        DataContainer d = new DataContainer(maxvalue(b, new Float(0), new Float(15), depth, MAXNODE, -1));
        System.out.println("maxVaue: " + d.getValue());
        //Display tree
        if(this.PRINTTREE)
            this.visualiseTree();
        System.out.println("valid moves were:");
        for (int i=0; i<(b.getValidMoves(player_num).getSize()); i++){
            System.out.println(b.getValidMoves(player_num).getMove(i));
        }
        System.out.println("chosen move n=" + d.getIndex());

        return d.getIndex();
    }

// maxvalue function: returns max value.
    private DataContainer maxvalue(BackgammonBoard b, Float alpha, Float beta, int depth, int nodeType, int index) {
        //Sanity check
        if (nodeType!=MAXNODE&&nodeType!=MAXCHANCENODE){
            System.err.println("Wrong type of node passed to maxValue");
            System.exit(1);
        }

        //Tree visualization
        if(this.PRINTTREE)
            this.openBracket(this.depthOfGameTree-depth + 1);

        //Reached Max depth or cut off due to a win here
        if ((depth == 0)||(b.hasWon(player_num))){
            DataContainer rVal = new DataContainer(index, evaluation.boardScore(b,player_num));
            if(this.PRINTTREE)
            {
                this.printValue(this.depthOfGameTree-depth + 1, "rVal" ,rVal.getValue());
            }

            return rVal;
        }
        //if called at chance node, generate possible dice rolls, search through them
        if (nodeType ==MAXCHANCENODE){
            int k = 1;
            float v = 0f;
            float p = 1f;
            BackgammonBoard newBoard;
            //generating dice rolls
            for (int i=1; i<Dice.DIE_MAX+1; i++){
                for (int j=i; j<Dice.DIE_MAX+1; j++){
                    if (i!=j) {
                        //clone the board
                        newBoard = (BackgammonBoard)(b.clone());
                        //set dice
                        newBoard.dc1 = i;
                        newBoard.dc2 = j;
                        v = v + maxvalue(newBoard, alpha/p1, beta/p1, depth-1, MAXNODE, k-1).getValue()*p1;
                        p = p - p1;
                        //prune condition: based on upperbound of the evaluation function and nodes visited so far
                        // if no pruning occurs, expected value will be returned like in minimax
                        if ((p*evaluation.MAX_SCORE<=alpha - v)){
                            if(this.PRINTTREE)
                                this.printValue(this.depthOfGameTree-depth + 1, "a=" + formatFloat(alpha,3,3) + " b=" + formatFloat(beta,3,3),(v + 0.0001f));
                            return new DataContainer(-1, (v + 0.0001f));
                            }
                        k++;
                    }
                }
                newBoard = (BackgammonBoard)(b.clone());
                newBoard.dc1 = i;
                newBoard.dc2 = i;
                v = v + maxvalue(newBoard, alpha/p2, beta/p2, depth-1, MAXNODE, k-1).getValue()*p2;
                p = p - p2;
                //prune condition: based on upperbound of the evaluation function and nodes visited so far
                // if no pruning occurs, expected value will be returned like in minimax
                if ((p*evaluation.MAX_SCORE<=alpha - v)&&!(i==Dice.DIE_MAX)){
                    if(this.PRINTTREE)
                        this.printValue(this.depthOfGameTree-depth + 1, "a=" + Float.toString(alpha) + " b=" + Float.toString(beta) ,v + new Float(0.0001f));
                    return new DataContainer(-1, (v + new Float(0.0001f)));
                }
                k++;
            }
            DataContainer rVal = new DataContainer(-1, v);
            if(this.PRINTTREE)
                this.printValue(this.depthOfGameTree-depth + 1, "a=" + Float.toString(alpha) + " b=" + Float.toString(beta) ,rVal.getValue());

            return rVal;
        }
        //This is a Maxnode
        else {
            MoveSet ms= b.getValidMoves(this.player_num);
            DataContainer v = new DataContainer(-1, evaluation.MIN_SCORE);
            BackgammonBoard newBoard;
            DataContainer data;
            DataContainer tmp;
            for (int i=0; i<ms.getSize(); i++){
                //for every move generate a board
                newBoard = (BackgammonBoard)(b.clone());
                //and apply the move
                newBoard.applyMove(player_num,ms.getMove(i));
                //if game over we keep looking for better way to win the game
                if (newBoard.hasWon(player_num))
                    v.setTo(new DataContainer(i, evaluation.boardScore(b,player_num)));
                else{
                    tmp = minvalue(newBoard, alpha, beta, depth-1, MINCHANCENODE, i);
                    if (tmp.getValue()>v.getValue())
                        v.setTo(i,tmp.getValue());
                    else
                        v.setTo(v.getIndex(),v.getValue());
                }
                //prune condition
                if (v.getValue()>=beta) {
                    v.setTo(i, v.getValue());
                    if(this.PRINTTREE)
                        this.printValue(this.depthOfGameTree-depth + 1, "a=" + formatFloat(alpha,3,3) + " b=" + formatFloat(beta,3,3), v.getValue());
                    return v;
                }
                alpha = max(alpha, v);
            }
            if(this.PRINTTREE)
                this.printValue(this.depthOfGameTree-depth + 1, "a=" + formatFloat(alpha,3,3) + " b=" + formatFloat(beta,3,3),v.getValue());
            return v;
        }
    }
    private DataContainer minvalue(BackgammonBoard b, Float alpha, Float beta, int depth, int nodeType, int index) {
        //Sanity check
        if (nodeType!=MINCHANCENODE&&nodeType!=MINNODE){
            System.err.println("Wrong type of node passed to minValue");
            System.exit(1);
        }

        //Tree visualization
        if(this.PRINTTREE)
        {