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


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


	虞国公主 ★

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

#1

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

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

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


	lcarron78

组别	校尉
级别	军师将军
功绩	10
帖子	962
编号	19205
注册	2004-10-20
来自	奥克兰

#2

发表于 2005-8-29 17:07 资料主页个人空间短消息只看该作者

在一盘象棋里, 如一次走一步. 按棋谱, 先走方不会选自己会输的棋谱,所以至少能够达成和棋.

同样,假设双方现在一次走两步, 把所有可能的走棋作为棋谱. 一开始先走方不能马上将死后走方, 而先走方不会选自己会输的棋谱, 所以至少能够达成和棋.

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


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


	虞国公主 ★

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

#3

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

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

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


	lcarron78

组别	校尉
级别	军师将军
功绩	10
帖子	962
编号	19205
注册	2004-10-20
来自	奥克兰

#4

发表于 2005-8-30 09:12 资料主页个人空间短消息只看该作者

QUOTE:

原帖由天公将军于2005-08-29, 20:09:34发表
楼上和正解非常接近... 唯一漏掉的是, 你尚需证明, 对于先走方的确存在自己不会输的棋谱. 在经典象棋, 这个问题很难, 但在"两步象棋"却有一个很巧妙的证法.

象棋存在先走方胜，和，输的棋谱。先走方必然不会选自己会输的棋谱，后走方也一样。其实大多数棋谱会是和局。

“但在"两步象棋"却有一个很巧妙的证法.”
这个要再想想。

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


	重阳


	高阳侯光禄大夫

组别	翰林学士
级别	前将军
好贴	2
功绩	585
帖子	1775
编号	50
注册	2003-8-21

#5

发表于 2005-8-30 09:56 资料主页文集短消息只看该作者

不知天公将军的本意是不是要证明先手方不可能必败？这和原题似乎略有区别，玩家是否能够通晓一切变化尚不得而知呢。

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


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


	虞国公主 ★

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

#6

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

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

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


	重阳


	高阳侯光禄大夫

组别	翰林学士
级别	前将军
好贴	2
功绩	585
帖子	1775
编号	50
注册	2003-8-21

#7

发表于 2005-8-30 11:17 资料主页文集短消息只看该作者

QUOTE:

原帖由天公将军于2005-08-30, 11:04:00发表
对... 命题就是要证明在两步象棋里, 对于先走方存在不败战术(i.e. 如果玩家足够理智, 不可能必败).

有点晕，加了括号里的话之后，怎么意思又有点偏回主贴了。

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

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


	zeroideal

组别	羽林都尉
级别	镇西将军
好贴	1
功绩	104
帖子	3851
编号	36223
注册	2005-4-7
家族	轩辕丐帮

#8

发表于 2005-8-30 12:44 资料主页文集短消息只看该作者

先手走偶数步，可复原，成后手。
故博弈角度看必定不败。

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


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


	虞国公主 ★

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

#9

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

QUOTE:

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

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

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

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

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


	lcarron78

组别	校尉
级别	军师将军
功绩	10
帖子	962
编号	19205
注册	2004-10-20
来自	奥克兰

#10

发表于 2005-8-30 18:01 资料主页个人空间短消息只看该作者

QUOTE:

原帖由冰血于2005-08-30, 12:44:26发表
先手走偶数步，可复原，成后手。
故博弈角度看必定不败。

不一定,象棋也有禁手.
抬抬杠

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


	zeroideal

组别	羽林都尉
级别	镇西将军
好贴	1
功绩	104
帖子	3851
编号	36223
注册	2005-4-7
家族	轩辕丐帮

#11

发表于 2005-8-30 18:41 资料主页文集短消息只看该作者

博弈里面已经假设了行动者充分理智的（就是假设了能够一算到底的），
普通的象棋，在博弈中就是一个平庸的问题了

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


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


	虞国公主 ★

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

#12

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

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

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


	lcarron78

组别	校尉
级别	军师将军
功绩	10
帖子	962
编号	19205
注册	2004-10-20
来自	奥克兰

#13

发表于 2005-8-31 02:38 资料主页个人空间短消息只看该作者

QUOTE:

原帖由天公将军于2005-08-31, 2:28:30发表
普通象棋是平庸问题? 不解... 难道谁已证明先走方开始就处于不败态么?

虽然有使后手胜或胜势的弃马陷车等开局,只要先手不走向那个局势发展的下着,后手就无法走成那些棋局. 所以,只要双方都完全明了每一着以后的发展,先手方必不败.

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


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


	虞国公主 ★

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

#14

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

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

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

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

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


	lcarron78

组别	校尉
级别	军师将军
功绩	10
帖子	962
编号	19205
注册	2004-10-20
来自	奥克兰

