通过数学归纳法可以证明二人棋类游戏的不败之法？ - 我思我在


	天宫公主 (司徒家的颖颖)


	虞国公主 ★

组别	限制发言用户
级别	大将军
好贴	6
功绩	517
帖子	11552
编号	1037
注册	2004-10-25
来自	天津
家族	司徒实业

#1

发表于 2010-1-8 15:05 资料主页短消息看全部作者

回复 #1 dimeterio 的帖子

证明起来很简单啊。。。几乎靠扣定义就可以了。。。

假设有两个玩家：I 和 U（博弈论中对玩家最常用的字母。。。呵呵）。由于游戏在有限步内结束，那么我们便把 A_0 定义为游戏结束时的盘面，显然至少有一方处于不败态（不败态的定义是，从此之后不可能失败），不妨架设不败着为 I。

那么假设 A_k 为游戏还有 k 步结束时的盘面，且玩家 I 在 A_k 的盘面下不败，那么 I 在 A_{k+1} 的盘面下也必然不败。因为如果在 A_{k+1} 的盘面下 I 处于失败态，那么 U 在 A_{k+1} 的盘面下，必然有对 I 有一套必胜策略。一个足够聪明的玩家 U 在有必胜策的情况下，必然能导致 I 在 A_k 的状态仍然处于必败态。矛盾！因此，I 在 A_{k+1} 的盘面下，必然处于不败态。由于游戏需要在有限步内完成，由数学归纳法，I 在游戏最开始就必然处于不败态了。

证毕。

另，这个定理在围棋，象棋和国际象棋都适用。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	天宫公主 (司徒家的颖颖)


	虞国公主 ★

组别	限制发言用户
级别	大将军
好贴	6
功绩	517
帖子	11552
编号	1037
注册	2004-10-25
来自	天津
家族	司徒实业

#2

发表于 2010-1-8 22:44 资料主页短消息看全部作者

回复 #4 dimeterio 的帖子
如果一种棋有可能出现无限步，则我的那个证明对它并不成立。如果一种棋允许无限步的话，我们甚至可以构造出一种既输既赢的状态出来（注，不是不输不赢的平局，而是双方既输既赢！）。

回复 #5 墨叶的帖子
楼主说的这个定理在博弈论中的意义是很深远的，很多博弈命题证明的关键一步都要用到它。

回复 #7 ukyo007 的帖子
能 Pass 没问题啊，Pass 本身也算一步棋，而且完全符合我三楼证明的假设。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	天宫公主 (司徒家的颖颖)


	虞国公主 ★

组别	限制发言用户
级别	大将军
好贴	6
功绩	517
帖子	11552
编号	1037
注册	2004-10-25
来自	天津
家族	司徒实业

#3

发表于 2010-1-9 00:58 资料主页短消息看全部作者

QUOTE:

原帖由 zhouhuan 于 2010-1-8 23:25 发表
能不能把必不败之法改为必胜之法？

能，前提是游戏没有平局。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！