【基于android的五子棋游戏设计与实现】基于Android的五子棋游戏设计与实现

　　摘要：随着人工智能的不断发展，人工智能算法也随之兴起。将人工智能算法应用于游戏中，将深度算法与剪枝算法相结合，既加强了对人工智能算法的应用，也在一定程度上提高了游戏运算速度，能够为移动终端上的游戏软件设计与开发提供参考。
　　关键词关键词：人工智能；人工智能算法；Android系统；游戏软件开发
　　中图分类号：TP319 文献标识码：A 文章编号：1672-7800（2016）004-0098-02
　　0引言
　　Android系统是最近几年才涌现出来的智能手机操作系统，对于其它操作系统而言，其无疑是一个新宠。许多家智能手机制造商不断推出基于Android操作系统的智能手机，使得Android操作系统的市场份额及影响力与日俱增，其前景正被越来越多的人所看好[1]。早在2005年，新的移动操作系统就开始研制，这即是目前为人们所熟知的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成为四大基础组件，必须在项目的androidmanifest.xml文件中注册。四大基础组件是构造安卓应用程序的基础模块，要将它们组合起来，实现数据传输并控制程序的运行尤为关键。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系统功能实现
　　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次测试时，表明黑白双方都没有成五和双活四、活四等棋型，只有让电脑挑选最佳的落子位置落子。首先看黑白双方有无双活三，没有就找半活四，依然没有就找活三、双活二或者活二等棋型。依此类推，直到游戏分出胜负，游戏结束。
　　深度优化法[]按照一定的顺序查找完一个分支再查找另一个分支[]准确性较高，但只能在给定的状态空间中进行，且速度较慢。
　　可行性剪枝算法[]该方法判断继续搜索能否得出答案，如果不能直接回溯[]准确性高、耗时较少
　　最优性剪枝算法[]它记录当前得到的最优值，如果当前结点已经无法产生比当前最优解更优的解时，可以提前回溯[]效率较高
　　极大极小数算法[]是一个递归过程，通过计算节点值，然后又不断返回上一层
　　5结语
　　本文基于Android平台设计开发了五子棋游戏系统，该系统主要实现人机博弈，通过电脑进行胜负判定。本文详细介绍了五子棋人工智能算法（各算法对比见表1），并在设计上进行了优化。后续还需对五子棋坐标进行更为深入的研究。
　　参考文献参考文献：
　　[1]唐烨.安卓之父的传奇故事[J].沪港经济，2012（1）：66-67.
　　[2]李宁.Android/OPhone开发完全讲义[M].北京：中国水利水电出版社，2012.
　　[3]余志龙，王世江.GoogleAndroidSDK开发范例大全[M].北京：人民邮电出版社，2009.
　　[4]党李成.基于GoogleAndroid智能手机平台的研究与应用[D].合肥：安徽大学，2003.
　　（责任编辑：孙娟）

【基于android的五子棋游戏设计与实现】基于Android的五子棋游戏设计与实现

https://m.bjyld.com/gwy/361078/