#15

发表于 2005-8-31 04:19 资料主页个人空间短消息只看该作者

用超级电脑可以用树形图把可能的每一步都记下来,最后标出结果.
这是个zero-sum game (总利益为零的游戏),后走方要胜,是和先走方利益相反.
而玩家是理智的,所以追求最大利益,就是胜.

玩家只要找出在每个棋面下他的最优下法(可有多个),按图下棋就行了.

我想这种严格的证明不可能有的, 要有的话, 估计就谁都甭下了.
会下国际象棋的超级电脑能记忆大量的棋谱,所以人类玩家按棋谱下的话是不可能赢的.
有的象棋大师比赛早早结束,有时候是因为双方都按棋谱下成宫和的局势.

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


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


	虞国公主 ★

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

#16

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

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

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


	lcarron78

组别	校尉
级别	军师将军
功绩	10
帖子	962
编号	19205
注册	2004-10-20
来自	奥克兰

#17

发表于 2005-8-31 04:35 资料主页个人空间短消息只看该作者

执白是后走吧.

国际象棋电脑执黑先走,人类大师执白后走.都按棋谱的话,国际象棋电脑先走绝不会输.只有当人类大师走出与棋谱不同的棋才可能赢

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


	zeroideal

组别	羽林都尉
级别	镇西将军
好贴	1
功绩	104
帖子	3851
编号	36223
注册	2005-4-7
家族	轩辕丐帮

#18

发表于 2005-8-31 09:47 资料主页文集短消息只看该作者

QUOTE:

原帖由天公将军于2005-08-31, 2:28:30发表
普通象棋是平庸问题? 不解... 难道谁已证明先走方开始就处于不败态么?

我不知道是不是我们考虑的角度不一样，

在假设了参与人是无限理性的话，对于象棋来说，存在一个算法来“解”这个博弈。
该技术为两个参与人各自确定了一个战略，这样就有一个“均衡”的结果，该结果的性质是无论其他参与人采用何种战略，只要参与人遵从他自己的战略，那么他的结果至少与均衡结果一样好。对于两个无限理性的参与人来说，象棋只有一个可能的结果。

至于这个结果是什么，以及如何获得这个结果，
在这个问题中，关键在于如何得到偏好关系，只要知道偏好关系，就解决了问题，
而这个偏好关系的计算，是进行博弈要知道的已知条件，根本就不应该是博弈所要研究或者所能够研究出的。

我的意思是说，在知道偏好关系的基础上，这种博弈是没有意义的；而对偏好关系的计算，是和博弈无关的。

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


	重阳


	高阳侯光禄大夫

组别	翰林学士
级别	前将军
好贴	2
功绩	585
帖子	1775
编号	50
注册	2003-8-21

#19

发表于 2005-8-31 11:45 资料主页文集短消息只看该作者

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

这完全是对规则的分析，说先手方是否理智似乎不妥。上面已经证明了存在先手方不败的方法，但并没有给出这个方法，仅据此我们还是不能保证一个特级大师真正就能不败。所谓足够理智，实际就是知道所有变化吧，对这么复杂的一个东西，也许人类永远也不能穷其所有变化。

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


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


	虞国公主 ★

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

#20

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

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

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

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

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

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


	lcarron78

组别	校尉
级别	军师将军
功绩	10
帖子	962
编号	19205
注册	2004-10-20
来自	奥克兰

#21

发表于 2005-8-31 12:59 资料主页个人空间短消息只看该作者

QUOTE:

原帖由天公将军于2005-08-31, 12:32:46发表
在两步象棋中, 如过先走的开始是处于败态, 那么他可以连走两步而还原, 把败态交给对手. 如果先走处于胜态, 那么则存在一系列的招数, 使得对手从第一步棋开始, 就无法翻身.

双方的棋面一般不是一样的！连走两步而还原，会输得更快。即使这是成立的，后走方也可以两步还原，棋局进入循环。

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


	zeroideal

组别	羽林都尉
级别	镇西将军
好贴	1
功绩	104
帖子	3851
编号	36223
注册	2005-4-7
家族	轩辕丐帮

#22

发表于 2005-8-31 13:05 资料主页文集短消息只看该作者

QUOTE:

原帖由lcarron78于2005-08-31, 12:59:24发表

QUOTE:

原帖由天公将军于2005-08-31, 12:32:46发表
在两步象棋中, 如过先走的开始是处于败态, 那么他可以连走两步而还原, 把败态交给对手. 如果先走处于胜态, 那么则存在一系列的招数, 使得对手从第一步棋开始, 就无法翻身.

双方的棋面一般不是一样的！连走两步而还原，会输得更快。即使这是成立的，后走方也可以两步还原，棋局进入循环。

