Code: Select all
Search(alpha, beta, depth)
{
tempBeta = beta;
for(ALL_MOVES) {
MakeMove();
LMR = 0;
score = -Search(-tempBeta, -alpha, depth-1-LMR);
if(alpha < score && score < beta)
score = -Search(-beta, -alpha, depth-1); // RE-SEARCH
UnMake();
if(score>alpha) {
alpha = score;
if(alpha >= beta) goto cutoff:
tempBeta = alpha+1; // POSSIBILITY 2
}
tempBeta = alpha+1; // POSSIBILITY 1
}
cutoff:
...
}
My question, however, is: should I close the window after the first move (possibility 1) or only after the first move that raised alpha (possibility 2). Most nodes with an open window are likely to occur from re-searches, where the parent just opened the window. That means that they were searched just before with a null window, to which they failed low. Because of that fail low, there will be no hash move. So it would not be uncommon that the first move we search is not the best reply, or would in fact even fail low. So my guess is that it would be better to use possibility 2: only collapse the window after alpha was raised. Am I right about this?
This classical way of representing PVS seems a bit inefficient in practice: when a re-search is triggered you re-enter a node immediately after returning from it, having to re-do move generation, sorting and everything. This could be easily prevented by having the node not return, but informing it that it should do the re-search with opened window of its own accord, without returnin. Pseudo-code for such an implementation would look like:
Code: Select all
Search(alpha, beta, forceOpen, depth)
{
originalAlpha = alpha;
iidDepth = START_DEPTH;
alpha = beta-1;
do {
if(forceOpen) alpha = originalAlpha;
open = forceOpen;
startAlpha = alpha;
for(ALL_MOVES) {
MakeMove();
score = -Search(-beta, -alpha, open, iidDepth-1);
UnMake();
if(score > alpha) {
alpha = score;
open = 0; // POSSIBILITY 2
if(alpha >= beta) goto cutoff;
}
}
if(originalAlpha < score && score < beta && alpha == startAlpha) {
alpha = originalAlpha; // OPEN WINDOW
continue; // AND RE-SEARCH
}
cutoff:
iid = NEXT_IID_DEPTH;
alpha = beta-1; // NEXT ITERATION USES NULL WINDOW AGAIN (?)
} while(iidDepth <= depth);
}
The parameter forceOpen now indicates if the search should be with open window, which was formerly implied by alpha an beta themselves, so that we can now pass the original alpha and beta even in case we want the search initially to be done with a closed window. Because of the IID we have to remember the original alpha, an reset to that before each new iteration.
The PVS is now implemented by normally setting the window {beta-1, beta}, (i.e. in nodes that are not forced open, which would have been called in regular PVS with null window already), which corresponds to {alpha, alpha+1} of the caller. When the whole iteration fails low to this null window, (meaning the move in the caller fails high), we then re-do the iteration at the same depth with open window. That is, if it was not immediately clear that we also fail low compared to the opened window, i.e. if bestScore > originalAlpha. That way we can simply use the original move list.
The condition score < beta would not really be needed when the cutoff label is behind the test, but is added for clarity. The test alpha == startAlpha indicates that we really had a fail low (no move increased alpha), and that we ended up with a score above originalAlpha then proves that we must have started with alpha != original alpha, i.e. with a null-window.
I am still wondering abot the interaction between IID and re-searching. I guess that depends on your IID strategy. If you do not normally do IID in non-PV nodes, you would initialy set START_DEPTH to depth, when forceOpen==0, so that iidDepth immediately starts at the maximum depth. But when you have to re-search with open window, without the benifit of a hash move, you might want to start this re-search at a lower iidDepth. And what would you do when in some earlier iteration, the score would fall out of the (opened) window? Would you close the window again to {beta-1, beta} for the next iteration, when the current one failed high (>=beta), to quickly verify cut-moves in subsequent iterations, untill the score of this cut-move candidate again falls in window, (and thus fails low w.r.t. the null window), and then re-search with open window at that depth?
And if your IID strategy was to use IID in non-PV nodes as well, woud yu first do all iteratons to maximum depth with null window, no matter how they failed, and then start again with IID in an open window when the score in the final iteration ended up in {alpha, beta}? (This would mimic the conventional seperate call for the re-search.) Or could you improve on it by immediately opening the window after a properly failing iteration?(And possibly close it again on a later iteration?) By self-re-searching you have more flexibility than with two separate calls, making it harder to decide what would be best. (In my engine HaQiKi D it proved advantageous to do one iteration of IID in non-PV nodes by starting at d=1 when the target depth was >=4, before jumping to the final depth.)
Yet another question: if you do LMR and PVS, you start searching with null window AND reduction. What best to do when this search fails high? Do one re-search with open window without reduction? First do a null-window search without reduction before deciding on an open-window search without reduction? And if the latter, where would you put the null window? (E.g. if the score in the reduced null-window search was >= beta, would you put a null window for the unreduced search at {alpha, alpha+1} or at {beta-1, beta}?) I would think that in all cases it would be best to take away the reduction: a move that fails high compared to alpha, even at reduced depth or because of search instability cannot be so without merit that it deserves to be reduced.
