Author: Vasik Rajlich
Date: 11:15:31 06/18/05
Go up one level in this thread
On June 18, 2005 at 12:25:00, Dieter Buerssner wrote:
>Hi Vaskik,
>
>one example, what can go wrong for fail soft.
>
>int qsearch(int alpha, int beta)
>{
> /* Fail soft version - extremly simplified */
> int best, score;
> best = eval();
> if (best > alpha)
> {
> if (best >= beta)
> return best;
> alpha = best;
> }
> for (all captures)
> {
> if (value of captured piece + margin < alpha)
> continue; /* Futile to try this move */
if (eval () + value of captured piece + margin < alpha)
{
best = eval () + value of captured piece + margin;
continue;
}
FYI - I caught this at the first pass, but of course the warning (and theme)
didn't hurt :)
> makemove();
> score = -qsearch(-beta, -alpha)
> unmakemove();
> if (score > best)
> {
> best = score;
> if (best > alpha)
> {
> if (best >= beta)
> return best;
> alpha = best;
> }
> }
> }
> return best;
>}
>
>Do you spot the error immediately? To fix it, you'll need to add more lines of
>code. If you forget to fix this problem, you probably won't see it easily
>by inspecting the output of the program.
>
>One has to add code to absearch and qsearch. When you do lazy eval, add score
>there, too. In all places, similar things than above can happen here and there,
>so one has to check very carefully.
>
For what it's worth, if you used the above code in an MTD (f) search, you would
notice it quickly - it would lead to serious blunders. In a PVS search, though,
you might not catch it.
Although I guess yes - just returning alpha is a bit easier. :)
>I am not sure, we agree about the move ordering reasoning in fail-soft vs. fail
>hard. But I certainly do not think, that move ordering will be significantly
>better. I think, it has the potential for better move ordering. May well be,
>that it gets worse in reality. If for example, it for some reason (which I would
>not know) sort moves in an order, where moves that need huger trees earlier, and
>those moves still would not help to get a cutoff. As you pointed out, we
>typically get scores at the bounds anyway.
>
As far as I can see, fail-soft affects FL HT moves but not FH HT moves.
Also, as far as I can see, all of these effects of fail soft are pretty small
compared to doing re-searches.
There are a number of things which tend to kill the softness of fail-soft
scores:
1) lazy eval
2) early cutoffs in q-search
3) null move
4) bad fail-high moves
Each of these is a sort of ultra-laziness of the search.
If you could find some way to manage & control this, even at the cost of a few
nodes, MTD (f) would be really nice I think. There might even be some other uses
for really good fail-soft scores.
Regards,
Vas
>Cheers,
>Dieter
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.