Alpha beta pruning [closed]

Question

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.

Closed 9 years ago.

Im building a Reversi game with alpha beta, and i need your help in the alpha beta. Problem is that the computer keep choosing one of the squares that are in the low side of the board. I have a List of possible moves for the computer (as you can see in the code below), meaning the computer is almost always choosing the last or one of the last moves in that List, even if its not the best move. My evaluation function is simple: black pieces minus white pieces. BTW: it works fine in depth=1, but i need it to work in depth=3.

public int AlphaBeta(int depth,int turn,TreeNode root,int alpha,int beta)
{
    if(depth==0)
        return evaluationFunc(turn,turns,root.board,root);
    else
    {
        buildSons(turn,root);
        TreeNode head =  generateList(root.sons);
        return executeCheckTheSons2(depth,turn,head,alpha,beta);
    }
}

public int executeCheckTheSons2(int depth,int turn,TreeNode head,int alpha,int beta)
    {
        int score;
        if(turn==1)
        {
            while(head!=null)
            {
                head.board=simulateTheMove(head.board,head.getX(),head.getY(),turn);
                score=AlphaBeta(depth-1,turn*-1,head,alpha,beta);
                if(score > alpha)
                {
                    alpha=score;
                    setMove(head);
                }
                if(alpha >= beta)
                    return alpha;
                head=head.next;
            }
                return alpha;
        }
        else
        {
            while(head!=null)
            {
                head.board=simulateTheMove(head.board,head.getX(),head.getY(),turn);
                score=AlphaBeta(depth-1,turn*-1,head,alpha,beta);
                if(score<beta)
                {
                    beta=score;
                    setMove(head);
                }
                if(alpha >= beta)
                    return beta;
                head=head.next;
            }
            return beta;
        }       
    }

    public void setMove(TreeNode root)
    {
        while(root.father.father!=null)
            root=root.father;
        pnt.setX(root.getX());
        pnt.setY(root.getY());
    }

Answer 1

I think the error is in the setMove function. I suppose this is the function which sets the final coordinates to set the piece. At the moment you are calling this for every depth in the tree even if the result from this branch is not the best possible result globally.

For example imagine you are evaulating the last possible move. You start with depth=3 and then you call yourself recursively for depth=2. When you enter in executeCheckTheSons2 now you will start with a score of 0 and evaluate the possible moves. One of these moves will probably give you a score greater than 0, so you will call setMove(head) and set the coordinates to move to to the last possible move. When you return now from the function you record the score for this depth in score, but globally seen it's not a great move. However the last call for setMove is still active and you don't change it afterwards.

You should move this call out of executeCheckTheSons2 and move it in some upper layer function. Alternatively record the x and y coordinates in a local variable of the executeCheckTheSons2 function and then call setMove before returning from the function instead.

If this question is useful for you, please accept this as an answer.