本文内容包含以下章节：

Chapter 2 AI Methods

Chapter 2.1 General Notes

本书英文版： Artificial Intelligence and Games - A Springer Textbook

这个章节主要讨论了在游戏中经常用到的一些基础的人工智能算法。这些算法大部分都出现在一些人工智能和机器学习的入门书籍中。在讲解算法在游戏中的应用的时候，会以吃豆人（Ms Pac-Man)作为样例，讲解怎么用行为树算法，树搜索算法，监督学习算法，无监督学习算法，强化学习算法和进化算法来构建一个玩游戏的AI。

吃豆人

一. AI算法的基本要素

这些AI算法虽然形态各有不同，但是本质上都是基于两个基本的要素来做文章。一个是算法的表示(Representation), 另外一个是效用(Utility)。

首先是怎么把学到的玩游戏的知识用某种数据结构来表示出来。这个数据结构也是和要用的算法强相关的。比如如果用文法演化算法(Grammatical Evolution），最后学到的就是一些文法（Grammars）；如果用概率模型或者有限状态机，最后知识就表示成一个图(Graphs)；而行为树和决策树还有遗传算法会学到一颗树(Trees)，神经网络自然是联结主义的(Connectionism）, 遗传算法和演化策略会带来一些基因编码(Genetic Representation), 而TD-learning 和 Q-learning则学到了一下状态转移的表格(Tabular)。

当然，寻找一个最优的算法表示通常是很难的，并且世界上没有免费的午餐，算法之间总是各有利弊的。不过一般来说，我们希望选择的算法的表示尽可能的简单，和占用更小的空间。而我们需要有一些先验知识来找到一个较好的算法表示。

另外一方面，我们会用效用（Utility)这个来自博弈论的术语来指导算法的训练。不严格的来说，可以把它看做一个函数，输入是当前状态和算法可能的动作(Action)，输出是算法做出某个动作所能够获得的好处。理论上来说，如果我们能得到一个准备的Utility Function, 我们的算法每次都可以找到最优的路径。但实际上，我们只能够得到一个估计值，或者更确切的，在没有先验知识的情况下，我们只能通过记住我们探索过的状态和路径及其获得的回报来估算一个效用值来表示某个走法的好坏(Measure of Goodness)。如果游戏本身的状态空间比较小，我们可以通过遍历所有的可能情况来得到一个准备的Utility Function。而通常我们面对的问题都有着极大的搜索空间，因此我们希望能够尽可能的探索到更多的路径，然后在探索到的数据上进行采样来得到一个估计的Utility。

Utility 在不同的算法上的叫法会有所不同，在含义上也有细微的差别。例如在一些树搜索算法上，我们会用启发式的规则(Heuristic)来指导算法的收敛。而在遗传算法上，它又被叫做适应度函数(Fitting Function)。在优化算法上，我们更常用的词语是Loss, Error, Cost； 而在强化学习，Reward是一个更常用的单词，这里最主要的原因是：做RL的人由于整天面对着逆天难的问题，所以喜欢用reward(相对于loss)来激励自己。（大雾）