德州扑克定理相关：象棋围棋麻将德州，哪种游戏更复杂有无必胜法？

有好多小朋友喜爱棋牌游戏，像象棋，围棋，麻将，扑克等等，在你跟对手拼杀得昏天黑地之际，有没有思考过这样一个问题，这些游戏存在必胜策略吗？

假如有那么一天，你不经意间身处一个洞穴之中，进而发现了一本秘籍，凭借此秘籍得到了某种棋牌的必胜方法，那些诸如深蓝、阿法狗之类的，都得退居其次，这该是一件何等荣耀的事啊！

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

策梅洛定理

一开头，我们得将游戏划分成两种类别，分别是完全信息博弈以及不完全信息博弈。要是全部的参与者，在游戏的任一阶段都能够知晓过去还有当下的每一游戏信息，这般的游戏名叫完全信息博弈。不然的话，那就称作不完全信息博弈。

好比象棋、围棋、五子棋，众人皆能瞧见对方的走法，此乃全然信息博弈。然而，军棋就并非如此这般，四国军棋时你无从知晓对方的排兵列布情况；翻翻棋中你就连自身棋子所处位置都全然不知。扑克牌方面你不清楚对方手头的牌；麻将呢，你不但不晓得对方手中所持之牌，还不知晓牌桌上剩余的牌，似军棋、扑克、麻将这类游戏，便称作不完全信息博弈。

在1913年的时候，数学家策梅洛给出了证明，表述为对于一个有着两人参与的完全信息游戏而言，必定存在着一个策略，此策略下要么先手必定会取得胜利，要么后手必定会取得胜利，要么双方必定会打成平局，而这就是所谓的策梅洛定理。

策梅洛

这个定理要怎样去证明呢？说真的 ，是挺简单的：存在一个轮流进行走棋操作的游戏 ，每一回走棋的方式都是数量有限的若干种 ，这种情况被称作游戏分支 ，该游戏所具有的分支数量是有限的。因为设定了一些关于胜负以及和棋的规则 ，所以该游戏进行的步骤数量同样是有限的。

假定存在一个十分简易的游戏，先手的A要做一次决策，即选择上路或者下路，而后手的B同样要做一次决策，也是选择上路或者下路 ，依照二人决策所产生的结果 ，游戏的胜负情况如下。借助这个表格 ，你能够知晓游戏的结果是哪一方获胜吗？

某个游戏的策略和结果

或许会有同学持有这样的看法，就是觉得A的获胜可能性相对大一点，然而实际情况并非是这样的。关于这盘棋的最终结果必定是和棋，除非存在一方的脑子实在是不太好使，才会出现输掉的情况。我们能够绘制出一个游戏树来对其进行解释。

游戏树

要是游戏变得复杂些许，那无非就是分支数量增多，长度得以延长，然而只要采取从最后端的子游戏起始，一层一层逆向推导的方式，就必定能够推算出在最优策略的情形下，游戏到底是先手获胜，还是后手获胜，亦或是和棋，这种胜负状况是不可避免的。

举个例子来说五子棋，双方是轮流去下子的，当有五子连线的时候便会获胜。人们是逐渐发现这样一个情况的，那就是先手有一种必定会获胜的方法。为了让这款游戏能够保持公平，于是就设计出来了三三禁手、四四禁手以及长连禁手，要是先手走出了禁手的情况，那么就算是输了。

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

跟五子棋相较，中国象棋、围棋的制订规则繁杂很多，然而它们依旧属于双人完全信息博弈。虽说我们不清楚最优套路是怎样的，可是我们坚信：必定存在那般一种最优策略，要是双方都践行了这种策略，那么必定是先手获胜、或者后手获胜、或者必定战成和棋。

可是，为什么我们从来没听说过谁掌握了象棋和围棋的必胜法呢？

井字棋

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

井字棋，极其容易上手。最先，要去画上一个井字模样，接着，先下棋的人画上叉，后下棋的人画上圈，于那九个格子里头依次轮流着画。哪一方的三个子能够在横竖斜方向上连接成为一条线，那么哪一方就赢得胜利了。要是九个格子都被画满了，而双方都没有取得胜利，那么此时就是打成平分秋色的和局了。比如说，下面所呈现给你的正是一个由一方率先取得胜利的井字棋的棋局。

一个井字棋牌局

这个游戏规则虽说简单，然而其具备着较高的可玩性，原因在于它实际上有着相当数量的变动，确切来讲，将之称作为游戏的复杂度。

首先，我们针对游戏的状态复杂度展开讨论，其意味着在该棋盘之上究竟会出现多少种具备可能性的局面。通常而言，我们没有办法精确地计算出一款游戏的状态复杂度，在许多情况下也没有必要精确算出来，我们只要对一个上限进行估算，或者是估算出一个数量级便可以了。

就拿井字棋来说，每一个格子存在叉、圈、空白这3种可能性，总共有着9个格子，所以，最多能够出现的局面不会超过3的9次方，也就是19683种。这里面存在许多不符合规则的情形，像叉的数量要么与圈相同，要么比圈多1个，其他状况都不符合规则。对称的情况，实际上应当算作一种情况。要是把这些不符合规则以及对称的情况都去除掉，最终剩余的状态数是765种——你于井字棋中仅能见到这765种局面。

