Search Constraints

Start Over
Filtering by: Creator Polk, Spencer Remove constraint Creator: Polk, Spencer

Search Results

  • Challenging established move ordering strategies with adaptive data structures

    Resource Type:
    Conference Proceeding
    Creator:
    Oommen, B. John and Polk, Spencer
    Abstract:
    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, that is, searching the best element first. Inspired by the formerly unrelated field of Adaptive Data Structures (ADSs), we have previously introduced the History-ADS technique, which employs an adaptive list to achieve effective and dynamic move ordering, in a domain independent fashion, and found that it performs well in a wide range of cases. However, 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, the History Heuristic, and the Killer Moves technique. We find 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.
    Date Created:
    2016-01-01

  • Enhancing history-based move ordering in game playing using adaptive data structures

    Resource Type:
    Conference Proceeding
    Creator:
    Polk, Spencer and Oommen, B. John
    Abstract:
    This paper pioneers the avenue of enhancing a well-known paradigm in game playing, namely the use of History-based heuristics, with a totally-unrelated area of computer science, the field of Adaptive Data Structures (ADSs). It is a well-known fact that highly-regarded game playing strategies, such as alpha-beta search, benefit strongly from proper move ordering, and from this perspective, the History heuristic is, probably, one of the most acclaimed techniques used to achieve AI-based game playing. Recently, the authors of this present paper have shown that techniques derived from the field of ADSs, which are concerned with query optimization in a data structure, can be applied to move ordering in multi-player games. This was accomplished by ranking opponent threat levels. The work presented in this paper seeks to extend the utility of ADS-based techniques to two-player and multi-player games, through the development of a new move ordering strategy that incorporates the historical advantages of the moves. The resultant technique, the History-ADS heuristic, has been found to produce substantial (i.e, even up to 70%) savings in a variety of two-player and multi-player games, at varying ply depths, and at both initial and midgame board states. As far as we know, results of this nature have not been reported in the literature before.
    Date Created:
    2015-01-01