[心得] 圍棋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