Alpha-Beta-Pruning. Weird results

[Peng1993]

Hey guys,
I implemented alpha-beta pruning but sometimes I get weird results. When (for example) black is winning in 2 moves and the evaluation says that it is winning it doesn't actually make the move for some reason.

Here is the implementation I am using:

Code: Select all

  public  int alphabeta(final CheckerBoard board,int alpha,int beta,int depth){
      nodeCount++;
        

        if(depth==0 || board.isTerminalState()){
           return board.color*GameEvaluation.evaluate(board);
        }


    ArrayList<Move>sucessors =MGenerator.getMoves&#40;board&#41;;
        int bestValue =Integer.MIN_VALUE;
        for&#40;Move  move &#58; sucessors&#41;&#123;
            board.makeMove&#40;move&#41;;
            int value =-alphabeta&#40;board, -beta, -alpha, depth - 1, true&#41;;
            board.undoMove&#40;move&#41;;
            if&#40;value>bestValue&#41;&#123;
                bestValue =value;
            &#125;
            alpha =Math.max&#40;alpha,value&#41;;
            if&#40;alpha>=beta&#41;&#123;
                break;
            &#125;
        &#125;

        return bestValue;
    &#125;

and the following code to start the search:

Code: Select all

 public int findBestMove(int depth){
        ArrayList<Move> sucessors =MGenerator.getMoves&#40;board&#41;;
        int max = Integer.MIN_VALUE;
        for&#40;Move m &#58; sucessors&#41;&#123;
            board.makeMove&#40;m&#41;;
            int value =-alphabeta&#40;board, -1000000, 1000000, depth&#41;;
            board.undoMove&#40;m&#41;;
            if&#40;value>max&#41;&#123;
                max=value;
                bestMove=m;
            &#125;
        &#125;

        board.makeMove&#40;bestMove&#41;;
        return max;
    &#125;

Is there anything wrong with my implementation. I am puzzled by the weird results I am getting.

[syzygy]

I implemented alpha-beta pruning but sometimes I get weird results. When (for example) black is winning in 2 moves and the evaluation says that it is winning it doesn't actually make the move for some reason.

I can't see what is happening, but maybe there are many winning moves and the search picks one that is winning but does not bring the win closer?

For example in KQvK any move that does not lose the queen (or causes stalemate) is winning, but randomly playing winning moves will likely not win the game.

[Peng1993]

I implemented alpha-beta pruning but sometimes I get weird results. When (for example) black is winning in 2 moves and the evaluation says that it is winning it doesn't actually make the move for some reason.

I can't see what is happening, but maybe there are many winning moves and the search picks one that is winning but does not bring the win closer?

For example in KQvK any move that does not lose the queen (or causes stalemate) is winning, but randomly playing winning moves will likely not win the game.

Maybe. But there isn't anything specifically wrong with my implementation ?

[AlvaroBegue]

Does `GameEvaluation.evaluate(board)' return the correct values for terminal states? The way I would normally write the code, it would look something like this:

Code: Select all

  // ...

  int final_result;
  if (board.isTerminalState(final_result))
    return board.color * final_result;
  
  if &#40;depth <= 0&#41;
    return board.color * GameEvaluation.evaluate&#40;board&#41;;

  // ...

If `GameEvaluation.evaluate(board)' is returning some heuristic value even for terminal positions, your code may prefer a larger material advantage than actually winning, e.g.

[bob]

Hey guys,
I implemented alpha-beta pruning but sometimes I get weird results. When (for example) black is winning in 2 moves and the evaluation says that it is winning it doesn't actually make the move for some reason.

Here is the implementation I am using:

Code: Select all

  public  int alphabeta(final CheckerBoard board,int alpha,int beta,int depth){
      nodeCount++;
        

        if(depth==0 || board.isTerminalState()){
           return board.color*GameEvaluation.evaluate(board);
        }


    ArrayList<Move>sucessors =MGenerator.getMoves&#40;board&#41;;
        int bestValue =Integer.MIN_VALUE;
        for&#40;Move  move &#58; sucessors&#41;&#123;
            board.makeMove&#40;move&#41;;
            int value =-alphabeta&#40;board, -beta, -alpha, depth - 1, true&#41;;
            board.undoMove&#40;move&#41;;
            if&#40;value>bestValue&#41;&#123;
                bestValue =value;
            &#125;
            alpha =Math.max&#40;alpha,value&#41;;
            if&#40;alpha>=beta&#41;&#123;
                break;
            &#125;
        &#125;

        return bestValue;
    &#125;

and the following code to start the search:

Code: Select all

 public int findBestMove(int depth){
        ArrayList<Move> sucessors =MGenerator.getMoves&#40;board&#41;;
        int max = Integer.MIN_VALUE;
        for&#40;Move m &#58; sucessors&#41;&#123;
            board.makeMove&#40;m&#41;;
            int value =-alphabeta&#40;board, -1000000, 1000000, depth&#41;;
            board.undoMove&#40;m&#41;;
            if&#40;value>max&#41;&#123;
                max=value;
                bestMove=m;
            &#125;
        &#125;

        board.makeMove&#40;bestMove&#41;;
        return max;
    &#125;

Is there anything wrong with my implementation. I am puzzled by the weird results I am getting.

I don't see all the details. Do you return a mate score that is something like "MATE - ply" so that deeper mates get worse scores than shallow mates???

[Edsel Apostol]

Code: Select all

             if([b]value>max[/b]){
                max=value; 
                bestMove=m; 
            }

That code is problematic along with the return value of Integer.MIN_VALUE when there is a mate found deeper in the tree, lets say it is going to be mated in the next ply. The Integer.MIN_VALUE will be propagated up in the tree and will have this statement:

if (Integer.MIN_VALUE > Integer.MIN_VALUE)

which will not be true and therefore bestMove will not be updated.

[hgm]

When (for example) black is winning in 2 moves and the evaluation says that it is winning it doesn't actually make the move for some reason.

It would be more enlightening if you could show an example of this.

[Henk]

What's the value the search returns when win in zero moves ?

[Daniel Anulliero]

What's the value the search returns when win in zero moves ?

Lol
No win in zero moves in search tree
Win in zero moves means the user played his moves and checkmated the engine
In the search tree it may have a win in one move and the value returned is MATE - 1

[Joost Buijs]

In my search tree a win in one move returns mateValue - ply which is something entirely different.