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


	dimeterio (李秀辰)

组别	校尉
级别	镇西将军
好贴	1
功绩	45
帖子	3985
编号	266634
注册	2008-2-7

#1

发表于 2010-1-8 13:32 资料个人空间短消息只看该作者

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

从维基上看到的：在博弈论中，可以通过数学归纳法可以证明如下定理：任何能在有限步内结束的二人棋类游戏，都必定存在着一方有必不败之法。

哪位能给出证明？

三大棋能够归入“有限步内结束的二人棋类游戏”的范畴吗？

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


	KYOKO (★御姐控★)


	唐国公荆南节度使 ★★

组别	节度使
级别	大将军
功绩	1456
帖子	65615
编号	32
注册	2003-8-19
来自	BWL

#2

发表于 2010-1-8 14:02 资料个人空间短消息只看该作者

恩这主题我看射虎更合适一点吧

“有限步数内结束”这也正是我想问的，拥有“无限步数”是怎样一个概念呢

[广告] 真诚支持说岳，携手共创辉煌


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


	虞国公主 ★

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

#3

发表于 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 在游戏最开始就必然处于不败态了。

证毕。

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

[广告] 真诚支持说岳，携手共创辉煌


	dimeterio (李秀辰)

组别	校尉
级别	镇西将军
好贴	1
功绩	45
帖子	3985
编号	266634
注册	2008-2-7

#4

发表于 2010-1-8 18:07 资料个人空间短消息只看该作者

回复 #3 天宫公主的帖子

关于证明过程还在研究中。

关于第二个问题却有很大的疑问，三大棋中，象棋禁止长将，围棋禁止全局同型再现，因此属于外力规则约束而形成的“有限步数内结束”，如果取消外力约束，能否适用这个结论呢？

国象不禁止长将，长将和棋，属于双方不败，不过不知道有无先行策略避免长将。

[广告] 《精忠报国岳飞传完整版》火热发布


	墨叶


	★★★★ 节度留后虎豹骑

组别	虎豹骑
级别	大将军
功绩	359
帖子	23258
编号	97330
注册	2006-12-26
家族	轩辕少林寺

#5

发表于 2010-1-8 18:32 资料个人空间短消息只看该作者

回复 #4 dimeterio 的帖子

没意义。因为不可能算清楚所有的变化。

五子棋有必胜开局。
而围棋、象棋都不可能，变化太多了。
残局是可能计算清楚。

[广告] 真诚支持说岳，携手共创辉煌


	zhouhuan (神鸟)


	光禄大夫白衣伯爵 ★

组别	虎豹骑
级别	安南将军
好贴	1
功绩	233
帖子	2822
编号	89468
注册	2006-10-30

#6

发表于 2010-1-8 19:10 资料个人空间短消息只看该作者

无限步数不就是双方均处于不败态么

[广告] 《精忠报国岳飞传完整版》火热发布


	ukyo007

组别	士兵
级别	仁勇校尉
功绩	2
帖子	151
编号	306901
注册	2009-1-21

#7

发表于 2010-1-8 22:05 资料短消息只看该作者

围棋可以PASS，所以理论上说可以有无限步，那就不适合题目了

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


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


	虞国公主 ★

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

#8

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

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

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

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

[广告] 《精忠报国岳飞传完整版》火热发布


	zhouhuan (神鸟)


	光禄大夫白衣伯爵 ★

组别	虎豹骑
级别	安南将军
好贴	1
功绩	233
帖子	2822
编号	89468
注册	2006-10-30

#9

发表于 2010-1-8 23:25 资料个人空间短消息只看该作者

能不能把必不败之法改为必胜之法？

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


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


	虞国公主 ★

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

#10

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

QUOTE:

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

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

[广告] 《精忠报国岳飞传完整版》火热发布


	harp

组别	士兵
级别	忠义校尉
功绩	3
帖子	286
编号	283766
注册	2008-6-25
来自	东都伊阙

#11

发表于 2010-1-12 07:25 资料短消息只看该作者

没有平局，而且不做倾向性约束，就是先手者必胜吧。

[广告] 真诚支持说岳，携手共创辉煌


	Sphynxyu

组别	校尉
级别	左将军
好贴	1
功绩	20
帖子	1229
编号	30540
注册	2005-1-18

#12

发表于 2010-1-15 09:12 资料主页文集短消息只看该作者

QUOTE:

原帖由 天宫公主 于 2010-1-8 15:05 发表
证明起来很简单啊。。。几乎靠扣定义就可以了。。。

假设有两个玩家：I 和 U（博弈论中对玩家最常用的字母。。。呵呵）。由于游戏在有限步内结束，那么我们便把 A_0 定义为游戏结束时的盘面，显然至少有一方 ...

不同意。
证明没问题，但是请问围棋，象棋和国际象棋是有限步内结束的吗？恐怕不一定吧？围棋找3个地方不停的轮流打吃，象棋更是简单，有平局就说明无法结束。。。。。
基本问题都不对，三大棋不能够归入“有限步内结束的二人棋类游戏”的范畴吗。

[广告] 真诚支持说岳，携手共创辉煌