AlphaGo 演算法

（編注：這篇不屬於零機壹觸專欄，有關零機壹觸專欄，請看其他文章（link）。這篇純粹 startupbeat 轉載（link））

在朋友fb 上的熱烈討論中回答提問分享左少少AlphaGo 討論。在這裡正式深入淺出寫番次解釋 AlphaGo 咁神祕的演算法背後的邏輯。筆者覺得大部份寫 AlphaGo 的文章或報導，都寫得 layman 看不明。但實際上它的演算法並不算是個深的演算法。

AlphaGo 的演算法，是由四部份組成：
1. Value Network，一個 deep learning 的神經網絡（Convolutional/Space Invariant Artificial Neural Network, CANN/SIANN）；
2&3. 兩個 Policy Network，一個快一個慢；
4. 所謂蒙地卡羅樹搜尋演算法，將整件事串合。

先講左個蒙地卡羅樹搜尋（Monte Carlo Tree Search, 一般都稱為 MCTS）。個名好勁，但其實個概念唔深，仲係日常生活好常用的方法。
在電腦 algorithm 的範疇，講個「乜乜蒙地卡羅模擬」「乜乜蒙地卡羅方法」，其實都是和隨機有關。「蒙地卡羅方法」的定義，是「當個問題唔能夠用邏輯推理解決，就試下用隨機方法解決，不斷隨機試試到岩為止」。最簡單的例子例如年輕人未識揀對象，試下同唔同異性去街，試下夾唔夾；或大量買六合彩電腦票，都可以算是一種蒙地卡羅演算法。但正宗「蒙地卡羅方法」的意思，通常係用盡量多、數以萬計的隨機數，使到個答案漸漸浮現出來。

圖：一個用「蒙地卡羅方法」找 pi 的演算法，每個紅點藍點都是一次隨機

圍棋是個經典電腦工程難題，主要原因是它的「遊戲樹」（game tree）大到電腦處理不到。遊戲樹就是所有的棋局可能性。「蒙地卡羅方法」用在圍棋上，就是不斷隨機地在這「遊戲樹」中㨂不同的位置，然後用上文的三個神經網絡得出三個百分率，然後用這三個百分率去引導下棋。這便大概總括了 AlphaGo 的演算法。
稱為「蒙地卡羅樹」，是因為這個不斷隨機的嘗試，最終要收納為一個樹狀結構。

讀者讀到這裡，基本上可以不看下面講神經網絡，都算對 AlphaGo 的演算法有個概念。

繼續講講那三個神經網絡做乜。
Value Network 得一個，個用途係*估計*現在的局勢，AlphaGo 自己的勝算是多少。「估計」打了星，是因為這真的是估計，而不是數學：因為是用神經網絡做。設計 AlphaGo 的電腦科學家，是以模擬人腦捉棋的思維去想。若你捉過棋，e.g. 飛行棋、鬥獸棋也可以：通常捉到某處，你會大約腦中知道自己是處於上風或是處於下風。這個「處於上風或下風」的人腦估計，就是 Value Network 的主要功能。
神經網絡不是邏輯組成的，是個比較像人類的「感性思維」的技術。結構不複雜，讀 Computer Science 的大學一年級生也做到出來，結構詳情網上有很多，這篇主要講 AlphaGo 不贅。而且筆者會建議看不明人工神經網絡的人，跳過不看，總之知道它是個「用電腦扮人腦」的演算法就可以。因為看不明一樣可以明白 AlphaGo 的演算法。
其實用神經網絡去辨認圍棋格局，有點像用 AI 認一張 19×19 pixel 闊的黑白相片。

圖：一個超級簡化的人工神經網絡模型，可用作解釋原理：左邊是輸入，要不斷以計算廻圈改線上的 weight 使右邊y=t，完成一個訓練數據。一般人工神經網絡都要用上百萬數據做數億廻圈以達致準確。

圖：Convolutional Artificial Neural Network 的設計，右半由上圖的人工神經網絡組成

講過 Value Network，講下 Policy Network。Policy Network 就是當你下棋時，e.g. 飛行棋 / 鬥獸棋，通常到你行棋，你見到個棋局大約會有個「最有可能贏的下一步」的諗法。Policy Network 做的就是這個功能。
快的 Policy Network 準確度較低，慢的 Policy Network 準確度較高。兩者都會用來估計下一步。
AlphaGo 演算法中亦加入了個「盡量不用太常見的下法」的變數。

以上便大約講解了 AlphaGo 的整個演算法。
有些問題有朋友問，在這裡寫一下。

問：AlphaGo 的技術可以用在其他地方嗎？
答：其實 AI 的演算法好多都係只在該 AI 精通的地方可行，AlphaGo 也只是 ANI（Artificial Narrow Intelligence）。AlphaGo 可以用在其他棋類或遊戲上，但大部份遊戲都沒有需要，因為遊戲樹沒有圍棋大。而這個研究是啟發了電腦科學對包含神經網絡的 AI的潛能，提升期望。而包含神經網絡的 AI，則可以用在很多地方；AlphaGo 的示範是一個大到不能以邏輯或數學去完全計算的問題。

問：圍棋定麻雀複雜尐？有無其他問題複雜過圍棋？
答：以人類歷史上發明過的遊戲，包括棋、賭博、電子遊戲，圍棋都是無出其右的。筆者在零機壹觸專欄講過：//國際象棋的遊戲樹大小為10^123（10的123次方）；圍棋則是10^360。試比較中國象棋10^150，和黑白棋10^58。// 麻雀是 10^12。

問：其他人做唔做到 AlphaGo？
答：大概做到。你只要找部大型電腦，輸入大量訓練資料，然後給它大量時間去訓練，並不斷嘗試提升準確度，大概都可以做到。不過這個程度的投資，不如做其他更有盈利的項目好過。

問：AlphaGo 象徵著甚麼？
答：圍棋一直以來都是人類最後防線。圍棋輸給電腦，正式揭開 AI 時代的序幕：電腦已在所有對戰遊戲中完勝人類。想像下：玩電腦第一身射擊遊戲，20人類對20電腦，電腦科學現有技術，已有能力 100 局 100 勝。
AlphaGo 的技術並不是新事，都是上世紀九十年代已有；AlphaGo 的突破只是演算法，而不是科技。而且 AlphaGo 勝棋的原因，很大程度是它的龐大運算力，和訓練時數。所以這事上對學術和專業領域的震動不大，倒是很有娛樂性。

圖：Tic-Tac-Toe的整個「遊戲樹」。圍棋的遊戲樹要比這個大上許多。