许多小伙伴喜欢棋牌游戏

比如象棋、围棋、扑克…

当你和对手厮杀的昏天黑地时

有没有想过这样一个问题：

这些游戏有必胜策略吗？

如果你偶然间在洞穴中找到了一本秘籍

从而获得了某种棋牌的必胜套路

那该是一件多么“荣耀”的事啊！

今天，我们就来讨论下这个问题

↓↓↓

策梅洛定理

首先，我们要把游戏分为两种：完全信息博弈和不完全信息博弈。如果所有的参与者，在游戏的任何阶段都可以获知过去以及现在的所有游戏信息，这类游戏就被称为完全信息博弈。否则，就称为不完全信息博弈。

比如：象棋、围棋、五子棋，大家都能看到对方是怎么走的，这就是完全信息博弈。但是，军棋却不是这样——四国军棋你不知道对方的排兵布阵，翻翻棋你连自己的棋子在哪里都不知道。扑克牌你不知道对方手里的牌，麻将你不光不知道对方手里的牌，也不知道牌桌上剩下的牌，像军棋、扑克、麻将这样的游戏，就叫做不完全信息博弈。

1913年

数学家策梅洛证明：

对于一个两人的完全信息游戏

一定存在一个策略，要么先手一定获胜

要么后手一定获胜，要么双方一定平局

▲策梅洛

这就是策梅洛定理，这个定理如何证明呢？其实很简单：一个轮流走棋的游戏，每一步的走法都是有限的，这称为游戏分支，游戏的分支是有限的。由于制定了一些胜负以及和棋规则，游戏的步骤也是有限的。

我们假设有一个非常简单的游戏，先手A和后手B各做一次决策（选择上路或者下路），根据二人决策的结果，游戏的胜负如下。通过这个表格，你能知道游戏的结果是谁获胜吗？

▲某个游戏的策略和结果

也许有同学认为：A赢面大一些，其实并非如此。这盘棋的结果一定是和棋（除非有一方实在脑子不太好用，才会输掉）。我们可以画一个游戏树来解释：

▲游戏树

如果先手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条路径，并发现：如果双方都采用最优策略，那么井字棋一定是和棋。

▲先手最优策略

像这样完整画出游戏树，找出最优策略的游戏叫做已解决游戏。尽管如此，大部分情况下，井字棋还是会出现输赢，这是因为有些人对游戏树掌握的好，有些人掌握的不好。

▲后手最优策略

一旦对方出现失误

对游戏树掌握信息好的人

就能迅速抓住这个漏洞

让不会玩的人陷入必败的游戏树分支之中

这就是大师和新手的区别

围棋

其实，象棋和围棋的本质

与井字棋没有本质不同

只是复杂度比井字棋高很多

▲围棋

以围棋为例：围棋在19x19=361个格子上轮流放棋子，所以每个格子有黑白空三种可能，整个围棋棋盘上的状态数上限是3361=1.7x10172，去掉一些重复和对称，围棋的状态复杂度大约是10171量级。

要知道：宇宙中的原子个数只有大约1080个，就算用宇宙中的一个原子代表一个围棋局面，穷尽宇宙中所有的原子，也不能表示出围棋所有的棋局局面。

围棋的游戏树就更难画了。因为围棋可以提子，有了空白的地方可以继续下，所以并不一定是填满了棋盘就结束。不过，我们可以估计游戏树的总层数和每一层的平均分支。根据统计和计算：一盘围棋的平均手数是150手，每一手的平均分支数是250种，所以整个围棋的游戏树复杂度大约250150≈10360。

理论上讲，如果我们遍历了所有10360种情况，就能知道围棋结局到底是先手必胜，还是后手必胜，或者一定是和棋了。但是，这个计算量实在太大了。世界上最快的计算机富岳每秒最高可以计算100亿亿次浮点运算，假如1次浮点运算就能算出一条路径，那么算完所有围棋游戏的可能情况，需要10342秒，而宇宙的年龄只有138亿年，大约只等于1017s。

显然我们知道围棋一定有最优策略，但是我们无法计算出这个最优策略。不过，数学家们也找到了一些其他方法，不用遍历所有情况，也能找到比较好的获胜方法，比如1997年深蓝战胜国际象棋世界冠军卡斯帕罗夫，2016年阿法狗打遍天下无敌手，都是采用了人工智能的方法。

▲人工智能战胜人类的过程

除了围棋以外，人们也估算了其他几种棋类游戏的复杂度，如下表所示。你会发现井字棋情况特别少，因此很容易成为大师，两位大师碰到一起，只能是和棋。五子棋情况稍多，但是只要玩的多，也能发现套路，从而成为大师，无禁手时先手必胜。像国际象棋、中国象棋，围棋复杂度就更高了。

军棋

刚才我们讨论的几种棋，虽然复杂度不同，但它们都是明棋，也就是博弈双方都对目前的局势了如指掌。这样的棋有最优解，谁更接近最优解，谁的棋术就更高，不出意外的情况下，棋术低的人绝不可能赢棋术高的人，就比如我和阿法狗下围棋，是绝对赢不了的。

但也有一些棋

