一种新的博弈树迭代向前剪枝搜索  

A new iterative forward-pruning search for game tree

作　　者：孙若莹[1] 宫义山[2] 赵刚[1] 

机构地区：[1]北京信息科技大学信息管理学院,北京100192 [2]沈阳工业大学信息科学与工程学院,沈阳110870

出　　处：《沈阳工业大学学报》2017年第3期304-310,共7页Journal of Shenyang University of Technology

基　　金：国家自然科学基金资助项目(61572079);北京市教委科技重点项目(KZ201411232036)

摘　　要：针对博弈树迭代加深搜索和向前剪枝搜索中误剪最佳分支的弱点,利用向前剪枝搜索与预评估搜索间的双重迭代调用,提出了一种新的博弈树迭代向前剪枝搜索方法.预评估搜索通过节点排序及调整剪枝比率可以更加准确地选取排序在前的最佳分支,进而使迭代向前剪枝搜索实现在预评估所保留的最佳分支方向进行深度搜索,二者迭代相互调用以提高向前剪枝搜索的有效性及效率.定性分析与中国象棋计算机博弈实验结果表明,迭代向前剪枝搜索提高了实时行棋决策的效率和效果,与α-β剪枝搜索相比,提高的搜索效率超过160倍,同时取得了胜负比近7倍的博弈效果.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.

关 键 词：人工智能 博弈树搜索 Α-Β剪枝 向前剪枝搜索 迭代加深搜索 评估函数 中国象棋博弈 实时行棋决策 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]