2016-03-12

【熱血時報】林爽文:Google大戰李世石 - 淺評與解釋 (1875)



1.賽前,大部分只懂圍棋的人,對李世石信心十足。大部分只懂電腦的人,對賽果是五十五十。頭兩場的結局出來了,無疑是令到圍棋界大跌眼鏡。

2.為什麼圍棋界之前這麼樂觀?原因有三:
(a)雖然說二十年前,深藍已經打敗了Kasporov,但圍棋的複雜程度,遠超國際象棋。
(b)直至Alpha Go出現之前,圍棋程式與人類相差甚遠,就算是業餘高段者,也是可以輕輕鬆鬆打敗圍棋程式。
(c)圍棋不單是整體盤面較國際象棋大,而是整個比賽進程的局部分割判斷難度,是與國際象棋非常不同,所以才有『Chess is a battle,Go is war』的說法。意思就是-環環緊扣的交鋒,可以令到每一個局部的結果改變。這一點,令到以往的AI難以勝過可以有抽象判斷力的人類。

3.過往,學術界是認為AI技術,還要差十年,才可以戰勝一般圍棋強手(注意,這裡說是強手,而不是李世石這種級數的頂級高手。)

4.那麼,這次Google有什麼基本上的技術分別呢?首先就要講圍棋程式的設計進程。
(a)一般人會以為,電腦是會利用自己的超級強大的運算能力,將每一個可能性計算出來。這就是所謂的『exhaustive search』方法。這是不對的,因為圍棋在symmetry breaking之後,他的總可能性是大約200^200步,就算用全世界的電腦放在一起,計算到宇宙的盡頭,也不會計算得到。
(b)所以,圍棋程式(或者是這一類型的智能程式)必定要限制自己運算的方法。而對上一次令到圍棋程式的棋力突飛猛進,是二十年前開始,科學家開始用所謂的Monte Carlo Tree Search(MCTS) 方法,去限制搜索範圍。
(c) Monte Carlo Tree Search的精髓,就是利用幾千萬份圍棋棋譜之中,與其盲撞,倒不如從以往對局的進程中,找出不同應手的概率,然後按各概率去搜索下一手。簡單點說,就是把搜索的範圍,收窄到約略經驗之中。這樣就可以大幅度減低搜索的時間。
(d)這種方法,就將圍棋程式從不入流,進步到業餘水平。但高手是可以憑複雜的棋形和大局判斷,輕易擊敗這種方法寫出來的圍棋程式。
(e)Google Deepmind這次用的方法,是Convolution Neural Network,這是一個比Monte Carlo Tree Search 更加厲害的算法,我會在下一點詳細講講。

5.如果你在美國寄信,你手寫地址。信件其實係會運送到一個中央的集散地,利用機器去讀你寫的字。機械人怎樣認得手寫的字?就是用『機器學習』(Machine Learning)的方法。機器學習,可以說是人工智能的一個範疇。
(a)而經過很多科學家的試驗,最有效率去認圖像的方法,就是用一種叫『neural network』的方法。這是從人類腦神經科學之中受到啟發的。
(b)簡單一點講,就是用一個很多層的網絡,將訊息通過這個網絡去運算。而學習的方法,就是將得出來的誤差計算出來,然後微調每一個網絡之間的關節位。
(c)事實上,這一種方法就是我們人類學習事物的方法。我們的腦部的腦神經網絡,是要透過不斷學習,才可以成型的。而且是要在生長快的時間裡學習,最事半功倍。所以,小孩往往是在三歲到五歲左右,學習語言學習得最快的。
(d)Neural Network有很多種,但這裡不深究。
(e)總之-neural network的好處是確實可以運算得非常精密。但凡事有得必有失-neural network算法的其中一個大問題,是他對於電腦計算力的要求比一般算法高。
(f)比如說,如果是學習讀郵件上的字跡的話,基本上只要三四層network,就非常夠用。但這次Alpha Go的算法,是用了十三層。
(g)這無疑是得益於近年電腦運算能力的突飛猛進,這裡有幾點:(i)distributed的算法技術越來越成熟-現在的算法設計,往往是拆開成為很多個小部份,讓很多部電腦一起計算。(ii)GPU越來越平-受到打機影響,現在的GPU越來越平之餘,其實這些都是很有利於平衡算法。這些都令到科學計算的速度快很多。

6.Google 最後用以打敗范麾(歐洲圍棋冠軍)的電腦運算力是多少?是1920個CPU加280個GPU,分64個thread去計算。招呼李世石用多少運算力?google未公佈,但應該只會多,而不會少。

