View Single Post
  #4   Report Post  
Old March 25th 04, 01:38 PM
Robert Hyatt
Posts: n/a
Default hash table collisions

Paul Rushmer wrote:

I'm writing my own chess program, and I'm just trying to implement a
transposition table using a hash table. My Zobrist keys seem to be working
ok, and I've loaded up some opening books at program start and the positions
are recognised when played. But when I use the table with my a/b function, i
get lots of collisions, many more than i expected. Typically during a 4 ply
search of a midgame I'll get many 1000's of collisions. Any idea of a
typical collision frequency? I'm using a 64 bit key, and the C rand
function (with bit shifts) to generate the random numbers, and I can't find
duplicates in the zobrist keys at initialisation, but like i say, during
play lots of positions hash to a key that when used to access my table i
find the "key lock" does not match. (key lock i use is the hash index used
to store the position) . My table size is currently 4 Mbyte and I've tried
increasing this but it makes little difference, so I think i have a
fundamental problem. Any ideas greatly appreciated.

Many thanks - Paul Rushmer

it sounds like you are defining "collision" incorrectly. Many different positions
will hash to the same table entry, but with different hash signatures. These are not

Robert M. Hyatt, Ph.D. Computer and Information Sciences
University of Alabama at Birmingham
(205) 934-2213 136A Campbell Hall
(205) 934-5473 FAX Birmingham, AL 35294-1170