THE EFFECT OF HASH SIGNATURE COLLISIONS IN A CHESS PROGRAM

Article type: Research Article

Authors: Hyatt, Robert M.^{a; 1} | Cozzie, A.^{b; 2}

Affiliations: [a] Birmingham, AL, USA | [b] Urbane, ILL, USA

Note: [1] Computer and Information Science Department, University of Alabama, Birmingham, AL 35294 USA. Email: hyatt@cis.uab.edu.

Note: [2] 012 East Kerr 107, Urbane, ILL 61802 USA. Email: acozzie@gmail.com.

Abstract: Hash signature collisions have been feared in computer-chess programs, dating back to the early Greenblatt program, and continuing until today. The fear has been that a signature collision, where the hashing function can take two different chess-board positions and produce the same hash signature, will produce errors in the tree search that will lead to gross playing errors and result in inferior play. As a result, chess programmers have spent significant amounts of time trying to reduce these signature collisions as far as possible (since a chess position cannot be uniquely stored in 64 or fewer bits, it is impossible to avoid all signature collisions). This research was done to answer the question: “Is it really worth all the effort to bring down the number of signature collisions to an absolute minimum?” The answer is surprising.

DOI: 10.3233/ICG-2005-28302

Journal: ICGA Journal, vol. 28, no. 3, pp. 131-139, 2005