分类： 游戏AI

04.《吃豆人》的游戏AI分析

P小二
在03.游戏AI的鼻祖——《吃豆人》中，主要介绍了《吃豆人》这个游戏开发的一些历程，也简单分析了游戏中出现的游戏AI类型与其发挥的作用。今天我们详细介绍它的游戏AI。
在上一篇文章中提到，《吃豆人》拥有三种现代游戏AI的雏形。包括了Character AI（角色AI)，Meta AI（概念AI）和Navigation AI（导航AI)。
它们分别在游戏中的作用如下：
  1. 角色AI ：控制角色功能 
  2. MetaAI：控制游戏整体难度
  3. 导航AI ：定位玩家并给出追踪路径
角色AI 
吃豆人的角色AI 是指游戏中四个鬼魂的AI， 我们这里也可以称为游戏NPC（非玩家角色）AI。
下面为四个角色的介绍：
  • 红色鬼魂Blinky：主动进攻型的角色，它会不停的追踪主角
  • 粉丝鬼魂Pinky：主动进攻型的角色，它会追踪主角正前方两格的位置
  • 蓝色鬼魂Inky： 会追踪红色鬼魂的位置，以主角朝向为轴进行翻转后的位置
  • 橙色鬼魂Clyde：和主角保持距离的角色，当距离主角比较远时，会开始追踪主角。当距离主角比较近时，会开始往地图的一个角落移动
吃豆人中的每只鬼魂都有自己的名字并且初始化的位置，运动方式都是不同的。这赋予了游戏的NPC，一种个性丰富的形态。
这种角色 AI是通过一套规则系统设计出来的。下面是游戏中吃豆人的状态图：
从上图可以看出，吃豆人的状态，是根据鬼魂是否在附近，是否吃了能量药丸发生变化的。同时鬼魂有三种状态。
鬼魂的状态有： 追逐，散播和受惊
 
  • 追逐  在追逐模式中，目标为在迷宫中抓住吃豆人
  • 散播  在散播模式中，鬼魂将暂时放弃追逐，并朝着各自的角落前进
  • 受惊  当吃豆人吃掉一个能量药丸时，鬼魂便会进入受惊模式并开始逃跑

 

四个鬼魂拥有这三种互斥状态中的任意一种，再加上吃豆人的状态，给游戏带来了更多的变化。
从现在来看，基于规则的AI，如果在游戏场景比较复杂的情况时，会多出很多的状态。如果要去分解这些状态，编写状态的行为，设计状态之间的转移条件，是会带来非常大的游戏开发成本。
MetaAI
MetaAI 有的文章翻译为概念AI，这里我们就使用这个翻译。
概念AI在游戏中，是为了让人感觉游戏很有趣，有时又会透过施加压力来为难玩家的一种AI。
在吃豆人游戏中，MetaAI 是可以控制游戏整体难度，让玩家不会觉得太难而放弃，或者太简单而没有乐趣。
概念AI算是游戏世界之神，它决定了游戏拿什么去撼动玩家的感情。一个好的游戏，会带动玩家的情感变化，让玩家收获情绪价值。
具体到吃豆人的实现中，《吃豆人》的程序可以通过分析玩家玩游戏的各种数据，来判断玩家的游戏水平，从而自动调整游戏的难易程度，达到每个人都可以获得一种叫做征服的情感体验。
 
40年后的今天，现代概念AI，能做的事情就非常多。可以分配一个NPC给玩家带路或者一起战斗，可以俯瞰整个关卡并控制难度，还可以生成剧情等等。
 
