Zero工作原理,阿尔法狗的前世今生

作者: 美高梅游戏官网娱乐  发布:2019-11-28

图片 1一,“阿尔法狗”为什么盯上围棋,而不是麻将?

2016年3月,Alpha Go Master击败最强的人类围棋选手之一李世石。击败李的版本,在训练过程中使用了大量人类棋手的棋谱。2017年10月19日,DeepMind公司在《自然》杂志发布了一篇新的论文,AlphaGo Zero——它完全不依赖人类棋手的经验,经过3天的训练,Alpha Go Zero击败了Master版本。AlphaGo Zero最重要的价值在于,它不仅仅可以解决围棋问题,它可以在不需要知识预设的情况下,解决一切棋类问题,经过几个小时的训练,已击败最强国际象棋冠军程序Stockfish。其应用场景非常广泛。

传说尧作围棋以教丹朱,如此算来围棋就有4000多年历史了。2009年的LG杯决赛,就被善于造势的韩国人渲染为“四千年之战”。当时对局的是李世石和古力,颇有中韩围棋此消彼长的天王山之战的意思。如今李世石又站在了历史的关头,肩负着人类四千年的高傲和尊严,只是对面坐着的是谷歌的计算机棋手阿尔法狗。谷歌,古哥,莫非前定。

AlphaGo Zero 采用了蒙特卡洛树搜索+深度学习算法,本文将尽可能用简单易懂的语言解释其工作原理。

围棋是什么?在计算机的眼里,她无非是一个桌面游戏。19*19的棋盘,黑白轮流走棋。一块棋没有气了,就得从棋盘上拿掉。最后无处可下了,谁占的地方大谁就赢。规则如此简单。

树搜索

treesearch

从一个棋盘的初始状态,开始思考下一步如何走。我们可以回顾一下我们思考的过程,我们会思考自己可以有哪几种走法,如果我走了这里,对手可能会走哪里,那么我还可以在哪里走。我和对手都会选择最有利的走法,最终价值最大的那一手,就是我要选择的下法。很明显这个思维过程是一颗树,为了寻找最佳的行棋点的过程,就是树搜索。

围棋第一手有361种下法,第二手有360种,第三手有359,依次类推,即一共有 361! 种下法,考虑到存在大量不合规则的棋子分布,合理的棋局约占这个数字的1.2%(Counting Legal Positions in Go). 约为2.081681994 * 10^170。这个一个天文数字,比目前可观测宇宙的所有原子数还要多。要进行完全树搜索,是不可能的。因此我们必须进行剪枝,并限制思考的深度。所谓剪枝,就是指没必要考虑每种下法,我们只需考虑最有价值的几手下法。所谓限制思考的深度,就是我们最多只思考5步,10步,20步。常见的算法是Alpha-beta剪枝算法。但是,剪枝算法也有它的缺陷,它很有可能过早的剪掉了后期价值很大走法。

但在人类的眼里,围棋早就超越了游戏的范畴。其中有历史,有礼仪,有美学,有人生哲理。本能寺变,淮上信至,十番棋,擂台赛,见证了多少历史;新布局,宇宙流,美学的大竹,石佛与妖刀,蕴含了多少风雅;入界宜缓,弃子争先,早成了无数人的人生信条。当计算机真的坐到自己对面时,人是五味杂陈的:我说这是人生,你却说这只是一场游戏。

蒙特卡洛方法

简而言之,蒙特卡洛方法(Monte Carlo method),是一种“统计模拟方法”。20世纪40年代,为建造核武器,冯.诺伊曼 等人发明了该算法。因赌城蒙特卡洛而得名,暗示其以概率作为算法的基础。

假设我们要计算一个不规则形状的面积,我们只需在包含这个不规则形状的矩形内,随机的掷出一个点,每掷出一个点,则N+1,如果这个点在不规则图形内则W+1。落入不规则图形的概率即为 W/N。当掷出足够多的点之后,我们可以认为:不规则图形面积=矩形面积*W/N。

要应用蒙特卡洛算法的问题,首先要将问题转化为概率问题,然后通过统计方法将其问题的解估计出来。

在浩如烟海的人类智力游戏中,围棋不过是一粟而已,其在民间的影响力,未必能比得上麻将和扑克。相比中国寻常巷陌的麻将桌子和赌城成千上万的扑克台子,下围棋多少有点曲高和寡的意思。

蒙特卡洛树搜索(MCTS)

