基于电阻电路评估策略的分阶段海克斯棋博弈方法的研究

张志礼，丁 濛，段金龙，罗锋骏，勾亮亮

（北京信息科技大学计算机学院，北京100101）

0 引 言

海克斯棋［1］，亦称六贯棋，最初是在丹麦报纸Politiken发表的一篇文章里出现，当时称为Polygon。1948年，John Nash却又将其重新独立发明出来，而热衷于此的玩家们随即就将其称作Nash。稍后于1952年Parker Brothers发行了一个版本，将其称为Hex，从此这个名字就固定了下来。六贯棋是在六边形格的棋盘上竞技的图版游戏，亦是数学游戏，通常使用10×10或11×11的菱形棋盘，而John Nash采用的却是14×14的棋盘。

海克斯棋的规则为：

（1）由2个人共同参与，棋盘为平行四边形，有2种颜色，通常是红、蓝或黑、白。4个边平行填上两方的颜色。

（2）双方轮流走棋，先后手自行选择，每次只能下一个棋子，每次占领一处空白格，在空白格放上自己颜色的棋子。

（3）整个比赛中，双方均不能吃掉对方或已方的棋子。

（4）最先将棋盘属于自己的颜色的边连成一线的一方为胜。

在棋类博弈比赛中没有统一的棋盘和棋谱格式，为了能够标准化导出棋谱并保留博弈数据，2018年中国大学生计算机博弈大赛为每种棋类项目发布了统一标准［2］，本次研究则严格按照中国大学生计算机博弈大赛棋谱标准说明书要求编写了海克斯棋博弈软件。此外，比赛程序BistuHex2提出了UCT、α-β剪枝和电阻电路评估策略配合使用的搜索方法，在往届中国大学生计算机博弈比赛中取得优异成绩。对此，本文拟展开研究论述如下。

1 评估策略设计与应用

海克斯棋获胜的方法是将棋盘属于自己的颜色的边连成一线，而且每个棋子的行棋都要考虑攻防兼备，因此双方每次落子都至关重要，棋类游戏的搜索算法大同小异，这时，一个较优的评估策略，及其与搜索算法的合理结合，则成了决胜的关键。BistuHex2程序是利用UCT算法、α-β剪枝算法与电阻电路评估策略［3］进行分阶段式配合使用，评估策略是利用电路电阻的特点，将其用来作为海克斯棋局面的评估函数，以棋局的局面特征作为输入，评估值及较优的可走棋子作为输出，为搜索算法进一步缩小搜索范围，并提供判断局面优劣的依据。

1.1 UCT、α-β剪枝与评估策略分阶段式结合

UCT算法（Upper Confidence Bound Apply to Tree），即上限置信区间算法，是一种博弈树搜索算法，该算法将蒙特卡洛树搜索（Monte—Carlo Tree Search，MCTS）方法与UCB公式结合，在超大规模博弈树的搜索过程中相对于传统的搜索算法有着时间和空间方面的优势。之前使用的程序仅基于UCT，搜索时间长、范围广，而且不准确，当前使用程序为BistuHex2，则是将UCT、α-β剪枝与电阻电路评估策略进行分阶段式结合。

通过上述评估算法可以得出许多可以减少已方电阻的点。将这些点作为UCT模拟的对象，就避免了盲目搜索，极大地提高了搜索效率。在开局时，需要搜索的点很多，用UCT模拟的效果很差，因此在开局的时候采用α-β剪枝算法与基于电阻电路评估策略结合的方法，使得程序在开局时依然可以非常强大。当评估算法获得的点较少时，再采用UCT搜索算法与基于电阻电路评估策略的结合，可以在后期有效地把控全局。

1.2 电阻电路评估策略

评估策略是用电路和电阻的思路结合海克斯棋的特点进行设计，对海克斯棋来说，一个合理的估值函数应该估计黑棋方建立一条获胜黑链的程度比白棋方要建立一条获胜的白链更接近。

衡量玩家建立链条的接近程度的一种流行方法是计算该玩家需要添加的最小数量的棋子以连接棋盘的两侧，但是这种方法没有考虑潜在链的数量。试图通过Hex位置的电路表示来修复这个缺陷。将4个多边形边界带视为附加单元，如图1所示。

假设黑色边界永久地被黑色棋子部分占据，并且白色边界永久地被白色棋子占据。对于每个海克斯棋的位置，将其与电路相关联。对于电路板的每个位置c，按以下方式分配电阻r，对此可阐释如下。

图1 白色棋子连接白色的两边边界，赢得了比赛Fig.1 The chain of white pieces connects white boundaries， White has won the game

