.游戏编程中的人工智能技术
. (连载之10)
..
这是《遗传算法入门》连载的最后一篇，将对连载来源进行一些说明。
0.本连载来自《游戏编程中的人工智能技术》一书，是该书第三章一章的基本上完整的内容。
1.全书介绍遗传算法(GA)和神经网络(NN)等人工智能技术的原理，以及它们在游戏编程中的应用。
2.<游戏编程中的人工智能技术> 目录(这是我交给出版社的原始手稿目录)如下
译者序 ………………………………………………………………………………… i 前言 ……………………………………………………………………………………vi 致谢 ……………………………………………………………………………………ix 关于作者 ………………………………………………………………………………ix 目录 ……………………………………………………………………………………xi 丛书编辑者的来信 ……………………………………………………………………xx 引言 …………………………………………………………………………………xxii
第一部分 Windows编程
第1章 Windows编程初步 ………………………………………………………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 9.5 …………………………………………………………………4 1.1.5 Windows 9.8.及其后续版本 ……………………………………………… 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
第二部分 遗传算法
第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 4.6 把一切组装在一起 …………………………………………………………… 119 4.6.1 #defines文件 …………………………………………………………… 120 4.7 总结 …………………………………………………………………………… 121 4.8 练习 …………………………………………………………………………… 122
第5章 遗传算法优化 ………………………………………………………… 123
5.1 TSP用的各种算子……………………………………………………………… 124 5.1.1 各种置换变异算子…………………………………………………………124 5.1.1.2 移位变异(Displacement Mutation，DM)………………………… 127 5.1.1.3 插入变异 (Insertion Mutation，IM) ……………………………128 5.1.1.4 倒置变异 (Inversion Mutation，IVM) ………………………… 129 5.1.1.5 倒置移位变异(Displaced Inversion Mutation，DIM)………… 129 5.1.2 各种置换杂交算子 ……………………………………………………… 130 5.1.2.1 基于顺序的杂交(Order-Based Crossover，OBX)…………………130 5.1.2.2 基于位置的杂交(Position-Based Crossover，PBX)…………… 133 5.2 各种处理工具 ………………………………………………………………… 136 5.2.1 选择(Selection)技术 ……………………………………………………137 5.2.1.1 精英选择(Elitism)………………………………………………… 138 5.2.1.2 稳态选择(Steady State Selection)………………………………138 5.2.1.3 适应性比例选择(Fitness Proportionate Selection)………… 138 5.2.1.4 赌轮选择(Roulette Wheel Selection)……………………………138 5.2.1.5 随机遍及取样(Stochastic Universal Sampling)……………… 139 5.2.1.6 锦标赛选择(Tournament Selection)………………………………140 5.2.2 变比技术(Scaling Techniques)…………………………………………142 5.2.2.1 排名变比(Rank Scaling)……………………………………………142 5.2.2.2 西格玛变比(Sigma Scaling)……………………………………… 143 5.2.2.3 波兹曼变比(Boltzmann Scaling)………………………………… 146 5.2.3 其它杂交算子 …………………………………………………………… 147 5.2.3.1 单点杂交(Single-Point Crossover)………………………………147 5.2.3.2 两点杂交(Two-Point Crossover)………………………………… 147 5.2.3.3 多点杂交(Multi-Point Crossover)……………………………… 148 5.2.4 子群技术(Niching Techniques)…………………………………………150 5.3 总结 …………………………………………………………………………… 151 5.4 练习 …………………………………………………………………………… 151
第6章 登月也不难………………………………………………………………152
6.1 创建和处理矢量图形 ………………………………………………………… 153 6.1.1 顶点和顶点缓冲 ………………………………………………………… 153 6.1.2 顶点变换 ………………………………………………………………… 155 6.1.2.1 平移(Translation)………………………………………………… 156 6.1.2.2 变比(Scaling)……………………………………………………… 157 6.1.2.3 旋转(Rotation)………………………………………………………157 6.1.2.4 综合运用 …………………………………………………………… 159 6.1.3 矩阵魔法(Matrix Magic)…………………………………………………161 6.1.3.1 矩阵究竟是什么？……………………………………………………161 6.1.3.2 矩阵的乘法 ………………………………………………………… 162 6.1.3.3 单位矩阵 …………………………………………………………… 163 6.1.3.4 用矩阵变换顶点 …………………………………………………… 163 6.1.3.5 奇妙部分来了 ……………………………………………………… 165 6.2 矢量是什么？……………………………………………………………………166 6.2.1 矢量加、减法 …………………………………………………………… 168 6.2.2 计算矢量大小 …………………………………………………………… 169 6.2.3 矢量的数量乘 …………………………………………………………… 170 6.2.5 矢量的分解(投影)…………………………………………………………171 6.2.6 奇妙的点积(Dot Product)……………………………………………… 172 6.2.7 SVector2.D实用工具类 ………………………………………………… 173 6.3 绝顶聪明的牛顿 ……………………………………………………………… 173 6.3.1 时间(Time)…………………………………………………………………174 6.3.2 长度(Length)………………………………………………………………175 6.3.3 质量(Mass)…………………………………………………………………175 6.3.4 力(Force)………………………………………………………………… 176 6.3.5 运动－速度(Velocity)……………………………………………………177 6.3.6 运动－加速度(Acceleration)……………………………………………178 6.3.7 感觉到了力，真快活 …………………………………………………… 180 6.3.8 引力(Gravity)…………………………………………………………… 180 6.4 登月工程－人控制的 ………………………………………………………… 181 6.4.1 Ccontroller类的定义 ……………………………………………………182 6.4.2 CLander类的定义 …………………………………………………………183 6.4.3 UpdateShip函数 ………………………………………………………… 185 6.5 遗传算法控制的登月艇 ……………………………………………………… 191 6.5.1 为基因组编码 …………………………………………………………… 191 6.5.2 杂交和变异操作 ………………………………………………………… 193 6.5.3 适应性函数(Fitness Function)…………………………………………194 6.5.4 更新函数(Update Function)…………………………………………… 196 6.5.5 运行程序 ………………………………………………………………… 199 6.6 小结 …………………………………………………………………………… 199 6.7 习题 …………………………………………………………………………… 199
第三部分 神经网络
第7章 用平常语言讲神经网络…………………………………………………202
7.1 神经网络介绍……………………………………………………………………202 7.2 一个生物学的神经网络-大脑 …………………………………………………203 7.3 数字版的神经网络 …………………………………………………………… 206 7.3.1 现在需要一些数学了 …………………………………………………… 208 7.3.2 我知道什么是神经细胞了，但用它来干什么呢？………………………210 7.4 聪明的扫雷机工程 …………………………………………………………… 212 7.4.1 选择输出 ………………………………………………………………… 213 7.4.2 选择输入 ………………………………………………………………… 215 7.4.3 隐藏的神经细胞要多少？…………………………………………………216 7.4.4 CNeuralNeth文件 …………………………………………………………217 7.4.4.1 SNeuron结构 ……………………………………………………… 217 7.4.4.2 SNeuronLayer结构 ………………………………………………… 219 7.4.4.3 CNeuralNet类 ……………………………………………………… 219 7.4.5 神经网络的编码 ………………………………………………………… 224 7.4.6 遗传算法 ………………………………………………………………… 225 7.4.7 扫雷机类(CMinesweeper Class)…………………………………………226 7.4.7.1 CMinesweeper::Update函数 ……………………………………… 228 7.4.8 CController类 ……………………………………………………………230 7.4.8.1 CController::Update方法 ……………………………………………233 7.4.9 运行此程序 ……………………………………………………………… 235 7.4.1.0 功能的两个改进 …………………………………………………… 236 7.4.1.1 改进一 ……………………………………………………………… 236 7.4.1.2 改进二 ……………………………………………………………… 239 7.5 最后说几句 …………………………………………………………………… 241 7.6 练习题 ………………………………………………………………………… 241
第8章 为你的Bot提供知觉器 …………………………………………………242
8.1 回避障碍物 …………………………………………………………………… 243 8.1.1 认识环境 ………………………………………………………………… 243 8.1.2 适应性函数 ……………………………………………………………… 246 8.2 为您的Bot提供一个记忆器(memory)………………………………………… 248 8.2.1 适应性函数 ……………………………………………………………… 255 8.3 本章小结 …………………………………………………………………… 256 8.4 练习题 ……………………………………………………………………… 257
第9章 有监督的训练方法 …………………………………………………… 258
9.1 异或函数(XOR Function)………………………………………………………258 9.1.1 反向传播(BP)怎么工作？…………………………………………………259 9.1.1.1 调整输出层的权重 ………………………………………………… 261 9.1.1.2 为隐藏层调整权重 ………………………………………………… 262 9.1.1.3 一个例子 …………………………………………………………… 262 9.1.1.4 改变成CNeuralNet代码 …………………………………………… 265 9.2 RecognizeIt - 鼠标手势的识别 ……………………………………………270 9.2.1 用向量来表示一个手势 ………………………………………………… 271 9.2.2 训练网络(Training the Network)………………………………………273 9.2.3 记录并变换鼠标数据 …………………………………………………… 275 9.2.4 增加新的手势 …………………………………………………………… 277 9.2.5 CController类 ……………………………………………………………278 9.3 一些有用的技术和窍门 ……………………………………………………… 281 9.3.1 增加动量(Momentum)………………………………………………………281 9.3.2 过拟合(Over Fitting)……………………………………………………282 9.3.3 柔性最大激励函数 ……………………………………………………… 284 9.4 监督学习的应用 ……………………………………………………………… 285 9.5 一个现代寓言 ………………………………………………………………… 286 9.6 练习题 ………………………………………………………………………… 287
第10 章 实时演化 …………………………………………………………… 288
10.1 聪明的外星人(Brainy Aliens)………………………………………………288 10.1.1 程序实现 …………………………………………………………………290 10.1.1.1 Roswell再现了：外星人大脑的尸体解剖 ……………………… 290 10.1.1.2 外星人的演化 ………………………………………………………295 10.1.1.3 CController::Update方法 ………………………………………… 299 10.1.2 运行Brainy Aliens程序 ………………………………………………… 301 10.2 练习题………………………………………………………………………… 302
第11章 神经网络拓扑结构的演化 ……………………………………………303
11.1 竞争约定(competing convention)问题 ……………………………………304 11.2 直接编码 ………………………………………………………………………305 11.2.1 GENITOR(基因子)…………………………………………………………305 11.2.2 二进制矩阵编码 …………………………………………………………306 11.2.2.1 几个相关问题 ………………………………………………………307 11.2.3 基于节点的编码 …………………………………………………………308 11.2.4 基于路径的编码 …………………………………………………………311 11.3 间接编码 ………………………………………………………………………311 11.3.1 基于文法的编码 …………………………………………………………312 11.3.2 二维生长编码 ……………………………………………………………313 11.4 NEAT(拓扑扩张的神经演化)………………………………………………… 314 11.4.1 NEAT基因组 ………………………………………………………………315 11.4.1.1 SLinkGene结构 …………………………………………………… 315 11.4.1.2 SNeuronGene结构 ………………………………………………… 317 11.4.1.3 CGenome类……………………………………………………………319 11.4.2 算子和创新(Operators and Innovations)………………………………322 11.4.2.1 CGenome::AddLink方法 ……………………………………………324 11.4.2.2 CGenome::AddNeuron方法 …………………………………………329 11.4.2.3 创新怎样帮助我们设计一个有效的杂交操作 ……………………336 11.4.3 物种形成(Speciation)………………………………………………… 341 11.4.3.1 兼容性测试 …………………………………………………………342 11.4.3.2 CSpecies 类…………………………………………………………345 11.4.4 Cga换时代方法(Cga Epoch Method) ………………………………… 348 11.4.5 将基因组转变为表现型 …………………………………………………354 11.4.5.1 SLink结构……………………………………………………………355 11.4.5.2 SNeuron结构…………………………………………………………355 11.4.5.3 把所有东西组合在一起…………………………………………… 357 11.4.5.4 CNeuralNet类……………………………………………………… 358 11.4.6 运行Demo程序 ……………………………………………………………363 11.5 本章小结 ……………………………………………… …………………… 364 11.6 练习题………………………………………………………………………… 365
第四部分 附录
附录A WEB资源 …………………………………………………………………367
A1 相关的URL地址 ……………………………………………………………… 367 A2 新闻组 …………………………………………………………………………368
附录B 参考书目及推荐读物 ………………………………………………… 369
B1 技术书 …………………………………………………………………………369 B2 论文 ……………………………………………………………………………370 B3 能激发思想的书 ………………………………………………………………371 B4 好得见血的科幻小说！……………………………………………………… 372
附录C 光盘上有些什么？……………………………………………………………373
技术支持 …………………………………………………………………………… 374
后记 ………………………………………………………………………………… 375
索引 ………………………………………………………………………………… 376
3.该书是英文《AI Techniques for Game Programming》的翻译，原书在Internet上可以找到很多好评，是目前国外、国内许多游戏学校或培训班的指定教材。其特点就是浅近易懂，且提供大量实际例子，也写得生动活泼，被认为是人工智能难得的好书，是一本指南性读物。
4.本书中文由沙鹰和我翻译，连载的那一章由本人翻译。同时也欢迎大家引用，大家可以放心。
5.本书现在已交清华大学出版社出版。这里的第三章是较早翻译并较早（2005年）贴出来的，系未经出版社审校的原始译文。出版时有过一些错误更正，但也不可避免会引入一些新的差错（最终出版时有不少删改，未经本人校对，十分遗憾！）。如果发现问题，请对照检查。
6.本连载所介绍内容的完整的VC++源程序和执行程序请到下面下载：
www.zzwu.cn/ai/AIch03.rar
谢谢各位读者提出的问题，我已作了更正，插图也已经都有了。 欢迎各位和其他网友继续批评指正！
预 告
游戏编程中的人工智能技术
<神经网络入门>连载 即将开始 。 (共６篇)
1：生物学的神经网络-大脑介绍
2：数字版的神经网络
3：聪明的扫雷机工程
4：CNeuralNet.h等代码
5：神经网络的编码及遗传算法
6：功能的两个改进
