Abstract: 本文介绍强化学习的一个具体例子，Tic-Tac-Toe，作为一种下棋类游戏，Tic-Tac-Toe规则简单，而且问题规模小，容易进行深入分析，了解强化学习在具体例子中的执行过程，进而了解强化学习的性质和特点。
Keywords: 强化学习，强化学习举例，Tic-Tac-Toe
强化学习的一个扩展举例
今天我们来讲一个很有趣的例子，英文名字叫”Tic-Tac-Toe” 中文名字有翻译成“井字棋”或者什么的，我们这里为了方便就称之为“井字棋”，叫井字棋的原因是因为其棋盘是个“井”字形的，玩法简单，但是这个玩的过程可以使用强化学习的方法来学习，这个简单的棋可以让我们从各个细节审视强化学习的特点，有点，缺点，以及一些小技巧。
“Tic-Tac-Toe”简介
规则描述
Tic-Tac-Toe的规则描述如下：
- 使用 $3\times 3$ 的正方形棋盘，双方各使用 ‘x’和’o’ 作为棋子，轮流下棋，
- 谁的棋子最先连成一行或者一列，或者对角线，那么获胜，棋局结束
- 对方完成这个过程，则失败
- 如果在最终双方都没能连成一行或者一列，或者对角线的情况下，棋局结束，则为平局。
下图来自Wikipedia:“井字棋”
上面的棋局，使用 ‘x’ 的一方率先完成连成一行的准则，故执’x’一方获胜。
简单规则下的问题
下面这个视频是我在Google上找到的一个小程序录的一段视频。
可见，在高级的情况下，双方（我和AI）基本都没法获胜，也就是平局会大量出现，原因是，我们对这种棋的技巧掌握的都很熟练，无法在现行环境（规则）下战胜对方，通过这个观察我们也能发现，在规则相对简单的游戏（“博弈”）中，平局会大量出现。
那么问题就要来了，我们 - 也就是人，在这种简单的规则下，多以平局收场，那么这怎么训练agent呢？如果每局训练总是平局，agent就不知道往什么方向走了。这里我们就要做出一些修改，我们让与我们agent下棋的人或者另一个agent不那么高级，换句话说，我们在简单规则下，降低规则执行者的能力，进而模拟出更高级的博弈（所谓更高级的博弈，无非是我们能力不足才会觉得当前环境，或者规则很困难）。
在后面的训练里，agent会将平局和失败都当做失败来处理，agent的目标明确，就是胜利。
非强化学习型的解决方法
这个棋局太简单，但是在如此简单的规则下，传统方法（非学习方法）都有诸多问题：
- 使用传统的“极大极小化”（minimax）方法，这个方法会假定对方按照某个既定方案下棋，而事实是对方可能无既定方案，或者既定方案我们永远无法得知。所以这个传统的博弈思想在此不适用。而且“极大极小化”（minimax）方法有个非常大的缺点：如果其认定当前状态必然失败的情况下，即使后面对手出现重大失误（可以逆转取胜的机会），其也不会采取任何致胜招数，而是按照既定失败的套路继续下去。
- 对于这种连续决策型问题的传统的优化方法，例如动态规划(dynamic programming)，可以计算出在对阵任何对手时候的最优解，但是前提是：对手的全部信息要作为输入提前提交给算法，其中包括在某特定情况（棋局）下，对手下一步棋下在哪的概率。如果我们提前不知道这些信息（大部分情况下，这个信息无法获得）
- 对于2中的动态规划方法，有另一种改进版就是在训练时和对手多次交手，从而记录学习出对手的信息，或者叫做给对手建模（model）然后再使用动态规划来寻找答案。
上面3中方法中，1和2对解决问题基本没有帮助，3有帮助。3和我们后面会介绍的很多强化学习方法有着非常相似的思路。
进化方法(Evolutionary Method)学习 “Tic-Tac-Toe”
进化方法 中讲解了进化方法的缺点，就是没有使用agent和环境之间的交互信息来改变agent。而这里如果把进化方法直接使用到“井字棋”中，其表策略（policy）的特点是：直接search全部可能的位置，找到获胜概率最大的位置，然后下棋。也就是，策略要考虑到当前盘面（ $3\times 3$ 的棋盘上 x和o的分布）并给出获胜概率最大的下棋位置。而这个概率的获得就需要和对手多次下棋，记录，学习出来的。有了这些信息，agent就知道接下来一步或者接下来很多步应该怎么走。
一个典型的进化方法就是在“策略空间”的 hill-climb ，这种方法的策略是逐渐找出能提高表现的策略（并不是一下找到最优的方法，而是像爬山一样，每一步都找到一个能提高agent表现的方案，一步一步的向上爬）。
遗传方法就更加直接暴力了，直接直接评估大量的策略(policies)，去除不合格的，留下好的，然后产生新一代的，以此迭代，直到问题解决。
解决“井字棋”问题，理论上存在很多种不同的优化方法。
评价函数(Value Function)学习 “Tic-Tac-Toe”
上面我们说了进化方法在井字棋中使用，下面我们就要看看另一个方向的方法 —— 评价函数(value Function)的方法了。
设计评价函数
我们列一个表，这个表中的每个格子对应一种状态（state），整张表就对应井字棋的全部情况，这个表的每一项都对应一个概率值，这个概率值表示当前状态下最后获胜的期望，注意两点，一个是当前的状态，第二是最终获胜的期望。这个期望，我们就把其当做评价函数的结果，value —— value值。这个表就是我们的评价函数(Value Function)了.
在井字棋中，这个表就包含下一步棋应该怎么走的评估。通过当前状态，我们可以缩小下一步可能出现的状态范围，然后比较所有可能的状态，如果A状态比B状态有更高的获胜期望，那么我们认为A状态比B状态好，所以我们倾向于把棋子走到A状态显示的位置。
对于这个状态表，假设我们执x，那么如果某状态中包含x在一行或者一列或者对角线，那么这个状态的获胜期望是1，相反，如果o在一行或者一列或者对角线，那么这个状态的获胜期望是0；同样，如果对应状态是棋盘下满，而没有获胜方，这时候期望同样是0 。除了上述这些情况，其他状态的初始化值都是0.5，即有一半的可能性会获胜。
执行(exploitation)和探索(exploration)
当我们有了这张表（上面的评价函数）我们就有了制胜法宝，但是具体执行也是有不同方案的，我们可以查找最大value的状态，然后执行贪心(greedily)选择，这是使得获胜期望最大的策略，也就是完全执行表（value function）中的指示，这个被称为exploitation。
但是我们有时候（偶尔，occasionally）在某些步骤中不选择最大value的状态，而是选择随机状态，因为这种方式可能带我们到一个前所未见的state下。
上面两段描述的评价函数，以及状态表在井字棋中可以表现为下图：
学习评价函数（value function）
在下棋的过程中，我们不断修改已有value function对于井字棋，也就是上面我们提到的那张表，我们的目标是试图使其更加准确，为了达到这个目的，我们增加了一步“返回”（back up） 过程（上图中的红色箭头），这个过程在每一步贪心选择后执行，这一步执行的实质是通过当前状态值（value）来适当修改上一步状态的value，使它更接近现在状态的值（评价函数的结果，value），比如图中的红箭头就是让e的值（评价函数的结果，value）更接近g的值（评价函数的结果，value）。
上面的数学表达为，让 $s$ 为贪心选择之前的状态的值（评价函数的结果，value）， $s’$ 为贪心选择后的值（评价函数的结果，value），然后我们的back up更新 $s$ 值，方式是：
$$
V(s)\leftarrow V(s)+\alpha[V(s’)-V(s)]
$$
其中 $\alpha$ 是一个小的正小数，叫做“步长”（step-size）参数，这个参数影响学习速率（the rate of learning）注意这里rate是速率的意思，而不是比率的意思，所以学习率这种翻译，我觉得欠妥。
这种基于 $[V(s’)-V(s)]$ 的变化方式（update rule）被称为“时序差分学习”（temporal-difference learning），字面解释：基于两个不同时间点的值（评价函数的结果，value）的差值的方法，这个解释基本能反应这类方法的特点。
这类方法是我们后面要重点学习。
上述方法对于这个任务可以非常出色的得出不错的结果，例如，在步长参数（step-size）被精确递减后，这个算法对于固定的对手是收敛的，每一步都能给出胜算最高的走法。也就是说，这个方法对于一个固定的对手给出了最优策略。这里的一个关键就是 步长参数（step-size） 的调整，如果这个参数不调整，那么最后的结果也会收敛，但是速度会慢很多。
“进化方法”与“评价函数”的区别
上面这些细节也佐证了我们前面提到的：“进化方法”和“评价函数学习法”的区别：
- 进化方法的为了学习一个策略，其根本原则是策略不变（不是永久不变，是在目前的短时间内），而去和对手进行多场游戏（就是和环境的交互，interaction），或者使用一个对手的模型，来模拟进行多场游戏。在进行多次游戏后，胜利的次数给出当前策略胜率的无偏估计，然后这个无偏估计被用来优化策略（根据一定的规则从多个策略中淘汰某些，或者其他办法生成新的策略）。
但是问题是每次策略进化都需要多场游戏来计算概率，而每场游戏内的信息被忽略掉了（因为计算概率只关心结果的 —— 胜利出现的次数）而且当一个player（也可以成为agent）获得了胜利，他本场比赛的所有行为都会被认为是正确的，且每一步给予相同的得分，但实际上并不是这样，首先并不是每一步的重要性都一样，其次是并不是每一步都是正确的选择。 - 对比之下“评价函数学习法”就有不同的表现了，每一步棋和环境的交互信息都会被利用来学习。
总之，进化方法和“评价函数学习法”都是在搜索policy的空间，但是“评价函数学习法”搜索起来更高效，因为他利用了更多的有效信息。
“Tic-Tac-Toe” 中的强化学习
这个小小的游戏基本展现了强化学习的所有特性：
- 首先强调和环境的交互，这里就是和对手下棋。
- 目标明确，正确的行为需要 Planning 或者 Foresight 来处理延迟出现的结果
- 另一个显著的特征是，RL形成有效的 Planing 以及 lookahead ，而且这个过程不需要使用对手模型（model of opponent），也不会对后面全部的可选操作序列进行搜索（减少policy的搜索空间）
虽然RL的这几个有点很是吸引人，但是这不能掩盖其某些缺点：
- 训练的时的对手，不可能是人，而还是程序，所以这个对手不是Nature的
- 学习过程也是打碎成不同的步骤（对于井字棋每一局都是一步），而不是连续的进行，只有下完了才会产生reward信号，而不是连续的。
- 同样对于某些连续的任务，我们也要把它拆成离散形式。
井字棋的搜索范围很小，现在alpha go所面对搜索空间比井字棋大到不知道哪去了~，1992年的时候就有学者研究了比井字棋更复杂的游戏，空间大概规模是 $10^{20}$ 他们使用了神经网络作为模型，结合上面的方法得出了很好的结果，具体我们在后面16章学习。
强化学习面对如此巨大的policy空间的行为，主要取决于他对之前学习的信息的理解程度，理解的越好，其行为就更加可靠，反之则不可靠。
先验知识(Prior Knowledge)与模型(Model)
在井字棋游戏中，RL的agent只知道游戏规则毫无游戏经验或者先验知识，先验知识是锦上添花的元素，也就是，有或者没有这个要靠缘分，就算没有我们也要解决问题，而如果有，那么我们可以利用先验知识节省大量时间，或者大幅度提高结果。RL处理先验知识有多种方式，并且对学习结果。
我们目前处理的情况都是当前环境对agent有明确的反馈，且state明确，在有些问题中state可能是隐藏的或者有大量重复的state这种情况过于复杂，不在我们初级范围内。
Model同样是强化学习中的一个组成要素：当我们的RL（agent）学习应该怎么样应对不同的状况的时候，他需要思考的就是环境会怎么对他的action进行反应，有些问题确实如此，环境对action的反应就是一个模型，但是有的问题可能比这要更复杂一些，他们有的时候什么模型都没有，不知道环境会做出什么样的反应，面对这样的问题RL也有解决方案。同样的，有模型可以帮助RL更快的学习。
但是我们的井字棋就没有这个model，原因是对手怎么下棋是不可能有模型的，这就是个 Model-Free system。存在精确模型的系统由于模型被精确的使用，所以做起来相对简单，但是有的时候建立模型的过程会成为这个问题的瓶颈，本书中我们会讨论一些Model-Free的问题，同时组合这些问题成为更复杂的系统。
总结
本文通过研究Tic-Tac-Toe这个小游戏，从实际应用的角度分析了RL的各个方面，基本涵盖了大部分主要内容，后面我们进入第二章，开始分析具体算法，欢迎大家关注。
References
Sutton R S, Barto A G. Reinforcement learning: An introduction[J]. 2011.