Collecting the principal Variation

[hgm]

But this is 2 out of 20 positions where there was as problem. The others are fine.

Even if there is only one in a million positions that has a problem, you still have a bug...

[Fguy64]

But this is 2 out of 20 positions where there was as problem. The others are fine.

Even if there is only one in a million positions that has a problem, you still have a bug...

well yeah, a problem is a problem, I just figured 2/20 + my descriptions might have pointed to the cause. My guess is it's a common oversight/omission, cause implementing ID with PV first is hardly the most complicated thing I've done with this program. There's only so many ways to screw it up. I'll find it I'm sure.

[hgm]

What always helps for me with errors like this is print out the complete list of moves and their scores (and bestScore, alpha, beta) in a specified node. (Selecting the node by comparing the path that leads to it with a path I specify.) That allows you to zoom in on the error very rapidly: Identify a mov with a wrong score in one node (starting at the root), and then extend the specified path with that move, and run the search again. In the daughter node you should then again find at least one move with a wrong score (either a cut muve with too high a score, or move which you think should have been a cut move, but in fact failed low.

That way you either stumple on a propagtion error (the returned score of the node was not equal to that of the best move, possibly because the latter was not searched at all), or an evaluation error.

If you don't know the correct scores beforehand (in a mate-in-N situation you probably do), you can still apply this technique by comparing two versions that gave different root score. By comparing the move lists, there should always be one move with contradictory bounds, and if you follow that move you step towards the error that generated the difference.

[Fguy64]

Thanks HG.

I found the problem. The code for searching PV first appears at the top of my alphaBeta method. The problem was that I forgot to increment my move counter after searching the PV move. As a result, for a node where there was only one legal move, that move naturally became the PV move, but after it was searched alphaBeta was returning a mate or stalemate score when it was neither, because I forgot to increment the move counter.

[Fguy64]

That would do it. To save some time, you might not want to copy every time upto maxPly, but hide a marker indicating the end of the PV, and stop there:

Code: Select all

if( eval > alpha ) { 
    alpha = eval; 
    PV[ply][ply] = m; 
    int j=ply+1; 
    while( PV[ply][j] = PV[ply+1][j] ) j++; 
} 

This assuming the PV ends with m == 0, which you put there on stand pat (when you have no best move).

OK, I haven't quite dealt with the stand pat thing yet, right now I am dealing strictly with a fixed depth search.

Anyways, just to expand on my conclusion about alpha updates, it seems we have do do the same thing for beta cutoffs also? So I came up with the following...

Code: Select all

if( eval >= beta ) {
    PV[ply][ply] = m;
    for&#40; int j=ply+1; j<=maxPly; j++ ) &#123; 
        PV&#91;ply&#93;&#91;j&#93; = PV&#91;ply+1&#93;&#91;j&#93;; 
    &#125;
    return beta;
&#125;
if&#40; eval > alpha ) &#123; 
    alpha = eval; 
    PV&#91;ply&#93;&#91;ply&#93; = m; 
    for&#40; int j=ply+1; j<=maxPly; j++ ) &#123; 
        PV&#91;ply&#93;&#91;j&#93; = PV&#91;ply+1&#93;&#91;j&#93;; 
    &#125; 
&#125;

[Desperado]

hi Fred,

Code: Select all

if( eval > alpha ) { 
    alpha = eval; 
    PV[ply][ply] = m; 
    for&#40; int j=ply+1; j<=maxPly; j++ ) &#123; 
        PV&#91;ply&#93;&#91;j&#93; = PV&#91;ply+1&#93;&#91;j&#93;; 
    &#125;

if i remember correctly, i saw this approach the first time in the famous
MiniMax program.

The problem with collecting the pv can be.

Code: Select all

ie: ply = 3  -> ply+1 = 4

         MoveNumber Ply
...

move        1        3
move        1        4  (PV[ply+1][j],so to say ex: Qf2)
move        2        3
move       noMove    4

if you now return to ply 3 and value>alpha you will collect ie Qf2
as pv move, which of course may not be a correct continuation.

noMove means, if you exit the search for example on stalemate,mate
Standpat or any other selective method where you dont collect a move.

if this is your problem,(that was mine short time ago), then
make sure before you enter ie ply 4 to clean the slot [ply+1][j]=noMove.
General spoken, clean the slot of the next ply before entering next ply.

If you dont do this, the code you use only works if on next ply a
valid move is written to the slot [ply+1][j], otherwise the content
of the slot is random.

I saw this "bug" in some other programs, but they didnt care.

this may lead to the following (or similar)

Code: Select all

if( eval > alpha ) { 
    alpha = eval; 
    PV[ply][ply] = m; 
    for&#40; int j=ply+1; j<=maxPly && PV&#91;ply+1&#93;&#91;j&#93;!=noMove; j++ ) &#123; 
        PV&#91;ply&#93;&#91;j&#93; = PV&#91;ply+1&#93;&#91;j&#93;; 
    &#125;

Michael

[Fguy64]

Thanks Michael

OK, so what I have shown is how my alpha updates and beta cutoff code deals with PV, within the iteration loop for possible moves at a given node.

I also have the following. Aside from the possible weirdness of my mate score, I believe this code deals with the possible problem you spoke of. This of course is outside of my iteration loop in alphaBeta.

Code: Select all

if( count == 0 ) {
    PV[ply][ply] = 0; 
    for&#40; int j=ply+1; j<=maxPly; j++ ) &#123; 
        PV&#91;ply&#93;&#91;j&#93; = 0; 
    &#125; 
    if&#40; inCheck&#40;gs&#41; ) return -&#40;100000-ply+2&#41;;
    else return 0;
&#125;

if this doesn't deal with your concern, do you have a specific example of a position where you believe I would return am incorrect PV?

[hgm]

There is no need to update on beta cutoffs: a cutoff is never a PV. You do a cutoff because it was proven that the move leading to the current node was not a PV move. The update is only needed when the sore is between alpha and beta.

When you do fixed-depth, you stand pat in every d=0 node...

[Fguy64]

There is no need to update on beta cutoffs: a cutoff is never a PV. You do a cutoff because it was proven that the move leading to the current node was not a PV move. The update is only needed when the sore is between alpha and beta.

When you do fixed-depth, you stand pat in every d=0 node...

I was wondering about that.

Still, at least in my engine, if I want to solve a mate in one, it seems I need a PV update for a beta cutoff at ply==1 ( i.e when searchine the root node).

because it is always PV[1][1] that actually gets returned to the game.

[hgm]

Good point. The root is different. I guess this type of beta cutoff is different anyway. You don't cut off because the previous move has aready been refuted, but because the highest possible score already has been obtained.