标题

Size: px

Start display at page:

Download "标题"

兢助慕
7 years ago
Views:

1 第 10 卷第 2 期智能系统学报 Vol 年 4 月 CAAI Transactions on Intelligent Systems Apr DOI: / j.issn 网络出版地址 :http: / / / kcms / detail / TP html 六子棋中基于局部路扫描方式的博弈树生成算法李学俊 1,2, 王小龙 1, 吴蕾 1 1, 刘慧婷 (1. 安徽大学计算机科学与技术学院, 安徽合肥 ; 2. 安徽大学计算智能与信号处理重点实验室, 安徽合肥 ) 摘要 : 针对六子棋博弈比赛中基于路的全局扫描方式的博弈树生成算法效率较低问题, 首先分析了基于路的全局扫描方式的计算规则和估值分析, 然后将博弈树生成算法中的全局扫描方式改进为局部扫描方式, 并给出其计算规则和估值分析, 接着设计了基于局部扫描方式的博弈树生成算法, 并集成到 Alpha Beta 剪枝算法中最后从搜索效率和博弈水平 2 个角度对全局扫描和局部扫描进行实验, 实验结果表明, 局部扫描方式在比赛时间要求的情况下, 能够大幅度提高搜索效率, 并且博弈水平显著优于全局扫描方式关键词 : 机器博弈 ; 六子棋 ; 路 ; 局部扫描 ; 博弈树 ; 剪枝算法 ; 估值中图分类号 :TP31 文献标志码 :A 文章编号 : (2015) 中文引用格式 : 李学俊, 王小龙, 吴蕾, 等. 六子棋中基于局部路扫描方式的博弈树生成算法 [ J]. 智能系统学报, 2015, 10( 2): 英文引用格式 :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): Game tree generation algorithm based on local road scanning method for connect 6 LI Xuejun 1,2, WANG Xiaolong 1, WU Lei 1, LIU Huiting 1 (1.School of Computer Science and Technology, Anhui University, Hefei , China; 2.Intelligent Computing and Signal Process ing Laboratory, Anhui University, Hefei , 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 al gorithm into local scanning method, and introduces the calculation rules and valuation analysis. The game tree gen eration 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 compe tition 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] 近年来, 国内外计算机博弈比赛, 极大地推动了计算机博弈问题的研究, 促进了计算机博弈理论和技术的发展棋类计算机博弈涉及的棋种较多, 六子棋就是其中之一, 它由台湾国立交通大学吴毅成教授发明六子棋竞赛规则很简单, 对弈双方分别执黑子和白

