Replacement Schemes for Transposition Tables
Dennis M. Breuker, JOS W. H. M. UITERWIJK, H.J. van den Herik · ICGA Journal · 1994
Almost every chess program makes use of a transposition table, typically implemented as a large hash table. Even though this table is usually made as large as possible, subject to memory constraints, collisions occur. Then a choice has to be made which position to retain or to replace in the table, using some replacement scheme. This article compares the performance of seven replacement schemes, as a function of transposition-table size, on some chess middle-game positions. A two-level table, using the number of nodes in the subtree searched as the deciding criterion, performed best and is provisionally recommended.