Author: Bas Hamstra
Date: 15:04:31 08/25/99
Go up one level in this thread
On August 25, 1999 at 17:36:55, Bruce Moreland wrote: > >On August 25, 1999 at 15:19:00, Bas Hamstra wrote: > >>Well at least the popular ab approaches have a bug. >> >>Suppose you had no tricks, no extensions, no nothing. Just ab and a qsearch on >>top of it. You set an aspiration window at the root, say [200, 300]. >> >>Now *if* the true ab value lies within this window, it should find it, right? >> >>WRONG! >> >>The fact that everyone has a >> >> if(Eval >= Beta) return Beta; >> >>somewhere in the qsearch, makes that this no longer must be true. Reason: >>suppose you sacrifice lots of material, but can win more material back, due to >>severe mating threats, or whatever. With the window [240, 260] the qsearch >>concludes at some point to return Beta because of the material advantage (3 >>pieces sacced), resulting in a fail-low on the [240, 260] window. However whith >>a wider window it can NOT do this, and finds the true value of 246. It now sees >>the material can be won back with rent. >> >>My conclusion is that a fail low on [240, 260] followed by a result of 246 >>on [-inf, inf] is completely normal and unavoidable in many cases. It also >>explains this: >> >> fail low on [240, 260] >> fail high on [-inf, 241] >> value = 246 on [-inf, inf] >> >>I don't like it. Suppose you start ab with [-inf, inf] and after a while >>alphabeta itsself has established a window of [x, y], halfway the search. >>Shouldn't the same phenomenon be possible? > >This is just an attribute of that kind of quiescent search, and it would work >with or without null-move forward pruning in the non-quiescent part of the >search. Bruce, I'm really glad you say that. Because Bob says this cannot occur without hashing/nullmove. Hashing was no factor, but without nullmove I couldn't reproduce this behaviour. Still I didn't understand why this couldn't theoretically happen even without nullmove, with such a (I would think standard) qsearch. >At the tips you are allowed to return the larger of the static eval, or a >quiescent search on any of the capturing successors. >If you removed all alpha-beta pruning from the search, you'd still get the same >result back from the search. Agreed, but i was specifically talking about the standard qsearch trick. >Of course this can make mistakes still, but they min-max horizon mistakes, >have nothing to do with alpha-beta. >If you aren't convinced I think I can add more to this. I am certainly convinced. Re-convinced. Because I thought so, but couldn't reproduce it without nullmove. You know: a lot of people told me long ago (while doing my first chess program) that this can't happen and must be a bug. I remember you saying it *can* happen with a-b based pruning. I thought this only referred to futility pruning in the q-search (got rid of that BTW). But I now understand Eval >= Beta is the same kind. Regards, Bas Hamstra.
This page took 0 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.