许多小伙伴喜欢棋牌游戏
比如象棋、围棋、扑克…
当你和对手厮杀的昏天黑地时
有没有想过这样一个问题：
这些游戏有必胜策略吗？
如果你偶然间在洞穴中找到了一本秘籍
从而获得了某种棋牌的必胜套路
那该是一件多么“荣耀”的事啊！
今天，我们就来讨论下这个问题
策梅洛定理
首先，我们要把游戏分为两种：完全信息博弈和不完全信息博弈。如果所有的参与者，在游戏的任何阶段都可以获知过去以及现在的所有游戏信息，这类游戏就被称为完全信息博弈。否则，就称为不完全信息博弈。
比如：象棋、围棋、五子棋，大家都能看到对方是怎么走的，这就是完全信息博弈。但是，军棋却不是这样——四国军棋你不知道对方的排兵布阵，翻翻棋你连自己的棋子在哪里都不知道。扑克牌你不知道对方手里的牌，麻将你不光不知道对方手里的牌，也不知道牌桌上剩下的牌，像军棋、扑克、麻将这样的游戏，就叫做不完全信息博弈。
1、军棋的棋子各方均有25个，分别为军旗、司令、军长各一；师长、旅长、团长、营长、炸弹各二；连长、排长、工兵、地雷各三。2、吃子规则：司令>军长>师长>旅长>团长>营长>连长>排长>工兵，小棋遇大棋被吃，相同棋子。
1913年
数学家策梅洛证明：
对于一个两人的完全信息游戏
一定存在一个策略，要么先手一定获胜
要么后手一定获胜，要么双方一定平局
▲策梅洛
这就是策梅洛定理，这个定理如何证明呢？其实很简单：一个轮流走棋的游戏，军棋怎么下视频讲解，每一步的走法都是有限的，这称为游戏分支，游戏的分支是有限的。由于制定了一些胜负以及和棋规则，游戏的步骤也是有限的。
我们假设有一个非常简单的游戏，先手A和后手B各做一次决策（选择上路或者下路），根据二人决策的结果，游戏的胜负如下。通过这个表格，你能知道游戏的结果是谁获胜吗？
▲某个游戏的策略和结果
也许有同学认为：A赢面大一些，其实并非如此。这盘棋的结果一定是和棋（除非有一方实在脑子不太好用，才会输掉）。我们可以画一个游戏树来解释：
▲游戏树
如果先手A选择上方，游戏进入到一个由进行B进行决策的分支，这叫做一个子游戏。在这个子游戏中，B选上方就A获胜，B选下方就B获胜，B要选择对自己有利的，所以他一定选择下方。这个子游戏的结局是固定的，就是B获胜。
如果先手A选择下方，游戏进入到另一个由B做决策的子游戏中，这时B选上方就A获胜，B选下方就和棋，B要选择对自己有利的，所以这个子游戏的结局一定是和棋。
如果游戏复杂一些，也不过是分支变多，长度变长，但是只要我们从最后端的子游戏开始，一层层倒推，就一定能推算出在最优策略下，游戏到底是先手胜，还是后手胜，还是和棋，这种胜负是不可避免的。
比如五子棋：双方轮流下子，五子连线获胜。人们逐渐发现：先手有必胜法。为了游戏公平，就设计了三三禁手、四四禁手、长连禁手，先手走出禁手就算输。与五子棋相比，中国象棋、围棋的规则就复杂很多，但是它们依然是双人完全信息博弈。
▲无禁手时五子棋的两种先手必胜开局
虽然我们不知道最优套路是什么
但是我们确信：
一定存在那样一种最优的策略
如果双方都执行了这种策略
则一定是先手赢、或者后手赢
或者一定和棋
可是，为什么我们从来没听说过谁
掌握了象棋和围棋的必胜法呢？
井字棋
棋子每方各有25个，分别为军旗、司令、军长各一；师长、旅长、团长、营长、炸弹各二；连长、排长、工兵、地雷各三。杀光对方所有能移动的棋子则获得胜利；或者用本方的棋子吃掉对方的军旗，也能获得胜利。司令>军长>师长>。
我们举一个最简单的棋——井字棋来说明。
▲一个井字棋牌局
这个游戏的规则虽然简单，但是可玩性还是很高的，因为它其实也有不少变化，说准确一点，应该叫游戏的复杂度。
首先，我们讨论游戏的状态复杂度，它表示在这个棋盘上到底会出现多少种可能的局面。一般来讲，我们没办法准确算出一个游戏的状态复杂度，很多时候也没必要准确算出来，我们只要估算一个上限，或者一个数量级，就可以了。
比如井字棋：每一个格子都有叉、圈、空白3种可能，一共有9个格子，所以最多能够出现的局面也不会超过39=19683种。这里面有许多不符合规则的情况，比如叉的数量要么和圈相同，要么多1个，其他情况都不符合规则。对称的情况，其实应该算作一种情况。如果把这些不符合规则和对称都去掉，最终余下的状态数是765种——你在井字棋中只能看到这765种局面。
状态数并不是衡量游戏复杂程度的唯一方式，因为同一个局面状态，也可以从不同的路径得出。要考察游戏玩法总数，我们得计算游戏树的大小。
▲井字棋的一部分游戏树
大家看：先手画第一个叉时，去掉对称性，其实只有三种画法：中间、边中点和角。这是树的第一层，有3个分支。
如果先手在中间画叉，去掉对称性，后手的圈只有两种画法：角和边的中点。如果先手画在边上或者角上，后手分别如图所示的五种画法。这是树的第二层，有12个分支。
之后，游戏还有很多层，每层又有很多分支，直到最后有一方获胜或者和棋。游戏树有多少个不同路径，就表示了游戏一共有多少种可能的变化。
人们已经考察了井字棋的全部26830条路径，并发现：如果双方都采用最优策略，那么井字棋一定是和棋。
▲先手最优策略
像这样完整画出游戏树，找出最优策略的游戏叫做已解决游戏。尽管如此，大部分情况下，井字棋还是会出现输赢，这是因为有些人对游戏树掌握的好，有些人掌握的不好。
▲后手最优策略
一旦对方出现失误
对游戏树掌握信息好的人
就能迅速抓住这个漏洞
让不会玩的人陷入必败的游戏树分支之中
这就是大师和新手的区别
围棋
其实，象棋和围棋的本质
与井字棋没有本质不同
只是复杂度比井字棋高很多
▲围棋
以围棋为例：围棋在19x19=361个格子上轮流放棋子，所以每个格子有黑白空三种可能，整个围棋棋盘上的状态数上限是3361=1.7x10172，去掉一些重复和对称，围棋的状态复杂度大约是10171量级。
要知道：宇宙中的原子个数只有大约1080个，就算用宇宙中的一个原子代表一个围棋局面，穷尽宇宙中所有的原子，也不能表示出围棋所有的棋局局面。
围棋的游戏树就更难画了。因为围棋可以提子，有了空白的地方可以继续下，所以并不一定是填满了棋盘就结束。不过，我们可以估计游戏树的总层数和每一层的平均分支。根据统计和计算：一盘围棋的平均手数是150手，每一手的平均分支数是250种，所以整个围棋的游戏树复杂度大约250150≈10360。
每方各有25颗。军棋的棋子分别为军旗、司令、军长各一个；师长、旅长、团长、营长、炸弹各二个；连长、排长、工兵、地雷各三个。军棋是中国深受欢迎的棋类游戏之一。军棋的行走路线包括铁路线和公路线，每方有5个行营、23。
显然我们知道围棋一定有最优策略，但是我们无法计算出这个最优策略。不过，数学家们也找到了一些其他方法，不用遍历所有情况，也能找到比较好的获胜方法，比如1997年深蓝战胜国际象棋世界冠军卡斯帕罗夫，2016年阿法狗打遍天下无敌手，都是采用了人工智能的方法。
▲人工智能战胜人类的过程
除了围棋以外，人们也估算了其他几种棋类游戏的复杂度，如下表所示。你会发现井字棋情况特别少，因此很容易成为大师，两位大师碰到一起，只能是和棋。五子棋情况稍多，但是只要玩的多，也能发现套路，从而成为大师，无禁手时先手必胜。像国际象棋、中国象棋，围棋复杂度就更高了。
军棋
刚才我们讨论的几种棋，虽然复杂度不同，但它们都是明棋，也就是博弈双方都对目前的局势了如指掌。这样的棋有最优解，谁更接近最优解，谁的棋术就更高，不出意外的情况下，棋术低的人绝不可能赢棋术高的人，就比如我和阿法狗下围棋，是绝对赢不了的。
但也有一些棋
下棋的人并不知道所有棋子的情况
有的时候，因为运气好
棋术差的人也能战胜棋术好的人
这就为游戏增添了很多乐趣
这种暗棋就是不完全信息博弈
比如，大家还记得军棋吗？
▲军棋
双方各有25个棋子，司令可以吃军长，军长可以吃师长，工兵可以挖地雷，挖完了地雷扛军旗就赢了。军棋有很多种玩法，其中一种是：开局之前，你要先暗自排兵布阵，把自己的25个子放在25个位置上，不让对方看到。两个子相遇，由裁判判定谁吃谁。所以双方都不知道对方的棋子是什么。我小时候特别喜欢玩军棋，运气好的时候自己的司令吃了敌方的军长，或者敌方司令踩了我的地雷，我就特别高兴。
怎么描述军棋的复杂程度呢？我们需要信息集这个概念。
信息集的大小表示所有未知信息的可能数。比如我和张三对局，我知道张三只会10种排兵布阵的方法，只是我不知道他选用了哪一种。这时，信息集大小就是10。
信息集的个数表示所有已知信息的可能数。比如我自己只会5种开局阵型，那么我的信息集个数就是5。
大家想想，我和张三对局时，局面有多少种可能？应该是50种对吗？只要用信息集大小乘以信息集个数就可以了。实际上如果两人对垒，双方各有25个子，排到自己的25个兵站上，开局时军棋的信息集的大小和个数都是25！=1.5x1025种（忽略重复的子）。
▲军棋棋盘
现在我们就从单一维度的局面状态
变成了信息集大小和信息集个数
两个维度了
信息集大小表示未知可能性的集合
信息集个数表示已知局面的总状态数
不完全信息博弈有两个维度的复杂度
麻将
我们再来看看我们的“国粹”：麻将。
麻将也是一种暗棋。34种牌，每种4张，一共136张牌。开局时四方各抓13张，每一轮抓一张再打一张，最后如果剩下14~16张还没有人胡牌，就算流局。我们知道自己手里的牌，但由于对手牌以及公共牌池中的牌均不可知，所以是不完全信息博弈，是暗棋。咱们具体来算算信息集个数和信息集大小：
▲麻将
军棋棋盘：行走路线包括铁路线和公路线，每方有5个行营、23个兵站（翻棋25个）、2个大本营。准备好双方不同颜色的棋子。兵站是棋子的摆放位置；铁路线是棋子的快行线，只要在直线上棋子走的步数都不限（除了工兵以外，其他。
第一轮
信息集个数：麻将牌一共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站、视频号
