科學與藝術？AlphaGo的棋力與棋風

壹、緒論

    Google開發的圍棋人工智慧，阿爾發圍棋(AlphaGo)與南韓圍棋棋王李世石乙(Lee Sedol)於2016年3月9日、10日、12日、13日語15日將進行五場對弈。比賽獎金獲勝方可以得到100萬美元，五連勝的獎金則為125萬美元。

李世石與AlphaGo之比賽成績

    如同阿姆斯壯登陸月球那一夜，我們的心都碎了。還我嫦娥！不過，也解了千年來的擔憂，『嫦娥應悔偷靈藥，碧海青天夜夜心。』。阿姆斯壯證明嫦娥並沒有在月宮寂寞地生活。而對於AI的期待與擔憂，也讓人揪心。媒體一方面訴說人工智慧的強大力量，同時擔心AI主宰未來的人類。而AI打敗歐洲圍棋冠軍，又打敗韓國為棋冠軍，似乎是人類的失敗，但是畢竟AI也是人類所發展出來的，就是這樣的矛盾情結，讓大家對於這場比賽，注目關心。

    不過，當電腦AI的實力越來越強大的時候，對於人類與AI的競賽規則，似乎也應訂定特定的規則。換句話說，類似圍棋棋力讓子的辦法，讓比賽更有看頭。當然，目前研發階段，或許研發團隊專注的是提升AlphaGo的棋力，求勝的決策。

    AlphaGo並不是第一位勝過人類大腦的AI，在AI家族中，以往也有許多勝利的實例，而人類似乎也要漸漸地學習接受AI在競賽中的勝利。例如，AI的兄弟深藍(Deep Blue)在1997年5月也打敗過西洋棋世界冠軍斯巴羅夫(Garry Kasparov)。可是，深藍在比賽後退休。在更早的1952年，電腦在井字遊戲(Tic-Tac-Toe)打敗人類，1994年，在西洋跳棋打敗人類。而圍棋的複雜性，相對地高，所以儼然成為電腦最後的挑戰。

貳、窮舉法與人工智慧

一、圈圈叉叉

1.列出所有的可能性

    在3X3的井字方格中，共有9！個可能的棋步，相當於362,880種。當然，此處若將四方形的各種棋步視為重複或一致，可能的棋步種類會大為減少，但是這並不是本文的重點，故暫時不討論此部分。

圈圈叉叉棋譜

2.歸納所有棋譜的勝負，為勝、負、和。

3.先下者有無”必勝”棋譜。若有，則先下者以該棋譜開局，將必勝。若無，再檢討後下者有無”必勝”棋譜。

4.如果先下者有”必勝”的棋譜，則”圈圈叉叉”遊戲將轉化為如何決定先後開局的比賽。

    圈圈叉叉AI程式設計的原則，即是歸納上述9!種棋譜中，最終為”必勝”的棋譜。即”以取勝為目標；以連線或是阻止對方連線為目標。”假設精明的玩家，不會犯下錯誤，則常玩圈圈叉叉遊戲的人大概都只能以”雙三”的棋步來強制取勝。

小結

    在圈圈叉叉遊戲的模擬中，不管先下或是後下，精明的專家對弈，最後都會達到”和局”。大家可以”左手和右手”對弈；或是”可以悔棋”的規則下，來模擬一下。

二、五子棋(連珠)

    規則

1.黑棋先。

2.在棋盤上形成直、橫或是斜角連續五個棋子連線者為勝。

    此部分亦可以上述歸納法得到結果可能為勝、負或是和局，並且得到先下或是後下的勝算。但是，實證上證明，黑子先下具有絕對的優勢，所以日本規則對於黑子就設下諸多限制，以求比賽的公平(註1)。

    五子棋先下者的優勢巨大，而日本規則則設下限制。甚至，在實際比賽中，發現以19X19的棋盤來下，在高手過招間，對於黑子還是有利，故再限縮黑方的優勢，設計15X15的五子棋專用棋盤。

