University of Ottawa - Carleton University
Ottawa-Carleton Institute for Computer Science (OCICS) Presentation
|
October 12, 2012 @ 10:00a.m.
"Improving state-of-the-art multi-player game playing with adaptive structures".
|
Speaker: Spencer Polk
Location: 3101 CB (Canal Building) |
ABSTRACT
In the field of game playing, Two Player Zero-Sum (TPZS) games, such as Chess and Go, have been extensively studied, and well-evolved strategies exist. However, the related field of Multi-Player Zero-Sum (MPZS) game playing has seen comparatively little research, with dominant techniques largely being an extension of existing TPZS games to an N-player environment. To address the problem of multiple opponents, we propose the previously unreported scheme of merging of two completely unrelated fields, namely those of MPZS game playing and Adaptive Data Structures (ADS). In this work, which, to the best of our knowledge is of a pioneering sort, we shall present a modification to an existing state-of-the-art MPZS game playing algorithm, namely, the Best-Reply Search (BRS). Our enhanced modification uses an ADS to rank the opponents in terms of the respective levels of the threats that they pose to the player modeled by the AI algorithm. This enhancement, referred to as Threat-BRS, has been rigorously tested, and the results conclusively demonstrate that while it cannot perform worse than the original BRS in any scenario, it almost always possesses superior node pruning than the original BRS. We present here two variants, referred to as A and B, which are distinguished by when, during the execution of the BRS, they query the ADS. |
| Return to Schedule |
|
