双人游戏的必胜招

该篇复习于2011年. 今天看到如月中天提到"胜也罢，败也罢，就是不要同他讲和！", 不知怎么, 突然想起这个双人游戏是可能有必胜招的, 还有一个华丽的证明, 然后自己又不记得了. 赶紧搜索了一下, 发现以前记录过.

zermelo's theorem 实在太帅了。看了耶鲁公开课博弈论第15集，终于揭开了从大一开始困扰我的谜题。大一的时候舒幼生教授一次很淡定的说，一个双人棋类游戏，如果没有平局，那么一定有必胜招。当时我就很迷惑，但他没给出证明。过了13年，我终于见到了证明。实在激动，记录一下。

zermelo's theorem

这个定律的全名叫做zermelo's theorem。具体描述是：

在一个双人游戏中，满足：

• 双人轮流行动
• 有限步。比如国际象棋好像重复出现六次相同的棋局判和
• 信息完备。所谓信息完备，大概是玩家明确知道所有之前的步骤。
• 仅有3种结局，对于玩家1只有：赢，和，输三种结局

当满足上述条件的游戏，只会出现下面情况之一：

• 玩家1有必胜招。就是玩家1按照某种特定的走法，不论玩家2如何努力，玩家1都可以赢
• 玩家1有必和招。
• 玩家2有必胜招。当然，有些游戏是有后手优势的，先走的人倒霉。

这个定律的证明相当华丽，建议每一个理科geek前去欣赏，可自行google "公开课 博弈论 15"查看视频.

证明

在此简单记叙一下，权作笔记。

N是某一游戏的最大步长，比如我们下棋，玩很多很多次，其中最多回合的一次，是大战300回合后我赢了，那么N=600。

数学归纳法第一步：

N=1时，zermelo's theorem显然成立。

玩家1，只用走一步，就可决定输赢。按照游戏的规定，也许有胜负和三种，那么玩家1显然选择胜的走法，于是满足玩家1有必胜招

数学归纳法第二步：

假设i<=N时命题成立

数学归纳法第三步：

试图证明i=N+1时命题成立

考虑N+1时的子游戏，除去玩家1走的第一步以后的游戏部分。玩家1第一步的每一种走法都会产生一个新游戏起始状态，它的最大步长<=N的，从数学归纳法第二步可知，每个子游戏有唯一确定的结果，玩家1必然会赢、输或者和。于是等价于N=1的情况了！相当于玩家1在第一步的时候来选择进入哪个游戏，是自己必赢还是必输还是必和。

这个证明的华丽之处在于，我在想N+1的时候，默认的想法是在游戏树后面再加一层，于是很多年都想不出来，而这个证明是在游戏树前面加上了一个树根。在看到这个证明之前，我根本就没有意识到自己有这样的思维定势。