基于Qt和博弈算法的五子棋游戏设计

赵杰，李亚文，杨滨峰

（商洛学院电子信息与电气工程学院，陕西商洛 726000）

随着网络的发展，棋牌类益智休闲游戏迅速火爆起来，受到许多人的欢迎与喜爱，相关企业及诸多学者与教育工作者也对此产生极大的兴趣[1-3]。万坤等[4]基于C/S（客户端/服务器）网络架构实现了五子棋游戏的设计，采用MySQL数据库和V-Play设计实现游戏框架，使用QML脚本语言实现游戏界面设计，用户间通信由服务器统一调度转发通信更容易实现。王梦寻等[5]通过STM32单片机及触摸屏设计了人机对战五子棋系统。蒋志凤等[6]基于Linux设计了一款象棋游戏，在基础游戏模式基础上增加了“悔棋”功能及其他的娱乐玩法，但该系统的可移植性差。棋牌类游戏中，人机对战与机器博弈是重要的设计因素[7-8]。也有研究者针对五子棋进行了相应研究。周洋等[9]利用极小极大值搜索提升运算速度，利用剪枝算法修剪不必要的分支，进一步提升搜索速率。郑健磊等[10]利用局部搜索、多线程技术、浅层最优算法优化剪枝算法，以提升着棋的速度和准确率。本文对五子棋博弈进行研究，利用Qt开发框架实现五子棋游戏博弈对战平台，在使用极大极小值搜索和α-β剪枝算法的基础上，选用AC自动机进行模式匹配，进一步优化博弈算法，以期提升搜索与匹配效率。

1 方案设计

1.1 总体方案

主界面上显示单人与多人游戏模式选择，方便用户自主选择游戏方式，并在该界面添加常见的设置功能和退出游戏功能，设置功能主要用于设置一些游戏属性。当用户选择单人游戏后，画面将跳转到人机对战界面，实现与电脑AI对战游戏，设置电脑难度和先后手顺序后即可开始游戏，玩家落子后交由计算机算法运算。多人游戏具备创建游戏和加入游戏的功能，在游戏大厅中会显示所有玩家的房间信息，玩家可自行决定是否创建、加入游戏。当有用户加入房间后，房主即可选择开始对弈。和单人游戏一样玩家双方拥有选择悔棋的权利，但需对弈双方同意后才能实现。当游戏结束后，房主可等待对方准备后重新开始对弈。在对弈过程中若一方选择退出游戏视为认输，退出后跳转到游戏大厅界面。系统网络结构同时采用TCP的C/S模型和UDP的广播来实现。当用户选择多人游戏后，用户会使用UDP广播发送请求房间信息，网络上存在房间的主机将自己的房间信息以UDP协议发送给请求的用户，用户之间不必通过建立连接来通信，这样所有的用户就可以知道存在的房间信息，从而更新游戏大厅信息。当房间信息发生改变时，该房主将会重新发送房间信息来更新其他用户的大厅信息。当用户建立房间后，该用户将变为服务器，并监听其他用户客户端的连接，有用户加入房间后，二者便建立TCP连接，变成P2P点对点通信模式用于传输二者的对弈、聊天[11]。设计思想结构图如图1所示。

图1 网络模型结构

1.2 网络对战

数据的接收发送使用Socket编程和Qt的多线程机制。房间信息的请求、发送都是使用UDP广播传输，当用户创建房间后就开启TCP服务器，用户的一切操作请求、游戏信息都是通过TCP连接传输。各用户间房间信息发送使用UDP广播实现，而和其他玩家对弈时的信息交流采用C/S模式，各用户间房间信息发送使用UDP广播实现，而和其他玩家对弈时的信息交流采用C/S模式。用户可以选择建立游戏房间（即创建TCP服务器）还是加入别人的游戏房间（请求TCP连接）进行对弈。用户可以选择自己建立游戏房间（即创建TCP服务器）或加入别人的游戏房间（请求TCP连接）进行对弈。用户落子后将落子信息发送给对弈对手，由对手判断这步棋是否获得胜利，若对方获得胜利则重置游戏棋盘，并将对方获胜消息发送给对弈对手。若双方在信息交互中等待超时响应，由程序判断对方是否断开连接。程序的运行流程如图2所示。

