网络出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20150326.1020.008.html

六子棋中基于局部“路”扫描方式的博弈树生成算法

李学俊1,2，王小龙1，吴蕾1，刘慧婷1

(1.安徽大学 计算机科学与技术学院,安徽 合肥 230601； 2.安徽大学 计算智能与信号处理重点实验室，安徽 合肥 230039)

摘要：针对六子棋博弈比赛中基于“路”的全局扫描方式的博弈树生成算法效率较低问题，首先分析了基于“路”的全局扫描方式的计算规则和估值分析，然后将博弈树生成算法中的全局扫描方式改进为局部扫描方式，并给出其计算规则和估值分析，接着设计了基于局部扫描方式的博弈树生成算法，并集成到Alpha-Beta剪枝算法中。最后从搜索效率和博弈水平2个角度对全局扫描和局部扫描进行实验，实验结果表明，局部扫描方式在比赛时间要求的情况下，能够大幅度提高搜索效率，并且博弈水平显著优于全局扫描方式。

关键词：机器博弈；六子棋；路；局部扫描；博弈树；剪枝算法；估值

DOI:10.3969/j.issn.1673-4785.201401022

中图分类号：TP31文献标志码：A

收稿日期：2014-01-09. 网络出版日期：2015-03-26.

基金项目：国家自然科学基金资助项目(61202227).

作者简介：

中文引用格式：李学俊，王小龙，吴蕾,等. 六子棋中基于局部“路”扫描方式的博弈树生成算法[J]. 智能系统学报， 2015, 10(2): 267-272.

英文引用格式：LI Xuejun, WANG Xiaolong, WU Lei， et al. Game tree generation algorithm based on local-road scanning method for connect 6[J]. CAAI Transactions on Intelligent Systems, 2015, 10(2): 267-272.

Game tree generation algorithm

based on local-road scanning method for connect 6

LI Xuejun1,2, WANG Xiaolong1, WU Lei1, LIU Huiting1

(1.School of Computer Science and Technology, Anhui University, Hefei 230601, China; 2.Intelligent Computing and Signal Processing Laboratory, Anhui University, Hefei 230039, China)

Abstract：Aiming at the problem that the game-tree generation algorithm generated by global scanning method is low in efficiency in the connect 6, this paper analyzes the calculation rules and valuation analysis of the global scanning method based on "road". Secondly, it develops the global scanning method of the game-tree generation algorithm into local scanning method, and introduces the calculation rules and valuation analysis. The game-tree generation algorithm is a local scanning method designed and integrated into the alpha-beta pruning search. Finally, the global and local scanning experiments are carried out from the two perspectives of search efficiency and playing skill. The experimental results showed that local scanning could greatly improve search efficiency within the competition time. The game ability is superior to that of the global scanning method.

Keywords：computer game; connect 6; road; local scanning; game tree; pruning algorithm; evaluation

通信作者：李学俊.E-mail:xjli@ahu.edu.cn.

机器博弈(即计算机博弈)是人工智能领域的分支，同时也是该领域公认的最具挑战性的研究课题之一。棋类博弈是人类所能从事的智能活动之一，如果可以掌握博弈的本质，也就说明可以帮助人类从事智能活动。因为存在于棋类博弈的原则或许就存在于人类的智能活动中[1]。……