人工智能连连看报告21.docx

《人工智能连连看报告21.docx》由会员分享，可在线阅读，更多相关《人工智能连连看报告21.docx（23页珍藏版）》请在三一办公上搜索。

1、江南大学人工智能大作业报告 人工智能期末考核大作业 报告主题 搜索算法在智能游戏开发领域的运用 班级 计科0901 姓名 汪胜圣 总学号 0304090112 得分 目 录第1章 人工智能31.1 什么是人工智能33.1 为什么要研究人工智能43.2 人工智能研究方法53.3 人工智能在游戏领域的一些应用6第2章 项目概要62.1 项目背景62.2 任务概述8第3章 分析游戏93.1 动手前的准备93.2 实现游戏的算法103.3 游戏设计核心问题14第4章 设计游戏154.1 用布局和按钮来实现算法的界面154.2 设计用户界面15第5章 核心代码165.1 图片的随机生成所用到的方法165

2、.2 得分设置 （对数组中两个元素是否可以消除的判断）175.3 过关设置19第6章 参考文献20第7章 人工智能设计小结20江南大学人工智能大作业报告第1章 人工智能1.1 什么是人工智能人工智能(Artificial Intelligence) ，英文缩写为AI。它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。 人工智能是计算机科学的一个分支，它企图了解智能的实质，并生产出一种新的能以人类智能相似的方式做出反应的智能机器，该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。第2章 “人工智能”一词最初是在1956 年Dartmou

3、th学会上提出的。从那以后，研究者们发展了众多理论和原理，人工智能的概念也随之扩展。人工智能是一门极富挑战性的科学，从事这项工作的人必须懂得计算机知识，心理学和哲学。人工智能是包括十分广泛的科学，它由不同的领域组成，如机器学习，计算机视觉等等，第3章 总的说来，人工智能研究的一个主要目标是使机器能够胜任一些通常需要人类智能才能完成的复杂工作。但不同的时代、不同的人对这种“复杂工作”的理解是不同的。例如繁重的科学和工程计算本来是要人脑来承担的，现在计算机不但能完成这种计算，而且能够比人脑做得更快、更准确，因之当代人已不再把这种计算看作是“需要人类智能才能完成的复杂任务”，可见复杂工作的定义是随着

4、时代的发 展和技术的进步而变化的，人工智能这门科学的具体目标也自然随着时代的变化而发展。它一方面不断获得新的进展，一方面又转向更有意义、更加困难的目标。目前能够用来研究人工智能的主要物质手段以及能够实现人工智能技术的机器就是计算机，人工智能的发展历史是和计算机科学技术的发展史联系在一起的。除了计算机科学以外，人工智能还涉及信息论、控制论、自动化、仿生学、生物学、心理学、数理逻辑、语言学、医学和哲学等多门学科。人工智能学科研究的主要内容包括：知识表示、自动推理和智能搜索、机器学习和知识获取、知识处理系统、自然语言理解、计算机视觉、智能机器人、自动程序设计等方面。在智能搜索领域的运用是人工智能的一

5、大运用领域。3.1 为什么要研究人工智能人工智能是研究使计算机来模拟人的某些思维过程和智能行为（如学习、推理、思考、规划等）的学科，主要包括计算机实现智能的原理、制造类似于人脑智能的计算机，使计算机能实现更高层次的应用。人工智能将涉及到计算机科学、心理学、哲学和语言学等学科。可以说几乎是自然科学和社会科学的所有学科，其范围已远远超出了计算机科学的范畴，人工智能与思维科学的关系是实践和理论的关系，人工智能是处于思维科学的技术应用层次，是它的一个应用分支。从思维观点看，人工智能不仅限于逻辑思维，要考虑形象思维、灵感思维才能促进人工智能的突破性的发展，数学常被认为是多种学科的基础科学，数学也进入语言

6、、思维领域，人工智能学科也必须借用数学工具，数学不仅在标准逻辑、模糊数学等范围发挥作用，数学进入人工智能学科，它们将互相促进而更快地发展。 从实用观点来看，人工智能是一门知识工程学：以知识为对象，研究知识的获取、知识的表示方法和知识的使用。3.2 人工智能研究方法人工智能在计算机上实现时有2种不同的方式。一种是采用传统的编程技术，使系统呈现智能的效果，而不考虑所用方法是否与人或动物机体所用的方法相同。这种方法叫工程学方法（Engineering approach），它已在一些领域内作出了成果，如文字识别、电脑下棋等。另一种是模拟法（Modeling approach），它不仅要看效果，还要求实

