魔慄少女 發自 凹非寺
小時候，感覺大家都在玩魔方。
我也買了一個，費盡腦細胞才拼出一層。然後，就沒有然後了……
後來遇到會玩魔方的小夥伴，我總是忍不住仰慕一下他的操作。
但是沒想到，有一天，我還能遇到一個會玩魔方的人工智能。
最近，加州大學歐文分校的一個研究小組，發佈了基於強化學習的魔方復原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 Rubik’s Cube Without Human Knowledge
傳送門在此：
https://arxiv.org/pdf/1805.07470v1.pdf
OMT
有獎 (嗎) 競猜，那個碎掉魔方的機器人選手，來自哪裡？
— 完 —
誠摯招聘
վ'ᴗ' ի 追蹤AI技術和產品新動態
閱讀更多 量子位 的文章
