28 天自制你的 AlphaGo (1) : 圍棋 AI 基礎

01-30

知乎對於人機大戰的關注度很高，希望這個系列能讓大家對於人工智慧和圍棋有更多的了解。如果有收穫，請記得點一下贊。

大家都知道 AlphaGo v13 的三大組件是：

現有的強的圍棋 AI 也都是這個思路了，我們也會按這個思路講。在這一篇先看看圍棋和博弈 AI 的一些基本常識。

本系列已更新多篇，其它幾篇的傳送門：

(2) : 安裝 MXNet 搭建深度學習環境知乎專欄
(3) : 訓練策略網路，真正與之對弈知乎專欄
(4) : 對於策略網路的深入分析（以及它的弱點所在）知乎專欄
(4.5)：後文預告（Or 為什麼你應該試試 Batch Normalization 和 ResNet）知乎專欄
(5)：結合強化學習與深度學習的 Policy Gradient（左右互搏自我進化的基礎）知乎專欄
(6)：蒙特卡洛樹搜索（MCTS）基礎知乎專欄
(6.5): 在瀏覽器 Javascript 中直接運行策略網路（附第78手分析圖）28 天自制你的 AlphaGo (6.5) : 在瀏覽器 Javascript 中直接運行策略網路（附第78手分析圖）

一、圍棋規則

圍棋博大精深，但基本規則很簡潔。推薦這個在線教程：

熊貓圍棋網 - 遊戲的內容 - 第一天圍棋的介紹 - 十天即可掌握！『PANDANET圍棋入門』

正常來說，黑棋的第 1 手要下到你的右上角，比如說右上角的"星位"或者"小目"。雖然棋盤是對稱的，下其它三個角也可以，但這是對弈的一種禮貌，這樣下對方就知道你是懂規矩的（當然，也可以第 1 手下在邊上，或者中腹，但目前人類一般認為是虧的）。

如果等不及，看完教程的"第一天"內容，其實就可以立刻玩一下了。下圖是我做的純神經網路走棋（稱為策略網路 Policy Network），這是電腦從幾十萬局人類高手棋譜所訓練得到的數據，棋力不錯，有奕城段位的水準。大家可以點擊打開：

打開後，123456789代表電腦對於下一手的推薦選點的前9位。試試先按電腦的建議走一走，培養一下"棋感"吧！例如，你將會看到，電腦認為，人類高手最喜歡下的第一手在右上角的"星位"（下圖中的1號點）：

看個有趣的事情。人機大戰第四局第78手後，其實策略網路給出的應對是正確的（1號點）。當時AlphaGo犯錯（選擇了5號點），說明當時價值網路和Rollout的判斷出現了問題：

圍棋規則實際有很多細節，而且並沒有世界統一的規則。現有的規則有中國、韓國、日本、應式等等，在大多數情況下不影響勝負的判斷結果，但還是有微妙區別，比如說中國是數子，有"粘劫收後"，日韓是數目，終局有死活的判斷問題。

較為簡潔，適合電腦描述的可能是 Tromp-Taylor 規則： Tromp-Taylor Rules 。不妨做幾個調整：

a. 再簡化一點，去掉"全局禁同形再現"，改成"罕見循環局面由裁判決定"（畢竟三劫以上循環的可能性很小），這樣程序就不一定要存一個每個局面的hash表。

b. 禁止自殺，這樣更接近其它規則。

c. 雖然目前看最佳貼目可能更接近 5.5，但還是按中國現有規則的 7.5 吧，方便大家統一。

目前市面最強的程序是銀星17 和 Zen6，不過價錢也比較高（雖然都有X版）。而目前免費軟體中最強的是 Leela，棋力也還不錯，請點擊： chess, audio and misc. software

而且 Leela 有 console 的介面，可以接上目前常用的圍棋 GTP 協議。如果你有興趣，現在還有一個電腦圍棋的天梯，可以連進去與其它程序對戰，看自己的排名： 19x19 All Time Ranks 。

關於蒙特卡洛樹搜索，有一個常見的錯誤認識，在此先糾正。

