游戏树

• 如果先手A选择上方，游戏进入到一个由进行B进行决策的分支，这叫做一个子游戏。在这个子游戏中，B选上方就A获胜，B选下方就B获胜，B要选择对自己有利的，所以他一定选择下方。这个子游戏的结局是固定的，就是B获胜。

• 如果先手A选择下方，游戏进入到另一个由B做决策的子游戏中，这时B选上方就A获胜，B选下方就和棋，B要选择对自己有利的，所以这个子游戏的结局一定是和棋。

• 我们再来考虑A：若A走上方，进入子游戏1，一定B获胜；A走下方，进入子游戏2，一定和棋。A也要选择对自己有利的，所以A选择下方。最终的游戏就是和棋。

如果游戏复杂一些，也不过是分支变多，长度变长，但是只要我们从最后端的子游戏开始，一层层倒推，就一定能推算出在最优策略下，游戏到底是先手胜，还是后手胜，还是和棋，这种胜负是不可避免的。

比如五子棋：双方轮流下子，五子连线获胜。人们逐渐发现：先手有必胜法。为了游戏公平，就设计了三三禁手、四四禁手、长连禁手，先手走出禁手就算输。与五子棋相比，中国象棋、围棋的规则就复杂很多，但是它们依然是双人完全信息博弈。

无禁手时五子棋的两种先手必胜开局

虽然我们不知道最优套路是什么

但是我们确信：

一定存在那样一种最优的策略

如果双方都执行了这种策略

则一定是先手赢、或者后手赢

或者一定和棋

可是，为什么我们从来没听说过谁

掌握了象棋和围棋的必胜法呢？

井字棋

我们举一个最简单的棋——井字棋来说明。

井字棋非常简单。首先画一个井字，然后先手画叉，后手画圈，在九个格子中轮流画。谁的三个子横竖斜连成一条线，谁就赢了。如果画满了双方都没有赢，那就是和棋。比如，下面就是一个先手胜的井字棋局。

一个井字棋牌局

这个游戏的规则虽然简单，但是可玩性还是很高的，因为它其实也有不少变化，说准确一点，应该叫游戏的复杂度。

首先，我们讨论游戏的状态复杂度，它表示在这个棋盘上到底会出现多少种可能的局面。一般来讲，我们没办法准确算出一个游戏的状态复杂度，很多时候也没必要准确算出来，我们只要估算一个上限，或者一个数量级，就可以了。

比如井字棋：每一个格子都有叉、圈、空白3种可能，一共有9个格子，所以最多能够出现的局面也不会超过39=19683种。这里面有许多不符合规则的情况，比如叉的数量要么和圈相同，要么多1个，其他情况都不符合规则。对称的情况，其实应该算作一种情况。如果把这些不符合规则和对称都去掉，最终余下的状态数是765种——你在井字棋中只能看到这765种局面。

状态数并不是衡量游戏复杂程度的唯一方式，因为同一个局面状态，也可以从不同的路径得出。要考察游戏玩法总数，我们得计算游戏树的大小。

井字棋的一部分游戏树

大家看：先手画第一个叉时，去掉对称性，其实只有三种画法：中间、边中点和角。这是树的第一层，有3个分支。

如果先手在中间画叉，去掉对称性，后手的圈只有两种画法：角和边的中点。如果先手画在边上或者角上，后手分别如图所示的五种画法。这是树的第二层，有12个分支。

之后，游戏还有很多层，每层又有很多分支，直到最后有一方获胜或者和棋。游戏树有多少个不同路径，就表示了游戏一共有多少种可能的变化。

在井字棋游戏中，我们可以估算游戏树的复杂度：先手先选位置，有9种可能；后手只剩下8种可能，先手又剩下7种可能…直到最后填满9个格子，所以游戏树复杂度不超过9!=362880种。这里面有许多不符合规则的，比如已经有一方获胜了，就不用再下了，还要去掉重复和对称的，最终的游戏树复杂度是26830。

人们已经考察了井字棋的全部26830条路径，并发现：如果双方都采用最优策略，那么井字棋一定是和棋。