2 268 智能系统学报第 10 卷子, 在的方格棋盘上, 除了黑子先手第 1 步落一颗子外, 双方轮流落 2 颗子, 先在水平垂直或对角线上形成连续的 6 子 ( 或 6 子以上 ) 的一方为胜 [2] 六子棋由五子棋改良而来, 但是其复杂度却远大于五子棋 [3], 其中博弈树复杂度达到 , 状态空间复杂度达到 , 仅次于围棋, 与象棋相当或略高 [4] 作为刚兴起不久的棋类游戏, 六子棋的智能搜索算法研究较少博弈树搜索为计算机博弈的基本搜索算法, 它是从根节点向下递归搜索而产生的包含双方所有对弈过程的搜索树由于受搜索时间的严格约束, 博弈树能够搜索到的叶子节点极少属于末端节点 ( 即根据对弈规则可以判定比赛结果 ), 此时需要通过估值函数对叶子节点进行量化计算, 判断该叶子节点所处的棋局状态是有利于己方还是对方, 且计算其有利程度大小 [5] 在博弈树的扩展过程中会将双方可能的对弈过程展示出来, 首先对叶子节点进行估值, 再倒推计算根节点各分支节点的值, 选择估值最大的分支节点作为最佳解但是随着搜索深度的增加, 博弈树的节点数量成指数性增长在极大极小值算法的基础上,Alpha Beta 剪枝技术在搜索的过程中忽略了无用的节点, 并将其删除, 不对其估值, 删除无用节点时不会造成信息丢失, 不影响根节点各分支节点的估值, 提高了搜索速度 [6] 在深层次的递归搜索中广泛采用 Alpha Beta 剪枝算法为了提高计算速度, 本文采用 Alpha Beta 剪枝技术由于六子棋对弈规则的特殊性, 如果只考虑单个棋子对棋局的影响进行估值计算, 而未考虑棋子间的位置关系, 肯定会影响棋局状态的评估效果, 由此产生了基于棋形的扫描方式 [7 8] 常见的棋形主要分为六连长连活五眠五死五活四眠四死四活三眠三朦胧三活二眠二朦胧二等 [9] 文献 [2] 提出基于棋形的数据表示方法, 数据结构依赖于棋形, 将棋局的数据表示和局面知识结合起来, 提高搜索效率基于棋形的扫描方式将棋子间的位置关系联系起来, 通过产生某种棋形来表示对整个棋局状态的影响程度, 更具有直观性, 减少对单个棋子进行估值的不稳定性 ; 然而目前棋形是通过经验总结的, 人为因素影响很大, 不排除还存在其他种类, 这需要通过大量实验来确定大部分六子棋的估值计算都是基于棋形的扫描方式, 但是由于棋形的判断要求很高, 常见的棋形种类较多, 且每种棋形又存在多种落子方式 [10], 由此文献 [11] 提出路的扫描方式所谓路就在棋盘的水平垂直或对角线上出现连续 6 点连成一线 [11] 基于路扫描方式能有效降低棋形判断的复杂度, 通过路扫描方式的估值相对于通过棋形扫描方式估值较为简单, 实现方面也更加容易, 并且搜索时间较短文献 [12] 在传统的基于路的全局扫描方式上采用自学习的方法自动调整估值函数的参数, 提高搜索精度文献 [13] 在应用 Alpha Beta 剪枝搜索时引入并行计算, 大幅度提高搜索效率路扫描方式的引入避免了精确判断棋形的难题, 减少了计算量 ; 同时应用面向对象的思想, 将路的信息抽象成类, 易于实现基于路的扫描方式解决了因棋形判断不准确而影响博弈水平的问题, 但是应用博弈树搜索时, 在对每个子节点的扩展时都需要对棋盘进行全局扫描受博弈竞赛时间约束, 搜索深度和宽度都有所限制, 博弈水平也达不到理想要求因此本文在博弈树生成子节点时将基于路的全局扫描方式改进为局部扫描, 并设计基于局部路扫描方式的博弈树生成算法 1 基于路的全局扫描方式 1.1 计算规则 [1 4 K 子棋可用 connect( m,n,k,p,q) 表示 ], 对弈双方为黑方和白方, 黑方先走 connect( m,n,k,p,q) 的规则包括 :1) 棋盘的方格为 m 行 n 列, 即含 m n 个交叉点 ;2) 对弈时双方轮流落 p 颗棋子 ( 根据六子棋比赛黑方先手规则, 第 1 次落 q 颗棋子 );3) 在棋盘的水平垂直或对角线上先形成 k 连获胜若在规定时间内双方均无法获胜, 则判为平局 K 子棋中路的计算规则 :1) 水平方向 :m 行 (n - k + 1) 路 / 行, 如图 1 中 (a) 所示 ;2) 垂直方向 :n 列 (m - k + 1) 路 / 列, 类似于水平方向 ; 3) 左斜方向 : 由于 k 连需要 k 子连续相连, 在左斜方向前 k - 1 行不可能形成 k 连, 故左斜方向路数为 (m -k + 1) 行 (n - k + 1) 路 / 行, 如图 1 中 (b); 4) 右斜方向 :(n - k + 1) 列 (m - k + 1) 路 / 列, 类似于左斜方向 [1 5 六子棋是 K 子棋的一种 ], 采用方格棋盘, 可表示为 connect(19,19,6,2,1), 总路数为 N road = 3 N direct i = 0 ( i) (1) 式中 : N road 表示六子棋全局扫描总路数,