1987年Bruce Abramson在他的博士论文中提出了基于蒙特卡洛方法的树搜索这一想法。这种算法简而言之是用蒙特卡洛方法估算每一种走法的胜率。如果描述的再具体一些,通过不断的模拟每一种走法,直至终局,该走法的模拟总次数N,与胜局次数W,即可推算出该走法的胜率为 W/N。

该算法的每个循环包含4个步骤:选择、扩展、仿真、反向传播。一图胜千言。

MCTS

图中N表示总模拟次数,W表示胜局次数。每次都选择胜率最大的节点进行模拟。但是这样会导致新节点无法被探索到。为了在最大胜率和新节点探索上保持平衡,UCT(Upper Confidence Bound,上限置信区间算法)被引入。所谓置信区间,就是概率计算结果的可信度。打个比方,如果掷了3次硬币,都是正面朝上,我们就认为掷硬币正面朝上概率是100%,那肯定是错误的,因为我们的样本太少了。所以UCT就是用来修正这个样本太少的问题。具体公式如下:

UCT公式

其中wi 是i节点的胜利次数,ni是i节点的模拟次数,Ni是所有模拟次数,c是探索常数,理论值为 √2,可根据经验调整。公式的后半部分,探索次数越少,值会越大,所以,那些被探索比较少的点,会获得更多的探索机会。

蒙特卡洛树搜索算法因为是直接模拟到游戏终局,所以这种算法更加的准确,而且并不需要一个明确的“估值函数”,你只需要实现游戏机制就足够了。而且,蒙特卡洛算法,可以随时终止,根据其训练的时间给予近似的最优结果。

但是对于围棋这种游戏而言,它的选择点依然太多,这棵树会非常的大。可能有一个分支早已被丢弃,那么它将不会被统计,这可能是李世石能够在第四局击败AlphaGo的主要原因。对于这类情况,我们依然需要依赖一个好的估值函数来辅助。

那么为什么人工智能如此青睐围棋呢?为什么不是“AlphaMajo”挑战四川麻将高手,或者是“AlphaHoldem”挑战德州扑克冠军呢?其原因有三:

深度学习

近年来,深度卷积神经网络在视觉领域取得很大的成功,如图片分类,人脸识别等。深度学习的网络结构在此不赘述,简而言之,深度学习是一个最优化算法。

我们可以将深度神经网络理解为一个黑盒,这个黑盒接收一批输入,得到一个输出,并根据输出计算出损失(误差),这个误差会反馈给黑盒,当给了足够多的数据之后,这个黑盒将具备一个特性,就是使误差最小化。

如果这么说还是难以理解的话,可以打个比方:深度神经网络是一种生物,它喜欢吃糖,有学习的能力,你给它看一张图片,它告诉你是猫还是狗,如果它猜对了,你就给它一颗糖,猜错了,就不给糖,久而久之,它就有了分辨猫狗的能力。作为创造者,你甚至不知道它是如何分辨猫狗的,但是它做到了,看得越多,识别的就越准。

这里至关重要的是——输入是什么?输出是什么?什么时候给糖的动作,也就是损失函数如何设计?在实际的操作过程中,网络结构的设计也很重要,这里不再细述。

对于围棋来说,深度网络可以用来评估下一步的主要选点(降低树的宽度),以及评估当前局面的值。

其一,围棋有简单的输赢规则 (explicit winning condition)。这一点非常重要,因为电脑需要对每一个决策的好坏做精确、量化的评估。把围棋下好可能需要十年,但初学者就能判断一盘下完的棋谁输谁赢。如果规则本身比较模糊,可以去想象电脑和人类比拼现代诗或者抽象派绘画,会出现什么样的结果。

AlphaGo Zero

在AlphaGo Lee版本,有两个神经网络,一个是策略网络,是一个有监督学习,它利用了大量的人类高手的对弈棋局来评估下一步的可能性,另一个是价值网络,用来评价当前局面的评分。而在AlphaGo Zero版本,除了围棋规则外,没有任何背景知识,并且只使用一个神经网络。

这个神经网络以19x19棋盘为输入,以下一步各下法的概率以及胜率为输出,这个网络有多个batch normalization卷积层以及全连接层。

