Android五子棋小游戏开发设计(10)
时间:2017-02-12 17:06 来源:毕业论文 作者:毕业论文 点击:次
（2） 负极大值搜索（Negamax Algorithm） 在极大极小过程中，每一次进行极大或者极小的比较之前，都要对到底是要选择极大还是极小节点进行判断，1975年Knuth和Moore提出的负极大值算法旨在消除两方面的差别，使算法简洁优雅。 它的核心思想在于：父节点的值是各子节点的负数的极大值。 负极大值搜索的原理和极大极小值是搜索一样的，只是表达形式不同，并且由于它的简洁，目前已经广泛取代了极大极小值算法。 （3） alpha-beta剪枝算法 然而在极大极小搜索的过程中，存在着一定程度的数据冗余，剔除这些冗余数据，是减小搜索空间的必然做法，所采用的方法就是1975年Monroe Newborn提出的alpha-beta剪枝。 alpha-beta搜索由于过程简单、容易理解、且占用空间小等优良特点被广泛应用，成为现在主流的搜索算法的基础。但是它也有缺点，即它对于节点的排列非常敏感。对于同一层上的节点，如果排列合适，剪枝效率就很高，可以使实际搜索的博弈树达到最小树。所谓最小树就是一经向下搜索，第一个节点就是要寻找的走步。可是，如果节点的排列顺序不是从最差到最好，就有可能使剪枝一直无法进行，从而实际上搜索了整棵的博弈树。 大多数alpha-beta剪枝算法都采用深度优先的搜索策略，是因为深度优先搜索较之宽度优先搜索节省存储空间，只需保存根节点到当前搜索节点的路径上的节点信息即可。 4 系统实现 本章具体介绍本设计中如何具体实现每个模块，最终实现整个系统。包括算法的设计思想和各个模块实现所使用的具体方法和技术点。 4.1 人工智能算法思想 本系统主要的算法应用在电脑的人工智能上面。接下来介绍一下本系统中人工智能的实现方法。 人工智能分析的最终目的是为了在棋盘上所有还未下过棋子的点中找到最合适的点来落子，这些点被放在一个list里面。但是如果遍历所有空白的点，这样过于浪费资源和时间，所以这里做了一个优化，限定一个范围，只遍历范围内的空白点。本系统中限定的范围就是所有已经下过的棋子的范围加1。在分析之前会初始化计算范围，并清除之前的分析结果。 第一步棋的下法上不需要做过多的判断和分析。如果玩家的第一步棋下在棋盘边上，则将电脑的第一步棋放在棋盘中央（point（maxX/2,maxY/2））；否则设置电脑的第一步棋放在玩家棋子的左边，即设置该点的横坐标为玩家第一步棋的横坐标x-1。 之后的每一步棋要进行三次分析： （1） 第一步分析 人工智能所做的第一步分析就是由一个算法计算出如果在当前位置上落下一枚棋子会形成怎样的形式。 这里所有尝试的位置都是包含在之前算出的范围内的空白点。若其中有绝杀点（可直接连成五子，胜利）则直接停止分析，否则电脑会分别计算出电脑和玩家在横、纵、正斜线方向和反斜线方向四个方向上可形成的状态，比如活四，活三等。如果里面有死棋（不可能有五子）情况或活1，半活2及其以下结果直接抛弃。第一次分析结束后将最多得到八个结果（敌我分别在四个方向各一）。 （2） 第二步分析 人工智能的第二步分析的目的是将第一步中所得的最多四个对象组合成为一个对象（敌我各一）。 由于在第一步分析中如果有绝杀棋就将中断分析直接下子，所以此时最好的结果就是活四棋。因此，在第二步分析中分成两个步骤分别分析敌我此时的形势，如果找到可以制造出活四的位置，则直接下子，中断分析。若无此位置，则将继续向下分析找出活三，半活三和活二的情况，并作统计，最后根据优势棋子的数量排序。 (责任编辑：qin) |