3 第 2 期李学俊, 等 : 六子棋中基于局部路扫描方式的博弈树生成算法 269 N direct ( i) 表示第 i 方向上的路数根据式 (1) 可得, 六子棋方格全局扫描的总路数为 924 图 1 水平及左斜方向路数计算示例 Fig.1 Road number of horizontal and left diagonal di rection 2 基于路的局部扫描方式应用 Alpha Beta 剪枝技术搜索时, 效率和精确 [1 6 度是非常重要又相互影响的因素 ] 文献 [2] 中指出棋局状态的变化均由新增的棋子引起, 在棋局中只有新增棋子的水平方向垂直方向和对角线方向上的棋形发生变化, 对其他位置棋形无影响在基于路的扫描过程中, 每步落子对棋局的影响是由该两落子在水平方向垂直方向和对角线方向上的路所引起, 与其他路没有关系, 故本文在博弈树生成时, 优化改进路的扫描方式 2.1 计算规则假设在棋盘的 (3,7) 位置模拟一个落子, 由图 2 可得在水平方向有 6 路包含该落子, 由此可得在局部扫描方式下, 每步落子所影响的路数计算如式 (5) 所示 N part = N direct N scan N chess (5) 式中 : N part 表示局部扫描每步落子影响的路数, N direct 表示每个方向所含的路数, N scan 表示一个落子所要扫描的方向数, N chess 表示每步的落子数 1.2 估值分析在路的信息表示中, 设置 n {0,1,2,3,4,5, 6} 表示该路中相同颜色棋子的个数, 设置 c { B, W } 表示路中棋子的颜色若某路中含 2 种颜色棋子, 表示该路不可能成为六连, 则初始值不变当某路中 c 为已方棋子颜色时分配不同的价值, 计算分配价值公式为 V own = f( n) (2) 式中 : V own 表示分配的价值, n 越大表明己方在该路越容易形成六连, 则分配的价值越大当某路中 c 为对方棋子颜色时分配不同的威胁值, 计算威胁值公式为 V threat = g( n) (3) 式中 : V threat 表示分配的威胁值, n 越大表明对方在该路越容易形成六连, 则分配的威胁值越大全局扫描估值可用己方所有路的价值之和减去对方所有路的威胁值之和表示全局扫描棋局估值 V total 可看作是每步落子后对当前棋局的影响程度大小, 即落子后棋盘全局扫描估值 V after 减去落子前棋盘全局扫描估值 V pre V total = V after - V pre (4) Fig.2 图 2 局部扫描水平方向路数计算示例 Road number of horizontal direction by the lo cal road scanning method 由式 (5) 可得, 一般情况下局部扫描的总路数为 :6 路 / 方向 4 方向 / 落子 2 落子 = 48 路, 大大小于全局扫描的总路数 924 局部扫描棋局估值 V total 即落子后棋盘局部扫描估值 V after 减去落子前棋盘局部扫描估值 V pre 2.2 估值分析 V total = V after - V pre (6) 局部扫描方式本质上和全局扫描方式的不同在于对每个子节点进行扩展时都要应用路进行局部扫描而不是全局扫描, 它们的估值存在一定的联系 1) 落子前落子点位置影响的局部扫描的路估值 V pre 与除局部扫描以外的路估值 V pre 之和相当于落子前棋盘全局扫描估值 V pre V pre + V pre = V pre (7) 2) 落子后落子点位置影响的局部扫描的路估值 V after 与除局部扫描以外的路估值 V after 之和相当于落子后棋盘全局扫描估值 V after

