[心得] 围棋AI AlphaGo 之我见

楼主: kafai (猪仔包 PigSonBow)   2016-03-13 15:30:45
零、前言
先描述一下我的棋力。我在 kgs 的帐号是只跟围棋AI 下的,去年下到 1k,也会掉下2k
,但由于时间问题,我半年没下过,最近开出来在不熟的情况下掉到3k,我相信如果下个
几十盘可以重回2k 甚至1k。
而我在 oro 围棋是跟人下的,我开了一个25k 的帐号杀到上4k,再开了一个4k的帐号,3
胜1败后就没有再下过,要上3k也是时间问题。
简单来说,我的棋力大致在1至3k 之间吧。(我希望有生之年能上业余段吧)
另一方面,我是电机博士,现为大学讲师,虽然我的研究领域是电子、通讯,但对控制理
论也有所知。以下就根据这两个基础开展。
一、围棋AI的两大流派
第一派的代表当然以 GnuGo 为代表,不是因为它最强,而是因为它免费,所以很普及,
同一流派的手谈可以到业余初段左右。这流派的做法是记住基本棋形,再加点穷举,对于
角部或边上定式,都不会有问题,棋形下得十分正,局部的简单死活绝对会给你正解,但
缺点是棋会比较缓,大局观不佳,会出现自己在炮大龙时脱先,被对方加补一刀大龙愤死

