強化學習演算法DeepCube，機器自行解決複雜魔方問題

2020 年 10 月 30 日
AI

譯者：AI研習社（季一帆）

雙語原文鏈接：//www.yanxishe.com/TextTranslation/2719

前瞻

我花了近一年的時間寫《動手深度強化學習》一書，距離該書出版已經過去半年了，在這段休整時間，我發現自己對強化學習的熱情已經無法退卻。無論是研究不同的RL方法，或是復現論文程式碼，對我而言是極大的樂趣。幸運的是，RL在各個領域均在迅速發展，很多有趣的主題值得探討。

引言

多數人對深度強化學習的認識主要集中在應用DRL進行遊戲，這並不意外，因為Deep Mind在2015年首次應用DRL進行Atari系列遊戲，並大獲成功。

事實證明，Atari系列套件與RL的結合簡直是天作之合，即使是現在，許多研究論文仍使用該套件來驗證自己的方法。隨著RL的發展，經典的53種Atari遊戲的挑戰性越來越小（在撰寫本文時，RL在一半以上的遊戲表現超過人類），所以，現在的一些研究轉向更複雜的遊戲，例如StarCraft和Dota2。

由於上述原因，會給人一種錯覺，即「 RL是用來玩遊戲的」，事實顯然不是這樣。在我2018年6月出版的書中，我不僅介紹了RL在Atari遊戲的應用，也介紹了其他領域的不同示例，包括股票交易（第8章），聊天機器人和NLP（第12章），自動駕駛（第13章），持續控制（第14-16章））和棋盤遊戲（第18章）。

實際上，基於MDP的RL可以用於各種不同的領域，電腦遊戲只是關於複雜決策的一個簡易且關注度高的領域。

在本文中，我將詳細介紹將RL應用於組合優化領域的最新研究工作。本文對UCI（加利福尼亞大學歐文分校）的研究人員發表的論文「Solving the Rubik』s Cube Without Human Knowledge」進行解讀。除了論文解讀之外，我還使用PyTorch復現了論文，通過訓練模型和流程解讀實驗，並對論文方法進行改進。

下文我將結合程式碼對論文的方法進行介紹，以加深對相關概念的理解。如果你只對理論方法感興趣，可以跳過程式碼部分。

OK，現在開始吧！

Rubik魔方和組合優化問題

我估計每個人都知道魔方是什麼，所以我就不做過多魔方介紹了，而是將這部分的重點放在它與數學和電腦科學的聯繫。如非特殊說明，本文中的「立方體」是指3×3經典魔方。除了3×3經典魔方，還有其他一些變體魔方，但3×3經典魔方至今仍是最受歡迎的。

雖然看起來Rubik的3×3模型似乎非常簡單，但考慮到各種可能的旋轉轉換，這其實非常棘手。據計算，3×3經典魔方旋轉狀態總共有4.33 × 10¹⁹種不同狀態。如果考慮一些魔方拼接出錯的情況，即模仿無法通過旋轉復原，只有拆解重新進行合理的拼接，那麼總狀態增加約12倍（≈5.19×10²⁰）。

所有狀態都可以通過各種旋轉組合得到。例如，在某種狀態下順時針旋轉魔方左側，就會達到一種新的狀態，從該狀態逆時針旋轉同一側就會回到原始狀態。另外，如果連續三次旋轉魔方左側，則回到原始狀態的最短路徑是再將魔方左側順時針旋轉一次，而不是逆時針旋轉三次（雖然這樣也可以，但卻不是最佳的）。

由於3×3魔方有6個面，並每個面可以沿兩個方向旋轉，因此總共有12種旋轉方式。當然，直接旋轉半圈（在同一方向上連續兩次旋轉）也是可以的，但為簡單起見，我們將其視為兩次旋轉。

數學中，有一些領域專門研究這樣的對象，最典型的便是抽象代數。抽象代數是數學研究的一個重要方向，也是現代電腦理論基礎之一，主要研究抽象對象集及其代數操作。根據抽象代數，Rubik魔方是一個非常複雜的『群』，有許多有趣的屬性。

但是魔方不只是簡單的狀態和變換，它還是不確定的，其主要目標是找到一個可以復原魔方的旋轉序列。這樣的問題可以通過組合優化進行研究，組合優化也是應用數學和理論電腦科學的一個典型子領域。該領域包含許多有價值的典型問題，例如：

