摘 要

随着智能手机的不断普及，人们对手机的需求早已不再是简单的通讯功能，于是手机游戏登上了历史舞台。作为智能手机操作系统的主流，android系统占据了大部分市场份额。本研究从android智能手机游戏入手，探讨手机游戏——军棋的设计与实现过程。并以军棋作为代表，介绍对部分信息游戏研究的重大意义与实现难点。对军棋三种不同的游戏模式——翻棋、明棋、暗棋分别使用不完全相同的人工智能算法——专家系统算法、极大极小算法和估计算法，分析它们各自的优缺点。

关键词：手机游戏、部分信息游戏、人工智能

Abstract

with the popularization of intelligent mobile phone, demand for mobile phone is no longer a simple communication function, so the mobile phone game appeared on the stage of history. As the mainstream smart mobile phone operating system, Android systems occupy most of the market share. This study from the Android intelligent mobile phone game, mobile phone game of chess - Design and in the implementation process. And as a representative of the significance of chess, and difficulty of the game of Kriegspiel.This paper will analyze the advantages and disadvantages of expert system algorithm , the minimax algorithm and estimation algorithm which are used respectively by flip chess,bright chess and dark chess.

Keywords: mobile phone games, partial information games, artificial intelligence

目录

第一章 绪论 1

1.1研究背景 1

1.2研究意义 1

1.3研究介绍 2

第二章 智能算法 4

2.1专家系统算法 4

2.2极大极小算法 5

2.3估计算法 5

第三章 实现过程 7

3.1App风格确定 7

3.2棋盘的绘制 8

3.3战局的记录 8

3.4棋子的走法 9

3.4.1判断棋子 9

3.4.2判断位置 9

3.4.3判断大小 11

3.5随机布局的产生 11

3.6玩家操作的捕捉 12

3.7棋局胜负的判定 14

第四章 总结 15

4.1成果 15

4.2存在的不足 15

4.2.1不能实现联机或者联网作战 15

4.2.2细节不够人性化 15

4.2.3翻棋的专家系统算法不够智能 15

4.2.4明棋的博弈树计算步数有限 16

4.2.5暗棋的估计函数不够智能 16

参考文献 17

致谢 19

第一章 绪论

1.1研究背景

随着4G技术的普及，智能手机用户群体规模越来越大。在当今智能手机的操作系统中，谷歌的android和苹果的ios两家独大，特别是在国际有三星，国内有小米、华为的助攻下，谷歌的android系统占据着约八成的市场份额。同时，手机也早已不再是满足人们日常的通讯需求的工具^[1]，而是成为了人们生活中的伴侣。手游《王者荣耀》的日活跃人数高达5000W，证明了人们对高质量的手机游戏的迫切需求，手机游戏市场每年都保持高速增长的速度^[2]，其前景正被越来越多的人看好^[3]。而基于android系统的应用程序开发条件也已经相当成熟^[4]，同时安卓开发的入门门槛并不是很高，只需要了解基础的java知识和一个开发环境——Android Studio或者eclipse的ADT插件。所以比起PC端的大型3D网游，安卓手游更倾向于个人或者小型团队合作开发，人们对手游较高的热度，减轻了宣传、推广的负担，可以把更多的精力放在游戏的创意设计和游戏高质量的实现上^[5]。

1.2研究意义

人机博弈，即计算机博弈，是人工智能方面十分有挑战性的研究方向之一^[6]。人工智能机器人是悠久传统的一部分，这种传统从古代起，就把机器人的前身，即自动装置，当成自然神奇或者说是魔法的一部分^[7]。自从1946年，美国宾夕法尼亚大学研制出世界上的第一台计算机——ENIAC，我们就开始不断探索，比如图灵测试的提出。为了使计算机拥有人的智能，让计算机具有下棋的本领，并让计算机可以打败人类就成为了许多学者努力的方向^[8]。人工智能在计算机科学中是最重要的研究领域之一，它与算术、科技有关，并且研究成果被广泛地运用到各种工业领域中，比如，军事、心理，智能机器还有商业智能^[9]。长久以来，许多学者在机器博弈方面的探索取得了很多可喜的成绩，诸如五子棋、国际象棋等完备信息游戏取得了完美的胜利。但是比起双方都了解所有信息的完备信息博弈，在部分信息游戏中各方都只了解部分的信息，不确定性大大增加。参与者往往无法获得其决策所需的全部信息^[10]。一方面，对部分信息游戏的研究，有利于我们在许多现实生活中对不确定情景的把握，比如战争、股市环境。通过对部分信息游戏的研究建立的模型或者编写的算法，稍加修改就可能会很好适应现实生活中的各种不确定性情景，所以对部分信息游戏的研究，是实际的需求。 另一方面，部分信息游戏对于计算机来说，部分信息游戏是很难去实现的。这些游戏通常需要复杂的任务，不断变化的环境，不断迭代的信息，甚至无法预测的意外^[11]。比如对于深蓝的人工智能，它是在完全知道对手的情况下进行的，能够对现有的棋盘状况进行足够多的计算，预测下几步甚至十几步 。对于军棋这类部分信息游戏，此方法显然不够用。此外,一些游戏是特别具有挑战性的,因为随时可能出现的变量,无法准确定义的规则以及远远超过现在的计算机存储和计算能力的可能性。

