魔方全能小王子降臨：一個完全不依賴人類知識的AI

魔方全能小王子降臨：一個完全不依賴人類知識的AI

來自專欄量子位44 人贊了文章

魔栗少女 發自 凹非寺

量子位 出品 | 公眾號 QbitAI

小時候，感覺大家都在玩魔方。

我也買了一個，費盡腦細胞才拼出一層。然後，就沒有然後了……

後來遇到會玩魔方的小夥伴，我總是忍不住仰慕一下他的操作。

但是沒想到，有一天，我還能遇到一個會玩魔方的人工智慧。

最近，加州大學歐文分校的一個研究小組，發布了基於強化學習的魔方復原AI。

這隻AI 完全不需要依靠人類的知識來解魔方，有速度有準度。據說沒有它復原不了的魔方。

除了這一種——

魔方的正確打開方式

如何讓AI自己學會破解魔方？

第一步是建立AI對魔方的基本認知。

魔方有26個小方格，可以按照它們身上的貼紙數量來分類——

中心，一張貼紙。

邊邊，兩張貼紙。

角角，三張貼紙。

這樣一來，54張貼紙，每張都有自己獨一無二的身份，即身屬哪類方格，同一方格上的其他顏色有哪些。

用獨熱編碼 (one-hot encoding) 便可以輕鬆表示每張貼紙的位置。

不過，由於每一張貼紙的位置不是獨立的，而是和其他貼紙相關。這樣，把表示方式降個維，每個方格可以只看一張貼紙。系統視角就是圖中右邊的樣子——

然後，按朝向來標註魔方的6個面，前(F)，後(B)，左(L)，右(R)，上(U)，下(D) 。

正對要操作的那一面，順時針轉 (90度) 直接用這幾個字母就行了，逆時針在字母后面加個撇。比如，R和R』就是把右面順時針轉90度，以及逆時針轉90度。

這樣算的話，6個面，操作一共有12種。

每一個時間步(t)，都有一個狀態(st) ，都會執行一個動作 (ta ) 。然後，就有了一個新狀態(s t+1 ) ，得到一個獎勵數值(Rs t+1 ) ，成功是1，沒成功是-1。

三階魔方的狀態有4.3e^19種，而其中只有一種狀態能夠收到獎勵信號，那就是復原成功的狀態。

正因如此，同樣是走在強化學習的大路上，魔方和圍棋之類的遊戲，存在明顯的不同。

到不了的終點？

在這樣險峻的情況下，如果使用A3C演算法，理論上有可能永遠到不了終點。

面對稀有的獎勵，團隊受到策略迭代 (policy iteration) 的啟發，提出了一種名為「自學迭代 (Autodidatic) 」的深度強化學習演算法，簡稱ADI。

在這裡，策略評估和策略優化兩個步驟會交替進行，最終找到最優策略。而把策略迭代和價值迭代 (value iteration) 結合在一起，便可以把評估和優化合而為一。

這還不是全部，把ADI和蒙特卡洛樹搜索 (MCTS) 搭配食用，便稱為「DeepCube (深度魔方) 」。到目前為止，復原魔方成功率高達100%。

自學迭代 (ADI)

ADI的訓練，用的是一個迭代監督學習過程。

深度神經網路fθ，要先學習一個策略 (policy) ，了解在已知的狀態下，應該採取怎樣的旋轉動作。

深度神經網路fθ(s)，參數θ，輸入的是狀態s，輸出的是一個價值和策略的組合 (v,p) 。這個輸出可以為MCTS鋪路。

生成訓練樣本，要從復原完成的狀態 (ssolved) 開始。

從初始狀態打亂魔方，轉動k次，得到k個魔方的序列。把上述打亂活動重複l次，生成k*l個訓練樣本。

給每一個訓練樣本，生成它的12個後代的狀態，然後用當前的價值網路，來估計每個後代的價值。

然後，這些後代裡面，價值評估的最大值，就是這個樣本的價值訓練目標。

而最大值對應的動作，就是這枚樣本的策略訓練目標。

復原大法

這裡，蒙特卡洛樹搜索 (MCTS) 才要出場。

團隊用了一個非同步MCTS，並用之前訓練好的fθ網路幫它增強了一下——策略輸出p可以降低它的廣度，價值輸出v可以降低它的深度。

要為每一個已知狀態s0，種起一棵搜索樹。

樹苗是T={s0}，迭代就從這個單一的集合開始。

在樹苗身上執行模擬遍歷 (simulated traversals) ，直至到達一個葉節點 (leaf node) 為止。

每一個狀態(s』)，都有它的專屬記憶——

Ns(a)，是從s開始，執行某個動作a的次數。

Ws(a)，是動作a從s那裡獲得的最大價值。

Ls(a) ，是動作a在s處的virtual loss (虛擬損失) 。

