策梅洛定理 (博弈论): Zermelo's theorem

很有意思的一个定理。

转载地址为http://blog.sina.com.cn/s/blog_4b91d3b501010hcj.html

策梅洛定理（英语：Zermelo's theorem）是博弈论的一条定理，以恩斯特·策梅洛命名。定理表示在二人的有限游戏中，如果双方皆拥有完全的资讯，并且运气因素并不牵涉在游戏中，那先行或后行者当中必有一方有必胜/必不败的策略。若应用至国际象棋，则策梅洛定理表示'要么黑方有必胜之策略、要么白方有必胜之策略、要么双方有必不败之策略'。

策梅洛的论文于1913年以德文发表，并被Ulrich Schwalbe和Paul Walker于1997年译为英文。

 

定理具体内容：

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

0. 双人轮流行动

1. 有限步。比如国际象棋好像重复出现三次相同的棋局判和

2. 信息完备。所谓信息完备，大概是玩家明确知道所有之前的步骤。

3. 仅有3种结局，对于玩家1只有：赢，和，输三种结局

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

1. 玩家1有必胜招。就是玩家1按照某种特定的走法，不论玩家2如何努力，玩家1都可以赢

2. 玩家1有必和招。

3. 玩家2有必胜招。

当然，有些游戏是有后手优势的，先走的人倒霉。 

证明方式就是传说中被很多人认为stupid的数学归纳法（Induction）。

 

Zermelo's theorem的证明大意：

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

 

• 数学归纳法第一步：

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

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

 

• 数学归纳法第二步：

假设i<=N时命题成立，试图证明i=N+1时命题成立

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

 

• 数学归纳法第三步：

总结：该结论对于所有的正整数都成立。