accelerated PVS
Posted: Mon Dec 24, 2012 10:07 am
I'd like to starty by pointing out that the chess programming wiki's pseudo-code for PVS is quite wrong:
This bSearchPV is rather clumsy, and the PV-ness of nodes must be passed on recursively via the search. For example when beta = alpha+1 in this code, the first move is search twice with exactly the same parameters.
Here's the code of my engine, as an example of a correct implementation in a real program. This is the part inside the move loop (the rest is obvious). In a real program, you need to pass on the depth recursively (otherwise you segfault on a stack overflow) as well as a search stack (not necessary but typical). And you need to cater for search reductions too, and the re-search mechanism. Anyway, here's the code, I hope it is self documenting:
Notice that:
- if we are in a PV node, and we are searching move number 2,3,4,...
- we expect them to fail low. so we do a zero window search at reduced depth first
- at PV nodes, if we don't fail low, we do not extend the depth but extend the window to (alpha, beta) first, and the depth after (if it doesn't fail low, again). In theory, this is unsound, as if the zero window reduced search fails low, the full window reduced search should also fail low. But in reality modern searches are plagued with inconsistencies, and often you will fail high on nonPVSearch(alpha,alpha+1) but fail low on PVSearch(alpha,beta). So we resolve the potential instabilities in this way, before extending the search. This is what Fruit does, for example.
Now a more traditional implementation of PVS, that typically doesn't care about search instabiities:
I wonder if other engine developpers have experimented with both approaches. For example Fruit uses the first version, and Glaurung/Stockfish use the second. I have experimented with both in DiscoCheck, and the first one (the Fruit one) was very measurably superior.
Experimental results, pros and cons, or other ideas, welcome.
Code: Select all
int pvSearch( int alpha, int beta, int depth ) {
if( depth == 0 ) return quiesce( alpha, beta );
bool bSearchPv = true;
for ( all moves) {
make
if ( bSearchPv ) {
score = -pvSearch(-beta, -alpha, depth - 1);
} else {
score = -pvSearch(-alpha-1, -alpha, depth - 1);
if ( score > alpha ) // in fail-soft ... && score < beta ) is common
score = -pvSearch(-beta, -alpha, depth - 1); // re-search
}
unmake
if( score >= beta )
return beta; // fail-hard beta-cutoff
if( score > alpha ) {
alpha = score; // alpha acts like max in MiniMax
bSearchPv = false; // *1)
}
}
return alpha; // fail-hard
}Here's the code of my engine, as an example of a correct implementation in a real program. This is the part inside the move loop (the rest is obvious). In a real program, you need to pass on the depth recursively (otherwise you segfault on a stack overflow) as well as a search stack (not necessary but typical). And you need to cater for search reductions too, and the re-search mechanism. Anyway, here's the code, I hope it is self documenting:
Code: Select all
// Play the move
B.play(ss->m);
// PVS
int score;
if (is_pv && first)
// search full window
score = -search(B, -beta, -alpha, new_depth, is_pv, ss+1);
else
{
// zero window search (reduced)
score = -search(B, -alpha-1, -alpha, new_depth - ss->reduction, false, ss+1);
// doesn't fail low: re-search full window (reduced)
if (is_pv && score > alpha)
score = -search(B, -beta, -alpha, new_depth - ss->reduction, is_pv, ss+1);
// fails high: verify the beta cutoff with a non reduced search
if (score > alpha && ss->reduction)
score = -search(B, -beta, -alpha, new_depth, is_pv, ss+1);
}
// Undo the move
B.undo();
- if we are in a PV node, and we are searching move number 2,3,4,...
- we expect them to fail low. so we do a zero window search at reduced depth first
- at PV nodes, if we don't fail low, we do not extend the depth but extend the window to (alpha, beta) first, and the depth after (if it doesn't fail low, again). In theory, this is unsound, as if the zero window reduced search fails low, the full window reduced search should also fail low. But in reality modern searches are plagued with inconsistencies, and often you will fail high on nonPVSearch(alpha,alpha+1) but fail low on PVSearch(alpha,beta). So we resolve the potential instabilities in this way, before extending the search. This is what Fruit does, for example.
Now a more traditional implementation of PVS, that typically doesn't care about search instabiities:
Code: Select all
if (is_pv && first)
// search full window
score = -search(B, -beta, -alpha, new_depth, is_pv, ss+1);
else
{
// zero window search (reduced)
score = -search(B, -alpha-1, -alpha, new_depth - ss->reduction, false, ss+1);
// fails high: verify the beta cutoff with a non reduced search
if (score > alpha && ss->reduction)
score = -search(B, -beta, -alpha, new_depth, is_pv, ss+1);
// doesn't fail low: re-search full window (reduced)
if (is_pv && score > alpha)
score = -search(B, -beta, -alpha, new_depth, is_pv, ss+1);
}
Experimental results, pros and cons, or other ideas, welcome.
