Parallel adversarial search to enhance decision-making in games
Abstract
This thesis investigates the process and the challenges of developing a parallel
implementation of an adversarial search algorithm that can be deployed on shared
memory architectures, such as big multi-core servers. The primary intention is to
produce faster algorithmic performance of adversarial search through parallelism; for
instance, a search within a (two-player) game tree, identifying the best move from the
current player’s perspective.
This thesis describes a three segment process for improving AI performance through
parallelism. The first phase involves selecting an AI approach to simulate decision making in a virtual game world. The second phase covers the selection of a parallel
programming technique of parallel invoking to enhance performance of the AI approach
that executes sequentially. The final phase defines the performance evaluation approach
that outlines the criteria in order to evaluate the performance of the AI algorithm. The
two evaluative parameters concerned in gauging the level of performance are the speed
of the search result and the quality of the search result.
Our methodology is utilised to develop parallel variants of a base sequential Minimax
with Alpha-Beta Pruning algorithm. Three different games are implemented as
instances of this general parallel Minimax algorithm and evaluated on their level of
performance using a state-of-the-art multi-core server (64 cores). The three games
included are TicTacToe (on an extended 7x7 board), Treblecross (on an extended 60x1
board) and GoMoku (on a reduced 11x11 board).
These parallel variants achieve a modest absolute speed-up over the sequential base on
the three test case games. The best absolute speed-up gain achieved on each test case
game was 8 for TicTacToe, 11 for Treblecross, and 11 for GoMoku. GoMoku generates
the most reliable and consistent absolute speed-up increases across the entire core usage
and set of board configurations.
Despite the modest gains, the absolute speed-up achieved is significantly below the
linear speed-up threshold in all test case games and board configurations. This can be
equated to increased memory consumption and increased memory residency for
programs that use many threads. In addition to this, memory overhead due to copying
operations to enable parallelism on top of the core Minimax algorithm is also a
contributing factor.