三、圍棋

(一)所有可能的棋譜

    圍棋的棋盤以19X19為例，共361子。可以下的棋步即有361!，假設目前的電腦無法運算出所有的棋譜，因此，AlphaGo上有很大的部分必須從比賽中”自我學習”，而這些自我學習或是比賽經驗，可以增大所有棋譜的資料庫。

    和上述井字遊戲與五子棋不同的是，既然在現有的計算能力下，不模擬所有的棋譜，而必須運用AI，則這即是AlphaGo積極的貢獻。

(二)棋譜的勝負

    在已經模擬的棋譜中，可以歸納出”科學”勝負的局數。但是，無法模擬的局數，則考驗AI的演算能力。這或許是目前人類尚存的一點點可以打敗AlphaGo的希望。

(三)戰術

    分析AlphaGo研發團隊的思考與AI程式設計的邏輯，找出”尚未模擬的棋譜”。從中尋求戰勝機率較大的”棋風”。特別是在執黑先的開局時，掌握機會。

(四)討論

    原來的假設是電腦運算能力足以演算所有棋譜的邏輯下，以及分析各項棋譜的勝負並選擇追求勝利的戰術。但是，假設電腦運算能力尚未能概算所有的棋譜，或是AI希望開發自我學習的能力而非決策模式的解決能力。這樣，又有點從科學回到藝術，人類是否可以找到”勝利的希望”。

(1).png

參、圍棋AI

一、假說

問題：能不能找到”開局”決定”勝負”的棋譜？假設可以，則必須另訂競賽規則。

一、所有的可能棋步

    從決策樹的角度來看，首先列出所有的可能性，先不管勝負或是對手的對策。例如以圍棋盤的起手來看，共有361個可能(19X19)。第二步，對手的對策，則有360個可能，依此類推，359、358、357等，共有361!個可能。

二、這些棋步的勝負

    在361!個棋譜中，可以得到三種結果。勝、負與和。

三、戰略

    假設可以在”執黑先”的棋譜中，找到必”勝”的棋譜。則當執黑先的情況下，可以主動採行最後為”勝”的棋步。反之，後下者，可能繼續從”勝”局的棋譜中，找出”勝”的棋譜。但是，假設執黑先的棋譜中，有找到必”勝”的棋譜；那麼，白子大約無法找到”勝”的棋譜。

四、討論

    假設以上的討論無誤，則複雜的圍棋勝負，將簡化為”剪刀、石頭、布”等決定開局先後的比賽。

    要驗證上述假設，先回來棋盤。圍棋的棋盤為19X19的方陣，或9X9的方陣。要模擬圍棋的走法，先假設棋手不考慮勝負，或是棋盤四方對稱的特性，即對戰雙方隨意落子的棋不，則可能有361!個走法。361!以iPhone的科學計算機來計算，計算結果是”錯誤”或是無限大。iPhone內建的科學計算機計算n!數式公式中，n最大的數字為103，也就是只能計算103!，計算的結果約為9.9X10的163次方；當輸入104!時，則出現”錯誤”訊息。以電腦線上工程計算機來看，計算170!時，答案為7X10的306次方。而171!則出現無限大的答案。在九成九(9路)的棋盤，則有81！種可能，即相當於5.8X10的120次方的可能。

    這個數量，超乎人類的數學想像，或許當前電腦的運算能力也尚未達到。以AlphaGo也需要時間運算來看。就這個部分請教具有圍棋專長的老師，他說明AI設計並不是窮舉法的概念(註2)。不過，我還是先從窮舉法來思考一下。首先，從比較簡單的圈圈叉叉遊戲(又稱井字遊戲，Tic-tac-toe)和五子棋(日本遊戲名稱，連珠)來發展運算原則。再歸納勝負的棋步，最後再從起子先後來看，試試看能否得到必勝的棋譜。當然，這樣的說明也算是為AI提供一個不同的思考。

