Author: Heiner Marxen
Date: 14:21:17 02/11/02
Go up one level in this thread
On February 11, 2002 at 13:03:40, Miguel A. Ballicora wrote:
>On February 10, 2002 at 21:31:34, Heiner Marxen wrote:
>
>>On February 10, 2002 at 19:49:01, Miguel A. Ballicora wrote:
>>
>>>On February 10, 2002 at 19:28:33, Scott Gasch wrote:
>>>
>>>>You know reading this again I realize I misspoke and probably did more to
>>>>confuse you than to clarify. Let me try this again.
>>>>
>>>>When your search finds a mate it returns a score that is based upon that mate's
>>>>distance from the root of the search. So if you find a mate somewhere in your
>>>>search you will build the mate score based upon the distance from the root.
>>>>
>>>>When hashing such a score you can get yourself into trouble. Instead of hashing
>>>>the mate score as distance from root you want to hash it as distance from the
>>>>node you are hashing. For example, if you are at ply 5 and the recursive search
>>>>has returned a +mate in 12 ply score.
>>>>
>>>>If you simply store "mate in 12 ply" for this node's value you have trouble if
>>>>you come across the same position later at a different distance from the root.
>>>>Like you see it at ply 3, for example. Well then you lookup the hash table
>>>>value and its wrong -- it says this is a mate in 12 ply but its not anymore.
>>>>This time it's a mate in 10 ply from the root because you're 2 ply closer to the
>>>>root when you saw it.
>>>>
>>>>So hash the distance from the current position to the mate instead of the
>>>>distance from the root to the mate. To do this simple subtract ply from the
>>>>mate score. In our example we have mate in 12 ply and we first see it at ply 5.
>>>> Store as mate in 12 - 5 ply (mate in 7 ply) in the hash table.
>>>>
>>>>Then when you hit it later at ply 3, get the real score of the mate from the
>>>>root by adding in ply. So you lookup mate in 7 ply and add current distance
>>>>from root (3) to get "mate in 10 ply from the root".
>>>>
>>>>I hope I've been more clear this time. Good luck
>>>>
>>>>Scott
>>>
>>>I never understood what the people is doing with the mate values, I always
>>>get confused. I am glad that I came up with my own approach before I asked or
>>>saw any post about it. :-)
>>>
>>>What I do in pseudo code in Gaviota is
>>>
>>>search (alpha, beta)
>>>{
>>> adjust_in (&alpha, &beta); /* increments alpha += 1 and beta += 1 if they
>>> are positive mate values, do the opposite if
>>> it is a negative mate value */
>>> probe_hashtables_normally()
>>>
>>> loop { /* normal alpha beta stuff */
>>> makemove();
>>> value = search_moves_for_best_value(-beta, -alpha);
>>> unmakemove();
>>> best = keep the best value;
>>> }
>>>
>>> store_in_hashtables_normally();
>>>
>>> adjust_out(&best); /* decrement best -= 1 if it is a +mate value
>>> increment +=1 if it is a -mate value */
>>> return best;
>>>
>>>}
>>>
>>>And basically, I do not do anything else. I store in the hashtables without
>>>any change. adjust_out() it is used too when I return early.
>>>
>>>Regards,
>>>Miguel
>>
>>Hey, that is interesting!
>>This is exactly the way I would do it, since it is so logical.
>
>Gaviota feels flattered...
:-))
>>Everybody else seems to do it the other way round:
>>when creating a mate value, all the adjust_out() operations that would
>>be applied to it on the way back to the root, are applied immediately,
>>and around hash table access this is adjusted in the opposite direction.
>>And where you adjust in/out, nothing happens.
>>May be this method is a bit faster, but I'm not even sure about that.
>
>I guess that either way won't be a bottleneck.
Right! Compared to a single call to eval() this is miniscule.
>>Also, mate values as alpha or beta may raise problems, this way.
>>With your adjustment method there is no such problem :-)
>>
>>BTW, I would probe/store the hash table _outside_ of the adjustments.
>>Logically they are associated with the makemove()/unmakemove().
>
>I'll have to think about it, but at first glance it looks to me that
>both ways will give correct results.
Yes, both ways are consistent, but with my ordering the value stored with
a position is the true value of the position, and not the value as popped
up by the recursive call inside a makemove()/unmakemove(), not yet adjusted
for the additional ply.
Its kind of "cosmetic".
> In the way I posted it, you can
>do "return adjust_out(best);" every time you return so it will be more
>readable and less prone to forgetting to adjust. I think it is a matter of
>taste.
Since I just switch the sequence of adjusting and hash table access,
you can do that in both cases. And in both cases you have not stored
anything into the hash table :-(
Personally I prefer to do "goto rdy;" or "break;" instead of embedded
return's, exactly to avoid incomplete cleanup or bookkeeping (if there is any).
>Of course this adjustment has to be done also in quies_search if it is capable
>of detecting checkmates.
Sure :-)
>One interesting side effect is that you can do after adjust_in()
>
>if (alpha >= MATE) return alpha;
>
>and you prune right away. That means that you cannot find a move
>that is better than MATE! This situation happens when the PV found
>a mate in 9 plies and you are in another branch at ply 9.
Yes! You got it!
That was meant by:
>>Also, mate values as alpha or beta may raise problems, this way.
>>With your adjustment method there is no such problem :-)
Happy programming!
Regards,
Heiner
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.