AlphaGo演算法再思考

加關注

微信號：無聊的王博士

2016年3月20日，谷歌人工智慧程序AlphaGo在與韓國圍棋高手李世石的最後一場比賽中獲勝,最終以4-1的比分贏得這場總計五局的人機大賽。之後在2017年5月27日，柯潔九段中盤告負,總比分0：3敗於AlphaGo。隨後，AlphaGo團隊公布了其基本的程序設計思路。

在基本設計思路公布之後，很多從事深度學習的研究者進行了解讀，其中比較全面的一篇名叫《這是迄今為止，AlphaGo演算法最清晰的解讀》，本文的第一部分節選並改編自這篇文章，有興趣的朋友可以找來看看。

本篇從以下三個方面再次解讀Alphago的演算法原理：1 AlphaGo演算法解的簡單介紹；2 從人類下圍棋的角度審視AlphaGo； 3 其他一些思考。

01

AlphaGo演算法的簡單介紹

AlphaGo 行棋的時候需要用兩個小的演算法：一個是value net（形勢判斷：模擬中，我走這步，我贏的概率是多少），另一個是policy net（選點：模擬中，這個局面我走那幾步最強）。

policy net 著眼於短期行為——計算下一步如何走，這個下一步是經過大量訓練產生的結果，同時要儘可能的讓局面向著勝率高的方向移動（和value net 產生了關聯）。

value net 著眼於最終的結局好壞——判斷局面，宏觀的判斷當前局面下，如果按照雙方最佳行棋（和policy net產生關聯），自己終局時的勝率是多少。

總體上，利用policy net 產生的各種棋譜來訓練value net ，再用訓練到的value net修正policy net 選擇下一步落子的位置，就是AlphaGo的基本演算法邏輯。

1.1 policy net怎麼工作的?

先大概看下這個圖。現在輪到黑棋下，圖上的數字是AlphaGo認為黑棋應該下這步的概率。我們還發現，只有幾步的概率比較大，其他步可能性都很小。這就像職業棋手了。學圍棋的人知道，初學者會覺得那裡都可以走，就是policy（選點）不行，沒有選擇性。隨著棋力增長，選擇的範圍在縮小。職業棋手就會鎖定幾個最有可能的走法，然後去推演以後的變化。

policy net先向職業選手學習。她從KGS圍棋伺服器，學習了3000萬個局面的下一步怎麼走。也就是說，大概職業選手怎麼走，AlphaGo她已經瞭然於胸。因此其預測職業選手的著法有57%的準確率。提醒一下，這還是AlphaGo「一眼」看上去的效果，她沒開始推演（模擬）呢。而且她沒預測對的著法不一定比職業棋手差。

此外，AlphaGo從職業棋手學完後，感覺沒什麼可以從職業棋手學的了。為了超越老師和自己，獨孤求敗的她只能自己左右互搏，通過自己下自己，找到更好的policy。比如說，她從監督學習學到了一個policy，P0。

AlphaGo會例外做一個模型P1。P1一開始和P0一樣（模型參數相同）。稍微改變P1的參數，然後讓P1和P0下，比如，黑用P1，白用P0選點，直到下完（終局）。模擬多次後，如果P1比P0強（贏的多），則P1就用新參數，否則，重新再原來基礎上改變參數。我們會得到比P0強一點點的P1。注意，選點是按照policy的概率的，所以每次模擬是不同的。多次學習後AlphaGo會不斷超越自己，越來越強。

1.2 value net怎麼工作的?

在講value的原理前，先看看定性看看value的結果。如圖，這是AlphaGo用value net預測的走下一步，她贏的概率。空的地方都被藍色標示了，越深說明AlphaGo贏的概率越高。這和我們學的棋理是相符的，在沒有戰鬥時，1、2線（靠邊的地方）和中間的概率都低，因為它們效率不高。而且大多數地方的概率都接近50%。所以說贏棋難，輸棋也很難——目前情況是開局，離終局還很遠。

Value Net可以用下面這個公式來解釋：

V*是這個評估的真值。

p*是正解（產生正解的policy）。

s是棋盤的狀態，就是上面那個圖，那個圖就是一個狀態s。

V是對這個狀態的評估，就是說贏的概率是多少。

p是AlphaGo前面所說學到的最強的policy net。

如果你知道V*這個函數，在當前局面，你要對走下一步（圍棋平均有250種可能性）後的狀態s進行評估，選最大的V*走就行。圍棋就完美解決了。但是，前面說了，V*不存在。同樣p*也不存在（理論上存在，實際因為搜索空間太大，計算量太大找不到）。