二、人工智慧

    和一般以擒王爭勝的比賽不同，圍棋是以在19X19的棋盤上，爭取以控制較多的領域來決定勝負。而其棋步數量約為10的170次方，導致無法以算數來搜尋所有可能的棋步(Gibney, 2016)。因此，許多設計圍棋AI團隊以AI來做為圍棋下子的決策，其中，AlphaGo的團隊在AI圍棋競賽中，戰績最佳。

    AlphaGo以神經網絡建立深度學習的”大腦”，可以經由樣本和經驗學習。AlphaGo首先從職業棋手的棋譜學習了30,000,000局，學習歸納資訊。接著，在50部電腦中，自我對戰以提升反應，加強學習。AlphaGo在與其他圍棋商業化軟體的競賽中，來得到較佳的策略，這個做法，打破過去30年來利用電腦的計算能力來決策的方法，DeepMind使用模仿人類知識，經由訓練得到能力的作法，而不是電腦程式的計算(Silver, 2016)。

肆、討論與限制

    到底人類所發明的AI打敗人類是不是仍然算是人類的勝利是一個議題。倒是在AlphaGo與李世石的比賽期間，各方人士(特別是圍棋高手)的論點，頗值得回味。

一、討論

(一)AlphaGo的棋風

    相對於人類，甚至個人，因應個人的成長，學習經驗等，有些棋士的棋步有其特殊風格。因此，棋風亦為圍棋令人探討與迷人之處。而AlphaGo獨特的棋路跳脫人類圍棋高手的思維。許多看似”漫無章法”的棋步，卻成為勝利的基礎。

    歐洲圍棋冠軍樊麾(Fan Hui)在與AlphaGo對戰落敗後，成為AlphaGo的顧問。他提到與AlphaGo對戰後，棋力上升，也說明了AlphaGo作為人類圍棋老師的潛力。

    另外，如果從電腦路徑圖的”勝利”棋譜反推電腦的棋譜，AlphaGo的棋譜是比較”科學的冷靜”。但是，相對於人類，似乎喪失了”人類的情緒”。而AlphaGo有些經驗學習自人類的經驗，包括犯錯。一時的犯錯，假設沒有影響大局，或是經驗棋局中，沒有出現失敗，這也使得AlphaGo的棋步，爾偶出現”人性化”的失誤。

    韓國棋院梁宰豪認為AlphaGo給人的感覺，不像高手在下棋，好像是山中自學成材之後下山的下棋高手。這也有可能在AlphaGo自學的棋步中，與人類不同的部分。也許，以後評論圍棋時，要加上AlphaGo棋風。

(二)AlphaGo的棋力

     根據決策樹的假設，開局之後的階段，可以下的棋步相對多，變數大到連AlphaGo的運算都感到吃力，需要時間。而到後面，可下的棋步相對變少，以AlphaGo的運算能力變成有餘力，而可以發揮AI的優勢。那麼，運算能力也變成未來棋力再加強的潛力。

    倒過來說，在第二局，當李世石用掉時間之後，AlphaGo也剩下約20分鐘，則若是規定AlphaGo能夠思考的時間再減少30分鐘，有可能會改變結果。

    AlphaGo的棋力，正在提升當中。以往，在與Crazy Stone和Zen等其他圍棋AI的500局比賽中，AlphaGo勝499局。

(三)電腦的計算能力

    單機版的AlphaGo擁有48個中央處理器和8個圖形處理器；而分散版的AlphaGo則擁有1,202個中央處理器和176個圖形處理器。

    因此，表示李世石面對的是”一群電腦”。如果把比賽的規格降低，李世石還是有可能獲得勝利吧！以AlphaGo的設計師黃士傑為例，在博士班期間設計圍棋AI「Erica」曾經擊敗過當時公認最強的「Zen」。

    另外，與AlphaGo對戰過的樊麾提到，『AlphaGo偶爾也會下錯棋。』不過，韓國的金成龍九段認為，『AlphaGo有幾次小錯誤，一開始認為這種小錯誤對李世石有利。不過，現在看來，似乎AlphaGo是以這種小錯誤換取更大的勝利。』

