Author: Bas Hamstra
Date: 15:40:02 08/25/99
Go up one level in this thread
On August 25, 1999 at 18:02:19, Robert Hyatt wrote: >On August 25, 1999 at 17:40:07, Bas Hamstra wrote: > >>I confirm I couldn't reproduce it without nullmove. Hashing on or off doesn't >>matter. My hashcode is perfect :) >> > >Wasn't implying that it wasn't... just that the hash table has this unfortunate >tendency to graft subtrees from one part of the search onto another part of >the search. And when that happens you can get scores passed around that >represent a possibly deeper search that expected because of this grafting. And >if that position then gets overwritten, the next time the same position occurs, >the hash hit won't happen, the score changes, and you can fail high or low >in bizarre ways. > >Hashing is the source of many strange effects that we tolerate because of the >benefits that hashing brings. But you ought to be able to turn hashing off when >looking at strange occurrences, just to eliminate one source of the strangeness. > > > > >>Well, remains the fact that a small aspiration window sometimes strangely >>interacts with nullmove and fails to produce a value within a window when there >>*is* such a value that can be found with a wider window. > >I don't see how this can happen unless you have a bug. IE if you disable >alpha/beta, you still _must_ get the exact same score. And that is quite >provable (Knuth/Moore, 1975, "An analysis of Alpha/Beta Pruning"... And if >you get the odd behavior without alpha/beta working, it can't be an alpha/beta >issue... Bob, I don't really intend to refute alpha-beta. The title of the thread was just an attention drawer, it might as well have been "Madonna is a man!" I only want to point out that Eval >= Beta is an imperfect heuristic that at least theoretically can give inconsistent results. And with nullmove on I really see it go wrong in one case (wac141). What happens is this: after a couple of sacced pieces by white, black (not being in check) concludes in the qsearch that Eval is greater than Beta and cuts. With a wider window it does NOT cut and sees black loses big material, or gets mated. case 1: searchresult = fail low on [x, y] case 2: searchresult = x < value < y >>And I am not yet convinced that this cannot happen without nullmove. Simply >>because the Eval >= Beta trick is imperfect. With a small window it cuts off >>many combinations in the qsearch, that with a wider window it wouldn't. So how >>can I be sure a smaller window leads to the same score as a wider, even without >>nullmove? Assuming true score within window? Theoretically it could fail to see >>winning combinations by cutting of *winning* capture-sequences which would not >>happen with a wider window. And thus return a different score. Can you please >>explain why that is impossible? > >Just don't make that quiescence 'assumption'. That isn't an alpha/beta issue, >as in the q-search you can stand pat or make a capture. If standing pat is >enough to produce a score > beta, searching captures won't be useful because >they can't return a score > beta either. And it isn't really cutting off >anything erroneously, unless you have a bug somewhere else. Because all that >alpha/beta wants to prove is that the score is > beta. And while zugzwang can >invalidate the 'stand pat' alternative in a capture search, the zug problem will >still be there with minimax alone... I agree of course. However in this case it is the other way around. Standing pat has a big material plus and thus cuts. However standing pat leads to mate in this case. So it's not failing to see a score above Beta, which is useless, but failing to see standing pat is very *bad* here. Because of a narrow window and an imperfect heuristic. Regards, Bas Hamstra. >>Regards, >>Bas Hamstra. >> >> >> >> >> >> >> >> >> >> >> >>On August 25, 1999 at 16:46:04, Robert Hyatt wrote: >> >>>On August 25, 1999 at 15:27:43, Bas Hamstra wrote: >>> >>>>Oops: forgot to tell recursive nullmove was ON. Will test without too. >>>> >>>>On August 25, 1999 at 15:19:00, Bas Hamstra wrote: >>>> >>>>>Well at least the popular ab approaches have a bug. >>> >>>the trick with eval > beta is not alpha/beta. That is a programmer's >>>trick. However, if you are at a leaf/tip position, that is perfectly >>>correct... because with traditional alpha/beta scores can't get > beta >>>or less than alpha. >>> >>>If you turn off null move, and turn off hashing, you won't see _any_ of >>>this nonsense. >>> >>> >>> >>> >>>>> >>>>>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? >>>>> >>>>> >>>>> >>>>>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.