AlphaGo人工智慧技術
電腦如何擊敗世界棋王？
撰文／嚴士淨（東華大學資訊工程學系教授）
轉載自《科學月刊》2016年5月第557期
由Google DeepMind 所開發的人工智慧圍棋程式── AlphaGo，在今（2016）年3 月以四勝一敗的戰績勝過南韓棋王李世石。此一消息震撼了資訊界與圍棋界，造就人工智慧的里程碑。AlphaGo 主要是以深度學習網路（deep learning networks）與蒙地卡羅樹搜尋（Monte Carlo Tree Search，MCTS）的技術來開發，並以自我學習的方式提高棋力。Google DeepMind 在三年前開始網羅電腦圍棋的專家，加上充沛的計算資源與大量的資訊人才，終於完成此一壯舉，不但影響了圍棋的發展，也讓人開始思考人工智慧對人類未來的影響。
電腦對局（computer game）是人工智慧領域中最吸引人的課題之一，也是衡量人工智慧的一個好方式，如1997 年美國科技公司IBM 在超級電腦上開發出來的「深藍（Deepblue）」，戰勝了西洋棋冠軍卡斯帕洛夫（Garry Kasparov）。對於目前世界上較廣為流傳的棋盤遊戲，我們可分析其複雜度（下表）。其中複雜度以該棋類起始盤面之後的所有可能變化為衡量標準。整體來說，西洋跳棋（checkers）、黑白棋（Othello）在電腦上的發展，已到達超越人類的程度；西洋棋、象棋、日本將棋程式，電腦也已到達職業棋士的水準；而Google DeepMind在此次挑戰圍棋九段成功，登上了21 世紀人工智慧電腦對局的聖母峰，將永留人工智慧電腦對局的青史。
●新型演算法提高搜尋效率
由下表中可以看出圍棋的複雜度相對很高，這是因為圍棋的盤面都比較大，如果使用暴力法搜尋，在每層的分支數過多的情況下，將無法搜尋很深。因此，一些全域搜尋的方式通常不適合用於圍棋這種複雜度太高的遊戲。因此，2006 年蒙地卡羅樹搜尋演算法的提出，使得電腦圍棋的研究有驚人的突破。
這種全域搜尋的演算法，以蒙地卡羅模擬演算法作為局面評估的依據，判斷形勢的良窳。又利用上界信賴演算法（Upper Confidence Bound，UCB）使得搜尋樹可以往較優秀的子點展開成為一棵不平衡樹，從而達到裁剪的目的以增加搜尋深度，適用於解決高複雜度的問題。此方法主要是為了解決著名的「多臂海盜」問題（K-armed bandit problem，俗稱吃角子老虎問題或博奕機問題）而發展的。一開始玩家會先將所有博奕機玩一遍，之後依照目前累積的經驗來決定下一次要選擇哪一台機器下注，這稱之為開發（exploitation）。相對地，如果玩家不斷地依照目前所獲得的經驗來決定，而不試圖嘗試其它的機器，則可能會忽略收益率更高的機器，因此適度地嘗試其他機器是必須的，這稱之為探索（exploration）。
概念上而言，蒙地卡羅樹搜尋演算法把每一個節點都當作是一個博奕機問題，而此節點的每一個分支，都是一台博奕機的機器。選擇分支，就會獲得相對應的收益。搜尋開始時，MCTS 方法會建立一棵樹，然後重複以下四個步驟，直到指定的時間或次數用盡為止：
- 步驟一、選擇（Selection）
選擇一條從根節點到葉節點的最佳路徑。選擇的方式則是從根節點開始，利用上界信賴公式計算每個子點的上界信賴值，選擇此值最高的子點，然後重複此方式，不斷往下搜尋，直到遇到葉節點為止。
- 步驟二、拓展（Expansion）
若步驟一最後找到的葉節點已經拜訪過，則我們會產生此葉節點的子節點，以找到從未拜訪過的葉節點。
- 步驟三、模擬（Simulation）
找到從未拜訪過的葉節點後，我們會使用蒙地卡羅模擬以得到此葉節點的收益值。
- 步驟四、倒傳遞（Backpropagation）
根據步驟三得到的收益值，更新這條從根節點到葉節點的最佳路徑上所有節點的收益值。經過上述步驟所得到的搜尋樹，其根節點之下，收益值最佳之子點，即為解。
MCTS 使用在圍棋上的主要概念，就是每個節點代表一個盤面，此節點的分支代表此盤面下的合法著手，每個分支連結到的子節點，就是原盤面加上分支代表的著手後，所產生的新盤面。一般而言，目前盤面為根節點，根節點的分支代表目前盤面下的合法著手，根節點的子節點代表根節點的盤面加上分支代表的著手後所形成的新盤面。
MCTS中的「選擇」，指的是從根節點開始，根據上界信賴公式向下搜尋，直到找到葉節點為止的過程。所謂葉節點，就是未曾拜訪過的節點。當搜尋時，若拜訪到的節點雖非葉節點，但仍無子點，則會產生子點，子點的多寡，直接影響到搜尋的深度與棋力的高低，因此對於產生出來的子點，必須加以裁減，搜尋的效率才會提高。裁減的策略就是所謂的搜尋策略，這方面AlphaGo是用深度學習類神經網路來找出搜尋策略。
第三個步驟是模擬棋局，就是由上一個步驟所找到的葉節點開始，由電腦接手下完，並回傳勝負結果，以更新蒙地卡羅上界信賴搜尋樹。模擬棋局的核心就是其決定著手的方法，一般來說，會用棋型與棋理選擇著手，然後用自我對弈方式完成一局棋。AlphaGo將這裡的模擬棋局策略叫做隨機策略（Rollout Policy），AlphaGo使用特殊的棋型，可以將隨機策略的正確率提高到24.2%。
有了模擬棋局的結果，我們就可依此更新蒙地卡羅上界信賴搜尋樹。從根節點到第二步驟中找到的葉節點所形成的路徑上的所有點，我們稱之為最佳路徑。更新意指依照模擬棋局的結果來更新最佳路徑上所有節點的勝場數與拜訪次數。所謂更新勝利次數，指的是若此點代表黑棋著手，且模擬棋局之結果為黑勝，則此節點的勝利次數加一，反之亦然。而拜訪次數的更新，則是此路徑上的所有節點的拜訪次數均加一。若總模擬次數達到我們所設定的門檻，或限制時間已用完，則結束搜尋，並且挑出根節點下拜訪次數最多的子點，作為此次搜尋的最佳著手。
●改善搜尋策略後棋力大增
19路圍棋棋盤相當廣大，即便以平均分支度而言，也高達180左右，如果單純使用MCTS，則搜尋深度將會相當淺，需要相對多的模擬次數才可提升棋力。為了改善此一問題，漸進擴展（Progressive Widening）演算法隨之而生。此演算法的核心概念在於，一開始不要開放所有的子點作為選擇步驟的候選點，而是根據某些經驗法則，或是棋型分數，將所有著手給予排名，只有前若干名的著手才開放候選。隨著模擬次數增加，開放的著手漸次增多，因此稱之為漸進擴展演算法。這個方法類似於人類棋手思維的方式，一開始先集中精力考慮最有可能的幾個著手，若時間許可，再將目光轉向那些比較不可能的著手；且此方法亦可有效降低搜尋樹的分支度，從而獲得更高的棋力。
然而，問題在於如何對著手取得正確的排名，這也正是所謂的搜尋策略（Tree Policy）。在學習圍棋對局之有效複雜棋型時，曾使用專家知識或單一隱藏層類神經網路，但辨識率並不高，且當訓練資料很大時其模型也無法輕易訓練。之後有法國學者提出特徵強化演算法（Minorization-Maximization），用統計配合模擬方法找出有效特徵，但辨識成功率仍低於42%。
Google DeepMind、Google Brain 與多倫多大學成功將深度學習類神經網路（Deep Learning Neural Network，DLNN）使用在圍棋程式著手評估上面，共使用12 層的DLNN，包括55 萬個隱藏層結點，6 億個連結與230 萬個參數，算出的著手中有55% 與職業棋士棋譜相同，每個著手計算時間約0.15 秒，可說是為AlphaGo 打下了基礎。深度學習類神經網路原本用在圖形辨識問題，並予以分類。2011 年起，因為可以充分利用GPU 繪圖顯示晶片的大量平行化的運算特性，大幅提高效能至實用階段。
AlphaGo將深度學習網路用於兩個元件，一為圍棋策略網路：辨識目前盤面以取得下棋策略，且使用3 千萬個圍棋盤面當作訓練資料，準確率可達57%。另一個元件則是圍棋評估網路：評估MCTS的葉節點盤面，輸出黑白雙方的勝率。AlphaGo 以這兩個元件，並配合MCTS架構，一舉將電腦圍棋程式的棋力提升到職業水準。
●電腦可能取代人腦嗎？
在AlphaGo 擊敗南韓棋王後，圍棋界乃至於電腦圍棋界，必須要面對人工智慧擊敗人類棋王的事實。而這面對人工智慧的過程，也可做為其他即將被人工智慧淹沒的領域之借鏡。這次的影響，目前在圍棋界的看法相當分歧，但毫無疑問的是，人工智慧將衝擊圍棋的文化與價值，特別是職業棋士存在的意義。例如一個以職業棋士為目標的小孩，若有人告訴他永遠不可能贏過電腦，那鍛鍊與增強棋力的決心是否就會動搖？樂觀的人則是認為，雖然圍棋是體育，比勝負的競技遊戲的部分可能因此打折扣。但是圍棋是文化藝術與一種道的觀點將更為穩固，我們可以透過人工智慧，更理解圍棋的優點，享受圍棋帶來的快樂。至少在目前，AlphaGo 所帶動的新聞效應，已經讓圍棋再度熱了起來。而且以圍棋龐大的複雜度來說，現在不管是人類或電腦目前在圍棋的表現，距離完美都還差得遠呢！在追求圍棋的神之一手的角度來看，圍棋與電腦圍棋的研究將是無止境的。
另一方面，這次AlphaGo 取得的大勝利，不免讓人擔憂電腦是否會取代人腦的問題，事實上，AlphaGo 的架構，只能解特定問題，並不是泛用性的智慧，因此並無跟一般人腦競爭的問題。倒是這種架構可以應用在許多領域，例如Google 即宣稱將使用在醫療問題上，此想法是相當合理的。我們可以把對病人的醫療當作下棋，而對手是疾病，所有醫療病歷則是棋譜，如此就可以將AlphaGo 的架構與技術使用在解決醫療問題。總而言之，AlphaGo的影響將是非常深遠的，不只是在擊敗人類棋王的勝利上，它的廣泛應用之後，對人類社會帶來的影響，不單是許多技術與服務的提升，原本許多行業的能力將受到人工智慧的挑戰，在可見的將來，許多的工作將逐步被電腦取代，這些才是我們真正必須面對的問題。
(本文由教育部補助「AI報報─AI科普推廣計畫」取得網路轉載授權)