易码技术论坛

 找回密码
 加入易码
搜索
查看: 750962|回复: 11

[教程] [分享]游戏中的人工智能实现

[复制链接]
发表于 2005-8-19 12:36:00 | 显示全部楼层
发现程序段里面常用的数组标记[i]会和UBB标签产生冲突……
比如
Array[ i]=10 //后面的字体都会变成斜体...
解决的办法就是在括号之间加一个空格。这样就不会出问题了。

这是一篇好文啊^_^,对于遗传算法的描述比我以前看过的几种都清晰,嘿嘿。收下仔细看看~
发表于 2006-5-27 20:27:00 | 显示全部楼层
仔细看了,虽然我不是很懂,仍然要说是一篇名副其实的精华帖,佩服!
发表于 2006-6-4 17:48:00 | 显示全部楼层
不是很懂……

以后再看呵呵
发表于 2006-6-5 00:26:00 | 显示全部楼层
要看的话过来我给你借本书看吧,相当棒的一本讲一串算法的书

另外这里对于“语义网络”的概念介绍和我接触到的有些差异,google下可以得到:

一个 语义网络(Semantic Network)常常被用作知识表示的一种形式。它其实是一个有向图,这个图的顶点代表概念,而边则用于表示这些概念之间的语义关系。

而这里引用的明显是一个神经网络的模型,包括刺激啊,门限啊,激活函数等等都是神经网络中的专业术语,下面那段解释有点混乱,但是似乎和神经网络的应用关系不大……也许是领域不同导致的,只希望不要误导人为好。


发表于 2006-6-5 16:46:00 | 显示全部楼层
一年前的帖子……
发表于 2006-6-7 15:18:00 | 显示全部楼层
那请问象棋,围棋的人工智能如何实现呢?

我的QQ:234114233
发表于 2006-6-22 21:37:00 | 显示全部楼层
不怎麽懂
发表于 2006-6-30 10:40:00 | 显示全部楼层
吃葡萄不吐葡萄皮
发表于 2006-7-18 18:00:00 | 显示全部楼层
有点晕
发表于 2006-7-21 22:56:00 | 显示全部楼层
相当的精彩啊!!!!


