Author: Bas Hamstra
Date: 01:51:05 08/26/99
Go up one level in this thread
On August 25, 1999 at 18:27:44, Bruce Moreland wrote: > >On August 25, 1999 at 18:04:31, Bas Hamstra wrote: > >>On August 25, 1999 at 17:36:55, Bruce Moreland wrote: >> >>> >>>On August 25, 1999 at 15:19:00, Bas Hamstra wrote: >>> >>>>Well at least the popular ab approaches have a bug. >>>> >>>>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? >>> >>>This is just an attribute of that kind of quiescent search, and it would work >>>with or without null-move forward pruning in the non-quiescent part of the >>>search. >> >>Bruce, I'm really glad you say that. Because Bob says this cannot occur without >>hashing/nullmove. Hashing was no factor, but without nullmove I couldn't >>reproduce this behaviour. Still I didn't understand why this couldn't >>theoretically happen even without nullmove, with such a (I would think standard) >>qsearch. >> >>>At the tips you are allowed to return the larger of the static eval, or a >>>quiescent search on any of the capturing successors. >>>If you removed all alpha-beta pruning from the search, you'd still get the same >>>result back from the search. >> >>Agreed, but i was specifically talking about the standard qsearch trick. >> >>>Of course this can make mistakes still, but they min-max horizon mistakes, >have nothing to do with alpha-beta. >>>If you aren't convinced I think I can add more to this. >> >>I am certainly convinced. Re-convinced. Because I thought so, but couldn't >>reproduce it without nullmove. You know: a lot of people told me long ago (while >>doing my first chess program) that this can't happen and must be a bug. I >>remember you saying it *can* happen with a-b based pruning. I thought this only >>referred to futility pruning in the q-search (got rid of that BTW). But I now >>understand Eval >= Beta is the same kind. > >I'm not sure what "it" is that is supposedly happening, so I'll pretend you >aren't convinced. *IT* is a search failing to produce a score of 246 with an aspiration window of [240, 260]. >Let's get rid of quiescent search for a moment and just search to a fixed depth >using alpha-beta and no other pruning. > >This will produce a move with the same score you'd get back from min-max, and if >you search the tree in the same order, it will produce the same move. > >This of course assumes you've gotten rid of all insanity such as extensions and >pruning based upon hash table elements, etc. > >OK, now we add null-move quiescent search to min-max. Null-move quiescent >search is used only at the tips, and allows you to choose between any "critical" >move, typically a capture, or the static eval. So you can pick the score you >want from amongst a limited set of possible moves, or the null move. > >Note that this has nothing to do with the kind of null-move people are talking >about when they talk about Fritz. > >When you use alpha-beta with null-move quiescence, all that "if (eval >= beta) >return beta;" does is make things go faster. It is a performance improvement, >and nothing else, since it is searching the same tree and returning the same >result, and you can prove this. Ok. In fact Eval>=Beta *is* nullmove quiescence. If you would strip that line it wouldn't be nullmove quiescence and could give different results I guess. IE a different set of leaves would be searched namely only nodes where there are no captures. >If you are talking about making decisions about whether to prune or not, or to >go deeper or not, based upon alpha or beta, then you've thrown out this min-max >equivalence. > >Null-move quiescent search doesn't throw out min-max equivalence. It took me a while, but I think I agree. A qnull min-max scheme would produce the same results. >Null-move forward pruning higher up in the tree does, unless you prune based >upon something other than alpha, since min-max doesn't have alpha (you could use >something constant like zero or the value returned from the previous search, >although you might get a weak search). > >Razoring based upon alpha also throws out min-max equivalence. So does pruning >based upon the hash table, since the score returned is dependent upon the order >in which the tree is searched. > >bruce Ok, it is settled that there is not much wrong with Eval >= Beta, in the sense that it could lead to inconsistencies (though I do think there are other problems with it, therefore I prevent this when in check). However with nullmove (R=2) on I still get that inconsistency: [240, 260] -> fail low [-inf, inf] -> 246 Without nullmove this problem goes away. I checked where the fail low is generated. It is in a qnode, where a=-260 b=-240 and the Eval is > -240 thus giving an beta cut while beta still has the "aspirationvalue". That's were the confusion started. Now I would very much like to know if this is normal nullmove behaviour or if there is something wrong in my code. IE can it theoretically occur that nullmove fails to produce a score within a window when there *is* such a score, that can be found with just a wider window? 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.