Title :
Two-ply iterative deepening in Chinese-chess computer game
Author :
Wang, Xi-Zhao ; He, Yu-lin ; Su, Pan ; Li, Wen-liang
Author_Institution :
Key Lab. for Machine Learning & Comput. Intell., Hebei Univ., Baoding, China
Abstract :
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.
Keywords :
computer games; iterative methods; search problems; tree data structures; Chinese-chess computer game; alpha-beta search algorithm; game tree; one-ply iterative deepening; two-ply iterative deepening; Computational intelligence; Cybernetics; Educational institutions; Helium; Iterative algorithms; Machine learning; Mathematics; Minimax techniques; Prototypes; Rivers; Alpha-beta search algorithm; Chinese Chess Computer Game; Game Tree; Minimax search; One-Ply Iterative Deepening; Two-Ply Iterative Deepening;
Conference_Titel :
Machine Learning and Cybernetics, 2009 International Conference on
Conference_Location :
Baoding
Print_ISBN :
978-1-4244-3702-3
Electronic_ISBN :
978-1-4244-3703-0
DOI :
10.1109/ICMLC.2009.5212141
