AlphaGo 與深度學習

作者：項亮

AlphaGo 對工業界和學術界的影響是深遠的，至少對於我來說，他讓我直接就把研究方向從其他方面轉向了深度學習。從今年2月開始，就一直在研究 AlphaGo 的演算法，並嘗試自己寫圍棋程序，一直忙到4月份。最近已經把精力從圍棋轉向更實際的領域了，所以寫一篇文章總結一下。

個人覺得，整個 AplphaGo 對於機器學習來說，最核心的演算法就是深度學習（Deep Learning）和增強學習（Reinforcement Learning）。蒙特卡洛樹搜索 MCTS 是一個搜索框架，將這些機器學習的技術融合在了一起。今天這篇文章的重點在深度學習，增強學習以後再說。

蒙特卡洛樹搜索

每個博弈類的人工智慧演算法的基礎都是一個搜索演算法。比如我們上學時學習的 A-star 演算法，alpha-beta 剪枝，極大極小搜索(min-max search)。蒙特卡洛樹搜索也是其中一個。所有搜索演算法大概的步驟都如下：

1. 基於當前的狀態，給出N種自己可以做出的選擇

2. 對於每種選擇，評估一下這種選擇對自己的好處

3. 選擇對自己好處最大的選擇

但是這裡有一個難點，就是如何評估每種選擇對自己的好處，也就是如何設計出評價函數。比如說，如果我們設計出一個評價函數，結果發現在N種選擇中，有M個選擇得分一樣，而且都是最高分，那這個時候我們怎麼辦？這裡本質的原因是，如果基於當前的狀態只看一步，其實很多時候看不出好壞。所以就要多看幾步。比如

1. 基於當前的狀態，給出N種自己可以做出的選擇

2. 對於每種自己可以做出的選擇，做出對手可能做出的N種選擇

3. 這個時候，我們最多可以面臨 N^2 種局面，對每種局面進行評估

4. 反推出自己應該做出什麼選擇

舉個例子，比如給定一個評價函數Q，在當前局面下，自己有A，B兩個選擇，且評分一樣 Q(A) = Q(B)。

但是，如果我做出A選擇，對手可以做出A1選擇，在這種選擇下我就死了，對手就贏了。那麼我肯定不能選A。這個時候，如果發現我選擇B，對手的選擇中，沒有一種選擇能讓我立即就死了，那麼至少B還是比A好的。這其實就是極大極小搜索的基本原理。而 Alpha-beta 剪枝是對極大極小搜索的一種優化。

當然，在上面的例子里我們只向前看了2步。但是也許看2步還是看不出局勢的好壞。這個時候就要不斷的擴展深度，直到能看出局勢的好壞，然後再反推自己第一步怎麼走。Alpha-beta 剪枝在國際象棋領域取得了很大的成功，深藍就是基於這個演算法的。但當人們把這個演算法應用到圍棋時就發現了一個問題：因為圍棋每種狀態下的選擇遠遠大於象棋，造成在相同的算力下，圍棋很難向前看太多步，但同時又很難設計出一個評價函數在搜索深度不大時，就能看清局勢。

於是 MCTS 就誕生了。其實這個演算法很早之前就誕生了，只是在圍棋的領域裡才找到了自己的出路。這個演算法有如下的本質：

1. 他對局勢的評估，是基於自我對局進行模擬的。模擬的次數越多，估計的越准。這種評估基本能做到不需要太深的搜索，就能看清局勢。

2. 每次選擇評估什麼局勢時，都是選擇對當前勝率最大的節點進行評估

舉個例子，比如棋局進行到X手時，輪到黑棋下，

1. 黑棋找到10個自己可能下的位置，每個位置有兩個數，一個是W，一個是T

2. 找出10個位置中，黑棋下了勝率最大（勝率就是W/T， 當然出於探索的需要，一般會在這裡使用多臂賭博機的模型，所以選擇時並不完全考慮勝率，這個以後再細說)的位置，進行模擬對局。

