标题: 搏弈问题 [打印本页]
作者:
天宫公主 时间: 2005-8-29 02:25
在一盘象棋里, 假设双方现在一次走两步, 而不是一次走一步. 求证先走方至少能够达成和棋.
作者:
lcarron78 时间: 2005-8-29 17:07
在一盘象棋里, 如一次走一步. 按棋谱, 先走方不会选自己会输的棋谱,所以至少能够达成和棋.
同样,假设双方现在一次走两步, 把所有可能的走棋作为棋谱. 一开始先走方不能马上将死后走方, 而先走方不会选自己会输的棋谱, 所以至少能够达成和棋.
作者:
天宫公主 时间: 2005-8-29 20:09
楼上和正解非常接近... 唯一漏掉的是, 你尚需证明, 对于先走方的确存在自己不会输的棋谱. 在经典象棋, 这个问题很难, 但在"两步象棋"却有一个很巧妙的证法.
作者:
lcarron78 时间: 2005-8-30 09:12
原帖由天公将军于2005-08-29, 20:09:34发表
楼上和正解非常接近... 唯一漏掉的是, 你尚需证明, 对于先走方的确存在自己不会输的棋谱. 在经典象棋, 这个问题很难, 但在"两步象棋"却有一个很巧妙的证法.
象棋存在先走方胜，和，输的棋谱。先走方必然不会选自己会输的棋谱，后走方也一样。其实大多数棋谱会是和局。
“但在"两步象棋"却有一个很巧妙的证法.”
这个要再想想。
作者:
重阳 时间: 2005-8-30 09:56
不知天公将军的本意是不是要证明先手方不可能必败？这和原题似乎略有区别，玩家是否能够通晓一切变化尚不得而知呢。
作者:
天宫公主 时间: 2005-8-30 11:04
对... 命题就是要证明在两步象棋里, 对于先走方存在不败战术(i.e. 如果玩家足够理智, 不可能必败).
作者:
重阳 时间: 2005-8-30 11:17
原帖由天公将军于2005-08-30, 11:04:00发表
对... 命题就是要证明在两步象棋里, 对于先走方存在不败战术(i.e. 如果玩家足够理智, 不可能必败).
有点晕，加了括号里的话之后，怎么意思又有点偏回主贴了。
先手方不可能必败，说的是这个规则，和玩家是否理智没啥关系，除非这个玩家理智到能一路计算到棋局结束。
作者:
zeroideal 时间: 2005-8-30 12:44
先手走偶数步，可复原，成后手。
故博弈角度看必定不败。
作者:
天宫公主 时间: 2005-8-30 16:47
原帖由重阳于2005-08-30, 11:17:21发表
有点晕，加了括号里的话之后，怎么意思又有点偏回主贴了。
先手方不可能必败，说的是这个规则，和玩家是否理智没啥关系，除非这个玩家理智到能一路计算到棋局结束。
换一个任意游戏，为什么先走方不可能必败？
这里我们当然要假设玩家的理智。。。也就是说，如果玩家已经在必胜态，他有足够的水平不要把自己走成必败态。
作者:
lcarron78 时间: 2005-8-30 18:01
原帖由冰血于2005-08-30, 12:44:26发表
先手走偶数步，可复原，成后手。
故博弈角度看必定不败。
不一定,象棋也有禁手.
抬抬杠
作者:
zeroideal 时间: 2005-8-30 18:41
博弈里面已经假设了行动者充分理智的（就是假设了能够一算到底的），
普通的象棋，在博弈中就是一个平庸的问题了
作者:
天宫公主 时间: 2005-8-31 02:28
普通象棋是平庸问题? 不解... 难道谁已证明先走方开始就处于不败态么?
作者:
lcarron78 时间: 2005-8-31 02:38
原帖由天公将军于2005-08-31, 2:28:30发表
普通象棋是平庸问题? 不解... 难道谁已证明先走方开始就处于不败态么?
虽然有使后手胜或胜势的弃马陷车等开局,只要先手不走向那个局势发展的下着,后手就无法走成那些棋局. 所以,只要双方都完全明了每一着以后的发展,先手方必不败.
作者:
天宫公主 时间: 2005-8-31 03:14
但你的这个猜测并没有被数学证明过吧?
所谓数学证明, 是要一步一步的逻辑推理, 严密的说明了后走方没有任何一步棋可以扭转局势, 最终将死先走方.
我想这种严格的证明不可能有的, 要有的话, 估计就谁都甭下了.
作者:
lcarron78 时间: 2005-8-31 04:19
用超级电脑可以用树形图把可能的每一步都记下来,最后标出结果.
这是个zero-sum game (总利益为零的游戏),后走方要胜,是和先走方利益相反.
而玩家是理智的,所以追求最大利益,就是胜.
玩家只要找出在每个棋面下他的最优下法(可有多个),按图下棋就行了.
我想这种严格的证明不可能有的, 要有的话, 估计就谁都甭下了.
会下国际象棋的超级电脑能记忆大量的棋谱,所以人类玩家按棋谱下的话是不可能赢的.
有的象棋大师比赛早早结束,有时候是因为双方都按棋谱下成宫和的局势.
作者:
天宫公主 时间: 2005-8-31 04:27
汗... 国际象棋电脑至今对人类大师也没构成执白不败... 离严格证明还远着呢.
作者:
lcarron78 时间: 2005-8-31 04:35
执白是后走吧.
国际象棋电脑执黑先走,人类大师执白后走.都按棋谱的话,国际象棋电脑先走绝不会输.只有当人类大师走出与棋谱不同的棋才可能赢
作者:
zeroideal 时间: 2005-8-31 09:47
原帖由天公将军于2005-08-31, 2:28:30发表
普通象棋是平庸问题? 不解... 难道谁已证明先走方开始就处于不败态么?
我不知道是不是我们考虑的角度不一样，
在假设了参与人是无限理性的话，对于象棋来说，存在一个算法来“解”这个博弈。
该技术为两个参与人各自确定了一个战略，这样就有一个“均衡”的结果，该结果的性质是无论其他参与人采用何种战略，只要参与人遵从他自己的战略，那么他的结果至少与均衡结果一样好。对于两个无限理性的参与人来说，象棋只有一个可能的结果。
至于这个结果是什么，以及如何获得这个结果，
在这个问题中，关键在于如何得到偏好关系，只要知道偏好关系，就解决了问题，
而这个偏好关系的计算，是进行博弈要知道的已知条件，根本就不应该是博弈所要研究或者所能够研究出的。
我的意思是说，在知道偏好关系的基础上，这种博弈是没有意义的；而对偏好关系的计算，是和博弈无关的。
作者:
重阳 时间: 2005-8-31 11:45
前面冰血说了，在每人走两步的规则下，先走方可以在起初自己走时走车一进一、再车一退一之类的，使棋局还原，此时后走方成为先走方，而棋局与开始时完全一样。假如在此规则走先走方必败，则按上面的走方后手法成为先手方后也是必败，显然是矛盾的。因此先手方至少可以和。
这完全是对规则的分析，说先手方是否理智似乎不妥。上面已经证明了存在先手方不败的方法，但并没有给出这个方法，仅据此我们还是不能保证一个特级大师真正就能不败。所谓足够理智，实际就是知道所有变化吧，对这么复杂的一个东西，也许人类永远也不能穷其所有变化。
作者:
天宫公主 时间: 2005-8-31 12:32
冰血: 在一个非随机搏弈里, 每个玩家在任何情况下, 都会处于:
A. 胜态(或者不败态, 看此游戏是否存在和棋的可能).
B. 败态.
在两步象棋中, 如过先走的开始是处于败态, 那么他可以连走两步而还原, 把败态交给对手. 如果先走处于胜态, 那么则存在一系列的招数, 使得对手从第一步棋开始, 就无法翻身.
但如过是普通象棋的话, 虽说经验告诉我们, 也许先走会占便宜. 但我想我们还不知道一系列让后走者无法翻身的招术. 因此我们还不能肯定先走就一定开局就处于胜态.
作者:
lcarron78 时间: 2005-8-31 12:59
原帖由天公将军于2005-08-31, 12:32:46发表
在两步象棋中, 如过先走的开始是处于败态, 那么他可以连走两步而还原, 把败态交给对手. 如果先走处于胜态, 那么则存在一系列的招数, 使得对手从第一步棋开始, 就无法翻身.
双方的棋面一般不是一样的！连走两步而还原，会输得更快。即使这是成立的，后走方也可以两步还原，棋局进入循环。
作者:
zeroideal 时间: 2005-8-31 13:05
原帖由
lcarron78于2005-08-31, 12:59:24发表
原帖由天公将军于2005-08-31, 12:32:46发表
在两步象棋中, 如过先走的开始是处于败态, 那么他可以连走两步而还原, 把败态交给对手. 如果先走处于胜态, 那么则存在一系列的招数, 使得对手从第一步棋开始, 就无法翻身.
双方的棋面一般不是一样的！连走两步而还原，会输得更快。即使这是成立的，后走方也可以两步还原，棋局进入循环。
如此则和，
天公给出的题目要求的是证明：存在使红方不败的战略。
满足题意的啊
作者:
zeroideal 时间: 2005-8-31 13:19
原帖由天公将军于2005-08-31, 12:32:46发表
因此我们还不能肯定先走就一定开局就处于胜态.
对于普通的象棋，我上面的说明并没有以“先走就一定开局就处于胜态”为前提。并且在此帖中我从来没有提出这一观点。
博弈，就是在已经知道偏好关系等的基础上（这里假设了充分理性），研究行动者集合如何采取每一步的行动将有最优期望。
我觉得象棋在博弈中的平庸可以这么说：如果你已经知道走哪步棋对你最好，你还需要用博弈来告诉你怎么走你的行动才是最优吗？
作者:
金圭子 时间: 2005-9-1 10:15
原帖由
lcarron78于2005-08-31, 12:59:24发表
原帖由天公将军于2005-08-31, 12:32:46发表
在两步象棋中, 如过先走的开始是处于败态, 那么他可以连走两步而还原, 把败态交给对手. 如果先走处于胜态, 那么则存在一系列的招数, 使得对手从第一步棋开始, 就无法翻身.
双方的棋面一般不是一样的！连走两步而还原，会输得更快。即使这是成立的，后走方也可以两步还原，棋局进入循环。
我一开始就想到了这个…………
天公将军（是天公，改了名字吧？看着真不习惯，觉得改名字真不是什么好东西……）的题目的意思是不是这样：
因为一开始是双方的情况完全相同的，所以如果先下的人必赢或者必和，就直接按照这种方法下下去；如果先下的人必输，则可以反复一次变成后下，把败局留给对方。是么？
当然，实际上的普通象棋会碰到这种情况：
没有必赢、必输、必和的方法，因为要从开局遍历所有的情况的复杂度过高，高于现在计算工具的可计算范围？
而且象棋虽然广度不如围棋，但是深度不像围棋是可估计的，象棋我自己觉得深度毕竟难以估计……嗯，不过或许可以改为有限种布局（棋盘上有有限个交叉点，上面放有限个棋子，除去若干不可能的情况，剩下有限种布局），或许深度可以控制在有限种。
当然纯粹从概率学上来说是可以的吧？不过天公自己又说“现在不存在执白不败的方法”
而且又说题目的要求是“当已经落入必败的情况下，怎么把必败转移给对方”
这个我就看不懂了。
作者:
天宫公主 时间: 2005-9-1 11:14
我改名事出有因，请到水区查讯过程。
你第一个想法是正确的，命题并没有要求你找出不败策略，只是要求你证明它存在而已。
普通象棋其实从第一步开始，胜负就已经注定。也就是说，红绿一方必定存在不败策略，但我们还不能严格证明这个策略站在哪一方。这个现象对于所有的有限非随机游戏(finite state deterministic games)都是成立的。
作者:
天宫公主 时间: 2005-9-1 11:17
冰血：对理智性的假设其实也不是完全必要，我们也可以用严格的数学语言去给一个不完全理智的玩家建模。准确的讲，不理智的玩家会把一个deterministic game转换成一个stochastic game。玩家的理智性可以用随机过程的方差去描述。
作者:
zeroideal 时间: 2005-9-1 13:22
原帖由天宫公主于2005-09-01, 11:17:55发表
冰血：对理智性的假设其实也不是完全必要，我们也可以用严格的数学语言去给一个不完全理智的玩家建模。准确的讲，不理智的玩家会把一个deterministic game转换成一个stochastic game。玩家的理智性可以用随机过程的方差去描述。
“有限理智的基础上，象棋不是平庸的”，对此我无异议。
作者:
常胜将军 时间: 2005-9-6 21:43
突然迸发出一个想法
其实很简单，我们要证明的是，初始的局面不是一个红方的必败局面，所谓必败局面就是无论红方采用何种策略，黑方总有一个策略使得红方必然输。
反证法，假设初始局面是红方的必败局面，那么红方如第一次移动使得局面不变(因为可以走两步，这是可以的，譬如上下移动一个车)，那么可以看到，黑方陷入了一个必败局面。矛盾，可知初始局面不是红方的必败局面。
作者:
天宫公主 时间: 2005-9-7 01:46
是的... 答案就是这么简单... 不过好象冰血几个已经说过了啊.
作者:
幽浪 时间: 2006-1-27 12:05
黑方也可照样.按棋规,红方违例.负.
作者:
小行者 时间: 2006-1-27 13:19
先手权利有二：
1
将对方的军
2
为自己的将军解围
二者必得其一 至少是和棋
作者:
幽浪 时间: 2006-1-27 15:06
这看来下的不是象棋的说。。。。。。
作者:
墨叶 时间: 2007-6-6 13:04
有策略但不知道什么时候用,等于没策略.
所以我认为该题无解.
作者:
石敢当 时间: 2007-6-6 16:31
小白来发言了
两步象棋.......
的确没想过,但我以为单就这么发帖讨论是没结果的，
棋理（如果两步象棋也算棋理的话）之所以成立，
大多是先有实践基础而后完善理论基础的结果。
所以，关于这种命题能否证明，
还需楼主、或对两步象棋有兴趣的人在先有实践上之认识的基础上，
才能从中引申或证明这个理论成立还是不成立
作者:
东倒西歪 时间: 2007-6-6 17:26
普通象棋双方都走正着的话，应该是和棋，先后手的那点差别，抵消不了强大专职防御力量。举个例子，一车难胜士相全，也就是说这种盘面优势净多一个车，还是和棋。
作者:
天宫公主 时间: 2007-6-6 17:30
前面重阳说了，前面冰血说了，在每人走两步的规则下，先走方可以在起初自己走时走车一进一、再车一退一之类的，使棋局还原，此时后走方成为先走方，而棋局与开始时完全一样。假如在此规则走先走方必败，则按上面的走方后手法成为先手方后也是必败，显然是矛盾的。因此先手方至少可以和。
作者:
石敢当 时间: 2007-6-6 18:01
我只看了主题帖子部分再加公主楼上部分。。。
假如在此规则走先走方必败
首先这个假设就很玄乎，因为你无法证明为什么这规则先走方先败，
如果你不先通过大量实践来证明你的假设可行，那么你在说这规则下谁先败谁后败，是没什么意义的。
连带车一进一、车一退一，也是没意义的钻空子行为
换言之，或许两步象棋将来会和普通象棋也成为艺术，楼主的命题才有可能证明，成立或不成立
[ 本帖最后由 石敢当 于 2007-6-6 18:02 编辑 ]
作者:
天宫公主 时间: 2007-6-6 18:07
作为一个非随即离散博弈游戏，任何一个局面对任何一方都会是：必胜态，必败态，或者平局态。
所谓非随即，就是不能有随即事故出现，例如《曹操传》中打出暴击等。
所谓离散，就是棋是一步一步的走，而不是连续时间操作的博弈。
所谓必胜态，就是当两个人无限理智的情况下，对手无法翻身。
所谓必败态，就是当两个人无限理智的情况下，我方无法翻身。
所谓平手态，就是当两个人无限理智的情况下，双手无法取胜，或者游戏进入无限循环。
这个定理可以用数学归纳法来证明。
那么在两步象棋的开局，如果先走的处于必胜态，那么他存在他自己的必胜策略。如果不然的话，他可以一步之内先走马，再回来，把第一步让给对方。
[ 本帖最后由 天宫公主 于 2007-6-6 18:09 编辑 ]
作者:
reynolds_wwy 时间: 2007-6-6 22:13
...為甚麼又發了一遍答案啊好像很早就討論完了呀這帖
作者:
天宫公主 时间: 2007-6-7 03:16
因为又有人问起。。。
作者:
lcarron78 时间: 2007-6-7 06:26
车一进一,车一平四,红方必胜
作者:
fy945 时间: 2007-6-7 09:19
原帖由
lcarron78 于 2007-6-7 06:26 发表
车一进一,车一平四,红方必胜
错的离谱，黑有多种方法阻挡红车，你回去自己好好想想吧。
举例：黑炮8平6，象7进5(或马2进3)，担子炮拒红车；
或者黑车9进1，车9平6，黑车拒红车；
或者黑炮8平6，士6进5……
甚至黑士6进5，士5进6，就轻松拒车。
作者:
东倒西歪 时间: 2007-6-7 17:05
原帖由 fy945 于 2007-6-7 09:19 发表
错的离谱，黑有多种方法阻挡红车，你回去自己好好想想吧。
举例：黑炮8平6，象7进5(或马2进3)，担子炮拒红车；
或者黑车9进1，车9平6，黑车拒红车；
或者黑炮8平6，士6进5……
甚至黑士6进5，士 ...
消极抵抗是没有用的，对手最简单的策略，吃了你再退回安全位置，下次再吃，完全没有悬念。
只有积极防御，一只手抵挡的同时，另一只手反击，才能多一些机会。（比如先平炮士角同时起横车）
作者:
东倒西歪 时间: 2007-6-7 17:07
不过讨论两步象棋的走法，已经跟主题无关了。
作者:
lcarron78 时间: 2007-6-8 15:49
To #43: ....吃了你再退回安全位置，下次再吃，完全没有悬念。....
To #44: 不过讨论两步象棋的走法，已经跟主题无关了。
To #42: Galic....
作者:
墨叶 时间: 2007-6-10 00:24
原帖由 天宫公主 于 2007-6-6 18:07 发表
作为一个非随即离散博弈游戏，任何一个局面对任何一方都会是：必胜态，必败态，或者平局态。
所谓非随即，就是不能有随即事故出现，例如《曹操传》中打出暴击等。
所谓离散，就是棋是一步一步的走，而不是连续时间操作的博弈。
所谓必胜态，就是当两个人无限理智的情况下，对手无法翻身。
所谓必败态，就是当两个人无限理智的情况下，我方无法翻身。
所谓平手态，就是当两个人无限理智的情况下，双手无法取胜，或者游戏进入无限循环。
这个定理可以用数学归纳法来证明。
那么在两步象棋的开局，如果先走的处于必胜态，那么他存在他自己的必胜策略。如果不然的话，他可以一步之内先走马，再回来，把第一步让给对方。
问题的关键是先走的一方不知道自己是处于什么状态.至少从公主的原题看不出.
就象划拳,确实对方的每种行为我都有取胜的方法.但是我不知道我应该选择哪种方法才是正确的.
所以虽然我知道对付对方的方法,还是不能保证我一定可以胜利.
作者:
reynolds_wwy 时间: 2007-6-10 08:48
但至少在三种状态的哪一种是确定的，所以公主并没有问保证不败的策略是什么而只是有没有。在讨论到底该怎么走才能赢就变成了另外一个问题了
作者:
墨叶 时间: 2007-6-10 09:33
原帖由 reynolds_wwy 于 2007-6-10 08:48 发表
但至少在三种状态的哪一种是确定的，所以公主并没有问保证不败的策略是什么而只是有没有。在讨论到底该怎么走才能赢就变成了另外一个问题了
确实至少在三种状态的哪一种是确定的,但是先走的一方并不知道现在是什么状态.所以实际是什么状态反而不重要.
"先走的一方可以确定棋局的状态"没有得到证明,现实中也没有人可以做到.
而且题干中亦无明确指出,所以答题者不能使用"先走的一方可以确定棋局的状态"来证明.
作者:
天宫公主 时间: 2007-6-10 11:56
"先走的一方可以确定棋局的状态" - 把这个理解为一个 proposition 就好了。
作者:
康维 时间: 2007-7-12 17:09
2步棋,如果没有特别的禁手的,从第1步齐就素平局态啊,因为先手和后手可以完全互换,如果2者都无限理智.除非2步秒杀.不然就完全素平局.....也就素说...如果2者都无限理智,这棋必和......
作者:
龙剑止水 时间: 2007-7-17 00:00
没学过博弈，不过还是有些问题。
是不是说任何一方处于必败态、必胜态，平手态三态要在第一步棋之后确定的呢？因为即便是假设博弈双方是无限理智且信息完全（背下所以的棋谱），而每一步策略的选择也要依靠上一步对方的策略，也就是说会形成无数条链路通往必败态、必胜态，平手态三态之其一，但走上哪条链路应该是由第一个点也就是第一步确定的。这个说法不知道成不成立？
如果成立的话，那么当先手方复原时，他只是将第一步的权利交给了对方，换言之是将走上哪条链路的选择权交给了对方，这样对方也可能会走上必胜态，也就是本来先手方的必败态的。这样也就不存在先手不败的说法了，不是吗？
没学过博弈，很多东西都不知怎么说，只好自己胡陬，各位勉强看吧，不好意思了。
作者:
天宫公主 时间: 2007-7-17 20:34
> 是不是说任何一方处于必败态、必胜态，平手态三态要在第一步棋之后确定的呢？
在没走之前就决定了。
> 因为即便是假设博弈双方是无限理智且信息完全（背下所以的棋谱），而每一步策略的选择也要依靠上一步对方的策略，也就是说会形成无数条链路通往必败态、必胜态，平手态三态之其一，但走上哪条链路应该是由第一个点也就是第一步确定的。这个说法不知道成不成立？
大体没错。唯一需要更正的: 1. 形成的是无数条链路通往失败，胜利或者平局。能通往这三种结果的状态分别叫做“必胜态”，“必败态”和“平局态”。但事实上在没走之前，双方就已经有一方至少在平局态了。
> 如果成立的话，那么当先手方复原时，他只是将第一步的权利交给了对方，换言之是将走上哪条链路的选择权交给了对方，这样对方也可能会走上必胜态，也就是本来先手方的必败态的。这样也就不存在先手不败的说法了，不是吗？
如果没走之前白棋（先走方－权且按国际象棋颜色讨论）如果已经处于必胜态，那么他可以执行已经存在的必胜策。如果他不处于必胜态，那么他可以把马跳出再跳回，将不必胜态交给对手，这样他至少可以保证平局。
作者:
龙剑止水 时间: 2007-7-17 22:19
原帖由 天宫公主 于 2007-7-17 20:34 发表
> 是不是说任何一方处于必败态、必胜态，平手态三态要在第一步棋之后确定的呢？
在没走之前就决定了。
> 因为即便是假设博弈双方是无限理智且信息完全（背下所以的棋谱），而每一步策略的选择也要 ...
公主好，其实我不太理解的就是“事实上在没走之前，双方就已经有一方至少在平局态了。”那也就是说在没走之前，有一方就必然处于必不胜态。那这个必不胜的一方是怎么确定的呢？因为我们假设两个人都是“无限理智且信息完全（背下所以的棋谱）”，那么我们假设是一个人的左手与右手下棋应该也是可以的。这样的话，双方所有的外界初始条件都是相同的，那么是什么因素导致必不胜一方被指定呢？除了上帝扔骰子，我想不出其他解释。
所以我的理解是这三态在没走之前是没有确定的，只有在任一方走出实质的第一步之后，才会连锁的引出一条通向某一态的唯一链路。而走后再复原相当于并没有走出实质的第一步，只是将走出第一步的资格转交给另一方。
这是我这个外行的理解，不知道公主怎么看。
作者:
天宫公主 时间: 2007-7-17 23:03
事实上无论普通象棋，还是围棋都是在没走之前，就已经决出胜负了。只不过如果必胜策过于复杂，也许人类无法算尽各种可能。但在国际象棋这个游戏中，电脑战胜所有人类只是时间问题，因为电脑比人类更会保持“不败态”。
| 欢迎光临 轩辕春秋文化论坛 (http://xycq.org.cn/forum/) |
Powered by Discuz! 5.0.0 |