搏弈问题 - 辕门射虎 - 轩辕春秋文化论坛 20周年


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


	虞国公主 ★

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

#1

发表于 2005-8-29 02:25 资料主页短消息看全部作者

在一盘象棋里, 假设双方现在一次走两步, 而不是一次走一步. 求证先走方至少能够达成和棋.

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


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


	虞国公主 ★

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

#2

发表于 2005-8-29 20:09 资料主页短消息看全部作者

楼上和正解非常接近... 唯一漏掉的是, 你尚需证明, 对于先走方的确存在自己不会输的棋谱. 在经典象棋, 这个问题很难, 但在"两步象棋"却有一个很巧妙的证法.

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


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


	虞国公主 ★

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

#3

发表于 2005-8-30 11:04 资料主页短消息看全部作者

对... 命题就是要证明在两步象棋里, 对于先走方存在不败战术(i.e. 如果玩家足够理智, 不可能必败).

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


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


	虞国公主 ★

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

#4

发表于 2005-8-30 16:47 资料主页短消息看全部作者

QUOTE:

原帖由重阳于2005-08-30, 11:17:21发表
有点晕，加了括号里的话之后，怎么意思又有点偏回主贴了。

先手方不可能必败，说的是这个规则，和玩家是否理智没啥关系，除非这个玩家理智到能一路计算到棋局结束。

换一个任意游戏，为什么先走方不可能必败？

这里我们当然要假设玩家的理智。。。也就是说，如果玩家已经在必胜态，他有足够的水平不要把自己走成必败态。

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


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


	虞国公主 ★

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

#5

发表于 2005-8-31 02:28 资料主页短消息看全部作者

普通象棋是平庸问题? 不解... 难道谁已证明先走方开始就处于不败态么?

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


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


	虞国公主 ★

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

#6

发表于 2005-8-31 03:14 资料主页短消息看全部作者

但你的这个猜测并没有被数学证明过吧?

所谓数学证明, 是要一步一步的逻辑推理, 严密的说明了后走方没有任何一步棋可以扭转局势, 最终将死先走方.

我想这种严格的证明不可能有的, 要有的话, 估计就谁都甭下了.

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


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


	虞国公主 ★

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

#7

发表于 2005-8-31 04:27 资料主页短消息看全部作者

汗... 国际象棋电脑至今对人类大师也没构成执白不败... 离严格证明还远着呢.

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


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


	虞国公主 ★

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

#8

发表于 2005-8-31 12:32 资料主页短消息看全部作者

冰血: 在一个非随机搏弈里, 每个玩家在任何情况下, 都会处于:

A. 胜态(或者不败态, 看此游戏是否存在和棋的可能).
B. 败态.

在两步象棋中, 如过先走的开始是处于败态, 那么他可以连走两步而还原, 把败态交给对手. 如果先走处于胜态, 那么则存在一系列的招数, 使得对手从第一步棋开始, 就无法翻身.

但如过是普通象棋的话, 虽说经验告诉我们, 也许先走会占便宜. 但我想我们还不知道一系列让后走者无法翻身的招术. 因此我们还不能肯定先走就一定开局就处于胜态.

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


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


	虞国公主 ★

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

#9

发表于 2005-9-1 11:14 资料主页短消息看全部作者

我改名事出有因，请到水区查讯过程。

你第一个想法是正确的，命题并没有要求你找出不败策略，只是要求你证明它存在而已。

普通象棋其实从第一步开始，胜负就已经注定。也就是说，红绿一方必定存在不败策略，但我们还不能严格证明这个策略站在哪一方。这个现象对于所有的有限非随机游戏(finite state deterministic games)都是成立的。

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


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


	虞国公主 ★

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

#10

发表于 2005-9-1 11:17 资料主页短消息看全部作者