图2 运行流程图

1.3 人机对弈

电脑AI针对玩家落子信息择优选择对应落子的目标落子。电脑AI会根据一定的计算规则计算棋盘全部位置的落子权重分数，根据分数选择落子目标。要对某一个位置进行打分就需要制定相应规则，按照评分规则计算位置评分。根据五子棋对弈的各种棋型指定棋型评估表，AI匹配棋型计算位置评分。棋型评估情况如表1所示。表1中X代表空位，O代表棋子，其中每一种棋型对应一个评分，评分越高代表其拥有越强的威胁。高评分的位置具有较大的优势威胁，相应的比它小的威胁再多加起来也不会超过其评分。表1中对某些对称棋型没有完全记录（如跳活三的对称OOXOX），但在设计数据结构实现时会对其进行定义（共计16种）。若某个棋子的两边都存在敌方棋子，则该位置这个方向的分数记为0。

表1 棋型评估表

2 局面评估与博弈

通过棋型评估表，对该位置横、竖、正、反、斜向的相关范围扫描匹配棋型，累加评分得出该位置的最终评分。该算法虽然具备判断棋盘所有位置的分数优势的能力，但是它最大的缺陷就是计算一步结果，只能看见眼前的利益，但分数最高的也不一定是最好的落子位置。将所有的局面列举计算稳定的收益分布构建最小生成树形，计算其局面评分形成树状图形，如图3所示。以整个棋局作为独立的评估单位，若局面分数越大，则对当前棋手越有利，反之分数越小，对当前棋手越不利。

图3 博弈树

根据“零和博弈”理论，敌方落子位置有很大可能是对己方最不利的位置，也就是对己方评分最小的位置上[12]。通过对比子节点收益情况，选择使己方收益最大的落子位置。

2.1 极大极小值搜索

使用极大极小值搜索算法思路，假设从四步棋局开始考虑，作为敌方肯定希望第四步分数最小，所以把同一第三步下的第四步的最小的分数作为第三步的分数，对于己方而言，第三步的棋局分数应该越大越好，所以将同一第二步下的所有第三步的最大分求出作为第二步的分数。同理将同一第一步下的所有第二步中最小的分数作为第一步的分数，最后找所有第一步中的最大值作为己方决策的最终位置，这就是极大极小值的计算方法。设计思路如图4所示。在设计实现算法时，其中MAX层数据就是其下一层分支中的最大值，而MIN层数据也是其下一层分支中的最小值。

图4 极大极小值搜索示意图

若要这样深层遍历所有可能节点，计算其局面分数将会导致产生非常大的计算量。虽然可以尽量排除局面中较远的点，但是越往后，每计算一步棋将要考虑三四十个位置，按照8层深度计算最少也有308=6 561亿个分支。所以还需要一些算法对目前算法进行优化。

2.2 α-β 剪枝算法

α-β剪枝算法相当于极大极小值算法的改进型算法，是由递归实现的一种搜索树算法，将搜索树中极大值用α表示，而极小值用β表示。每个节点都会有一个α-β的数值，通过比较来判断是否继续搜索该节点，数值的大小对应对下棋者的利弊。剪枝算法如图5所示。

图5 剪枝算法示意图

MAX可以看成己方落子层，MIN层就是敌方落子层，双方都不会使对方利益最大化，但都希望自己利益最大化。当搜索MAX层时，假设已搜索到当分支下同一层中所有已搜索过的最大值α，就剪掉其下一层所有比α值小的节点分支。当搜索MIN层时，假设已搜索到当分支下同一层中所有已搜索过的最小值β，就减掉其下一层所有比β值大的节点分支。在初始时α将被赋予-∞，β将被赋予+∞，在搜索过程中搜索MAX会将α不断变大，搜索MIN会将β不断变小。这样就会有一个[α，β]的窗口区域，窗口不断缩小，最终被窗口筛选出的值就是最优的选择。随着搜索的进行，会出现一种局面分数比α大但比β小的情况，说明该落法对弈双方都可以考虑落子。但当这种局面出现时要将其舍弃，所以必须在博弈树的上一层选择另一种下法。

