Author: rasjid chan
Date: 10:17:28 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:
I dont measure statistics yet.
>
>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.