旅行商問題：在圖中找到最短的路徑；
蛋白質摺疊模擬：尋找蛋白質的3D結構；
資源分配：通過在消費者之間分配固定的資源，以獲得最佳目標。

還有其他一些類似的問題。這些問題的共同之處在於狀態空間特別大，從而導致通過遍歷所有可能組合以找到最佳解決方案是不可行的。Rubik魔方也屬於這類問題，該問題狀態空間為4.33×10¹⁹，想要通過蠻力求解幾乎不可能。

最優化與『上帝之數』

使組合優化問題變得棘手的原因是，儘管我們非常清楚該怎樣達到問題的目標狀態，但實際上我們並沒有很好的解決方案。魔方問題尤其如此：在發明魔方之後，就確定了通過12種旋轉可以達到目標狀態，但Ernő Rubik花了大約一個月的時間才找到一種復原方法。如今，有了許多不同的魔方復原方法，包括入門方法、Jessica Fridrich方法和許多其他方法。

所有這些方法差異巨大。例如，入門方法需要記住5-7種旋轉序列旋轉大約100次才能還原魔方。與之形成對比的是，當前三階魔方還原的世界紀錄是4.22秒，這需要更少的步驟，但也要求挑戰者需要記憶和訓練大量的旋轉序列。Jessica Fridrich方法平均約需55個動作，但需要熟悉大約120個動作序列。

但是，最大的問題是：給定任意狀態的三階魔方，其還原最短動作序列是什麼？十分遺憾，儘管三階魔方已經有54年的歷史了，這個問題依然沒有答案。只有在2010年，Google的研究小組證明，解決任何魔方狀態所需的最小移動量為20，該數字也稱為『上帝之數』。當然，這只是一個平均數字，最佳解決方案可能要短一些，也就是說，復原很多魔方平均需要20步移動，但某個狀態可能不需要任何移動（已復原狀態）。

但是，上述研究僅證明了最少平均移動量，卻沒有找到實際的解決方案。如何找到任何給定狀態的最優解仍然是一個懸而未決的問題。

魔方復原的方法

在該論文之前，魔方復原問題主要有兩個研究方向：

使用群論方法，顯著減小要搜索的狀態空間。這種方法種最典型的包括Kociemba演算法；
使用蠻力搜索以及人工定義的啟發式搜索，使搜索指向最有可能的方向。典型的如Korth演算法，該演算法使用A *搜索和大型模式資料庫避免選擇錯誤的方向。

本文介紹了第三種方法：通過在海量不同狀態的魔方數據集上訓練神經網路，獲得求解狀態方向的策略。該訓練不需要提供任何先驗知識，僅需要魔方數據集（不是物理魔方，而是電腦模型）。這是其與上述兩種方法的最大不同：前兩種方法需要大量的領域知識，並以電腦編碼進行定義。

後續章節是新的論文方法的詳細介紹。

數據表示

我們從數據表示開始介紹。在三階魔方問題中，我們首先對動作和狀態以某種方式進行編碼。

動作

此處的動作是指魔方在任何狀態下可能的旋轉，前文已經說過，我們總共只有12個動作。對於3階魔方，共有左，右，上，下，前和後六個側面可以旋轉。而對每一面，有兩種不同的操作，即該側的順時針和逆時針旋轉（90°或–90°）。一個很小但非常重要的細節是，當需要旋轉的面朝向你時，你能方便的進行操作。例如，你可以哦容易的旋轉正面，但對於背面而言，總是有些不太習慣。

根據上述說明，動作名稱可以根部不同側面的首字母做出以下定義。如右側的順時針旋轉命名為R；至於逆時針的動作，可能會使用不同的符號，包括R’/r/r̃。第一種和最後一種表示法對於電腦程式碼而言不太友好，因此我使用了小寫字母來表示動作的逆時針旋轉。這樣，右側面的兩個動作是R和r，左側面的兩個動作為L和l，依此類推。

在我的程式碼中，動作空間是通過python枚舉實現的，其中每個動作映射為唯一的整數。

狀態

狀態是指三階魔方當前的排列組合方式，正如前文介紹的，該狀態空間極其龐大（4.33×10¹⁹個不同狀態）。但除了要面對海量的狀態，我們在選擇特定的狀態表示形式時，還要考慮到以下這些要求：