另一派就像 AlphaGo 或是 AyaBot 等,会用 Monte Carlo Tree Search (MCTS) 去找出
最佳嬴棋路径。后者我在 kgs 下得最多,它的棋力从4k 到至少2d 都有。这派的棋会比
较难以捉摸,特别是序盘,天马行空,不会跟着走定式,大局观很好(也不好,后面再说)
,但反而局部的正解可能会漏掉。比如 AyaBot (1k) 会在征子不利下跑征子,
computer-go digest 有人提过用DNN 在复杂的对杀是会出错的。至于要多复杂呢?后面
就再作讨论。另一重要特征是,它喜欢嬴一目半或半目,只要它领先,它就会放回来,跟
AyaBot 下输的话,十盘有九盘是输一目半的,剩下是输大多,它来不及还回来。而当它
判断要输的时候,它就会下出胜负手甚至无理手,只要应对得宜,你便能守住优势,甚至
马上胜出,否则便会被追近甚至被逆转。
二、关于 AlphaGo
正如上节所讲,AlphaGo 是用 MCTS 的,同时在 Nature 中提到,它用了类神经网络(NN)
运作,这是 Google 厉害创出来的吗?非也!这两个技术其实早就用在围棋 AI 上,正如
computer-go digest 有人说到,Google 是靠庞大资源,将原有的技术推到极致。也有
人说,如果打败李世石是一个蛋糕,那 Google 就是蛋糕上的一颗樱桃。
比赛时它是用1000台 server 跑 grid 来运算的。而另一 Google 的强项就是它的信息量
,去年十月对战樊麾,它的 NN 是用大量业余围棋谱来 train 的,这次对李世石,则是
用职业棋谱来 train 的。如果用龙珠来做比喻,AlphaGo 就好像斯路,集各家之大成。
目前 AlphaGo 领先3:0,那么 AlphaGo 就攻克了围棋吗?还差很远。
三、类神经网络(NN)
类神经网络这个名子听起来很 fancy,但说穿了其实就是 adaptive filter。对于用职业
棋谱来 train 的 model,很简单可以想像得到,它的水准会是职业棋手的平均,最高的
由于太稀有,是不可能 train 入 model 内。另外加上一些自我学习的机制,它就会是平
均偏上的水准(偏上多少就很难说了)。那么为什么它能轻取李世石?因为它不会所谓误算
,加上由于越接近后盘,变化越少,电脑越能穷举出最佳路径,要跟 AI 收大官子的话,
肯定是可以亏个贴目。但到了小官子,职业棋手还是可以算得足够精确的。
四、Monte Carlo Tree Search (MCTS)
MCTS 对于 AlphaGo 来说是决定计算深度的。在 kgs 上,AyaBot (1k) 是每手棋 1200
sims。每上升一级是双倍。假设李世石能让 1k 十子的话,那么 AlphaGo 合理估算是每
手棋 一百万 sims。就算能再多两子,也就四百万。(这是官方说的吗?当然不是,但作
为一个工程领域的科研人员,凭线索推估一些参数是应有的技能,这个数不一定准,但也
不需要很准,可是比没有来得好。)那要李世石能看到过百万个变化图才能下得过吗?也
并不是,因为那过百万 sims 里面大部份是不会发生的,那只是在算机率而已,要将
sims 的数目转为李世石要算到多少手也是不可能的。但这关乎到究竟多复杂的局面才能
让 AlphaGo 吃到苦头。我认为 game 1 的混战并不够复杂,因为至少我还看得懂,而我
相信假如李世石能发挥出他算路的极致,是可以杀爆 AlphaGo 的。可能要像籐泽秀行长
考3小时杀爆加籐正夫大龙的复杂度。又或者是有回古李大战,古力下半盘的棋筋已被擒
获,古力突然棋盘上方2路靠断,所有解说都说莫名奇妙的损进去,结果下一步古力被擒
获的棋筋马上暴动,李世石马上投子。要靠这种要超长算路才有机会进入 AlphaGo 的那
一百万以外的领域。
(写这里是快要进入第四战的时间,但我相信并没有所谓马后炮的问题)
五、从 AyaBot 估计 AlphaGo 的可能弱点
基本上我在 kgs 是从 4k 起是主要杀 AyaBot 升到1k的,到1k只要我能专心下,是胜比
负稍多的,大概是一年可以升一级的速度。那么我这节就从 AyaBot 估计 AlphaGo 的可
能弱点。你可能会 argue AyaBot 弱 AlphaGo 那么多,你好意思拿它们来比。但从科技
层面来看,它们用了很接近的方法,AlphaGo 强那么多的原因在于它有更多的运算资源去
提高它的强度,还有可能有些参数的微调做得更好。所以可以预期 AlphaGo 有 AyaBot
类似的弱点,只是由于它的计算深度增加了,把它的弱点藏得比较好而已。正如在
computer-go digest 上一堆从事围棋 AI 的人员也清楚知道 AlphaGo 的弱点在哪里,
只是它们就是没有资源把这个 AI 这样 implement 出来。要是职业棋手明确清楚知道这
些弱点而发起猛攻,人类要嬴 AlphaGo 并不是问题。
先描述一下对 AyaBot 是要怎么嬴,基本上在后盘翻盘是近乎不可能,在嬴 AyaBot 的棋
之中,没有过百盘也总有几十盘,我只试过一次是后盘逆转的。基本上要嬴的话,是开局
一个局部杀爆 AI(也有不少是我崩的XD),这个方法比较难,因为我比较懒做死活手筋,
我的计算力应该是5k左右吧:)。另一个方法是比较简单的,是用好的布局理论对 AyaBot
的棋作惩罚(看了不少泰哥自战解说,所以我的布局大局观会比1k来得高,也因为这样跟
5k计算力平均起来可以跟1k的 AyaBot 下),几个定式下来,就会大优。这两个方法接下
来,就是中盘对于 AI 的强手不要过于退让,也不要突然崩了。还有对于无理手的及时惩
罚。
1. 中盘杀爆 AlphaGo
这对于职业棋手的算路来说是可行的,上面提到 AyaBot (1k) 是每手棋 1200 sims,然
而它有时候会乱跑征子。基本上,把一个棋子从一角的4路征到对面3线的引征需要二十多
手棋(2^20 ~一百万),而假设征子每手有2种变化,那10手棋就会是2^10=1024。基本上你
在一百万个点取样一千个点来算机率的话,会出现乱跑征子的状况只能说不意外。那么上
面估计 AlphaGo 是一百万sims的话(20手),那么要嬴过 AlphaGo 很可能要算出三四十手
的最强变化才有可能。问题是一定能激发出李世石的小宇宙吗?在巨大压力下,是很难的
,就像古李十番棋,这种硬生生造出来的世纪大战,棋的内容跟他们在世界大赛相碰所下
出的内容是不能比的,就像上面提到的那盘,还有诸如三劫循环名局,压力彻底将他们相
碰时的激情火花浇熄了。李世石在输了前三盘后,假如能真正放下要取胜压力,将被5:0
横扫的压力看淡放手一搏的话才有机会作出高强度的挑战。但从第一局开局的对攻失利后
,李世石似乎是惧怕了 AlphaGo 的计算力,后面多采取退让的下法,正中了 AlphaGo 的
下怀。因为从上面(三)的推论,李世石能发挥出九成实力就能稳嬴,但这是可遇不可求的
,就像龙珠里斯路还是被悟空悟饭打败一样。
2. 布局取利
同理 AlphaGo 的布局由于学习的原因,又或者是开局变化过多的原因,肯定是它的弱项
。包括第三局开局 AlphaGo 挂到高中国流的变化,在围棋TV 有人用 Zen 的判断知道李
世石从开局的 49%(因为贴7目半黑输的机率稍大)胜率升到51%胜率,可见在该局部
AlphaGo 是有亏损的。假如能累积这些亏损(比方说到了60%),AI 就会像突然吃了泻药
似的乱下。奈何李世石的布局在职业棋手中是公认弱的,他的强项是在于中盘强大的战力
,以及在后半盘的冲击力,但后者刚好被AI的强项完克。说真的,让古力甚至孟泰龄上,
结果说不定比李世石好。
3. 失误?优势意识?还是守住最大获胜机率?
很多人争论诸如第一局双飞燕靠断,第二局的接两残子是怎么回事。其中一种可能的情形
是 AlphaGo 跟 AyaBot 一样追求1目半胜或是半目胜,就好像你看棋灵王塔矢亮故意下四
局和棋一样。这种假设是职业棋手很难想像的(我相信台湾一些有协助发展AI的职棋是知
道的),但跟 AyaBot 下得多就会简单发现。而李世石出于“棋道”在判断出必败就投子
之下,变成没有这样的实验数据(或许让朴廷桓跟它下,他必跟你磨到收完单官就会发现)
。但从现象上观察,这很有可能,因为比如第一局的双飞燕,随便下个定式,局部比较好
,也不会增加风险,从获胜机率上是说不通的。假如我的假设是对的话,这就是电脑的优
势意识,棋手必需最大化因 AI 退让而得获得的利益,才有机会逆转,当然要逆转在越接
近终局越不可能发生。
(两点多吃完饭继续写)
六、假如 AlphaGo 5:0 代表什么?
1. AI 攻克了围棋吗?
肯定不是,从上面的推论 AlphaGo 的实力是职棋实力的平均+?,另外最强是外加不会大
失误,和官子很强。昨天在围棋TV上,一个在开发中国的围棋AI的人说现时的算法是有
瓶劲的,它大概只能保持现在跟人类的差距,从而加速围棋理论的进步,等到职棋进步了
之后,AI再 train 进步了的棋谱,再保持着这个差距。
这很好想像,因为当AI已经是最强的时候,表示职业谱的水准都比它弱。如果它吃进去的
话,它反而变弱,而如果它能拒绝的话,那它能学到的就极为有限了。所以大家都震惊从
去年十月的时候,AlphaGo 是李世石还能让两子的实力,到现在能嬴李世石,担心半年后
可以让李世石二子的可能性是不存在的,因为它从去年十月 train 业余谱,变成今天是
train 职业谱,你不可能找到能让职业二子的谱去 train了,不然职业都不职业了。
2. 人类的智慧输给电脑吗?
当然不是,应该是千千万万研究围棋AI的硕博士研究生加上工程师的努力,配合 Google
的资源,得出一个足以战胜李世石的围棋数学模型。你说研究生为了毕业或者工程师为了
保住工作所爆发出的意志来得强,还是一个棋手为了保住所谓人类尊严和一百万美金的意
志来得强?
3. 李世石下围棋输给AI吗?
大家都认为李世石跟 AlphaGo 在下围棋,其实现在是相当于出了一款叫 AlphaGo 的电脑
游戏,要求李世石在只有五条命的情况下破关三次(或者现在的情况是五命破一次关)。这
条件是很严苛的,特别是如果李世石当现在是下围棋,而不是找电脑游戏 bug 的话。举
个例子,有一款叫 Dark Soul 的游戏是出命恶搞玩家的,各种死法,有人戏称死亡模拟
器。在游戏初期有一回是进到一个庭院,突然冒出一只 Boss,它基本上挥中你两下就死
了,你要是以为要无限次以高超技术闪躲它的所有攻击而反击成功来击倒它的话,那么你
就错了,在庭院的某个地方有一线极不起眼的门,当你穿过去走完一段路后,你会去到庭
院的上层,然后再开场便可以一招打掉 Boss 的大半血,轻松过关。虽然这游戏那么坑,
但经过不同人的研究,在 Youtube 上就会出现这游戏的 speedrun。如果现在李世石认为
他在下围棋,相当于他在上面场景中选择硬拼 Boss,而不是找那扇门。所以我的观点是
,要是让李世石跟 AlphaGo 下三五十盘,或是足够的盘数,李世石是可以辗压回去的。
前提是 AlphaGo 保持着现在的算法、资源和这种学习模式。从这个意义来看,这才是人
的智慧,那个AI就不是智慧,除非那个AI可以改自己的算法让自己变得更强。
4. 职棋跟AI的差距很大?
这很难说,说不定像我上面说的找个布局好的棋手就能迫它自爆。不然要量化 AI 跟人的
差距的话,你可以加大AI对人的贴目,它就会突然感到自己输很多而很快走出无理手自爆
。这个情形跟在棋灵王中,进藤光在新初段系列赛中,让 SAI 跟塔矢名人下,为了不让
塔矢名人知道,SAI 自行增大自己的贴目数,结果尽走无理的变化被杀爆一样。
七、结语
这到这里(3:20 P.M),看围棋TV讲第四局似乎 AlphaGo 要自爆了。
作者: iamfenixsc (哈囉你好吗)   2016-03-13 15:32:00
太专业了 我只看得懂部分QQ
作者: Y78 (Y78)   2016-03-13 15:36:00
作者: EhDaGer (ㄟ大哥)   2016-03-13 15:41:00
完全看不懂 还是推个
作者: OCG (千山鸟飞绝)   2016-03-13 15:42:00
外行看热闹 热心分析给推
楼主: kafai (猪仔包 PigSonBow)   2016-03-13 15:46:00
第六比较没有专业知识,出于个人判断,应该普通人也明白吧
作者: henrypuff (小迷乐)   2016-03-13 15:54:00
推!看完这篇有比较理解了~
作者: fallcolor (秋天走了)   2016-03-13 16:01:00
对NN的理解太草率了
作者: Edaw (Wade)   2016-03-13 16:07:00
早三个小时出来就是先知了
作者: dirty5566 (得體五六)   2016-03-13 16:10:00
楼主: kafai (猪仔包 PigSonBow)   2016-03-13 16:13:00
f大,是草率了,我连个code 都没写过我不是要做先知,我第六就写5:0的,我本来就觉得李不会嬴
作者: MOONY135 (谈无欲)   2016-03-13 16:14:00
今天还没开始下就写完这篇文章就是先知
楼主: kafai (猪仔包 PigSonBow)   2016-03-13 16:15:00
所以今天根本没看,到写完才发现 ALPHAGO自爆XD 我好高兴啊
作者: MOONY135 (谈无欲)   2016-03-13 16:16:00
话说攻克围棋的定义是啥? 变成最强? 还是可以下赢职业选手? 还是赢得头衔?用理论上是职业选手的平均之上好像并不是很精准
作者: stfang925 (司马铃薯)   2016-03-13 16:19:00
你想成人类跟电脑下 就像你去跟李世石下的感觉一样好了
作者: MOONY135 (谈无欲)   2016-03-13 16:19:00
我认为选手棋力不会永远都在定值 每场的状态也是
楼主: kafai (猪仔包 PigSonBow)   2016-03-13 16:20:00
我对攻克的定义是它把整颗树都算完,你未下棋就可以认输
作者: MOONY135 (谈无欲)   2016-03-13 16:20:00
假设李的能力大约在 97~93间波动 而AlphaGo训练的棋谱
作者: Waterpig (waterpig)   2016-03-13 16:21:00
结论是否没有考虑自我学习?他有可能下出没人下过的棋路
作者: mike0227 (我又小看了那复杂的世界)   2016-03-13 16:21:00
NN的目的是让MCTS展开更有效率
作者: MOONY135 (谈无欲)   2016-03-13 16:21:00
自我学习的结果是在平均95以上的棋谱的话那基本上能不能算他是永远棋力不会下降只会上升的呢
楼主: kafai (猪仔包 PigSonBow)   2016-03-13 16:23:00
要嬴过人类是很简单的,就算算法照搬,加大运算资源就OK了在COM-GO DIGEST 上有人提到,自我学习在一开始作用比较明显,但之后就没什么作用
作者: MOONY135 (谈无欲)   2016-03-13 16:25:00
我觉得这目标太远大了 那不就是说你认为围棋可以有必胜下法吗?分布式 VS 单机版 大概七成胜率 代表多台算的效应其实没有提升多少...
楼主: kafai (猪仔包 PigSonBow)   2016-03-13 16:26:00
MIKE大,是啊,就条件机率的概念
作者: Murasaki0110 (麦当劳欢乐送)   2016-03-13 16:27:00
谈到布局就错方向了 alphago永远只看输赢前进
作者: weltschmerz (威尔特斯克˙闷死)   2016-03-13 16:27:00
应该会有限制条件啦 不会故意走无理手自爆
楼主: kafai (猪仔包 PigSonBow)   2016-03-13 16:28:00
积体电路虽然走到后Moore's law 时代,但目前还是有进步啊
作者: MOONY135 (谈无欲)   2016-03-13 16:30:00
我觉得把它丢进职业棋士的圈子里面看他的战绩就可以知道有没有攻克了 (我的攻克只是顶尖选手)
作者: Pojin (oPTTo阿尼)   2016-03-13 16:32:00
龙珠的斯路是三小?
作者: JDKnife (绝地小刀)   2016-03-13 16:36:00
谁说不能谈布局 你怎知道设计者没有喂它一些围棋观念在判断胜率上?
楼主: kafai (猪仔包 PigSonBow)   2016-03-13 16:37:00
那是广东话的叫法,我不是台湾人,就绿色那只
作者: carylorrk (carylorrk)   2016-03-13 16:37:00
如果自我对战时加上 mutation 呢?虽然人类没想到的妙
作者: yungo (peerness)   2016-03-13 16:37:00
龙珠斯路?? 本文是翻译文??
作者: carylorrk (carylorrk)   2016-03-13 16:38:00
手机率占整个 space 太小不太可能成功XD
作者: jerry0701 (南部瘦一哥)   2016-03-13 16:38:00
可以转八卦吗
作者: carylorrk (carylorrk)   2016-03-13 16:39:00
基觉得 CNN 学习前人考虑局部再结合成大局跟布局很类似
楼主: kafai (猪仔包 PigSonBow)   2016-03-13 16:40:00
要转可以
作者: bbbtri (cycling)   2016-03-13 16:44:00
就算算法还有bug 棋院还是可以用AlphaGo来检讨棋局和训练
楼主: kafai (猪仔包 PigSonBow)   2016-03-13 16:50:00
b大说得很对,还可以解决张飞还是岳飞强这类八卦版月经文布局是不是弱点,只是我猜想,没有实验就没法验证或推翻从对AYA 的观察,AG对李,还有变化最多的层面来看,我会猜布局可能是一个弱点覆盘的话现在在卖的软件就可以,你可以看每步它判断的胜率你看到胜率突然变很大的话就表示是好/恶手,只是它不能解释
作者: daviddwlee84 (海滩的太阳)   2016-03-13 17:07:00
作者: bbbtri (cycling)   2016-03-13 17:07:00
也许DeepMind正想透过这次全球转播 让世人自愿且很有效率的完善AI的算法 再扩大应用(或侵占?)到其他领域 而这个交换 最后对人类来说搞不好是损到了喔~
作者: frank61708 (Sensation)   2016-03-13 17:46:00
AI方面的理解有些错误,对棋士棋谱进行的监督式学习,只在model毅开始建立的时候使用,后面很大一部分是根据这个模型,自我对奕进行强化学习数千万局,也就是说他后来的模型主要还是仰赖强化学习才有这样的程度的
楼主: kafai (猪仔包 PigSonBow)   2016-03-13 17:49:00
f大,我同意你的看法,不过这样的强化也是有瓶颈的COM GO DIGEST 那边有在做的人是这样说的
作者: frank61708 (Sensation)   2016-03-13 17:51:00
我也很讶异他没有overfitting哈
楼主: kafai (猪仔包 PigSonBow)   2016-03-13 17:52:00
那要靠TUNE啊,做过研究生就知道啊XD
作者: frank61708 (Sensation)   2016-03-13 17:58:00
博士就应该更有感了
作者: sharpwolf (萧狼)   2016-03-13 18:15:00
龙珠的斯路 台湾是翻译赛鲁吧
作者: qaaz (hiromi)   2016-03-13 18:24:00
专业推,很多人以为AlphaGO攻克围棋就是天网的开始,但那也是他要能改进自己的算法才行,多面应用只是train的样本不同
作者: wade0130 (阿潪仔)   2016-03-14 00:17:00
讲的很好,大推
作者: Pojin (oPTTo阿尼)   2016-03-14 00:26:00
感谢楼上s大突破盲点XDDD 原po说绿绿的我还在想比克=w=

Links booklink

Contact Us: admin [ a t ] ucptt.com