状态数并非是用以衡量游戏复杂程度的独一无二的方式，因为针对同一个该局局面状态，其也是能够从不一样的路径推导得出的。若要去考察游戏玩法的总体数量，那我们是需要计算游戏树的规模大小的。

井字棋的一部分游戏树

咱大伙瞧一瞧：当最先开始画那第一个叉的时候，把对称性给去除掉，实际上仅仅存在三种画法，分别是在中间画，在边的中点画，以及在角上画。这便是树的第一层，它有着三个分支。

倘若先手于中间画上叉以消除对称性，那么后手之圈仅存在两种画法乃是角以及相邻两条交叉线中点；要是先手把叉画于边上抑或是角上，而后手就会分别拥有如图所呈现的五种画法。此乃树的第二层，存在着12个分支。

在此之后，游戏具备许多层次，每一个层次之中又存在诸多分支，一直持续到最终出现一方取得胜利这种情况得以发生或者和下棋局达成平局的状态成立。游戏所形成的树状图示里拥有多少个彼此各异的路径，那就意味着游戏整体总共拥有多少种具备可能性的变化情况。

井字棋游戏里，能估算游戏树复杂度，先手先是要选位置，存在九种可能性，继而轮到后手，此时剩余八种可能性，接着先手再选又剩下七种可能性，依此类推直至填满九个格子，所以游戏树复杂度不超过九的阶乘即362880种。当中存在许多不符合规则的情形，比如说存在一方已经获胜了，后续就无需再继续下了，并且还要将重复以及对称的情况去掉，最终得到的游戏树复杂度是26830。

有人已然探究了井字棋的全部二万六千八百三十条路径，并且发觉：要是双方均运用最优策略，那么井字棋必定是和棋。

先手最优策略

后手最优策略

诸如这般完整地描绘出游戏树，寻觅到最优策略的游戏称作已解决游戏。即便如此，在大多数情形下，井字棋依旧存在输赢状况，这是源于有的人对游戏树把握得不错，有的人把握得欠佳。一旦对方出现差错，对游戏树掌握信息良好的人便能迅速捕捉到这个破绽，致使不擅长玩的人陷入必定失败的游戏树分支里头。这便是大师与新手的差异所在。

围棋

实际上，象棋是这样的情况，围棋也是如此这般，它们跟井字棋不存在本质上的差异，仅仅是复杂度相较于井字棋要高出来许多。

围棋

以围棋作为例子，围棋在尺寸为19乘以19等于361个格子的棋盘上轮流去放置棋子，因而每个格子存在着黑、白、空这三种可能性。整个围棋棋盘上面的状态数上限是3的361次方等于1.7乘以10的172次方，去除掉一些重复以及对称的情况，围棋的状态复杂度大概是10的171次方量级。

需明白，宇宙里的原子数量仅仅大概有1080个，哪怕用宇宙当中的一个原子去代表一个围棋局面，就算用尽宇宙内所有的原子，也没办法表示出围棋全部的棋局局面。

围棋的游戏树画起来就更具难度了，因为围棋存在提子的情况，存在能继续落子的空白区域，所以并非棋盘填满就宣告结束，不过，我们能够估算游戏树的总层数以及每一层的平均分支数量，依据统计与计算，一盘围棋的平均手数为150手，每一手的平均分支数是250种，所以整个围棋的游戏树复杂度大概是250150≈10360。

从理论方面来讲，要是我们将所有的10360种情形都进行了遍历，那么就能够知晓围棋的结局究竟是先手必定获胜，还是后手必定获胜，又或者肯定是和棋了。然而，这个计算的数量实在是太过庞大了。世界上速度最快的计算机富岳，其每秒能够进行的最高浮点运算次数是100亿亿次，假设1次浮点运算就能够计算出一条路径，那么要计算完所有围棋游戏可能出现的情况，需要10342秒，而宇宙的年龄仅仅只有138亿年，大概只等同于1017s。

明显地，我们晓得围棋必然存在最优策略，然而我们没办法算出这个最优策略。

但是，数学家们，还寻觅到了好些别的途径，并非要逐一遍历全部情形，同样能够探究出相对优良的取胜办法，这般的例子有，在1997年的时候，深蓝成功击败了国际象棋世界冠军卡斯帕罗夫，还有在2016年，阿法狗在整个天下都未曾有敌手，这些皆是运用了人工智能的方式。

人工智能战胜人类的过程

除掉围棋之外，人们还对其他几种棋类游戏的复杂度做了估算，情况如下表所示。你会发觉井字棋的情形特别少，所以极易成为大师，要是两位大师碰到一块儿，那就只能是和棋。五子棋的情况稍微多些，不过只要玩得多，也能够发现套路，进而成为大师，无禁手时先手必定获胜。诸如国际象棋、中国象棋，围棋的复杂度更高。

军棋

