Author: Miguel A. Ballicora
Date: 10:03:40 02/11/02
Go up one level in this thread
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.
>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. 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.
Of course this adjustment has to be done also in quies_search if it is capable
of detecting checkmates.
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.
Regards,
Miguel
>
>Cheers,
>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.