五子棋先手必胜

        五子棋作为一种老少皆宜的游戏，不仅是阖家欢乐的助手，更是上班摸鱼的利器。智慧的人们早已知道：无论有无禁手，五子棋都是一种先手必胜的游戏。那什么样的游戏会有必胜策略，它们又为什么会有必胜策略呢？
        我们先考虑一个简单的游戏，但它与五子棋有着相同的本质：
        地上有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的过程。
        不管怎么说，五子棋依然是阖家欢乐的助手，也是上班摸鱼的利器！