?

前 言（Forward）

欢迎来到《游戏编程人工智能技术》。我想你就会发现，这正是你所读到的有关游戏编程的最有用的书之一。

Mat最先引起我的注意是在大概2000年的时候，那时，他开始在GameDev论坛 (www.gamedev.net)发布各类关于游戏人工智能的帖子，并回答网友的各种相关问题。他很快就获得了大家的关注，在跟贴中也不乏赞扬与认同，尤其是在贴出他为公众消遣而制作的有关神经网络和遗传算法的两个教程之后。Mat发现游戏开发者需要获得AI技术方面的知识以期运用在游戏制作中，而他的两个教程以及在Gamedev论坛里提问的耐心答复无疑是满足这一需要的一个途径。我对能为这样一个专题的书写前言而感到荣幸，希望以后能有更多的此类专著。

本书内容（Content of This Book）

这本书基本上是为提高游戏制作水平而写的。主要通过使计算机对手更聪明，更有能力，和更接近真人来达到这个目的。这个新的知识领域只是在过去10年左右的时间里才开始引起真正的关注。

本书出版的同时，游戏开发者可以发现当今的游戏产业正不断扩展，吸引着更多新的玩家，并以史无前例的速度蓬勃发展。随着新的游戏机和PC平台不断拥入市场，游戏开发者会发现自己拥有极为充裕的物质条件：更大的记忆空间，更快的CPU速度，更多的连接选项，和更高的视频分辨率。这些新的功能为游戏开发者提供了无限的可能，但同时也让他们面对无数的取舍和重点选择。新的游戏应该是在视频分辨率上更高一些呢，还是应该使碰撞更具有真实感些？在游戏速度方面，我们在制作一年半以后要上市的游戏时，能够在那时的主流机上做何种程度的开发呢？如何使我们的游戏区别于市场上那些竞争对手的产品？

采用大量的游戏人工智能（AI）显然是使你的游戏鹤立鸡群的重要手段之一，有关游戏AI专题的书和文章的源源出版能充分说明这一点。高质量的游戏AI已经不再是为提高出帧率（framerate）才予以考虑的东西，它现在已是和图形（graphics）或声音（sound）一样，成为游戏设计过程的极为重要的一个部分，它是促进还是阻碍游戏产品畅销的一个决定性因素。游戏开发者正竭尽所能研究新的AI技术，以籍此构筑更好、更聪明的游戏AI。他们想要探索新的理念，使AI技术进入下一代，到那时，AI不仅是要创造有趣的游戏对手，而且还要使这个对手能够与玩家交谈（talk），能和众多的在线冒险家周旋（interact with)，能在一个一个的游戏中不断学习，使它在下一轮的游戏中变得更加聪明机智。

　　自然，这些新的AI也得帮助游戏产品更好地销售。这永远是一根底线。如果一个游戏产品不销售出去，则无论它的AI有多么高超也都无关紧要了。

制作更好的游戏（MakingSmarter Games）

本书着重探讨一个比较“新奇”的技术领域（无论如何，对于游戏行业来说如此）：遗传算法和神经网络及其在游戏制作中的运用。这个领域以前一直很难使游戏开发者感兴趣，主要是有以下几个原因。大多数游戏开发者都认为他们现有的技术已经很完善且容易调试。标准的有限状态机（finite state machine，FSM）和模糊状态机（fuzzy state machine，FuSM）已经出色地提供了稳固而易于调试的AI技术，一些备受欢迎的游戏，诸如帝国时代（Age of Empires）到Quake都采用这种技术的。的确，该些技术是切实可用，而且如果有足够的编程时间，该技术可以适用于几乎所有的场合。

但是这些技术也常常面临着过多的选择，而这就是游戏开发者开始采用减少返回法则（Law of Diminishing Returns）的地方。通过构筑FSM来处理一些新游戏所固有的无数的可能性会使开发者心思混乱，AI必须估算的选项数量多得使他们无法抵挡。对于一个游玩人来说，可能只有二、三种“明显”更好的选择，但对一个需要在星期六晚上为即将发送到出版商那里的游戏最终版编写AI程序的开发者，会这么认为吗？如果玩家看到，在一个将使游戏完全死机（hang）的关键抉择面前，AI作出了错误的选择，或者更糟的是，做了一个愚蠢的选择，且这样的情况发生了几次，那么，完蛋了！玩家就会把你的CD从驱动里退出并转向去玩别的游戏了。

