alphabetabackgammonagent.java.bak

人工智能_bachgammonagent

            this.openBracket(this.depthOfGameTree-depth + 1);
        }

        //Depth cutoff/win check
        if ((depth == 0)||(b.hasWon(otherPlayerNum))) {
            DataContainer rVal = new DataContainer(index, evaluation.boardScore(b,otherPlayerNum));
            if(this.PRINTTREE)
            {
                this.printValue(this.depthOfGameTree-depth + 1, "rVal:", rVal.getValue());
            }
            return rVal;
        }
        //if this is a chance node
        if (nodeType == MINCHANCENODE){
            int k = 1;
            BackgammonBoard newBoard;
            float v = 0f;
            float p = 1f;
            //generate chance paths
            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 and set the dice
                        newBoard = (BackgammonBoard)(b.clone());
                        newBoard.dc1 = i;
                        newBoard.dc2 = j;
                        v = v + minvalue(newBoard, alpha/p1, beta/p1, depth-1, MINNODE, k-1).getValue()*p1;
                        p = p - p1;
                        //prune condition based on nodes visited so far and lower bound for evaluation fn
                        // if no pruning occurs, expected value will be returned like in minimax
                        if ((p*evaluation.MIN_SCORE>=beta - v)){
                            if(this.PRINTTREE)
                                this.printValue(this.depthOfGameTree-depth + 1, "pruned" ,v - new Float(0.0001f));
                                return new DataContainer(k-1, (v - new Float(0.0001f)));
                        }
                        k++;
                    }
                }
                newBoard = (BackgammonBoard)(b.clone());
                newBoard.dc1 = i;
                newBoard.dc2 = i;
                v = v + minvalue(newBoard, alpha/p2, beta/p2, depth-1, MINNODE, k-1).getValue()*p2;
                p = p - p2;
                if ((p*evaluation.MIN_SCORE>=beta - v)&&(i!=Dice.DIE_MAX)){
                    if(this.PRINTTREE)
                        this.printValue(this.depthOfGameTree-depth + 1, "pruned" ,v - new Float(0.0001f));
                    return new DataContainer(k, (v - new Float(0.0001f)));
                }
                k++;
            }
            DataContainer rVal = new DataContainer(-1, v);
            if(this.PRINTTREE)
                this.printValue(this.depthOfGameTree-depth + 1, "a=" + formatFloat(alpha,3,3) + " b=" + formatFloat(beta,3,3) ,rVal.getValue());

            return rVal;
        }
        else {

            MoveSet ms= b.getValidMoves(this.otherPlayerNum);
            BackgammonBoard newBoard;
            DataContainer v = new DataContainer(-1, evaluation.MAX_SCORE);
            DataContainer tmp;
            for (int i=0; i<ms.getSize(); i++){
                newBoard = (BackgammonBoard)(b.clone());
                newBoard.applyMove(otherPlayerNum,ms.getMove(i));
                //pruning condition
                if (newBoard.hasWon(otherPlayerNum))
                    v.setTo(new DataContainer(i, evaluation.boardScore(b,otherPlayerNum)));
                else{
                    tmp = maxvalue(newBoard, alpha, beta, depth-1, MAXCHANCENODE, i);
                    if (tmp.getValue()<v.getValue())
                        v.setTo(i,tmp.getValue());
                    else
                        v.setTo(v.getIndex(),v.getValue());
                 }

                if (v.getValue()<=alpha) {
                    if(this.PRINTTREE)
                        this.printValue(this.depthOfGameTree-depth + 1, "a=" + formatFloat(alpha,3,3) + " b=" + formatFloat(beta,3,3), v.getValue());
                    return v;
                }
                beta = min(beta, v);
            }
            if(this.PRINTTREE)
                this.printValue(this.depthOfGameTree-depth + 1, "a=" + formatFloat(alpha,3,3) + " b=" + formatFloat(beta,3,3),v.getValue());
            return v;
        }
    }
    //compares DataContainer value and float returns bigger value
     public Float max(Float a, DataContainer b){
        if (a>b.getValue()) return a;
        else return b.getValue();
    }
    //compares DataContainer value and float returns smaller value
    public Float min(Float a, DataContainer b){
        if (a<b.getValue()) return a;
        else return b.getValue();
    }

//The functions below are only used for tree printing
    // for tree printing, needs to be called whenever we enter a node
    private void openBracket(int currentLevel)
    {
        if(currentLevel>this.highestLevelReached)
        {
            this.treeVisualisation[currentLevel]="";
            this.highestLevelReached=currentLevel;
        }
        if(this.treeVisualisation[currentLevel-1].length()-1>this.treeVisualisation[currentLevel].length())
        {
            int difference=this.treeVisualisation[currentLevel].length();
            for(int i=0;i<((this.treeVisualisation[currentLevel-1]).length()-difference-1);i++)
            {
                this.treeVisualisation[currentLevel]+=" ";
            }
        }
        this.treeVisualisation[currentLevel]+="(";

    }
    // for tree printing, needs to be called whenever we exit a node
    private void printValue(int currentLevel, String text,float value)
    {
        String toBeAdded=addSpaces(text, 30) + " rVal="+ formatFloat(value,2,1) + ")";
        int lengthToBeAdded=toBeAdded.length();
        if(((this.treeVisualisation[currentLevel].length()-lengthToBeAdded)>0)&&this.treeVisualisation[currentLevel].charAt(this.treeVisualisation[currentLevel].length()-1)!='(')
        {
                this.treeVisualisation[currentLevel]=this.treeVisualisation[currentLevel].substring(0,(this.treeVisualisation[currentLevel].length()-lengthToBeAdded));
        }
        this.treeVisualisation[currentLevel]+=toBeAdded;
        for(int i=1;i<currentLevel;i++)
        {
            int length=this.treeVisualisation[i].length();
            for(int y=0;y<(this.treeVisualisation[currentLevel].length()-length);y++)
                this.treeVisualisation[i]+=" ";
        }
    }

    //formats a string by making it "length" in length by adding spaces
    public String addSpaces(String s, int length){
        String rVal = new String();
        for (int i=s.length(); i<=length;i++) rVal = rVal + " ";
        return rVal + s;
    }
    //formats float by adding spaces on the right and left
    public String formatFloat(float f, int left, int right){
        String tmp = new String(Float.toString(f));
        int z = tmp.indexOf(".");
        String s = new String();
        for (int i = 0; i<=left; i++)
        {
            if (z-i>=0) s = tmp.substring(z-i,z-i+1) + s;
            else s = " " + s;
        }
        for (int i = 1; i<=right; i++)
        {
            if (z+i<tmp.length()) s = s + tmp.substring(z+i,z+i+1) ;
            else s = s + " ";

        }
        return s;
    }
    //Prints out the tree array
    private void visualiseTree()
    {
        System.out.println("\nHere is the decision tree:\n");
        for(int i=1;i<=this.highestLevelReached;i++)
        {
            System.out.println(this.treeVisualisation[i]);
        }
        System.out.println();
    }

public static void main(String[] args) {

	/* Start up a backgammon game using these two agents. */
	BackgammonAgent agent0 = new UserBackgammonAgent(0);
	BackgammonAgent agent1 = new AlphaBetaBackgammonAgent(1);
        //BackgammonAgent agent1 = new SimpleBackgammonAgent(1);

        BackgammonGame bg = new BackgammonGame(agent0,agent1,System.out);
        bg.playGame();
    }
}