4 270 智能系统学报第 10 卷 V after + V after = V after (8) 3) 由于每步落子不会对局部扫描以外的路估值产生影响, 即落子后除局部扫描以外的路估值 V after 等于落子前除局部扫描以外的路估值 V pre, 表达为所以, 局部扫描的棋局估值为 V after = V pre (9) V total = V after - V pre = V after - V pre = ( V after + V after ) - ( V pre + V pre ) (10) 由式 (10) 可以看出, 局部扫描方式和全局扫描方式的棋盘估值相同, 并没有降低精确度, 因此在博弈树生成时, 本文将棋盘扫描方式由全局扫描改进为局部扫描, 忽略无用扫描, 以提高搜索速度 3 局部扫描方式的博弈树生成算法局部扫描方式的博弈树生成算法主要用于子节点的扩展过程因为搜索的宽度是有限的, 根节点递归向下搜索时, 先采用局部扫描方式扩展子节点并进行估值, 并通过排序选择估值排名靠前的 Width 个节点继续递归向下搜索, 删除其他不进行递归搜索的节点为了更方便地应用博弈搜索策略, 将 2 步落子并作一步, 对模拟的 2 步落子进行综合估值, 保证搜索效率和博弈水平基于局部扫描方式的博弈树生成算法伪代码如下基于局部扫描的博弈树生成算法中, 输入模拟落子的棋子颜色 Color 及搜索宽度 Width, 输出估值排名前 Width 的落子组合点本文的六子棋搜索算法采用 Alpha Beta 剪枝技术实现, 设置深度为 Depth, 宽度为 Width 对弈过程中, 根据当前棋局状态扩展子节点时, 采用基于局部扫描的博弈树生成算法对所有可以进行扩展的子节点进行估值, 选择估值为前 Width 名的子节点继续扩展, 直至扩展深度为 Depth 为止通过对叶子节点估值, 倒推计算根部各分支节点的估值, 选择最大值节点对应的落子方式为最佳解 / Input:Color,Width Output:listWay ( 估值排名前 Width 的 2 步落子组合 ) / 1) Localscanning( int Color,int Width){ 2)AddMovePoints(ListPoints); / / 计算模拟移动的落子位置 3)for( i = 0; i <ListPoints.Count-1; i ++) 4)for(j = i +1; j <ListPoints.Count; j ++){ 5) scanpart( ListPoints[ i ].Point,ListPoints[ j ]. Point); / / 落子前局部扫描 6)Part_preValue = Caculate( ); / / 计算模拟落子前局部扫描估值 7)SimulateMove(); / / 模拟落子 8) scanpart( ListPoints[ i ].Point,ListPoints[ j ]. Point); / / 落子后局部扫描 9)Part_afterValue = Caculate( ); / / 计算模拟落子后局部扫描估值 10) Value = Part_afterValue-Part_preValue; 11)RestoreMove(); / / 撤销落子 12) AddListWay( ListPoints[ i ]. Point,ListPoints [ j ].Point,Value); 13)} 14) GetListWay( ListWay,Width); 4 实验 4.1 实验环境基于上述六子棋搜索策略, 本文设计并实现了六子棋博弈系统 DragonWorld( 龙行天下 ) - 人机对弈平台该系统采用 C # 语言开发, 操作系统为 Windows 7, 硬件环境为联想 (G490) CPU 2.60 GHZ 的 Inter 处理器和 4 G 内存 4.2 实验与分析为比较不同的扫描方式, 本文从搜索效率和博弈水平 2 个角度进行实验对比通过搜索效率的实验, 分析不同深度和宽度对搜索效率的影响通过博弈水平的实验, 在严格遵循竞赛时间要求的前提下, 分析同等条件下不同搜索深度和宽度对博弈水平的影响实验中每局对弈时间不超过 15 min 表 1 价值与威胁值分配 Table 1 The distribution of the value and threat value 路数己方路的价值对方路的威胁值 6 路路路路路路搜索效率实验搜索效率包括深度和宽度 2 个方面通过深度实验, 分析同等宽度情况下不同搜索深度对搜索效率的影响 ; 通过宽度实验, 分析同等深度情况下不同搜索宽度对搜索效率的影响设置 Width = 10, 采用深度为时, 全局扫描和局部扫描时间进行对比实验, 各对弈 100 局, 每

