Research And Implmentation On Chinese Chess Game Tree Search Algorithm

Computer game is a traditional researching field of artificial intelligence(Al).It provide a test platform for Al. Apply some theories and methods of Al in computer game, we can prove the validity of those by means of testing the level of game system. In turn, the fruits obtained through researching the computer game are used in the other realms of Al. So, they supplement and promote each other. Chess computer game has a long history, has acquired great success. Whereas, many techniques of chinese chess computer game are not mature enough, with deeper study on artificial intelligence, research on Chinese chess computer game becomes a hot spot of AI.In this thesis, chinese chess game tree search algorithm and game systems is researched, introduces the key technology about chinese chess computer game, analysis the effective of evaluation function and data structure design. In-depth study the characteristics of the game tree, andα-βpruning based on the game tree search algorithm improvement strategies, including the principle of the window, transposition table, history heuristic, iterative deepening, null move, etc., combination of different improvement strategies get different search engines, test these engines performance verify their pruning efficiency. Studied the quiescence search, quiescence search and selective extended search avoid the greatly fluctuant evaluation risk that result from changing chessman and checkImplement a human-computer game system, statistical the leaf nodes and time used by search engine, combination of different optimization strategies to get different search engines, through a variety of experiments proof that integrated strategy improved the search algorithm pruning efficiency. Select the search engine which pruning more efficient inject quiescence search to improve playing strength, play game with each other, proved the most efficient pruning search algorithm—PVSHNTIQ playing strength is highest.