Author: rasjid chan
Date: 10:42:11 06/19/05
Go up one level in this thread
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".
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.
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.
I rather like these to be correct otherwise the gains would be almost
unmeasurable.
>
>>
>>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.
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.