Author: Vasik Rajlich
Date: 15:03:27 06/19/05
Go up one level in this thread
On June 19, 2005 at 13:42:11, rasjid chan wrote:
>On June 19, 2005 at 12:46:23, Vasik Rajlich wrote:
>
>>On June 19, 2005 at 11:09:22, rasjid chan wrote:
>>
>>>Vasik,
>>>
>>>quote
>>>1)This should never happen. At FL nodes, your return type will be UB.
>>>2)If you can get a return type of something other than UB at a FL node, then I
>>>don't understand properly how your return type works.
>>>3)As I understand, you could figure out the "return type" at each interior node
>>>- it's not something that needs to be passed around.
>>>unquote
>>>
>>>On (3) - I think you mean this :- eg.
>>>score = -search();
>>>if score <= alpha, then the return_type must be LB as the previous node FH,
>>>etc .... so no need to pass things around.
>>>
>>
>>Yes.
>>
>>>Exactly because I have a purpose (if correct and posssible ?), I need to pass
>>>things around.I will explain what I am trying to achieve.
>>>
>>>First we must assume hashing in QS and no special check generation in QS
>>>allowed.ie, the move set is always capture/ep/promote for QS. This is for making
>>>theoretical discussion simple. General ideas about hashing QS applies, only
>>>depth = 0.
>>>
>>>Now there is a rule :
>>>
>>>Rule: - In fail low(soft) with best < alpha, hashing is as follow:-
>>> hash_value = best.
>>> hash_type = UB.
>>>
>>>I think this is the correct usual rule and if it is not then it means I have a
>>>misunderstanding about hashing and alpha-beta.
>>>
>>
>>Correct.
>>
>>>We discard return_type for the moment so as not to confuse things.
>>>
>>>What I am trying to show is that the rule above need not be observed all the
>>>time and in some situations it is posssible to fail low and yet able to hash
>>>with hash_type = EXACT.
>>>So this is the simple aim (nothing about returning value or type).
>>>
>>>Assume we are in QS:-
>>>
>>>int qsearch(alpha, beta){
>>> int best, alpha0 = alpha;
>>>
>>> best = eval();
>>> for (QS_MOVE){
>>> makemove();
>>> score = -qsearch();
>>>
>>>/*
>>> Assume this current score end up finally as the best score and a fail low.
>>> and best < alpha. Consider the situation when this best score comes from FH
>>> in the node above for the current move:-
>>> 1) FH was a score from eval()
>>> 2) There was no QS moves.
>>>
>>>*/
>>>
>>> unmakemove();
>>> if (score > best){
>>> best = score;//new best is set.
>>> if (best > alpha)
>>> alpha = best;//never set
>>> }
>>>
>>> if (alpha>alpha0){
>>> return alpha;
>>>
>>>
>>> //execution reaches here as we have a fail-low situation.
>>> storehash(depth = 0, value = best, hash_type = UB);
>>> //This is the usual hashing.
>>> return best;
>>>}
>>>
>>
>>Ok - so far, so good.
>>
>>> In such a case this best score is actually exact and we can hash with
>>> hash_type = EXACT instead of the usual UB.ie in all subsequent visit to this
>>> node with whatever search window,the value that search will return, whether
>>> FL/FH/within search bounds, will be this same best value.
>>>
>>
>>This is true.
>>
>>> Now this can be done when the node above pass down return_type = EXACT.
>>> Now as this best score is again exact, this exact type is again passed down
>>> with :-
>>> return_type = EXACT
>>> return best.
>>>
>>> So now we have a FL and a return type as exact and not the usual upper bound.
>>> This answera your question (2) above.
>>>
>>
>>Yes, also true.
>>
>>> This method of passing return_type may enable us to pass down
>>> return_type = EXACT all the way down to root. Hashing may also be exact even
>>> for FL / FH.
>>>
>>
>
>
>
>>This exactness won't get far up the tree in the main search. A parent can only
>>get an "EXACT" score if:
>>
>>1) It is a fail-low node
>>2) Every single child is a quiescence-search node which was able to return
>>EXACT.
>
> I don't measure statistics yet.
>
> I will have to think again when questioned. My understanding(?) now is :-
> 1) parent FL node -
> a) child nodes need not be q-nodes, just any node that
> return an exact type; exactness may be simply passed down back
> to absearch() and still "exact".
Ok, true - but children of FL nodes are FH nodes, and FH nodes in the full
search will almost never be exact. (See below.)
> b)not necessary for every child node to return an exact type, but only
> the best move of the parent must receive an exact return.(?)
> Consider a search of this same parent node when revisited. We have
> this same best move which again will received an exact type and the
> same score. All other moves are limited by UB below this best-score
> received, irrespective of subsequent search bounds of all moves.
Aha, you're right - thanks for correcting me.
In fact, if you really wanted to get theoretical, you could return from each
node both a lowerbound and an upperbound. At a FL node, the upperbound would of
course be the fail-soft value; while the lower bound would be the negative of
the lowest of the upper bounds of the children. (Or, to use your original
terminology, the highest exact score.)
> 1) a parent FH node may also get an exact score.
> When then FH move happened to receive exact and also happen to be the
> last move. This is more likely in QS FH.
This will be very rare in the full search. It might happen on occasion when
escaping from check.
I think this is the big problem here. As soon as you get to the full-width
search, your first fail-high node will (almost certainly) end the exactness and
prevent it from propagating further. In other words, it is usually not possible
to get an upper bound at fail-high nodes.
>
> I rather like these to be correct otherwise the gains would be almost
> unmeasurable.
Yes, true. I think the practical gains are minimal, but I can't think of any
drawbacks here - it's theoretically correct. It should save you a few nodes here
and there (when you need to re-search nodes at or close to the horizon). The
smaller your windows from the root, the better these small savings should be.
It's basically a sort of beefed-up fail soft, in that you're trying to return
more than the minimum information.
>>
>>>
>>>If the reasoning is not flawed, there is at least a theoretical advantage.
>>>
>>
>>As far as I can see, your conclusion is true. You could simplify it slightly by
>>passing up a single boolean "score_is_exact" flag, rather than a three-way
>>"LB/EX/UB".
>
> Will think again. Adding REP3 will help to prevent purists from HT
> path-dependency corruption.
>
I have to think about this a bit. This seems to me to be a different issue, so
it should be handled separately ?!
Vas
> Best Regards,
> Rasjid
>
>
>>
>>I would guess that adding this capability to an MTD (f) engine will slightly (ie
>>by <0.1%) reduce the node count. In MTD (f), you will often come to a node in
>>quiescence search with different bounds, and being able to set both bounds might
>>save you from a re-search in the q-search.
>>
>>Vas
>>
>>>Best Regards
>>>Rasjid
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.