AlphaGo天才般的用最強poilicy，p來近似正解p*，從而可以用p的模擬Vp來近似V*。即使Vp只是一個近似，但已經比現在的職業9段好了。想想她的p是從職業選手的著法學來的，就是你能想到的棋她都想到了。而且她還在不斷使的p更准。頂尖職業棋手就想以後的20-40步，還會出錯。AlphaGo是模擬到終局，還極少出錯。

value net也是一個監督的深度學習的模型。多次的模擬的結果（誰贏）為它提供監督信息。它的模型結構和policy net相似，但是學的目標不同：policy是下步走哪裡，value是走這後贏的概率。

簡單說，Value Net的邏輯是，在當前狀態為s，且下一步選擇為p的情況下，尋找下一步對應的V（s+1），使得V（s+1），取值最大（勝率最高）。至於如何估算勝率，下到終局就可以了。

當然對於AlphaGo來說，這些V（s）早已瞭然於胸——我都下了幾千萬盤了，這些局面s對應的勝率V（s）大概我都知道啦。

以上就是AlphaGo演算法的基本介紹。

02

從人類下圍棋的角度審視AlphaGo

我們人類下圍棋大概是以下步驟：

A、根據經驗選擇幾個最可能的落子點。

B、選擇其中一個落子點，然後推演接下去雙方的下法，比如推演雙方各下20步。

C、判斷推演完的情況對自己是否有利，具體利益有多高，記錄下該利益d1。

D、重新選擇一個落子點進行B、C步驟。

E、總結所有的d1，d2，d3... 選擇最佳結果。

這種思維是一個單向的線性行為（看上去有多次選擇，但實際上是簡單的循環）。

相比之前所述AlphaGo的行棋，不難發現人類和他的演算法有很多不同：

2.1 從後往前下棋

我們人類下棋是一步一步從前往後下的，因為圍棋千變萬化，誰也不知道最後是下成什麼樣子，是收官還是中盤決勝，人類肯定不會在計算下一步的時候考慮最後的結果如何。

但計算機強大在其記憶容量——內存太大，在訓練的時候就記住大量的不同局面s，以及不同局面s下對可能對應的勝率V（s）。

所以，只要遍歷一下內存里的大量s，總可以找到目前局面接近的歷史局面，並估算下幾步以後的局面s+n對應的勝率V（s+n）。從而選擇較好的下法。知道了後面的結果，只要引導局面向自己需要的結果前進即可。

這種下法是逆推的——我知道我想要前進的方向，我引導目前的局面向我需要的、勝率高的局面前進。

也就是說，AlphaGo的下法是從後往前下。

2.2 形狀的還原

圍棋里講究一個手順，大致的意思是：黑白雙方在某個局面s下各下幾手棋，形成了一個局面s+n。假設各下5手吧，局面由s變成了s+5，這5手的次序（手順）標註為：

黑1 黑2 黑3 黑4 黑5

白1 白2 白3 白4 白5

則，假設另一種下棋的次序，但最終的結果不變，假設這種新的次序（新手順）是：

黑1 黑3 黑2 黑4 黑5

白1 白3 白4 白2 白5

形成的局面依舊是s+5，這裡就是形狀還原了。

這種不同的下法卻導致相同的狀態s的情況，對於AlphaGo的Value Net來說是很好的事情——減少了需要記憶的局面s的數量；實際上，某個局部如果是具有這種還原性，顯然是一個雙方可以接受的局部妥協解，是雙方博弈的結果——因此也更加接近最優解——這對policy net的計算也有參考價值。這種情形很類似於圍棋中的「定式」，當然定式是在開局的階段，而這種常見的還原形狀是在中局時期。

因為計算機具有強大的記憶能力，因此他可以記憶這些「中局定式」；反觀人類忽視了記憶這些中盤戰鬥中的特定形狀，所以這點上人類是吃虧的。

2.3 打劫的問題

打劫，是指黑白雙方都把對方的棋子圍住，這種局面s下，如果輪白下，可以吃掉一個黑子；如果輪黑下，同樣可以吃掉一個白子——這樣下了兩手的局面s+2就還原到了局面s，如此往複就形成循環無解，所以圍棋中有打劫的規定：根據規則規定「提」一子後，對方在可以回提的情況下不能馬上回提，要先在別處下一著，待對方應一手之後再回「提」。如圖中的情況：

很多人認為打劫是計算機的弱點，因為打劫導致局面複雜化，對於人類棋手來說，打劫中需要1不斷的計算劫材，2判斷得失以及3尋找合適的消劫時機——聽起來就頭大。但對於AlphaGo來說，這些過程並不存在，他依舊按照自己的下棋邏輯進行自己的判斷：