7、现方法也和人类或生物机体所用的方法相同或相类似。本书介绍的遗传算法（Generic Algorithm，简称GA）和人工神经网络（Artificial Neural Network，简称ANN）均属后一类型。遗传算法模拟人类或生物的遗传-进化机制，人工神经网络则是模拟人类或动物大脑中神经细胞的活动方式。为了得到相同智能效果，两种方式通常都可使用。采用前一种方法，需要人工详细规定程序逻辑，如果游戏简单，还是方便的。如果游戏复杂，角色数量和活动空间增加，相应的逻辑就会很复杂（按指数式增长），人工编程就非常繁琐，容易出错。而一旦出错，就必须修改原程序，重新编译、调试，最后为用户提供一个新的版本或提供

8、一个新补丁，非常麻烦。采用后一种方法时，编程者要为每一角色设计一个智能系统（一个模块）来进行控制，这个智能系统（模块）开始什么也不懂，就像初生婴儿那样，但它能够学习，能渐渐地适应环境，应付各种复杂情况。这种系统开始也常犯错误，但它能吸取教训，下一次运行时就可能改正，至少不会永远错下去，用不到发布新版本或打补丁。利用这种方法来实现人工智能，要求编程者具有生物学的思考方法，入门难度大一点。但一旦入了门，就可得到广泛应用。由于这种方法编程时无须对角色的活动规律做详细规定，应用于复杂问题，通常会比前一种方法更省力。3.3 人工智能在游戏领域的一些应用人工智能在游戏中的目标主要有五个：一是为玩家提供适合

9、的挑战；二是使玩家处于亢奋状态；三是提供不可预知性结果；四是帮助完成游戏的故事情节；五是创造一个生动的世界。这个生动的世界可以是类似现实生活中的世界，也可以是与现实世界完全不同的世界。但不管何种世界都要求有一整套能够自圆其说的游戏规则。 在游戏制作过程中，实现人工智能的关键主要有：虚拟现实与拟人化、动画效果与机器角色场景感知、机器角色的机器学习和进化、玩家与机器角色之间的平衡性、人工愚蠢技术、确定性人工智能技术与非确定性人工智能技术的互补。人工智能在游戏中应用的技术非常之多，如：有限状态自动机(Finite State Machines)、模糊逻辑(Fuzzy Logic)、产生式系统（pro

10、duction system）、脚本设计(Scripting)、基于规则的人工智能和系统(Rules-based AI and Systems)、贝叶斯推论(Bayesian Inference)和非确定性贝叶斯网络(Bayesian Networks for Uncertainty Decisions)、人工生命(Artificial life)、决策树（Decision Tree）、专家系统（Expert system）、神经网络(Neural Networks)、遗传算法(Genetic Algorithms)等。下面MFC连连看就是运用人工智能中的智能深度搜索算法制作的，是人工智能在游

11、戏开发领域的小应用。锻炼我的编程能力，更深入了我对人工智能这门课的了解与领悟。第2章 项目概要2.1 项目背景2.1.1 连连看游戏产业作为现代电脑电子技术的产物，正在以其独特的魅力在全世界的娱乐领域占据主流位置，我们在承认广大娱乐网民的选择空间狭小的同时，也必须明确的一点就是游戏本身所具有的强大的吸引力。游戏的吸引力主要在于，它在让玩家打发时间的同时，可以让人实现在显示生活中不能实现的理想，得到在现实中不能得到的东西。而且游戏产业促动高科技技术不断升级，作为经济增长的一大支撑点，已经成为经济腾飞的“第四产业”。现在小游戏、网页游戏越来越受网民欢迎，除了玩的方法简单外（不像其他游戏还需要注册下

12、载繁琐过程），很多游戏不乏经典。连连看游戏就是典型了！游戏“连连看”顾名思义就是找出相关联的东西，这个连连看在网上基本是用在小游戏中，就是找出相同的两样东西，在一定的规则之内可以作为相关联处理。“连连看”的发展经历了从桌面游戏、在线游戏、社交游戏三个过程。 游戏“连连看”是源自台湾的桌面小游戏，自从流入大陆以来风靡一时，也吸引众多程序员开发出多种版本的“连连看”。这其中，顾方编写的“阿达连连看”以其精良的制作广受好评，这也成为顾方“阿达系列软件”的核心产品。并于2004年，取得了国家版权局的计算机软件著作权登记证书。 随着Flash应用的流行，网上出现了多种在线Flash版本“连连看”。如“水

