- 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

}

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:

- 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();

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:

- 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);

}

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.