Data Structure Design And Game-Tree Search Algorithm Research For Chinese Chess Computer Game

Artificial Intelligence (AI) is the synthesis of computer knowledge, psychology and philosophy. Chinese chess computer game belongs to the field of artificial intelligence research. Now, people have obtained success in Othello, Gobang, chess with computer game, however, Chinese chess computer game which has huger searching-tree, is still at the initial stage. Based on practical experience in Chinese chess computer game, the following work has mainly been done in this paper:Firstly, the software data structure of Chinese chess computer game is designed. The template matching method is used for Knight and Elephant move-generation, and prefabricated table which based on Bitrank and Bitfile is used for the move-generation of Rook, Cannon, Pawn and so on. And because the methods of template matching and prefabricated table are needless on the border judgement and the game-tree search is replaced by table-query by these ways, the speed of move-generation is increased, and then the rate of game-tree search is enhanced.Secondly, the research about game-tree searching has been done. PVS(Minimal Window Search), which is derived from alpha-beta search, is used to increases the rate of pruning; In order to adjust search priorities effectively, these heuristic Algorithms such as translation table, history heuristic table, iterative deepening algorithm are used. Quiescence search and selective extended search are used. it avoid the greatly fluctuant evaluation risk that result from changing chessman and check. Null-move is used to increase about tow tiers for search depth. What is more, we do betterment for Null-move that makes it safer in use.Finally, it outlines the main points of evaluation function. The practice results indicate the algorithm isfeasible, and the program shows a good performance.