13、晶连连看”、“果蔬连连看”等，流行的“水晶连连看”以华丽界面吸引了一大批的女性玩家。 2008年，随着社交网络的普及和开放平台的兴起，“连连看”被引入了社交网络。“连连看”与个人空间相结合，被快速的传播，成为一款热门的社交游戏，其中以开发者Jonevey在Manyou开放平台上推出的“宠物连连看”最为流行。2.1.2 MFCMFC(Microsoft Foundation Classes)，是一个微软公司提供的类库（class libraries），以C+类的形式封装了Windows的API，并且包含一个应用程序框架，以减少应用程序开发人员的工作量。其中包含的类包含大量Windows句柄封装类

14、和很多Windows的内建控件和组件的封装类。2.1.3 深度优先搜索深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。2.2 任务概述2.2.1 任务概述1. 实现单机版连连看。2. 开始游戏后，随机生成图片位置。3.

15、 实现深度搜索算法。4. 使用布局实现用户界面 。5. 使用数组实现算法的核心 。2.2.2 实现目标l 游戏概况l 方案论证l 界面设计l 图片选取及生成l 算法路径实现l 游戏运行第3章 分析游戏3.1 动手前的准备3.1.1 看看别人现成的游戏 在盖房子之前，我们都会先打好地基，然后搭起框架，最后再就是一点一点添砖加瓦，做软件也是一样的道理，都是从大体的框加向细节部分设计实现，现在，我们开始吧。其实不管是做软件也好，做游戏也好，只要是写程序，在动手之前是一定会存在需求和分析的，如果不经过一定的分析就开始动手写程序，那么，这个程序一定会很难写下去的，最后的结果可能会导致放弃。那么，在我们动

16、手之前，让我们先简单的分析一下吧。由于“连连看”并不是一个我们凭空开发的游戏，并且网上也已经有很多别人已经开发好的版本，因此，对于我们来说，我们已经拥有了一个很好的原型（比如说 QQ 游戏中的“连连看”），分析起来也应该是轻松得多。由于 QQ 中的“连连看”是网络版，为了开发上的简便，我们先放弃网络功能，做一个简单的单机版就行了。现在，让我们现在来看一看 QQ 中的连连看吧。“连连看”的游戏规则其实并不复杂，首先，游戏开始的时候，地图上会有由数张不同的图片随机分散在地图上（并且每张图片会出现偶数次，通常是 4 次），只需要在地图上找出两张相同的图片（点），并且这两个点之前可以用不超过 3 条的

17、直线连接起来就可以消除这两点，如此下去，直到地图上的点全部消除完就算游戏结束，怎么样，规则很简单吧？：）我们的开发就完全按照些规则来吧。 3.1.2 分析游戏规则找出算法 通过上面的分析，我们已经知道了游戏规则，通过对上图的观察，我们发现，可以将游戏中的地图看作是一个二维数组，运用了深度搜索。其中的所有图片（以下称“点”）可以看作是数组中的一个具体的元素。那么，游戏中相同的图片可以看作是数组中不同位置两个值相同的元素。至于直线，让我们给组数中的每一个元素赋一个特殊的值如 0 ，以表示地图上空白的位置。并且同时规定：当连续的具有该特殊值的点的横向索引或纵向索引相同时，可以认为这是一条直线，比如下

18、图： 当数组中两点的值相同并且两点间只需要不超过 3 根直线能连接起来的时候，就让这两点的值变为 0 ，如果数组中全是 0 值的点，就认为游戏已经结束。3.2 实现游戏的算法 3.2.1 将游戏地图转换为数组来描述 算法总是很枯燥的，没有直接设计界面来得舒服，然而，算法却是整个程序的核心，所以，仅管枯燥，我们还是得耐心地完成这一步。 在进行程序算法的设计时，我们首先要尽可能抛开一些无关紧要的部分，这样可以使算法看起来直接明了，但同时也要考虑弹性，以便将来扩充。 在前面已经说过了，整个游戏的核心算法也就是以二维数组为主体的算法，那么，定义一个二维数组是必不可少的了。 二维数组究竟应该有多大呢？

19、10X10 是不是小了， 20*20 呢，大了？究竟多大比较合适？为了考虑到程序以后改动的需要，我们还是定义成变量吧，这样以后要改动的时候，只需要改动一下变量的值就行了，因此，我们现在为程序增加一个类，使之专门用来保存与程序有关的一些数据。3.2.2 初始化游戏地图 在地图初始化的时候，我们需要用一些“随机”的数字来填充这张地图，之所有将“随机”用引号括起来，是因为这些数字并不是真正意义上的随机：首先，数组中具有相同值的元素只能出现 4 次（具有 0 值的元素除外），其次，这些数字是被散乱的分布在数组中的。 要使元素出现 4 次，那么数组中所有不重复的元素个数最大为数组的大小 /4 ，为了简单