2.3 AC模式匹配

虽然使用α-β剪枝算法优化减少了算法的计算量，但是每次计算模式匹配的时候都需要重新依次遍历匹配所有模式，这样会在模式匹配上花费许多时间，因此本文选用AC自动机来进行模式匹配。AC自动机的实现有三个重要的组成部分：构建字典树、寻找失配指针、字符串匹配。要用AC自动机完成计算就需先构造字典树，从根节点开始将所有字符串依次排列成树状结构，若不存在字符节点就创建新的节点存储该字符。在字典树构建完之后需要构建匹配失败时的回退机制，所以要对每个节点配置失配指针。设置原则是根节点下的所有节点失配指针指向根节点，所有子节点的失配指针指向其父节点的同深度的与其自己相同的节点，若没有相同节点则指向根节点。构建匹配查找时，失配后就查找其失配指针所指节点的子节点继续匹配，重复该过程直到匹配串走到结尾为止。使用AC算法能够极大地减少计算局面分数时模式匹配的时间，提升计算速度。

3 测试结果

软件设计采用Qt Designer跨平台GUI资源库，开发工具为Qt Creator 4.3.0，使用Qt 5.9 for Desktop打包工具。所测试数据皆在Windows10操作系统下完成。

3.1 基础功能测试

本平台的基础功能主要从人机对弈、房间创建与加入、网络对弈三个方面进行功能测试。其中，人机对弈具备设置先后手、设置难度、悔棋、重新开始等功能，其功能实现如图6所示。

图6 人机对弈界面

游戏大厅展示所有已创建的房间信息，通过表格中按钮加入退出房间、开始游戏，通过表格下方的按钮创建关闭房间。通过刷新按钮刷新表格内所有房间信息。功能实现如图7所示。网络对弈界面实现网络中双人对弈、聊天、 悔棋、认输等功能，功能测试如图8所示。

图7 游戏大厅界面

图8 网络对弈界面

3.2 速度性能测试

在玩家先手下，对不同难度对应的不同计算深度每走一步棋进行计算时间统计测试，计算时间通过使用QTimer类倒计时功能和超时响应槽函数设计计时器记录算法用时，统计三次对局计算时间取平均值记录如表2所示。

表2 3～6层深度下算法每计算一步所需时间

本文分别对比文献[9]和文献[10]中的计算数据，分别取文中在3层、5层深度下算法每计算一步所需时间数据（取五次对局时间平均）和4层、6层深度下计算一步所需时间，结果分别见表3和表4。

表3 文献[9]五子棋博弈算法3层和5层深度下每计算一步所需时间

表4 文献[10]五子棋博弈算法4层和6层深度下每计算一步所需时间

通过对比可以看出，本设计通过算法优化使得算法AI的计算时间得到极大的缩减，计算时间拥有几十倍之差，计算能力得到提升，提高了游戏体验感。再次对7层、8层、9层深度下进行算法时间测试，测试结果如表5所示。

表5 本文算法不同深度每计算一步所需时间

从表5中可以看出，本设计在7层以下的计算时间都在1 s以下，且第8层下每计算一步所需时间平均不超过1 s。为了不影响游戏体验，将最高难度设置为8层遍历深度，在不影响游戏体验感的同时，AI的计算能力和速度已满足人机对弈要求。

4 结语

本文使用Qt的GUI交互设计工具，设计具有交互界面的五子棋游戏平台，可以实现网络对战及人机对战两种游戏模式。该设计具有较高智能程度，并且具有较好的人机交互界面和响应速度。人机对战博弈在采用极大极小值搜索和α-β剪枝算法的基础上，引入AC自动机来加快模式匹配的计算，从而对博弈算法进行了速度优化，计算时间明显小于传统搜索及α-β剪枝算法。