游客:
注册
|
登录
会员
|
搜索
|
统计
|
帮助
轩辕春秋文化论坛
»
我思我在
» 通过数学归纳法可以证明二人棋类游戏的不败之法?
兴唐传·瓦岗山异闻录(20150519版)发布
(2015-5-19)
论坛营运现状公告
(2014-8-10)
三国志12pk版下载
(2013-4-20)
《精忠报国岳飞传》制作组对外开放
(2013-1-16)
岳飞传解密剧本发布
(2011-4-12)
招募各版斑竹和网站管理技术人员
(2006-4-19)
<< 上一主题
|
下一主题 >>
投票
交易
悬赏
活动
打印
|
推荐
|
订阅
|
收藏
|
开通个人空间
|
加入资讯
标题: 通过数学归纳法可以证明二人棋类游戏的不败之法?
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 天宫公主 的帖子
关于证明过程还在研究中。
关于第二个问题却有很大的疑问,三大棋中,象棋禁止长将,围棋禁止全局同型再现,因此属于外力规则约束而形成的“有限步数内结束”,如果取消外力约束,能否适用这个结论呢?
国象不禁止长将,长将和棋,属于双方不败,不过不知道有无先行策略避免长将。
[广告]
安装Alexa工具条,提高轩辕排名,支持轩辕发展!
墨叶
★★★★
节度留后虎豹骑
组别
虎豹骑
级别
大将军
功绩
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,所以理论上说可以有无限步,那就不适合题目了
[广告]
真诚支持说岳,携手共创辉煌
天宫公主
(司徒家的颖颖)
虞国公主
★
组别
限制发言用户
级别
大将军
好贴
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
资料
个人空间
短消息
只看该作者
能不能把必不败之法改为必胜之法?
[广告]
《精忠报国岳飞传完整版》火热发布
天宫公主
(司徒家的颖颖)
虞国公主
★
组别
限制发言用户
级别
大将军
好贴
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个地方不停的轮流打吃,象棋更是简单,有平局就说明无法结束。。。。。
基本问题都不对,三大棋不能够归入“有限步内结束的二人棋类游戏”的范畴吗。
[广告]
安装Alexa工具条,提高轩辕排名,支持轩辕发展!
投票
交易
悬赏
活动
正在浏览此帖的会员 - 共
1
人在线
轩辕春秋文化论坛
轩辕史话
> 炎黄春秋
> 我思我在
> 法律探讨
> 三国史话
春秋文艺
> 古典小说
> 诗词歌赋
> 现代文艺
> 韦编三绝
> 对联雅座
> 滴翠亭
> 藏经阁
> 双七钟社
> 笑书神侠
> 辕门射虎
> 虎帐点兵
游戏人生
> 同人战棋手游
> 三国戏英杰传
> 三国鼎立
> 轩辕公会
> 三国志12
> 英雄史诗
> 运筹帷幄
> 人间五十年
> 步步为营
> 游行天下
> 游戏贴图
轩辕工作室
> 兴唐传·瓦岗山异闻录
> 豪华曹操传
> 精忠报国岳飞传
> 《精忠报国岳飞传》制作组
> 大一统演义
> 曹操传MOD作品交流
> 东吴霸王传
> 封神英杰传
> 杨家将
> 吕布传
> 三国无双战略版
> 北宋志·赵匡胤传
> 战旗春秋
> 曹操传MOD制作交流
> 金庸群侠传MOD交流
> 风华录
> 设计与修改
怡情岁月
> 影音经典
> 动漫先锋
> 绘画摄影
> 情感轩辕
> 衣食住行
> 体坛动力
> 谈股论金
> 水泊轩辕
参政议政
> 迎宾阁
> 鸿胪寺
> 登闻鼓
> 监造府
当前时区 GMT+8, 现在时间是 2025-1-2 22:29
京ICP备2023018092号
轩辕春秋
2003-2023 www.xycq.org.cn
Powered by
Discuz!
5.0.0
2001-2006
Comsenz Inc.
Processed in 0.010045 second(s), 9 queries , Gzip enabled
TOP
清除 Cookies
-
联系我们
-
轩辕春秋
-
Archiver
-
WAP
控制面板首页
编辑个人资料
积分交易
公众用户组
好友列表
基本概况
论坛排行
主题排行
发帖排行
积分排行
管理团队
管理统计