Memory Efficiency in Some Heuristics

Article type: Research Article

Authors: Uiterwijk, Jos W.H.M.

Affiliations: Dept. of Computer Science, University of Limburg, Maastricht, The Netherlands

Abstract: The history heuristic and the countermove heuristic having been found to be reasonable methods for move ordering, they both are assumed to incur a large memory obligation: for both, two tables of 64 × 64 entries seem to be needed. In this article we present an alternative way of storing the history information or the countermoves. In both cases one needs only two 6 × 64-entry tables, which relative to the 64 × 64 tables represents a better than 90 percent saving in memory requirement. It is demonstrated that both the original (i.e., the from_square representation) and the new representation (i.e., the from_piece representation) may wrongly identify distinct moves, thereby influencing the search efficiency negatively. Considerations on the frequency of occurrence of such “errors” and on their seriousness provide no clear evidence for choosing amongst them. Experiments reveal that the computational expense of the new representation with its large storage saving is no more than a minor decrease in the efficiency of move re-ordering.

DOI: 10.3233/ICG-1992-15203

Journal: ICGA Journal, vol. 15, no. 2, pp. 67-74, 1992