游戏中的人工智能（第3版）

    除了在棋盘游戏中发威，AI技术在其他类型的游戏中也给玩家留下了深刻的印象，例如，有限状态机、路径发现（这是“寻路术”技术的代名词，本书第3章有详细介绍）、转向行为、自动编队、行为树决策、模糊逻辑决策、航点和战术分析等。这些技术都关联着大量算法，本书对这些算法都进行了详细的分析，并提供了伪代码（方便开发人员在不同的编程语言中实现）、实现说明和性能分析等。
    此外，本书还提供了许多技术和算法在游戏中的应用思路，包括在游戏中实现AI的中间件思想、执行管理和调度方法、游戏世界的表示方式和接口、工具链创建和脚本的开发、各种游戏类型及其AI实现技巧等。这些内容可以为开发人员实现自己的游戏AI提供很好的启发。

《游戏中的人工智能（第3版）》详细阐述了与游戏人工智能相关的基本解决方案，主要包括游戏AI、移动、路径发现、决策、战略和战术AI、学习、程序化内容生成、棋盘游戏、执行管理、世界接口、工具和内容创建、游戏AI编程、游戏AI设计、基于AI的游戏类型等内容。此外，本书还提供了相应的示例，以帮助读者进一步理解相关方案的实现过程。 本书适合作为高等院校计算机及相关专业的教材和教学参考书，也可作为相关开发人员的自学读物和参考手册。 