AlphaGo Zero的核心思想是:MCTS算法生成的对弈可以作为神经网络的训练数据。 还记得我们前面说过的深度学习最重要的部分吗?输入、输出、损失!随着MCTS的不断执行,下法概率及胜率会趋于稳定,而深度神经网络的输出也是下法概率和胜率,而两者之差即为损失。随着训练的不断进行,网络对于胜率的下法概率的估算将越来越准确。这意味着什么呢?这意味着,即便某个下法AGZ没有模拟过,但是通过神经网络依然可以达到蒙特卡洛的模拟效果!也就是说,我虽然没下过这手棋,但凭借我在神经网络中训练出的“棋感”,我可以估算出这么走的胜率是多少!

AlphaGo Zero的对弈过程只需应用深度网络计算出的下法概率、胜率、MCTS的置信区间等数据即可进行选点。

其二,围棋是信息对称的,或者说是信息完整的 (perfect information)。面对棋盘,电脑和其人类对手看到的是完全一样的信息。象棋和国际象棋亦是如此。麻将、扑克和四国军棋则不同:每个玩家只能看到自己一方的信息,而必须通过对手的行为去推测他的底牌。这就不难解释,为什么久经沙场的麻将老手往往输给不按常理出牌的新手,以及为什么德州扑克里有层出不穷的骗术与心理战。信息的完整和对称,让电脑可以做绝对理性的决策:不管你为什么这么下,我只要下当前局面下最好的一手就行了。

AlphaGo Zero 论文节选

AlphaGo Zero增强学习过程

a:自我对弈过程s1,...,sT。 在每个状态st, 使用最近一次的网络fθ,执行一次MCTS αθ (见图2)。 下法根据MCTS计算的搜索概率而选择,at ~ πt. 评价终止状态sT,根据游戏规则来计算胜利者z。
b: AlphaGo Zero的神经网络训练。网络使用原始的棋盘状态st作为输入,通过数个卷积层,使用参数θ,输出有向量 pt, 表示下法的分布概率,以及一个标量vt,表示当前玩家在st的胜率。网络参数θ将自动更新,以最大化策略向量pt和搜索概率πt的相似性,并最小化预测赢家vt与实际赢家z的误差。新参数将应用于下一次自我对弈a的迭代。

AlphaGo Zero 蒙特卡洛树搜索过程

a: 每次模拟选择的分支,有最大Q+U, 其中Q是动作价值,U是上限置信,U依赖于一个存储在分支上的优先概率P和该分支的访问次数N(每访问一次N+1)。
b: 扩展叶节点,神经网络(P(s, .), V(s)) = fθ(s)评估s; 将向量P的值被存储在s的扩展边上。
c: 根据V更新动作价值(action-value)Q,反映所有该动作的子树的平均值。
d: 一旦搜索结束,搜索概率π被返回,与 Ν^(1/τ) 成正比,N是每个分支的访问次数,而τ是一个参数控制着温度(temperature)。

其三,围棋广阔的搜索空间,带来的挑战和诱惑是电脑无法抗拒的。人类下象棋和国际象棋早已沦为电脑的手下败将,而围棋至少还能期待柯洁。

AlphaGo Zero的应用

AGZ算法本质上是一个最优化搜索算法,对于所有开放信息的离散的最优化问题,只要我们可以写出完美的模拟器,就可以应用AGZ算法。所谓开放信息,就像围棋象棋,斗地主不是开放信息,德扑虽然不是开放信息,但本身主要是概率问题,也可以应用。所谓离散问题,下法是一步一步的,变量是一格一格,可以有限枚举的,比如围棋361个点是可以枚举的,而股票、无人驾驶、星际争霸,则不是这类问题。Deepmind要攻克的下一个目标是星际争霸,因为它是不完全信息,连续性操作,没有完美模拟器(随机性),目前在这方面AI还是被人类完虐

所以看到AG打败人类,AGZ打败AG,就认为人工智能要打败人类了,这种观点在未来可能成立,但目前还有点危言耸听。距离真正打败人类,AGZ还差得很远。

二,电脑学下围棋,到底有多难?

围棋究竟有多难呢?对人类棋手来说,这很难量化。聂卫平曾谦虚地表示“围棋境界高不可及,我也只能算是刚刚入门。” 职业棋手经常被问到与“围棋之神”的差距:有人说让两子,柯洁说让先,有人则认为围棋的发展接近尽头,众说不一。人类的视野总是被眼前的山挡住,等爬到山顶,才知道山外有山。

对计算机来说,这个问题就好回答得多。围棋究竟有多少种变化呢?如果对每一种变化我都能判断局面好坏,那我岂不就是每步都能走到最优的围棋之神了吗?早期的人工智能的设计者们的确是这样想的。

作者简介