1.3研究介绍

军棋是中国深受欢迎的棋类游戏之一。当四人时，四人在棋盘上分占四角，分为两方，相对的两家联合与另外两家对抗，互相配合战斗；两人游戏时，则分占棋盘的上下两角，相互作战。由于android手机屏幕普遍为长宽不相等的矩形，为了适应整块手机屏幕，从而使玩家拥有更好的游戏体验，本app采用两人游戏的军棋游戏。军棋棋盘分行走路线、10个行营、46个兵站和4个大本营，其中行走路线又分为公路和铁路^[12]。在公路线上，棋子可以一步一格地走；然而在铁路线上，棋子可以一步走很多格，但是必须是直线而且中间不能有其它棋子，包括我方棋子阻挡。如果是工兵，甚至可以摆脱直线的限制，在铁路线上允许拐弯，但是仍然不能跨越其它棋子。行营是所有棋子的保护区，绝对安全。而且在行营中的棋子不仅不能被攻击，而且可以任意攻击周围兵站的其它棋子。兵站是最最普通的摆放棋子的地方，没有任何特别之处也许正是它最特别的地方。大本营是在布局游戏中用来放置军旗的特殊地点，为了保障军旗的安全，它不仅处于每方的最后一排，而且每方有两个，真真假假，把兵法体现得淋漓尽致。布局对抗中，军旗能且只能摆放在自家大本营中，而另一个大本营可以摆放任何棋子，但是摆在大本营的棋子不允许移动。如果在对战中，如果一方的一颗棋子走进了另一方没有放置军棋的大本营，则也不许再进行移动。不管任何棋子，不管是布局时就在大本营还是后来走进去的，也无论是我方还是敌方，只要在大本营，就不允许走动，相当于已经死掉的活棋子。关于棋子，每方各有25个，包括1个司令、1个军长、2个师长、2个旅长、2个团长、2个营长、3个连长、3个排长、3个工兵、3颗地雷、2颗炸弹和1个军旗^[13]。除地雷、炸弹和军旗外，其它棋子均为生命棋子。生命棋子的大小关系如下，司令gt;军长 gt;师长gt; 旅长 gt;团长gt; 营长 gt;连长 gt;排长gt; 工兵。司令最大，工兵最小，而且并没有最小吃最大的循环。关于非生命棋子，地雷可以胜过除工兵以外的所有生命棋子；炸弹可以与所有棋子同归于尽，包括所有生命棋子和非生命棋子；军旗在布局游戏中是最小的，任何棋子都可以扛军旗（炸弹是炸军旗）。但是在翻棋游戏中，在没有被挖掉三颗地雷的情况下，军棋不能被任何棋子扛，包括炸弹炸；被挖掉三颗地雷之后，军棋能且只能被工兵扛，但是此时也能被炸弹炸了。军棋的获胜方法有两种，一是消灭对面所有可以移动的棋子，包括所有生命棋子和两颗炸弹；二是消灭对方的军棋。在翻棋对战中，一般是采用吃光的方法获胜；而在布局游戏中，一般则是采用拿旗的方法获胜。但是无论何种游戏模式，两种获胜方法通用，达到任意一个的获胜条件都能获得胜利。在翻棋游戏中，游戏开始，所有棋子被打乱任意摆放在所有兵站和大本营里，双方轮流走棋，走棋包括翻开任意一个未被翻开的棋子或者走动一步本方棋子。在明棋对战中，每局开始双方的棋子各摆在本方的阵地里，同样是在兵站和大本营，任何游戏模式的行营在初始布局中都是空的。关于摆放的初始布局，双方可以各自随意排兵布阵，只需要遵守三条简单的规则即可。一是军旗必须摆放在大本营，二是地雷只能摆放在最后两排，三是炸弹不能摆放在第一排。在双方完成调度之后，则各自一步，轮流走棋。军棋的暗棋，规则与明棋大致相同，唯一的不同是在暗棋状态下只能看见对方棋子的位置而不能看见对方棋子具体的大小，包括军旗。但如若某一方的司令被杀，那一方会亮出军旗。随机的布局再加上特有的玩法，使暗棋一直吸引着很多人，正所谓“兵者，诡道也”。

第二章 智能算法

2.1专家系统算法

翻棋的智能算法采用专家系统算法，判断当时的那一步棋局，根据事先确定的走法优先级，做出思考。

