1、摘要：近年来随着手机的不断普及,导致了手机游戏市场呈现爆炸式的发展。目前Google推出了基于Linux平台的开源手机操作系统Android。通过基于Android平台的手机游戏的开发能加深对面向对象程序设计的理解，掌握开发基于移动平台的应用程序的方法与技术。本课题结合手机游戏的发展现状和需求，利用Eclipse功能强大的集成开发环境，在Android平台上利用核心库和Dalvik虚拟机使用Java语言设计出一款智能型五子棋游戏。此游戏利用AI算法中的估值函数来实现人机对战，具有一定的智能性。同时该游戏能设置难易度，可以保存和装入游戏进度。通过此平台，用户可以与电脑玩家进行对战，并能从中体会到
2、斗智的乐趣。关键词：Android系统；手机游戏；五子棋；人机对战Mobile Phone Game Development based on Android PlatformAbstract： In recent years,with the increasing popularity of mobile phones, this phenomenon leads to a explosive development in the mobile games market.At present Google rolls out an open source mobile operating s
3、ystem-Android based on Linux platform. Through developing the mobile games based on the Android platform, the developer can deepen the understanding of object oriented programming and master the developments method and technology of the applications based on the mobile platform.This project is combi
4、ned with the present dcvclopmcnl and requirements of the mobile gamcs.lt uses the tool of Eclipse which have powerful integrated development environment, the Android platform using the Dalvik virtual machine and cors library, and uses Java language to design a paragraph of intelligent renju game. Th
5、e game uses the valuation function of Al algorithm to realize human-machine against and has a certain intelligence against. The game also can set difficulty degrees and can save and load the game progress. Through this platform, users can play against with the computer player and also can appreciate
6、 the fun of the battle of wits.Keywords： Android system; Mobile gamc:Gobang ;Man-machinc against目录1绪论11.1课题的研究背景11.2课题研究的目的与意义11.3手机游戏的特点21.4手机游戏的发展情况21.4.1手机游戏开发平台21.4.2手机游戏的现状31.4.3手机游戏的未来42基础知识介绍52.1开发工具简介52.2五子棋及简介52.2.1五子棋简介52.2.2游戏规则52.2.3名词解释63需求分析83.1可行性分析83.1.1经济可行性83.1.2技术可行性83.2功能需求93.3性能
7、需求93.3.1实用性93.3.2可靠性93.3.3界面和操作103.3.4容错性104总体设计114.1软件总体结构设计114.2用户界面设计125系统设计与实现145.1AI设计145.1.1极大极小树145.1.2深度优先搜索（DFS）155.1.3剪枝方法155.1.4静态估值函数165.2主要游戏模块175.2.1游戏主屏幕175.2.2游戏设置175.2.3游戏帮助205.2.4游戏主界面226系统测试与评价346.1软件测试的基本概念346.2测试与评价346.2.1单元测试346.2.2集成测试376.2.3系统测试与评价387总结391绪论1.1课题的研究背景手机游戏是相对于
8、传统计算机游戏而提出。通俗来说，手机游戏就是在手机上进行游戏应用。最早手机游戏是1997年Nokia推出手机内置游戏贪吃蛇（Snake）。随着手机终端和移动通信网络不断发展，手机游戏也正在经历由简单到复杂进化过程。2003年9月，随着移动百宝箱正式收费，国内手机游戏产业正式启动，用户增长十分迅速。短短几个月时间里，手机游戏用户就增长到200万。此后时间里，手机游戏用户规模一路高歌猛进，在2005年时即突破1500万。近年来,因特网在国内迅速普及,导致了网络游戏的高速发展。同样手机的普及,导致了手机游戏市场呈现爆炸式的发展。尤其是国内外巨大的手机拥有量,更是让商家看到了商机,手机游戏市场利润将会
9、十分丰厚。面对潜力如此巨大的手机游戏市场,各游戏开发商,运营商,服务商以及手机终端厂商等都纷纷开始了各自的应战准备,以便抢占商机。诺基亚,索爱,摩托罗拉等各大手机厂商开始不断的提升手机在游戏方面的性能,同时还在手机操作系统方面采用开放式的平台,方便用户享受不同的手机游戏业务。而国内游戏开发商,如盛大,网易等公司,纷纷跻身手机游戏开发商行列.新浪,搜狐等著名的门户网站,也纷纷涉足手机游戏领域,相继开辟了各自的手机游戏频道和栏目,其他一些游戏网站也都全面加快了手机游戏开发的步伐。目前Google于2007年11月5日宣布的基于Linux平台的开源手机操作系统Android在智能手机领域这块虽然不是
10、做的最早的，但是现在确实做的最好的，市场满意度和市场份额也是整个智能机市场里较大的一个。据了解，最早进入Android市场的台湾宏达电陆续在一年内推出了G1、Magic、Hero、Tattoo等手机，三星也在近期推出Galaxyi7500，摩托罗拉在早前推出新款Android手机Droid，中国移动也以Android为基础开发了OPhone平台。1这些都证明Android已经成为了智能手机市场的重要发展趋势。1.2课题研究的目的与意义近来随着计算机和手机的快速发展，出现了各种各样的游戏，使得人们能有更多的娱乐项目。手机的游戏给大家提供一个轻松快乐放松愉悦，当然在游戏的过程中你能够体会到人生的乐
11、趣或者是能够感悟到更多的人生的道理或者是你能学到更多的知识获得更多的启发，我想这个是在游戏上面衍生出来的。1而棋类游戏能起到锻炼人的思维和修身养性的作用，因此作者选择设计这款手机版的五子棋游戏软件，可以供人们闲暇时间随时随地地在进行娱乐的同时锻炼了自己的脑力。1.3手机游戏的特点作为运行在手持设备上的应用程序，手机的硬件特征决定了手机游戏的特点。1.庞大的潜在用户群全球在使用的移动电话已经超过10亿部，而且这个数字每天都在不断增加。在除美国之外的各个发达国家，手机用户都比计算机用户多。手机游戏潜在的市场比其他任何平台，比如PlayStation和GameBoy都要大。2.便携性在控制台游戏时代
12、，GameBoy热销的一个原因就是便携性人们可以随时随地沉浸在自己喜欢的游戏中。和游戏控制台或者PC相比，手机虽然可能不是一个理想的游戏设备，但毕竟人们总是随时随身携带，这样手机游戏很可能成为人们消遣时间的首选。3.支持网络因为手机是网络设备，在一定限制因素下可以实现多人在线游戏。4.不足之处娱乐游戏市场的主要消费群体大多为年轻人，收入水平不高。目前移动所推出的JAVA百宝箱中的手机游戏，偏重于低端的娱乐游戏，但能够支持JAVA程序下载使用的手机数量不多，而且大多为3000元以上的高端产品。这就使目前手机游戏产品的目标用户与手机终端用户存在矛盾，喜欢玩游戏的用户终端产品消费能力弱；终端支持游戏
13、功能的用户对游戏的接受度和使用率不高。目前开发手机游戏产品的投入和成本相对少，进入该市场的SP较多。2但多数SP由于受技术、成本投入等因素的影响，产品设计从游戏方案过程设计到任务设计均有欠缺，游戏质量粗糙，在产品品质上下工夫相对较少。1.4手机游戏的发展情况最早手机游戏是1997年Nokia推出手机内置游戏贪吃蛇（Snake）。随着手机终端和移动通信网络不断发展，手机游戏也正在经历由简单到复杂进化过程。32003年9月，随着移动百宝箱正式收费，国内手机游戏产业正式启动，用户增长十分迅速。短短几个月时间里，手机游戏用户就增长到200万。此后时间里，手机游戏用户规模一路高歌猛进，在2005年时即突
14、破1500万。1.4.1手机游戏开发平台手机游戏开发一般都是开放式的开发平台。下面对目前市面上流行的手机游戏平台做一个简单2的介绍。1.嵌入/内置式游戏早期手机的功能简单、屏幕也仅仅是单色，手机厂商能做的就是在手机内置一些简单的游戏。这些游戏都是厂商以自己的专属平台开发的，这些发售时就内置的游戏在手机预存了多少就是多少，用户无法自己新增或删除。2. .In-FusioExEn娱乐平台虽然现在手机屏幕变成了彩色，但是无论内置游戏如何好玩也总有玩腻的时候。因此，手机用户希望能够玩新的游戏或者像下载图片、铃声那样通过无线网络下载游戏。法国In-Fusio公司看中了这个市场，在2001年推出了ExEn
15、（ExecutionEngine）游戏平台，通过把专属的ExEn芯片加入手机内，赋予手机彩色画面与流畅的执行速度，让手机也有掌上游戏机的效果。3. .J2ME平台J2ME（Java2PlatformMicroEdition）平台上可以下载和安装一些小的应用程序。J2ME简单的可以理解为Java的移动版本，其MIDP（MobileInformationDeviceProfile，即移动信息装置简表）架构就是专门为手机与PDA设计的。4目前MIDP有1.0和2.0之分，后者在兼容性以及游戏的多媒体表现力上（如音效和振动方面）有更好的效果，此外通过测试软件显示，支持MIDP2.0的JAVA游戏在图形
16、运行能力对比1.0版本也有更优秀的表现。4. .Android平台Android一词的本义指“机器人”，同时也是Google于2007年11月5日宣布的基于Linux平台的开源手机操作系统的名称，该平台由操作系统、中间件、用户界面和应用软件组成，号称是首个为移动终端打造的真正开放和完整的移动软件。5Android作为Google企业战略的重要组成部分，将进一步推进“随时随地为每个人提供信息”这一企业目标的实现。Android不仅在智能手机市场与苹果、微软、RIM等公司进行争夺，索尼、罗技和东芝等10多家厂商均计划在生产的平板电脑、网本、机顶盒、电子书阅读器以及电视机上使用Android系统。G
17、artner副总裁肯杜兰尼说：“Android是目前唯一一个能够取代iOS的产品。”1.4.2手机游戏的现状根据iResearch艾瑞市场咨询整理的国外数据显示，全球手机游戏市场的收入规模在2005年达到了102亿美元，2008年达到520亿美元。12在中国，游戏已成为娱乐第一大产业，2009年产业总值达256亿元。如今电脑游戏毫无疑问的成为了人们主要的休闲娱乐方式。上网玩游戏几乎成了年轻人的习惯，尤其是经历了全球性金融危机后，游戏产业的良好态势仍然保持强劲。没有人3不看好游戏产业的光明前景。移动领域同样如此，09年全球手机娱乐市场圈增长势头强劲，其中游戏市场增长率与份额均已超过音乐。随着国内
18、通信运营商集体加快3G宽带无线的建设和智能手机的不断普及，移动娱乐业务已经成为移动互联网业务增长的重要推动力量。6在中国，据预测2010年手机游戏市场总规模将达到9527亿元从2003年到2010年的市场规模年均复合增长率为624。为了提升增值业务收入。运营商纷纷将目光盯上了手机游戏。1.4.3手机游戏的未来3G时代到来，手机上网逐渐普及，资费进一步下调，尝试使用手机进行娱乐互动的人们必然逐渐增加。随着移动支付系统的成熟和盈利模式逐渐清晰，随着资本对于手机游戏市场的关注，随着行业内各个环节逐渐完善与壮大，随着行业内从业人员专业水平的不断提高，中国的手机游戏产业将会迎来一个发展高峰。742基础知
19、识介绍2.1开发工具简介本系统在Eclipse集成开发环境下完成，在Android平台上设计出一款智能型游戏软件。主要使用Java语言。由于技术有限，本游戏的界面属于2D的。基于Android的手机游戏开发需要AndroidSDK、JDK、Eclipse、ADT等开发工具。8JDK是整个Java的核心，包括了Java运行环境，Java工具和Java基础的类库。在Eclipse编译IDE环境中，需安装ADT(AndroidDevelopmentTools)Plug-in,这是Android的开发工具。92.2五子棋及简介2.2.1五子棋简介五子棋相传起源于四千多年前的尧帝时期，比围棋的历史还要悠
20、久，可能早在“尧造围棋”之前，民间就已有五子棋游戏。有关早期五子棋的文史资料与围棋有相似之处，因为古代五子棋的棋具与围棋是完全相同的。在上古的神话传说中有“女娲造人，伏羲做棋”一说，增山海经中记载：“休舆之山有石焉，名曰帝台之棋，五色而文状鹑卵。”李善注引三国魏邯郸淳艺经中曰：“棋局，纵横各十七道，合二百八十九道，白黑棋子，各一百五十枚”。这段虽没明讲是何种棋类，但至少知道远古就以漂亮的石头为棋子。因而规则简单的五子棋也可能出自当时，并是用石子作棋子。亦有传说，五子棋最初流行于少数民族地区，以后渐渐演变成围棋并在炎黄子孙后代中遍及开来。在古代，五子棋棋具虽然与围棋相类同，但是下法却是完全不同的
21、。正如辞海中所言，五子棋是“棋类游戏，棋具与围棋相同，两人对局，轮流下子，先将五子连成一行者为胜”。传统五子棋的棋具与围棋相同，棋子分为黑白两色，棋盘为1515，棋子放置于棋盘线交叉点上。两人对局，各执一色，轮流下一子，先将横、竖或斜线的5个或5个以上同色棋子连成不间断的一排者为胜。五子棋，日文亦有“连五子、五子连、串珠、五目、五目碰、五格、五石、五法、五联、京棋”等多种称谓，英文则称之为“FIR(FiveInARow的缩写)、Gomoku(日语“五目”的罗马拼音)、Gobang、connect5、mo-rphion”。捷克语piskvorky，韩语omok2.2.2游戏规则对局开始时，先由执
22、黑棋一方将一枚棋子落在天元点上，然后由执白棋一方在黑棋周围的交叉点上落子。但是，为了尊重对方和礼貌起见，持白棋的一方通常将盘面的第二着棋布在自己河界的一侧，即直止或斜止。此后黑白双方轮流落子，直到某一方首先在棋盘的横线、纵线或斜线上形成连续五子或五子以上（仅对白棋而言），则该方就算获胜。连珠五子棋的一个特点是先行的一方优势很大，因此在职业比赛中对黑方做了种种限制，以利5公平竞争。五子棋的比赛规则如下：（1）黑先、白后，从天元开始相互顺序落子。（2）最先在棋盘横、纵或斜向形成连续的同色五个棋子的一方为胜。（3）黑棋禁手判负、白棋无禁手。黑棋禁手有“三三”、“四四”和“长连”，包括“四三三”和“四
23、四三”。黑棋只能以“四三”取胜。（4）如分不出胜负，则到为平局。（5）五连与禁手同时形成，判胜。（6）黑方禁手形成时，白方应立即指出。若白方未发现或发现后不立即指出，反而继续落子，则禁手失效，不再判黑方负。10在本游戏中，没有采用职业比赛的规则，直接采用明间规则，一人一手棋，先成5为胜。2.2.3名词解释1阳线与阴线（1）阳线：棋盘上可见的横纵直线。（2）阴线：棋盘上无实线连接的隐形斜线。2.连：在棋阳线或阴线上形成同色棋子不间隔地紧紧相连。（1）五连：在棋盘上形成的5个同色棋子的“连”。（2）长连：在棋盘上形成的6个或6个以上同色棋子的“连”。3.三：指“活三”，己方再走一着就能形成“活四”
24、的三。（1）连三：在棋盘某一条阳线或阴线上有同色三子相连，并且在此三子两端延长线上有一端至少有一个、另一端至少有两个无子的交叉点与此三子紧密相连。（2）跳三：中间仅间隔一个无子交叉点的连三，但两端延长线均至少有一个无子的交叉点与此三子相连。（3）单活三：只有一个点能形成“活四”的四叫做“单活三”。4.四：包括“活四”和“冲四”。（1）活四：有两个点能形成“连五”的四就是活四。（2）冲四：只有一个点能形成“连五”的四叫做“冲四”或“单四”。（3）白棋再下一着可形成长连的局面也视为“四”。5.禁手：仅对黑棋对局中禁止使用的着法。黑棋禁手包括“三三”、“四四”和“长连”。1）三三：由于黑方走一着在无
25、子交叉点上同时形成二个或二个以上黑方“活”的局面。62）四四：由于黑方走一着在无子交叉点上同时形成二个或二个以上黑方“四”的局面。6.先手与四三（1）先手：对方必须应答的着法，其中“冲四”称为绝对先手。（2）四三：指某一方同时具备两个先手，其中一个是“四”，一个是“活三”。7.进阶禁手（1）三手可交换：是指黑棋下盘面第3着棋后，白方感觉黑方棋形不利于己方，可在第四着时有一次提出交换的机会，即执白棋一方变为执黑棋一方，而黑方不可以不换。（2）五手两打：是指黑棋在下盘面上关键的第5手棋时，必须下两步棋，让白棋在这两步棋中任选一步，然后再继续对弈。一般说来，白棋肯定拿掉对白方不利的一点，而保留对黑方
26、较为不利的那点让黑方行棋。73需求分析3.1可行性分析3.1.1经济可行性开发该手机五子棋游戏软件时需要估算软件的开发费用和今后的运行以及维护的费用，还要估算该软件可以给手机游戏商带来多少利益。下面从以几个方面对该软件的经济可行性进行具体的分析：（1）一次性项目建设费用为：人民币12000元。其中：计算机设备及游戏软件费：人民币12000元整个项目建设期为0.4年（2）投产后的年发生费用预计为：人民币7000元。其中：年运营耗材费：人民币5000元年折旧费（支付游戏软硬件维护及更新）：人民币2000元（3）新游戏投产后预期年经济收益为：人民币20000元。其中：销售信息利用增值：人民币1000
27、0元游戏收益：人民币7000元客户满意度提升的收益：人民币3000元（4）预计本游戏使用寿命五年，按后年利率5%计算：项目投资回收期=项目投资/（年收入-年支出）=12000/（20000-7000）0.92年通过以上分析得知，该手机五子棋游戏软件的开发在经济上是切实可行的。3.1.2技术可行性根据该软件目标来衡量所需的技术是否具备，一般可从软硬件的性能要求、环境条件、操作人员水平和数量等方面去考虑和分析。作者考虑到手机游戏不同于一般的电脑单机游戏，所以在软件方面选择了Eclipse、jdk1.6.0_10和ADT进行此手机游戏的开发。Eclipse和jdk1.6.0_10均为非常成熟的开发工
28、具，保证了此手机游戏开发的可用性、可靠性和安全性。所以软件方面是切实可行的。11硬件方面选择Pentium系列及以上的CPU（推荐PentiumIV）、内存在128M以上（推荐256MB以上）、1GB硬盘空间（推荐3GB以上）就可以满足系统的开发需要。当然，硬件的配置越高，系统的开发和运行就会越顺畅。所以硬件方面是可行的。现在人们压力日益增大，需要劳逸结合才能获得更高的工作效率，工作之余的娱乐对每一个人8来说都是必不可少的。五子棋这种娱乐方式简单易学又具有深奥的技巧，非常富有趣味性和消遣性。在经过不断发展后，五子棋已经成为棋盘娱乐的一个重要的组成部分，它能够增强思维能力、开发智力，是人们休闲娱
29、乐的不错选择。因此，本系统能满足一定的实用性。3.2功能需求综合手机的高度普及和游戏的市场及发展前景，结合五子棋游戏的特点等考虑，此游戏应能够达到以下目标：（1）此游戏软件能够实现人机对战并且具有一定的人工智能水平。（2）玩家可以根据自己的需要选择先后手、游戏等级。（3）能够为玩家提供上一步的“悔棋”功能。（4）此游戏可以保存和装入游戏进度。（5）为玩家提供游戏介绍和规则说明。（6）软件界面美观、交互性好、操作方便。本游戏软件一共分为三大模块：游戏选项、游戏设置和帮助。每个模块的功能都是按照在调研中搜集的资料进行编排制作的。在三大模块的基础上每一大模块又分为几个小模块：游戏设置包括：开始游戏时
30、先后手设置、游戏等级设置；游戏选项包括：新游戏、继续游戏、悔棋、退出游戏；帮助包括：游戏的规则和关于。3.3性能需求3.3.1实用性有用性是衡量使用一种产品来执行指定任务的难易程度的尺度，它与实用性和受欢迎度等相关概念是有差异的。决定产品可接受性的核心属性是其有用性，它用于评价实际使用产品时，是否能达到设计人员期望产品实现的目标。有用性的概念可以进一步划分为实用性和可用性。虽然这些术语间有联系，但它们却不能相互替代。软件具有的人工智能算法原理要简单并且运行要快速。游戏是需要快速反应的，手机处理器的频率直接要求需要使用简单实用的智能算法。五子棋游戏本身就非常知名，玩过的人都印象深刻，本游戏操作简
31、单，操作方便，通过触摸屏进行游戏，并且下载安装都极其方便，市场前进广阔，在有用性上可以满足要求。3.3.2可靠性用软件系统规模越做越大越复杂，其可靠性越来越难保证。应用本身对系统运行的可靠性要求越来越高，在一些关键的应用领域，如航空、航天等，其可靠性要求尤为重要，在银行等服务性行业，其软件系统的可靠性也直接关系到自身的声誉和生存发展竞争能力。特别是软件可靠性比硬9件可靠性更难保证，会严重影响整个系统的可靠性。在许多项目开发过程中，对可靠性没有提出明确的要求，开发商(部门)也不在可靠性方面花更多的精力，往往只注重速度、结果的正确性和用户界面的友好性等，而忽略了可靠性。在投入使用后才发现大量可靠性
32、问题，增加了维护困难和工作量，严重时只有束之高阁，无法投入实际使用。本游戏的每个功能模块都做了多方面的考虑，为了能让程序在各种情况运行起来，专门调整了代码结构，适应不同的环境。软件的可靠性上面是可行的。3.3.3界面和操作软件的界面简洁明了，操作简单容易。受手机屏幕大小和显示的影响，设计的软件界面必须是简洁的。要求操作简便，层次分明，人机对战，都能在很好的表现下棋的效果，通过简单的触摸屏内幕，达到游戏目的。对于仅可键盘输入的用户，游戏需要设计得容易操作。3.3.4容错性所谓容错是指在故障存在的情况下计算机系统不失效，仍然能够正常工作的特性。容错即是FaultTolerance，确切地说是容故障
33、（Fault），而并非容错误（Error）。例如在双机容错系统中，一台机器出现问题时，另一台机器可以取而代之，从而保证系统的正常运行。在早期计算机硬件不是特别可靠的情况下，这种情形比较常见。现在的硬件虽然较之从前稳定可靠得多，但是对于那些不允许出错的系统,硬件容错仍然是十分重要的途径。在本游戏编码过程中，尽量做到异常的处理，不给系统留下任何出错的机会，保证系统的正常运行。104总体设计4.1软件总体结构设计游戏总体功能结构图如图4-1所示。各模块的详细功能如下：先后手设置：对人机双方下棋先后顺序的选择。游戏等级设置：对手机中安排的难易等级进行选择。新游戏：进行新一局的五子棋游戏。继续游戏：读取
34、玩家上一盘所保存的游戏并继续进行游戏。悔棋：人机对弈时人方对自己的上一步棋重新思考。退出游戏：退出此手机五子棋游戏软件。游戏规则：五子棋游戏的规则介绍和控制键说明。关于：此五子棋游戏软件的介绍。图4-1系统功能模块图五子棋游戏的业务流程描述如下：（1）玩家可以不通过设置而默认的系统设置直接进入游戏。（2）玩家也可以根据自己需要进行游戏设置，设置分为：设置先后手、设置游戏的等级，玩家进行游戏设置后再进入游戏。业务流程图符号说明如图4-2所示：11图4-2业务流程图符号说明五子棋游戏的电脑落子流程如图4-3所示。图4-3五子棋游戏的电脑落子流程图4.2用户界面设计用户界面在整个系统的使用中起着很大
35、的作用，它将直接影响到用户对软件的评价。界面是人机交互的平台，所以在设计时尽量往用户方考虑。12提供操作简便和友好界面。拥有较为良好的交互功能。12以下是系统使用的界面，感觉还有很多地方需要改进和完善。但是总体来说已经能够基本满足系统的需要。拥有较为良好的交互功能。界面初始设计如下图4-4：图4-4界面初始设计135系统设计与实现5.1AI设计人工智能(ArtificialIntelligence)，英文缩写为AI。它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。13人工智能是计算机科学的一个分支，它企图了解智能的实质，并生产出一种新的能以人类智能相似
36、的方式作出反应的智能机器，该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。在该部分我们尽量去模拟人类在下棋中思考的方式，找出一种合乎逻辑的规则。根据我们平常下棋的经验，当放入一个棋子时总是尽量的往利于己方的位置也既是“攻”；同时要提防对方使其不能得逞也既是“防”；我们可以用计算机模拟这个过程。假设我们在棋盘中放入一个己方棋子，然后考虑对方最可能下的棋子位置，也就是最有利于对方的点。（我们假设只进行两次的探索），再逐个的比较每个可下棋的点，最后得出最有利于我方的点。这就是本个系统中所采用的一个思路。对于人说用手工去比较计算是不现实的。当考虑的深度加深的话甚至无法在有效的时间
37、内实现的。我们正是利用计算机快速的计算机能力进行这样的笨重检索，就能够在很短的时间内计算完。下面对AI算法中所涉及的几个重要概念作下介绍。5.1.1极大极小树目前绝大部分的博弈类游戏中的人工算法都采用这种方法。假设己方为MAX点，对方则为MIN点。如果当层的节点为奇数时那么就为MAX层，同样为偶数时就为MIN层。当在MAX层时，该层的值就应该为下一个MIN层中的最大一个的值。当在MIN层是，该层的值就应该为它子层MAX的最小的一个。通俗的说就是当轮到我方时，我们就应该选择一个最有利于我们的点，预测对方可能下的最有利他方的点（相对我方来说就是最坏的点）。这样反复计算下去就能够得到根节点的最大值，
38、这个点也就是我们最佳下棋点。在计算这个点时可以很明显的看出这是一个不断递归的过程，到达叶子节点时根据相关的计算规则算出该值然后向上一层不断的返回。如图5-1所示矩形代表极大层，椭圆代表极小层。601560105601040205图5-1树图145.1.2深度优先搜索（DFS）在图论中有两个很重要的遍历的方法，一个是深度优先搜索（DFS）,另外一个是广度优先搜索(BFS).这两个方法的主要区别在于下一个节点的选择。DFS首先选择它的连接节点，若它的下个节点已经全部被遍历过或者不存在的话。则向上返回到上一个节点，在遍其他的未被访问过的点。很容易想到这要用到堆栈结构，使用一个递归来实现。而BFS则是
39、逐个的遍历它的联接接点，将已经访问过的点放入队列中。然后再依次取出继续这个过程。ABEFCD图5-2遍历图DFS遍历过程如下：首先从A点出发访问它的领接点B，因为B的领接点C,F均未被访问过，所以B点选择C（当然也可以选择F点）作为下一个要访问的点，C点的领接点是D,F选择下个节点D，而D的邻接点只有一个E且未被访问过，就将E作为了它下个节点。这时因为E已经没有可访问的邻点，所以向上一层返回到D，发现D也已经没有可访问的点了，继续向上层返回到C，由于C的邻节点F未被访问过，那么就访问F。所以整个过程的遍历结果为：A-BCDEF。BFS的的遍历过程为：ABECFD。145.1.3剪枝方法在上面中
40、提到当预测的深度达到3的时候，最坏情况下225*225*225=11390625个，这在目前的一些常规平均的机器性能下也需要40多秒的时间，这是不能够容忍的。那么是否有很好的改进技术，去除哪些不必要的节点，并且在剪去了这些点后不影响结果呢？答案是肯定的，这种方法就是Alpha-Beta剪枝。下面通过图5-3来说明，矩形代表极大层，椭圆代表极小层。15A:40B:40C:=25I:25?图5-3AlphaBeta剪枝从上图可以看出，由于C节点的值肯定不大于30而B节点的值为40大于C节点，那么目前为止可以很肯定的说A节点值一定不小于40。所以C点的其他子节点无须去访问也不会对结果的值有影响。这个
41、就是剪枝。在I节点的值确定为25后，我们就可以断定H节点一定不小于25,而F点的值为20，那么就可以很确定的说D的值为20。这个就是剪枝。下面给出完整的定义：剪枝:若任一极小值层节点的值小于或等于它任一先辈极大值层节点的值,即(先辈层)(后继层),则可终止该最小值层中这个Min节点的搜索过程。这个Min节点最终的倒推值就确定为值。剪枝:若任一极小值层节点的值大于或等于它任一先辈极大值层节点的值,即(后继层)(先辈层),则可终止该最大值层中这个Max节点的搜索过程。这个Max节点最终的倒推值就确定为值。5.1.4静态估值函数当极大极小树到达叶子节点时，需要估算一下当前盘面的值。这个就根据某个计算
42、规则计算也即是估值函数。因为这个值是已经确定的所以称为静态。当只有一个点时，并且相邻的无对方的棋子或者不是边界等“阻碍物”就给他50，否则给予10。当两个点时，并且相邻的无对方的棋子或者不是边界等“阻碍物”给予1000，若存在一方有“阻碍物”则给以100，否则给予10。16当是活三的时候给予3600，当存在一边被堵时，就给予500。否则给予10。当是活四的时候给以500000，当一边被堵时，给予50000。否则给予10当是五连子的时候就给予最高分1000000。最后判断是否是己方的，若不是则给予负号。静态估值函数会很严重的影响到算法的智能，所以可根据在下棋的过程中不断的做出调整，使其更加的合理
43、。根据一些测试，这组静态估值函数能够很好的反映棋盘重要性指标。5.2主要游戏模块5.2.1游戏主屏幕进入五子棋游戏前是选择主屏幕。效果图如图5-4所示。图5-4游戏主屏幕5.2.2游戏设置在开始游戏前可以为游戏设置等级和先后手。效果图如图5-5所示。游戏等级设置：可以为电脑AI设置难度，让不同水平的用户都可以上手，不至于难度太高吓走一些用户。可选择以攻为主或者是是以守为主。先后手设置：设置自己是先手还是后手，为用户提供多样的游戏方式。17图5-5游戏设置游戏设置相关事件代码：publicclassSettingActivityextendsActivityListViewlist;String
44、levels=以攻为主,以守为主;StringfirstHand=人类先手,电脑先手;18Preferencesp;intlevel;OverrideprotectedvoidonCreate(BundlesavedInstanceState)/TODOAuto-generatedmethodstubsuper.onCreate(savedInstanceState);setContentView(R.layout.setting);p=Preferences.getInstance(getApplicationContext();list=(ListView)findViewById(R.id.settinglist);ArrayAdapteradapter=newArrayAdapter(this,android.R.layout.simple_list_item_1,newString先后手设置,游戏等级设置);list.setAdapter(adapter);list.setOnItemClickListener
陕公网安备 61072602000132号 违法和不良信息举报：0916-4228922