Two-ply iterative deepening in Chinese-chess computer game

In Chinese-chess computer game (CCCG), a computer player could find the best move for a given board position by using alpha-beta search algorithm. The technique of iterative deepening is an enhancement to alpha-beta search. It is helpful to reduce the size of game tree. In this paper, we improved the prototypical one-ply iterative deepening (OPID) and proposed two-ply iterative deepening (TPID). In game tree searching, we extend the search by two plies from the previous iteration. An iterated series of 2-ply, 4-ply, 6-ply, --- searches is carried out. In the experiments, we validate that TPID is feasible and effective. Through applying TPID to minimax search and alpha-beta search respectively, we found that the total number of nodes generated in TPID minimax search and TPID alpha-beta search are all reduced compared with OPID.