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.