刚才，我们所讨论的那几种棋，其复杂度存在差异，然而，它们均属于明棋，这就是说，博弈的双方，都对当下的局势，清清楚楚，明明白白。像这样的棋，存在最优解，谁与最优解更为接近，谁此人的棋术，便更为高超，在不出意外的情形之下，棋术较低之人，绝对没有可能赢棋术较高之人，就如同我与阿法狗进行围棋对弈，那是绝对赢不了的。

然而，存在一些棋类，那些下棋之人并不清楚全部棋子的情形。有时，鉴于运气佳，棋艺欠佳的人也能够战胜棋艺精湛的人，如此便给游戏增添了诸多乐趣。这类暗棋属于不完全信息博弈。

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

军棋

两方都有25个棋子，司令能够吃掉军长，军长能够吃掉师长，工兵能够挖出地雷，挖完地雷扛起军旗便获胜了。军棋存在多种玩法，有一种玩法为：在开局前，需暗自进行排兵布阵，将自身的25个子放置在25个位置上面，使得对方无法看见。两个子相遇时，由裁判判定谁吃掉谁。故而双方都不清楚对方的棋子究竟是什么。我小时候格外喜爱玩军棋，运气佳的时候自己的司令吃掉了敌方的军长，或者敌方司令踩到了我的地雷，我就会特别开心。

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

信息集的规模展现出全部未知信息的可能性数量，举例而言，当我与张三进行对局之时，我明白张三仅仅拥有10种排兵布阵的方式，然而我并不清楚他采用了其中的哪一种，在此种情形下，信息集的规模便是10。

所有已知信息的可能数，是由信息集的个数加以表示的。就有如，我自身仅仅会 5 种开局阵型，那么我的信息集个数即为 5。

大家伙儿琢磨琢磨，当我同张三进行对局之际，那局面存在着多少种可能性？是不是五十种？是不是把信息集的大小和信息集的个数相乘就行？事实上要是两人相互对垒，双方各自都拥有二十五个子，将它们排列到自身的二十五个兵站上，在开局的时候军棋的信息集的大小以及个数均为二十五的阶乘，也就是一.五乘以十的二十五次方种（把重复的子忽略掉）。

军棋棋盘

此时，我们已从单一维度的那种局面状态，转变成为在两个维度下了，这两个维度分别是信息集大小以及信息集个数。其中，信息集大小所代表的是未知可能性的集合德信竞技，表示未知可能性情况的集合，而信息集个数代表着已知局面的总状态数。此外，不完全信息博弈有一种复杂度，这种复杂度是体现在两个维度方面的。

麻将

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

麻将

有种类似暗棋称为麻将，它有34种牌，每种有4张，总共是136张牌，开局时四方中的各方各自抓取13张牌，每一轮抓取一张牌之后再打出一张牌，最后要是剩下14至16张并且还没有任何人胡牌，那就算流局，我们清楚自己手里所拿的牌，然而不清楚别人手里的牌以及自己和其他人接下来将会抓到的牌，所以它属于不完全信息博弈，是暗棋。

咱们具体来算算信息集个数和信息集大小：

第一轮

第二轮

……

于麻将的结尾阶段，当剩余的牌数介于14至16张时便会出现流局此类状况，因而最多可进行大约17轮的游戏行为。针对此情形，遵循如此这般的方式方法，将这17轮所涉及的信息集个数以及信息集大小全部予以罗列呈现，其结果如下表所示。

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

用图表更清晰一些：

在打牌的过程当中，你会察觉到，随着打牌的持续推进，信息集的数量会逐渐地变得越来越大，这意味着，我所能观察到的、具备可能性的局面数量会不断增多。与此同时，信息集的规模会渐渐变得越来越小，这也就表明，我所未知的局面的可能性会越来越少。

能够计算得出：于麻将里，信息集的总体数量大概是大概是10115，此即我们打麻将之际，所能见到的状态总数上限。针对每一个局面而言，信息集的平均规模大概是1049，亦即是我们所不知晓的、他人手中牌的可能组合情况。借助信息集总数乘上平均信息集大小那般的方式，能够估算出麻将的状态复杂度，大概是10^165。

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

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

你将会发觉：井字棋，国际跳棋，中国象棋，国际象棋，还有围棋，鉴于全然不存在不确定性，其信息集大小是1，仅仅只有信息集个数这一个维度，像我们方才所讲的那般，这些棋类都具备最优策略。

然而，麻将、桥牌以及德州扑克，在自己所拿到的牌存在诸多变化情况之外；就算目睹了相同的局面，他人还有诸多可能的牌；它们包含两个维度，属于不完全信息博弈。相比之下，麻将相较于德州扑克以及桥牌，其信息集的大小要大出许多；这表明麻将的不确定性更为突出，运气在麻将当中更为关键。

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

麻将存有诸多变化以及不确定性，能使一名普通选手也有战胜大师的可能，偶发的意外之喜，才致使许多人上瘾，打麻将需顺势而行，不管你牌术多么厉害，都存在无法操控牌局走向的可能。比如说，倘若你打麻将一心只想胡清一色，那么极有可能会输上一整晚。

打麻将是这样，生活又何尝不是呢？