3.1.3 井字棋（Tic-Tac-Toe）

井字棋是最简单的棋类强化学习环境之一，由于这个游戏的简单性，它经常被作为博弈树（Game Tree）搜索的例子用在各种人工智能算法的测试上。下面首先介绍一下棋类的强化学习环境。

和一般的强化学习环境不同，由于很多棋类游戏都涉及两个对手之间的博弈，所以对于棋类游戏来说，我们有两个智能体，一个智能体需要让自己获得的奖励最大，另一个智能体也需要让自身获取的奖励最大，同时对手获得的奖励最小。一般来说，对于这种有两个或多个智能体，每个智能体都希望让自身获取的奖励最大，其他智能体获得的奖励最小的强化学习环境，我们称为竞争性强化学习环境（Competitive Environment）。一般来说，对于这种类型的强化学习环境，不但需要智能体能获取更多的奖励，而且需要智能体能最小化其他智能体的奖励，这时具体的策略就不再是贪心策略，而需要所谓的对抗搜索策略（Adversarial Search）。

具体对于井字棋来说，整个棋盘是一个3×3的网格，其中每个格子可以填入两种棋子：叉号（✕）或者圆圈（◯）。这里默认叉号先下，圆圈后下。然后规则是当下棋的某一方在横方向、纵方向或者斜线方向上三个相同的可以连成一条线，则这一方获胜。当双方填满所有的格子而没有任意一方获胜的时候，我们认为双方和局。如图3.2所示，分别是井字棋初始的棋盘、一方获胜的棋局，以及和局的棋局。若考虑对称性，井字棋共有765种可能的状态，如果不考虑对称性（认为旋转以后的棋局不同），则井字棋共有26830种可能的状态。因为状态数目非常少（对比国际象棋大约有1040种不同的状态，围棋大约有10170种不同的状态），让井字棋成了一个很好的用来测试博弈类型的强化学习算法的环境。

从博弈论的角度来看，井字棋是一种完美信息（Perfect Information）的零和博弈（Zero-Sum Game）。完美信息意味着两个智能体都能获得棋局的全部信息，零和博弈则意味着两个智能体之间的局面只有一方获胜，另一方失败；或者两方和局的结果。假如我们认为获胜时获取的奖励是+1，失败为-1，和局为0，那么可以看到整个棋局的所有智能体的奖励的和永远为零，这也是零和博弈这个名词的由来。对于这个强化学习环境来说，可以看到，每一个智能体下的每一步都可以视为一个动作，而棋盘的局面视为一个状态。这样就可以把棋局博弈的问题视为一个强化学习的问题（这个观点对于很多其他游戏，比如国际象棋和围棋都适用）。

为了描述这个智能体在这种类型的强化学习环境中的决策过程，需要引入一个概念来描述这种类型的决策，这就是所谓的博弈树（Game Tree）。博弈树实际上是一种搜索树（Search Tree），代表博弈双方的智能体在双方所有可能的动作空间的搜索。图3.3演示了博弈树的一个搜索过程。

其中，第零步是初始棋盘，可以看到棋盘上没有任何棋子，这也是整个强化学习环境的初始状况。第一步开始叉号这一方先下子，图3.3中演示了其中的三种状态；第二步开始则轮到圆圈这一方下子，这里列出的是第一步开始最左边的一种情况衍生的三种状态。对应的从图3.3的0、1、2三步可以看到除了最开始的一种状态（这个状态称为所有状态的根结点，Root），所有的其他状态都有一个父结点，构成了一个树状的结构，因此描述这种类型的强化学习环境的数据结构被称为博弈树。有了博弈树之后，我们就能得知状态之间的先后连接关系，从而能够允许智能体在这个数据结构的基础上进行搜索。跟所有的树状数据结构一样，除了最后的叶（Leave）结点，所有的结点都有子结点。在最终的叶结点中，我们定义最先下子的一方会获取一个奖励，这个奖励或者为+1，这种情况对应这一方获胜；或者为0，对应双方和局的状态；或者为-1，对应这一方的对手获胜。图3.3中也展示了叶结点，我们可以在第N步的图中看到不同的状态及其对应的奖励。

为了演示博弈树在智能体搜索过程中的作用，下面以一个简单的例子介绍使用基于博弈树的算法来进行决策。这个决策过程算法的思想是：对于某一个智能体来说，考虑的是对手的决策能够获取的所有可能的奖励，以及如何决策才能让对手决策所能获取的最大可能的奖励最小。为了了解这个搜索算法，首先让我们回到前面定义的奖励上来，在整个决策过程中，因为以最后棋局终止的结果来决定智能体获取的奖励，结合上述的零和博弈的定义可以发现，如果以固定的某一个智能体获取的奖励作为标准，那么这个智能体的策略应该是极大化奖励，而对应的对手智能体的策略应该是极小化同一个奖励。基于这个思想，我们就可以考虑一个搜索算法，因为这个算法基于的是极大化自身的奖励和极小化对手的奖励的策略，因此我们称为极小化极大搜索（Minimax Search）算法。

