一种新的博弈树迭代向前剪枝搜索
|
摘要
针对博弈树迭代加深搜索和向前剪枝搜索中误剪最佳分支的弱点,利用向前剪枝搜索与预评估搜索间的双重迭代调用,提出了一种新的博弈树迭代向前剪枝搜索方法.预评估搜索通过节点排序及调整剪枝比率可以更加准确地选取排序在前的最佳分支,进而使迭代向前剪枝搜索实现在预评估所保留的最佳分支方向进行深度搜索,二者迭代相互调用以提高向前剪枝搜索的有效性及效率.定性分析与中国象棋计算机博弈实验结果表明,迭代向前剪枝搜索提高了实时行棋决策的效率和效果,与α-β剪枝搜索相比,提高的搜索效率超过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 newiterative 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 showthat 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.
Aiming at the weakness of incorrectly pruning the optimal subtrees in the iterative deepening-search and forward-pruning search for game-tree,a newiterative 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 showthat 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.
引文
[1]王亚杰,邱虹坤,吴燕燕,等.计算机博弈的研究与发展[J].智能系统学报,2016,11(6):788-798.(WANG Ya-jie,QIU Hong-kun,WU Yan-yan,et al.Research and development of computer games[J].CAAI Transactions on Intelligent System,2016,11(6):788-798.)
[2]李学俊,王小龙,吴蕾,等.六子棋中基于局部“路”扫描方式的博弈树生成算法[J].智能系统学报,2015,10(2):267-272.(LI Xue-jun,WANG Xiao-long,WU Lei,et al.Game tree generation algorithm based on local-road scanning method for connect 6[J].CAAI Transactions on Intelligent System,2015,10(2):267-272.)
[3]Silver D,Huang A,Maddison C J,et al.Mastering the game of Go with deep neural networks and tree search[J].Nature,2016,529(7587):484-489.
[4]李焕哲,吴志健,郭肇禄.两阶段多峰优化算法求解纳什均衡[J].武汉大学学报(理学版),2016,62(5):444-450.(LI Huan-zhe,WU Zhi-jian,GUO Zhao-lu.Two-stage multimodel optimization algorithm for solving nash equilibrium[J].Journal of Wuhan University(Natural Science),2016,62(5):444-450.)
[5]蔡屾.一种中国象棋机器博弈剪枝策略的改进方法[J].国外电子测量技术,2016,35(3):47-49.(CAI Shen.Improved pruning strategy of Chinese chess machine game[J].Foreign Electronic Measurement Technology,2016,35(3):47-49.)
[6]王溪波,王彬,赵海,等.基于HOG特征的优化区域模板匹配检测[J].沈阳工业大学学报,2016,38(6):667-673.(WANG Xi-bo,WANG Bin,ZHAO Hai,et al.Template matching detection for optimized region based on HOG features[J].Journal of Shenyang University of Technology,2016,38(6):667-673.)
[7]Nijssen J A M,Winands MH M.Search policies in multi-player games[J].International Computer Chess Association Journal,2013,36(1):3-21.
[8]吕艳辉,宫瑞敏.计算机博弈中估值算法与博弈训练的研究[J].计算机工程,2012,38(11):163-166.(LYan-hui,GONG Rui-min.Study on valuation algorithm and game training in computer game[J].Computer Engineering,2012,38(11):163-166.)
[9]刘子正,卢超,张瑞友.基于蒙特卡罗树搜索的“2048”游戏优化算法[J].控制工程,2016,23(4):550-555.(LIU Zi-zheng,LU Chao,ZHANG Rui-you.An algorithm for the game of 2048 based on Monte Carlo tree search[J].Control Engineering of China,2016,23(4):550-555.)
[10]张海峰,刘当一,李文新.通用对弈游戏:一个探索机器游戏智能的领域[J].软件学报,2016,27(11):2814-2827.(ZHANG Hai-feng,LIU Dang-yi,LI Wen-xin.General game playing:a research field for exploring machine intelligence in games[J].Journal of Software,2016,27(11):2814-2827.)
[11]岳金朋,冯速.中国象棋Alpha-Beta搜索算法的研究与改进[J].北京师范大学学报(自然科学版),2009,45(2):156-160.(YUE Jin-peng,FENG Su.Improvement on AlphaBeta search algorithm in Chinese chess[J].Journal of Beijing Normal University(Natural Science),2009,45(2):156-160.)
[12]苏攀,王熙照,李艳.基于不平衡学习的分类器博弈模型及其在中国象棋中的应用[J].计算机研究与发展,2011,48(5):841-847.(SU Pan,WANG Xi-zhao,LI Yan.Modeling chess strategy by classifier based on imbalance learning and application in computer Chinese chess[J].Journal of Computer Research and Development,2011,48(5):841-847.)
[2]李学俊,王小龙,吴蕾,等.六子棋中基于局部“路”扫描方式的博弈树生成算法[J].智能系统学报,2015,10(2):267-272.(LI Xue-jun,WANG Xiao-long,WU Lei,et al.Game tree generation algorithm based on local-road scanning method for connect 6[J].CAAI Transactions on Intelligent System,2015,10(2):267-272.)
[3]Silver D,Huang A,Maddison C J,et al.Mastering the game of Go with deep neural networks and tree search[J].Nature,2016,529(7587):484-489.
[4]李焕哲,吴志健,郭肇禄.两阶段多峰优化算法求解纳什均衡[J].武汉大学学报(理学版),2016,62(5):444-450.(LI Huan-zhe,WU Zhi-jian,GUO Zhao-lu.Two-stage multimodel optimization algorithm for solving nash equilibrium[J].Journal of Wuhan University(Natural Science),2016,62(5):444-450.)
[5]蔡屾.一种中国象棋机器博弈剪枝策略的改进方法[J].国外电子测量技术,2016,35(3):47-49.(CAI Shen.Improved pruning strategy of Chinese chess machine game[J].Foreign Electronic Measurement Technology,2016,35(3):47-49.)
[6]王溪波,王彬,赵海,等.基于HOG特征的优化区域模板匹配检测[J].沈阳工业大学学报,2016,38(6):667-673.(WANG Xi-bo,WANG Bin,ZHAO Hai,et al.Template matching detection for optimized region based on HOG features[J].Journal of Shenyang University of Technology,2016,38(6):667-673.)
[7]Nijssen J A M,Winands MH M.Search policies in multi-player games[J].International Computer Chess Association Journal,2013,36(1):3-21.
[8]吕艳辉,宫瑞敏.计算机博弈中估值算法与博弈训练的研究[J].计算机工程,2012,38(11):163-166.(LYan-hui,GONG Rui-min.Study on valuation algorithm and game training in computer game[J].Computer Engineering,2012,38(11):163-166.)
[9]刘子正,卢超,张瑞友.基于蒙特卡罗树搜索的“2048”游戏优化算法[J].控制工程,2016,23(4):550-555.(LIU Zi-zheng,LU Chao,ZHANG Rui-you.An algorithm for the game of 2048 based on Monte Carlo tree search[J].Control Engineering of China,2016,23(4):550-555.)
[10]张海峰,刘当一,李文新.通用对弈游戏:一个探索机器游戏智能的领域[J].软件学报,2016,27(11):2814-2827.(ZHANG Hai-feng,LIU Dang-yi,LI Wen-xin.General game playing:a research field for exploring machine intelligence in games[J].Journal of Software,2016,27(11):2814-2827.)
[11]岳金朋,冯速.中国象棋Alpha-Beta搜索算法的研究与改进[J].北京师范大学学报(自然科学版),2009,45(2):156-160.(YUE Jin-peng,FENG Su.Improvement on AlphaBeta search algorithm in Chinese chess[J].Journal of Beijing Normal University(Natural Science),2009,45(2):156-160.)
[12]苏攀,王熙照,李艳.基于不平衡学习的分类器博弈模型及其在中国象棋中的应用[J].计算机研究与发展,2011,48(5):841-847.(SU Pan,WANG Xi-zhao,LI Yan.Modeling chess strategy by classifier based on imbalance learning and application in computer Chinese chess[J].Journal of Computer Research and Development,2011,48(5):841-847.)