避免冗餘：在極端情況下，我們可以通過記錄每側每個貼紙的顏色來表示魔方的狀態。但是，如果你計算一下這些組合的數量，會發現它等於6⁶*⁸=6⁴⁸≈2.25×10³⁷，遠遠大於三階魔方的狀態空間大小，這意味著這種表示形式是高度冗餘的，例如，魔方兩側中心對稱的情況。至於為什麼得到6⁶*⁸，很簡單：三階魔方有6個面，每個面除了中心塊外有8個小立方體，所以總共有48個貼面，每個貼面可用6種顏色之一上色。
記憶體效率：在後續的訓練和模型應用過程中，我們需要將大量魔方集的不同狀態保存在記憶體中，這可能會影響流程效率。因此，我們希望表示形式儘可能緊湊。
轉換性能：另一方面，我們需要對某一狀態進行所有可能的旋轉操作，並且要求這些操作快速完成。如果在記憶體中的狀態表示非常緊湊（例如使用位編碼），這會導致魔方側面的每一次旋轉需要進行冗長的解壓縮過程，嚴重影響訓練速度。
適宜的神經網路：就像其他機器學習、深度學習實例中那樣，並非每個數據表示都符合神經網路的輸入格式。在NLP中通常使用字元或單詞嵌入，在CV中將影像從jpeg解碼為原始像素，Random Forests則需要對數據進行大量特徵設計等。

在本文中，使用獨熱編碼將三階魔方的每個狀態表示為20×24張量。接下來以下圖為例，對這種表示方式進行說明。

將魔方中需要關注的面標為白色

上圖中，我們用白色標記了我們需要關注的魔方模組，其餘部分（藍色）是冗餘的，不需過多關注。我們都知道，3×3魔方由三種類型的模組組成：8個三色的角塊，12個兩色的側邊塊和6個單色的中心塊。

雖然不太明顯，但實際上根本不需要過多關注中心塊，因為它們不能更改其相對位置，只能整體旋轉。因此，對於中心塊，我們只需就其位置達成一致就可以。例如，在我的實現中，白色面總是在頂部，前面是紅色，左邊是綠色，依此類推。這使得數據集狀態的部分固定，意味著將魔方上所有可能的旋轉被視為同一狀態。

由於無需關注中心塊，所以在上圖中所有中心塊都是藍色。那其餘藍色是怎麼回事呢？這是因為每種特殊的立方模組（角塊或側變塊）的顏色組合都是固定的。例如，根據上述對魔方前後左右各方向的定義（頂部為白色，紅色為正面等等），左上角塊一定是綠色、白色和紅色，其他立體塊不會有這三種顏色的組合。側邊塊也是如此。

因此，要找到某個特定模組的位置，我們只需要知道其某個面的位置即可。一般來說，你可以在側邊塊或角塊選擇一個面進行跟蹤關注，但是一旦選定，就要堅持下去。如上圖所示，我們選擇在頂部跟蹤八個立方塊貼面，從底部跟蹤八個貼面，以及四個側邊塊貼面，兩個在正面，兩個在背面。這樣，我們需要跟蹤關注的總計有20個貼面。

那麼，張量維度中的「 24」是從哪裡來的？我們總共要跟蹤20種不同的貼面，但是由於魔方旋轉，它們可能出現在不同的位置，至於具體位置，這取決於要跟蹤的立體塊的類型。以角塊開始說明，我們總共有8個角塊，旋轉魔方可以按任何順序對它們進行重新排列。因此，任何一個角塊都可能出現在8個角中的任何一個位置。此外，每個角塊也可以旋轉，例如，這會使「綠色、白色、紅色」對應的角塊有以下三種可能的方向：

白色在頂部，綠色在左面，紅色在前面；
綠色在頂部，紅色在左面，白色在前面；
紅色在頂部，白色在左面，綠色在前面；

因此，為精確表示角塊的位置和方向，我們得到8×3=24種不同的組合。

至於12個側面塊，由於它們只有兩個貼面，因此只能有兩個方向。也得到24種組合，只不過是通過12×2=24計算得到的。最後，我們要跟蹤20個立方塊，8個角塊和12個側邊塊，每個立方塊有24個可能的位置。

獨熱編碼是指當前對象的位置為1且其他位置為0，該編碼可以輸入神經網路進行處理。因此，本文中狀態的最終表示形式為20×24的張量。

