五子棋先手必胜

奇闻趣事 2023-03-20 20:16www.nkfx.cn奇闻趣事
        五子棋作为一种老少皆宜的游戏,不仅是阖家欢乐的助手,更是上班摸鱼的利器。智慧的人们早已知道无论有无禁手,五子棋都是一种先手必胜的游戏。那什么样的游戏会有必胜策略,它们又为什么会有必胜策略呢?
        我们先考虑一个简单的游戏,但它与五子棋有着相同的本质
        地上有12个苹果,甲乙两人轮流拿,甲先拿,每人每次只能拿1个或2个,谁拿走一个苹果就胜利
        稍微一想就能明白这个游戏是后手必胜的如果甲拿1个乙就拿2个,甲拿2个乙就拿1个,就可以保证乙一定拿到编号为3的倍数的苹果。
        这个游戏和五子棋有什么相同点呢?
        (1)有两个玩家,依次轮流动手
        (2)每步的选择数有限,且有限步后能分出胜负,或者平局
        (3)每个玩家都知道对方和自己的所有动作(完全信息)
        (4)全过程没有随机性
        可以证明符合(1)-(4)的一切游戏都是先手必胜,或后手必胜,或双方都有不败策略的。
        这个结论并不是一句废话,它虽然并不能告诉我们一个特定的游戏是先手必胜,还是后手必胜,还是一定平局,但它阐述了一种存在性一定有必胜或不败策略。如果让两个顶级AI互相博弈,结果一定是某一个AI一直输,或者一直平局,具体是哪种取决于游戏设定。
        第一眼看时,这个结论似乎非常强,因为包括五子棋、跳棋、围棋、象棋在内的一摞游戏都是满足这些条件的,也就是说它们都有不败策略(具体是先手还是后手需要额外讨论)。但仔细一品,其实也在意料之中,因为这些条件还是比较强的,特别是(ii)直接要求了空间有限。对于一个有限的东西,有不败策略其实并不十分惊奇,这个结论的证明也特别简单!
        暂且不允许平局(其实加入平局情况对证明完全无影响),因为这个游戏的一切走法都能分出胜负而且长度有限,可以找出一条最长的,我们对这个长度N做归纳
        N=1,即游戏中先手一动,游戏就结束且分出胜负,后手甚至没机会动手。在这样的游戏中,如果先手能赢,那他就去赢,这个游戏是“先手必胜”的,记为W;如果先手不能赢,那它就是“后手必胜”的,记为L
        假设N<=n时游戏都有必胜策略
        N=n+1时,第一步时先手有m(<∞)种走法,每种走法都会导致一个“残局”(子游戏),而这个子游戏的长度显然不超过n. 由归纳假设,每个子游戏都是W或L的。如果这些子游戏中有L,那就选这个分支,导致“父游戏”先手必胜(注意父游戏中的先手在子游戏里就是后手了);如果这些子游戏全是W,那父游戏先手必败。父游戏也是W或L的
        行吧,那咱就证完了。
        值得一提的是,100年前人们就已经知道这个结论了,后来还在两个方面有所升华1. 考虑无限!一切都要无限;2. 知道有不败策略后,能不能得到不败所需要的走法长度的上界?这些研究大多是作为集合论的应用而出现的,具体可参考《Zermelo and the Early History of Game Theory》。我们证明的这个结论,仅仅只是Zermelo's theorem的一个羸弱版本。
        在概率游戏中,人们通常不太愿意玩明显不公平的游戏,这些有着不败策略的棋类游戏却始终生生不息,原因也很显然啦虽然状态空间是有限的,但还是太大了,除了存在性外,我们对不败策略几乎一无所知。很多游戏都是在一个有限但很大的空间里去找东西或者对弈,它们大多经历了一个从AI模仿人类到人类模仿AI的过程。
        不管怎么说,五子棋依然是阖家欢乐的助手,也是上班摸鱼的利器!

Copyright © 2016-2025 www.nkfx.cn 趣谈网 版权所有 Power by