Alpha-Beta-Pruning. Weird results

[Henk]

A win in zero moves returns in my chess program the value MATE_SCORE - plyCount + 1. That is when it captures the king,

[Daniel Anulliero]

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

Yes of course I would say mate -ply (where ply = 1 if it's a win in one move)

[hgm]

It depends on how you define a 'win'. I suppose in Chess you don't actually have to capture the King, and you have already won when the opponent leaves his King in check (blitz rules). Fairy-Max returns a +INF score for such positions. Illegal moves thus get a -INF score after negamaxing, and when all moves (including null move) are illegal the node returns -INF+1 (because of the delayed-loss bonus) for mated-in-0. Mate-in-1 then gets an INF-1 score, etc.

[AlvaroBegue]

I should point out that using Integer.MIN_VALUE has another problem: If you compute -Integer.MIN_VALUE you'll get Integer.MIN_VALUE again!!!

Instead of MIN_VALUE I normally use a constant like 1000000000 or 8000 (I use 14 bits to represent a score in the hash table).

[Joost Buijs]

It depends on how you define a 'win'. I suppose in Chess you don't actually have to capture the King, and you have already won when the opponent leaves his King in check (blitz rules). Fairy-Max returns a +INF score for such positions. Illegal moves thus get a -INF score after negamaxing, and when all moves (including null move) are illegal the node returns -INF+1 (because of the delayed-loss bonus) for mated-in-0. Mate-in-1 then gets an INF-1 score, etc.

The move generator I use generates legal moves only.
When the side to move has no moves at all and his king is in check I return -valueMate + ply (ply == 0 at the root).
When his king is not in check I return valueDraw (which is zero in my case because I don't use contempt).

[Joost Buijs]

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

Yes of course I would say mate -ply (where ply = 1 if it's a win in one move)

You can also have a win in one move somewhere deep in the tree, of course I understand you mean a win in one move relative to the root.

[bob]

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

Depends on how you implement it. For me, it would be -(MATE - 1, since I got to ply=1 and had no legal moves.

[Sven]

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;

[...]

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

Hi Robin,

apart from the other comments, especially regarding mate scoring, I see some small issues with your code, not sure whether these are causing trouble but you should check these at least:

- You are using fail-soft alpha-beta. This algorithm works best if you do the recursive call like this:

Code: Select all

int value =-alphabeta(board, -beta, -Math.max(alpha,bestValue), depth - 1);

You do almost the same but not exactly. First thing is, the recursive call for the first move gets -alpha instead of -max(...) as an argument. Second, you use max(alpha,value) instead of max(alpha,bestValue) which is not always the same.

- There is an additional boolean parameter for your alphabeta() function which is not part of the signature, so probably the code above is not the original code.

As far as mate scoring is concerned, there are several valid solutions around. One is the "delayed loss bonus" preferred by HGM. Probably most popular is to simply return -(MATE_SCORE - distanceToRoot) at a node where the side to move is checkmated. Bob and few others use a variant of this which is based on a slightly different ply counting (root is "ply 1" instead of "ply 0"). If you don't handle mate scoring properly then your program will almost never play the move that leads to the shortest mate, which effectively means it will not be able to win even in a position with a forced mate in N plies. In your implementation above you always return the same mate score so that your program does not know that a mate in 1 ply is better than a mate in 3 plies.

[Henk]

Maybe first implement minimax. If that works and code is kept similar to alpha beta search then probably problem is somehow dependent on alpha beta parameters if your test was right.