首先，遍历棋盘上所有的两点组合，判断是否存在这样的一个两点组合。其中一点为电脑方棋子，另一点为棋手方棋子。而且电脑方棋子大于棋手方棋子同时电脑方棋子可以走到棋手方棋子，即电脑方棋子可以吃掉棋手方棋子。如果遍历到这样的两点组合，则停止继续遍历，智能算法选择吃掉对方棋子。如果遍历完整个棋盘，并没有搜索到满足上述条件的两点组合，则进行第二轮遍历。第二轮遍历棋盘上所有的三点组合，判断是否存在这样的一个三点组合。第一点为电脑方棋子，第二点为空，第三点为棋手方棋子。同时棋手方棋子大于电脑方棋子，而且棋手方棋子可以走到电脑方棋子当前所在的点但是不能走到三点组合中为空的那个点。同样，如果搜索到满足上述条件的三点组合，则立即停止遍历，智能算法选择逃脱对方棋子追杀。如若不存在这样的三点组合，则开始第三轮遍历。智能算法的第三轮遍历，遍历棋盘上所有的两点组合。其中一点为我方棋子，不在行营；另一点为行营，且为空。如果找的这样的两点组合，则停止遍历，智能算法选择棋子进营操作。如果本轮依然没有搜索到符合条件的组合，则进行第四轮遍历。第四轮遍历同样搜索一个两点组合，规则如下：一点为电脑方棋子，另一点为棋手方棋子，棋力大小相等且电脑方棋子可以走到棋手方棋子位置。如果遍历到这样的两点组合，则结束本轮遍历，智能算法选择所遍历到的走法。如果第四轮遍历同样没有遍历到达到要求的两点组合，则开始进行第五轮遍历，搜索整个棋盘是否存在没有被翻的棋子，如果有，则智能算法随机进行翻棋操作。如果第五轮没有遍历到未被翻的棋子，即所有棋子都已经被翻出来了，则进行最后一轮遍历，搜索两点组合，能走棋的两点组合。一点为电脑方棋子，另一点为该电脑方棋子合法的能够走棋的位置。一旦搜索到，则智能算法选择该走法。从理论上来说，该轮遍历不可能遍历不到符合条件的两点组合，因为条件已经很低了。如果当前棋局的确没有符合条件的两点，那么胜负判断已经可以判我方即电脑方失败了，也无需调用智能算法了。

该算法为翻棋的智能算法，是仅仅针对当前棋局的智能算法，不能考虑对手即棋手方的走法，仅仅考虑一步。如果说有考虑两步甚至以上步数的话，也只是简单的逃脱敌方棋子的追杀的第二轮遍历。并不能计算到未来几步可能发生的其它情况，从而导致该智能算法选择的走法并不是很智能。

2.2极大极小算法

明棋的智能算法采用博弈树，极大极小算法。每个节点存储当前布局，选择的走法即从父亲节点走到该节点的方式，分数即根据当前布局评估的得分，该节点层数，该节点儿子的个数，整个博弈树的深度，怎样走到每一个儿子节点走法，当然还有儿子节点。对于分数的计算，采用局势评估函数进行计算。局势评估函数对于每个棋子，给予一定的评分，即该棋子的价值，红方为正，蓝方为负。整个棋局的分数为当前布局所有棋子的价值之和，分数越大，对红方即棋手方越有利；分数越小，对蓝方即电脑方越有利。对于每个棋子的价值，根据每个棋子的大小、作用进行定价。各个棋子价值的绝对值如下：排长为1、连长为2、营长为4、团长为7、旅长为12、师长为20、军长为36、司令为45、工兵为5、地雷为6。至于军旗，因为决定着整场战斗的胜负，虽然最小，但是价值理应无限的，本设计取9999。考虑到炸弹随着战局的发展，可以炸的棋子越来越小，所以其价值的绝对值为敌方最大棋子价值的绝对值的三分之一。对于走法的搜索，是通过遍历实现的。遍历棋盘上所有的两点组合，如果该两点组合满足走棋规则，即电脑方的棋子可以在棋盘上从一点走到另一点，则记录该走法，遍历结束之后则会根据所有这些记录的合法的走法，逐一产生儿子节点。接着所有这些产生的儿子节点，用相同的方法再次产生他们的儿子节点，当然判断条件改为棋手方走棋，就这样一代一代，循环往复，直到整颗博弈树的深度达到要求，即停止产生新的儿子节点。至于最最开始的根节点，则是智能算法所思考的布局，当前战况、布局，就这样，考虑了敌我双方在所考虑的步数范围内的所有走法的博弈树就产生了。至于最终智能算法走法的选择，采用极大极小算法。逆行分析是一种算法技术，从叶子开始^[14]。在奇数层即电脑方走棋时，选择分数最小的走法；在偶数层即棋手方走棋时，选择最大值。与博弈树的产生方向不同，最小值、最大值的选择从层数最大的节点开始往回计算。就这样，选择出了最终最坏情况中的最好情况，即为该智能算法选择的走法。