Author: Bas Hamstra
Date: 01:05:24 08/26/99
Go up one level in this thread
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)
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.