（1）对于黑色电路，研究可得规则表述为：

① 如果该位置为空，rB（c）＝1。

②如果该位置被黑色棋子占据，rB（c）＝0。

③如果该位置被白色棋子占据，rB（c）＝+∞。

（2）对于白色电路，研究可得规则表述为：

① 如果该位置为空，rW（c）＝1。

② 如果该位置被白色棋子占据，rW（c）＝0。

③ 如果该位置被白色棋子占据，rW（c）＝+∞。

接下来，对于每对相邻位置（c1，c2），将电路与电阻相关联，对此可阐释如下。

（1）对于黑色电路，研究可得数学计算公式如下：

（2）对于白色电路，研究可得数学计算公式如下：

现在向相对的边界施加电压并测量两者之间的总电阻，研究得到的测试电路详见图2。

图2 黑色棋电路和白色棋电路Fig.2 Black＇s and White＇s circuits

根据基尔霍夫电流定律，总电阻估算了为连接电路板的两侧而需要添加到电路板的棋子数，以及可以完成的方式。为此，定义一个估值函数，相应计算公式如下：

其中，如果存在获胜的黑链，E＝0；如果存在获胜的白链，E＝+∞；E越小，表示黑色棋子位置越好，白色棋子位置越差。

已知UCT的公式也会得出一个值，让E和此值按照一定的比例计算得出一个可以衡量落子好坏的值，并用此值去寻出最优点进行落子。

2 评估策略实现流程

评估策略先接受当前状态的棋盘，根据棋盘上棋子情况选出所有可走棋子，用电阻电路评估策略选出对已方较为有利的可走棋子，而且每个可走的棋子点都由评估策略算出权值，而后判断当前选出的可走棋子个数，如果小于30，选用α-β剪枝算法得出最优点行棋，否则，选用UCT算法得出最优点行棋，从而转入输出环节操作。分析后可得设计步骤如图3所示。

图3 评估策略流程图Fig.3 The flow chart of evaluation strategy

3 海克斯棋交互界面设计与实现

3.1 海克斯棋棋谱标准简介

参照海克斯棋棋谱标准可知［2］，海克斯棋盘由11×11个六边形单元格组成，如图4所示，坐标原点位于左下角，横坐标从 A到K，纵坐标从1到11。

图4 海克斯棋棋盘Fig.4 Hex chess board

在此基础上，将给出海克斯棋棋谱的具体要求如下：棋谱文件为纯文本文件，文件名的格式为：“HEX-先手参赛队 R vs后手参赛队 B-先（后）手胜-比赛时间地点-赛事名称”，文件的扩展名为txt。棋谱中的所有指令和定界符号的字符都应是英文输入法输入的字符，参赛队名等参数也可以使用中文汉字，棋谱所采用的字符集为GB2312，海克斯棋谱输出格式样例如下：

｛［HEX］［先手参赛队 R］［后手参赛队 B］［先手胜］［2017.07.29 14：00 重庆］［2017 CCGC］； R（E，7）；B（E，6）；R（F，7）；B（G，7）；R（D，6）；B（F，6）；R（C，6）；B（G，6）｝

3.2 交互界面的实现效果

界面程序能够实现基本的人人交互博弈、人机交互博弈以及AI与AI交互博弈，其中的人人交互博弈界面效果如图5所示，而且也能够导出标准化棋谱，棋谱效果如图6所示。

图5 交互博弈界面效果Fig.5 Interactive game interface effect

图6 棋谱Fig.6 Chess

4 实验结果与分析

本文将基于UCT、α-β剪枝和电阻电路评估函数的海克斯棋程序与基于UCT的海克斯棋程序进行了对弈。测试50局，各先手25局，后手25局。测试结果见表1。

表1 对弈比赛结果统计Tab.1 Game result statistics

实验表明，改进后的程序胜率很大，证实了本程序改进的有效性。对BistuHex2程序算法的修改能够提高算法搜索精确度，在一定程度上增加了找到最优落子坐标的概率。通过加大α-β剪枝算法搜索的深度，以及更改UCT搜索可走棋子的个数可以让搜索更加准确，从而大幅提升了算法效率。

5 结束语

通过对之前仅用UCT算法的程序进行了改进，根据α-β剪枝算法的特点与UCT和电阻电路评估策略合理结合，很好地提高了最优点的搜索效率。但是本程序并没有体现深度学习的算法及思路，在今后的工作中，研究将会继续丰富界面程序功能，添加更为人性化的交互界面，学习参考Alpha Go和Alpha Zero思想与方法，旨在进一步完善海克斯棋程序。