7.這裡不單單是計算機和neural network的威力大。而是Google執行這些的技術,也有層次:
(a)首先,從歷史對局中,預計高手過招每一步的演化。
(b)然後,用neural network的想法,去詳細學習每一步頂尖高手的好壞。好了,到這裡,只是開始,戲肉在後面。
(c)利用(a)和(b)的結果,作為第三個網絡的起始(initialized state)階段。然後用這個階段作一個非常深入的訓練模式:自己同自己比賽,再用比賽結果做所謂的標籤訓練(supervised learning)。這裡就可以將前兩層似是而非的結果,確切的深化出來。為什麼要這樣做?因為其實以往圍棋的棋譜雖然多,但同樣圍棋的可能性大大,所以單單用以往高手過招的實例去train個network,略嫌不夠,會有一定誤差。
(d)最後用一個linear regression去綜合判斷每一步可能的價值,再參考這個價值,去決定下之後一步。

8.為什麼我之前會覺得李世石會贏?這是因為我覺得7(c)的部分,其實是言過其實,因為始終這裡對運算的需求,應該非常大。而7(c)如果不成立,那麼其實7(a)和7(b),頂尖棋手如李世石,必定可以輕鬆打敗AlphaGo,因為AlphaGo只是學高手的下法,但李世石是頂尖高手,這裡的差距可以很大。

9.所以說,綜觀第一點後,其實AlphaGo每一步的計算複雜程度,比當年DeepBlue打敗Kasporov還要簡單上千倍。但計算能力,卻比當年DeepBlue的能力高上萬倍(這個待查-但應該差不多是這個數)。

10.我心裡很矛盾,始終圍棋是人類最後一個可以抗衡AI的策略遊戲,但這個已經被攻陷了。其實就算李世石追回三盤,亦改變不了AI可以與頂尖高手分庭抗禮的事實,只要可以分庭抗禮,只要最多一年,就可以完全超過第一流的圍棋高手。

11.Alpha Go兩局之中,有幾個觀察:
(a)每一次Alpha Go妥協之後,其實都沒有『蝕底』。
(b)開局或會有少許落後,但後半盤凌厲。反而官子好像沒有想像中這麼厲害。
(c)很多時候避開了開劫。
(d)非常厲害的大局觀。
(e)兩局,都是因為李世石犯錯比AlphaGo犯錯的次數多,才輸。

12.關於(11)幾點,幾個想法如下:
(a)妥協不蝕底,這是很有機械人的特質,這個是意料之內,但計算得這麼精準,在林場對陣的時候,尤其是遇上李世石這種大砍大殺的高手,其實是對李世石打擊很大的。
(b)開局的優勢不明顯-這是應該取決於很多新的局部形勢,在盤上的可能性很大的時候,局部的判斷因為運算需求大,還未做到超一流的水平。反而官子能力沒有想像中厲害,這是有點怪,有待觀察。
(c)這個就不知道為什麼,中國第一人柯潔說-AlphaGo可能與李世石簽了不打劫協議,但Google馬上走出來澄清了,這些子虛烏有的說法。
(d)這個應該是7(c)做得非常好的功效。
(e)AlphaGo當然還未到完美,但高手如李世石,亦難免有算錯的時候。

13.新手-AlphaGo在比賽進程中,下了幾個人類認為是沒有效力的新手,但最終出了並不如他們想得這麼差。這令我想起吳清源嶄露風頭的時候,下了很多當時亦被嗤之以鼻的新手,但後來卻證實了吳清源是對的。這裡這非常恐怖,完全脫離人類現時圍棋知識的判斷,是7(c)的功效。

14.期待更多的新手,令到圍棋棋手可以進步更快。

15.最後,我也同意無論是李世石勝還是AI勝,最終都是人類的勝利。但對於這一天來臨,儘管我是一個既會用machine learning又同少少圍棋的人-我的心是毫無疑問的傾向圍棋的。紋枰上的高低起伏,千百年來的黑白對弈,判斷、算法、大局;一幅幅爭勝的畫面,我一直都覺得-這是屬於人類,屬於生命的。
這種想法可能有點過於不理性,但每一棵花也有自己的生長的高度,仲會向上力爭上游-我不是懼怕AI,只是對生命更有感情而已。

16.
最後最後-大家不妨幻想,AI可以取代什麼工種。 :o)


Match 1


Match 2



原文連結



0 comments:

Post a Comment