您好、欢迎来到现金彩票网!
当前位置:秒速时时彩 > 搜索树 >

AlphaGo是如何被训练成围棋之神的?真相了

发布时间:2019-06-07 06:59 来源:未知 编辑:admin

  编者按:本文作者为彩云天气创始人兼 CEO 袁行远,由雷锋网整理自其知乎专栏,获授权发布。

  袁行远:19年前计算机击败国际象棋冠军卡斯帕罗夫的情景还历历在目,现在计算机又要来攻克围棋了吗?

  1933年,东渡日本19岁的吴清源迎战当时的日本棋坛霸主、已经60岁的本因坊秀哉,开局三招即是日本人从未见过的三三、星、天元布阵,快速进击逼得对方连连暂停“打卦”和弟子商量应对之策。随后以“新布局”开创棋坛新纪元。难道阿尔法狗会再造一个“新新布局”?

  作为一个关心人工智能和人类命运的理科生,近些天刷了好些报道,记者们说“阿尔法狗是个价值神经网络和策略神经网络综合蒙特卡洛搜索树的程序”,但我觉得光知道这些概念是不够的。我想看看“阿尔法狗”的庐山真面目。

  这样,设计一个围棋人工智能的程序,就转换成为了,任意给定一个s状态,寻找最好的应对策略a,让你的程序按照这个策略走,最后获得棋盘上最大的地盘。

  如果你想要设计一个特别牛逼惊世骇俗的围棋程序,你会从哪里开始呢?对于在谷歌DeepMind工作的黄士杰和他的小伙伴而言,第一招是:

  深度卷积神经网络早在98年就攻克了手写数字识别,近些年在人脸识别、图像分类、天气预报等领域无往而不利,接连达到或超过人类的水平,是深度学习火遍大江南北的急先锋。我们现在看到的Picasa照片自动分类,Facebook照片识别好友,以及彩云小译同声传译(软广出现,不要打我)都是此技术的应用。这等天赐宝物,如果可以用来下围棋,岂不是狂拽酷炫吊炸天?

  所以2015年黄士杰发表在ICLR的论文一上来就使出了“深度神经网络”的杀招,从网上的围棋对战平台KGS(外国的qq游戏大厅)可以获得人类选手的围棋对弈的棋局。观察这些棋局,每一个状态s,都会有一个人类做出的落子a,这不是天然的训练样本吗?如此可以得到3000万个样本。我们再把s看做一个19x19的二维图像(具体是19x19 x n,n是表示一些其他feature),输入一个卷积神经网络进行分类,分类的目标就是落子向量a,不断训练网络,尽可能让计算机得到的a接近人类高手的落子结果a,不就得到了一个模拟人类棋手下围棋的神经网络了吗?

  于是我们得到了一个可以模拟人类棋手的策略函数P_human,给定某个棋局状态s,它可以计算出人类选手可能在棋盘上落子的概率分布a = P_human(s),如下图:

  不咋地。黄士杰说P_human已经可以和业余6段左右的人类选手过招,互有胜负,但还未能超过当时最强的电脑程序CrazyStone[1,5],距离人类顶尖玩家就差得更远了。

  所以,为求更进一步,黄士杰打算把P_human和CrazyStone的算法结合一下,师夷长技以制夷,先击败所有的其他围棋AI再说。

  哦,那个算法是黄士杰的老师Remi Coulum在2006年对围棋AI做出的另一个重大突破:

  蒙特卡洛搜索树(Monte-Carlo Tree Search)是一种“大智若愚”的方法。面对一个空白棋盘S0,黄士杰的老师Coulum最初对围棋一无所知,便假设所有落子方法分值都相等,设为1。然后扔了一个骰子,从361种落子方法中随机选择一个走法a0。Coulum想象自己落子之后,棋盘状态变成S1,然后继续假设对手也和自己一样二逼,对方也扔了一个筛子,随便瞎走了一步,这时棋盘状态变成S2,于是这两个二逼青年一直扔骰子下棋,一路走到Sn,最后肯定也能分出一个胜负r,赢了就r记为1,输了则为0,假设这第一次r=1。这样Coulum便算是在心中模拟了完整的一盘围棋。

  我刚才从(S0, a0)开始模拟赢了一次,r=1,那么新分数=2,除了第一步,后面几步运气也不错,那我把这些随机出的局面所对应落子方法(Si,ai)的分数都设为2吧。然后Coulum开始做第二次模拟,这次扔骰子的时候Coulum对围棋已经不是一无所知了,但也知道的不是太多,所以这次除(S0, a0)的分值是2之外,其他落子方法的分数还是1。再次选择a0的概率要比其他方法高一点点。

  那位假想中的二逼对手也用同样的方法更新了自己的新分数,他会选择一个a1作为应对。如法炮制,Coulum又和想象中的对手又下了一盘稍微不那么二逼的棋,结果他又赢了,Coulum于是继续调整他的模拟路径上相应的分数,把它们都 1。随着想象中的棋局下得越来越多,那些看起来不错的落子方案的分数就会越来越高,而这些落子方案越是有前途,就会被更多的选中进行推演,于是最有“前途”的落子方法就会“涌现”出来。

  最后,Coulum在想象中下完10万盘棋之后,选择他推演过次数最多的那个方案落子,而这时,Coulum才真正下了第一步棋。

  蒙特卡洛搜索树华丽转身为相当深刻的方法,可以看到它有两个很有意思的特点:

  1)没有任何人工的feature,完全依靠规则本身,通过不断想象自对弈来提高能力。这和深蓝战胜卡斯帕罗夫完全不同,深蓝包含了很多人工设计的规则。MCTS靠的是一种类似遗传算法的自我进化,让靠谱的方法自我涌现出来。让我想起了卡尔文在《大脑如何思维》中说的思维的达尔文主义[6]。

  2)MCTS可以连续运行,在对手思考对策的同时自己也可以思考对策。Coulum下完第一步之后,完全不必要停下,可以继续进行想象中的对弈,直到对手落子。Coulum随后从对手落子之后的状态开始计算,但是之前的想象中的对弈完全可以保留,因为对手的落子完全可能出现在之前想象中的对弈中,所以之前的计算是有用的。这就像人在进行对弈的时候,可以不断思考,不会因为等待对手行动而中断。这一点Coulum的程序非常像人,酷毙了。

  但黄士杰很快意识到他老师的程序仍然有局限:初始策略太简单。我们需要更高效地扔骰子。

  如果某一步被随机到很多次,就应该主要依据模拟得到的概率而非P_human。

  这样就既可以用P_human快速定位比较好的落子方案,又给了其他位置一定的概率。看起来很美,然后实际操作中却发现:“然并卵”。因为,P_human()计算太慢了。

  一次P_human()计算需要3ms,相对于原来随机扔骰子不到1us,慢了3000倍。如果不能快速模拟对局,就找不到妙招,棋力就不能提高。所以,黄士杰训练了一个简化版的P_human_fast(),把神经网络层数、输入特征都减少,耗时下降到了2us,基本满足了要求。先以P_human()来开局,走前面大概20多步,后面再使用P_human_fast()快速走到最后。兼顾了准确度和效率。

  这样便综合了深度神经网络和MCTS两种方案,此时黄士杰的围棋程序已经可以战胜所有其他电脑,虽然距离人类职业选手仍有不小的差距,但他在2015年那篇论文的最后部分信心满满的表示:“我们围棋软件所使用的神经网络和蒙特卡洛方法都可以随着训练集的增长和计算力的加强(比如增加CPU数)而同步增强,我们正前进在正确的道路上。”

  看样子,下一步的突破很快就将到来。同年2月,黄士杰在Deepmind的同事在顶级学术期刊nature上发表了“用神经网络打游戏”的文章。这篇神作,为进一步提高MCTS的棋力,指明了前进的新方向:

  左右互搏,自我进化红白机很多人小时候都玩过,你能都打通吗?黄士杰的同事通过“强化学习”方法训练的程序在类似红白机的游戏机上打通了200多个游戏,大多数得分都比人类还好。

  “强化学习”是一类机器学习方法,Agent通过和环境s的交互,选择下一步的动作a,这个动作会影响环境s,给Agent一个reward,Agent然后继续和环境交互。游戏结束的时候,Agent得到一个最后总分r。这时我们把之前的环境状态s、动作a匹配起来就得到了一系列,设定目标为最后的总得分r,我们可以训练一个神经网络去拟合在状态s下,做动作a的总得分。下一次玩游戏的时候,我们就可以根据当前状态s,去选择最后总得分最大的动作a。通过不断玩游戏,我们对下总得分的估计就会越来越准确,游戏也玩儿得越来越好。

  机器学习的开山鼻祖Samuel早在1967年就用自对弈的方法来学习国际跳棋[7],而之前的蒙特卡洛搜索树也是一个自对弈的过程。但是现在黄士杰不仅有一个从人类对弈中学习出的P_human这样一个高起点,而且有一个神经网络可以从对弈样本中学习,有理由相信这次会有更好的结果。

  先用P_human和P_human对弈,比如1万局,就得到了一万个新棋谱,加入到训练集当中,训练出P_human_1。然后再让P_human_1和P_human_1对局,得到另外一万个新棋谱,这样可以训练出P_human_2,如此往复,可以得到P_human_n。P_human_n得到了最多的训练,棋力理应比原来更强。我们给最后这个策略起一个新名字:P_human_plus。这时,再让P_human_plus和P_human对局,在不用任何搜索的情况下胜率可达80%,不加任何搜索策略的P_human_plus和开源的MCTS相比也有85%的胜率。自对弈方法奏效了。

  既然P_human_plus这么强,我们先代入到MCTS中试试,用P_human_plus来开局,剩下的用P_human_fast。可惜,这样的方法棋力反而不如用P_human。黄士杰认为是因为P_human_plus走棋的路数太集中,而MCTS需要发散出更多的选择才好。看来,P_human_plus练功还是太死板,还没有进入无招胜有招的境界。

  没关系,黄士杰还有局面评价函数v(s)这一招,有了v(s),如果我可以一眼就看到“黑棋大势已去”,我就不用MCTS在想象中自我对弈了。但考虑到P_human_plus的招法太过集中,黄士杰在训练v( )的时候,开局还是先用P_human走L步,这样有利于生成更多局面。黄士杰觉得局面还不够多样化,为了进一步扩大搜索空间,在L 1步的时候,干脆完全随机掷一次骰子,记下这个状态SL 1,然后后面再用P_human_plus来对弈,直到结束获得结果r。如此不断对弈,由于L也是一个随机数,我们就得到了开局、中盘、官子不同阶段的很多局面s,和这些局面对应的结果r。有了这些训练样本,还是使用神经网络,把最后一层的目标改成回归而非分类,黄士杰就可以得到一个v( )函数,输出赢棋的概率。

  v( )可以给出下一步落子在棋盘上任意位置之后,如果双方都使用P_human_plus来走棋,我方赢棋的概率。如果训练v()的时候全部都使用P_human不用P_human_plus呢?实验表明基于P_human_plus训练的v,比基于P_human训练的v,棋力更强。强化学习确实有效。

  前两项和原来一样,如果待更新的节点就是叶子节点,那局面评估分就是v(SL)。如果是待更新的节点是上级节点,局面评估分是该节点所有叶子节点v()的平均值。

  如果v()表示大局观,“P_human_fast模拟对局”表示快速验算,那么上面的方法就是大局观和快速模拟验算并重。如果你不服,非要做一个0.5: 0.5之外的权重,黄士杰团队已经实验了目前的程序对阵其他权重有95%的胜率。

  深度学习、蒙特卡洛搜索树,自我进化三招齐出,所有其他围棋ai都毫无还手之力。99%的胜率不说,“阿尔法狗”还可以在让四子的情况下以77%的胜率击败crazystone。“阿尔法狗”利用超过170个GPU,粗略估算超过800万核并行计算,不仅有前期训练过程中模仿人类,自我对弈不断进化,还有实战时的模拟对局可以实时进化,已经把现有方法发挥到了极限,是目前人工智能领域绝对的巅峰之作。

  后记围棋是NP-hard问题,如果用一个原子来存储围棋可能的状态,把全宇宙的原子加起来都不够储存所有的状态。于是我们把这样的问题转换为寻找一个函数P,当状态为S时,计算最优的落子方案a = P(s)。我们看到,无论是“狂拽酷炫”的深度学习,还是“大智若愚”的MCTS,都是对P(s)的越来越精确的估计,但即使引入了“左右互搏”来强化学习,黄士杰和团队仍然做了大量的细节工作。所以只有一步一个脚印,面对挑战不断拆解,用耐心与细心,还有辛勤的汗水,才能取得一点又一点的进步,而这些进步积累在一起,终于让计算机达到并超过了人类职业选手的水平。

  因为一盘棋走一步需要3ms(P_human_plus遍历整个棋盘的时间),谷歌用大规模集群进行并行化计算,自我对弈3000万盘棋生成训练集只需要一天左右的时间[4],所以如果对弈更多棋局可以提高棋力的话,黄士杰他们早就做了。目前的方案可能已经达到了CNN网络能力的极限。完整的阿尔法狗不仅需要生成训练集,还要用训练集来生成局面评估函数v(),而这还使用了两周时间,一局比赛需要花掉4个小时,自我对局速度不够快,这也许是阿尔法狗并没有能够完全使用强化学习,而仅仅是在整个过程的一小部分使用左右互搏的原因。左右互博用的还不够多,这是一个遗憾。

  面对一个如此高难度的问题,计算机和人类都无法在有限时间内找到完全的规律(柯洁和李世乭比赛是一人有3小时时间思考,阿尔法狗今年3月和李世乭进行的比赛则是每人2小时)。计算机和人都是在对问题做抽象,然后搜索最佳策略。要下好围棋所需要的能力已经接近人类智力的极限:要有大局观、要懂得取舍、还要会精打细算,治理一个国家也不过如此。计算机可以学会围棋,就能学会很多一样难度的技能。在未来,也许围棋、自动驾驶、同声传译(「彩云小译」已经开始公测,欢迎体验)都会被一一攻克。甚至在数论、量子场论等领域,深度学习和搜索相结合,可能也会带给我们更多惊喜,比如攻克“哥德巴赫猜想”。

  虽然在智力方面AI有希望登峰造极,但高智商只是人类众多能力的一个方面。吴清源先生在方寸之间纵横无敌,但仍然漂泊一生,被命运推着前进。早年他做段祺瑞的门客,棋盘上把段祺瑞打的落花流水,弄得下人都没有早饭吃;后来东渡日本,三易国籍,留下许多遗憾。如果把“强人工智能”比作一个天才少年,虽然智商爆表,但其他方面还需要我们悉心加以引导。创造出“德才兼备,匡扶济世”的人工智能,才是我辈真正应该努力实现的目标。

  加关注,每日最新的手机、电脑、汽车、智能硬件信息可以让你一手全掌握。推荐关注!【

http://golfsandpiper.com/sousuoshu/245.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有