[em01][em01]
发表于 2006-7-22 23:47:00 | 显示全部楼层
以下是引用gcwy在2006-6-7 15:18:00的发言:[BR]那请问象棋,围棋的人工智能如何实现呢?我的QQ:234114233
 楼主| 发表于 2005-8-18 18:45:59 | 显示全部楼层 |阅读模式

  1. 游戏中的人工智能实现
  2.                                                             周凤英 羽天
  3. 一、人工智能慨述
  4.   提到人工智能,就不能不说说我非常景仰的人工智能之父图灵。他相信如果模拟人类大脑的思维就可以做出一台可以思考的机器,他于1950写文章提出了著名的“图灵测试”,测试是让人类考官通过键盘向一个人和一个机器发问,这个考官不知道他现在问的是人还是机器。如果在经过一定时间的提问以后,这位人类考官不能确定谁是人谁是机器,那这个机器就有智力了。这个测试在我们想起来十分简单,可是伟大的思想就源于这种简单的事物之中。
  5.   然而,图灵的测试也只说明了事物具有了智能的表象,何可谓智能的本质呢,可能当今世上谁也说不清楚。浩浩星空茫茫幻化演变,何可谓智,何可谓能,本就是空。只是以我们人类的认识和想象,无中生有罢了。所以我们谈的智能只能局限于我们人类的认知和想象,抛开了主观,也就只剩客观存在而已。
  6.   也正因为我上面的观点,在此我仅讲一些简单的实用的模型,使我们的程序具有一定的智能表象,但绝非智能的本质。希望大家能通过不断的实践进行学习,如果能对大家有些许帮助,就已心满意足。
  7.   在这里先说一句非常重要的话,如果你无法用语言描述一个事物,那么你就很难更深入的研究它。在我们计算机程序中,如何为事物建立模型是非常非常重要的,好的模型一旦建立,就已成功一半了。
  8.   在这里,我们逐步学习一些的算法模型,逐步建立更好的智能系统,希望大家能够喜欢。
  9. 二、状态空间法
  10.   将问题转换到对应状态空间,然后以状态空间的分析方法分析问题,是解决简单问题常用的有效方法。在一个大的游戏智能系统中,局部的智能表象模拟通常都是采用这种简单而行之有效的方法。
  11.   例1:4个人晚上过桥,一个手电筒,最多2人同过,单独过桥需要时间分别为10、5、2、1分钟,2人同过,按慢的人算时间,问最少多长时间?
  12.   首先,我们建立状态表示模型,状态转化模型,智能评估模型。
  13.   状态表示模型即能表示任一时刻(或时段)的状态(最好和实际状态是一一映射方式)。状态通常由一些状态参数或规则表示。比如模型R :
  14. Time:已用时间
  15. PersonState[4]:4个人的状态,0表示未过桥,1表示已过桥
  16. PersonWalkTime[4]:4个人的走路时间
  17. LightState:手电筒状态,0表示未过桥,1表示已过桥
  18.   状态转化模型:由一状态如何转化到下一状态。比如模型T:加最简单限制,if(LightState==0) 可两人过桥,否则只许一人过桥,并且所有状态发生相应变化。采用广度搜索方式进行所有可能的状态转化。
  19.   智能评估模型:和智能表象相关的评估模型,可嵌套组合子模型。
  20.   模型E:Time越小越优。
  21.   在这个系统建立好后,我们很容易通过广度搜索来找到最佳过河方案。若是把相应数据输入电脑,而电脑可以得出过桥方式,那么我们就可认为在一定程度这个系统具有了智能的表象(想象着我们不知道其内部如果工作)。当然模型定义的越好,系统的性能也越好。
  22.   因为上面算法使用的是广度搜索,为此我们可加入一些改进,使其速度更快。
  23.   改进1:我们尽量使走的慢的人过桥次数少一些,因此我们在每次返回一携带手电筒的人时,都选择走的快的,这样的话,我们的搜索就显的更智能了一些,速度也会快很多了。这种算法也就是A算法(即每次搜索,选取最可能达到最优的情况搜索,这里就需要一个局部评估模块)。
  24.   改进2:我们在开始阶段定义一个Time数值,若出现搜索过程中Time已超过此数值的,其下搜索不再进行。若出现搜索结果小于Time的,我们更新Time,并继续搜索。运用这种方法,我们将省去很多无用的搜索。这种方法称为alpha-beta剪枝技术。
  25. 三、棋类游戏算法
  26.   由于棋类游戏就是一种智力游戏,被研究的也较为深入,所以在这里我们举一个简单的黑白棋的人工智能的实现(因为黑白棋比较简单,对初学者来说很容易上手,所以比较适宜做教材)。在这里仍然采用了状态空间法。
  27.   例2:黑白棋的人工智能。黑白棋,又叫反棋、奥赛罗棋等,在西方很流行。黑白棋的棋盘是一个有8*8方格的棋盘。下棋时将棋下在空格中间,而不是像围棋一样下在交叉点上。开始时在棋盘正中有一白一黑四个棋子交叉放置,黑棋总是先下子。下子的方法是:把自己颜色的棋子放在棋盘的空格上,而当自己放下的棋子在横、竖、斜八个方向內有一个自己的棋子,则被夹在中间的全部会成为自己的棋子。并且,只有在可以翻转棋子的地方才可以下子。最后棋盘全部占满,子多者为胜。

  28. 图1
  29.   下面建立模型。
  30.   状态表示模型:模型R:board[8][8],=BLACK 表示黑棋,=WHITE 表示白棋,=EMPTY 表示空,turn=1 表示电脑走棋,turn=0 表示玩家走棋,mode=0 表示电脑走黑棋。
  31.   状态转化模型T:即先判断可以落棋的地方(是否为空,并且可以翻转棋子),然后落棋后改变board[m][n],turn。
  32.   智能评估模型E:吃子越多越好。
  33.   这样我们就建立了一个有低级智能表象的系统。为改进这个系统,我们来学习一些常用的技巧和算法。
  34.   战略点权值表:经过多次下棋,我们就可以知道棋盘的四个角是永远不能被吃掉的,所以这四个点是战略要地。同样,我们可以得出另一些重要的战略点。我们把这些点赋一个较大的权重,这样,我们可得到一个权重表(对应棋盘)。当然这个表可使用一些参数,并且可随过程改变而改变,越灵活的格式(如果你能收的住)将产生越好的智能表象。局势评估模块:对敌我双方的总体或局部兵力分布得出一个较为合理的分析结果,有了这个模块,才能更好的把握战局。
  35.   博弈树算法:也是一种状态搜索算法,但每个状态节点上都有一个评估。我们记敌我评估函数为 E(state)、M(state):

  36. 图2
  37. 如图在node0时候,电脑走棋有3种选择,在每种选择后,玩家又有三种选择。简单记评估值为 F(node)= M(node)-E(mode)。设  node20 评估值为F(node20) = M(node20) - E(node20)。node21 评估值为F(node21) = M(node21) - E(node21)。node22 评估值为F(node22) = M(node22) -E(node22) 。那么电脑在选择node10后,认为玩家会选择E(node)大而M(node)小的那个,所以电脑选择node10的所取得的优势应该是MIN( F(node2i) )。
  38.   所以遍历 node10,node11,node12,电脑就可以得到其能获得的最大优势是MAX(MIN(F(node2i)))。当然此博弈树可以加大树的深度,并且可用A算法和alpha-beta算法改进。具体算法不再详述,有兴趣者可以自己研究。
  39. 四、遗传算法
  40.   上述的几种算法虽然可以模拟出比较好的智能表象,但遗憾的是没有学习功能。而学习功能相对于智能生物是一个非常重要的功能。因此,我们简单介绍一下遗传算法,并举一个具体的例子。
  41.   生物的进化是一个奇妙的优化过程,它通过选择淘汰,突然变异,基因遗传等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全局优化算法。
  42.   遗传算法简介:对问题产生一个描述,对待解决问题进行编码。随机初始化群体X(0)=(x1, x2, … xn)。对当前群体X(t)中每个个体xi计算其适应度F(xi),适应度表示了该个体的性能好坏。应用选择算子产生优良种群goodX(t)。对goodX(t)应用遗传算子,产生新一代群体X(t+1)。t:=t+1;如果不满足终止条件继续(3)。选择算子:选择算子从群体中按某一概率成对选择个体,某个体xi被选择的概率Pi与其适应度值成正比。最通常的实现方法是轮盘赌模型。
  43.   例3:同样看黑白棋,我们采用自学习的方法来模拟智能的实现。棋盘状态采用 敌方=-1、空=0、我方=1。棋盘大小为64,我们对每一个格子用5*5的局部棋子来评价其战略重要性。采用线性方式Important[node]=∑Wi*state[ i]。这样我们就得到一个W[64][25]的表,对于每一种棋盘局势它总能判断出战略重要性最大的点(姑且不论对与否)。这种编码方式考虑了棋盘全局位置特性与局部局势特性,大家可自行改进。
  44.   选取种群大小为30,随机生成30个Wi[64][25]。
  45.   初始训练阶段:对每一个Wi[64][25],让其判断一些特定的战略点,判断力好的适应度大。后期训练阶段:和人对下,赢的多的适应度大。选择适应度大的10个为产生优良种群goodX(t)。对goodX(t)应用遗传算子,产生新一代群体X(t+1)(30个个体)。交叉遗传,可选取father[0-32][25]和mother的[32-64][25]产生新的个体。变异遗传,对father[64]25]中的数值产生一些随机变化从而生成新个体。t=t+1;如果不满足终止条件继续(3)。
  46.   采用这种方式,我们可以使程序自己学习,从而模拟智能。遗传算法的主体就是对问题编码,然后通过进化方式进化出优秀(相对于适应度)的种群,编码方式由具体问题决定,进化方式影响进化范围和速度。通过这种方式的学习,模型一般都能得到此编码方式下的最优编码,从而具有超越人为编码的性能。有兴趣的读者可以自行深入研究。
  47. 五、语意网络模型
  48.   学会了以上算法,但一般只能进行小规模模型的智能模拟。下面我再给出一个语意网络模型,用来构建整体的模型,结合上面的算法,就可以作出漂亮的中等规模的智能系统。
  49.   例4:一个小型的带时限的语意网络模型。网络由节点及连接节点的线组成,为简单化,每个节点性质相同。节点:受到刺激后可被激活,激活后又可刺激邻接节点。激活度由一个刺激度的函数决定。节点有门限,只有刺激度超过此门限时节点才可被激活或抑制。节点有一个受激缓存,用来记录短期内受到的刺激。有一个激活缓存,用于控制激活时间段。
  50.   门限:GateT(激活)、GateN(抑制)。
  51.   受激缓存:FMemory记录受激大小,衰减度,受激时刻。
  52.   激活缓存:BMemory记录激活度大小,衰减度,激活时刻。
  53.   激活函数:Active 计算激活度,可由节点自定义。
  54.   连接节点的线:传递刺激并可调节刺激大小。
  55.   Wi:权值,表示相应的支持度(>0,越大表示越支持)或抑制度(<0)。0表示无关。权值和门限决定了与操作和或操作的类型。
  56.   设A^B^C—>D ,对应网络模型如下:

  57. 图3
  58.   假设情景:A激活,1秒后B激活,2秒后C激活。A激活:D受激 Active(A) * W1 <Gate(D),记入受激缓存。1秒后B激活:D受激 Active(B) * W2 + 受激缓存中随时间衰减的刺激 <Gate(D),记入受激缓存。2秒后C激活: D受激 Active(C) * W3 + 受激缓存中随时间衰减的刺激 >Gate(D),被激活,记入激活缓存。这样就可以表示短时间内事物受A、B、C事件刺激,将产生D时间。
  59.   如果 A^B->D成立, A^B^C->D不成立,D->H,A^B^C^E->D成立。
  60. A发生,Active(A)*Wa<GateT(D),记入D的缓存。
  61. B发生,Active(B)*Wb + NowActive(FMemory)>GateT(D),D激活 Active(D)*Wd>GataT(H),H激活。记入D和H的缓存。
  62. C发生,Active(C)*Wc + NowActive(FMemory)<GateN(D),D被抑制。当D被抑制后,D根据激活缓存中的值对H发出负的刺激(作用相当于D不再刺激H)。若达到H的抑制门限,则H抑制,否则H不被抑制(即H仍可能处于激活状态)。
  63. E发生,D 被重新激活,又再次激活H。
  64. 对于缓存中的记录,当且仅当衰减达到一定程度时候,才会自动消失。
  65.   如果我们将语意网络建设好并将权值分配的非常漂亮,就可建立一套规则系统,而每个节点均可用任意程序事件代替,即可对每个节点使用前面所讲的算法来模拟局部智能表象,从来模拟整体智能表象。
  66.   然后,这个语意网络模型可做大量改进。
  67. 自动生成新的节点连接通路。
  68. 自动生成新的事件节点,扩充网络。
  69. 自动修改权值。
  70. A:使用特定算法,自动修改权值。
  71. B:加入智能评估系统,修改特定类事件的路径权值。
  72. C:生成特定事件节点,例如体力增强节点,智力上升节点,当触发此类节点事件时候,对起作用的节点的路径权值加大,激活门限减小。(因不可能知道是哪些具体事件起作用,故可看作是当前所有激活状态的节点事件起作用)。
  73. 在改进3的基础上,加入“灵感”模拟,即对网络部分节点加入大的瞬时(衰减快)刺激。
  74. 等等。
  75.   下面简单举一个例子:一只小狗,节点事件如下:看见主人、看见事物、肚子饿、吃食、叫、跑、打滚。
  76.   语意规则1:看见食物^肚子饿->吃食。
  77.   特定奖励节点:吃食。
  78.   随机动作:  叫、跑、打滚。
  79.   那么当小狗肚子饿时,如果没有食物,它可以选随机动作,如果它选择了跑或打滚,没有事物。如果它选择了叫,而刚好主人在主人就喂食,那么触发规则1,触发奖励节点。此时小狗肚子饿事件和看见主人事件和叫事件处于激活状态,这些事件节点之间的联结将改变,以至于小狗能够在肚子饿时候没有食物时候看见主人时候叫。(当然这还需要改进上述系统,只要大家肯动脑,相信没什么大问题)。
  80.   在这里,每个节点都是一个抽象的概念,可以由任何模型组成,也就是说它可以由任意模型嵌套组合而成,这样就可以以最优的嵌套组合(模型本无定式,惟用而化)构成整个智能系统,从而模拟智能表象。
  81. 六、结尾
  82.   因为游戏中智能模拟的重点就是建立相应的算法模型,并且想对深入研究游戏中的人工智能,就需要不断实践,所以在上面的文章中我用了几乎全部篇幅来讲解有关算法,就是希望大家能通过时间深入研究和学习。相信大家通过研究,也可建出漂亮的游戏智能系统。更复杂的人工智能系统需要建立如下几个重要部分,环境模型、事物模型、事物与环境的交互接口、(事物与事物交互接口、环境与环境交互接口)、智能决策模型、智能评估模型,智能学习模型。而这里的每一个部分都牵扯到非常广的领域,非一时所能叙述清楚,因此就不再细述。
复制代码

您需要登录后才可以回帖 登录 | 加入易码

本版积分规则

Archiver|手机版|小黑屋|EMAX Studio

GMT+8, 2024-3-29 17:10 , Processed in 0.010426 second(s), 19 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表