Author: Robert Hyatt
Date: 09:08:50 08/26/99
Go up one level in this thread
On August 26, 1999 at 04:05:24, Bas Hamstra wrote:
>On August 25, 1999 at 19:43:46, Robert Hyatt wrote:
>
>>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?
>
>No, I think not. I have been thinking about what you and Bruce have said. My
>theory was that *every* capture worsens the score. And that with a wide window
>it sees this node is rotten, but with a small window not. But now I think I
>agree in both cases the same Beta is returned. So that is solved. Without
>nullmove it should give the same result with a wide and narrow window if the
>score is within the windows. As confirmed in practice.
>
>But now with nullmove: remember the fail low on [240, 260] while the full window
>score is 246. I bothered to check where that fail-low was generated. It was in a
>qnode with alpha=-260 and Beta=-240 and that node had
>Material >= -240 and thus gave a cutoff. Now I would like to know if this is
>normal behaviour or not...? IE is it normal (though rare) that with nullmove a
>score can not be found within [240, 260] when actually there is such a score? Or
>is there some strange bug? (Without nullmove not a single problem)
>
>
one sec... you said "Material > -240" which is a lot different from saying
"Evaluate() > -240". IE the 'stand pat' score is the material+positional
evaluation score...
Before going further, did you really mean 'material' or "evaluation"???
>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.