Game tree search on a massively parallel SIMD machine : an algorithmic study with computer chess

Game tree search on a massively parallel SIMD machine : an algorithmic study with computer chess

A parallel game tree search algorithm is presented in this thesis to verify the possibility of efficient use of a Single Instruction Multiple Data (SIMD) machine for computer game playing. It follows a loop of search and load balancing. In order to eliminate the serious processor starvation that is...

Full description

Saved in:
Bibliographic Details
Main Author: He, Shaojun.
Other Authors: Sisira K Amarasinghe
Format: Theses and Dissertations
Language:English
Published: 2008
Subjects:
DRNTU::Engineering::Computer science and engineering::Computing methodologies::Artificial intelligence
Online Access:http://hdl.handle.net/10356/13352
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
Description
Summary:A parallel game tree search algorithm is presented in this thesis to verify the possibility of efficient use of a Single Instruction Multiple Data (SIMD) machine for computer game playing. It follows a loop of search and load balancing. In order to eliminate the serious processor starvation that is usually present in a SIMD game tree search, a new load balancing scheme is proposed as a part of this algorithm which provides massive parallelism whilst being in control of the search overhead. Besides, a dynamic triggering mechanism that is especially suited for a complex game such as Chess is used to optimally balance the search and load balancing. Furthermore, a search procedure with useful heuristic enhancements is designed in detail to reduce the search overhead and the synchronization overhead.

Similar Items