导航AI 
导航可以分成世界导航和局部导航，两者的区别只有范围上的区别，但是在实现上会区别对待。
世界导航是指玩家可以从世界中的A点达到B点的一条路径，而局部导航是指让我们的NPC从他的世界中的位置，移动到他要去的地方。
局部导航和世界导航不同的地方是，局部导航需要考虑局部世界，并且导航NPC在里面穿越，它必须知道周围的环境，还需要考虑其他的NPC位置，发现存在哪些路径可以选择，然后选择一条走。
吃豆人游戏中的导航AI主要的负责定位玩家位置，也就是吃豆人的位置 ，然后给出每个鬼魂的追踪路径。
《吃豆人》整体地图及界面设计
在吃豆人中，动态定位吃豆人的位置是较简单的，主要还是鬼魂的追踪路径和逃跑路径的问题。因为每个鬼魂的设定是不一样的，而且鬼魂不能倒退，只能在迷宫中路口才能转弯，对于实时的追踪路径算法还是有一定的要求。
《吃豆人》的游戏AI就介绍到这里了。后面的几篇文章，我们将把《吃豆人》这个游戏为例子，来讲解一些常见的游戏AI方法。
 
这些游戏AI方法包括：特定行为编辑 ，树搜索，进化计算，还有像监督学习，强化学习和无监督学习等一些算法。
往期推荐：
03.游戏AI的鼻祖——《吃豆人》
02.游戏AI从简单世界开始夺权
01.AI将改变未来的游戏

03.游戏AI的鼻祖——《吃豆人》

P小二
不少教科书和课程会把《吃豆人》这个游戏作为游戏AI的鼻祖。为什么它会是鼻祖呢，今天就带来游戏AI鼻祖《吃豆人》。


吃豆人游戏介绍

《吃豆人》（Pac-Man）是一款由南梦宫制作的街机游戏，游戏最初于1980年5月22日在日本发行，由南梦宫公司的岩谷彻设计。

图片

吃豆人，在1980年代风靡全球，被认为是最经典的街机游戏之一，游戏的主角吃豆人的形象甚至被作为一种大众文化符号。它的开发商南梦宫（现：万代南梦宫娱乐）也把这个形象作为其吉祥物和公司的标志，一直沿用至今。


吃豆人制作人——岩谷彻

1977年，一个名叫岩谷彻的有为青年通过自学技术，到东京的一家娱乐设备制造公司南宫梦求职。南宫梦因为他在游戏设计方面的创新能力和天赋，决定雇用岩谷彻，岩谷彻得到了给南宫梦的新电子游戏部门设计游戏的工作。

图片
                    岩谷彻(中)
岩谷彻的游戏设计方法之一是，用与故事有关的关键词来辅助游戏想法的构思。
《吃豆人》的灵感，岩谷彻是从一个关于保护孩子免于被怪兽吃掉的童话故事中获得的。这个童话故事的怪兽有四种鬼，它们会在迷宫中追击玩家，从而增加游戏的紧张感，而且鬼对玩家的进攻是分批的，而不是无限的袭击。

每一个鬼都有独特的个性，童话故事中还有一个“精神”的概念，是可以让吃豆人能够吃鬼的力量。岩谷彻把这个概念变成游戏迷宫中的可吃的力量丸，玩家吃了这种力量丸就获得了吃鬼的力量。
图片
               《吃豆人》游戏策划书
游戏名称和基本概念到位后，岩谷彻正式启动项目。南宫梦分配给岩谷彻开发《吃豆人》的团队包含一名程序员、一名硬件工程师、一名美工和一名作曲师。《吃豆人》的外观和感觉在这一年里不断演化。开发团队花了大量时间和精力制作鬼在迷宫中的特殊移动模式和调整游戏难度的变化。
《吃豆人》制作了一年零五个月。最终，这款当时开发耗时最长的游戏于1980年5月22日在日本发行。
吃豆人游戏玩法
游戏的目的就是控制游戏的主角吃豆人吃掉藏在迷宫内所有的豆子，并且不能被鬼魂抓到。
迷宫的四个角落有大的闪烁点称为大力丸，提供吃豆人一小段时间，可以反过来吃掉鬼魂的力量。鬼魂在这段时间内会变成深蓝色，会往反方向逃逸，而且比平常的移动速度慢。当鬼魂被吃掉时，它的眼睛还在，会飞回鬼屋，并再生而恢复正常的颜色。当深蓝色的鬼魂反白闪动时，表示大力丸的效力即将消失，而随着游戏的进展，大力丸的有效时间会越来越短。

