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.