基于Android的五子棋游戏设计与实现
作者：李舒婷 高燕
来源：《软件导刊》2016年第04期
        摘要：随着人工智能的不断发展，人工智能算法也随之兴起。将人工智能算法应用于游戏中，将深度算法与剪枝算法相结合，既加强了对人工智能算法的应用，也在一定程度上提高了游戏运算速度，能够为移动终端上的游戏软件设计与开发提供参考。
        关键词关键词：人工智能；人工智能算法；Android系统；游戏软件开发
        中图分类号：TP319 文献标识码：A 文章编号：1672-7800（2016）004-0098-02
        0引言
        Android系统是最近几年才涌现出来的智能手机操作系统，对于其它操作系统而言，其无疑是一个新宠。许多家智能手机制造商不断推出基于Android操作系统的智能手机，使得Android操作系统的市场份额及影响力与日俱增，其前景正被越来越多的人所看好[1]。早在200
5年，新的移动操作系统就开始研制，这即是目前为人们所熟知的Android。经过两年多的研发，Android的第一个版本Android1.0在2007年11月5日被发布，而HTC（宏达电子）也在10个月后发布了世界上第一部装有Android系统的手机：G1，这也标志着Android正式成为移动操作系统大家族的成员，而且出身名门[2]。AndroidSDK历经数次改版（m5.rcl5、0.9），2008年底，全球第一款由美国T-Mobile电信与HTC（宏达电子）正式推出的“G-Phone”（代号为“Gl”），让一直处于“软件模拟器”的Android正式成为“机器人”，也有人将其称为“Dream”[3]。
        人工智能算法与Android系统的结合，使得游戏运算速度有了一定程度的提高，同时也促进了安卓系统及其编程的应用。
        1总体设计
        这款五子棋游戏是基于Android操作系统而设计开发的，其功能简单明了，主要实现人机对战模式。系统可划分为3个类别：棋盘类、消息面板类、控制面板类，如图1所示。
        2系统开发运行环境
        Android虚拟机是基于寄存器的，这与普通的Java基于堆栈不同，其速度得到了很大提升，这为基于Android平台开发游戏提供了坚强后盾[4]。
        Android上的应用程序可以分成4种主要类型：Acitivity、Service、Receiver和Contentprovider。Acitivity、Service、Receiver和Contentprovider成为四大基础组件，必须在项目的l文件中注册。四大基础组件是构造安卓应用程序的基础模块，要将它们组合起来，实现数据传输并控制程序的运行尤为关键。Android构成和工作流程如图2所示。
        3系统功能实现
        3.1棋盘实现
        棋盘是游戏的关键，首先要对棋盘进行绘制。Surface是Android系统最基础的一种语言，整个棋盘都用Surface进行绘制。每一个Window对应一个Surface，每个Surface对象都是通Surfaceflinger合成到FrameBuffer。每个Surface都是双缓冲，都有一个BackBuffer和FrontBuffer，BackBuffer是画图的，FrontBuffer则是用来合成的。
        3.2棋坐标实现
        在游戏中，胜负判定是根据落下的最后一颗棋子来决定。应该从落子的位置出发，从横向、竖向、正斜、反斜这4个方向来进行判断。在落下棋子的同时，获得横坐标与纵坐标的数据，即可获得该子落下的位置坐标。
        3.3胜负功能判定
        游戏的结果就意味着输赢，在五子棋游戏中，白子（黑子）五子任意方向连成一条线，则游戏结束，这也是判断游戏胜负的标准。结合深度优化算法和剪枝算法，可以对游戏进行3次深度搜索，当游戏一开始，最先落子的位置大部分在棋盘的中央，所有搜索范围应该从棋盘中央开始，这样可以减少搜索时间。
        4算法实现
        当游戏开始时，放入棋盘的棋子应该考虑如何防守住对手；同样，也应该考虑到自己下一步的最佳位置，不仅要“攻”而且要“防”。该游戏结合深度算法和剪枝算法，对棋子进行3次搜索，判断出电脑最佳落子位置。
        极大树极小树是博弈游戏中最常用的算法之一。设计算机落子的节点为Max，对方落子的节点为Min。当该层的节点是奇数时为Max，是偶数时则为Min。当节点是Max时，该值为下一层Min的最大值；如果为Min，则该层的值是下一层Max的最小值，也即当电脑（玩家）落子时，寻一个当前的最佳位置，预测下一步玩家（电脑）的落子位置。该位置对自己不利，但对对手有利。这是一个递归过程，通过计算节点值，然后又不断返回上一层。
        深度优先搜索（DFS）和广度优先搜索（BFS）也是常用算法，这两个方法的主要区别在于对下一个节点的选择。DFS首先选择其连接节点，若它的下个节点已经全部被遍历过或者不存在，返回到上一个节点，接着遍历其它未被遍历的节点。BFS方法是逐个遍历它所连接的节点，将已访问过的节点放到队列中，再进行下一个节点的遍历。
        Alpha-Beta剪枝算法是，当预测深度为3时，在不影响结果的前提下，去除一些不必要的节点。剪枝算法是通过递归方法实现的，一个是Alpha，即搜索到的最好值；另一个是Beta，即搜索到的最坏值。每次搜索的结果都和Alpha和Beta值有关，从而决定是否停止或返回搜索。
        结合深度优化算法和剪枝算法，可以对游戏进行3次深度搜索，影响搜索效率的时间因
