趋势

2019/03/15  顏士淨 | 東華大學資訊工程系 近50年來電腦圍棋的發展可分為原始時代、 手工時代以及機器學習時代3階段， 在每個階段的演進及技術開發又如何呢？ 在電腦圍棋四十多年的歷史中，研發人員前赴後繼，讓電腦圍棋棋力不斷向前推進，電腦圍棋的研究才正要進入一個新的世代。（圖片來源：種子發） 電腦圍棋自Zobrist在1970年設計出第1個可與人對奕的程式以來，至今已有近50年的歷史。這幾十年來電腦圍棋的發展，可分為原始時代（1970～1985）、手工時代（1986～2006）和機器學習時代（2007～）。以下就從這3個時代來了解電腦圍棋的演進，以及每個階段的開發方法。 原始時代 Shannon於1950年提出利用電腦來下西洋棋的概念，之後電腦對局就成為人工智慧領域中吸引人的課題之一。早先的圍棋程式棋力約在35～25級左右，因為運用在西洋棋、象棋的那一套窮舉搜尋演算法完全不適用於圍棋。窮舉搜尋就是找出當下局面所有可走的棋步，並且嘗試走走看，然後電腦再反過來替對手找出所有可走的棋步，也嘗試走走看。如此一來一往模擬數個回合之後，電腦程式再根據所走出的局面優劣程度，反推最初的最佳著手。 為何這套演算法不適用於圍棋程式？原因之一是圍棋棋盤比象棋大得多，可選擇著點平均就有二百多個，電腦的負荷量太大了。更關鍵的是，圍棋不像象棋那樣容易迅速地評估優劣。 象棋或西洋棋都是以「擒王」這個明確的目標作為獲勝條件，其他棋子不論偏重攻擊或防守或攻防兼備都有其大致上的價值，只要把盤面上雙方存在的棋子價值加總，然後雙方做個對比就可以得知一個局面的優劣程度。透過這樣的方法，電腦就能夠非常迅速地計算出局面的大致優劣程度。 然而圍棋每個棋子都是等價的，判斷優劣所依靠的是棋子排列的陣形。雖然決定圍棋勝負的是圍取地域的多寡，但在這當中包含了太多諸如死活、厚勢、味道、地域確定性等不確定的因素，因此一個圍棋盤面很難找到迅速有效的方法判斷局勢優劣。 若事先把左圖建立為一個棋形，並指出白A長是好點，碰到如右圖的類似局面時，電腦就能看出白A長是好棋。 手工時代 這個時代圍棋程式的棋力有明顯提升，主要因素之一是應氏杯（1984～2000）的成立。應氏杯主要由應昌棋圍棋教育基金會支持，是第一個全世界性的電腦圍棋比賽。這個比賽提供了一個舞台，在這個舞台上的程式約以每年進步1級的速度發展。 代表性的程式有臺灣大學資工系的Friday、Dragon、Stone、Archmagic，與筆者的Jimmy。其他程式包括大陸陳志行的「手談」，美國陳克訓的GoIntellect，英國Michael Reiss的Go4++，美國David Fotland的Many Faces of Go，以及德國Mark Boon的Goliath。這個時期的程式棋力約在23～2級左右。這時的程式大多利用一些技術輔助選點下棋，例如在布局階段輸入定石資料庫，以及利用人造棋型資料庫協助找出好點。 除了棋型資料庫外，最常使用的技術是攻殺搜尋。這是一種由追殺某個棋串以及防禦該棋串這兩種副程序互相循環呼叫，最後檢驗能否吃掉該棋串的技術。 儘管使用了這些技術，但要讓圍棋程式接近業餘高手的程度仍有很大的距離。例如，攻殺搜尋時發現某個棋串可以吃掉，可是要判斷這個棋串是否是要子？吃這個棋串的價值高低？棋型的分數如何給定？就需要更高層的分析技術與專業知識。鄭銘煌的程式「若葉」就用到大量專家知識，幾乎不需要搜尋就可以下出不錯的棋步。因此，在1998年左右，是日本最暢銷的圍棋軟體。 廣州中山大學退休教授陳志行研發的「手談」，可說是手工時代的代表程式。「手談」擅長分斷對方棋子展開攻勢，且對於死活頗有獨到之處，也建立了相當專業的知識庫。無論在定石、棋形、局部手段、攻殺細算，不少地方都可以看出出類拔萃之處，以致「手談」自出賽以來（1993～2005）奪冠無數，無論應氏杯、FOST杯、Olympiad杯都連連告捷，成為當時公認的最強圍棋程式。 機器學習時代  電腦圍棋的棋力之所以長期落後給人類，最大的原因是不容易找到良好的審局函數。直到2006年，Rémi Coulom使用蒙地卡羅法程式的Crazy Stone，才在杜林舉行的第11屆電腦奧林匹亞的九路圍棋項目中奪得金牌。2007年，蒙地卡羅法結合上界信賴樹狀搜尋法，合稱蒙地卡羅樹搜尋（MCTS）的程式開始出現。 以MCTS為基礎的圍棋程式MoGo也逐漸在一些較非正式的比賽中嶄露頭角。2007年，第12屆電腦奧林匹亞於阿姆斯特丹舉行，上屆冠軍GNUGO、亞軍GO Intellect以及Crazy Stone等程式都參賽。MoGo在強敵環伺之下，以全勝戰績奪得了十九路圍棋項目的金牌，Crazy Stone拿到了第2名，GNUGO退居第3。這象徵現在使用的標準MCTS（即UCT人工智慧）的成功，也代表一個嶄新的局面即將到來。 MCTS是一種使用強化學習的方法，可以在實戰時利用自我對下模擬結果評估盤面，某種程度解決了之前所提到的圍棋不容易找到良好審局函數的問題，且可以充分利用機器的能力，使用的機器核心數越多，棋力就越強。之後更開始利用各種機器學習技術，學習如何找出當前盤面較好著手的機率分布，乃至於近幾年開始發展的深度學習直接評估盤面與產生著手，這些發展都充分運用了機器的能力。 2006年後，以蒙地卡羅法程式為基礎，開始發展的深度學習充分運用了機器的能力。（圖片來源：種子發） 機器學習時代又約可分為機器暴力搜尋、離線機器學習、加強模擬準確率、深度學習4個階段。 機器暴力搜尋階段 機器學習時代一開始由MoGo稱霸，MoGo的作者是Gelly Sylvain、王一早等人。後期由Olivier Teytaud負責研發，並且把這系統平行化，改寫至可以在500～1,000核的分散式系統機器上執行。這個程式是第一個使用MCTS為基礎的電腦程式，最早的版本在模擬階段是用專家知識撰寫模擬落子順序，並使用3×3的人造棋型。其後加入了強化學習改進模擬方法，加速收斂MCTS搜尋的結果，對於增加棋力可說是立竿見影。 MoGo建立了現代圍棋程式的典範。MCTS程式與以往圍棋程式的行為有很大差異，布局很差，可說是沒有布局，但擅長近距離接觸戰，也擅長收官，這可以說是所有以MCTS為基礎的圍棋程式共同的特性。局面優時，則下得極端保守，常常最後只贏半目，局面不佳時，則想盡辦法翻盤，甚至下出像在耍賴的棋。MCTS另外一個特性是棋力跟使用的計算資源成正比，給予越多的計算資源，棋力就越強。 MoGo在2008年開始與東華大學和臺南大學合作，開發MoGoTW版本，並在2013年九路圍棋比賽中擊敗職棋。 離線機器學習階段 Crazy Stone的作者Rémi Coulom提出特徵自動學習法，以監督學習的方式從棋譜自動學習棋型的權重。學到的棋型不僅可以用在加強模擬的準確性，也可以用在MCTS搜尋樹展開選點的優先順序。執行模擬棋局時，就分析每一個可能著手的特徵，得出其重要性的分數，並算出選擇這著手的機率，再依機率落子。 此外，MCTS搜尋樹展開選點時，可以採用漸進式展開的技術，減少搜尋樹的分支度。Crazy Stone先依著手機率排序，隨著模擬次數逐漸增多，再逐步開放子點以供選擇。這階段另外的程式還有Many Faces Read more…

 2,434 total views,  2 views today