下面结合一个具体的博弈树的定义来阐述如何在搜索过程中使用这个算法。图3.4描述了一个非常简单的博弈树，这个博弈树一共有两个决策步骤，其中的两个决策的智能体分别称为A和B，从第一层的根结点出发，首先由A进行决策，然后由B进行决策，到达最终的叶结点（图3.4中标记为A的底层）。最后输出的结果是A获取的奖励。由于最后一步的决策是B，因此A在决策的时候需要考虑B的决策，而B的决策肯定是使A获取的奖励最小。因此，在最后B的决策所输出的所有结点中，一定会选择A获取最小奖励的结点，用向下的箭头表示这个过程，即极小化步骤。可以见到，B决策初始时可能的三个结点，A对应的可能获取的最大奖励分别-1、0和+1。继续沿着这颗博弈树回溯，在最初的选择中由于是A开始做选择，因此A需要尽可能获取最大的奖励，也就是选择最右边的分支，我们称为决策的极大化步骤，用向上的三角形来表示。在这个过程中，A可能获取的最大奖励为+1。

回到井字棋对应的强化学习环境。为了求解井字棋的问题，首先需要构建对应的强化学习环境的代码。代码3.1演示了如何构造一个这种类型的代码（这里只看关键的几行，详细的代码和示例请参见本书所附的文件ex_3_1.py）。下面具体分析一下这段代码。整个强化学习环境是一个类，这个类中的board成员保存棋局，这个棋局由一个3×3的二维列表构成。在初始情况下，用“*”字符来代表未被占据的格子，用“x”字符代表✕这一方占据的位置，用“o”字符来代表◯这一方占据的位置。我们需要记录的信息主要有当前下棋的步数nstep，当前是否是第一个（这里是✕这一方）玩家（智能体）在执行棋局first_player，以及当前是否结束了游戏end，如果结束了游戏，那么获取的奖励是多少reward。通过reset方法，可以把强化学习环境还原到最初始的阶段。有了这个环境之后，我们需要知道每一步棋子可能落子的位置，用action_space方法来获取所有可能的落子位置，实现起来也很简单，只要检查所有的位置并判断这个位置是不是“*”字符即可。最后一个关键的方法则是执行落子的步骤，给定一个位置，我们检查当前是第一个玩家下棋还是第二个玩家下棋，根据当前落子的选手把目标的位置替换为“o”字符或者“*”字符。在落子之后，需要检查游戏是否结束（我们会发现至少需要5步才能决定游戏是否结束，而且可以根据最后落子的位置来判断这个落子是否和其他的落子构成连线）。最后则是平局的判断，当下完9步之后，如果发现游戏还没结束，那么将会直接把游戏标记为平局结束（同时设置奖励为0）。

代码3.1 井字棋强化学习环境示例代码。

有了这个强化学习环境之后，就可以基于这个强化学习环境来实现一个简单的极小化极大搜索算法。具体代码说明如代码3.2所示（同样的，可以在源代码文件ex_3_1.py中找到这个算法的一个实现）。这个代码的输入是强化学习环境，在这个算法的函数中首先需要检测环境是否处于结束状态，如果是，则直接返回当前环境获取的奖励；如果否，则需要分成两种不同的状态来进行讨论。在第一种状态中，智能体处于第一个玩家的状态，那么根据极小化极大搜索算法的原理可以知道，我们需要极大化当前的奖励。这时需要穷举当前可能的决策，在这些决策中选出最大的可能奖励的决策步骤即可；与此相对的，在第二种状态中，智能体处于第二个玩家的状态，那么根据算法可知需要极小化当前的奖励。注意，这个算法是递归的（而且是深度优先的），在环境处于结束状态之前两个智能体会交替决策，直到获得一个确定的奖励为止。

代码3.2 井字棋强化学习环境的极小化极大搜索算法示例。

有兴趣的读者可以通过修改文件ex_3_1.py中的源代码来观察极小化极大搜索算法的决策过程。在实际的运行过程中，对于最初的几步决策，因为决策空间非常大，我们的算法会非常缓慢（笔者的电脑大约需要1min来执行一步决策），随着决策的深入，算法会越来越快，第二步开始大概就花几秒钟。

可以看到，搜索空间的大小对于极小化极大搜索速度影响很大。在实际的应用中需要引入一些其他的优化策略，比如Alpha-Beta剪枝（Alpha-Beta Pruning）的方法，在搜索过程中确定奖励的上界和下界，这样就不需要走博弈树的一些分支，从而有效地减少搜索空间的大小，加快搜索算法的速度。

由于篇幅所限（而且这种类型的博弈树搜索方法并不是本书的主题），有兴趣的读者可以参考本书的参考文献2，来获取有关Alpha-Beta剪枝算法的相关信息。当然，即使采用了Alpha-Beta剪枝的极小化极大搜索算法，在面对状态空间非常大的棋类游戏，比如围棋的时候，也会变得非常缓慢，以至于算法不能被应用在实际问题上。我们在本书有关章节中会讨论蒙特卡洛树搜索算法（Monte Carlo Tree Search, MCTS），结合深度学习价值网络和策略网络来有效地解决状态空间过大的问题。