冰血：对理智性的假设其实也不是完全必要，我们也可以用严格的数学语言去给一个不完全理智的玩家建模。准确的讲，不理智的玩家会把一个deterministic game转换成一个stochastic game。玩家的理智性可以用随机过程的方差去描述。

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


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


	虞国公主 ★

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

#11

发表于 2005-9-7 01:46 资料主页短消息看全部作者

是的... 答案就是这么简单... 不过好象冰血几个已经说过了啊.

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


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


	虞国公主 ★

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

#12

发表于 2007-6-6 17:30 资料主页短消息看全部作者

前面重阳说了，前面冰血说了，在每人走两步的规则下，先走方可以在起初自己走时走车一进一、再车一退一之类的，使棋局还原，此时后走方成为先走方，而棋局与开始时完全一样。假如在此规则走先走方必败，则按上面的走方后手法成为先手方后也是必败，显然是矛盾的。因此先手方至少可以和。

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


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


	虞国公主 ★

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

#13

发表于 2007-6-6 18:07 资料主页短消息看全部作者

作为一个非随即离散博弈游戏，任何一个局面对任何一方都会是：必胜态，必败态，或者平局态。

所谓非随即，就是不能有随即事故出现，例如《曹操传》中打出暴击等。
所谓离散，就是棋是一步一步的走，而不是连续时间操作的博弈。

所谓必胜态，就是当两个人无限理智的情况下，对手无法翻身。
所谓必败态，就是当两个人无限理智的情况下，我方无法翻身。
所谓平手态，就是当两个人无限理智的情况下，双手无法取胜，或者游戏进入无限循环。

这个定理可以用数学归纳法来证明。

那么在两步象棋的开局，如果先走的处于必胜态，那么他存在他自己的必胜策略。如果不然的话，他可以一步之内先走马，再回来，把第一步让给对方。

[ 本帖最后由天宫公主于 2007-6-6 18:09 编辑 ]

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


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


	虞国公主 ★

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

#14

发表于 2007-6-7 03:16 资料主页短消息看全部作者

因为又有人问起。。。

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


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


	虞国公主 ★

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

#15

发表于 2007-6-10 11:56 资料主页短消息看全部作者

"先走的一方可以确定棋局的状态" - 把这个理解为一个 proposition 就好了。

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


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


	虞国公主 ★

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

#16

发表于 2007-7-17 20:34 资料主页短消息看全部作者

> 是不是说任何一方处于必败态、必胜态，平手态三态要在第一步棋之后确定的呢？

在没走之前就决定了。

> 因为即便是假设博弈双方是无限理智且信息完全（背下所以的棋谱），而每一步策略的选择也要依靠上一步对方的策略，也就是说会形成无数条链路通往必败态、必胜态，平手态三态之其一，但走上哪条链路应该是由第一个点也就是第一步确定的。这个说法不知道成不成立？

大体没错。唯一需要更正的: 1. 形成的是无数条链路通往失败，胜利或者平局。能通往这三种结果的状态分别叫做“必胜态”，“必败态”和“平局态”。但事实上在没走之前，双方就已经有一方至少在平局态了。

> 如果成立的话，那么当先手方复原时，他只是将第一步的权利交给了对方，换言之是将走上哪条链路的选择权交给了对方，这样对方也可能会走上必胜态，也就是本来先手方的必败态的。这样也就不存在先手不败的说法了，不是吗？

如果没走之前白棋（先走方－权且按国际象棋颜色讨论）如果已经处于必胜态，那么他可以执行已经存在的必胜策。如果他不处于必胜态，那么他可以把马跳出再跳回，将不必胜态交给对手，这样他至少可以保证平局。

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


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


	虞国公主 ★

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

#17

发表于 2007-7-17 23:03 资料主页短消息看全部作者

事实上无论普通象棋，还是围棋都是在没走之前，就已经决出胜负了。只不过如果必胜策过于复杂，也许人类无法算尽各种可能。但在国际象棋这个游戏中，电脑战胜所有人类只是时间问题，因为电脑比人类更会保持“不败态”。

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