百度正用谷歌AlphaGo，解決一個比圍棋更難的問題 | 300塊GPU在燃燒_風聞

曉查 發自 凹非寺

量子位 報道 | 公眾號 QbitAI

9102年，人類依然不斷回想起圍棋技藝被AlphaGo所碾壓的恐怖。

卻也有不以為然的聲音：只會下棋的AI，再厲害也還是個運動員啊！

百度説：你們錯了，它還是一位數學家。

百度硅谷AI實驗室的同學們，就在用這個出自谷歌DeepMind的圍棋算法，解決一個比圍棋複雜得多的數學問題。

為了重新訓練這個算法，百度用了300張1080Ti和2080Ti顯卡。

他們解決的問題，叫做“圖着色問題”，又叫着色問題，屬於前些天讓中國奧數隊全軍覆沒的圖論。它是最著名的NP-完全問題之一。

簡單來説，就是用盡可能少的顏色，給一張圖的頂點上色，保證相鄰頂點的顏色不重複。

10個頂點的簡單版是這樣的：

而複雜版……只要頂點足夠多，分分鐘讓人類數學家無從下手，如果有512個頂點，這個問題的複雜度會比圍棋高出幾百個數量級。

在這個數學問題上，運動員AlphaGo表現優秀，最高能將一張圖所用的顏色減少10%。

從四色定理談起

就算你對“圖論”、“着色問題”這些詞有點陌生，應該也聽説過“四色定理”。這是第一個由計算輔助證明的數學定理。

四色定理告訴我們，只需4種顏色我們就可以讓地圖上所有相鄰國家的顏色互不相同。

這其實就是一個平面上的着色問題，國家可以簡化為頂點，國與國之間的相鄰關係可以簡化為連接頂點之間的線。對於平面圖而言，顏色數k最小等於幾？

歷史上數學家已經手工證明了五色定理（k=5），但是因為運算量太大，在將顏色數量進一步減少到四種（k=4）時卻遲遲無法解決，最終在70年代靠計算機才完成證明。

一般來説，我們可以用貪心算法解決這個問題，其基本思路是：先嚐試用一種顏色給儘可能多的點上色，當上一步完成後，再用第二種儘可能多地給其他點上色，然後再加入第三種、第四種等等，直到把整張圖填滿。

或者是用深度優先搜索算法，先一步步給圖像着色，若遇到相鄰點顏色相同就回溯，再換一種着色方法，直到問題解決為止。

比圍棋世界更復雜

如果圖的頂點數比較少，以上兩種方法還可行，但隨着頂點數的增加，以上兩種算法的侷限性就暴露了出來。

△ 用貪心算法着色和最優解的對比

貪心算法會陷入局部最優解，而深度優先搜索算法的運算量會越來越大，以至於完全不可行。

圖着色問題的複雜度隨着頂點數增加而急劇增長。當頂點數達到512時，其可能得狀態數就達到達到了10^790，遠超圍棋的10^460，當然更是比全宇宙的粒子數10^80多得多。

即使中等大小圖的狀態數也遠超圍棋，如果頂點數量達到1000萬，複雜度會大得驚人，相當於在1後面有4583萬個0。

另外着色問題還有另一個複雜維度，圍棋算法可以反覆在同一張相同棋盤上進行測試，而圖即使頂點相同，因為連接各點的邊不相同，結構也不完全相同。

從圍棋中獲得啓發

這些更復雜的問題對算法的訓練和推理提出了極大的挑戰。而AlphaGo曾在解決這類複雜問題上取得了很大的成功，研究人員也很自然的想到了用它來解決圖的着色問題。

對於這類問題，我們一般採用啓發式搜索算法（heuristic search），就是在狀態空間中的搜索對每一個搜索的位置進行評估，得到最好的位置，再從這個位置進行搜索直到達到目標。

AlphaGo使用的蒙特卡洛樹搜索（MCTS）用的就是一種啓發式搜索算法。

△ 蒙特卡洛樹搜索算法示意圖：選擇路徑；擴展樹；由神經網絡執行模擬；將最終結果反向傳播，更新路徑節點。

AlphaGo下棋通過正是這種方法，計算當前棋盤上獲勝概率最大的點，直到贏棋為止。

