The basic idea is that there are two uncertainties in the estimate of the pv- move evaluation:
1) upperbound-lowerbound interval: we don't know the exact value of the current evaluation
2) search depth: we don't know if the current best move is the real best move, so what is the value of having an exact score?
Phrased in another way: if two moves are within the error margin for depth d the better way to evaluate them is depth d+1.
In pseudo code
Code: Select all
while time_remaining>0
{
go through (part of) the move list with alphabeta(pos,gamma-1,gamma,d)
count faillow
re-order list based on failhigh / faillow results
if ((upperbound - lowerbound < error) or faillow_count==1)
//alternatives estimated within error margin or a best move found
{
d++
reset upper & lower bounds
}
else
gamma= f(gamma, lowerbound, upperbound, stepsize)//adjust gamma to get a better cut off between best move & alternatives
error = f(error,game phase,d,time_remaining)// adjust allowable error to increase/decrease resolution if desired
}