图片
吃豆人角色介绍
吃豆人： 玩家控制的角色。  

目标吃掉藏在迷宫内所有的豆子，以获取胜利。吃豆人也能吃大力丸来反吃鬼魂,让自己的关卡局势变得更好。
图片
鬼魂：
图片
红色的鬼魂(Blinky)，游戏开始后第一个出来。
追击模式：他会直直朝吃豆人的位置前进，并且会随着豆子数量减少而加速。
粉红色的鬼魂(Pinky)
追击模式：她会瞄准吃豆人移动位置的前四格（16个像素）推进，试图伏击玩家。
浅蓝色的鬼魂(Inky)，吃了30个豆子后出来，他是行动最复杂的鬼魂。
追击模式：他会求得Blinky和吃豆人之间的向量，设计一个有效的陷阱来夹击玩家。

橘色的鬼魂(Clyde)，最后出来的鬼魂。
追击模式：他会朝吃豆人的位置前进，但直到他接近吃豆人8格时，他会撤退回到属于他的迷宫角落（左下）。
吃豆人的游戏AI
《吃豆人》里一共有4种颜色的怪物。如果这4个怪物都以相同的算法来追踪玩家的话，那游戏里就变成4个怪物排队追赶玩家。如此一来，玩家只要确保屁股不被咬到就能安全过关。
 
所以团队把这4只怪物分散到了玩家的四周，同时采用了包围并追击玩家的算法。据团队回忆，这个想法是由当时的程序员提出来的，每只怪物的运动方式都各不相同。
图片
描述了4只怪物不同状态下行动模式的表格
从现在的角度来说，《吃豆人》可以说是第一款能够把游戏中的角色以个性丰富的形态呈现出来的作品。具体来说，能让角色表现出不同个性的角色AI，和控制游戏整体难易度的Meta AI功不可没。
当时我连“人工智能”或者“AI”这两个词都不知道，我只是努力地让所有人能都从我的游戏中获得快乐。除了经常能在游戏厅看到的青少年之外，小女孩和上了年纪的老人也是我们预设的用户对象。  岩谷彻在后面的采访中说。
 
现代游戏AI的要素
现代游戏AI其实已经发展成角色AI、Meta AI和导航AI三部分组成的复合型程序。在《吃豆人》中，其实我们也可以看到这三个要素。
 
角色AI是肩负起怪物角色大脑功能的AI、Meta AI则是控制游戏整体难度的AI，而在游戏内负责定位玩家位置并给出追踪路径的，也正是导航AI。
游戏AI带来的惊喜
《吃豆人》中的MetaAI，是可以从玩家的游戏记录中判断出“这个人水平不行”，然后降低游戏难度。
岩谷彻说：“由程序来判断玩家的游戏水平，然后以此为基准调整游戏的难易度——这个被称为自主控制系统的东西，我在很久之前的开发工作中就已经在使用了”。
游戏本身很好玩，但仅仅是因为几个数字变化的难易度调整就被骂成垃圾游戏的经历，我已经体会了很多次了。所以我非常希望有一个能监视玩家的游戏状态，比如说命中率和操控失误等数据的程序。
 
当时我们做了一个这样的对比实验：在一个游戏厅里放两台《吃豆人》，其中一台的难度设定比较高。当时有玩家来玩了之后很纳闷，甚至觉得是不是自己状态不太好，实际上是他玩的那台机器是高难度版本的。
图片
经过测试，这两台机器每天的收入差大概有2000日元。假设在全日本范围内有1万台《吃豆人》，然后按300天来计算就是60亿日元。只是一个难度控制的开关就能制造出如此巨大的收入差距，而且游戏越受欢迎数字就会越大，这给了我们巨大的震撼。

