时间：2022-12-18 20:46:01
很多伙伴喜欢象棋、围棋、扑克牌等棋牌游戏…你有没有想过，当你和对手厮杀的时候，这些游戏是否有必胜之策？
如果你偶然在洞穴里发现秘籍，获得某种棋牌必胜型，那该是多么“光荣”。 今天，我们来讨论一下这个问题。
策梅罗定理
首先，将博弈分为完全信息博弈和不完全信息博弈两种。 如果所有参与者都能在游戏的任何阶段知道过去和现在的所有游戏信息，这种游戏就称为完全信息游戏。 否则，称为不完全信息博弈。
例如，象棋、围棋、五子棋，大家都能看到对方是怎么走的。 这就是完全信息博弈。 但是，军棋却不是这样。 ——四国军手不知道对方排兵的布局，甚至不知道自己的棋子在哪里。 特朗普不知道对方手里的牌。 麻将不仅不知道对方手里的牌，还不知道桌上剩下的牌。 军手、扑克牌、麻将这样的游戏被称为不完全信息游戏。
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先生选择下面。 最终的游戏是国际象棋。
游戏越复杂，分支点就越多，长度也就越长，但如果从最后一个子游戏倒推几级，就可以推测游戏是先下手为强、后下手赢、还是和棋赢这样的胜负是不可避免的。
例如：五子棋：双方轮流下一子，五子接续获胜。 我们知道先手有必胜之法。 为了使游戏公平，设计了三三禁手、四四禁手、长连禁手，先手出禁手则输。 与五子棋相比，中国象棋、围棋的规则相当复杂，但仍然是两人的完全信息游戏。
在没有禁手的情况下，五子棋两种先手必胜开局
虽然我们不知道最好的策略是什么，但我们确信一定会有这样的策略存在，只要双方实行该策略，就一定会先下手为强，或者后手取胜，或者一定是和棋。 但是，为什么没有听说过谁掌握了将棋和围棋的必胜法呢？
井字将棋
举最简单的——井架将棋进行说明。
井架很简单。 先画井架，再先手画叉，后手画圆，在九个格子里交替画。 有人的个子横着连成一条直线，有人赢了。 如果画满了，双方都没赢，那就是日本围棋。 例如，接下来是先手赢的井字围棋局。
井架将棋牌局
这个游戏的规则很简单，但可玩性很高。 那是因为实际上也有很多变化。 准确地说，应该称为游戏的复杂性。
首先，讨论游戏状态的复杂性。 这说明了这块板上有多大的可能性。 一般情况下，不能正确计算游戏状态的复杂性，很多情况下不需要正确计算，只需要估计上限或估计订单即可。
例如：井架将棋：每个方格有叉、圆、空白三种可能，共有9个方格，所以最多能出现的棋局也不超过39=19683种。 这里面有很多不符合规则的情况，比如叉子的数量是和圈一样还是多一个。 对称的情况，实际上应该看作一种情况。 如果去掉所有这些不符合和对称性，最终剩下的状态数为765种——，在井架象棋中只能看到这765种局面。
状态数并不是衡量游戏复杂性的唯一方法。 因为同一个局面的状态可以从不同的路径中得到。 要调查游戏玩法的总数，必须计算游戏树的大小。
井架将棋游戏树的一部分
请看。 先手画第一个叉子的时候，没有了对称性，其实只有中间、边的中点、角三种画法。 这是树的一楼，有三个分支。
如果先手在中间画叉，失去了对称性，后手的环只有角和边的中点两种画法。 先手画在边或角上时，后手分别如图所示有5种画法。 这是树的第二层，有12根树枝。
之后，游戏有很多层，每层又有很多分支，到最后要么谁赢，要么下国际象棋。 游戏树中有多少个不同的路径表明了整个游戏中有多少种可能的变化。
在井架游戏中，可以推测游戏树的复杂性。 先手先选择位置，有九种可能性。 后手只剩下8种可能性，先手只剩下7种可能性…直到最后都填满了9个格子，所以游戏树的复杂度在9以下！=362880种。 这里面有很多不符合规则的东西。 例如，已经有一方赢了，不需要再下车，需要消除重复和对称。 最终游戏树的复杂度是26830。
人们已经考察了井架围棋的所有26830条路径，发现只要双方采用最优策略，井架围棋一定是日本围棋。
先手最佳对策
这样完整地绘制游戏树并找到最佳策略的游戏称为已解决游戏。 尽管如此，大多数情况下，井字将棋都会输。 这是因为有些人很擅长游戏树，有些人很差劲。
后手的上策
如果对方失误的话，很了解游戏树信息的人就能迅速抓住这个漏洞，把做不到的人逼到必败游戏树的分支。 这就是大师和初学者的区别
围棋
其实，象棋和围棋的本质与井架没有本质上的不同，但复杂度比井架高得多
围棋
以围棋为例，围棋在19x19=361的方格中交替放置棋子，所以每个方格有黑白天空三种可能性。 围棋棋盘整体状态数的上限为3361=1.7x10172，消除了重复和对称，围棋状态的复杂度约为10171级。
要知道，宇宙中的原子数量只有大约1080个，无论是用宇宙中的一个原子来表示围棋的局面，还是囊括宇宙中所有的原子都不能表示围棋的所有局面。
围棋游戏树更难画。 围棋是可以进球的，有空白的话就可以继续，所以并不一定填了盘就结束了。 但是，你可以估算游戏树的总层数和每层的平均点。 据统计和计算，围棋一局棋平均步数为150步，每局棋平均步数为250种，因此围棋整体游戏树的复杂度约为250(10360 )。
理论上，如果调查了10360种情况，就可以知道围棋的结局是先手必胜，还是后手必胜，或者一定是和棋。 但这个计算量真的太多了。 世界上最快的计算机富岳每秒最高可以计算100亿次浮点运算。 如果一次浮点运算可以计算一个路径，那么计算所有围棋游戏的可能性需要10342秒，宇宙的年龄为138亿年，大约只有1017s。
显然围棋一定有上策，但不能计算这个上策。 但是，数学家们也找到了一些其他的方法。 不用遍历所有情况，也能找到比较好的取胜方法。 例如，1997年深蓝战胜国际象棋世界冠军卡斯帕罗夫，2016年阿法狗咬定天下无敌手，也是采用人工智能的方法。
人工智能战胜人类的过程
除了围棋以外，如下表所示，还推测了其他几种国际象棋游戏的复杂性。 井字棋情况特别少，所以你会发现很容易成为大师。 两个大师相遇的只有日本围棋。 五子棋的话有点多，但是多玩的话，就能找到模子，成为大师。 没有禁手的话先手必胜。 像国际象棋和中国象棋一样，围棋的复杂性更高了。
军手
刚才讨论的几招，虽然复杂不同，但都是明确的招，也就是说游戏双方对当前的形势都很了解。 这样的手有最佳解。 要说谁接近最佳解，谁的棋术都很高。 意外的是，棋艺低的人绝对不可能战胜棋艺高的人。 例如，即使我和阿法狗下围棋，也绝对赢不了。
但是，有些下国际象棋的人不知道所有的棋子。 运气好，象棋不好的人也能战胜象棋好的人。 这给游戏带来很多乐趣。 这样的暗手是不完全信息博弈。 例如，大家还记得军棋吗？
军棋
双方各有25个棋子，司令能吃军长，军长能吃师长，工兵能挖地雷，挖完地雷扛军旗就赢了。 象棋有各种各样的玩法，其中之一是在开局之前，必须暗中排兵，把自己的25个子放在25个位置，不让对方看到。 两个人的背影相遇，裁判判断谁吃谁。 所以双方都不知道对方的棋子是什么。 我小时候很喜欢军棋。 运气好的时候自己的司令官吃敌人的军长，敌人的司令官踩地雷，我会很高兴。
你怎么解释军棋的复杂性？ 需要信息集这个概念。
信息集的大小表示所有未知信息的可能性数量。 例如，我和张三对局，张三只知道10种排兵布阵的方法，但我不知道他选了哪一种。 此时，信息集的大小为10。
信息集的数量表示所有已知信息的可能性数量。 比如说我自己只能做五种开局阵型，那么我的信息集数量是5。
想想看。 我和张三对局时，局面有几种可能？ 应该是50种吧？ 信息集的大小乘以信息集的个数就可以了。 实际上在两人对战的情况下，双方各有25人的背影，在自己的25个兵站并排，开局时的军手信息集的大小和个数都是25！=1.5x1025种(忽略重复的子项)。
将棋盘
现在，我们从单维的局面状态
现在是信息集大小和信息集数量
变成了二维
信息集大小表示未知可能性的集合
信息集的个数表示已知局面的总状态数
不完全信息博弈具有两个维度的复杂性
打麻将
来看看我们的“国粹”。 我打麻将。
麻将也是一种黑暗将棋。 34种卡片，每种4张，共136张卡片。 开局时四面各抓13张，一轮各打一张再打一张，如果最后剩下14~16张还没有胡牌，可以出局。 我们知道自己手里的牌，但不知道对方的牌，也不知道公共牌池里的牌，是不完全信息游戏，是暗手。 具体来说，计算一下信息集的个数和信息集的大小吧。
麻将
第一回合
信息收集个数：麻将牌共有136张，我拿起13张牌，不考虑重复，有我拿到的牌的可能方法的数量。
情报集的大小：除了我手里的13张卡之外，还有123张卡，剩下的3个玩家各有13张，所以有可能是未知的。
第二周
信息收集的数量(在第一回合中，4名玩家分别玩了一张。 麻将共有34种，所以扑克牌的方法数量共有344种。 此时，我手里还有13张牌，方法有数，所以现在有我可能面临的局面。
情报集的大小：除了我手里的13张和上一轮打出的4张之外，还有剩下的119张卡。 三只手里还有13张卡。 数一下。
……
麻将最后用剩下的14~16张卡进行交战，所以最多可以玩17次左右。 使用此方法列出这17次信息集的个数和信息集的大小，如下表所示。
麻将每轮信息集的个数和大小
用图表更清晰：
可以看出，随着扑克牌的发展，信息集的数量会变大。 也就是说，我能观察到的可能局面数量在增加。 情报集的大小越小，也就是说我未知局面的可能性越来越小。
麻将中，信息收集的总个数约为10115，可以计算出这是打麻将时能看到的状态的总数的上限。 对于每个局面，信息集的平均大小约为1049，也就是我们未知的、他人手中的卡的可能组合。 将信息集的总数乘以平均信息集的大小，可以推测麻将状态的复杂度约为10￣165。
微软亚洲研究院曾经比较过几种棋牌游戏状态的复杂性。 在此图中，垂直轴表示信息集的大小，即不确定性； 横轴表示信息组的个数，也就是卡片部分的变化。
参考微软亚洲研究院绘制的棋牌复杂度图
由于井字棋、国际象棋、中国象棋、国际象棋、围棋完全没有不确定性，所以信息集的大小为1，可以看出有信息集个数的维度。 正如我刚才所说，这些国际象棋类有最佳策略。
另一方面，麻将、桥牌、德克萨斯扑克除了自己拿到的牌有各种各样的变化外，即使看到了同样的局面，其他人依然有很多可能性的牌。 它们是不完全信息博弈，有两个维度。 相比之下，麻将比桥牌和德克萨斯扑克的信息集大小要大得多，麻将的不确定性更高，表明运气在麻将中更重要。
只要游戏存在两个维度，存在不确定性，一般就没有必胜之策。 很明显，只要我的牌打得足够好，不管水平多高，打麻将也有很大概率输。 计算麻将等不完全信息博弈问题上的计算机进度明显落后于将棋围棋。
许多游戏都有丰富的变化和不确定性
普通选手也可能战胜高手
意外的喜悦
可能是游戏的魅力
与游戏相比
生活充满了更多的可能性，想得更多，选择更多未来的路，一定会更坚定。
结束
编辑：孟丽君
校正：陶铮
审校：余治国
来源：李永乐老师
关注“青春深圳”微信、嘀嘀打车、快手、B站、视频号码
