Computer Science Seminar Series
NEUCHESS : An Implementation of Chinese Chess Computer Game
November 14, 3:00pm
Weir Hall, Room 235
Xiaofei (Sophie) Nan
Decision game programming is an important field of Artificial Intelligence. As chess computer game has won great success, Chinese chess, a game with large popularity and higher computational complexity than chess, has been researched extensively. A Chinese chess project, NEUCHESS, won the championship of the Chinese chess in the 11th World Computer Olympiad. This project mainly focuses on move generation and searching strategies.
Bitmap board representation was introduced to improve searching efficiency by accelerating local decision makings. Hash table was used to enable efficient position comparison and to make or unmake a move by a Boolean operator XOR. By storing the moves generated off-line, we significantly speed up move generation. Searching is another important component of a chess computer game. Compared with basic Alpha-Beta pruning technique, Principal Variation Search (PVS), which views the left child of a node as the best child, is more effective in finding a minimum tree. Additionally, Null-Move and History Pruning are used in forwarding pruning. To alleviate the horizon effect, Quiescent search, Check Extension, and Mate Extension, are included in PVS.