魔方全能小王子降臨:一個完全不依賴人類知識的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

傳送門在此:

arxiv.org/pdf/1805.0747

OMT

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

在量子位公眾號(ID:QbitAI)對話界面,回復:「魔方」兩個字,答案立刻揭曉。

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

誠摯招聘

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

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

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


推薦閱讀:

中國全史百卷本—第027卷 秦漢科技史
嗯?DeepMind給AI們開了個心理實驗室
4· 科技新聞|VR,是一個什麼產物?

TAG:人工智慧 | 強化學習ReinforcementLearning | 科技 |