考慮到冗餘情況，這種表示方式非常接近總狀態空間，其可能的組合數量為24²⁰≈4.02×10²⁷。雖然它仍遠大於魔方的狀態空間，但是這種方式要比比對每個貼面的所有顏色進行編碼要好得多。冗餘得原因是魔方旋轉自身得屬性，如不可能只旋轉一個角塊或是一個側邊塊，每次旋轉總是會轉一個面。

好了，數學知識就介紹這麼多，如果你想了解更多，推薦Alexander Frey和David Singmaster撰寫的著作「Handbook of Cubic Math」。

細心的讀者可能會注意到，這樣的魔方狀態的張量表示有一個重大缺點：記憶體效率低下。實際上，如果將狀態表示為20×24的浮點張量，我們浪費了4×20×24=1920位元組的記憶體，考慮到在訓練過程中需要表示數千種狀態，這會導致數百萬位元組記憶體的損耗。為了克服這個問題，在本文的實現中，我使用兩種表示形式：一種是張量，用做神經網路輸入；另一種是更緊湊的表示形式，以便更長久地存儲不同的狀態。我們將這種緊湊狀態保存為一系列列表，根據角塊和側邊面的排列及其方向進行編碼。這種表示方式不僅具有更高的記憶體效率（160位元組），而且使魔方的轉換也更加方便。

更多細節參見該模組，緊湊狀態見函數namedtuple，神經網路張量表示見函數encode_inplace。

訓練過程

現在我們已經知道了三階魔方的狀態是如何以20×24張量編碼的，下面我會介紹本文使用的神經網路結構及其訓練方法。

神經網路結構

下圖是神經網路結構（取自原論文）：

該神經網路將魔方狀態的20×24張量表示作為輸入，併產生兩個輸出：

策略。由12個數字組成，表示行動的概率分布；
值。使用一個標量表示對狀態的評估，具體含義見下文。

在輸入和輸出之間，神經網路由若干ELU激活函數的全連接層。在我的程式碼實現中，網路結構與此處並無差異，詳見此處。

訓練

可以看到，網路非常簡單：策略告訴我們對當前狀態進行何種轉換，值用於評價狀態的好壞程度。那麼，最大的問題就是：如何訓練網路？

論文提出的訓練方法是「 Auto-Didactic Iterations」（簡稱「 ADI」），該方法也簡潔明了。從目標狀態（復原的魔方）開始，執行一些預定義的長度為N的隨機變換序列（文中給出了N個狀態的序列）。對序列中的每個狀態，一次執行以下過程：

將所有可能的變換（總共12個）應用於狀態s；
將這12個狀態傳遞給當前的神經網路，以輸出值。這樣就得到s的12個子狀態的值；
根據vᵢ = maxₐ(v(sᵢ,a)+R(A(sᵢ,a)))計算狀態的目標值，其中A(s, a)是對s執行動作a之後的新狀態；如果s是目標狀態，則R(s)為1，否則為0；
狀態s的目標策略使用相同的公式進行計算，不同的是我們選擇最大值，即pᵢ = argmaxₐ (v(sᵢ,a)+R(A(sᵢ,a)))。這僅意味著目標策略只有在最大值的子狀態時取值為1，否則為0。

具體過程見下圖。生成序列為x₀，x₁…，以魔方xᵢ為例進行詳細說明，對狀態xᵢ，通過上述公式確定策略和值目標。

通過該過程，我們可以生成任意數量的訓練數據。

模型應用

假設我們已經通過上述過程訓練得到模型，那麼如何使用模型來複原魔方呢？根據網路結構，我們很容易想到這樣的方法（但不幸的是該方法並不可行）：

向模型提供要解決的三階魔方的當前狀態；
根據策略選擇最大可能的動作（或從結果分布中取樣）；
對模型執行該動作；
重複上述過程，知道魔方復原。

看上去這樣是可以奏效的，但是在實踐中，這樣的方法卻行不通。主要原因是模型品質不過關。由於狀態空間巨大，加上神經網路特性，對於所有輸入狀態，不可能經過訓練使得NN返回準確的最佳動作。也就是說，模型並沒有告訴我們明確的求解思路，只是向我們提出值得探索的方向，但這些方向可能使我們更接近解決方案，也有可能會引起誤導。因為在訓練過程中，不可能處理所有可能狀態。要知道，即使使用GPU以每秒處理數十萬狀態的速度進行訓練，對於4.33×10¹⁹的狀態空間，也需要經過一個月的訓練時間。因此，在訓練中我們只取狀態空間的一小部分，大約為0.0000005％，這就要求我們使用更複雜的方法。

