基于α-β剪枝树算法的安卓五子棋程序设计与实现

摘  要：本文设计并研发了一种基于智能算法的安卓五子棋应用程序，程序中包括两种模式：玩家对弈和人机对弈，其中在人机对弈模式中，程序一方采用α-β剪枝树算法实现。程序主要由界面显示及控制模块、玩家对弈模块、人机对弈模块和胜负判定模块组成。经过测试，程序具有较高智能程度，能够击败大多数业余选手，并且具有较好的人机交互界面和响应速度，兼顾了智能性与娱乐性。

关键词：博弈论;α-β剪枝树算法;五子棋;安卓程序

Abstract：This paper designs and develops an Android Gobang application program based on intelligent algorithm. The program includes two modes：player game and man-machine game. In the man-machine game mode，the program side uses α-β pruning tree algorithm. The program is mainly composed of interface display and control module，player game module，man-machine game module and win-loss judgment module. After testing，the program has a high degree of intelligence，can beat most amateur players，and has a better human-computer interaction interface and corresponding speed，taking into account the intelligence and entertainment.

Keywords：game theory;α-β pruning tree algorithm;Gobang;Android program

0  引  言

人工智能在最近幾年得到了飞速的发展，很多国家甚至把人工智能作为高科技发展计划的重点项目，在此方面投入了巨大的资源。最优化策略是人工智能研究的一个分支，而博弈论则是最优化策略的一个代表性算法，博弈论的思想是穷举当前状态的所有后继情况，计算最终收益，以求在可接受的条件内获取尽量高的收益[1]。这种算法的思想和棋类游戏中对抗的思想类似，本文选用α-β剪枝树算法，设计并开发一款安卓端的五子棋程序，程序中包括两种模式：玩家对弈和人机对弈。在玩家对弈中，黑白棋子由两名玩家控制，程序负责控制下棋的顺序并判断输赢;而在人机对弈中，由玩家选择一方，另一方由程序自动控制实现对弈。

本文程序选用Java开发语言，在Android Studio开发环境中编译开发，程序中实现了游戏对弈选择、游戏流程控制、游戏胜负判断、基于α-β剪枝树的自动下棋等功能。程序兼顾了趣味性和智能性，能够帮助用户丰富业余生活。

1  α-β剪枝树算法原理

在五子棋人机对弈过程中，考察的重点在于哪一方的“眼光”更能超前[2]，双方根据当前具有的完备的局面信息以及规则判断自己和对方落子的所有情况并分别作为节点，汇总所有的节点，就可以得到一颗基于层次的博弈树，落子时根据对博弈树的权重进行搜索，选择当前情况的最优解，即为五子棋的落子位置，但对于五子棋来说，博弈树的每层节点数量可以达到几十甚至上百，如果需要搜索连续的几层节点，那么搜索的数量是指数级的，搜索时间可能是无法接受的。因此，需要采用一定的策略缩小搜索范围，而α-β剪枝树算法就是一种比较常用的棋类对弈游戏搜索算法[3]。

α-β剪枝树算法是由递归实现的一种搜索树算法，在搜索过程中主要关注两个值，即α与β，α值用来表示在搜索过程中对自己有利的值中的最好值，β则为最不利于对方的值，每一个节点都可以返回一个与α-β相关的值，以此来判定是否继续搜索[4]。在整个搜索过程中，MAX方被称为α，MIN方被称为β，双方都拥有最优的值，在开始搜时，α被赋初值为-∞，β被赋初值为+∞，而在搜索过程中，节点MAX使α的值持续增长，节点MIN则使β持续递减，因此形成了一个[α，β]区域，该区域被叫做窗口。该窗口中的值用来表示该节点的子节点的值的范围，缩小窗口值的过程就是向下搜索的过程，最终在这个窗口中会留下最优值。当节点MAX得到该节点的子节点返回值大于β的值或者节点MIN得到该节点的子节点返回值小于α值，就会执行减枝。