与此相反，我们应该让玩家面对的电脑对手不存在盲点（blind spot），在一游戏中不存在那种会被玩家发现、并一旦运用就会引起AI脑死（AI brain-dead）的某种特殊状态组合。并要求玩家面对的AI能够不断适应玩家的风格，能随着玩家对游戏学习的深入，一起变得更加精明能干。

这种适应性，或者学习本领，对游戏开发者及游戏玩家来说就犹如一个圣杯（HolyGrail），无论何时，当问及玩家未来最希望看到的游戏时，回答的都会是这个。玩家希望接受能够适应他们的游玩风格的AI的挑战，而AI也能预料到玩家最有可能做些什么并相应地采取一些策略步骤，AI所做的就如同另一个人所做的那样。

进入未来（To theFuture）

现在让我们转来谈谈如本书所包含的一些更有兴趣的AI技术。这些技术给通常是枯燥的、逻辑性较强的AI领域，带来了许多生物学的思考方法，为开发者提供用以创造能和玩家一样思维的电脑对手的工具。使用这些技术，一个开发者可以构筑一个足够聪明的AI，它将能尝试不同的事物来考虑哪个效果更好，而不是只简单的从程序员编制的菜单里挑选出某个选项。它将会分析敌对部队的相对实力和位置，找出一个最近的突击点，并且不时地重新调配自己的部队来夺取胜利。

这些技术所带来的好处不仅仅是玩家能够玩得更畅快。如果构造合理，一个有学习功能的AI可以对程序员所花的游戏开发和测试时间产生确实的效果，因为程序员将不再必须构筑和测试几十甚至上百的脆弱而死板的AI逻辑。如果AI可以在只给予几个基本指导之后就通过观察职业人类玩家来学习怎样玩游戏，这个AI就不但会更牢靠，而且无疑能把游戏玩得更好。这就是阅读关于篮球的知识和实际亲手玩篮球的效果区别。

是不是这样就意味着Mat已经完成所有高难的工作，而你所需要做的就只是复制和粘贴他的编码到你最新的项目里去构筑一个能象真人一样的AI玩家呢？当然不是。这里所呈献的，是为那些完全不了解这些更边缘的AI技术和正在为新项目寻找灵感的人提供一个指导，一个筐架，和一条基线。可能，你没有时间去亲自研究这些可能性，又或者你想摆脱那些课本或网站上提供的过于理论性的说明。那么这本书可以为你提供所需的知识。

接下来的章节将用一种简单易懂的方式探讨这些技术。采用Mat一贯使用的游戏开发者互相探讨问题的方式阐述问题。

有学习功能和高适应性的AI技术是一门新兴的技术，它可以使游戏制作更完善，更满足游戏玩家的要求，并且，更重要的是，能更好的促进游戏发行量。

Steven Wookcock

????ferretman@gameai.com

?

?

致谢（Acknowledgments）

首先，我要感谢我的爱妻Sharon，在我写这本书的时候给予我极大的容忍、理解和鼓励。有无数次，当我从键盘前转过头去，眼神空洞地问她：“对不起，你刚才说什么来着？”时，她竟没有一次失去耐心对我扔盘子。

感谢Premier 出版社的Mitzi女士在本书写作的整个过程中给予我的帮助，回答我那些常常显得很荒唐的提问（虽然她认为约克夏男人讲话象Jamie Oliver！）。非常感谢Jenny, 我的编辑，对负责检查我的程序的bugs的Andre如此严厉，也感谢Heather帮我纠正了我的所有错误，并美国化了我的文章。

非常感谢Gary"Stayin' Alive" Simmons，他第一个建议我编写此书；还有我的网上教程的支持者们，他们的邮件每天都给予我很多鼓励；感谢Steve "Ferretman" Woodcock 为我写了前言；还有Ken，回答了我很多关于NEAT的疑问。