有一種非常適用的方法，即「蒙特卡洛樹搜索」，簡稱MCTS。該方法有很多變體，但總體思路很簡單，可以與眾所周知的蠻力搜索方法（如「廣度優先搜索BFS」或「深度優先搜索DFS」）對比來進行說明。在BFS和DFS中，我們嘗試所有可能的動作，並探索通過這些動作獲得的所有狀態對狀態空間進行詳盡搜索。可以發現，這種方式是上述過程的另一個極端。

MCTS在這兩種極端之間進行折衷：我們想要執行搜索，並且存在一些值得關注的資訊，但是，某些情況下資訊可能是不可靠的雜訊或錯誤，有時資訊也可能提供正確的方向，從而加快搜索過程。

正如上文提到的，MCTS是一類方法，不同方法在具體細節和特徵方面有所不同，本文使用的是UCT方法（Upper Confidence bound1 applied to Trees）。該方法在樹上操作，其中節點是狀態，邊是動作，將所有狀態聯繫起來。在多數情況下，整個樹是非常巨大的，因此我們不會試圖構建整個樹，只是構建其中的一小部分。首先，讓我們從一棵由單個節點組成的樹開始，也就是我們的當前狀態。

每執行一步MCTS，都要沿著樹探索某些路徑，一般可以面對以下兩種選擇：

當前節點是葉節點；
當前節點在樹的中間，並具有子節點。

對於葉節點，通過對狀態執行所有可能的動作對其進行「擴展」，並檢查所有結果狀態是否為目標狀態（如果找到了魔方復原的目標狀態，則搜索完成）。然後，將葉節點狀態傳遞給模型，輸出值和策略，將其存儲備用。

如果當前節點不是葉節點，那麼我們能夠知道該節點的子節點（可到達狀態），並從網路獲得值和策略輸出。因此，我們需要決定選擇哪條路徑（換句話說，探索哪種行動最優）。這一決定極其重要，甚至稱得上是強化學習方法的基石，即「探索-利用問題」。一方面，神經網路的策略告訴我們該怎麼做，另一方面，對於策略出錯的情況，可以通過探索周圍的狀態來解決。但由於狀態空間巨大，不能一直探索，這就要求我們在這兩者之間保持平衡，這直接影響著搜索性能和結果。

為解決這個問題，對於每個狀態，我們為每個可能的動作（共12個）設置計數器，每次在搜索過程中選擇某一動作，相應計數器就會增加。在決定採取特定動作時，可以通過計數器進行判定，即某一動作的執行次數越多，將來選擇的可能性就越小。

此外，模型返回的值也用於輔助決策，即從當前狀態的值及其子節點狀態的值中選擇最大值進行跟蹤。根據這樣的模型，可以從父節點的狀態找到最可能的路徑。

總而言之，對於非葉節點狀態，通過以下公式選擇要執行的動作：

其中，N(s,a)是狀態s選擇動作a的次數，P(s,a)是模型為狀態s返回的策略，W(s,a)是模型根據狀態s的分支a下所有子節點狀態返回的最大值。

重複此過程，直到找到解決方案或時間耗盡。為加快此過程，MCTS通常以並行方式進行，利用多個執行緒同時執行多個搜索。在這種情況下，可以從A(t)中減去一些額外損失，以防止多個執行緒探索相同路徑。

為使用MCTS樹得到復原方案，論文作者提出兩種方法：

naïve：得到目標狀態後，使用從根狀態開始的路徑作為復原方案；
BFS方法：得到目標狀態後，對MCTS樹執行BFS，以找到從根到此狀態的最短路徑。

論文提到，第二種方法找到的復原方案比第一種方案更短，這並不奇怪，因為MCTS過程的隨機性，在第一種復原方案路徑中可能引入了無用的循環。

論文結果

論文的結果令人印象深刻。在使用三個GPU並行訓練了44小時之後，網路學會了類似甚至超過人工復原魔方的方案。最終，將本文模型DeepCube已與先前介紹的兩種求解方法進行了比較，分別是Kociemba two-staged solver 和Korf IDA*。