如图1所示，在MAX层，假如当前层中的节点值是已搜索过的所有值中最大的一个，如果发现下一层（MIN）中的其中一个节点可能会产生比刚才搜索到的最大值还要小，即可以把该节点直接剪掉。反之，如果在MIN层，找到了已搜索过的所有值中最小的一个，发现下一层（MAX）会产生比刚才搜索到的最小值还要大，即可把该节点直接剪掉。即双方都不会走出让对方更有利的一步。

在五子棋游戏中，如果某一个落点的结果不大于α，那么该落点就可以被视为是很差的落点，该落点将被抛弃;如果某一个落点的结果不小于β，那么就作废整个节点，因为对方不希望出现这个局面，对方会有更好的落点避免这个局面出现，在判定过程中档发现了一个不小于β的落点的结果，对该结果及其后续进行剪枝操作，不计算后续所有节点。但是当一个落点的结果介于α与β之间的时候，那么该落点就可以被一方考虑。在搜索过程中，α会持续增加以至于能反映新的情况，但是可能会出现计算超时的情况，因此还需添加其他限定条件，以保证搜索能够及时停止，获得一个可以接受的局部最优值，在本文中，考虑到安卓手机的性能，采取限定最大搜索4层的策略，来实现五子棋游戏中的人机对弈的效果。

2  程序设计与实现

五子棋应用程序需要具有良好的人机交互体验，界面要美观，下棋计算时间要快，能供用户选择进行玩家对弈或者人机对弈功能，并且能够自动判定胜负并记录得分[5]。根据功能需求，将该程序划分成如图2所示的几个模块，程序的主要人机交互界面划分如图3所示。

页面显示及主控模块：修改配置文件main.xml插入背景图片，通过TextView字符串组件来显示菜单与结束的字符串，用View.OnClickListener接口中的setOnClick Listener来监听是否有触摸，如果有触摸则运行相应的状态。程序运行过程中，自定义onDraw函数来绘制棋盘以及棋子，确保程序界面正常显示和触摸控制。

游戏模式选择模块：因为本程序可以由用户选择玩家对弈还是人机对弈两种模式，所以在进入页面中提供游戏模式选择按钮，用户点击按钮时，名为mMenuTv的菜单的字符串组件将获取到的选择状态传递给界面初始化函数showPopupWindow（）以及pop_choose_gobang配置文件来执行相应的操作。

游戏胜负判断模块：通过继承View并重载返回值为布尔类型的onTouchEvent函数来判断该触碰是否可以落子，如果对应的位置为空的话，则在该位置记录落子信息，并且判断游戏胜负。胜负判断主要通过获取该点并通过遍历它的周围来判断横向、纵向或者斜向是否有五子相连，Android中的View横纵坐标与正常的x、y轴不同，它是正常的坐标轴顺时针旋转90度，所以判断五子相连的时候，横向则是y轴加减、纵向才是x轴加减。如果遍历出有五个字相连则调用GameOver函数中的Toast.makeText来显示游戏结束，否则继续游戏。胜负判断的流程图如图4所示。

3  结  论

本文实现了一款Android平台下的五子棋游戏程序。程序中可以实现玩家对弈和人机对弈的功能，其中人机对弈功能采用4层的α-β剪枝树搜索算法实现，经过测试，程序的智能水平已经能够达到业余中高级水平，并且程序运行速度较快，落子时间以及胜负判定时间都可以接受。程序基于Android 6.0开发，能够兼容市面上绝大多数手机，兼顾了趣味性和智能性。

参考文献：

[1] 董慧颖，王杨.多种搜索算法的五子棋博弈算法研究 [J].沈阳理工大学学报，2017，36（2）：39-43+83.

[2] 孙世文.五子棋人工智能算法实现研究 [J].中国新通信，2018，20（23）：143.

[3] 周洋，邓莉，谢煜.一种五子棋博弈算法的分析 [J].现代计算机（专业版），2017（10）：8-10.

[4] 毛丽民，卢振利，刘叔军，等.五子棋对弈机器人移动平台的研究 [J].微特电机，2017，45（1）：9-14.

[5] 刘洋.点格棋博弈中UCT算法的研究与实现 [D].合肥：安徽大学，2016.

作者简介：宋万洋（1991-），男，汉族，天津人，助教，硕士研究生，研究方向：软件工程、数據挖掘。