编辑
锁定
讨论

上传视频

本词条缺少概述图,补充相关内容使词条更完整,还能快速升级,赶紧来编辑吧!
人工智能之父图灵相信如果模拟人类大脑的思维就可以做出一台可以思考的机器,他于1950写文章提出了著名的“图灵测试”。
中文名
游戏人工智能
外文名
Artificial Intelligence games
人工智能之父
图灵
人工智能慨述
伟大的思想就源于这种简单的事物
状态空间法
将问题转换到对应状态空间


提到人工智能,就不能不说说我非常景仰的人工智能之父图灵。他相信如果模拟人类大脑的思维就可以做出一台可以思考的机器,他于1950写文章提出了著名的“图灵测试”,测试是让人类考官通过键盘向一个人和一个机器发问,这个考官不知道他问的是人还是机器。如果在经过一定时间的提问以后,这位人类考官不能确定谁是人谁是机器,那这个机器就有智力了。这个测试在我们想起来十分简单,可是伟大的思想就源于这种简单的事物之中。
然而,图灵的测试也只说明了事物具有了智能的表象,何可谓智能的本质呢,可能当今世上谁也说不清楚。浩浩星空茫茫幻化演变,何可谓智,何可谓能,本就是空。只是以我们人类的认识和想象,无中生有罢了。所以我们谈的智能只能局限于我们人类的认知和想象,抛开了主观,也就只剩客观存在而已。
也正因为我上面的观点,在此我仅讲一些简单的实用的模型,使我们的程序具有一定的智能表象,但绝非智能的本质。希望大家能通过不断的实践进行学习,如果能对大家有些许帮助,就已心满意足。
在这里先说一句非常重要的话,如果你无法用语言描述一个事物,那么你就很难更深入的研究它。在我们计算机程序中,如何为事物建立模型是非常非常重要的,好的模型一旦建立,就已成功一半了。
在这里,我们逐步学习一些的算法模型,逐步建立更好的智能系统,希望大家能够喜欢。


将问题转换到对应状态空间,然后以状态空间的分析方法分析问题,是解决简单问题常用的有效方法。在一个大的游戏智能系统中,局部的智能表象模拟通常都是采用这种简单而行之有效的方法。
例1:4个人晚上过桥,一个手电筒,最多2人同过,单独过桥需要时间分别为10、5、2、1分钟,2人同过,按慢的人算时间,问最少多长时间?
首先,我们建立状态表示模型,状态转化模型,智能评估模型。
状态表示模型即能表示任一时刻(或时段)的状态(最好和实际状态是一一映射方式)。状态通常由一些状态参数或规则表示。比如模型R :
Time:已用时间
PersonState[4]:4个人的状态,0表示未过桥,1表示已过桥
PersonWalkTime[4]:4个人的走路时间
LightState:手电筒状态,0表示未过桥,1表示已过桥
状态转化模型:由一状态如何转化到下一状态。比如模型T:加最简单限制,if(LightState==0) 可两人过桥,否则只许一人过桥,并且所有状态发生相应变化。采用广度搜索方式进行所有可能的状态转化。
智能评估模型:和智能表象相关的评估模型,可嵌套组合子模型。
模型E:Time越小越优。
在这个系统建立好后,我们很容易通过广度搜索来找到最佳过河方案。若是把相应数据输入电脑,而电脑可以得出过桥方式,那么我们就可认为在一定程度这个系统具有了智能的表象(想象着我们不知道其内部如果工作)。当然模型定义的越好,系统的性能也越好。
因为上面算法使用的是广度搜索,为此我们可加入一些改进,使其速度更快。
改进1:我们尽量使走的慢的人过桥次数少一些,因此我们在每次返回一携带手电筒的人时,都选择走的快的,这样的话,我们的搜索就显的更智能了一些,速度也会快很多了。这种算法也就是A算法(即每次搜索,选取最可能达到最优的情况搜索,这里就需要一个局部评估模块)。
改进2:我们在开始阶段定义一个Time数值,若出现搜索过程中Time已超过此数值的,其下搜索不再进行。若出现搜索结果小于Time的,我们更新Time,并继续搜索。运用这种方法,我们将省去很多无用的搜索。这种方法称为alpha-beta剪枝技术。