5 第 2 期李学俊, 等 : 六子棋中基于局部路扫描方式的博弈树生成算法 271 步的平均搜索时间如图 3 所示由图 3 可得, 随着步数的增加, 全局扫描的搜索时间明显增加, 局部扫描却无明显变化随着搜索深度的增加, 局部扫描的搜索效率优化愈加明显对于第 9 步, 在深度为时, 全局扫描搜索时间分别为 s; 而局部扫描搜索时间分别为 s 图 4 2 种扫描方式在不同宽度的博弈结果 Fig.4 Game results with different widths 图 5 2 种扫描方式在不同深度的博弈结果 Fig.5 Game results with different depths 5 结束语本文将优化后的扫描方式应用到六子棋博弈中, 从搜索效率和博弈水平 2 个角度评价, 相对于全局扫描, 局部扫描大幅度提高搜索效率, 博弈水平也有明显提高本文仅在开局和中局采用局部扫描方式, 提高搜索效率, 如何在残局阶段改进估值提高效率, 有待进一步研究博弈树生成算法仍存在改进之处, 例如估值方法中对于己方路的价值和对方路的威胁值的分配仍需手动调整, 搜索深度仅到 5 层, 依然未达到理想要求参考文献 : 图 3 2 种扫描方式不同深度的搜索时间对比 Fig.3 Search time two scanning method with different depths 博弈水平实验设置 Depth = 3, 全局扫描和局部扫描采用不同宽度对弈, 每个宽度对弈 100 局, 博弈水平如图 4 所示局部扫描显著优于全局扫描,Width = 20 时, 局部扫描和全局扫描的对弈胜率是 96:4 设置 Width = 10, 全局扫描和局部扫描采用不同深度对弈, 各深度对弈 100 局博弈水平如图 6 所示在同等条件下, 局部扫描的搜索深度增加, 博弈水平远远超过全局扫描在 Depth = 5 时, 局部扫描和全局扫描的对弈胜率是 95: 5 因为随着深度增加, 搜索层次越大, 叶子节点越接近末端节点, 越提高获胜几率 [1] 张利群. 五道棋计算机博弈程序的设计与实现 [ J]. 计算机工程, 2010(10): , 231. ZHANG Liqun. Design and realization of Wudao chess com puter game program [ J ]. Computer Engineering, 2010 (10): , 231. [2] 徐长明, 马宗民, 徐心和. 一种新的连珠棋局面表示法及其在六子棋中的应用 [ J]. 东北大学学报 : 自然科学版, 2009(4): XU Changming, MA Zongmin, XU Xinhe. A new board rep resentation method for k in a row games with its application to connect 6 [ J]. Journal Northeastern University: Natural Science, 2009(4): [3] QIAO Zhihua, YANG Ming, WANG Zijuan. Technologies analysis of connect6 computer game[ J]. Advanced Materi als Research, 2011, 1077 (171) : [4] ZHANG Ruimei, LIU Changcheng, WANG Chuandui. Re search on connect 6 programming based on mtd(f) and dee per always transposition table[ C] / / 2012 IEEE 2nd Interna

