开局库在点格棋计算机博弈系统中的应用

北京信息科技大学计算机学院 靳淑娴 高铭 王修锴

计算机博弈，是人工智能领域的一个重要研究方向。在点格棋计算机博弈的过程中，由于开局可能着法较多、计算量巨大，在开局阶段往往会花费大量的时间，为了解决这一问题，我们将开局库技术应用到点格棋的计算机博弈中。利用对局数据库生成方法，在UCT算法的基础上，我们生成了点格棋的开局库，与未采用开局库策略的点格棋博弈程序对弈后，取得了明显的优势。实验结果表明，应用了开局库策略的点格棋博弈程序具有较强的棋力和较高的计算效率。

开局库是棋类软件的组件之一，其中包括着与开局有关的数据库。开局库相关技术主要应用在象棋计算机博弈系统中，目前已经建立了基于SQL Server数据库技术的中国象棋开局库[1]，在四国军棋的计算机博弈领域也有着定式库的相关应用[2]。在点格棋计算机博弈的过程中，由于开局可能着法较多、计算量巨大，在开局阶段往往会花费大量的时间，开局库策略有助于改善这一状况，而在点格棋的计算机博弈领域，目前仅仅存在简单的镜像开局库策略的相关研究[3]。为了解决这一问题，我们参考中国象棋和国际象棋的成熟的开局库技术[4-6]，设计开发点格棋博弈系统的开局库，在点格棋计算机博弈系统中应用开局库技术。

1 点格棋研究现状

1.1 点格棋规则简介

全国大学生计算机博弈大赛中规定了点格棋项目的比赛规则：

（1）N×N的点格棋的棋盘是由N×N个等距的点阵构成的。全国计算机博弈大赛规定采用6×6的点格棋盘。

（2）博弈双方通过轮流将横向或者竖向上相邻两点相连来进行占边操作（不可以跨越点，不可以重复占边）。

（3）当某一格子四条边都被某一方连线后，占领格子最后那一条边的玩家得到这个格子。

（4）玩家占领格子后，可以继续进行一次占边。

（5）当棋盘上的所有格子都被占领后，则游戏结束，占领格子数多者获得胜利。

由于6×6的点格棋有5×5即25个格子，所以6×6点格棋是一定可以分出胜负的。

一个6×6的点格棋棋盘如图1所示：

图1 6×6点格棋棋盘Fig.1 A 6×6 board of dots-and-boxes

1.2 点格棋常用算法

点格棋的博弈系统主要由搜索算法和估值函数这两部分组成。点格棋博弈搜索算法主要有alpha-beta剪枝搜索算法、UCT搜索算法等[7-9]。UCT（UCB applied to Tree）搜索算法[10-11]是近几年来在计算机博弈中采用最多的一种算法，有着搜索效率较高、搜索时间可控的特点。UCT算法是一种将蒙塔卡罗搜索树（Monte-Carlo Tree Search），简称MCTS，方法与UCB公式进行结合的博弈树搜索算法。MCTS算法通过大量随机模拟，建立博弈树概率模型进行在线搜索，而UCB公式，用来在每个局面状态节点处有倾向地选择分支节点。

UCT算法的搜索过程，如图2所示，共分为四个阶段，即选择（Selection）、拓展（Expansion）、模拟（Simulation）和回溯（Backpropagation）。

图2 UCT的搜索过程：选择、拓展、模拟、回溯Fig.2 The search process of UCT: selection, expansion, simulation, backpropagation

（1）选择：根据UCB公式，通过递归的方式对不同分支进行选择，一直到达博弈树的叶子节点。UCB公式如公式（1）所示。

其中，wi表示特定局面下第i个分支所有模拟中当前玩家的胜利次数，ni表示特定局面下第i个分支模拟的总次数，N表示特定局面下所有分支的模拟总次数，c表示探索的倾向参数，通常被设置为。

（2）拓展：当到达叶节点之后，以此局面为基础，计算该叶子节点所代表局面下的所有的合法动作，选择其中的一个节点进行拓展，生成该节点的子节点，并将其添加到搜索树中。

（3）模拟：从新扩展的节点处开始模拟博弈的过程，直到博弈结束为止，记录博弈的结果。

（4）回溯：模拟结束后，根据模拟的博弈结果向上回溯并更新该路径上所有节点的访问次数和收益情况信息。

2 开局库研究现状

点格棋的博弈过程一般可以分为开局、中局和残局三个阶段[12]。开局库是存储开局着法的数据文件或者数据库。通过开局库，可以把一些比较好的开局存储起来，在开局时，用查询数据库的方法来代替搜索和评估，可以提高计算机在开局时的对弈水平并减少运算时间。优秀的棋类博弈系统，基本上都拥有自己的开局库。

2.1 由脱离棋谱的拓展自动生成

