宇宙溯源吧 关注:40贴子:1,887
  • 5回复贴,共1

【长文恐惧症】不要再用穷举法来侮辱围棋和阿尔法狗

只看楼主收藏回复


阿西的HCl镇楼
前言:
自从阿尔法狗第一次赢了欧洲冠军后,就一直有人在说穷举法,叫嚣着不过是个职业二段,什么时候干掉李世石再说话;现在阿尔法狗光速打脸,第一局比赛中干掉李世石,依然有人在拿穷举法狡辩。
每次看到高举【穷举法大法好】的人,我真想一棋盘加361颗棋子全塞到他的嘴巴里。
楼下开始放正文。


IP属地:浙江1楼2016-05-27 13:53回复
    一、围棋他妈的到底有多少种可能性?
    让我们先来看看常用的两种估计方法。
    1.假设不会出现大家都被提光再从头再来的情况,那么,第一步有361种选择,第二步有360种选择,以后的情况大致如此,我们就以361为界,那么变化数是361!,约为10的768次方。
    2.另一种估计方法大概是宋朝的沈括老先生首先使用的:棋盘上每个点有黑、白、空三种状态,所以围棋变化数是3的361次方,约为10的172次方,用沈老先生的说法,就是“连书‘万’字四十三”。这虽然也很大,但比起前面的估计值来,小得实在是太多了。
    不幸的是,沈老先生的估计方法是错误的。他只考虑了这种种状态,却没有考虑这些状态间的相互关系。就比如数学中的图,沈老先生只考虑了顶点的总数,却忘了把连接顶点的边算进去了。
    那么回到第一种方法计算出来的数值:10的768次方,这又是个什么概念呢?我们知道,宇宙中所有基本粒子的总数,据估计为10的80次方。然而,对我们来说,10的768次方和10的80次方,又和无穷有什么区别?(这意味着把已知全部宇宙的物质做成内存,每个原子,干脆,每个夸克存储一种状态,都是远远不够的)
    看到这里,你一定会想,哇,围棋的变化这么多啊!
    那你就太天真了!


    IP属地:浙江2楼2016-05-27 13:53
    回复
      很遗憾的是,连第一种估计方法都是错误的。围棋真正的变化数,连10的(3的361次方)次方都挡不住,大学学历的人都清楚,一旦出现指数天梯,那这个数字有多大已经是不可想象的了。
        如果从结局入手的话,棋盘上一共361个点位,局终时每一个点位上不是白子就是黑子,要么就是空,也就是说每一个点位有三种选择,那么按照排列组合的规律,围棋的结局就有3的361次方=1.7408956e+172
      《梦溪笔谈》的作者沈括,就是用这种方法在计算,按他的话说,这个数字的大小是——连书“万”字四十三次!
      这还单单只是结局的数量,因为围棋过程中势必会出现打劫——也就是双方互相提子的情况,这就导致了哪怕是同一种结局,也可能拥有着无数种完全不同的过程:比如这一局在第N手提子、那一局在第N+1手提子;这一局连提两子,那一局隔一子提一子……沈括的这种算法,其实只是一个终态或者说静态值,并没有包含对弈过程中可能出现的动态变量。比如“2+3=?”沈括确实计算出了“5”这个答案,但是反过来说“5”却不一定等于“2+3”,它也可以等于“1+4”,如果取上小数的话,能够让“5=?+?”这个等式成立的值就是无穷多!
      也就是说:围棋结局的数量确实是一个有穷的数值,但是导致这些有穷结局的过程量,却是无穷的!所以说围棋的棋局数量,是没办法枚举出来的,又所谓:纵横十九行,围棋千古无同局! 


      IP属地:浙江3楼2016-05-27 13:53
      回复
        二、你说了那么多废话,你怎么还不说阿尔法狗是怎么下围棋的?
        阿尔法狗之所以能够战胜九段高手李世石。我们先来看看官方怎么用专业名词跟民众吹逼的:
        “它背后主要的方法是 Value Networks(价值网络)和 Policy Networks(策略网络),其中 Value Networks 评估棋盘位置,Policy Networks 选择下棋步法。这些神经网络模型通过一种新的方法训练,结合人类专家比赛中学到的监督学习,以及在自己和自己下棋(Self-Play)中学到强化学习。这不需要任何前瞻式的 Lookahead Search,神经网络玩围棋游戏的能力,就达到了最先进的蒙特卡洛树搜索算法的级别(这种算法模拟了上千种随机自己和自己下棋的结果)。我们也引入了一种新搜索算法,这种算法将蒙特卡洛模拟和价值、策略网络结合起来。”
        说了半天,阿尔法狗这些看起来很牛逼的什么鬼网络是什么意思呢?
        其实很简单,阿尔法狗的两个网络——价值网络和策略网络,就是围棋中常说的“大局观”和“算子能力”。
        价值网络给予了阿尔法狗对整个棋盘局势的判断,也就是大局观,大局观是人类棋手最大的优势,有了大局观,你可以在很短的时间内筛选掉绝大多数无用的落子。如今阿尔法狗装备了价值网络,使得阿尔法狗能够快速的判断整个棋盘哪里最为重要最为紧迫,做到主动出击而不是被动应战,能够“吃着碗里看着锅里”而不是“捡了芝麻丢了西瓜”。这是他能够从一堆围棋AI中脱颖而出的很大一个原因。
        策略网络则是旧调重弹了。下过棋的都知道,对这一步棋后续的发展,能够预测得越后,一般就说明这个人水平越高。拿围棋举例,经过一段时间学习的人(达到了可以独立依照正常套路对局能力)一般可以思考落子后的两到三步的大部分可能性,达到段位级别至少能够分析五步,而对于李世石这种职业九段的大神来说,给他时间,他能分析到之后十多步的情况。然而这在阿尔法狗的策略网络面前都是不堪一击的,十多步的预测对于阿尔法狗来说那就是饶痒痒,可以说,在局部作战,阿尔法狗是无敌的。


        IP属地:浙江4楼2016-05-27 13:53
        回复
          四、回归标题
          总而言之我跟你们这些人废话了这么多,就是想说一句:
          你们这些整天穷举的啊,偶摸希裸衣!你们呐,穷举也是要按照基本法来的!不懂围棋又不懂编程,就不要瞎逼逼,不然闹出笑话下不了台的话就excited了!


          IP属地:浙江6楼2016-05-27 13:54
          回复
            六、穷举法(补充)
            什么是穷举法?三体吧的起点是维基百科,落点是百度百科,于是我都翻了一遍给一些不理解概念的人来看。
            维基百科
            计算的复杂性最明显的算法就是穷举法,即寻找一切组合并取其最短。这种算法的排列数为n!(n的阶乘,其中n为节点个数)。用动态规划技术,我们可以在O(n22n))[1]时间内解决此问题。虽然这仍然是指数级的,但要比O(n!))快得多。
            百度百科
            本词条由“科普中国”百科科学词条编写与应用工作项目提供内容并参与编辑
            穷举法的基本思想是根据题目的条件确定答案的范围,并在此范围内对所有可能的情况逐一验证,直到全部情况验证完毕。若某个情况验证符合题目的全部条件,则为本问题的一个解;若全部情况验证后都不符合题目的全部条件,则本题无解。穷举法也称为枚举法。
            爱问知识人
            穷举法也叫枚举法或列举法。
            在研究对象是由有限个元素构成的集合时,把所有对象一一列举出来,再对其一一进行研究。


            IP属地:浙江7楼2016-05-27 13:54
            回复