2011年4月27日星期三

zermelo's theorem学习笔记

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

这个定律的全名叫做zermelo's theorem。具体描述是:
在一个双人游戏中,满足:
0. 双人轮流行动
1. 有限步。比如国际象棋好像重复出现六次相同的棋局判和
2. 信息完备。所谓信息完备,大概是玩家明确知道所有之前的步骤。
3. 仅有3种结局,对于玩家1只有:赢,和,输三种结局
当满足上述条件的游戏,只会出现下面情况之一:
1. 玩家1有必胜招。就是玩家1按照某种特定的走法,不论玩家2如何努力,玩家1都可以赢
2. 玩家1有必和招。
3. 玩家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的时候,默认的想法是在游戏树后面再加一层,于是很多年都想不出来,而这个证明是在游戏树前面加上了一个树根。在看到这个证明之前,我根本就没有意识到自己有这样的思维定势。

Posted via email from goldengrape's posterous

2011年4月10日星期日

混搭

总结下,一部分人类通过基因改良成为调整者,进入太空到各个星系,其中一部分人继续进化成为seed,能够控制原力成为Jedi,他们建立了回到过去建立了魔法世界,将普通人称为麻瓜


@gliceren: 有部分邪恶势力去了中土世界,建立了魔多


调整者中的seed Jedi之一的安纳金受到黑暗原力的诱惑,成为维德勋爵,建造了机器星球死星,又称赛博坦


死星或者赛博坦的操作系统叫做matrix,它的源代码压缩在一个戒指之中也掉落在中土世界


@gliceren: 为了监视戒指,正义力量在月球建立了他们的基地。当需要的时候他们以人类的面貌出现在地球拯救危难。虽然他们出现时的面貌不同,但口号是一样的“代表月亮消灭你”


但实际上这些是一个叫neo的石器时代人落入潜意识边缘的梦境,梦境中他活了几万年还保持35岁


neo在睡着之前,当然他那时还在石器时代,一直在思考一个问题,6*7=? 


===

填空题,上述故事涉及到那些作品,请按顺序填写:

____系列,

____系列,

____系列,

____系列,

____系列,

____系列,

____战士,

____空间,

这个男人来自____

____漫游指南

Posted via email from goldengrape's posterous