当然，我也不能忘了Fish和Scooter两个小宝贝，每当我坐下来写作时，它们就会跳到我的膝盖上来，向我亲热，使我感到温暖。

?

?

关于作者（Aboutthe Author）

Mat Buckland在伦敦大学学完计算机科学后，当过多年的风险管理咨询顾问。终于他开始厌倦了所有的金钱游戏和公司制度，就一把火烧掉了他原有的公司礼服，跑到一家为GremlinSoftware开发游戏的公司工作。虽然薪水少得多，但是却很有趣，而且他可以每天穿牛仔裤去上班了！现在Mat同时是一个自由程序员和人工智能咨询顾问。自从80年代初第一次接触到这些技术，他就对进化计算和AI尤感兴趣。他是ai-junkie.com网站（www.ai-junkie.com）的作者，该网站提供一些有关进化算法的教程和建议。

?

?

目 录 简 要

（Contents at a Glance）

?

前 言………………………………………………………………………………………… vi

丛书编辑者的来信…………………………………………………………………………xviii

引 言……………………………………………………………………………………………xx

第1部分 Windows编程 …………………………………………………………………… 1

第1章 Windows编程入门 ……………………………………………………………… 2

第2章 Windows编程进阶……………………………………………………….…… 30

第2部分遗传算法 ………………………………………………………………………… 75

第3章 遗传算法入门………………………………………..………………………..…76

第4章 置换码，TSP问题 ….………………………………………………….……. 100

第5章 改进遗传算法…………………………………………………………………… 123

第6章 登月工程 ……………………………………………………………………… 152

第3部分神经网络? ………………………………………………………………………201

第7章 神经网络入门………………………………………………………………… 202

第8章 为机器人增添知觉…………………………………………………………… 242

第9章 有监督的训练方法…………………………………………………………… 258

第10章 实时演化………………………………………………………………………288

第11章 演化神经网络的拓扑…………………………………………………………303

第4部分附录 …………………………………………………………………………… 366

附录A Web资源…………………………………………………………………… 367

附录B 参考书目和推荐读物………………………………………………………….369

附录C 光盘内容说明………………..……………………………………………… 372

结 束 语 …………………………………………………………………………………… 375

索 引 …………………………………………………………………………………………376

?

目? ?录

?

译者序 ………………………………………………………………………………i

前言 ……………………………………………………………………………… vi

致谢 ……………………………………………………………………………… ix

关于作者 ………………………………………………………………………… ix

目录 ……………………………………………………………………………… xi

丛书编辑者的来信 ……………………………………………………………… xx

引言 ……………………………………………………………………………xxii

?

第一部分 windows编程……….………………………………… 1

第1章 开始出现一个字, 这个字就是Windows ……….…………………… 2

1.0 后来再出来Word和Excel，…，等……….………………………………………… 2

1.1 历史一瞥…………………………………………………………………………… 2

1.1.1 Windows 1.0 …………………………………………………………………… 3

1.1.2 Windows 2.0 …………………………………………………………………… 3

1.1.3 Windows 3.0和3.1………………………………………………………… 3

1.1.4 Windows 95 ………………………………………………………………… 4

1.1.5 Windows 98及其后续版本 ………………………………………………… 5

1.2 Hello World! ………………………………………………………………………5

1.3 你的第一个Windows程序 ………………………………………………………6

1.3.1 匈牙利表示法 ………………………………………………………………… 9

1.3.2 你的第一个窗口 …………………………………………………………… 11

1.3.2.1 注册你的窗口…………………………………………………………… 12

1.3.2.2 创建窗口………………………………………………………………… 15

1.3.3 Windows消息循环（Message Pump）……………………………………… 18

1.3.4 Windows过程（Windows Procedure）……………………………………… 21

1.3.4.1 WM_CREATE消息…………………………………………………… 23

1.3.4.2 WM_PAINT消息……………………………………………………… 24

1.3.4.3 WM_DESTROY消息………………………………………………… 26

1.3.4.4 其余的怎样呢？………………………………………………………… 27

1.3.5 键盘输入 ……………………………………………………………………… 27