Ps(a) ，是動作a在s處的先驗概率。

每一次模擬，都是從根節點開始，跟隨著樹的策略，不斷跌帶著選擇各種各樣的動作。

每一個時間步，都會選擇一個動作。

而Virtual loss可以避免搜索樹多次關照同一個狀態，也可以阻礙多個非同步worker走上同樣的道路。

到達一個葉節點之後，狀態就會加上後代 (s』) 。這樣，樹上有了新的元素，後代也會生成自己的記憶。

生生不息。

全能小王子

枝繁葉茂之後，測試一下效果：DeepCube大戰另外兩個魔方高手演算法。

一個是Kociemba在1992、1992年提出的兩段式演算法，依賴人類提供的領域知識，用群論來解魔方。這種方法的特點是運行速度非常非常快，也的確能解開任何狀態下的魔方。但它所找到的解法，通常不是最優解，比其他方法要多花幾步。

另一個是Korf在1997年提出的迭代式深入A*(IDA)*演算法。這種方法藉助模式庫進行啟發式樹搜索，無論在什麼樣的初始狀態下，都能找到最優解，但尋找答案的過程要花費很長時間。

這些方法展開了兩場競賽。

第一場，DeepCube和Kociemba的方法用640個隨機打亂的魔方進行了比拼，這些魔方都被胡亂擰了1000次。

兩種方法都在1小時之內解開了全部魔方，Kociemba方法的速度比較快，每個魔方用時不到1秒，而DeepCube平均每個魔方用了10分鐘。

Kociemba方法找到的解法都在31-33步的樣子，DeepCube的解法分布稍微廣一點，大概從28到35都有，不過作者們說，在55%的情況下都能匹敵Kociemba方法。

第一場，比速度。

DeepCube和Kociemba都成功復原了640個 (1000次打亂) 魔方。

DeepCube單個魔方用時的中位數是10分鐘，Kociemba是不到1秒鐘。但，在55%的魔方大戰中，DeepCube或與後者速度相當，或好於後者。

其實自學成才的DeepCube和人類智慧結晶的Kociemba，基本上還算旗鼓相當。

至於Korf？這位選手玩一個魔方需要6天。

第二場，比最優解。

100個魔方，每個經過15次打亂。

這次Korf比較厲害，中位數是13步，只有一個魔方超過15步。

不過，DeepCube也不差，在74%的魔方上，都和Korf找到了一樣的最優解。當然DeepCube超過15步的次數，比Korf略多一點。

至於kociemba？成績太差，慘不忍睹。

順便，再和人類對比一下，三階魔方最少步數的世界比賽中，人族的最好成績是22步。

如此看來，DeepCube堪稱魔方全能小王子。

殊途同歸

我們一直強調說，這個魔方AI，不依賴任何人類經驗。

但是，從最後的結果看，DeepCube也和人類選手類似，學到了一些「套路」，包括用複雜的排列組合來解魔方，以及與人類速擰選手相近的策略。

比如，DeepCube大量使用一組特定的操作，即aba-1。就是先執行某個轉動a，再執行另外一個轉動b，最後把a步驟轉回去。

團隊檢查了DeepCube處理640個完全打亂的魔方時，發現AI經常使用這樣的操作，這樣能在移動某些方格的過程中，讓其他方格不要受到影響。具體來說，就是查看每三次相鄰的轉動，出現頻次最高的14種，都是aba-1格式。比其他格式的出現頻率明顯要高。

至於現在嘛，團隊可能覺得，自家的AI復原三階魔方已經百發百中了，於是就開始研究四階魔方，以及各種奇奇怪怪的魔方。

團隊可能覺得，自家的AI復原三階魔方已經百發百中了，於是就開始研究四階魔方，以及各種奇奇怪怪的魔方。

另外，走出魔方的世界，他們覺得這種方法也可以用來處理其他組合優化問題，比如預測蛋白質的三級結構。

許多組合優化問題，都可以想成序列決策問題，也就可以用強化學習來解決。

論文

這篇論文已經提交到NIPS，題目是：Solving the Rubiks Cube Without Human Knowledge

傳送門在此：

https://arxiv.org/pdf/1805.07470v1.pdf

OMT

有獎 (嗎) 競猜，那個碎掉魔方的機器人選手，來自哪裡？

在量子位公眾號（ID：QbitAI）對話界面，回復：「魔方」兩個字，答案立刻揭曉。

— 完 —

歡迎大家關注我們的專欄：量子位 - 知乎專欄

誠摯招聘

量子位正在招募編輯/記者，工作地點在北京中關村。期待有才氣、有熱情的同學加入我們！相關細節，請在量子位公眾號(QbitAI)對話界面，回復「招聘」兩個字。

量子位 QbitAI · 頭條號簽約作者

?? ? 追蹤AI技術和產品新動態

推薦閱讀：