為什麼AlphaGo不懂圍棋規則也可以擊敗棋王?

為什麼AlphaGo不懂圍棋規則也可以擊敗棋王?
圖片來源:《自然》期刊
我們想讓你知道的是

AlphaGo每下一步棋,都是累積了歷史棋王的功力,並先驗算可能勝率,再決定走法,可說步步為營,步步機關算盡,當然不是人腦可以比擬。

唸給你聽
powered by Cyberon

電腦圍棋程式AlphaGo如何擊敗韓國棋王李世乭,看了網路半天看不到簡單明瞭好理解的相關文章,只好自己寫。

電腦下棋要贏過人腦,不管是最簡單的井字遊戲,很困難的西洋棋,或是最複雜的圍棋,基本方法都是:每一步棋都要下在最可能獲勝的地方。

以大家都玩過的井字遊戲,也就是○○○XXX誰先連成一線誰先贏的遊戲來說,對方先下第一步以後,電腦可以算出接下來一來一往八個棋步,可能有多少種走法,如果畫成流程圖,會看到從第一步開始的一個井字圖,逐漸開枝散葉,越來越多井字圖,形成樹枝狀的演算圖。在這些走法裡,有些我方最後會獲勝,有些會落敗,於是接下來我方要走的,就是獲勝機會最大的那一步。

當然井字遊戲因為十分簡單,即使沒有電腦,用筆算也能畫出樹枝狀演算圖,只是這樣的工作更適合電腦來做。當所有可能走法被電腦窮盡,那麼對手不管下哪一步,都不會贏。後來這樣的演算法就被電腦西洋棋程式深藍(Deep Blue),於1997年用來打敗世界棋王卡斯巴羅夫。這樣的演算法被稱做暴力搜尋法。

然而這樣的演算法要擴展到圍棋並不可能,因為圍棋走法複雜太多,在19X19的棋盤上,當對方落下第一子,接下來有三百六十種可能走法,遠超過目前最強電腦的計算能力,即使算到天荒地老也還算不出來,這就是電腦打敗西洋棋王後,始終無法用同樣的演算法打敗圍棋高手的原因。

電腦必須另闢蹊徑。蒙地卡羅方法早在幾十年前就被發現,那是一種統計模擬方法,運用亂數來解決計算問題。重點來了。圓周率π要怎麼計算?只有天才數學家才能想出解法,但運用蒙地卡羅方法,不懂幾何原理的人也能算出圓周率,方法是在一正方形內劃出一個內切圓,然後拿一把豆子從半空灑落,再看看落在圓形內的豆子數目,跟落在圓形外正方形內的豆子數目,比例是多少,就可換算出π。換言之,這是一種利用機率向上天叩問數學答案的方法。

這跟AlphaGo有什麼關係?AlphaGo不懂圍棋規則,也能下贏棋王,運用的就是類似的機率原理。蒙地卡羅方法後來被運用在井字棋與西洋棋運算,但不了了之,直到2006年,有人又把蒙地卡羅方法找了出來,加了樹枝狀搜尋,成了蒙地卡羅樹枝搜尋法,從此開啟了電腦圍棋程式設計的新天地。當時有人就預言,十到二十年後,圍棋程式將擊敗人類頂尖棋手。

果然,2016年,這個預言實現了。箇中功臣很多,但最值得提起的兩位,就是將AlphaGo運作原理寫成論文,刊載在今年初的《自然》期刊的兩位論文主要作者,英國的大衛西瓦(David Silver)與台灣的黃士傑。大衛西瓦專攻深度神經網絡,尤其是增強式學習網絡,而黃士傑的博士論文寫的就是蒙地卡羅樹枝搜尋法在電腦圍棋程式的運用。

黃士傑是台灣土生土長,自己栽培的電腦程式專家,能有這樣的成就,令人感動!他大學念交大,碩博士念師大,念書之餘對圍棋非常有興趣,拿到了六段資格,後來更以電腦圍棋程式做為研究主軸,而且最重要的,他對自己非常有信心,相信台灣也能做出世界頂尖研究成果,終於大放異彩。他的生涯發展歷程值得台灣年輕學子參考。

黃士傑怎麼做?基本上AlphaGo用的就是蒙地卡羅樹枝搜尋法,而非井字棋或西洋棋所用的暴力搜尋法。

蒙地卡羅樹枝搜尋法有四個步驟:

一、從第一步棋開始,選擇最優勢的下一步棋,一步步擴展,這擴展過程便形成一棵小樹。

二、擴展方式是從樹枝的末端,也就是樹葉往外延伸,尋找下一個棋步。

三、擴展到不想再擴展時,便從最末端的棋步,進行棋局模擬,運用隨機下法,也就是三秒鐘內你來我往亂下一通,看看最後輸贏。

四、是把輸贏結果沿著樹枝往上傳,一直傳回到樹根,這時回傳過程中所經歷的擴展點,都會獲得一次走過的紀錄,而重複上述搜尋千萬次以後,累積起來得到的,最常被走過的那一個棋步,便是我方的下一個走法。

這樣了解嗎?跟暴力搜尋法有何不同?蒙地卡羅樹枝搜尋法,並沒有窮盡所有走法,而是尋找優勢步,算出接下來幾步以後,剩下的便靠機率把這盤棋下完,而如果這步是好步,那麼即使是亂下,贏的機率也比較大。圍棋太複雜,不可能把三百六十步全部算完,AlphaGo大約算了十幾二十步以後,剩下的便靠機率模擬來推算獲勝可能,並據以選擇棋步。