6 272 智能系统学报第 10 卷 tional Conference on Cloud Computing and Intelligence Sys tems. [S.l.], 2012: [5] 徐长明. 基于连珠模式的六子棋机器博弈关键技术研究 [D]. 沈阳 : 东北大学, 2010: XU Changming. Research on key technologies of connection pattern based computer connect 6 [ D]. Shenyang: North eastern University, 2010: [6] KNUTH D E, MOORE R W. An analysis of alpha beta pruning[ J]. Artificial Intelligence, 1975, 6(4): [7] 李翠珠. 六子棋计算机博弈系统的研究与实现 [ D]. 重庆 : 重庆理工大学, 2010: LI Cuizhu. Research and Implementation of the system of connect 6 game [ D]. Chongqing: Chongqing University of Technology, 2010: [8] 张颖. 六子棋启发式搜索算法的优化与设计 [ J]. 西北师范大学学报 : 自然科学版, 2008(4): 31 36, 58. ZHANG Ying. Optimization and design of connect6 heuristic searching algorithm[ J]. Journal of Northwest Normal Uni versity: Natural Science, 2008(4): 31 36, 58. [9] 黄继平, 苗华, 张栋. 用遗传算法实现六子棋评估函数参数优化 [J]. 重庆工学院学报 : 自然科学版, 2009(11): HUANG Jiping, MIAO Hua, ZHANG Dong. Optimizing the evaluation function parameters of connect6 with genetic algo rithms [ J]. Journal of Chongqing Institute of Technology: Natural Science, 2009(11): [10] 陈光年. 基于智能算法的六子棋博弈行为选择的应用研究 [D]. 重庆 : 重庆理工大学, 2010: CHEN Guangnian. The research and application on the be havior election of connect 6 based on intelligent algorithms [ D ]. Chongqing: Chongqing University of Technology, 2010: [11] 张小川, 陈光年, 张世强, 等. 六子棋博弈的评估函数 [J]. 重庆理工大学学报 : 自然科学版, 2010( 2): ZHANG Xiaochuan, CHEN Guangnian, ZHANG Shiqiang. Research on evaluation functions for computer game of con nect6[ J]. Journal of Chongqing University of Technology: Natural Science, 2010(2): [12] 徐长明, 马宗民, 徐心和, 等. 面向机器博弈的即时差分学习研究 [J]. 计算机科学, 2010(8): XU Changming, MA Zongmin, XU Xinhe. Study of tempo ral difference learning in computer games [ J]. Computer Science, 2010(8): [13] 徐心和, 邓志立, 王骄, 等. 机器博弈研究面临的各种挑战 [J]. 智能系统学报, 2008, 3(4): XU Xinhe, DENG Zhili, WANG Jiao, et al. Challenging issues facing computer game research[ J]. CAAI Transac tions on Intelligent Systems, 2008, 3(4): [14] 闵文杰. 六子棋计算机博弈关键技术研究 [ D]. 重庆 : 重庆交通大学, 2010: MIN Wenjie. Research on the key technologies of the con nect 6 computer game[ D]. Chongqing: Chongqing Jiaotong University, 2010: [15] MARTIN K, SVEN S, RAINER H. Improved tree based strategies for a connect 6 threat based hardware design [C] / / 2013 IEEE Pacific Rim Conference on Communica tions, Computers and Signal Processing ( PACRIM ). [S.l.], 2013: [16] 张明亮, 吴俊, 李凡长. 五子棋机器博弈系统评估函数的设计 [J]. 计算机应用, 2012(7): , 210. ZHANG Mingliang, WU Jun, LI Fanchang. Design of eval uation function for computer gobang game system[ J]. Jour nal of Computer Applications, 2012(7): , 210. 作者简介 : 李学俊, 男,1976 年生, 副教授, 中国人工智能学会机器博弈专业委员会理事, 主要研究方向为智能软件云工作流王小龙, 男,1989 年生, 硕士, 主要研究方向为机器博弈吴蕾, 女,1978 年生, 讲师, 博士研究生, 中国人工智能学会机器博弈专业委员会理事, 主要研究方向为机器博弈, 软件测试

Microsoft Word - 专论综述1.doc

Microsoft Word - 专论综述1.doc 2016 年第 25 卷第期 http://www.c-s-a.org.cn 计算机系统应用 1 基于节点融合分层法的电网并行拓扑分析王惠中 1,2, 赵燕魏 1,2, 詹克非 1, 朱宏毅 1 ( 兰州理工大学电气工程与信息工程学院, 兰州 730050) 2 ( 甘肃省工业过程先