(四)電腦會不會出錯？

    基本上，電腦不應該出錯。不過，這個攸關所謂”出錯”的定義。另外，若是上述運算所需要的時間給予限制，則電腦在未能搜尋全部”勝利”棋譜的情況下，所下的棋步，有可能不是最佳的棋步。

    綜而言之，圍棋可以使用的戰術很多，AI採用的方法是1.了解賽局發展，2.擬定戰術，並立即應用。DeepMind利用深度學習來開發AlphaGo系統，利用人工神經網路在廣大的資料中，找出模式和意義。

二、限制與未來之路

(一)電腦冷靜、沒有情緒

    也許目前AlphaGo的設定就是從”勝利”棋譜的棋步中，找出勝利機率最高的棋步。不過，人類感性的一面，例如有時候面對棋力較低者或是小孩，讓子或認輸的感性，似乎是研發團隊未來在求勝之後，有餘力時可以教育AlphaGo的。

    例如2015年西班牙舉辦的自行車賽，選手Ismael Estaban在終點前300公尺爆胎，而後來趕上的選手AQgustin Navarro選擇放慢速度禮讓。

(二)無限可能

    以AlphaGo可以記憶棋譜的能力與自行模擬的訓練來看，超越人類的極限。例如，AlphaGo自行對決，模擬3,000萬局對弈。假設以每局4小時，不眠不休，則相當於5百萬天或13698年。相反地，以人類圍棋對弈經驗來看，假設30年不眠不休，則可以得到65,700局的經驗，相當於AlphaGo對弈局數的0.2%。再者，以記憶力來看，假設AlphaGo可以記住所有的棋局，而人類記憶力或許有其侷限。這樣，AlphaGo對戰人類時，獲勝的機會不無可能。

(三)對圍棋的貢獻

    文前提到與AlphaGo對戰過後對圍棋戰略的體認並有助於棋力的提升。有些人也擔憂AI取代圍棋教育師資。不過，在對戰期間，民眾掀起對圍棋學習的風潮，也算是一種貢獻。

(四)尋找AI挑戰

    AlphaGo和其他遊戲AI不一樣的地方是他的AI是一項”一般”的AI，也就是不侷限於圍棋項目，而是經由修改，可以應用到其他項目。例如已經在洽談與戰略遊戲「星海爭霸」的玩家比賽的可能。

參考文獻

黃立安，圈圈叉叉遊戲研究。

Gibney, Elizabeth (28 Jan 2016), “Google masters Go,” Nature, Vol529, pp.445-446.

Silver, David, Aja Huang, et al. (28 Jan 2016), “Mastering the game of Go with deep neural networks and tree search,” Nature, Vol529, pp.484-489.

註1：日本五子棋規則

1.黑方有三三、四四及長連禁手，即不管主動或是被動，若是下禁著點，則被判定為負。黑方下禁手時，白方必須指出才算獲勝，不過，這一點在電腦程式中，假設電腦不會出現忘記指出的錯誤。

2.五連與禁手同時出現則不算犯規，黑子仍算獲勝。

註2：本文感謝本系施懿宸老師在圍棋與圍棋AI上的指證。他並提供Nature雜誌上發表的圍棋AI文章訊息。

註3：本文從AlphaGo與李世石對戰新聞起，對AI的一些發想，提出一些思考。而對圍棋與AI的生疏為限制。若對圍棋的一些戰略，如「空」「劫」等，若能熟習，則更見樂趣。

附錄

一、圈圈叉叉遊戲的規則

1.兩位玩家在3X3的方格中，分別畫”圈圈”或”叉叉”。

2.先以垂直、水平或對角，連成一線者勝。