其实自主控制系统虽然能判断一个人的水准是否满足了难度提升的条件，但它无法知道这个人所能承受的极限在哪里。
 
从这点来说，AI有时候会把人逼到一个窘境。如果能让AI在某个难度的前提下保持一段时间不再继续提升。这样玩家就获得一种征服的感觉，并且会觉得自己至少能玩上30分钟，那我们的目的就达到了。

往期回顾
02.游戏AI从简单世界开始夺权
01.AI将改变未来的游戏

02.游戏AI从简单世界开始夺权

P小二
棋牌游戏作为人类最早的游戏类型，也是我们最早会接触到的，规则简单易学的桌游。游戏AI的出现，也是从这种最简单的游戏开始，然后攻城略地。这期间不乏趣事，土耳其行棋傀儡就是其中之一。
土耳其行棋傀儡
土耳其行棋傀儡是18世纪出现的一个自动下棋装置，它是奥地利的沃尔夫冈·冯·肯佩伦在1770年为取悦玛丽娅·特蕾西娅女大公而建造并展出的，声称可以击败人类棋手。
它从1770年被造出来，到1854年毁于大火的84年间，被带到欧洲和美洲进行展览和与人对弈，击败了很多的挑战者，包括了凯瑟琳大帝，本杰明富兰克林和拿破仑。
当时作为数学家的计算机先驱，查尔斯·巴贝奇也两度输给它，而埃德加·爱伦·坡则写文章质疑这台机器。他认为这个机器是一场彻头彻尾的骗局，如果真的是机器，应该总能赢才对。
直到1857年，《国际象棋月刊》刊登了一篇文章，正式揭露土耳其行棋傀儡是由人类棋手藏到里面操作机械手这一骗局。
 
下图为原理图
其实，它在和拿破仑对弈的时候，就表现出了破绽。当时拿破仑拿一系列不合规的行动对它进行测试，然而它却以飞快的速度把桌子上的棋子一扫而空，这让拿破仑起了怀疑之心。 这场骗局最聪明的地方其实是在于，那位真人棋手是怎么巧妙的隐藏自己而不被人们检查装置时发现。
在当时的很长一段时间内，为了达到制造能够打败人类的机器这个目标，主要是追求的重点放在计算上。 如果优秀的棋手能够预判7步，那机器能够预判8步就算赢，后面的事实证明，这种预判更远的优势其实并不是人类赢棋的真正秘诀。
卡斯帕罗夫与深蓝的对决
卡斯帕罗夫是有史以来最伟大的国际象棋大师之一，他与IBM制造的超级电脑深蓝一共进行过两次对决。
在1996年首次对决中，卡斯帕罗夫以4:2的战绩击败深蓝。在1997年，他输给了卷土重来的“深蓝”。
在对决结束后的采访中，卡斯帕罗夫认为电脑更善于计算，而人类则善于类比思维和视觉思维。
他认为：我们棋手有评估棋路的不同方法。举例来说，在国际象棋中，如果你试图简化它，有些特定的位置是我必定要选择占据的。我的决定大约只有1%是基于计算而来，甚至更少。而99%的棋路则是基于我对棋谱的理解以及经验加成。电脑做出决定的过程完全相反，它99%的棋路是通过计算而来，只有1%左右是自己的理解，虽然这种理解正不断增强。
其实根据心理学家蔡斯和西蒙的研究，国际象棋高手，有一部分特长是能够将当时的情况与他们之前遇到的情况进行比较。这种将两种经验进行比较的能力，可以做出更好的决策。
这种借鉴过去经验的能力对于卡斯帕罗夫能够第一次战胜深蓝是非常重要的。这是因为人类可以动态切换风格，而深蓝则一直在使用相同的硬编码来决策。如果深蓝在判断哪一步最佳的标准上出了错，就算后面深蓝能算出几亿个位置，也是无济于事的。
图为1996年时代杂志封面：Can machines think?
突破”简单”的围棋
围棋在理念层面上是一个非常简单的游戏，游戏中唯一的武器就是在何处落子。
围棋的位置状态空间，有3个状态： 黑子，白子和没有子。因为有19X19的网格，所以是3的361次方。2016年，研究者移除了不合规的状态，算出来状态数量大约为10的170次方。
从上面的数字可以判断，围棋的状态数量是非常巨人的，如果还考虑游戏内部互联的问题，往前预判一步，预判的难度会成指数级增长。
所以就人类预判的多少步来讲，现在计算机和人就变得一样。虽然计算机计算速度比人类快，但是能考虑的信息量其实也是有限的，这就导致人类和计算机都变成了速记员。
AlphaGo的成功其实很不一样，一方面依靠了计算机在运算速度方面这20年的进步，另一方面它抛弃蛮力，利用自己对过去的知识学习，来确定当前比赛的每一步的价值。
 
