机器博弈(即计算机博弈)是人工智能领域的分支，同时也是该领域公认的最具挑战性的研究课题之一。棋类博弈是人类所能从事的智能活动之一，如果可以掌握博弈的本质，也就说明可以帮助人类从事智能活动。因为存在于棋类博弈的原则或许就存在于人类的智能活动中^[1]。近年来，国内外计算机博弈比赛，极大地推动了计算机博弈问题的研究，促进了计算机博弈理论和技术的发展。

棋类计算机博弈涉及的棋种较多，六子棋就是其中之一，它由台湾国立交通大学吴毅成教授发明。六子棋竞赛规则很简单，对弈双方分别执黑子和白子，在19×19的方格棋盘上，除了黑子先手第1步落一颗子外，双方轮流落2颗子，先在水平、垂直或对角线上形成连续的6子(或6子以上)的一方为胜^[2]。六子棋由五子棋改良而来，但是其复杂度却远大于五子棋^[3]，其中博弈树复杂度达到10¹⁴⁰，状态空间复杂度达到10¹⁷²，仅次于围棋，与象棋相当或略高^[4]。

作为刚兴起不久的棋类游戏，六子棋的智能搜索算法研究较少。博弈树搜索为计算机博弈的基本搜索算法，它是从根节点向下递归搜索而产生的包含双方所有对弈过程的搜索树。由于受搜索时间的严格约束，博弈树能够搜索到的叶子节点极少属于末端节点(即根据对弈规则可以判定比赛结果)，此时需要通过估值函数对叶子节点进行量化计算，判断该叶子节点所处的棋局状态是有利于己方还是对方，且计算其有利程度大小^[5]。

在博弈树的扩展过程中会将双方可能的对弈过程展示出来，首先对叶子节点进行估值，再倒推计算根节点各分支节点的值，选择估值最大的分支节点作为最佳解。但是随着搜索深度的增加，博弈树的节点数量成指数性增长。在极大极小值算法的基础上，Alpha-Beta剪枝技术在搜索的过程中忽略了无用的节点，并将其删除，不对其估值，删除无用节点时不会造成信息丢失，不影响根节点各分支节点的估值，提高了搜索速度^[6]。在深层次的递归搜索中广泛采用Alpha-Beta剪枝算法。为了提高计算速度，本文采用Alpha-Beta剪枝技术。

由于六子棋对弈规则的特殊性，如果只考虑单个棋子对棋局的影响进行估值计算，而未考虑棋子间的位置关系，肯定会影响棋局状态的评估效果，由此产生了基于棋形的扫描方式^{[7, 8]}。常见的棋形主要分为六连、长连、活五、眠五、死五、活四、眠四、死四、活三、眠三、朦胧三、活二、眠二、朦胧二等^[9]。文献[2]提出基于棋形的数据表示方法，数据结构依赖于棋形，将棋局的数据表示和局面知识结合起来，提高搜索效率。

基于棋形的扫描方式将棋子间的位置关系联系起来，通过产生某种棋形来表示对整个棋局状态的影响程度，更具有直观性，减少对单个棋子进行估值的不稳定性；然而目前棋形是通过经验总结的，人为因素影响很大，不排除还存在其他种类，这需要通过大量实验来确定。大部分六子棋的估值计算都是基于棋形的扫描方式，但是由于棋形的判断要求很高，常见的棋形种类较多，且每种棋形又存在多种落子方式^[10]，由此文献[11]提出“路”的扫描方式。所谓“路”就在棋盘的水平、垂直或对角线上出现连续6点连成一线^[11]。

基于“路”扫描方式能有效降低棋形判断的复杂度，通过“路”扫描方式的估值相对于通过棋形扫描方式估值较为简单，实现方面也更加容易，并且搜索时间较短。文献[12]在传统的基于“路”的全局扫描方式上采用自学习的方法自动调整估值函数的参数，提高搜索精度。文献[13]在应用Alpha-Beta剪枝搜索时引入并行计算，大幅度提高搜索效率。

“路”扫描方式的引入避免了精确判断棋形的难题，减少了计算量；同时应用面向对象的思想，将“路”的信息抽象成类，易于实现。基于“路” 的扫描方式解决了因棋形判断不准确而影响博弈水平的问题，但是应用博弈树搜索时，在对每个子节点的扩展时都需要对棋盘进行全局扫描。受博弈竞赛时间约束，搜索深度和宽度都有所限制，博弈水平也达不到理想要求。因此本文在博弈树生成子节点时将基于“路”的全局扫描方式改进为局部扫描，并设计基于局部“路”扫描方式的博弈树生成算法。

K子棋可用connect(m,n,k,p,q)表示^[14]，对弈双方为黑方和白方，黑方先走。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 水平及左斜方向路数计算示例 Fig. 1 Road number of horizontal and left diagonal direction

图选项

六子棋是K子棋的一种^[15]，采用19×19方格棋盘，可表示为connect(19,19,6,2,1),总路数为

在“路”的信息表示中，设置n∈{0,1,2,3,4,5,6} 表示该路中相同颜色棋子的个数，设置 c∈{′B′,′W′} 表示路中棋子的颜色。若某路中含2种颜色棋子，表示该路不可能成为六连，则初始值不变。

当某路中 c 为已方棋子颜色时分配不同的价值，计算分配价值公式为

当某路中c 为对方棋子颜色时分配不同的威胁值，计算威胁值公式为

全局扫描估值可用己方所有“路”的价值之和减去对方所有“路”的威胁值之和表示。全局扫描棋局估值 V_total 可看作是每步落子后对当前棋局的影响程度大小，即落子后棋盘全局扫描估值 V_after 减去落子前棋盘全局扫描估值 V_pre ，可表达为

