Author: Bruce Moreland
Date: 09:50:25 08/26/99
Go up one level in this thread
On August 26, 1999 at 04:51:05, Bas Hamstra wrote: >On August 25, 1999 at 18:27:44, Bruce Moreland wrote: >>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]. I can't see what you mean by 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. The problem with quiescent search is that you have to have some way of bailing out. If you force the side to move to choose between one of those capture moves, effectively you've written a checker program, where captures are compulsory and lead to odd effects that are not at all chess. You could say "if (eval > alpha) alpha = eval;" instead of "if (eval >= beta) return beta;" You'd get the same tree, absent weird hashing effects, without pruning here. It's just less efficient, since you may have just set alpha to a value >= beta, so why search on with a negative width window? I think the pruning must be bugging you. All it's doing is trying to get max(static eval, capturing moves) and respond accordingly. Any of these capturing moves, or the static eval, can cause a cutoff. >>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. Right, this is just normal alpha-beta, only in the quiescent part, you allow a null-move to be counted as legal, and you disallow non-captures. You could have an absolutely pure alpha-beta search in there, if you made your move generator actually stick a null move in the move list. >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). Now we aren't talking about alpha-beta at all any more, we're talking about making a quiescent search that doesn't overlook tactics and mis-evaluate obvious situations. Mine ignores checks in quiescent search, but it's perfectly valid not to. The Thompson implementation of "qsearch" checked to see if the side to move is in check, and simply called "search" with a depth of 1 if this was so. It sounds like you are going that route, which is fine. >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. Yes, without null move this problem might go away. To get it to really go away you have to stop pruning based upon hash element values, and you have to stop razoring or doing any other search guidance based upon alpha or beta. What you have to do is make the search perform the same regardless of the values of alpha and beta. Null move is a great example of something that uses alpha or beta to guide the search. What it is doing is trying to see if the opponent can get the score of the position below some number that's derived from beta (either beta or beta plus or minus some constant, typically). If you have a search where the opponent can't drive the score below beta, you assume that a full search would also produce a score that's above beta, so you immediately return beta. If you increase the value of beta, perhaps now the opponent can drive the score below beta, so now you can't cut off. But when you do your search, you find that you are severely hosed, and perhaps you return alpha, which may have been below what beta was originally. This is an unavoidable search instability, unless you can remember your null-move cutoff value and use it consistently. >Now I would very much like to know if this is normal nullmove behaviour or if >there is something wrong in my code. I answered this above, I guess. The short answer is that it is normal. When you start a chess program you can keep yourself very clean. Things are deterministic. When you add a hash table you notice that you have dirt in your hair and this really bothers some people, and a lot of posts on here are people trying to come to terms with the fact that there is no way to get clean. When you add null-move pruning you are completely buried in mud, and your mind has to be able to handle the inconsistencies. >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? Anything can happen. If you re-search the same part of the tree again, you cannot assume that the value returned will lie within the same window that it did before. It can be *anything* the second time. bruce
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.