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:
Hi


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
collisions...




--
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