Challenging state-of-the-art move ordering with Adaptive Data Structures

摘要

The field of game playing is a particularly well-studied area within the context of AI, leading to the development of powerful techniques, such as the alpha-beta search, capable of achieving competitive game play against an intelligent opponent. It is well-known that tree pruning strategies, such as alpha-beta, benefit strongly from proper move ordering, i.e., by searching the best element first. A wide range of techniques have been developed over the years to achieve good move ordering, and improved tree pruning, in the field, in general and in particular, in the alpha-beta search, have been extensively studied. Inspired by the formerly unrelated field of Adaptive Data Structures (ADSs), we had previously introduced the History-ADS technique, which employs an adaptive list to achieve effective and dynamic move ordering, in a domain independent fashion. Our previous results confirmed that it performs well in a very wide range of cases, and in varied types of board games. However, our previous work did not compare the performance of the History-ADS heuristic to any established move ordering strategy. In an attempt to address this problem, we present here a comparison to two well-known, acclaimed strategies, which operate on a similar philosophy to the History-ADS, namely, the History Heuristic, and the Killer Moves technique. We also introduce, in this work, a mechanism by which these established move ordering strategies can be approximated, or directly implemented, in terms of ADSs. We confirm that, in a wide range of two-player and multi-player games, at various points in the game’s progression, the History-ADS performs at least as well as these strategies, and, in fact, outperforms them in the majority of cases.