素有很多，一个是搜索的深度，另一个则是搜索的宽度。当游戏开始时，最先落子的位置大部分在棋盘中央，所有搜索范围应该从棋盘中央开始，这样可以减少搜索时间。接下来在搜索范围为玩家的第一步棋子的边界值加1，然后分别遍历黑白两方已下的棋子，如果该棋子在当前搜索范围内，则当前的搜索范围不作任何改变；如果该棋子不在当前搜索范围之内，则修改当前搜索范围使得该棋子在当前搜索范围之内。搜索时应该先搜索有棋子的地方，这样可以提前进行剪枝，同样可以缩短时间。
        第2次搜索是为了缩短系统搜索时间，节省系统开销，系统将对黑白双方的第1次搜索结果分别作分析。第2次分析的目的主要是分析第1次搜索的结果，第1次搜索结果会把一步棋在4个方向上形成的结果生成最多4个对象，而第2次搜索把这4个对象组合成一个对象。
        当进行到第3次测试时，表明黑白双方都没有成五和双活四、活四等棋型，只有让电脑挑选最佳的落子位置落子。首先看黑白双方有无双活三，没有就半活四，依然没有就活三、双活二或者活二等棋型。依此类推，直到游戏分出胜负，游戏结束。
        3系统功能实现
游戏xml文件修改
        3.1棋盘实现
        棋盘是游戏的关键，首先要对棋盘进行绘制。Surface是Android系统最基础的一种语言，整个棋盘都用Surface进行绘制。每一个Window对应一个Surface，每个Surface对象都是通Surfaceflinger合成到FrameBuffer。每个Surface都是双缓冲，都有一个BackBuffer和FrontBuffer，BackBuffer是画图的，FrontBuffer则是用来合成的。
        3.2棋坐标实现
        在游戏中，胜负判定是根据落下的最后一颗棋子来决定。应该从落子的位置出发，从横向、竖向、正斜、反斜这4个方向来进行判断。在落下棋子的同时，获得横坐标与纵坐标的数据，即可获得该子落下的位置坐标。
        3.3胜负功能判定
        游戏的结果就意味着输赢，在五子棋游戏中，白子（黑子）五子任意方向连成一条线，则游戏结束，这也是判断游戏胜负的标准。结合深度优化算法和剪枝算法，可以对游戏进行3次深度搜索，当游戏一开始，最先落子的位置大部分在棋盘的中央，所有搜索范围应该从棋盘中央开始，这样可以减少搜索时间。
        4算法实现
        当游戏开始时，放入棋盘的棋子应该考虑如何防守住对手；同样，也应该考虑到自己下一步的最佳位置，不仅要“攻”而且要“防”。该游戏结合深度算法和剪枝算法，对棋子进行3次搜索，判断出电脑最佳落子位置。
        极大树极小树是博弈游戏中最常用的算法之一。设计算机落子的节点为Max，对方落子的节点为Min。当该层的节点是奇数时为Max，是偶数时则为Min。当节点是Max时，该值为下一层Min的最大值；如果为Min，则该层的值是下一层Max的最小值，也即当电脑（玩家）落子时，寻一个当前的最佳位置，预测下一步玩家（电脑）的落子位置。该位置对自己不利，但对对手有利。这是一个递归过程，通过计算节点值，然后又不断返回上一层。
        深度优先搜索（DFS）和广度优先搜索（BFS）也是常用算法，这两个方法的主要区别在于对下一个节点的选择。DFS首先选择其连接节点，若它的下个节点已经全部被遍历过或者不存在，返回到上一个节点，接着遍历其它未被遍历的节点。BFS方法是逐个遍历它所连接的节点，将已访问过的节点放到队列中，再进行下一个节点的遍历。
        Alpha-Beta剪枝算法是，当预测深度为3时，在不影响结果的前提下，去除一些不必要的节点。剪枝算法是通过递归方法实现的，一个是Alpha，即搜索到的最好值；另一个是Beta，即搜索到的最坏值。每次搜索的结果都和Alpha和Beta值有关，从而决定是否停止或返回搜索。
        结合深度优化算法和剪枝算法，可以对游戏进行3次深度搜索，影响搜索效率的时间因素有很多，一个是搜索的深度，另一个则是搜索的宽度。当游戏开始时，最先落子的位置大部分在棋盘中央，所有搜索范围应该从棋盘中央开始，这样可以减少搜索时间。接下来在搜索范围为玩家的第一步棋子的边界值加1，然后分别遍历黑白两方已下的棋子，如果该棋子在当前搜索范围内，则当前的搜索范围不作任何改变；如果该棋子不在当前搜索范围之内，则修改当前搜索范围使得该棋子在当前搜索范围之内。搜索时应该先搜索有棋子的地方，这样可以提前进行剪枝，同样可以缩短时间。
        第2次搜索是为了缩短系统搜索时间，节省系统开销，系统将对黑白双方的第1次搜索结果分别作分析。第2次分析的目的主要是分析第1次搜索的结果，第1次搜索结果会把一步棋在4个方向上形成的结果生成最多4个对象，而第2次搜索把这4个对象组合成一个对象。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。