Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Pawn hashing without Zobrist keys

Author: Gerd Isenberg

Date: 13:40:41 09/12/03

Go up one level in this thread


On September 12, 2003 at 14:50:11, Dann Corbit wrote:

>On September 12, 2003 at 14:39:46, Dieter Buerssner wrote:
>
>>Hi Gerd,
>>
>>my answer is not exactly referring to your post, but an idea I always had.
>>Instead of Zorbrist type hashing, one could use some "classical" hashing
>>function: See all the position data (or pawn pos data) as a string, and
>>calculate a hash - perhaps a 32 bit hash. Many schemes don't need any modulo.
>>One could use a (32-bit) modulo in the last step. Perhaps one could try the
>>typical CRC scheme (source available for example in zip). Crypto experts
>>certainly could suggest even better schemes. Incremental updates would perhaps
>>be difficult or impossible, but might be possible in some schemes. For pawn
>>hashing, storing the whole pawn structure as 2 bitboards, plus perhaps 12 bytes
>>for the KK pos for verification of clashes might be no problem (I guess, most
>>that use pawn hashing already store lot's of things about the pawnstructure
>>anyway, so the size overhead should not be too bad, and would have the
>>advantage, that one really has certainty).
>
>An n-bit SDBM hash scheme would be a good one, I bet.
>Perhaps 2^20 entries (1,048,576) and a simple and operation will finish the
>hash.  (Or you could even have an unsigned:20 type).
>
>The SDBM hash is super simple and yet of high quality.
>http://www.cs.yorku.ca/~oz/hash.html


Thanks,

i tried this one on the fly with 64K entry table:

unsigned int CPawnHashTable::GetIndex(const CNode &node)
{
  unsigned int hash;
  hash = (UINT)(node.wPawns() & 0xffffffff);
  hash = (UINT)(node.wPawns() >> 32)        + (hash<<6) + (hash<<16) - hash;
  hash = (UINT)(node.bPawns() & 0xffffffff) + (hash<<6) + (hash<<16) - hash;
  hash = (UINT)(node.bPawns() >> 32)        + (hash<<6) + (hash<<16) - hash;
  hash -= (hash >> 16);
  return hash & 0x0000ffff;
}

not sure about the folding but i got reasonable hitrate.
Not as good as the mod approach (~84% after 1 min initial position).
Unfortunately the MS-compiler uses three imul instructions ;-)
First tests indicate about equal performance.

Regards,
Gerd






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.