A New Game-tree Search Algorithm And Its Application Research

Computer game is a very popular field in AI, Game-tree search is the key core of computer game. This paper gives profound research is game-tree search algorithm and game-tree optimization technique. The author combines theory and practice presents the following results:⑴It puts forward a new game-tree search algorithms which based on breadth-first continuously null-window test method. Experiments have proved that the efficiency of this algorithm out-performs the popular algorithms such as PVS and MTD(f) which are considered as having most high efficiencies. The new method also has some advantages in iterative-deepening search, and the search limit of this algorithm is smaller than minimal game-tree. Thus a wide application can be promised by this algorithm.⑵It gives a new technique of optimizing game tree: sub-game-tree reuse. This technique can improve deep search efficiency by 10 percent and more with deeper depth but no extra expenditure. The sub-game-tree reuse technique has added effect in limit time game or must victory phase. Of course, it has a better application value.⑶It gives a new proof of the theory about the number bottom-nodes of minimal game-tree, and points out the deficiency of old method. It also clarifies the misunderstanding concepts of minimal tree and window searching efficiency and gives the correct conclusion.⑷In this paper a high level human-machine playing gobang system is developed, and the author proves that by using evaluation function of rough value the better whole effect in depth searching can acquire, and the extending evaluating technique of the evaluation function also can reduce the horizon effect. The author also testifies that with the help of playing gobang knowledge, the move-generation function can produce good results in human-computer play gobang system. The author also extends use of minimax search algorithm in the optimizing game-tree area and achieves good result. With all these ideas and experiments, the paper provides a good reference to fellow researchers.