Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Hash table efficiency

Author: Robert Hyatt

Date: 13:17:22 12/06/00

Go up one level in this thread


On December 06, 2000 at 15:12:47, Miguel A. Ballicora wrote:

>On December 05, 2000 at 15:46:15, Robert Hyatt wrote:
>
>>
>>Try this position:
>>
>>/k/3p/p2P1p/P2P1P///K/ w
>>
>>The solution is Kb1, and should take between 18 plies and maybe 21-22 plies
>>to find.  If you can't get to 18 instantly, your hashing is not working right.
>>For comparison, on a 550mhz single cpu machine, Crafty can reach depth 34 in
>>8.2 seconds...
>
>I tried it and did not work. (it eventually finds the solution after a long
>time). I found a bug (silly but nasty!) that justifies most of the problem.
>
>I was storing "depth-1" when I should have been storing "depth"
>In pseudo code this was the bug:
>
>int search(position_t position, int depth)
>{
>  hash_hit = retrieve ( hashsig(position), &depthstored, &valuestored... );
>  if (hash_hit && depthstored >= depth)
>      return valuestored /*in hash table*/;
>  ...
>  loop until I find a cutoff or run out of moves {
>         makemove(move);
>         value = search (position, depth-1);
>         unmakemove(move);
>         ...
>         compare value with best, alpha and beta.
>  }
>  ...
>  hashtable_stored (hashsig(position), depth-1 /*BUG!!!!!*/ etc.);
>
>  return best
>}
>
>Now the program reaches ply 23 in less than a second but it does not find
>the solution even when I disabled NULLMOVE. I went to sleep and it found it
>overnight, though.
>
>There are *NOT* many things that can go wrong here!!! Are they?. I am almost
>sure that the problem I have is the way I handle draw by repetition but I have
>to test it (and I will have to think of a solution which might not be trivial).
>I think is not right to store in the hashtable a value returned after
>a search that hit a move repetition.
>
>I'll try to explain what I mean whit this scheme:
>
>Moves
>    m1    m2   m3   m4   m5   m6   m7   m8
>Ply --> 1 -> 2 -> 3 ->(4)-> 5 -> 6 -> 7 -> 8
>             |         *    ^              ^
>             |              |              Position 4 is repeated.
>             | m3'          |              so, in ply 7 I store "DRAW"
>             \___ 3'__ 4'__/               (reached after move = m8).
>              Alternativee path
>              where postion 4' is different than 4.
>
>This is a problem, because I can reach, say, postion "7" through and
>alternative path without passing through position "4". Then, when I am in
>position "7" I hit the hashtable saying that it is a DRAW by repetition
>when If I play m8 I don't repeat any position!
>
>At least the plan is to get it right with this position... no null move
>evaluation = material evaluation. Maybe the hashing is ok, but do you think
>that how move repetition is handled could cause an apparent bug in
>the hashing? I think so.
>
>This morning, before I left to work, I disabled move repetition detection.
>It reached ply 23 (still Kb2) in less time that it took me to hit enter and look
>at the screen, but the, it hit a "wall". Ply 24 takes forever and I left.
>
>Tonight I will do more tests with the repetition detection. Hopefully
>I'll get it right.
>
>Thanks,
>Miguel


Repetition is a known hashing "issue".  But in fact, it is there even when
you aren't thinking about a repetition... because what says that you can search
from the node where you get the hash hit, to the terminal node that follows
that deeper in the tree, without repeating something?

It is messy.  I simply ignore it.



This page took 0.02 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.