為驗證本文方法的效率，論文使用640個隨機打亂的魔方對不同方法分別進行測試，並設置最大求解步驟為1000步，最大求解時間為1小時，實現發現DeepCube和Kociemba方法均能在限制步驟和時間內復原魔方。具體而言，Kociemba求解速度非常快，其中值僅為一秒鐘，但是由於依賴人工定義規則，其求解並不總是最短的。DeepCube方法花費了更多的時間，中值約為10分鐘，但在55％的情況，該方法會比Kociemba得到更好的復原方案，即更少的步驟。從我個人的角度來看，55％雖然不足以說NN明顯更好，但至少證明該方法還不錯。下圖（摘自論文）顯示了所有求解方法的復原步數分布。可以看到，由於復原時間較長，在1000步魔方復原測試中沒有比較Korf求解方法，但為了將DeepCube與Korf求解方法的性能進行比較，論文進一步設計了更容易的15步魔方復原測試集。

實現細節

好的，現在我們開始介紹程式碼實現。在本部分中，我將簡要介紹程式碼方案及一些關鍵設計，但在此之前，我還是要先強調一些事情：

我不是該項目的研究人員，因此這段程式碼只是想要復現論文的方法。但不幸的是，由於論文沒有提供確切的超參數資訊，因此我進行了大量猜測和試驗，但實現結果與論文的結果依然存在較大差異。
同時，我試圖以通用方式實施所有操作來簡化實驗。例如，有關魔方狀態和轉換的詳細資訊不做詳細展示，僅僅通過添加一個新模組來抽象化3×3魔方問題。在我的程式碼中，分別對2×2魔方和3×3魔方進行實驗，但類似這樣有固定可預測動作集的、環境完全可見的問題都可以通過這樣的方式進行解決。下一節會做詳細說明。
相比程式碼性能，我更關注程式碼的可讀性與簡潔性，當然，對於不引入過多複雜性與成本消耗就能提高模型性能的操作，我在程式碼中還是保留了它們。例如，僅通過分割魔方數據集和正向網路傳遞，就可以將訓練過程加快5倍。但是，如果需要將大多數內容重構為多GPU和多執行緒模式，我為簡單起見就沒有這樣做。典型的就是MCTS進程，通常採用多執行緒程式碼實現，加快模型速度，但這就需要處理進程之間的同步問題。我沒考慮那麼多，只是以串列方式進行MCTS，僅對批量搜索進行了簡單優化。

綜上，我的程式碼由以下幾部分組成：

魔方環境，用於定義觀察/狀態空間、可能的動作以及網路狀態的表示，見libcube / cubes模組；
神經網路，包括要訓練的模型、訓練樣本的生成和循環訓練過程。見the training tool和libcube / model.py模組；
魔方復原方法, 見the solver tool和libcube/mcts.py；
其他一些不同組件，例如超參數的配置文件和魔方數據生成文件等。

魔方環境

正如前文介紹的，組合優化可不是個小問題，而且種類繁多，即使單就魔方而言，也包含數十種變體，包括2x2x2、3x3x3和4x4x4Rubick魔方，以及Square-1，Pyraminx等。本文介紹的方法不依賴於預定義的領域知識、動作集和狀態空間大小，具有較強的適用性。具體而言，求解魔方問題基於以下假設：

環境狀態必須是完全可觀察的，根據觀察結果可以區分不同狀態。在魔方問題中，我們可以觀察到魔方所有面的狀態，因此該問題符合我們的假設。但對於類似撲克牌這樣的問題，我們是看不到對手的牌的，本文方法就不再適用了。
動作的數量是離散且有限的。在魔方復原問題中，我們只需執行12中動作，這符合假設。但是對操作空間是「旋轉角度α∈[-120°…+ 120°]」這樣的非離散動作的問題，就需要不同的處理方法了。
環境的準確建模。換句話說，我們要能夠回答以下問題：「對狀態s採取行動a會產生什麼結果？」。如果無法解決這樣的問題，ADI和MCTS方法都會失效。這個要求對於實現模型是及其必要的。然而，對於大多數問題，並不存在這樣的模型，或者模型的輸出非常嘈雜，但在象棋或圍棋之類的遊戲中，遊戲規則即是這樣的符合要求的模型。
領域確定性。即對相同狀態的相同動作會得到相同的最終狀態。不過我覺得，即使採取隨機行動也應該會起作用，但也不一定。

