If the decision to search null move depends on the window limits (usually through the condition curEval >= beta), you can prevent this by having a null move that fails high return the threshold for the decision (i.e. curEval) as a lower bound, rather than beta or the score bound it came up with. This lower bound will then not be sufficient for satisfying a request with beta > curEval, making an entry based on null-move search automatically invalid for a probe that would not do one. The other way around (beta during probe lower) is never a problem anyway.smrf wrote:Reentering tree evalution with changed alpha beta window at a node reusing matching results stored inside a cache will errornously rely on the assumption that identical subtrees would be inspected. But that is definitely wrong.
Search extensions at promising trajectories
Moderators: hgm, Rebel, chrisw
-
- Posts: 27821
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Search extensions at promising trajectories
Re: Search extensions at promising trajectories
Extending is a bet, you'll never know before extending if there is a gain.smrf wrote: Nevertheless this all is going more and more distant to my initial question, whether deepening caused by promising trajectories has been experienced to be beneficial. H.G.Muller argued (as i understood), that this could lead into subtrees the opponent never would like to enter at all and thus would be irrelevant, and so additionally maybe time consuming.
I did some experimentations with a kind of forced move extension, but with a null window search it's quite hard to tell wich moves are forced.
My idea was to look more deeply moves that would have a search score around alpha (or gamma) and if the number of moves with such a score is low then there is some kind of forced moves. Note that I was mostly interested in quiet moves, not captures. I had mixed results ; one problem is that I don't get any information at cut nodes because I only play one or two mores here. The other 'problem' is that even where it works well it's still possible that the subtree is still irrelevant to the search.
HJ.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Search extensions at promising trajectories
I am still not following. perhaps I don't understand your wording. But my "evaluation cache" has nothing to do with a subtree. My eval cache stuff is all based on just the current position being evaluated.smrf wrote:The moment someone e.g. uses nullmove pruning he already makes his tree evaluation depending on the initial alpha beta frame. Of course, it is possible to completely ignore this, as it would be handled mostly. Nevertheless that problem exists. Reentering tree evalution with changed alpha beta window at a node reusing matching results stored inside a cache will errornously rely on the assumption that identical subtrees would be inspected. But that is definitely wrong.bob wrote:... My evaluation doesn't depend on alpha/beta or anything else, so I don't see how/why one would write a program where this might be a problem
Perhaps you are talking about the scores generated and stored in the TT that represent the values produced by searching sub-trees???
-
- Posts: 484
- Joined: Mon Mar 13, 2006 11:08 am
- Location: Klein-Gerau, Germany
Re: Search extensions at promising trajectories
Well, a position associated with a searching level represents a subtree, which will be evaluated fully using the end nodes and minimax. Maybe there is known a lower bound, an upper bound, both or none of them. Of course there is an end node evaluation for every node, but is this top interesting for an inner node's evaluation?