在當前狀態為s，且下一步選擇為p的情況下，尋找下一步對應的V（s+1），使得V（s+1），取值最大（勝率最高）。至於如何估算勝率，下到終局就可以了。

在人類看來需要各種判斷和計算的複雜的打劫局面——在AlphaGo看來和其他的局面沒什麼不同——都是19×19的一張平面圖像而已——而這些平面圖的近似圖形很可能已經在自己的內存庫里了。

2.4 AlphaGo演算法的啟發意義

人類的演算法是局限於以下邊界條件的：

A、人記憶力有限；

B、盤面的判斷是積少成多，先判斷實地，再判斷一部分厚勢，是一個定性的判斷。

計算機的演算法很粗暴，也很有效，因為：

A、計算機的記憶力遠勝人類；

B、盤面的判斷是由實際下完後的結果判定的，是一個全盤的定量判斷。

本質上，AlphaGo開創了一種從後往前下圍棋的方法：判斷某盤面下繼續到終局的勝率，引導局面向有利方向前進。

所以最重要的啟發應該是，在確定規則的棋盤上，人類確實無法戰勝具備合適演算法的電腦。無論棋盤是19路還是29路。

03

其他一些思考

3.1 AlphaGo的弱點？

AlphaGo走的是大巧不工的路線：只要我的內存足夠大，賽前的訓練足夠多，我一定能找到和目前局面相似的「下過的棋局」，我可以判斷目前的局面是否對我有利，又可以找到合適的下一步p來引導目前的局面走向對我更有利的下一個局面。

那麼AlphaGo有沒有弱點，如果有，如何利用並戰勝他？

實際上，越是接近終局，可下的位置越少，局面越簡單，AlphaGo越是不可戰勝——收官無敵——當年石佛也應該敵不過。那麼可選位置最多的開局呢？

AlphaGo在開局階段是參考人類的定式進行訓練的，並沒有盲目的進行蒙特卡洛隨機擲色子，因此可以確定這部分的能力大約等同於人類頂尖水平，似乎人類可以在開局做點什麼？

遺憾的是，由於開局階段離終局實在太遠，很多特別的選點都會在後續進程中還原成一些普通的選點，因此開局並沒有什麼機會。

終局沒有機會，開局沒有機會，似乎只有在中盤存在一些可能。

例子是AlphaGo和李世石的第四盤，盤中78手：

白78手之後黑棋AlphaGo出現了很多奇怪的招數，很可能78手的這個局面超過了他的「局面內存庫」的搜索範圍。

當然在後續的進一步優化的過程中，AlphaGo可能已經完善了自己的「局面內存庫」，這些神之一手都被收納其中，人類的機會就更小了。

3.2 貼目

貼目是現代圍棋的發明，用以平衡先手相對後手的優勢。歷史上貼三目，三目半，四目，四目半，五目，五目半，六目半，七目半的都曾經存在過。而實際上，日本韓國現今實行貼六目半，中國以及應氏杯規則等價於七目半。到底多少合適？恐怕沒人能說清！

AlphaGo似乎可以用來計算黑先手應當貼目的大小。為此，試提出如下問題：

在19x19的棋盤上，假設雙方棋力相同，進行儘可能多的比賽。求按黑先白後順序，完賽後雙方所佔空平均相差多少？

因為黑先，因此總應該是黑占的空比白多，而這個差值，就應當是貼目的大小。

但用AlphaGo實現起來，可能遇到點麻煩。因為其value net是根據獲勝概率來計算的，因此如果沒有事先約定貼目的大小，value net將無法計算獲勝概率——頂尖棋手勝負常常一兩目而已，更何況AlphaGo的左右互搏。因此可能需要改進演算法。

如果能利用深度學習計算出黑棋應貼目大小，對圍棋是一大貢獻。

3.3 圍棋的意義

我們自以為最厲害的圍棋，也被計算機演算法打敗了。但並不存在什麼機器打敗人類的說法。

畢竟，AlphaGo的團隊也是由人類組成的，因此應該說，是人類創造的各種演算法、計算機技術的進步、研究人員長期努力的共同結果戰勝了人類最強的圍棋選手。

那麼圍棋的意義是什麼？

本質上還是一種遊戲，一種由人類發明的，用以打發時間和排遣無聊的遊戲。

能夠創造未有之物，是我們人類區別與其他任何物種和機器的最終區別。

這一點上看，AlphaGo只是人類創造的演算法而已，連智能的邊都沾不上。

如果說偉大，那個創造圍棋的中國人，比創造AlphaGo的人要高到不知道哪裡去了。

但我們身為中國人，沒有創造出AlphaGo，確實應該反思。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！