Author: Bas Hamstra
Date: 06:38:18 10/19/99
Go up one level in this thread
On October 19, 1999 at 05:51:22, José Carlos wrote: >I use the standard hash function generated from a set of 64bit random numbers. I >use the n rightmost bits of the 64bit code as index (of the array), n depending >on the hash table size. >I think this is normal, but my question is related to the checksum to ensure the >position in the table is equal to that in the board. >The only way to ensure this is to code the board (256bits if 4bits per square >and piece or about 180 if using huffman code). I use the first. >But last night I was looking at Crafty's code (16.15, if I remember right), and >saw it uses a 64 bit checksum. That's what I read in the comment before the >HashProbe function, but I could not find where is this checksum generated, and >how. >My question is: with, at most, 128bits per position (that I'll never would use >in fact), isn't it possible to make mistakes? I know the probability is small, >but eventually there could be a very strange move coming from a hash table >mistake. Is this true? What am I missing? >Is, anyway, safe to use a 64bit checksum? And if so, is the checksum generated >the same way as the hash code, but with different random numbers? > >Thanks in advance. > >José C. Hello José, Yes, with a 64 bits key there is a probability for errors. In practice the probability so small you don't notice it. For example: when I have a move in my hashrecord that is not legal, my program prints a errormessage. But I hardly ever see such messages. You talk of a hash function. Most programs keep track of a 64 bits hashkey that represents the position. With every make/unmake the hashkey is updated as follows: HashKey ^= Zobrist[PieceType][Square][Color]; To XOR a piece on square Square out of the position. And another XOR to XOR it in for another square. In this story Zobrist[][][] is a table with 64 bits random numbers. No hash-function needed to compute a hashvalue, the above incremental scheme is much faster and easy to understand. (Hope I did not misunderstand what you wrote) Regards, Bas Hamstra.
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.