Author: Sven Reichard
Date: 10:36:27 04/24/01
Question about transposition tables: I implement TTables in what I think is a rather standard way as a hash table. For each piece/color/square combination I generate a primary and a secondary hash code. The hash code of a position is the bitwise XOR of all the pieces present, plus some more codes for information like color to move, e.p. squares, castling rights, etc. The primary code is used as an address into the TTable, the secondary is used to detect some collisions quickly. Let's say that two distinct positions form a minor collision if their primary codes coincide, and a major collision if both their primary and their secondary codes coincide. In order for the TTable to work well, we want to minimize both minor and major collisions during the search. So far I generate the individual hash codes pseudo-randomly, with the result that there are lots of minor collisions and apparently also major collisions even in shallow searches. (The minor collisions make sense in view of the Birthday Paradox.) Has any work been done on choosing the codes intelligently? What do other people do? I think there might be some connection to things like error correcting codes, but I haven't seen anything published on that. Thanks for your comments, Sven.
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.