1.3.5.1 虚拟键代码（Virtual Key Codes）……………………………………… 27

1.3.6 嗒的嗒！……………………………………………………………………… 29

?

第2章Windows编程中进一步的各种奇遇 ……………………………… 30

2.1 Windows图形设备接口（GDI）………………………………………………… 30

2.1.1 设备描述表（Device Context, DC）……………………………………………31

2.1.1.1 怎样得到句柄（Handle）呢？…………………………………………… 31

2.1.2 各种绘图工具：画笔、画刷、颜色、线和形状……………………………… 33

2.1.2.1 自定义画笔（Pen）………………………………………………………… 37

2.1.2.2 画刷（Brushes）…………………………………………………………40

2.1.2.3 形状（Shapes）………………………………………………………… 42

2.2 文本（Text）………………………………………………………………………46

2.2.1 TextOut ………………………………………………………………………… 47

2.2.2 DrawText ……………………………………………………………………… 47

2.2.3 加入颜色（color）和透明度（Transparency）……………………………… 48

2.2.4 实时消息抽取循环 …………………………………………………………... 49

2.3 如何创建后备缓冲区? ……………………………………………………………… 51

2.3.1 这听上去很棒，但怎样来实现呢？…………………………………………… 53

2.3.2 我怎样来使用后备缓冲器呢？………………………………………………… 55

2.3.3 保持干净（Tidy）………………………………………………………………57

2.4 使用资源（Resources）…………………………………………………………59

2.4.1 图标（Icons）………………………………………………………………….60

2.4.2 光标（Cursors）……………………………………………………………61

2.4.3 菜单（Menu）………………………………………………………………62

2.4.4 为菜单添加具体功能 ………………………………………………………… 63

2.5 对话框（Dialog Boxes）………………………………………………………65

2.5.1 一个简单的对话框 …………………………………………………………… 66

2.5.2 一些更有用的知识 …………………………………………………………… 68

2.6 正确定时（Timing）……………………………………………………………73

2.7 结束了！………………………………………………………………………… 74

?

第二部分 遗传算法（Genetic Algorithms）…………………… 75

第3章 遗传算法入门 …………………………………………… 76

3.1 鸟和蜜蜂…………………………………………………………………………… 76

3.2 二进制数速成……………………………………………………………………… 81

3.3 计算机内的进化…………………………………………………………………… 83

3.3.1 什么是赌轮选择（Roulette Wheel Selection）？………………………… 84

3.3.2 什么是杂交率（Crossover Rate）？……………………………………………85

3.3.3 什么是变异率（Mutation Rate）? ………………………………………………85

3.3.4 咂搞的呀！…………………………………………………………………… 85

3.4 帮助Bob找回家 ……………………………………………………………………86

3.4.1 为染色体编码 ………………………………………………………………… 88

3.4.2 Epoch方法 …………………………………………………………………… 93

3.4.3选取参数值 …………………………………………………………………… 95

3.4.4 算子函数（Operator Functions）……………………………………………96

3.4.4.1 重温赌轮选择…………………………………………………………… 96

3.4.4.2 重温杂交（Crossover）算子 …………………………………………97

3.4.4.3 重温变异（Mutation）算子 ……………………………………………98

3.4.5 运行寻路人（Pathfinder）程序 ……………………………………………99

3.5 练习题……………………………………………………………………………… 99

?

第4章 置换码与巡回销售员问题 ………………………………………… 100

4.1 巡回销售员问题（TSP）……………………………………………………… 100

4.1.1 小心陷阱 …………………………………………………………………… 102

4.1.2?CmapTSP，SGenome，CgaTSP??? ……………………………………… 104

4.1.2.1 CmapTSP类………………………………………………………… 104

4.1.2.2? SGenome结构 ……………………………………………………… 107

4.1.2.3 CgaTSP类 …………………………………………………………… 109

4.2 置换变异算子（Permutation Mutation Operator）………………………… 111

4.3 置换杂交算子（Permutation Crossover Operator）……………………… 115

4.4 挑选一个适应性函数 …………………………………………………………… 116

4.5 选择 (Selection) ………………………………………………………………… 118