Implementing pvs

[CDaley11]

I have a quick question about PVS implementation. Basically here's how I've been trying to implement it (I've turned off all other optimizations besides move ordering, and alpha-beta cutoffs in order to be sure that it is working)

Code: Select all

// Inside the evaluation function

for (EACH_MOVE) {
     makeMove();
     toggleTurn();
     if ( IS_FIRST_MOVE ) {
          temp = -searchToDepth( depth - 1, -beta, -alpha );
     } else {
          temp = -searchToDepth( depth - 1, -alpha - 1, -alpha );
          if ( temp > alpha ) {
               temp = -searchToDepth( depth - 1, -beta, -alpha );
          }
     }

     toggleTurn();
     unmakeMove();

     // Check for alpha and beta cutoffs
     // ....
}

But I've been getting some really weird results. It does significantly speed up my program, but now my program will sometimes play horrendous moves. Losing a queen to a pawn for example.

[lucasart]

I have a quick question about PVS implementation. Basically here's how I've been trying to implement it (I've turned off all other optimizations besides move ordering, and alpha-beta cutoffs in order to be sure that it is working)

Code: Select all

// Inside the evaluation function

for (EACH_MOVE) {
     makeMove();
     toggleTurn();
     if ( IS_FIRST_MOVE ) {
          temp = -searchToDepth( depth - 1, -beta, -alpha );
     } else {
          temp = -searchToDepth( depth - 1, -alpha - 1, -alpha );
          if ( temp > alpha ) {
               temp = -searchToDepth( depth - 1, -beta, -alpha );
          }
     }

     toggleTurn();
     unmakeMove();

     // Check for alpha and beta cutoffs
     // ....
}

But I've been getting some really weird results. It does significantly speed up my program, but now my program will sometimes play horrendous moves. Losing a queen to a pawn for example.

No idea what else you're doing wrong, but your PVS implementation is correct. Now there are two things in your code comment that worry me:
- what do you mean by "inside the evaluation function" ? Surely you mean the *search* function ?
- what do you mean by "alpha and beta cutoffs" ? What is an "alpha cutoff" ?

[lucasart]

I have a quick question about PVS implementation. Basically here's how I've been trying to implement it (I've turned off all other optimizations besides move ordering, and alpha-beta cutoffs in order to be sure that it is working)

Code: Select all

// Inside the evaluation function

for (EACH_MOVE) {
     makeMove();
     toggleTurn();
     if ( IS_FIRST_MOVE ) {
          temp = -searchToDepth( depth - 1, -beta, -alpha );
     } else {
          temp = -searchToDepth( depth - 1, -alpha - 1, -alpha );
          if ( temp > alpha ) {
               temp = -searchToDepth( depth - 1, -beta, -alpha );
          }
     }

     toggleTurn();
     unmakeMove();

     // Check for alpha and beta cutoffs
     // ....
}

But I've been getting some really weird results. It does significantly speed up my program, but now my program will sometimes play horrendous moves. Losing a queen to a pawn for example.

No idea what else you're doing wrong, but your PVS implementation is correct. Now there are two things in your code comment that worry me:
- what do you mean by "inside the evaluation function" ? Surely you mean the *search* function ?
- what do you mean by "alpha and beta cutoffs" ? What is an "alpha cutoff" ?

There is however, one important inefficiency in the above code. Not a bug, but an inefficiency.
- at non PV node, when searching a move that isn't the first one
- you do not fail low, as expected. So you do a re-search with the full window. But the full window *is* the zero window at non PV nodes. So you are wasting time by doing the same search twice.
A hacky way to fix your code is as follows:

Code: Select all

     if ( IS_FIRST_MOVE ) {
          temp = -searchToDepth( depth - 1, -beta, -alpha );
     } else {
          temp = -searchToDepth( depth - 1, -alpha - 1, -alpha );
          if ( temp > alpha && temp < beta ) {
               temp = -searchToDepth( depth - 1, -beta, -alpha );
          }
     }

"temp < beta" is a hack that ensures you don't do the re-search in the useless case where beta=alpha+1 (it ensures that beta > alpha+1 in order to re-search).

[CDaley11]

Thanks for your help and identifying some inefficient code. I found out that using a transposition table with the pvs was throwing it off, I think it's because my table doesn't distinguish between nodes that returned an exact evaluation and nodes that only produced a cutoff.