Click to See Complete Forum and Search --> : Low bound on zero-window search


DeepButi
September 28th, 2004, 08:11 AM
I am testing a cut-off for a constant, cumulative score game. The idea is "even if I would win all remaining points, I have already better things to do".
for (each move)
{
DoMove();
CalculateScore();
if (current_score + remaining_score <= alpha)
{
UndoMove();
ret_value=current_score;
break; // cut-off
}
NegaScout(....) ... or ... NegaMax(...)
....
}

While in most situations this works fine (and it produces an improvement of 20%), sometimes it fails to find the correct solution.

I tested it with NegaMax and it works, but NegaScout or MTD(f) (calling NegaMax) fails, so it's clear than the problem is with zero-window calls.

The reverse idea "even if I would not make any more points, the opponent will not let me get here" always works
...
if (current_score >= beta)
{
ret_value=current_score;
break;
}
...


As a 20% improvement is really important, I guess if there is a solution, but I cannot figure out how to do it.

Any ideas?

Thanks

DeepButi
September 29th, 2004, 03:35 AM
Solved.