A new iterative forward-pruning search for game tree
SUN Ruo-ying
GONG Yi-shan
ZHAO Gang
Abstract：Aiming at the weakness of incorrectly pruning the optimal subtrees in the iterative deepening-search and forward-pruning search for game-tree, a new iterative forward-pruning search method for game tree was proposed through adopting the reciprocal iterative calls between the forward-pruning search and pre-estimation search.The optimal subtrees with high priority could be selected more exactly through ordering the node and adjusting the pruning ratio in the pre-estimation search, which made the iterative forward-pruning search realize the deep research in the direction of optimal subtrees preserved with the pre-estimation search, and both methods could iteratively call each other to improve the effectiveness and efficiency of forward-pruning search.The qualitative analysis and the experimental results of Chinese chess computer game show that the effectiveness and efficiency of real time move decision can be improved with the iterative forward-pruning search.Compared with the α-β pruning search, the search efficiency gets improved more than 160 times, and the game effect with the win-lost ratio of nearly 7 times is obtained.
Keywords：artificial intelligencegame-tree searchα-β pruningforward-pruning searchiterative-deepening searchevaluation functionChinese chess gamereal time move decision
Publication Date：2017-01-01
Online Publishing Date：2025-08-15(First online date of this platform, not the publication date of the document)
Pages：7( 304-310 )