On Achieving History-Based Move Ordering in Adversarial Board Games Using Adaptive Data Structures

This paper concerns the problem of enhancing the well-known alpha-beta search technique for intelligent game playing. It is a well-established principle that the alpha-beta technique benefits greatly, that is to say, achieves more efficient tree pruning, if the moves to be examined are ordered properly. This refers to placing the best moves in such a way that they are searched first. However, if the superior moves were known a priori, there would be no need to search at all. Many move ordering heuristics, such as the Killer Moves technique and the History Heuristic, have been developed in an attempt to address this problem. Formerly unrelated to game playing, the field of Adaptive Data Structures (ADSs) is concerned with the optimization of queries over time within a data structure, and provides techniques to achieve this through dynamic reordering of its internal elements, in response to queries. In earlier works, we had proposed the Threat-ADS heuristic for multi-player games, based on the concept of employing efficient ranking mechanisms provided by ADSs in the context of game playing. Based on its previous success, in this work we propose the concept of using an ADS to order moves themselves, rather than opponents. We call this new technique the History-ADS heuristic. We examine the History-ADS heuristic in both two-player and multi-player environments, and investigate its possible refinements. These involve providing a bound on the size of the ADS, based on the hypothesis that it can retain most of its benefits with a smaller list, and examining the possibility of using a different ADS for each level of the tree. We demonstrate conclusively that the History-ADS heuristic can produce drastic improvements in tree pruning in both two-player and multi-player games, and the majority of its benefits remain even when it is limited to a very small list.