标题: 通过数学归纳法可以证明二人棋类游戏的不败之法？ [打印本页]
作者:
dimeterio 时间: 2010-1-8 13:32 标题: 通过数学归纳法可以证明二人棋类游戏的不败之法？
从维基上看到的：在博弈论中，可以通过数学归纳法可以证明如下定理：任何能在有限步内结束的二人棋类游戏，都必定存在着一方有必不败之法。
哪位能给出证明？
三大棋能够归入“有限步内结束的二人棋类游戏”的范畴吗？
作者:
KYOKO 时间: 2010-1-8 14:02
恩 这主题我看射虎更合适一点吧
“有限步数内结束”这也正是我想问的，拥有“无限步数”是怎样一个概念呢
作者:
天宫公主 时间: 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 时间: 2010-1-8 18:07 标题: 回复 #3 天宫公主 的帖子
关于证明过程还在研究中。
关于第二个问题却有很大的疑问，三大棋中，象棋禁止长将，围棋禁止全局同型再现，因此属于外力规则约束而形成的“有限步数内结束”，如果取消外力约束，能否适用这个结论呢？
国象不禁止长将，长将和棋，属于双方不败，不过不知道有无先行策略避免长将。
作者:
墨叶 时间: 2010-1-8 18:32 标题: 回复 #4 dimeterio 的帖子
没意义。因为不可能算清楚所有的变化。
五子棋有必胜开局。
而围棋、象棋都不可能，变化太多了。
残局是可能计算清楚。
作者:
zhouhuan 时间: 2010-1-8 19:10
无限步数不就是双方均处于不败态么
作者:
ukyo007 时间: 2010-1-8 22:05
围棋可以PASS，所以理论上说可以有无限步，那就不适合题目了
作者:
天宫公主 时间: 2010-1-8 22:44
回复 #4 dimeterio 的帖子
如果一种棋有可能出现无限步，则我的那个证明对它并不成立。如果一种棋允许无限步的话，我们甚至可以构造出一种既输既赢的状态出来（注，不是不输不赢的平局，而是双方既输既赢！）。
回复 #5 墨叶 的帖子
楼主说的这个定理在博弈论中的意义是很深远的，很多博弈命题证明的关键一步都要用到它。
回复 #7 ukyo007 的帖子
能 Pass 没问题啊，Pass 本身也算一步棋，而且完全符合我三楼证明的假设。
作者:
zhouhuan 时间: 2010-1-8 23:25
能不能把必不败之法改为必胜之法？
作者:
天宫公主 时间: 2010-1-9 00:58
原帖由 zhouhuan 于 2010-1-8 23:25 发表
能不能把必不败之法改为必胜之法？
能，前提是游戏没有平局。
作者:
harp 时间: 2010-1-12 07:25
没有平局，而且不做倾向性约束，就是先手者必胜吧。
作者:
Sphynxyu 时间: 2010-1-15 09:12
原帖由 天宫公主 于 2010-1-8 15:05 发表
证明起来很简单啊。。。几乎靠扣定义就可以了。。。
假设有两个玩家：I 和 U（博弈论中对玩家最常用的字母。。。呵呵）。由于游戏在有限步内结束，那么我们便把 A_0 定义为游戏结束时的盘面，显然至少有一方 ...
不同意。
证明没问题，但是请问围棋，象棋和国际象棋是有限步内结束的吗？恐怕不一定吧？围棋找3个地方不停的轮流打吃，象棋更是简单，有平局就说明无法结束。。。。。
基本问题都不对，三大棋不能够归入“有限步内结束的二人棋类游戏”的范畴吗。
| 欢迎光临 轩辕春秋文化论坛 (http://xycq.org.cn/forum/) |
Powered by Discuz! 5.0.0 |