许多小朋友喜欢棋牌游戏，比如象棋、围棋、麻将、扑克…当你和对手厮杀的昏天黑地时，有没有想过这样一个问题：这些游戏有必胜策略吗？
如果你某一天偶然间在一个洞穴中找到了一本秘籍，从而获得了某种棋牌的必胜套路，什么深蓝、阿法狗，统统需要让位，那该是一件多么荣耀的事情啊！
今天，我们就来讨论一下这个问题。
策梅洛定理
首先，我们要把游戏分为两种：完全信息博弈和不完全信息博弈。如果所有的参与者，在游戏的任何阶段都可以获知过去以及现在的所有游戏信息，这类游游戏就称为为完全信息博弈。否则，就称为不完全信息博弈。
比如：象棋、围棋、五子棋，大家都能看到对方是怎么走的，这就是完全信息博弈。但是，军棋却不是这样——四国军棋你不知道对方的排兵布阵，翻翻棋你连自己的棋子在哪里都不知道。扑克牌你不知道对方手里的牌，麻将你不光不知道对方手里的牌，也不知道牌桌上剩下的牌，像军棋、扑克、麻将这样的游戏，就叫做不完全信息博弈。
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，去掉一些重复和对称，围棋的状态复杂度大约是1171量级。
要知道：宇宙中的原子个数只有大约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