见招拆招，招招制敌！真有必胜法吗？

青春深圳 04-22 565

前言：

目前各位老铁们对“五子必胜算法是什么”可能比较珍视，我们都需要学习一些“五子必胜算法是什么”的相关文章。那么小编同时在网上搜集了一些关于“五子必胜算法是什么””的相关文章，希望看官们能喜欢，大家快快来学习一下吧！

许多小伙伴喜欢棋牌游戏

比如象棋、围棋、扑克…

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

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

这些游戏有必胜策略吗？

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

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

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

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

↓↓↓

策梅洛定理

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

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

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张牌，不考虑重复，我拿到的牌的可能方法数有种。