大家别急着嘲讽题主。如果不看补充说明的话,这其实是个好问题。
太长不看版:无法证明中国象棋红方有必胜或和的策略。涉及策梅洛定理、策略窃取、迫移局面。
知道策梅洛定理的人很多,我简单复述一下。
在二人完美信息回合制有限抽象策略游戏中,以下三者有且只有一项成立:
1、先手方有必胜策略;
2、后手方有必胜策略;
3、双方的最优策略将会导向平局。
而在满足一定条件的某些游戏中,第二项“后手方有必胜策略”是可以被逻辑证否的。
比如 不贴目 的围棋。
证明(反证法):假设存在白方必胜策略P。那么黑方可以开局时就选择“停一手”。若白方也选择“停一手”,则按照规则,棋局立即结束,平局。否则若白方在棋盘上落任意一子,黑方即可窃取后手方的策略P;这样黑方变成了实质上的后手方,采取策略P必胜。然而这与“存在白方必胜策略P”矛盾,因此不存在白方必胜策略P。
这种证明的方式即“策略窃取”(strategy stealing argument/ copycat lemma)。
适用策略窃取的游戏需要满足两个条件:
1、是对称游戏。
2、某方的行动永远不会帮倒忙。
满足以上条件的游戏包括无禁手的五子棋、六贯棋、井字棋等。
用同样的方式证明无禁、不允许停招的五子棋黑先必不败:
证明(反证法):假设存在白方必胜策略P。那么黑方可以开局时就选择随便走一着棋A。我们知道在五子棋中,任意“免费”的一招棋只会对局面有帮助,不会帮倒忙。因此接下来白方在棋盘上落任意一子,黑方即可窃取白方的策略P;这样黑方变成了实质上的后手方,采取策略P必胜。然而这与“存在白方必胜策略P”矛盾,因此不存在白方必胜策略P。
不是对称游戏的例子包括带贴目的围棋、有禁的五子棋。
这一条比较微妙。请看国际象棋的一个例子:
此局面若轮白走则是和棋,若轮黑走则黑负。所以这是一个先手方不利的局面,术语称“迫移局面(zugzwang)”。这种局面的存在,使得“策略窃取”证明在国际象棋上不成立。
象棋中不能停招,而围棋“停一招”永远合法,所以围棋中不存在“迫移局面”。
与国际象棋类似,中国象棋中也存在“迫移局面”。如下图:
因为“将帅不得见面”规则的存在,本局面红先红负,黑先黑负。
如果我们尝试用“策略窃取”证明中国象棋红方有必不败策略,仍然假设黑方有必胜策略P;现在红方不能“停一招”。因此红方总得走一手棋A,才能去窃取黑方的策略。然而我们不知道红方的这手棋A会不会让局面变得更糟(因为存在“迫移局面”),所以策略窃取证明失效。
因此我们不能通过逻辑推理证明中国象棋红方有必不败策略。
实际上,后手方有优势的对称棋类游戏是存在的,比如动物将棋。
已有研究者通过穷举证明,动物将棋的后手方拥有必胜策略。
不过,从现实出发考虑,中国象棋黑方有必胜策略的可能性非常非常低。事实上,黑方存在某种必胜策略P,等价于中象的开局(S_0)就是迫行局面;直觉上来看这几乎不可能,但理论上我们不能排除黑棋有必胜策略的可能性——万一黑棋有办法将局面导向某种迫行残局呢?
当然,题主的补充说明就是扯淡了()即使能证明红方有必不败策略,肯定也不能说没有意义。本文仅解答问题的题面,对补充说明不再展开批驳。
某种意义上,你说的没错。
世间一切的完全信息博弈的游戏,只要总局面数是有限的,你总可以从博弈树的叶子倒推,给每一个局面以“先手胜”、“先手负”、“和棋”的判断。
所以,如果世间真的有围棋之神,我们抓来两个让他们下棋、想要观摩,结局就会是:先手在某一个位置落子,后手认输。
中国象棋就很可能会是,先手提和,后手同意,压根没有动子。
但是,这一切只是理论意义上的,在实践中,你先手一步不走提和,你看看对面的表情?
为什么?因为人家是理论的“神”,但在实践中,要能够下出每个局面的最佳着法,也即“神之一手”,是极其复杂的。象棋的局面约有7×10的四十次方,围棋的局面数更是超过宇宙中的原子数量,理论的神告诉你这个局面红必胜,但你有计算能力和资源穷尽后面所有的变化,并在任何局面下下出最好的应对,从而确保对方所谓“必败”吗?(除了井字棋,恐怕都不可能)
所以人类提取一些有很强预示性的“表征”,英文representation,例如子力有多少、占据的位置如何等等,作为某种判断当前局面是否是必胜的heuristic(启发)。在你平时做的那些先手必胜的数学题里,比如Nim取石子游戏,你用以判断局面是否必胜的那个判断函数(将所有堆异或判断是否非零)本质上也是一种表征,只不过,那些游戏都太简单,表征容易计算而且 完全和真实的胜败一致。 但是一个棋类游戏能够成为让人着迷的游戏, 一定是这种表征函数极其复杂,永远不能简单看清,天文数字的变化更是让纯记忆完全不可能。
人类的比拼,本质上也就是比拼各自对于局面衡量表征函数的准确程度和计算力。AI如此之强,也正是因为这两点远超人类。但是,它们离理论上断言先手必胜的“神”都还太远,我们要感谢这一点,否则根据策梅洛定理,游戏确实就没意思了。
策梅洛定理只能告诉我们,中国象棋要么红必胜,要么黑必胜,要么必和棋,却不能告诉我们红棋是不是必胜的。
事实上,比较好的推测是中国象棋很可能存在必和的策略。不过这个策略以我们目前的算力可能还不足以计算出来,以我们目前的人脑更不可能完全的理解、记忆下这个策略。
纵使你把市面上所有的和棋谱都背了下来,只要实战中别人走一步试探手,牺牲一点先手以达到脱谱的目的,如果你只知道背谱而没有强大的计算力,还是很可能逐渐落入下风的。
这不就是独孤九剑嘛。
对于精通独孤九剑的高手来说,只要对手一出招,自己就有破法,那自然是后发者胜利了,要是两大高手都练到了独孤九剑的最高境界,那自然俩人就呆若木鸡,谁也不出招了,只能是相视一笑,收剑罢斗,只好在酒量上拼个高手。
可是世间哪有那么多高手呀,就连风太师叔一辈子也遇不到几个,天下用剑的大多还是五岳剑派这些凡俗,总不能让大家都铸剑为犁吧。
策梅洛定理(英语:Zermelo's theorem)是博弈论中非常有名的定理,以恩斯特·策梅洛命名。
在二人的有限游戏中,如果双方皆拥有完全的信息,并且运气因素并不牵涉在游戏中,那先行或后行者当中必有一方有不败的策略。
若应用至国际象棋,象棋,印度象棋,日本将棋等,策梅洛定理表示"要么先手一方有必胜之策略、要么后手有必胜之策略、要么双方有必不败之策略"。
策梅洛定理这篇论文在1913年以德文发表,1997年译为英文。并广为人知。
随着人工智能的发展。机器的算力已经可以碾压人类。其中阿法狗在围棋中碾压人类的超一流高手已经说明这个问题。
策梅洛定理并不能得出红必胜,也不能得出黑必胜,同时也不能得出必定和棋。
数学上也很难证明。
因为这是一个庞大的决策树。是一个NP问题。
因此要证明某种策略的存在,只能用电脑双手互博来例证。
目前有某种分支下(残局)下的必和,红必胜,黑必胜的情况而已。
补充如下:
根据策梅洛定理,中国象棋不应该要么红必胜,要么必和棋吗?
不正確。
策梅洛定理中結論是: 先行或後行者當中必有一方有必勝/必不敗的策略。
所以可以是黑不敗,反證。
既然结果就确定了,那游戏还有玩的必要吗?
结果是确定了 , 但對於人類來說是未知的
还是说策梅洛定理本身就是错的?
不能以此反證此定理
有一次我在王天一的直播间里看下棋。
王天一一边下棋,一边回答棋友的各种问题。
前十几步,双方你来我往,形成了均势。
棋友就在直播间里讨论,这个对手看起来很厉害。
王天一直接说了一句:“这哪里是很厉害,明明是要弄死我。”
又下了十几步,突然王天一又说了一句,“刚才上马这步错了,没解了。”
紧接着几步之后,王天一的马被对手吃掉,王天一投子认输。
作为在一旁观战的很多人,全程懵逼。
不能理解,王天一为什么提前几十步就知道结局了。
我也是通过复盘分析,才明白为什么: 对手是Ai,每一步都是最优解。
王天一的大多数行棋,同样也能做到最优解。只有极少数的几步棋,做到了99%。
然后这1%的差距,不断扩大叠加。王天一的水平,很快发现自己失势,然后失马,最终败北。
所以这个定理是正确的。
中国象棋的一先,对于同等级的高手来说,优势很大。
就像五子棋,执黑可以必胜。比这个更容易理解的是,和机器猫石头剪子布,出布必胜。
象棋类游戏,两个Ai对战,必和。
王天一那个层次的高手,对战AI,一心求和是能做到的,想赢根本不可能。
所以红方必胜或平,没有问题。
这就是赵王要把廉颇换为赵括的原因,四十对四十,咱主动进攻又是先手,怎么搞了个全军覆灭呢?因为老帅(粮道)被干了。你说括大佬要是懂策梅洛定理,至不济也搞个和棋么是不是,哀哉赵王,惜哉策梅洛!
而且,抛开棋手能力的因素,根据策梅洛定理:①有可能红必胜(占据先手),②有可能红必和(先手占优势但不足以赢棋)③先手必败:因开局时双方住置最平衡,红先动子,黑方针对红方这一步走出最优棋,以此类堆黑必胜,(因为强制走子不能原地不动)
不是的,你理解错定理了。
策梅洛定理:在二人的有限游戏中,如果双方皆拥有完全的资讯,并且运气因素并不牵涉在游戏中,那先行或后行者当一必有一方有必胜/必不败的策略。
什么意思呢?比如以象棋举例,以下四个情况之一必然发生:
1、红棋有必胜策略
2、红棋有不败策略
3、黑棋有必胜策略
4、黑棋有不败策略
把3、4翻译成红棋就是:
3、红棋必败
4、红棋最多和棋
那么,如果象棋的最终结论是3,那么红方就必败。所以你提的问题本身就有问题。
根据策梅洛定理,中国象棋不应该要么红必胜,要么必和棋吗?既然结果就确定了,那游戏还有玩的必要吗?为什么中国象棋那么有名?还是说策梅洛定理本身就是错的?
然后我来解释附加的这句话。
这句话其实核心问题就是:
为什么结果确定的游戏还有玩的必要?
原因很简单,以人类的计算能力和记忆能力,不能做到所谓的最优解。
比如说,我们假设红棋有必胜策略,第一步走炮二平五。
那么请问,接下来黑棋的第一步,我能说出来的至少有
炮2平5 炮8平5 马2进3 马8进7 象7进5 象3进5
你想要赢,就需要把这六步对应的所有方式全部知道应对方案。你背的下来吗?
策梅洛定理没错,下象棋的选手也不是吃饱了撑得没事干。
策梅洛定理的前提是 双方完全了解了博弈的每一个变化。
举个简单的例子比如井字棋,稍微研究两局就可以摸透所有变化——比如先手走中间,后手必须走角上否则就输了。那对于这两个已经摸清所有变化的棋手来说,玩井字棋已经没有意义了。因为双方都会走出最强招法(最优解),而另一方面后手有必不败策略,所以他们两个怎么走都是和棋。
而我们来看看井字棋的升级版——13路五子棋。这个变化就多了,一般人无法摸透所有变化,这时候这个游戏对于人类来说就有的玩,各有输赢。而对于顶级电脑来说,他们可以穷举出所有招法,从而走出最优解,一旦走的不够优就是输棋。那把游戏交给电脑来玩的结果就是 和棋
再来看看象棋,双方如果只有一个车,那很显然谁都赢不了,哪怕你让我去面对王天一,我都输不了,这其实是因为你自己在心里穷举了所有变化(或是早就想通了必定可以求和的策略,一定能走出最优解)
而如果再多给双方一对马炮呢?明知道是和棋,但是你有把握顶和王天一吗?而把子力给双方配齐,你明知道是和棋,你有把握撑过20回合吗?
所以下象棋不同于玩井字棋,因为深度不同。下象棋你没法穷举得出结果,不需要你走出最优解(事实上没人知道最优解是哪一步),而比的是谁下的更优。王天一为什么牛逼,就是因为他更接近最优解。
地球online这个游戏的最终结果就是下线,要不你别玩了。
CPU不行的时候,不要运行太大的程序。
所以我建议题主在思考能力不足的情况下,不要涉猎过于复杂的问题。
至少你先把这个定理看懂再思考问题。
我随便查了一下这个定理:
来看:如果……,并且……,那么,必然有( 存在 )必胜的策略。
首先是有一个理想化的前提,然后这个策略也只是在理论上被证明存在。
好,我拿围棋举个例子,下个结论:
你和柯洁对弈,你肯定有战胜柯洁的策略,你只需要跟阿尔法狗一样下就行了。
有意义吗?
象棋也好,围棋也罢,比的就是双方“资讯”的掌握程度和熟练运用的能力。结果你跟我讲,在双方“资讯掌握相同”的情况下,存在必胜的策略???
这个定理只是在数学意义上严格证明了个人努力是有意义的,并没有说你不用努力了。
明白?
你看,你看这个题主啊,才下两步,就忘了(所有分支),真的太逊了。
策梅洛定理的证明其实很简单,用数学归纳法就行,这也是为什么需要有有限个可能的对弈的结局。
最近看了很多范大将军的采访,我仿写一个
“从另一方面来说,题主是穷举中国象棋分支树最早的选手……”
“我都已经说了,你连将杀的基础都没打好,你能跟我保证在左马盘河和急进中兵这样关键的变化上你能赢啊?
务实一点,我劝你把象棋的这个基本理念先搞懂。《弈林新编》看的蛮好的,你把这书扔了干什么你告诉我。在业6输个1比5你倒告诉我怎么解释?”
标签:中国象棋,红方,或必