A Hybrid Game Tree Algorithm And Its Application Research In Chinese Chess Man-machine Game

The problem of man-machine game is very popular precently. Match is described as a fruit fly of the artificial intelligence by experts. That's to say human's research to the machine has achieved massive research results. These achievements have played an important influence on a more widespread domain. Chess is a kind of Games of Perfect Information,which means that both sides know clearly if every chessman is existed or not and where they are at any time completely.It will be clear as long as you take a look at the chessboard. Chesses such as jump chess,I-go and chess all belong to Games of Perfect Information. Through overseas researchers' exploration of chess gambling system for more than 50 years, IBM Corporation developed supercomputer "Dark Blue" in 1997, and has defeated world chess master Ksparov;while the Chinese chess history is more glorious, the level of the Chinese chess computer game is not easier than chess.Not only the number of scholar who joines in the computer Chinese chess game is little,but also information which is worth of reference is few. The difficulty of Chinese chess computer game mostly lies in the greater model of chessboard, the more different move generation, the more complex change. The Chinese chess man-machine gambling system is generally divided into: the data expression, move generation, the search engine, evaluation function, the database of starting game and the database of aftermatch.By describing and analyzing the module of chess program "QZM" such as its data expression,move generation,search engine,evaluation function and database of starting game,this article expounds the Chinese chess program's principle of design and realization,furthermore,it puts forward a hybrid search algorithm which combined by the improved transposition table and some popular search algorithm(null-move pruning,history heuristic,interative deepening and so on) ,and it improve calculation efficency of the program obviously after being applied to the chess program. "QZM" won the new personality award in The First China Chess computer match on Aug.6th 2006.