Author: Robert Hyatt
Date: 16:43:46 08/25/99
Go up one level in this thread
On August 25, 1999 at 18:40:02, Bas Hamstra wrote:
>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.
>
>
But how does that matter? I mean the typical q-search looks like this:
int Quiesce(alpha,beta) {
val=Evaluate();
if (val > beta) return(val);
alpha=val;
foreach move in(move_list) {
MakeMove();
val=-Quiesce(-beta,-alpha);
if (val > alpha) {
if (val > beta) return(val);
alpha=val;
}
}
return(alpha);
}
In that framework, I don't see how changing alpha/beta is going to affect
a thing. You still choose to stand pat. Or try more captures. With beta
= +infinity, you try all captures, but all that can do is to improve the
score for the side on move even further, since Evaluate() was used to set
the lower bound (stand pat score) for this ply...
Maybe I am missing what you are explaining?
>
>
>
>
>
>>>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.