如此则和，
天公给出的题目要求的是证明：存在使红方不败的战略。
满足题意的啊

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


	zeroideal

组别	羽林都尉
级别	镇西将军
好贴	1
功绩	104
帖子	3851
编号	36223
注册	2005-4-7
家族	轩辕丐帮

#23

发表于 2005-8-31 13:19 资料主页文集短消息只看该作者

QUOTE:

原帖由天公将军于2005-08-31, 12:32:46发表
因此我们还不能肯定先走就一定开局就处于胜态.

对于普通的象棋，我上面的说明并没有以“先走就一定开局就处于胜态”为前提。并且在此帖中我从来没有提出这一观点。

博弈，就是在已经知道偏好关系等的基础上（这里假设了充分理性），研究行动者集合如何采取每一步的行动将有最优期望。
我觉得象棋在博弈中的平庸可以这么说：如果你已经知道走哪步棋对你最好，你还需要用博弈来告诉你怎么走你的行动才是最优吗？

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


	金圭子


	白衣伯爵中大夫 ★

组别	白衣卿相
级别	征西将军
好贴	4
功绩	265
帖子	4926
编号	27961
注册	2004-12-16

#24

发表于 2005-9-1 10:15 资料文集短消息只看该作者

QUOTE:

原帖由lcarron78于2005-08-31, 12:59:24发表

QUOTE:

原帖由天公将军于2005-08-31, 12:32:46发表
在两步象棋中, 如过先走的开始是处于败态, 那么他可以连走两步而还原, 把败态交给对手. 如果先走处于胜态, 那么则存在一系列的招数, 使得对手从第一步棋开始, 就无法翻身.

双方的棋面一般不是一样的！连走两步而还原，会输得更快。即使这是成立的，后走方也可以两步还原，棋局进入循环。

我一开始就想到了这个…………
天公将军（是天公，改了名字吧？看着真不习惯，觉得改名字真不是什么好东西……）的题目的意思是不是这样：
因为一开始是双方的情况完全相同的，所以如果先下的人必赢或者必和，就直接按照这种方法下下去；如果先下的人必输，则可以反复一次变成后下，把败局留给对方。是么？

当然，实际上的普通象棋会碰到这种情况：
没有必赢、必输、必和的方法，因为要从开局遍历所有的情况的复杂度过高，高于现在计算工具的可计算范围？
而且象棋虽然广度不如围棋，但是深度不像围棋是可估计的，象棋我自己觉得深度毕竟难以估计……嗯，不过或许可以改为有限种布局（棋盘上有有限个交叉点，上面放有限个棋子，除去若干不可能的情况，剩下有限种布局），或许深度可以控制在有限种。

当然纯粹从概率学上来说是可以的吧？不过天公自己又说“现在不存在执白不败的方法”
而且又说题目的要求是“当已经落入必败的情况下，怎么把必败转移给对方”
这个我就看不懂了。

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


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


	虞国公主 ★

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

#25

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

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

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

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

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


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


	虞国公主 ★

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

#26

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

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

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


	zeroideal

组别	羽林都尉
级别	镇西将军
好贴	1
功绩	104
帖子	3851
编号	36223
注册	2005-4-7
家族	轩辕丐帮

#27

发表于 2005-9-1 13:22 资料主页文集短消息只看该作者

QUOTE:

原帖由天宫公主于2005-09-01, 11:17:55发表
冰血：对理智性的假设其实也不是完全必要，我们也可以用严格的数学语言去给一个不完全理智的玩家建模。准确的讲，不理智的玩家会把一个deterministic game转换成一个stochastic game。玩家的理智性可以用随机过程的方差去描述。

“有限理智的基础上，象棋不是平庸的”，对此我无异议。

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


	常胜将军

组别	百姓
级别	在野武将
功绩	0
帖子	31
编号	18323
注册	2004-9-24

#28

发表于 2005-9-6 21:43 资料短消息只看该作者

突然迸发出一个想法
其实很简单，我们要证明的是，初始的局面不是一个红方的必败局面，所谓必败局面就是无论红方采用何种策略，黑方总有一个策略使得红方必然输。
反证法，假设初始局面是红方的必败局面，那么红方如第一次移动使得局面不变(因为可以走两步，这是可以的，譬如上下移动一个车)，那么可以看到，黑方陷入了一个必败局面。矛盾，可知初始局面不是红方的必败局面。

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


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


	虞国公主 ★

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

#29

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

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

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


	幽浪

组别	士兵
级别	平北将军
好贴	1
功绩	8
帖子	1923
编号	23580
注册	2004-11-10

#30

发表于 2006-1-27 12:05 资料主页个人空间短消息只看该作者

黑方也可照样.按棋规,红方违例.负.

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