Author: Vasik Rajlich
Date: 09:46:23 06/19/05
Go up one level in this thread
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.
>
>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".
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.