為了使我們的方法可以很方便的遷移到非3×3魔方的問題，我將所有具體的環境資訊都移到了一個單獨模組，並通過抽象介面CubeEnv與其餘程式碼進行聯繫（見此處）。通過這樣的方式，每個環境都有一個名稱，指定環境名稱即可使用相應的的環境類型。目前，我們定義了兩種不同的環境：經典三階魔方cube3x3和二階魔方cube2x2。

如果你要使用自己的魔方數據或其他不同的環境，只需要修改該模組，通過介面即可在其它程式碼中使用你自定義的環境。

訓練

模型訓練過程見train.py和libcube/model.py。為簡化實驗，同時增強實驗的可重複性，在單獨的ini文件中設置訓練的所有參數，包括：

要使用的環境的名稱，我們提供了cube2x2和cube3x3兩個環境；
運行名稱，在TensorBoard的名稱和目錄中顯示，並用於保存模型；
ADI的目標值計算方法。本程式碼提供兩種計算方式：一種是原論文的方法，另一種是我改進的方法。實驗表明，我的改進方法收斂更加穩定；
訓練參數，包括batch、是否使用CUDA、學習率、LR衰減等。

可以在ini文件夾查看我的實驗設置。訓練過程中，TensorBoard參數被寫入runs文件夾，並將最優模型保存到saves文件。

搜索過程

訓練的結果是一個帶有網路權重的模型文件。根據模型可以使用MCTS方法復原魔方，具體實現見solver.py和libcube/mcts.py模組。

其中，求解器可用於不同模式：

復原一個雜亂魔方。該魔方由一系列由逗號分隔的動作索引打亂，該序列由-p選項傳遞。例如，-p 1,6,1是依次執行第二個動作、第七個動作、第二個動作來打亂魔方。動作執行是面向特定環境的，通過-e選項傳遞，在魔方環境模組可以找到帶有索引的動作。例如，2×2魔方的動作1,6,1分別表示L，R’，L變換。
從文本文件（每行代表一個魔方數據）讀取排列並進行復原。文件名通過-i選項傳遞。我在cubes_tests文件夾提供了幾個示例，此外，你還可以使用gen_cubes.py生成自己的數據集。
生成更多步驟的打亂魔方並進行復原。
執行複雜的系列打亂測試，並對其復原，然後將結果寫入csv文件。通過-o選項可以啟用此模式，這可用於評估模型的品質，但同時也需要花費更多的時間。一旦選擇該選項，就會生成測試結果圖。

在所有情況下，都需要使用-e選項來傳遞環境名稱，並使用-m選項傳遞模型文件。此外，還有其他參數可以調整MCTS、時間或搜索步長等，在此不做過多贅述。

實驗結果

一開始我已經說過，我不是論文的研究人員，因此本工作僅僅是復現論文並進行簡單實驗。但是，原論文沒有提供相關方法的詳細資訊，例如超參數，在訓練過程中對魔方打亂的步數，收斂性等等。為獲取這些資訊，我已向論文作者發送了一封電子郵件，但至今未收到他們的回復。

因此，我進行大量的實驗，但實驗結果與論文結果仍存在較大差異。首先，原始方法的收斂非常不穩定，即使降低學習率和增大batch，訓練依然不穩定，值損失呈指數增長，如下圖所示。

經過多次實驗，我認為導致這種現象的原因是原始方法中值目標是錯誤的。

確實如此，在公式vᵢ = maxₐ(v(s, a) + R(A(s, a)))中，網路返回的值v(s,a)總是與實際獎勵R(s)相加，即使對目標狀態也是這樣。這樣，網路返回的實際值可以是-100、10⁶或3.1415。這樣大的差異對神經網路極不友好，尤其是MSE值目標。

為此，我做了以下修改，將目標狀態值設為0：

具體而言，指定參數value_targets_method = zero_goal_value而不是默認的value_targets_method = paper，你可以在ini文件中選擇該新的目標函數。

通過這種簡單修改，訓練過程模型可以更快地收斂穩定狀態，見下圖。

二階魔方