由于棋类游戏就是一种智力游戏,被研究的也较为深入,所以在这里我们举一个简单的黑白棋的人工智能的实现(因为黑白棋比较简单,对初学者来说很容易上手,所以比较适宜做教材)。在这里仍然采用了状态空间法。
黑白棋的人工智能。黑白棋,又叫反棋、奥赛罗棋等,在西方很流行。黑白棋的棋盘是一个有8*8方格的棋盘。下棋时将棋下在空格中间,而不是像围棋一样下在交叉点上。开始时在棋盘正中有一白一黑四个棋子交叉放置,黑棋总是先下子。下子的方法是:把自己颜色的棋子放在棋盘的空格上,而当自己放下的棋子在横、竖、斜八个方向内有一个自己的棋子,则被夹在中间的全部会成为自己的棋子。并且,只有在可以翻转棋子的地方才可以下子。最后棋盘全部占满,子多者为胜。
下面建立模型。
状态表示模型:模型R:board[8][8],=BLACK 表示黑棋,=WHITE 表示白棋,=EMPTY 表示空,turn=1 表示电脑走棋,turn=0 表示玩家走棋,mode=0 表示电脑走黑棋。
状态转化模型T:即先判断可以落棋的地方(是否为空,并且可以翻转棋子),然后落棋后改变board[m][n],turn。
智能评估模型E:吃子越多越好。
这样我们就建立了一个有低级智能表象的系统。为改进这个系统,我们来学习一些常用的技巧和算法。
战略点权值表:经过多次下棋,我们就可以知道棋盘的四个角是永远不能被吃掉的,所以这四个点是战略要地。同样,我们可以得出另一些重要的战略点。我们把这些点赋一个较大的权重,这样,我们可得到一个权重表(对应棋盘)。当然这个表可使用一些参数,并且可随过程改变而改变,越灵活的格式(如果你能收的住)将产生越好的智能表象。局势评估模块:对敌我双方的总体或局部兵力分布得出一个较为合理的分析结果,有了这个模块,才能更好的把握战局。
博弈树算法:也是一种状态搜索算法,但每个状态节点上都有一个评估。我们记敌我评估函数为 E(state)、M(state):
此主题相关图片如下:
图2
如图在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) )。
所以遍历 node10,node11,node12,电脑就可以得到其能获得的最大优势是MAX(MIN(F(node2i)))。当然此博弈树可以加大树的深度,并且可用A算法和alpha-beta算法改进。具体算法不再详述,有兴趣者可以自己研究。


上述的几种算法虽然可以模拟出比较好的智能表象,但遗憾的是没有学习功能。而学习功能相对于智能生物是一个非常重要的功能。因此,我们简单介绍一下遗传算法,并举一个具体的例子。
生物的进化是一个奇妙的优化过程,它通过选择淘汰,突然变异,基因遗传等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全局优化算法。
遗传算法简介:对问题产生一个描述,对待解决问题进行编码。随机初始化群体X(0)=(x1, x2, … xn)。对当前群体X(t)中每个个体xi计算其适应度F(xi),适应度表示了该个体的性能好坏。应用选择算子产生优良种群goodX(t)。对goodX(t)应用遗传算子,产生新一代群体X(t+1)。t:=t+1;如果不满足终止条件继续(3)。选择算子:选择算子从群体中按某一概率成对选择个体,某个体xi被选择的概率Pi与其适应度值成正比。最通常的实现方法是轮盘赌模型。
例3:同样看黑白棋,我们采用自学习的方法来模拟智能的实现。棋盘状态采用 敌方=-1、空=0、我方=1。棋盘大小为64,我们对每一个格子用5*5的局部棋子来评价其战略重要性。采用线性方式Important[node]=∑Wi*state[ i]。这样我们就得到一个W[64][25]的表,对于每一种棋盘局势它总能判断出战略重要性最大的点(姑且不论对与否)。这种编码方式考虑了棋盘全局位置特性与局部局势特性,大家可自行改进。
选取种群大小为30,随机生成30个Wi[64][25]。
初始训练阶段:对每一个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)。
采用这种方式,我们可以使程序自己学习,从而模拟智能。遗传算法的主体就是对问题编码,然后通过进化方式进化出优秀(相对于适应度)的种群,编码方式由具体问题决定,进化方式影响进化范围和速度。通过这种方式的学习,模型一般都能得到此编码方式下的最优编码,从而具有超越人为编码的性能。有兴趣的读者可以自行深入研究。