在棋類博弈 AI 中，很多年前最早出現的是蒙特卡洛方法，就是到處隨機走，然後看哪裡的勝率最高。但這有一個問題，舉個例子：

a. 如果走在 A，人有100種應對，其中99種，電腦會立刻贏，只有1種電腦會立刻輸。

b. 如果走在 B，人有100種應對，但局勢很複雜，大家都看不清，如果隨機走下去，後續的勝率雙方都是50%。

那麼如果計算蒙特卡洛的勝率，電腦會發現走在 A 的勝率是 99%，走在 B 的勝率是 50%。

可是，電腦的正解是應該走 B！因為如果走了 A，人如果夠聰明，就一定會走電腦立刻輸的變化。如果電腦執意要走 A，就只能稱之為"騙著"了。

於是有的人會說蒙特卡洛方法有缺陷。但是，蒙特卡洛樹搜索在理論上解決了這個問題。

怎麼把人想像得盡量聰明？這就要靠博弈樹。蒙特卡洛樹搜索是博弈樹和蒙特卡洛方法的結合，它不會犯 A 和 B 的問題，它很快就會發現 B 比 A 好。容易證明，如果給定足夠的計算時間和足夠的存儲空間，蒙特卡洛樹搜索可以收斂到完美的博弈樹，成為圍棋之神。

然而，實際的計算和存儲資源是有限的，實際的 A （不妨稱之為陷阱）也會更複雜。比如說：

c. 如果走在 A，經過博弈樹的模擬，電腦幾乎是怎麼走都怎麼贏；但是人更清楚後續的走法，人會走出完美的應對，在許多步後電腦一定會突然死亡。

這時，電腦要走遍了博弈樹的許多層，才能發現原來走到 A 會存在致命缺陷，掉入陷阱。這種情況下，蒙特卡洛樹搜索就容易在 A 和 B 的問題上給出錯誤的答案。這有好多種表現，比如說"地平線效應"，又像 AlphaGo 被擊中的第 78 手。

圍棋中是有很多陷阱局面的，比如說"大頭鬼"。人工智慧如何正確應對陷阱局面，或者避免進入陷阱局面？這就需要策略網路（policy network）、價值網路（value network）、強化學習的共同作用。在後續的文章將會逐步介紹，包括具體的訓練方法。

1. 上面的那個純神經網路走棋是開源的，請改它的代碼，做一個基本的圍棋界面，包括吃子、打劫、點目等等基本規則。

2. 請閱讀它的論文： http://jmlr.org/proceedings/papers/v37/clark15.pdf 。

3. 請做一個傻瓜版的策略網路，比如說會做眼，會吃子。可以參考 GnuGO 的 6. Move generation 。

4. 請做一個傻瓜版的價值網路，比如說可以用"棋子向外輻射影響"的方法。可以參考 GnuGO 的 13. Influence Function 和 Bouzys 5/21 algorithm 。

本系列已更新多篇，其它幾篇的傳送門：

(2) : 安裝 MXNet 搭建深度學習環境知乎專欄
(3) : 訓練策略網路，真正與之對弈知乎專欄
(4) : 對於策略網路的深入分析（以及它的弱點所在）知乎專欄
(4.5)：後文預告（Or 為什麼你應該試試 Batch Normalization 和 ResNet）知乎專欄
(5)：結合強化學習與深度學習的 Policy Gradient（左右互搏自我進化的基礎）知乎專欄
(6)：蒙特卡洛樹搜索（MCTS）基礎知乎專欄
(6.5): 在瀏覽器 Javascript 中直接運行策略網路（附第78手分析圖）28 天自制你的 AlphaGo (6.5) : 在瀏覽器 Javascript 中直接運行策略網路（附第78手分析圖）

如需轉載本系列，請先與本人聯繫，謝謝。小廣告：晚上工作學習是否覺得光線不夠舒服，精神不夠集中，眼睛容易疲勞？不妨點擊看看我們的自然全光譜燈系列：Blink Sunshine護眼LED燈泡高顯指97顯色指數無頻閃學習檯燈床頭如果需要好用的耳機或錢包，我們也有