原論文中，使用三個Titan XP GPU並行訓練了44小時，在這個過程中，模型總計看過約80億魔方狀態。根據這樣的敘述，可以得到訓練速度約等於每秒查看50000魔方狀態。我的實現在單個GTX 1080Ti上進行，其訓練速度為15000/秒，與論文差別不大。因此，使用論文的數據，在單個GPU上訓練一次大概需要6天時間，這使得實驗和超參數調整及其困難。

為解決這個問題，我設置了簡單的2×2魔方環境，只需一個小時的訓練時間。如果你也想繼續復現，可參見repo中的兩個ini文件：

cube2x2-paper-d200.ini：使用原論文中的值目標方法；
cube2x2-zero-goal-d200.ini：改進的0值目標計算方法。

在這兩種配置中，狀態批次均為10k，魔方打亂步驟為200，其他訓練參數也相同。

分別進行訓練後，生成了兩個模型（模型文件）：

原論文方法的損失為0.18184；
改進0值方法的損失為0.014547。

實驗表明，模型損失越小，成功率越高，可用於復原更多打亂步驟的魔方。兩種模型的實驗結果如圖所示。

接下來對魔方復原過程中的MCTS步驟進行對比。如下圖所示，改進的0目標模型通常以更少的步驟復原魔方，也就是說，該模型學到更優的復原策略。

最後，比較不同魔方復原方法的長度。下圖繪製了naïve和BFS方案的長度。從圖中可以看出，naïve方法的長度要比BFS長約10倍，這表明調整MCTS參數可以改善模型性能。同時還可以發現，「零目標」模型的解決方案比原論文模型更長，其原因可能是前一種方法不存在更長的復原路徑。

三階魔方

3×3魔方的模型訓練過程要複雜的多，所以在這裡僅進行簡單介紹。但即使只是簡單的實驗，也表明0值目標函數可以極大地提高訓練穩定性和模型品質。另外，三階魔方訓練一次大約需要20個小時，想要進行大量實驗需要花費很多時間和耐心。

正是由於上述原因，我的實驗結果不如論文所示結果，我得到的最佳模型僅解決12-15步的亂序魔方復原問題，對於更複雜的問題則無能為力。如果你想獲得更好的效果，可能使用更多CPU內核+並行MCTS來提升模型性能。為了獲得數據，我將搜索過程限制在10分鐘內，並對每個亂序干擾生成五個隨機干擾。

下圖是論文方法與改進的零目標值方法的比較。

下圖所示為找到的最佳解決方案的長度。圖示表明兩點：第一，在10-15干擾深度範圍內，「零目標」方法求解長度大於論文的，這意味著模型雖然沒有找到生成測試數據的干擾序列，但發現了更長其他解決方法；第二，對於12-18深度範圍，原論文方法找到比干擾序列更短的解決方案，可能的原因是生成了簡併測試序列。

進一步的改進和實驗

針對上述研究，有許多其他方法可提升模型性能，改進實驗結果。比如：

更詳細的輸入和更複雜的神經網路。由於魔方問題非常複雜，僅僅通過簡單的前饋神經網路並不能獲得最佳模型，考慮卷積網路可能會提升模型的學習能力；
訓練期間的振蕩和不穩定性在RL問題中十分常見，這可能是步間相關性導致的。通常的解決方法是，在使用策略網路學習引導值時引入目標網路；
引入臨時緩衝區可提高訓練速度；
實驗表明，樣本加權（與擾亂深度成反比）有助於獲得更好的策略，該策略知道如何解決擾亂魔方問題，但這也可能使對更深狀態的學習過程變慢。為此，可以使用自適應權重，以減少其在後續訓練階段的影響；
在訓練過程中使用熵損失來正則化學習策略；
2×2魔方的訓練模型沒有考慮到魔方問題中存在的不動中間塊，因此整個二階魔方都可以旋轉。由於二階魔方的狀態空間很小，所以無需考慮冗餘的相同狀態，但對於4×4魔方來說，去冗餘至關重要；
多次實驗尋找更好的訓練參數和MCTS參數。

感謝你的閱讀，期待你的評論！本文的PDF文件可從此處下載。

AI研習社是AI學術青年和AI開發者技術交流的在線社區。我們與高校、學術機構和產業界合作，通過提供學習、實戰和求職服務，為AI學術青年和開發者的交流互助和職業發展打造一站式平台，致力成為中國最大的科技創新人才聚集地。

如果，你也是位熱愛分享的AI愛好者。歡迎與譯站一起，學習新知，分享成長。