Design And Implementation Of Othello Based On Improved Chess Game Tree Search

The research of Artificial Intelligence is a challenge work of human being. The AI domain is what the research scholars fighting for all long. And to let the chess games having AI is an important part of the AI area. Chess game AI commonly comprises the game tree search and the evaluation of the chessboard's situation. Some high intelligence chess games always provide with the machine learning ability which can let the system become cleverer via playing with others. The chess game tree search algorithm is the core of chess's AI which is commonly among almost all the chess games. This paper work is a research and analysis of the chess game tree search algorithm and then to design and implement an Othello game system based on the improved chess game tree search algorithm.The main works and achievements of the paper are as follow:(1) Research and analysis of the core part of chess game AI——chess game tree search that comprise the min-max search, alpha-beta search, heuristic search, aspiration window and selected cutoff strategy; At last, the parallel search. The design and implement of the Othello AI system are based on this comprehensive and systemic technical theory.(2) The Othello AI system is designed and implemented based on the object-oriented method. The design work abstracts the Othello AI to the four aspect——reasoning, analysis, memory and learning as the human beings which is different from the design based on the process of the algorithm.(3) At the Othello game tree search algorithm aspect, there are some improved works to speed up the efficiency such as using two transposition tables, shallow exploration, killer heuristic and selecting the sort node dynamically. This heuristic method improves the cutoff of the chess game tree search. And then, this design using 0-window search method which can improves the efficiency and is also propitious to extend the parallel implement.(4) At the Othello's chess game rule and the evaluation aspect, this design uses the bit-board data structure and the pattern match evaluation method which improve the running efficiency and the game's AI. The bit-board design and the pattern evaluation is the advanced design method at the present stage and also the other chess games develop trends.(5) At the Othello system's opening book and self-learning aspect: The opening book doesn't use the traditional tree data structure, which use the one-dimensional array based on the binary search. And the self-learning ability not only can learn to become cleverer, but also high efficiency. At last, a test given shows that the improved heuristic chess game tree search are better than the pure alpha-beta search and the traditional heuristic search. And a test also shows that the game's AI has reached a quite high level that has senses of research and usage.