Research And Implementation Of Chinese Chess Game Tree Search Algorithm

Computer gaming is one of the first tasks of artificial intelligence. Compared with the developed computer game of chess, Chinese chess computer game studies are still developing. With the development of artificial intelligence technology, Chinese chess computer game problem has attracted a growing number of scholars into it. In this article, basing on the proven technology of chess computer game and combining with the development of Chinese chess computer game, the core game tree search algorithms in the move generator are studied deeply.Firstly, through the research of the Chinese chess game system, the data structures in Chinese chess system are designed, the move generator and evaluation functions of the situation are realized.Secondly, various pruning algorithms based on exhaustive search strategies are analysed, the iterative deepening method is taken to prevent the strategic error caused by “horizon effect”.Furthermore, B* algorithm based on best-first strategy was analysed, aiming at the problem of B* algorithm’s relying too much on evaluation function, the BSP search algorithm based on probability is designed and implemented.Finally, according to different search strategies, the pruning algorithm as the core of the move generator and BSP search algorithm based on probability are achieved respectively. In VC++6.0 environment, the Chinese chess man-machine system is built, and the efficiency and accuracy of the move generator are tested.