下棋的人并不知道所有棋子的情况

有的时候，因为运气好

棋术差的人也能战胜棋术好的人

这就为游戏增添了很多乐趣

这种暗棋就是不完全信息博弈

比如，大家还记得军棋吗？

▲军棋

双方各有25个棋子，司令可以吃军长，军长可以吃师长，工兵可以挖地雷，挖完了地雷扛军旗就赢了。军棋有很多种玩法，其中一种是：开局之前，你要先暗自排兵布阵，把自己的25个子放在25个位置上，不让对方看到。两个子相遇，由裁判判定谁吃谁。所以双方都不知道对方的棋子是什么。我小时候特别喜欢玩军棋，运气好的时候自己的司令吃了敌方的军长，或者敌方司令踩了我的地雷，我就特别高兴。

怎么描述军棋的复杂程度呢？我们需要信息集这个概念。

信息集的大小表示所有未知信息的可能数。比如我和张三对局，我知道张三只会10种排兵布阵的方法，只是我不知道他选用了哪一种。这时，信息集大小就是10。

信息集的个数表示所有已知信息的可能数。比如我自己只会5种开局阵型，那么我的信息集个数就是5。

大家想想，我和张三对局时，局面有多少种可能？应该是50种对吗？只要用信息集大小乘以信息集个数就可以了。实际上如果两人对垒，双方各有25个子，排到自己的25个兵站上，开局时军棋的信息集的大小和个数都是25！=1.5x1025种（忽略重复的子）。

▲军棋棋盘

现在我们就从单一维度的局面状态变成了信息集大小和信息集个数两个维度了信息集大小表示未知可能性的集合信息集个数表示已知局面的总状态数不完全信息博弈有两个维度的复杂度

麻将

我们再来看看我们的“国粹”：麻将。

麻将也是一种暗棋。34种牌，每种4张，一共136张牌。开局时四方各抓13张，每一轮抓一张再打一张，最后如果剩下14~16张还没有人胡牌，就算流局。我们知道自己手里的牌，但由于对手牌以及公共牌池中的牌均不可知，所以是不完全信息博弈，是暗棋。咱们具体来算算信息集个数和信息集大小：

▲麻将

第一轮

信息集个数：麻将牌一共136张，我起手抓13张牌，不考虑重复，我拿到的牌的可能方法数有种。

信息集大小：除了我手中的13张牌外，还有123张牌，其余三名玩家每人手里有13张，所以未知的可能数有种。

第二轮

信息集个数：在第一轮中，4个玩家每人打了1张，麻将牌一共有34种，所以打牌的方法数共有344种。此时，此时我手里还有13张牌，方法数有，所以现在，我可能面临的局面有种。

信息集大小：除了我手里的13张，以及上一轮打出的4张，还余下119张牌，三家手里还是各有13张牌，可能数有种。

……

因为麻将最后要余下14~16张牌就流局，所以最多可以打17轮左右。我们按照这种方法，把这17轮的信息集个数和信息集大小全部列出来，如下表所示：

▲麻将每一轮的信息集个数和大小

用图表更清晰一些：

你会发现：随着打牌的进行，信息集的个数越变越大，也就是我能够观察到的、可能的局面数量越来越多。信息集的大小越变越小，也就是我未知的局面的可能性越来越少。

还可以算出：在麻将中，信息集的总个数大约是大约是10115，这就是我们打麻将时，能看到的状态总数上限。对每一个局面，信息集的平均大小大约是1049，也就是我们未知的、别人手里的牌的可能组合。用信息集总数乘以平均信息集大小，能够估计出麻将的状态复杂度，大约是10^165。

微软亚洲研究院曾经比较过几种棋牌游戏的状态复杂度。在这张图上，纵轴表示信息集大小，也就是不确定性；横轴表示信息集个数，也就是明牌部分的变化。

▲参考微软亚洲研究院做出的棋牌复杂度图

你会发现：井字棋、国际跳棋、中国象棋、国际象棋和围棋，因为完全没有不确定性，它的信息集大小为1，只有信息集个数一个维度。如我们刚刚所说，这些棋类都有最优策略。

而麻将、桥牌、德州扑克，除了自己拿到的牌有很多种变化外，就算你看到了同样的局面，别人依然有很多种可能的牌，它们是不完全信息博弈，有两个维度。相比而言，麻将比桥牌和德州扑克的信息集大小大很多，这说明麻将的不确定性更大，运气在麻将里更重要。

只要游戏存在两个维度，存在不确定性，一般就没有必胜的策略了。显然，只要我的牌足够好，无论你水平多高，你打麻将也会大概率输给我。计算机在计算麻将这类不完全信息博弈问题中的进度，明显落后于象棋围棋。

许多游戏都具有丰富的变化和不确定性一个普通选手也可能战胜高手偶尔的意外之喜或许就是游戏的魅力

相比游戏

生活充满更多的可能性

多一次思考、多一点选择

通往未来的路

一定会更加踏实坚定！

END编辑：孟丽君校对：陶铮审校：余治国来源：李永乐老师

▼关注"青春深圳"微信、抖音、快手、B站、视频号