Question : is there a best move in alpha-beta ?

[Paul JF]

In the following alpha-beta code :

Code: Select all

int alphaBeta( int alpha, int beta, int depthleft ) {
   if( depthleft == 0 ) return quiesce( alpha, beta );
   for ( all moves)  {
      score = -alphaBeta( -beta, -alpha, depthleft - 1 );
      if( score >= beta )
         return beta;   //  fail hard beta-cutoff
      if( score > alpha )
         alpha = score; // alpha acts like max in MiniMax
   }
   return alpha;
}

The move is the best move found so far if

Code: Select all

score > alpha

. But if this condition is always false on a given position, does this means there is no best move ? And how to know the best move if this is the case (because obviously every position has a best move) ?

[JVMerlino]

It means that there is no best move given the [alpha, beta] window. In other words, every move is being scored as "no better than alpha", so you need to search with a wider window. Most engines do this: https://www.chessprogramming.org/Aspiration_Windows

But if you are searching a full-width window (eg [-INFINITY, INFINITY]) and no move is better than alpha, then you have a bug.

[Paul JF]

I thought Aspiration Window was used as an iterative deepening enhancement. How to use it in alpha-beta ?
I've also read on CPW that Aspiration Window and PVS are not friendly together. I use a PVS algorithm and use a triangular PV-table, but sometimes some moves in the PV are 0 because there was no best move according to the score > alpha condition. How can I fix that ?

[JVMerlino]

I thought Aspiration Window was used as an iterative deepening enhancement. How to use it in alpha-beta ?
I've also read on CPW that Aspiration Window and PVS are not friendly together. I use a PVS algorithm and use a triangular PV-table, but sometimes some moves in the PV are 0 because there was no best move according to the score > alpha condition. How can I fix that ?

As far as I'm aware, all strong engines use PVS and Aspiration Windows (AW) together, although AW implementations vary greatly (how big is the initial window, how quickly does it widen, how many windows before you fall back to a full-width search, etc). The strength gain from improving time-to-depth far outweighs the potential instability. You just need to be a bit careful on how you handle the widening of the window, as CPW suggests.

So, since it seems you're only using full-width windows at the root, you'll have to do some debugging to see why none of them are improving alpha.

[Paul JF]

So, since it seems you're only using full-width windows at the root, you'll have to do some debugging to see why none of them are improving alpha.

Thank you, but how can I debug this ?

[JVMerlino]

So, since it seems you're only using full-width windows at the root, you'll have to do some debugging to see why none of them are improving alpha.

Thank you, but how can I debug this ?

Heh, that's always the tough question. Debugging problems in the search can often be very challenging and time-consuming. A shortcut might be to post your code somewhere, and one of us might be able to spot the problem rather quickly.

A lot will depend on what language and IDE you are using. One generic method would be to create a log file that, in whatever way makes sense to you, prints out the entire search tree as it is traversed by the search - each move for each depth, with the alpha-beta window and return value at each node. Or you could use an integrated debugger to just step through the code, making sure that alpha and beta are correct at every node, and that your evaluation is returning reasonable values for the leaf nodes.

[Paul JF]

Ok thanks, I will try to fix this.

A shortcut might be to post your code somewhere, and one of us might be able to spot the problem rather quickly.

Here is my search code in JavaScript (I've got roughly the same in Python if needed): https://github.com/PaulJeFi/reglisse-ch ... 1839-L2047
If someone spot an evident problem, he is welcome.

[JVMerlino]

Ok thanks, I will try to fix this.

A shortcut might be to post your code somewhere, and one of us might be able to spot the problem rather quickly.

Here is my search code in JavaScript (I've got roughly the same in Python if needed): https://github.com/PaulJeFi/reglisse-ch ... 1839-L2047
If someone spot an evident problem, he is welcome.

This looks a little suspicious. The comment says "depth = 1", but the code is "depth <= 1".

Code: Select all

        // Futility pruning : at pre fontier nodes (depth = 1), if the score
        // plus a bishop value is not better than alpha, simply return alpha.
        if ((depth <= 1) && (!(isCheck  || storePV)) &&

[KhepriChess]

So, since it seems you're only using full-width windows at the root, you'll have to do some debugging to see why none of them are improving alpha.

Thank you, but how can I debug this ?

Very slowly and painfully. Sometimes you just need to step slowly through the code. Use either the IDE's debugger or, since it's Javascript, use the browser's debugger.

[Paul JF]

This looks a little suspicious. The comment says "depth = 1", but the code is "depth <= 1".

Thank you so much !
It's because with LMR, depth can be a float, and as if depth <= 0 is checked before this condition, depth <= 1 makes sure the node is a pre-frontier node, even if depth is a float.
So this is bad with this line :

Code: Select all

var pvNextIndex = pvIndex + depth;

so I created a realdepth variable fixing this.

This fix many (most) of the 0-moves in the PV, but there are still some bugs in it.