应用Alpha-Beta剪枝技术搜索时,效率和精确度是非常重要又相互影响的因素^[16]。文献[2]中指出棋局状态的变化均由新增的棋子引起，在棋局中只有新增棋子的水平方向、垂直方向和对角线方向上的棋形发生变化，对其他位置棋形无影响。在基于“路”的扫描过程中，每步落子对棋局的影响是由该两落子在水平方向、垂直方向和对角线方向上的“路”所引起，与其他“路”没有关系，故本文在博弈树生成时，优化改进“路”的扫描方式。

假设在棋盘的(3,7)位置模拟一个落子，由图 2可得在水平方向有6路包含该落子，由此可得在局部扫描方式下，每步落子所影响的路数计算如式(5)所示。

图 2 局部扫描水平方向路数计算示例 Fig. 2 Road number of horizontal direction by the local-road scanning method

图选项

由式(5)可得，一般情况下局部扫描的总路数为：6路/方向×4方向/落子×2落子=48路，大大小于全局扫描的总路数924。局部扫描棋局估值 V′_total 即落子后棋盘局部扫描估值 V′_after 减去落子前棋盘局部扫描估值 V′_pre ，可表达为

局部扫描方式本质上和全局扫描方式的不同在于对每个子节点进行扩展时都要应用“路”进行局部扫描而不是全局扫描，它们的估值存在一定的联系。

1)落子前落子点位置影响的局部扫描的“路”估值 V′_pre 与除局部扫描以外的“路”估值 V″_pre 之和相当于落子前棋盘全局扫描估值 V_pre ，可表达为

2)落子后落子点位置影响的局部扫描的“路”估值 V′_after 与除局部扫描以外的“路”估值 V″_after 之和相当于落子后棋盘全局扫描估值 V_after ,可表达为

3)由于每步落子不会对局部扫描以外的“路”估值产生影响，即落子后除局部扫描以外的“路”估值 V″_after 等于落子前除局部扫描以外的“路”估值 V″_pre ，表达为

所以，局部扫描的棋局估值为

由式(10)可以看出，局部扫描方式和全局扫描方式的棋盘估值相同，并没有降低精确度，因此在博弈树生成时，本文将棋盘扫描方式由全局扫描改进为局部扫描，忽略无用扫描，以提高搜索速度。

局部扫描方式的博弈树生成算法主要用于子节点的扩展过程。因为搜索的宽度是有限的，根节点递归向下搜索时，先采用局部扫描方式扩展子节点并进行估值，并通过排序选择估值排名靠前的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);

基于上述六子棋搜索策略，本文设计并实现了六子棋博弈系统DragonWorld(龙行天下)-人机对弈平台。该系统采用C#语言开发，操作系统为Windows 7，硬件环境为联想(G490) CPU、2.60 GHZ的Inter处理器和4 G内存。

为比较不同的扫描方式，本文从搜索效率和博弈水平2个角度进行实验对比。通过搜索效率的实验，分析不同深度和宽度对搜索效率的影响。通过博弈水平的实验，在严格遵循竞赛时间要求的前提下，分析同等条件下不同搜索深度和宽度对博弈水平的影响。实验中每局对弈时间不超过15 min。

搜索效率包括深度和宽度2个方面。通过深度实验，分析同等宽度情况下不同搜索深度对搜索效率的影响；通过宽度实验，分析同等深度情况下不同搜索宽度对搜索效率的影响。

设置Width=10，采用深度为3、4、5时，全局扫描和局部扫描时间进行对比实验，各对弈100局，每步的平均搜索时间如图 3所示。由图 3可得，随着步数的增加，全局扫描的搜索时间明显增加，局部扫描却无明显变化。随着搜索深度的增加，局部扫描的搜索效率优化愈加明显。对于第9步，在深度为3、4、5时，全局扫描搜索时间分别为23.030、269.902、640.780 s；而局部扫描搜索时间分别为2.010、31.855、36.301 s。

图 3 2种扫描方式不同深度的搜索时间对比 Fig. 3 Search time two scanning method with different depths

图选项

设置Depth=3，全局扫描和局部扫描采用不同宽度对弈，每个宽度对弈100局，博弈水平如图 4所示。局部扫描显著优于全局扫描，Width=20时，局部扫描和全局扫描的对弈胜率是96：4。设置Width=10，全局扫描和局部扫描采用不同深度对弈，各深度对弈100局博弈水平如图 5所示。在同等条件下，局部扫描的搜索深度增加，博弈水平远远超过全局扫描。在Depth=5时，局部扫描和全局扫描的对弈胜率是95：5。因为随着深度增加，搜索层次越大，叶子节点越接近末端节点，越提高获胜几率。

图 4 2种扫描方式在不同宽度的博弈结果 Fig. 4 Game results with different widths

图选项

图 5 2种扫描方式在不同深度的博弈结果 Fig. 5 Game results with different depths

图选项

本文将优化后的扫描方式应用到六子棋博弈中，从搜索效率和博弈水平2个角度评价，相对于全局扫描，局部扫描大幅度提高搜索效率，博弈水平也有明显提高。本文仅在开局和中局采用局部扫描方式，提高搜索效率，如何在残局阶段改进估值提高效率，有待进一步研究。博弈树生成算法仍存在改进之处，例如估值方法中对于己方“路”的价值和对方“路”的威胁值的分配仍需手动调整，搜索深度仅到5层，依然未达到理想要求。