Photo Credit: AP/達志影像

AlphaGo的模擬算法有兩種,一種是估值函數,也就是利用迴歸分析,以歷史棋譜為比對根據,算出目前棋局的可能勝負,另一種是快速布局網絡,也就是利用棋局的局部特徵,以傳統演算法(非深度神經網絡)算出可能勝負,兩種算法的平均值便是勝負估算依據。

問題來了。前面說到,AlphaGo只算了十幾二十步,剩下的便交給機率,那麼這十幾二十步要怎麼算出來?深度神經網絡的角色便在這時出現了。AlphaGo不懂圍棋規則,但它知道,只要模仿歷史棋王的下法,便可能會贏。因此AlphaGo開始了學習歷程,從幾萬局歷史棋譜裡,學習歷史棋王在各種棋局時的下法,並記在腦海,等到比賽時便拿來比對目前盤面狀況,找出最能獲勝的棋步。

原理簡單,但實務上要怎麼學習?靠深度神經網絡。神經網絡是一種模擬人類腦神經系統的運算流程,有資料輸入端與輸出端,中間則是運算神經元,透過一次次學習,比對輸出資料與正確資料的差異,反饋調整神經元的運算參數,便能學會某種運算技能。

神經網絡在電腦學習的最初運用是手寫文字辨識,將字體寫在10X10方格上,每一小格當成輸入資料,有墨跡是1,沒墨跡是0,然後送往神經元進行運算,最後判斷這是什麼字,再公布答案看差多少,然後據以修正運算參數,以提升正確率。這就是所謂的監督式學習。另外一種是無監督學習,也就是沒有老師只靠自學,也沒有標準答案,而學習目標通常只是把輸入資料做一個分類,沒有對錯問題。

深度神經網絡的意思,就是運算神經元有許多層,每一層處理原始資料的一種特徵,多層加總起來,運算能力更加強大。然而當原始資料很複雜,比如像圍棋棋譜,如果每一個神經元都接受來自所有方格的資料,那麼電腦處理效能容易破表,於是卷積神經網絡出現了。

卷積網絡就是AlphaGo使用的兩種神經網絡之一,另一種是增強式學習網絡。卷積網絡的運算神經元,只接收來自棋盤上鄰近方格的資料,而非棋盤全部資料,大大簡化了處理程序。AlphaGo從棋盤擷取四十八種特徵,也就是布局方式,再利用十三層神經網絡,分層處理各項特徵,然後透過反覆學習調整參數,而學會辨認眼前的棋局。學成以後,只要看到每個棋局,AlphaGo便能辨認,如果是棋王來下,下一步會怎麼走?猜中的機率高達57%。

於是上面提到的,AlphaGo要選擇十幾二十步來做估算,便是透過卷積神經網絡,找出歷史棋王最可能走法的前十幾二十種,來加以演算。此外,為了增強對戰能力,還利用增強學習網絡,讓AlphaGo自己跟自己對戰,或者跟先前下過的棋局對戰,以累積更多實戰經驗。

增強學習網絡是一種半監督式學習,它沒有標準答案,但如果程式下贏了棋局,便會得到正向回饋,下輸了便會被扣分,跟人類學習一樣,由此慢慢累積學習成果,越學習越厲害。實施以後,AlphaGo可以輕易打敗以其他方法做演算的圍棋程式。此外,因為這類學習需要比較久的時間,AlphaGo也另外用傳統演算法實施快速布局網絡,推算棋王下法,雖然命中率只有兩成多,但耗時短上許多。

好了,差不多就是這樣了,至此AlphaGo已經闖過十八銅人陣,可以出少林寺下山挑戰高手了。只要對方下了一步棋,AlphaGo便能算出歷史棋王,比如本因坊秀策,接下來會怎麼走,吳清源會怎麼走,然後將最可能的十幾二十步棋,進行蒙地卡羅樹枝演算,找出勝算最大的一步,做為下一步走法。

須知蒙地卡羅演算法找下一步棋時,並非窮盡所有可能,而是用多臂老虎機演算法,也就是選擇吃角子老虎機器的方法。如果眼前有五台吃角子老虎,要選擇哪一台來玩,可以贏最多錢?一個方法是試了三台以後,選擇勝率最高那台,但其他兩台呢?說不定勝率更高,但也可能較低,於是就要在利用現行優勢與探索新可能之間做一個取捨。蒙地卡羅搜尋法便是依此原理選擇下一個可能走法,再進行接下來的模擬運算。

所以說AlphaGo每下一步棋,都是累積了歷史棋王的功力,並先驗算可能勝率,再決定走法,可說步步為營,步步機關算盡,當然不是人腦可以比擬。但也因為靠的是機率,還是有算錯可能,使得李世乭還能在五盤裡贏得唯一一盤。人腦還是可能下贏AlphaGo,但它的學習能力越來越強,越來越難被打敗。

AlphaGo的成功讓人開了眼界,原來學習也可以是這個樣子,不懂遊戲規則也可以下贏棋王。其實很多時候人們的學習也是如此,比如母語學習,都是不懂語言規則,靠著模仿而來的學習。

人生一局棋,要下每一步前,應像AlphaGo一樣,從成功前輩累積經驗,找出可能獲勝的幾步,然後加以推算,再選出勝算最大的一步,然後努力往前衝刺。

你的人生,下對棋步了嗎?

本文經作者授權刊登,原文發表於沈政男臉書

責任編輯:翁世航
核稿編輯:楊之瑜

或許你會想看
更多『評論』文章 更多『國際』文章 更多『沈政男』文章
Loader