第1部分  AI和游戏
第1章　导论 3
1.1　AI的定义 4
1.1.1　学术派AI 5
1.1.2　游戏AI 9
1.2　游戏AI模型 11
1.2.1　移动 12
1.2.2　决策 13
1.2.3　策略 13
1.2.4　基础架构 14
1.2.5　基于代理的AI 14
1.2.6　该模型在本书中的意义 15
1.3　算法和数据结构 15
1.3.1　算法 16
1.3.2　表示方式 18
1.3.3  实现 19
1.4  本书的布局结构 20
第2章　游戏AI 21
2.1  复杂度谬误 21
2.1.1  简单的AI也能做得很好 21
2.1.2  复杂的AI也可能很糟糕 22
2.1.3  感知窗口 23
2.1.4  行为的变化 24
2.2  游戏中的AI类型 24
2.2.1  借鉴技术 25
2.2.2  启发式方法 26
2.2.3  算法 28
2.3  速度和内存限制 28
2.3.1  处理器问题 29
2.3.2  低级语言问题 29
2.3.3  内存问题 31
2.3.4  平台 33
2.4  游戏AI引擎 36
2.4.1  游戏AI引擎的结构 37
2.4.2  工具问题 38
2.4.3  综述 39
第2部分  技    术
第3章　移动 43
3.1  移动算法基础 44
3.1.1  二维移动 45
3.1.2  静止状态 46
3.1.3  运动学 49
3.2  运动学移动算法 52
3.2.1  寻找 53
3.2.2  漫游 56
3.3  转向行为 58
3.3.1  转向基础知识 58
3.3.2  变量匹配 59
3.3.3  寻找和逃跑 60
3.3.4  到达 62
3.3.5  对齐 65
3.3.6  速度匹配 68
3.3.7  委托行为 69
3.3.8  追逐和躲避 70
3.3.9  朝向 73
3.3.10  直视移动的方向 74
3.3.11  漫游 75
3.3.12  路径跟随 77
3.3.13  分离 82
3.3.14  避免碰撞 85
3.3.15  避开障碍物和避免撞墙 90
3.3.16  小结 94
3.4  组合转向行为 95
3.4.1  混合和仲裁 95
3.4.2  加权混合 96
3.4.3  优先级 101
3.4.4  合作仲裁 104
3.4.5  转向管道 106
3.5　预测物理 117
3.5.1  瞄准和射击 118
3.5.2  抛射物轨迹 118
3.5.3  射击问题求解 120
3.5.4  具有阻力的抛射物 123
3.5.5  迭代定位目标 125
3.6  跳跃 131
3.6.1  跳跃点 131
3.6.2  着陆垫 134
3.6.3  坑洞填充物 138
3.7  协调移动 139
3.7.1  固定编队 140
3.7.2  可扩展的格式 141
3.7.3  自然编队 142
3.7.4  两级编队转向 143
3.7.5  实现 146
3.7.6  扩展到两个以上的级别 151
3.7.7  槽位的职业角色和更好的分配 153
3.7.8  槽位分配 156
3.7.9  动态槽位和队形 160
3.7.10  战术移动 162
3.8  马达控制 165
3.8.1  输出过滤 165
3.8.2  与能力匹配的转向 167
3.8.3  常见执行属性 169
3.9  第三维中的移动 171
3.9.1  三维旋转 172
3.9.2  将转向行为转换为三维 173
3.9.3  对齐 174
3.9.4  对齐向量 175
3.9.5  朝向行为 176
3.9.6  直视移动的方向 179
3.9.7  漫游 179
3.9.8  假旋转轴 181
3.10  习题 185
第4章　路径发现 189
4.1  路径发现图形 190
4.1.1  图形 190
4.1.2  加权图形 191
4.1.3  有向加权图形 194
4.1.4  术语 195
4.1.5  表示方式 195
4.2  迪杰斯特拉算法 196
4.2.1  问题 197
4.2.2  算法 198
4.2.3  伪代码 202
4.2.4  数据结构和接口 205
4.2.5  迪杰斯特拉算法的性能 206
4.2.6  弱点 207
4.3　A*算法 208
4.3.1  问题 208
4.3.2  算法 208
4.3.3  伪代码 212
4.3.4  数据结构和接口 216
4.3.5  实现说明 220
4.3.6  算法性能 220
4.3.7  节点数组A*算法 221
4.3.8  选择启发式算法 223
4.4  游戏世界的表示方式 230
4.4.1  图块图形 232
4.4.2  狄利克雷域 234
4.4.3  可见性点 236
4.4.4  导航网格 238
4.4.5  非平移问题 242
4.4.6  成本函数 243
4.4.7  路径平滑 244
4.5  改进A*算法 246
4.6  分层路径发现技术 247
4.6.1  分层路径发现图形 248
4.6.2  分层图形上的路径发现 251
4.6.3  基于排除法的分层路径发现技术 254
4.6.4  分层结构对路径发现的奇怪影响 255
4.6.5  实例几何 257
4.7  路径发现中的其他思路 263
4.7.1  开放目标路径发现 263
4.7.2  动态路径发现 263
4.7.3  其他类型的信息重用 264
4.7.4  低内存算法 265
4.7.5  可中断路径发现 266
4.7.6  汇集路径规划请求 266
4.8  连续时间路径发现 267
4.8.1  问题 268
4.8.2  算法 269
4.8.3  实现说明 272
4.8.4  性能 273
4.8.5  弱点 273
4.9  关于移动路径规划 273
4.9.1  动作 274
4.9.2  移动路径规划 275
4.9.3  示例 276
4.9.4  脚步规划 278
4.10  习题 278
第5章　决策 283
5.1  决策概述 283
5.2  决策树 284
5.2.1  问题 285
5.2.2  算法 285
5.2.3  伪代码 290
5.2.4  知识的表示方式 292
5.2.5  实现节点 292
5.2.6  决策树的性能 293
5.2.7  平衡决策树 293
5.2.8  超越决策树 294
5.2.9  随机决策树 295
5.3  状态机 297
5.3.1  问题 299
5.3.2  算法 299
5.3.3  伪代码 300
5.3.4  数据结构和接口 301
5.3.5  性能 303
5.3.6  实现说明 303
5.3.7  硬编码的FSM 304
5.3.8  分层状态机 306
5.3.9  组合决策树和状态机 319
5.4  行为树 321
5.4.1  实现行为树 328
5.4.2  伪代码 328
5.4.3  装饰器 332
5.4.4　并发和计时 338
5.4.5  向行为树添加数据 347
5.4.6  重用行为树 351
5.4.7  行为树的局限性 356
5.5  模糊逻辑 357
5.5.1  讨论之前的重要说明 358
5.5.2  模糊逻辑简介 358
5.5.3  模糊逻辑决策 367
5.5.4  模糊状态机 376
5.6  马尔可夫系统 381
5.6.1  马尔可夫过程 382
5.6.2  马尔可夫状态机 384
5.7  面向目标的行为 386
5.7.1  面向目标的行为概述 387
5.7.2  简单选择 389
5.7.3  整体效用 391
5.7.4  计时 394
5.7.5  整体效用GOAP 398
5.7.6  使用IDA*的GOAP 403
5.7.7  “散发气味”的GOB 411
5.8  基于规则的系统 413
5.8.1  问题 413
5.8.2  算法 418
5.8.3  伪代码 419
5.8.4  数据结构和接口 419
5.8.5  规则仲裁 425
5.8.6  统一 428
5.8.7  Rete算法 430
5.8.8  扩展 439
5.8.9  发展前瞻 443
5.9  黑板架构 443
5.9.1  问题 443
5.9.2  算法 444
5.9.3  伪代码 445
5.9.4  数据结构和接口 446
5.9.5  性能 449
5.9.6  其他的黑板系统 449
5.10  动作执行 450
5.10.1  动作的类型 450
5.10.2  算法 455
5.10.3  伪代码 456
5.10.4  数据结构和接口 457
5.10.5  实现说明 459
5.10.6  性能 460
5.10.7  综述 460
5.11  练习 461
第6章　战略和战术AI 465
6.1  航点战术 466
6.1.1  战术位置 466
6.1.2  使用战术位置 474
6.1.3  生成航点的战术属性 479
6.1.4  自动生成航点 484
6.1.5  简化算法 485
6.2  战术分析 489
6.2.1  表示游戏关卡 489
6.2.2  简单的影响地图 490
6.2.3  地形分析 496
6.2.4  用战术分析学习 498
6.2.5  战术分析的结构 500
6.2.6  关于地图覆盖 504
6.2.7  卷积滤镜 509
6.2.8  细胞自动机 518
6.3  战术性路径发现 524
6.3.1  成本函数 524
6.3.2  战术权重和关注事项的混合 525
6.3.3  修改路径发现启发式算法 527
6.3.4  路径发现的战术图形 528
6.3.5  使用战术航点 528
6.4  协调动作 529
6.4.1  多层AI 530
6.4.2  自发合作 536
6.4.3  编写群体动作的脚本 538
6.4.4  军事战术 543
6.5  习题 545
第7章　学习 549
7.1  关于机器学习的基础知识 549
7.1.1  在线或离线学习 549
7.1.2  行为内学习 550
7.1.3  行为间学习 551
7.1.4  对机器学习应用的警告 551
7.1.5  过度学习 552
7.1.6  混杂的学习算法 552
7.1.7  工作量的平衡 552
7.2  参数修改 553
7.2.1  参数地形 553
7.2.2  爬山算法 555
7.2.3  基本爬山算法的扩展 558
7.2.4  退火技术 561
7.3  动作预测 565
7.3.1  左还是右 565
7.3.2  原始概率 566
7.3.3  字符串匹配 566
7.3.4  N-Gram预测器 567
7.3.5  窗口大小 570
7.3.6  分层N-Gram 572
7.3.7  在格斗游戏中的应用 575
7.4  决策学习 575
7.4.1  决策学习的结构 575
7.4.2  应该学习的东西 576
7.4.3  4种技术 576
7.5  朴素贝叶斯分类算法 577
7.5.1  伪代码 580
7.5.2  实现说明 582
7.6  决策树学习 582
7.6.1  ID3 583
7.6.2  具有连续属性的ID3 590
7.6.3  增量决策树学习 595
7.7  强化学习 599
7.7.1  问题 599
7.7.2  算法 600
7.7.3  伪代码 603
7.7.4  数据结构和接口 604
7.7.5  实现说明 605
7.7.6  性能 605
7.7.7  适应性调整参数 605
7.7.8  弱点和现实应用 609
7.7.9  强化学习中的其他思路 611
7.8  人工神经网络 613
7.8.1  概述 615
7.8.2  问题 617
7.8.3  算法 618
7.8.4  伪代码 622
7.8.5  数据结构和接口 624
7.8.6  实现警告 626
7.8.7  性能 626
7.8.8  其他方法 626
7.9  深度学习 630
7.9.1  深度学习的定义 631
7.9.2  数据 632
7.10  习题 634
第8章  程序化内容生成 639
8.1  伪随机数 641
8.1.1  数值混合和游戏种子 641
8.1.2  霍尔顿序列 643
8.1.3  叶序的角度 646
8.1.4  泊松圆盘 647
8.2  Lindenmayer系统 651
8.2.1  简单的L系统 651
8.2.2  将随机性添加到L系统 655
8.2.3  特定阶段的规则 657
8.3  地形生成 659
8.3.1  修饰器和高度图 659
8.3.2  噪声 660
8.3.3  佩林噪声 661
8.3.4  断层 664
8.3.5  热侵蚀 666
8.3.6  水力侵蚀 667
8.3.7  高地过滤 672
8.4  地下城与迷宫的生成 676
8.4.1  深度优先的回溯迷宫 677
8.4.2  小生成树算法 687
8.4.3  递归细分 692
8.4.4  生成和测试 696
8.5  形状语法 697
8.5.1  运行语法 700
8.5.2  规划 703
8.6  练习 707
第9章　棋盘游戏 709
9.1  博弈论 710
9.1.1  游戏类型 710
9.1.2  博弈树 712
9.2  极小极大化算法 714
9.2.1  静态评估函数 714
9.2.2  关于极小极大化 716
9.2.3  使用极小极大化算法 717
9.2.4  负值化算法 720
9.2.5  AB修剪 722
9.2.6  AB搜索窗口 726
9.2.7  负值侦察 727
9.3  置换表和内存 730
9.3.1  哈希游戏状态 731
9.3.2  哈希表中存储的内容 733
9.3.3  哈希表实现 734
9.3.4  替换策略 736
9.3.5  完整的置换表 736
9.3.6  置换表的问题 737
9.3.7  使用对手的思考时间 738
9.4  内存增强型测试算法 738
9.4.1  实现测试 738
9.4.2  MTD算法 740
9.4.3  伪代码 742
9.5  蒙特卡洛树搜索 743
9.5.1  纯蒙特卡洛树搜索 743
9.5.2  添加知识 748
9.6  开局库和其他固定进攻战术 750
9.6.1  实现开局库 750
9.6.2  学习开局库 751
9.6.3  固定进攻战术库 751
9.7  进一步优化 752
9.7.1  迭代加深 752
9.7.2  可变深度算法 753
9.8  游戏知识 755
9.8.1  创建静态评估函数 757
9.8.2  学习静态评估函数 760
9.9  回合制策略游戏 764
9.9.1  不可能的树大小 764
9.9.2  回合制游戏中的实时AI 765
9.10  习题 766
第3部分  支 持 技 术
第10章　执行管理 769
10.1  调度 769
10.1.1  调度程序 770
10.1.2  可中断进程 776
10.1.3  负载平衡调度程序 779
10.1.4  分层调度 781
10.1.5  优先级调度 782
10.2  随时算法 785
10.3  细节层次 786
10.3.1  图形细节层次 786
10.3.2  关于AI中的细节层次技术 787
10.3.3  调度细节层次 788
10.3.4  行为细节层次 789
10.3.5  群体细节层次 794
10.3.6  总结 797
10.4  习题 797
第11章　世界接口 799
11.1  通信 799
11.1.1  轮询 800
11.1.2  事件 800
11.1.3  确定使用的方法 801
11.2  事件管理器 802
11.2.1  实现 804
11.2.2  事件播送 807
11.2.3  代理间通信 809
11.3  轮询站点 809
11.3.1  伪代码 810
11.3.2  性能 811
11.3.3  实现说明 811
11.3.4  抽象轮询 811
11.4  感知管理 813
11.4.1  模拟才是王道 813
11.4.2  内部知识和外部知识 814
11.4.3  感知形态 815
11.4.4  区域感知管理器 820
11.4.5  有限元模型感知管理器 828
11.5  习题 835
第12章　工具和内容创建 837
12.1  关于工具链 837
12.1.1  工具链限制AI 837
12.1.2  AI知识的来源 838
12.2  路径发现和航点战术的知识 838
12.2.1  手动创建区域数据 839
12.2.2  自动图形创建 841
12.2.3  几何分析 841
12.2.4  数据挖掘 844
12.3  关于移动的知识 847
12.3.1  障碍问题 847
12.3.2  高级调度 848
12.4  关于决策的知识 849
12.4.1  对象类型 849
12.4.2  具体动作 849
12.5  工具链 850
12.5.1  集成游戏引擎 851
12.5.2  自定义数据驱动的编辑器 853
12.5.3  AI设计工具 854
12.5.4  远程调试 855
12.5.5  插件 856
12.6  习题 857
第13章  游戏AI编程 859
13.1  实现语言 860
13.1.1  C 861
13.1.2  C# 861
13.1.3  Swift 863
13.1.4  Java 864
13.1.5  JavaScript 865
13.2  脚本AI 867
13.2.1  脚本AI的定义 869
13.2.2  优秀脚本语言的基本要件 869
13.2.3  嵌入 871
13.2.4  选择开源语言 871
13.2.5  语言选择 872
13.3  创建语言 877
13.3.1  优点 878
13.3.2  缺点 878
13.3.3  创建自定义语言的实际操作 879
13.3.4  工具：Lex和Yacc简介 883
第4部分  设计游戏AI
第14章　游戏AI设计 887
14.1  设计 887
14.1.1  示例 888
14.1.2  评估行为 889
14.1.3  选择技术 891
14.1.4  一款游戏的范围 893
14.2  射击类游戏 894
14.2.1  移动和射击 895
14.2.2  决策 897
14.2.3  感知 898
14.2.4  路径发现和战术AI 899
14.2.5  射击类风格游戏 900
14.2.6  近战格斗类游戏 901
14.3  驾驶类游戏 904
14.3.1  移动 905
14.3.2  路径发现和战术AI 906
14.3.3  类驾驶游戏 907
14.4  即时战略类游戏 907
14.4.1  路径发现 908
14.4.2  群体移动 909
14.4.3  战术和战略AI 909
14.4.4  决策 910
14.4.5  MOBA 911
14.5  体育类游戏 912
14.5.1  物理预测 913
14.5.2  战术套路库和内容创建 914
14.6  回合制战略游戏 914
14.6.1  计时 915
14.6.2  帮助玩家 916
第15章　基于AI的游戏类型 917
15.1  游戏角色教学 917
15.1.1  表示动作 918
15.1.2  表示游戏世界 918
15.1.3  学习机制 919
15.1.4  可预测的心理模型和病理状态 921
15.2  蜂拥算法和放牧游戏 922
15.2.1  制造生物 922
15.2.2  为交互调整转向行为 923
15.2.3  转向行为的稳定性 924
15.2.4  生态系统设计 925
附    录
参考资料 929
A.1  图书、期刊、论文和网站 929
A.2  游戏 934

    2017年5月，在中国乌镇围棋峰会上，由谷歌（Google）旗下DeepMind公司戴密斯·哈萨比斯领衔的团队开发的围棋AI（Artificial Intelligence，人工智能）程序AlphaGo与当时世界排名的中国棋手柯洁对战，并以3比0的总比分完胜。至此，围棋AI的棋力超越人类围棋的水平成为不争的事实。
    实际上，AI创造的辉煌并不是从那一天开始的。1997年，IBM的深蓝计算机首次战胜国际象棋棋王卡斯帕罗夫也同样成为佳话。2014年10月，浪潮天梭击败了5位中国象棋特级大师。从那时起，普通玩家使用家用个人计算机，通过象棋软件击败国家特级大师已不是什么新鲜事，目前的中国象棋人王天一就经常在与普通“棋友”的直播对弈中折戟沉沙。
    象棋游戏AI的设计依赖于极小极大化算法、AB修剪、负值侦察、置换表和开局库等技术，本书第8章对此有详细介绍。象棋很早就被计算机AI攻克，因为它的变化相对围棋而言较少，并且有大量的棋谱可用，而围棋的状态空间复杂度是10172，博弈树复杂度是10300，曾经被认为是计算机AI无法翻越的高山。但是，凭借着机器学习和神经网络的利器，计算机AI实现了历史性的突破。本书第7章介绍了机器学习技术。
    除了在棋盘游戏中发威，AI技术在其他类型的游戏中也给玩家留下了深刻的印象，例如，有限状态机、路径发现（这是“寻路术”技术的代名词，本书第3章有详细介绍）、转向行为、自动编队、行为树决策、模糊逻辑决策、航点和战术分析等。这些技术都关联着大量算法，本书对这些算法都进行了详细的分析，并提供了伪代码（方便开发人员在不同的编程语言中实现）、实现说明和性能分析等。
    此外，本书还提供了许多技术和算法在游戏中的应用思路，包括在游戏中实现AI的中间件思想、执行管理和调度方法、游戏世界的表示方式和接口、工具链创建和脚本的开发、各种游戏类型及其AI实现技巧等。这些内容可以为开发人员实现自己的游戏AI提供很好的启发。
    为了更好地帮助读者理解和学习，本书以中英文对照的形式保留了大量的术语，这样的安排不但方便读者理解书中的伪代码，而且有助于读者查找和利用网络资源。