Massively parallel implementation of a pattern based evaluation function for computer chess

• Main Author: U. G. Namal Prasanna Kumara
• Other Authors: Sisira, K. Amarasinghe
• Format: Theses and Dissertations
• Language: English
• Published: 2008
• Subjects: DRNTU::Engineering::Computer science and engineering::Computing methodologies::Artificial intelligence; DRNTU::Engineering::Computer science and engineering::Computing methodologies::Pattern recognition
• Online Access: http://hdl.handle.net/10356/13312
• Institution: Nanyang Technological University

A considerable amount of research has been carried out on efficient algorithms for computer chess on both the single instruction multiple data (SIMD) and multiple instruction multiple data (MIMD) machines. However, much of these algorithms have been written for the game tree search process rather than in incorporating chess knowledge itself. It has been proved that SIMD machines could not efficiently parallelize game tree search algorithms, thus foregoing the power of massive parallelism realizable from the SIMD model to computer chess. Very little research has been done in using SIMD models for implementing knowledge rich chess programs. This thesis describes how existing knowledge of certain positional features of a chess game can be implemented in a parallel evaluation function using the SIMD model. Since SIMD machines are very efficient in pattern matching, it is possible to examine thousands of feature patterns associated with chess positions in parallel. With the SIMD model of massive parallelism, even up to 64K patterns can be checked in just a few cycles. Results obtained show that the efficiency of an evaluation function based on the SIMD model is higher with a larger number of processors. In addition, the results suggest that a parallel evaluation is an ideal method to incorporate a large knowledge base into a chess program without compromising its speed of search.