Author: Bas Hamstra
Date: 12:07:28 08/26/99
Go up one level in this thread
On August 26, 1999 at 12:08:50, Robert Hyatt wrote:
>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"???
I meant Evaluation, but there is difference (yet). I think I know what is going
on. With the smal window it gives a nullmove cut. With the wider window it
doesn't. I saw it happen, in the debugger.
There is *one* critical move (wac 141) that is Qxf4, sacrificing a queen and a
rook for a mating attack. On that critical move the small window leads to a beta
cutoff from nullmove. Well, if you throw away that critical move, it is normal
that a bad score evolves. With a wider window no nullcut (as I've *seen*) and it
sees the critical move.
My nullmove code is very simple and looks like this:
(notice I don't search to Depth == 0, but to Depth == MaxDepth)
if(DoNull && !InCheck && Depth < MaxDepth-R)
{ MakeNull();
Value = -AlphaBeta(-Beta, -Beta+1, Depth+1, MaxDepth-R, false);
UnmakeNull();
if(Value >= Beta) return Beta;
}
(the last parameter "false" is the DoNull parameter)
In the last R=2 plies of the search, near the leaves, the nullmove code is just
ignored. So in fact the last 2 plies are brute force. I'm not sure that's the
way to do it, but it seems to work ok.
The brute force part picks up Qxf4 (because Depth >= MaxDepth-R the Nullmove
code is ignored). One ply deeper Qxf4 lies within < MaxDepth-R range and so the
nullmove code is NOT ignored and with a small aspiration window Nullmove throws
the move Qxf4 out (resulting in a fail low on [240,260]). In a research with a
wider window Nullmove does not cut Qxf4 and that move is re-established in the
PV.
Regards,
Bas Hamstra.
>
>
>
>
>>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.