桂糊涂,多年从事服务端架构工作,2015年开始机器学习相关研究,现任某互联网公司CTO。长期招聘高可用架构、机器学习、Go、node.js、移动端开发等优秀工程师

图片 29(3的9次方,即9个3相乘)=19,683种状态。就算考虑到落子的顺序,也不过是9!

362,880种变化。评估不到一百万种变化的优劣,对当今的计算机来说,自然是小菜一碟。

但是这个办法用得围棋上,一下子就傻眼了,变化太多!

那么围棋的变化有多少呢?如果也考虑每个交叉点有黑子、白子、无子三个状态,那么一张围棋盘的状态是3361种,除去实际不可能出现的状态,大约是10170。相比起来,国际象棋的状态数只有不到1050,这与围棋的复杂度相比较,完全可以忽略不计。如果考虑行棋的顺序,那么围棋有大概361!种变化,或者说是10768(实际上没有这么多,因为总有不能落子之处)。无论哪一个,都是天文数字,因为宇宙中可观测的原子的总数,也无非是1080。

或许有人说,围棋之神也不一定每手都算到底吧,往后推算个三五十步差不多了。好,序盘的时候推算50步大概有超过10120种。10步?1024。就算只推5步也有超过2∗1012种变化。就算评价一种变化只需一个纳秒,那么下这一手也要40分钟。何况对计算机来说有更严肃的问题:不走到底我怎么知道谁好谁坏?

看起来太难了!那么棋盘小一点会不会简单一点呢?答案是肯定的。在13*13的棋盘上,变化的个数降低到了10304。9*9的棋盘上则只有10120。张栩自创的四路棋,变化数只有1013,而状态数更降低到了几千万个:仍然很多,但对计算机来说完全可以处理。

好了,现在我们知道围棋之神和宇宙之神大概是同一位。她既然能洞悉棋盘上所有的变化,大概也熟悉宇宙中所有的原子。AlphaGo真的能穷尽每一个变化吗?没关系,就算能也并不恐怖。我们明天就把棋盘扩大到21路,那就算全宇宙的原子都变成AlphaGo也不行了。

三,早期的计算机围棋靠人教套路

计算机当然不是围棋之神。你可以把他想象成一个天赋异禀的少年,想要挑战武林高手。他内功极强,动作极快,但不会招数(想想刚刚学会九阳神功的张君宝或者张无忌),他如何才能战胜招法娴熟的武林高手呢?

由于对天文数字般的围棋变化的恐惧,最早的计算机围棋,选择了模仿人类的方式。你会我不会,但你走哪、我就走哪总会吧。这也是被专业棋手戏称为“背棋谱”的方式。小飞挂角,应以小飞。你逼住,我就跳,你跳,我就跟着跳,被人走得多的总是好的。大量的围棋知识如定式、手筋等,就这样从棋谱中提炼出来,然后被程序员以规则的方式告诉电脑。然后,电脑在实战中按部就班跟着走。著名国产围棋软件“手谈”的早期版本,就是走的这个路子。

这样的算法的棋力当然与规则库的完备程度相关,但基本上是相当低下的。见一招流星飞堕,便会应以一招花开见佛,这充其量是林平之他爹的水平。这种背定式的算法,实战稍微变化一下,小飞挂变成大飞挂,跳着走变成飞着走,电脑就立刻感到面目全非,找不到北。

当然,程序员也有对策:他们在“死记硬背”之上,逐渐加入了许多模糊匹配的尝试。在实战中见到略有不同的场面下,也可以走出下一手。这可以看成一定程度上的举一反三。当然,在差之毫厘、谬以千里的中盘战斗里,这样的模糊匹配很难奏效。

“背棋谱”的算法,还有一个重大缺陷,就是这些规则绝大多数都限于窄小的局部,而对全局棋子的协同则毫无章法。早期的围棋程序,最怕“征子”,即是这个缺陷的典型体现。

既然背棋谱的下法缺陷如此明显,为什么还是计算机围棋的程序员们的第一感呢?从计算机的角度讲,背棋谱极大地缩小了选择的空间。挂角除了小飞、跳、夹、尖顶、靠出,大概也没有多少应法了吧。这样值得考虑的选择就变得很少,大大减轻了电脑的计算强度。

本文由美高梅手机登录网站发布于美高梅游戏官网娱乐,转载请注明出处:Zero工作原理,阿尔法狗的前世今生

关键词:

上一篇:有限的障壁,或许也不坏
下一篇:没有了