3. 對局結束後，T = T + 1, 如果黑棋勝了，W = W + 1，同時這個節點的祖先節點中，所有黑棋對應的節點的W都會加1。

4. 假設經過一段時間後，黑棋可能下的10個位置都已經評估過了。這個時候就找出勝率最高的位置，開始考慮如果黑棋下在這個位置後，白棋怎麼下。假設白棋也找10個可能下的位置。

5. 當我們在評估白棋的位置好不好時，也要進行模擬對局。如果白棋勝了，那麼這個節點的W ＝ W ＋ 1，同時這個節點的祖先節點中，所有的白色節點的W都加1。

上面這個過程其實是一種 min-max 搜索。為什麼呢？我們考慮如果我們發現一個黑色節點，在之前的評估中勝率很高。但是，如果我們擴展了這個節點後，存在一個白色子節點的勝率很高（假設100%），那麼我們在評估那個白色節點時，這個黑色節點的T會增加，但W不變，此時就會拉低黑色節點的勝率，直到這個節點降低到一定的程度。計算資源就不會再評估這個節點，而是去評估別的黑色節點了。

從上面的描述時，我們知道 MCTS 需要解決兩個問題：

1. 在每個狀態下， 如果找出下一步的候選位置

2. 如何評估每個狀態的最終勝率。

1. 在傳統的 MCTS 里，是通過自己和自己下棋，一直下到最後確定勝負，然後下很多局可以計算出勝率。那麼自己和自己下棋，也得有一個演算法去給出下一步可能走在哪裡。

2. AlphaGo 在這裡有一個創新，就是不通過自我對局，而是直接通過神經網路基於當前局面，給出最後勝率的估計。

綜合上面的討論，下面這個問題顯然是 AlphaGo 需要解決的第一個問題：

1. 如果基於當前的局面，給出下一步的可能位置

這就是 AlphaGo 的 Policy Network 做的事情。在傳統的圍棋程序，比如 GnuGo 中，這一步大都是通過大量的規則去確定的。這裡我們不考慮這種方法，只討論如果通過機器學習，怎麼實現。

預測下一步的傳統機器學習實現

假設我們有一個數據集，包含了過去幾十年人類高手對局的棋譜。那麼我們就有了大量關於在某個盤面下，人類是怎麼走下一步的例子。在19路棋盤上，總共有361個位置，如果我們對每個盤面能建立一個特徵，那麼就可以轉化為一個361類的分類問題。這個時候最簡單的就是可以用最大熵的分類器來解決這個問題。

更進一步，出於提高效率的考慮，我們也可以把這個361類的分類問題轉化為一個兩類分類問題。就是對於一個盤面S和一個合法的下一步p。判斷y(S, p)是1， 還是0。是1表示人會下在p這個位置，是0表示人不會下。對於兩類分類問題，我們的任務就是對於盤面S和位置p，抽取相關的特徵。此時，我們的圍棋知識就可以派上用場了：

1. 如果我下在p，是不是就能吃掉對方几個子？

2. 如果我下在p，是不是能救活我方的幾個子？

3. 如果我下在p，是不是能讓對方的幾個子處於危險之中？

4. 如果我下在p，是不是能讓我方几個子脫離危險？

5. 如果我下在p，是不是能斷開對方的大龍？

6. 如果我下在p，是不是能讓我方的大龍連回家？

7. 如果我下在p，能否破對方的眼？

8. 如果我下在p，是否能做我方的眼？

9. 如果我下在p，是否征子有利？

10. 如果我下在p，能否讓一塊棋活了？

11. ……

基於圍棋知識，我們可以設計出很多特徵。

同時，在傳統的機器學習中，也可以用模版法。直接抽去p這個位置的N鄰域，hash出一個數做為特徵。這個特徵最終的權重代表在歷史的對局中，當遇到這個局部時，人類會在p落子的可能性。