20、起先，我们使这些元素的值用 1 、 2 、 3 进行编号。 要想将这些分配好的元素再分配到二维数组中，我们需要一个一维数组来辅助完成这项工作。 首先，我们按照二维数组的大小来建立一个大小相同的一维数组，并且，我们规定数组中出现的不重复的元素的个数（元素个数的多少代表了地图的填充率，填充率越高，表示游戏难度越高），同时，我们也要保证数组的长度能被 4 整除（目前是这样，其实不是必需的），因为相同的元素会出现 4 次。因此，我们定义一个变量，用来表示地图上可能出现元素种类的最大个数，同时也定义一个变量，表示目前地图上出现的元素的个数。 3.2.3 对数组中两个元素是否可以消除的判断 地图的初始化已

21、经完成了，现在的问题是，我们怎么样才能知道数组中的两个元素是否可以消除呢？ 根据游戏规则，如果两个点之间可以用不超过 3 条直线连接起来，这两点就可以消除，现在我们来分析一下所有可能的情况： 两点之间只需要一条直线连接： 如果两点间只需要一条直线能够连接起来，则 A 、 B 两点的横坐标或纵坐标必定相同，有了这个条件，我们判断 A 、 B 两点是否只需要一条直接连接就简单了许多。图略。 两点之间需要两条直线连接： 如上图， A 、 B 两点如果需要两条直线连接起来，有可能有两种方式，于是，我们可以巧妙的构建一个 C 点和一个 D 点，并且规定 C 点的横坐标为 A 点的横坐标， C 点的纵坐标

22、为 B 点的纵坐标， D 点的横坐标为 B 点的横坐标， D 点的纵坐标为 A 点的纵坐标（这一点很重要，因为 C 、 D 决定了 AC 、 BC 、 AD 、 BD 的连线方式），如下图： 如果此时 C 点（或 D 点）能同时满足 AC （ AD ）、 BC （ BD ）只需要一条直线相连，就表示 A 、 B 之前能够使用两条直线连接起来，并且 C 点（ D 点）为拐点（以后会用上的） 两点之间需要三条直线连接： 这种方式是最复杂的了，我们还是先分析一下出现三条直线的所有可能性吧。 ( 图 A) ( 图 B ：这种方式比较容易忽略掉 ) 以上图说明了两点间三条直线的所有可能性，和二条直线的情

23、况相比，拐点是两个，麻烦了一点，但也不难处理。 下面我们来分析一下该怎么处理二个拐点的情况（三条直线）。由上面的图可以看出， A 、 B 如果要通过三条直线相连，则必须有 C 、 D 两个拐点，如果能确定下 C 、 D ，问题就好解决多了。 怎么样来确定 C 、 D 两点呢？我们以图 A 中的左图为例，在此之前，我们规定 C 点与 A 点在同一竖线上， D 点与 A 点在同一直线上。同时，从图中我们也可以看出， A 、 B 两点间如果只能通过三条直线连接起来，则必定有一条直线处于 A 、 B 的横向夹线纵向夹线中（如画圈的线）。 我们假设相等的线为在 A 、 B 两点的横坐标相等、纵坐标为 0

24、Setting.ROW 构成的区域上 ( 如图 ) 。 我们先扫描出所有的线，并且我们发现，如果在 A 、 B 构成的区域中存在两个点能构成直线，那么，这条直线就 有可能 是我们需要的直线，我们称此线为符合线，如果符合线的两端（ C 、 D 两点）与 A 、 B 两点分别能 AC 、 CD 、 DB 能构成直线的原则，则 AB 间一定可以通过三条直线连接起来。（这个可能我描述得不太清楚，但相信你应该不难明白的） 。消除该两个元素消除该两个元素时，只需要将两个元素的值置为 0 即可。 3.3 游戏设计核心问题23第4章 设计游戏4.1 用布局和按钮来实现算法的界面 上面已经说完了算法，相信大家也

