A Trappy Alpha-Beta Search Algorithm in Chinese Chess Computer Game

摘要

In this paper, we propose an improved alpha-beta search algorithm, named trappy alpha-beta (simply Trap_B~A), for game-tree in order to identify and set the potential traps in the game playing. Trap_B~A can be regarded as an extension of the traditional alpha-beta search algorithm which ties to predict when the opponent might make a mistake and select such moves that can most likely lead the an opponent into the trap by comparing the various scores returned through iterative deepening technology. In Trap_B~A, we define two basic components: 1) defining a trap by considering the nature of alpha-beta search algorithm and referring the evaluation value returned by iterative deepening; and 2) evaluating a trap by calculating the probability that the opponent fall into the trap and the advantage followed when the opponent fall into it. In our experiment, we test the performance of Trap_B~A in comparison with three game-tree search algorithms, i.e., min-max, trappy minimax, and alpha-beta, by playing with four testing opponents (their depthes are 7, 8, 9, and 10 respectively), which are obtained form a typical Chinese chess computer game programme-Xqwizard (http://www.xqbase.com/). The comparative results show that our designed Trap_B~A can effectively find and set the traps in the playing with opponents.