那到底学习了哪些过去的知识呢？AlphaGo团队用了3000万场真实存在的大师棋局来训练策略算法，这让它有了大师面对各种各样情形的经验。但是AlphaGo的真正目标是超越人类，团队就设计了在当前棋局中反复无数次的自己跟自己博弈，来改进自己的价值网络。
所以深蓝和AlphaGo的区别，就是我告诉了深蓝一步秒棋，深蓝就照着走了。而AlphaGo则是告诉自己，在特定的环境下，一步秒棋会是怎么样的，在这个前提下，自己找到当前能够执行的最优解。
我们应该向AI学习？
2006年的世界象棋竞标赛中，一个选手的经理指责另外一个选手去洗手间过度频繁，有可能是在洗手间向另外一个国际象棋程序寻求帮助。然后他还展示了那个选手的下棋方式和一款热门的国际象棋软件的下棋方式有80%的相似度。
作为比赛选手，向AI学习并用来作弊，是否道德暂且不论。我们现在讨论的是，后面的真实人类比赛应该怎么举办。
我们要禁止选手上洗手间么？我们会允许选手戴眼镜么？后面比赛的时候，我们是不是也要检查选手是否有设备植入身体呢？
 
 
现在电子竞技这么发达，一个游戏比赛的观众很容易就破几亿，而Dota2的比赛奖金也已经过亿了。这些比赛如果被AI突破，那些观众如何知道他们看到的是真人操作还是AI操控的游戏呢？
我们可以预想，那时的比赛规则可能会比现在的F1方程式规则更严，而AI作为更强的兴奋剂，会时刻被那些想赢的人惦记，不管它是用来训练选手还是做数据挖掘，或者决策。
最后，我们是否想过，在未来，当机器变得比现在的人脑更复杂的时候，机器是否会控制一切呢？在生命进化的历程中，人类，大自然，机器这三个选手，人类是否还会依然坚定选择大自然呢？那大自然会站在人类还是机器那边么？ 作为人类的你，会支持谁呢？
往期推荐
01.AI将改变未来的游戏

01.AI将改变未来的游戏

P小二
写在前面：这是我和好朋友大空新一的一个实验，大空新一写DPU专栏，每周一更新，我写GameAI专栏，每周二更新，欢迎关注评论并转发。
游戏AI
AI在近年来取得了巨大的进步，更多的AI落地应用出现在我们的生活中，让人们能够更好的执行和理解图像，语音和文字。在比如情感检测，自动驾驶汽车，多模态搜索，辅助创意设计，蛋白质结构预测等任务上都有所突破。特别在游戏上，有一些任务，机器已经达到甚至超越了人类的水平。 
 