脱离棋谱的拓展[4]即DOE（Drop-out Expansion）是由Thomas Lincke发明的，在西洋跳棋中取得了比较大的成功。该方法在建立开局库时，对于一些好的着法进行扩展，然后在扩展后的局面继续，通过扩展后的局面来判断先前着法的优劣。该方法会有一个优先函数，对每个可能的路径给出优先值，对优先值较高的路径的叶子节点进行扩展。采用这种开局库的程序一般只会走开局库中好的着法，所以当在遇到不恰当的局面时往往表现很糟糕。

2.2 由对局数据库生成

生成开局库最简单的方法就是找到或者创建一个对局数据库，根据对局数据库中对局的最终结果选择比较可靠的着法。对于每个局面，可以生成所有着法的统计数字，例如，采用这步着法的最终胜率，使用开局库时可以根据数据来选择最佳着法。对于人类非常精通的棋类,例如，中国象棋、国际象棋等，可以手工整理高质量的高手对弈的棋谱收录到开局库中，而点格棋目前还不存在现有的高质量开局库，所以需要利用数据库自动生成。

2.3 镜像开局库策略

镜像开局库策略[3]是一种较为特殊的开局库策略，它通过模拟对方的落子，将对方落子进行镜像，重现对方的开局。这种策略在面对实力较强的对手时，可以学习对手的开局来增加自己的开局信息，避免在前中期开局不利的情况。

3 点格棋开局库的设计与实现

3.1 开局库生成策略

我们选择利用对局数据库的方法来生成点格棋的开局库。可以用来判断着法优劣的相关标准有：

（1）一个着法被人采用的次数越多，着法就越好。

（2）棋力较高的棋手/博弈程序的着法更好。

（3）通过对局结果获胜的一方着法更好。

结合以上因素，我们选择将胜率作为判断着法优劣的标准。由于空间有限，且胜率较小的局面存储价值不大，所以我们通过设置胜率的阈值来筛选录入开局库的局面。为了开局库的生成与局面的查询与匹配，我们将开局库分为先手开局库与后手开局库。在实际实验中，我们选取了1000个对局棋谱，设定第1～10步为开局阶段，则产生10×1000=10000个（包含重复局面）局面，分别为先手局面5000个，后手局面5000个，设置胜率阈值为40%，通过计算不同局面的胜率，对局面筛选并去重，我们得到最终的开局库。

3.2 数据结构设计

由于开局仅为棋局的前10步，如果记录所有边的被占有信息时没有必要的，所以我们选择按照从左到右、从上到下的顺序，记录被占领的边的信息来表示局面。我们假设开局时没有格子被占领的（通常在开局中是没有格子被占领的），而边被占有后是属于共有的边，所以我们不记录某边是被博弈的哪一方所占领。而某一条被占边的信息我们用三个连续的数字表示，即公式（2）所示。

其中，Direction代表该边方向（0为横向，1为竖向），X代表该边所在横坐标（1～6），Y代表该边所在竖坐标（1～6）。

4 实验结果与分析

为了验证本文研究的开局库策略的有效性，将该策略与不采用开局库策略的蒙特卡洛算法进行博弈测试，棋盘大小为6×6，采用前面提到的点格棋项目规则，计时方式为包干计时15分钟。6×6的点格棋棋盘共有60条边，我们假设一方走三十步（可能有一方得到棋子后连走的情况，所以实际上的走棋一般达不到30步），所以将单步时限设为15分钟/30步，即单步时限为30秒。由于开局库查询所需时间较少，所以对于采用开局库策略的程序，我们将开局后的单步时限调整为35秒。该测试硬件环境为：Intel Core i7-1165G7，主频2.80GHz。测试结果如表1，表2，表3所示。

表1 采用开局库策略先手Tab.1 Use-opening-book first

表2 不采用开局库策略先手Tab.2 Nonuse-opening-book first

表3 总对弈结果Tab.3 The total result

由表1、表2、表3可以得出，采用开局库策略的程序的胜率明显比未采用的程序更高。

5 结语

计算机博弈是一个复杂又具有挑战性的课题，对于博弈论的学习和研究具有很深远的意义。本文在点格棋蒙塔卡罗搜索树算法的基础上，运用了开局库策略，创建了点格棋的开局库并与未采用开局库策略的点格棋博弈程序进行对弈，由实验结果，我们可以看出，开局库策略取得了一定的效果。

此次研究虽然小有成果，但开局库在点格棋方面运用的经验与知识与中国象棋、国际象棋等棋类相比十分缺少，我们通过对其他棋类开局库研究的借鉴与自己的探索，对点格棋的开局库策略有了初步的研究成果，但仍存在一些不足有待进一步的改进和研究，受各种条件限制，所建立的开局也并不完整，期待日后能够进一步研究，尽量开发出更加精确和完善的开局库。