圖着色問題與圍棋也有類似之處，它的每一步棋就是給接下來的點填上顏色。它和圍棋和象棋一樣都可以用強化學習來解決問題，差別則是獎勵。

在圖着色問題中，最明顯的獎勵選擇是顏色種類，使用的種類越少越好。而在圍棋和象棋中，獎勵是遊戲的勝負結果。

在棋類遊戲中，讓算法在自我對弈中進化是很一件很自然的事，讓表現最好的學習算法與自己對抗，這就是AlphaGo的升級版本AlphaGo Zero。

AlphaGo Zero沒有學習人類棋譜，它只是懂得圍棋規則，在不斷的對弈中獲得提高，谷歌只用了21天，就讓這個0基礎的升級版打敗了5-0戰勝柯潔的AlphaGo Master版。

當AlphaGo進化到自學版本AlphaGo Zero後，它就更適合做圖着色問題了，因為着色問題是沒有所謂“人類棋譜”可以學習的。

在圖着色問題種，研究人員讓AlphaGo Zero與其他算法比賽，看誰用的顏色種類少，這就是算法的獎勵機制。

原理

和AlphaGo一樣，圖着色算法也有策略網絡（p-network）和價值網絡（v-network），p是頂點塗某種顏色的概率，v是最終顏色數量少於之前最佳算法結果的概率。

而在圍棋遊戲中，p代表落子位置的概率，v代表最終獲勝的概率。

為此，研究人員設計了一個快速着色網絡（FastColorNet）。

對於這個網絡，有如下要求：

1、可擴展性（Scalability）：線性O(V)或線性對數O(E+VlogV)時間複雜度，保證它在更大的圖形（比如1000萬頂點）上也能使用。

2、完整圖形上下文（Full Graph Context）：不同的圖有不同的着色策略，因此網絡需要有圖形結構的信息。

我們將該網絡的損失定義為：

π代表當前行走步數，z代表當前使用的顏色數。

上圖就是FastColorNet的架構。它的輸入包含兩個部分：問題上下文（problem context）和可能顏色上下文（possible color context）。

問題上下文（problem context）是根據剛剛着色的頂點，來安排接下來對哪些頂點進行着色。它在任務開始和結束的時候都是零。問題上下文中包含的頂點數是一個超參數，在實驗中設置為8。

可能顏色上下文（possible color context）是以上頂點集合每種可能用到的顏色。它也是一個超參數，在實驗中設置為4。

以上兩個上下文都輸入當策略網絡和價值網絡中。

策略網絡使用全局圖形上下文（global graph context），它負責計算將每個顏色選擇分配給當前頂點的概率。

隨着填充過程的進行，顏色數量會逐漸增加。為了支持顏色數量的變化，它會首先獨立處理每種顏色，產生一個非標準化分數，然後通過seq2seq模型對該分數進行處理，該模型還會考慮與其他顏色的依賴性。最終通過softmax操作得出歸一化的填充顏色概率。

策略網絡利用了具有相同顏色的節點之間的局部關係，提高了準確性，同時還降低了大圖計算的時間複雜度。

價值網絡負責從輸入數據預測着色問題最終的結果。 問題上下文（problem context）中的頂點與着色順序存儲在對應的序列中。使用seq2seq模型處理此序列，然後將這個序列與圖形上下文（graph context）組合起來，並將它們饋送到完全連接的reLU層中，最終結果輸入softmax，計算出勝利、失敗或平局的概率。

結果

研究人員用FastColorNet的強化學習過程來訓練圖着色問題，圖形大小從32個頂點到1000萬個頂點不等。

上圖顯示了圖所需顏色的數量如何隨頂點數量的增長而增長。

在32K到16M個頂點的圖上進行測試，FastColor在訓練集中使用的顏色比以往的啓發式搜索算法提高了5％-10％。 儘管在測試集有所遜色，但性能也比先前的算法高出1％-2％。

雖然提升比例看起來不高，但這種算法顯示出解決此類問題的潛力。Twitter上一位網友這樣評價：這篇文章以線性複雜度O(n)解決了一個NP完全問題。

論文地址：https://arxiv.org/abs/1902.10162