Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Hash table efficiency

Author: Miguel A. Ballicora

Date: 12:12:47 12/06/00

Go up one level in this thread


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



This page took 0.03 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.