很不幸的是，當我們運用大量的圍棋知識去設計各種特徵，並加上各種鄰域的模版特徵之後，下一步預測的準確率只能達到30%~40%之間。這也是目前發表的paper中具有的水平。

預測下一步的 DCNN 實現

由於傳統方法在這個問題上表現的很挫，因此 AlphaGo 用 DCNN（deep cnn）來解決這個問題。DCNN 之前在圖片分類的問題中取得了很大的成功，給定一幅圖，DCNN 可以知道這個圖裡是一棵樹，還是一隻貓，還是一艘船，還是一棟樓。由於圍棋的棋盤其實可以看成一個19*19的圖片，每個像素就是對應的位置的狀態（是黑棋，還是白棋，還是沒放棋）。因此我們可以把每個盤面表示成一個三通道的圖片，對於位置p，

1. 通道0 ＝ 1 表示p放的我方的子 （這裡我方代表在這個盤面下，下一步走棋的子的顏色，對方反之）

2. 通道1 ＝ 1 表示p放的對方的子

3. 通道2 ＝ 1 表示p沒放子

然後這個圖片的類別就是下一步可能的位置，一共有361種可能性，因此就是一個361類的分類問題。然後用 DCNN 訓練一下，結果發現預測下一步的準確率可以達到44%。這是很令人驚奇的，因為整個過程中我們沒有利用到任何圍棋知識，也沒有提前任何特徵。DCNN 就自動學習出44%的精度了。

當得到這個驚人的結果時，群眾們覺得，還是加點圍棋知識吧，於是有人把3通道擴展到了更多的通道，比如：

1. 通道0 ＝ 1 表示p放的是我方的棋子

2. 通道1 ＝ 1 表示p放的是對方的棋子

3. 通道2 ＝ 1 表示沒有放子

4. 通道3 ＝ 1 表示p放的是我方的棋，且於p相連的棋串只有1口氣

5. 通道4 ＝ 1 表示p放的是我方的棋，且於p相連的棋串有2口氣

6. 通道5 ＝ 1 表示p放的是我方的棋，且於p相連的棋串有3口氣

7. 通道6 ＝ 1 表示p放的是我方的棋，且於p相連的棋串大於3口氣

8. 通道7 ＝ 1 表示p放的是對方的棋，且於p相連的棋串只有1口氣

9. 通道8 ＝ 1 表示p放的是對方的棋，且於p相連的棋串有2口氣

10. 通道9 ＝ 1 表示p放的是對方的棋，且於p相連的棋串有3口氣

11. 通道10 ＝ 1 表示p放的是對方的棋，且於p相連的棋串大於3口氣

12. 通道11 ＝ 1 表示p是上一步剛剛落的子

可以看到，這裡只利用到了2個圍棋知識，一個是棋串，一個是氣。另外還利用到了上一步的信息。然後用 DCNN 訓練一下，會發現下一步的預測準確率能達到53%左右了。在 AlphaGo 里，還利用到了更多的圍棋知識，它們一共使用了48個通道（也就是每個點提取了48個特徵），然後就可以達到57%的準確率了。

當我看到這個結果時，確實覺得 DCNN 的效果已經超出我之前的認識了，因此促使我開始全面的研究深度學習。

目前開源的圍棋程序 Pachi (GitHub - pasky/pachi: A fairly strong Go/Baduk/Weiqi playing program) 已經支持了 DCNN 用來預測下一步，有興趣的可以關注一下。按照我在網上的實測，配合不太多的模擬之後，棋力在業餘2段到3段之間。關於這裡用的網路的詳細信息可以參考 [Computer-go] CNN with 54% prediction on KGS 6d+ data

本文首發微信公眾號【ResysChina】，中國最專業的個性化推薦技術社區。

猜你喜歡：「深度學習與推薦系統」

推薦閱讀：