其实自从AI诞生开始，游戏一直为AI的研究提供助力。因为游戏不仅提出了有趣且复杂的问题，而且游戏还是科学与艺术相互碰撞出来的领域，这给AI提供了独特且优秀的研究环境。
1997年，IBM设计的深蓝击败国际象棋世界冠军卡斯帕罗夫，2016年DeepMind研发的围棋AI AlphaGo击败韩国著名棋手李世石，2017年AlphaGo战胜世界第一棋手柯洁，然后围棋AI再无人类对手。
最近，柯洁在比赛中完败一向有“申工智能”之称的申真谞后，在微博留下一句：“我受够了AI围棋”。这也说明人类正在向围棋AI学习，越来越像AI了。
                            AlphaGo对战李世石
在AlphaGo后，还出现了更多的游戏AI。比如在星际争霸中击败99.8%的玩家的“AlphaStar” ，在电竞游戏中击败世界冠军的Dota2 AI “OpenAI Five”，以及在六人无限制德州扑克中击败人类职业选手的Pluribus，越来越多的游戏被AI突破。 
AI如何改变游戏
随着AI在游戏中不断的应用，AI将改变游戏的未来。不止是在上面提到的AI玩游戏这个方向，AI会在游戏的各个方面起到变革的作用。
很多游戏AI的研究者把游戏AI分为玩游戏，生成内容和对玩家建模三种。
 
本专栏主要讨论的是，针对设计师的生成内容和针对玩家的玩家建模以及自动生成内容和玩游戏，不讨论利用游戏进行AGI（通用人工智能）研究和对玩家行为进行数据挖掘等方向。
          来自：《人工智能与游戏》p208
专栏内容涉及到的算法，既有传统的AI算法，像行为树，有限状态机，决策树，路径规划等，也会有进化计算，监督学习和强化学习等算法。
开始我会从一些游戏AI的案例讲起，比如经典街机游戏《吃豆人》的AI，流行的视频游戏如《巫师3》的AI实现，再到使用GPT-3文本生成内容的AI Dungeon，以及会带你解析最近OpenAI的Codex，为什么能用7句话就能生成一个极简版塞尔达，还会介绍我们应该怎么使用AI来解决wordle这种字谜游戏。
                              吃豆人游戏
专栏内容如果碰到算法原理，我会尽量用代码的方式来解释说明各种算法，也会把完整代码放出来供大家运行，希望达到一个直观的学习效果。
游戏AI方法
  • 特定行为编辑
    • 有限状态机
    • 行为树
    • 基于效用的AI
  • 树搜索
    • 非启发式搜索
      • 深度优先
      • 广度优先
    • 最佳优先搜索
      • A*
    • 极大极小
    • 蒙特卡罗树搜索
  • 进化计算
    • 局部搜索
    • 进化算法
  • 监督学习
    • 神经网络
    • SVM
    • 决策树
  • 强化学习
    • 动态规划
    • 蒙特卡罗方法
    • 时序差分学习
      • Q-learning
  • 无监督学习
    • 聚类
      • km聚类
      • 层次聚类
    • 频繁模式挖掘
      • Apriori
      • 广义序贯模式
  • 混合算法
    • 神经进化
    • ANN+时序差分学习
      • TD-Gammon
      • Deep Q network
上面的游戏AI方法，我基本都会提到，但是会有一部分没有案例解答，一是因为我研究的重点在PCG(程序化内容生成）和基于AI的游戏，很多方向不是很熟悉。二是专栏是周更，内容太多更不完，也没那么多的精力。如果有同学对某个方法有研究，欢迎投稿给我。
 
如果需要完整的学习整个游戏AI，可以参考下面的参考书籍和参考资源。
 
除了上面的游戏AI方法，我还会对基于AI的游戏进行进一步的讨论，包括现在的游戏Chatbot，AI文字游戏等利用AI作为游戏内容一部分的游戏。
 
参考书籍
– 游戏中的人工智能（第3版)
– 人工智能与游戏
参考资源
– AI and Game Youtube频道
https://www.youtube.com/c/AIGamesSeries
– 人工智能与游戏的官网
 http://gameaibook.org
往期推荐
游戏，人工智能与元宇宙