25、迫不及待的想进入界面的设计了吧，好了，多的不说，我们开始吧。 既然我们的算法是基于二维数组的，那么我们也应该在界面使用一个能反映二维数组的控件。这里有两种方式，一种使用表格来实现，第二种是使用布局来实现。 相对而言，用表格来实现二维数组要简单一些， 4.2 原型设计展示 第5章 核心代码5.1 图片的随机生成所用到的方法 说明：通过数组从图片库随即获取规定个数得到图片，随机分布在画布上。图片个数一定是偶数个。 private void IniteBmp(int maxnum) g_g = this.CreateGraphics(); for (int i = 0; i MAPWIDTH; i+

26、) for (int j = 0; j MAPHEIGHT; j+) gmapi, j = 0; IniteRandomMap(ref gmap, maxnum); AI = new Kernal(ref gmap); for (int i = 0; i maxnum; i+) ResourceManager rm = new ResourceManager(LLK.data, Assembly.GetExecutingAssembly(); imgi= (Image)rm.GetObject(i.ToString()+.bmp); /imgi = (Image)Bitmap.FromFile

27、(Images+(i+1).ToString()+.bmp); for (int i = 0; i 6; i+) /bombimgi = (Image)Bitmap.FromFile(ImagesB+(i+1).ToString()+.bmp); 5.2 得分设置 （对数组中两个元素是否可以消除的判断） 说明：1：两个目标是相同的 2：两个目标之间连接线的折点不超过两个。（连接线由x轴和y轴的平行线组成） 那么分析一下连接的情况可以看到，一般分三种情况1：直线相连 2：一个折点 3：两个折点：可以发现，如果有折点，每个折点必定有且至少有一个坐标（x或者y）是和其中一个目标点是相同的，也就是说，

28、折点必定在两个目标点所在的x方向或y方向的直线上。所以设计思路就是：假设目标点 p1 , p2 ,如果有两个折点分别为z1 , z2 那么，所要进行的是 1：如果验证p1 , p2 直线连线，则连接成立 2：搜索以p1,p2的x,y方向四条直线（可能某两条直线会重合）上的有限点，每次取两点作为z1,z2 ,验证p1到z1/z1到z2/z2到p2 是否都能直线相连 ，是则连接成立。BOOL C_LLK_Dlg:IsLink(int x1, int y1, int x2, int y2)/X直连方式if(x1=x2)if(X1_Link_X2(x1,y1,y2)return TRUE;/Y直连方式

29、else if(y1=y2)if(Y1_Link_Y2(x1,x2,y1)return TRUE;/一个转弯直角的联通方式if(OneCornerLink(x1,y1,x2,y2)return TRUE;/两个转弯直角的联通方式else if(TwoCornerLink(x1,y1,x2,y2)return TRUE;return FALSE;5.3 过关设置 把界面上全部图片都消去即为通过此关，进入下一关，种类数加1.实现代码：private bool CheckWin(ref int, map) bool Win = true; for (int i = 0; i MAPWIDTH; i+

30、) for (int j = 0; j MAPHEIGHT; j+) if (mapi, j != 0) Win = false; return Win; /判断过关 if (CheckWin(ref gmap) starttimer = false; MessageBox.Show(恭喜过关!); bStart = false; picnum+;/种类加1 第6章 参考文献1、 VB连连看游戏的设计与实现论文论文-李蒙2、 连连看原理3、 游戏中的人工智能4、 连连看毕业设计文档5、 人工智能教程-王士同第7章 人工智能设计小结代码内容非常长，工作量也是很大的，且几乎全部是在代码中编写，没有

31、添加什么界面上的控件操作。另外这个游戏没有用到数据库，所使用的功能也不是很多，但是由于考虑到要按固有的游戏规则来编写，因此要写较多时间考虑游戏怎么玩，怎么通过代码判断用户每个鼠标点击的坐标以及当前坐标位置代表的图片内容等各方面的判断考虑得就较多了。 就目前来说，人工智能在游戏上的应用技术上的困难主要来源于两个方面：一是游戏中的非确定状态实在太多，人的情感是极其复杂的，并非是简单的数理关系就能表现出来的；二是现有的硬件和计算机网络水平还不是很高。目前要解决这些困难，在技术上来说还是不成熟的。对于数量极多的非确定状态来说，尽可能地提高硬件和计算机网络的速度，可能是一个解决方法。但是要提高硬件和计算机网络的速度也并非易事，而更有效的办法是提高软件的执行速度。比如使用更有效的算法或神经网络等新技术。随着游戏制作技术和计算机技术日趋发达，这些问题终将被解决，我们未来的游戏也将会更加完善。我曾经见过很多这样的玄幻小说，就是带着个头盔便可以进入一个虚拟的游戏世界，人在里面的感觉和真实世界一样，例如游戏里挨打身体真的会疼。也许，在不久的将来，游戏中的一串代码和人的感觉会具有相似的效果。