学会了以上算法,但一般只能进行小规模模型的智能模拟。下面我再给出一个语意网络模型,用来构建整体的模型,结合上面的算法,就可以作出漂亮的中等规模的智能系统。
例4:一个小型的带时限的语意网络模型。网络由节点及连接节点的线组成,为简单化,每个节点性质相同。节点:受到刺激后可被激活,激活后又可刺激邻接节点。激活度由一个刺激度的函数决定。节点有门限,只有刺激度超过此门限时节点才可被激活或抑制。节点有一个受激缓存,用来记录短期内受到的刺激。有一个激活缓存,用于控制激活时间段。
门限:GateT(激活)、GateN(抑制)。
受激缓存:FMemory记录受激大小,衰减度,受激时刻。
激活缓存:BMemory记录激活度大小,衰减度,激活时刻。
激活函数:Active 计算激活度,可由节点自定义。
连接节点的线:传递刺激并可调节刺激大小。
Wi:权值,表示相应的支持度(>0,越大表示越支持)或抑制度(D ,对应网络模型如下:
此主题相关图片如下:
图3
假设情景:A激活,1秒后B激活,2秒后C激活。A激活:D受激 Active(A) * W1 Gate(D),被激活,记入激活缓存。这样就可以表示短时间内事物受A、B、C事件刺激,将产生D时间。
如果 A^B->D成立, A^B^C->D不成立,D->H,A^B^C^E->D成立。
A发生,Active(A)*WaGateT(D),D激活 Active(D)*Wd>GataT(H),H激活。记入D和H的缓存。
C发生,Active(C)*Wc + NowActive(FMemory)吃食。
特定奖励节点:吃食。
随机动作: 叫、跑、打滚。
那么当小狗肚子饿时,如果没有食物,它可以选随机动作,如果它选择了跑或打滚,没有食物。如果它选择了叫,而刚好主人在主人就喂食,那么触发规则1,触发奖励节点。此时小狗肚子饿事件和看见主人事件和叫事件处于激活状态,这些事件节点之间的联结将改变,以至于小狗能够在肚子饿时候没有食物时候看见主人时候叫。(当然这还需要改进上述系统,只要大家肯动脑,相信没什么大问题)。
在这里,每个节点都是一个抽象的概念,可以由任何模型组成,也就是说它可以由任意模型嵌套组合而成,这样就可以以最优的嵌套组合(模型本无定式,惟用而化)构成整个智能系统,从而模拟智能表象。


因为游戏中智能模拟的重点就是建立相应的算法模型,并且想对深入研究游戏中的人工智能,就需要不断实践,所以在上面的文章中我用了几乎全部篇幅来讲解有关算法,就是希望大家能通过时间深入研究和学习。相信大家通过研究,也可建出漂亮的游戏智能系统。更复杂的人工智能系统需要建立如下几个重要部分,环境模型、事物模型、事物与环境的交互接口、(事物与事物交互接口、环境与环境交互接口)、智能决策模型、智能评估模型,智能学习模型。而这里的每一个部分都牵扯到非常广的领域,非一时所能叙述清楚,因此就不再细述。

Leave a comment

Your email address will not be published. Required fields are marked *