新棋吧 关注:5,694贴子:254,357
  • 29回复贴,共1

【科普】策梅洛定理,为什么?

只看楼主收藏回复

如题。
一楼不给看。


回复
1楼2017-06-25 14:39
    2018-11-19 00:29 广告
    二楼提前声明。
    插楼者删楼不解释。
    别怪我没提醒你。


    回复
    2楼2017-06-25 14:39
      策梅洛定理,为什么?
      首先我们来看看策梅洛定理是什么——
      假设一场对弈,双方知道全部的信息,包括自己的和对弈对手的,那么这场对弈总会有一方或双方有必胜或必不败的策略。
      有人看到这就会误解,难不成会出现双方都胜的策略?
      否。
      首先这种描述方式就容易令人产生误解。然而还就偏偏有人用了。这个人是谁我不用解释了。
      首先棋是一场零和博弈。
      当然,彻底的零和博弈建立在无和棋的前提下。
      那么就意味着,总有一方赢,另一方输。或是双方和棋。
      所以,对弈双方的“必”策略无疑会是以下三种当中的一种——
      1,先手方必胜;
      2,后手方必胜;
      3,双方和棋。
      那么,为何不是胜率平摊呢?
      很简单。双方都采用尽力让自己胜出或不败策略的时候,所使用的套路是固定的。
      没错,固定的!
      为何固定?
      因为这种下法是最优解。是先手应对后手的最优解,也是后手应对先手的最优解。而这种最优解只有一条道路可以走。


      回复
      3楼2017-06-25 14:47
        因为最优解的存在,算出最优解的高级机器人的对弈总会使用着最固定最优解的开局方式,在中途也用最优解的应对方法,在残局时也用优势方的最优击杀手段或是劣势方的最优防御手段。
        而一旦确定了这个,那么结局在一开始就被确定了。谁胜谁负,只能由最优解的结局说了算。
        而一方一旦使用了这种下法,另一方的任何反抗手段都无效。唯有最优解能够给对手最大的阻力。


        回复
        4楼2017-06-25 14:50
          甚至是开局第一步。
          在动物将棋中,棋盘12格。棋子共8个,小小的动物将棋中就已经出现了一个对于后手来说的最优解。先手无论如何都下不过已经算出必胜下法的后手。不信各位可以自己下载一个动物将棋zog试试。你找不出赢的手段。
          甚至是,先手无论如何迈出自己的第一步,后手总有反制手段。
          这就是动物将棋的策梅洛定理的体现。
          其他棋呢?一样。


          回复
          5楼2017-06-25 14:53
            然而下棋的开局那么多,如何确定哪一种是必胜策略呢?
            很简单,一种叫做“策略树”的东西。
            然而说简单很简单,说难也很难。因为我们知道这样东西,但却在如何探索这条路上犯了难。人有探索不到的策略树,而机器也往往大多数都在学习人本就正在采用的策略。所以才会出现如此多的机器与人对弈的镜头。


            回复
            6楼2017-06-25 14:56
              当然,上一层所说的,也是探索策略树的过程。
              那么,为什么会有策略树这种东西呢?
              首先,请把自己假想成任意一个回合制游戏的对弈者,你是先手方。
              那么,作为先手方的你,肯定会有几种走棋手段,或是说几种操作,而你要从中选择一种。(不正常的棋先不考虑在内,本帖只考虑正常的棋)
              然后,当轮到对手时,对手在你选择一种操作后,对手也有几种操作。她/他也选择了其中一种。
              接下来,又轮到你了,你又有几种的操作。那么你又需要从中选择一种。
              这就是策略树。你的第一步,是策略树的第一节“树枝”,而对手的第一步则是第二节树枝,然后你接下来的第二步就是第三节树枝…………以此类推。
              这棵策略树当中,有倾向你的树枝,有倾向对手的树枝,而玩家双方都需要从对手选择的那节树枝当中再次选择最倾向于自己那节树枝。
              直到选择的树枝尽头到了自己这边。这就是自己获得胜利的时候。
              这就是为什么会有最优解这种东西的原因了。


              回复
              7楼2017-06-25 15:05
                而策梅洛定理当中,最优解则是整个策梅洛定理的最核心的东西。它是建立在假设对弈双方完全知道策略树发展的前提下。
                这就是为什么说策梅洛定理当中假设双方知道完全的信息时必定会有必胜或必不败的策略了。


                回复
                8楼2017-06-25 15:07
                  而策略树当中的那个最优解,则是在玩家双方知道整个策略树后,决定整盘棋胜负的最核心树。
                  和棋?很简单,树杈的终点最终指向了河界。
                  哪一方胜?仍然很简单,树杈的终点最终倒向了那一方。
                  先手胜?就是树杈的终点最终倒向了先手。
                  后手胜?就是树杈的终点最终倒向了后手。
                  先后手胜负参半?很抱歉,我根本找不到那棵树枝。有谁能帮我找找?找得着算你厉害。


                  收起回复
                  9楼2017-06-25 15:12
                    完。从此楼开始,下方可自由发言。


                    回复
                    10楼2017-06-25 15:13
                      再仔细讲讲呗~


                      回复
                      11楼2017-06-25 15:24
                        @夏日的炎炎空中 的回答:
                        真是提出了个好问题啊,积分制。
                        然而积分制的存在看似让这个问题变得复杂化,最终目标还是争取够足够的分数。所以说只要棋子进入禁区达到了一定的次数,照样是一方胜。
                        所以说,仅仅是等于将一个策略树拆成了好几个策略树再根据场上情况进行选用。而其中一方完全可以算准了出现某一种情况之后立即切换到另一种必胜情况的策略树上,照样能够稳稳拿分。只不过由于布阵的存在,增强了后手一定的优势。也因此加强了平衡性。
                        看似难理解,换个合适的角度照样能够读懂。


                        回复
                        12楼2017-06-25 15:49
                          标题的“策梅洛定理,为什么?”我觉得应该是缩略句(显然没有动词),敢问这个缩略句的完整的样子是什么。。。


                          收起回复
                          来自iPhone客户端13楼2017-06-25 16:40
                            不知道楼主说什么其实,策梅洛定理的精髓就是:任何局面的客观结果存在唯一性,要么这方胜,要么那方胜,要么和棋!只能存在三种结果中的一种结果。就像中国象棋著名排局征西的客观结果就是和棋!而组合象棋舍得与不舍得排局的客观结果就是白方胜!


                            收起回复
                            14楼2017-06-25 17:01
                              博弈信息双方可见,回合制,有限游戏,但是算出最优解只能等着计算机技术突破,能突破到穷举象棋的地步


                              回复
                              来自Android客户端15楼2017-06-25 21:28
                                有一种更浅显的证明方法:
                                假设一种游戏双方总共有10轮,即20步。
                                先手方按照X方法走完第19步以后,如果后手方最后一步的候选步中还有能赢棋的走法,那么后手方一定会选择赢棋的走法,如果后手方最后一步的候选步中最好只能有和棋的走法,就会选择和棋的走法;或者说,只有后手方的所有选择都意味着输棋时,先手方第19步走X才能胜利。
                                我们可以通过第20步的所有情况,来标记先手第19步的走法X1,X2,X3,如果发现所有X中对于X来说最好的结果也是输棋,那么就可以认为对应的后手第18步是后手必胜的。用同样的方法可以再用第18步的结果标记对应第17步的结果,这样一直标记到第一步的结果,即可判断出这个游戏到底是先手必胜、必输还是必和。


                                收起回复
                                16楼2018-10-25 11:24
                                  楼主现在毕业了吗?


                                  回复
                                  来自手机贴吧17楼2018-10-27 23:23
                                    楼主现在毕业了吗?


                                    回复
                                    18楼2018-10-27 23:56
                                      这种东西只要找几个容易被破解的棋就知道了:成三棋,只要知道全部内容,基本是和棋;没有禁项的五子棋,不好意思,先手必胜。五子棋这个样子让我瞬间失去兴趣(不要跟我谈职业比赛,大多数人下五子棋哪管什么禁项)
                                      一个棋是先手必和还是先手必胜主要是看这个棋,你和人类下经常和棋,一遇到电脑杀得你毫无脾气,两人下棋拼的是计算力,老将背的棋谱肯定比年轻人多,但是下不过年轻人


                                      回复(1)
                                      来自手机贴吧19楼2018-11-08 01:14
                                        对了这还牵扯到一个问题,下棋啊,先手是占主动性的。先手中这个定理只能说明你技术不够,就不存在知道所有策略树了


                                        回复
                                        来自手机贴吧20楼2018-11-08 01:27
                                          目前象棋软件下棋远没有到先手必胜的程度,国象软件双手互搏还是胜负和各三分之一,拼的是计算力罢了,只有穷举了所有变化才有可能先手必胜。


                                          回复
                                          来自手机贴吧21楼2018-11-08 01:33

                                            扫二维码下载贴吧客户端

                                            下载贴吧APP
                                            看高清直播、视频!