<mark id="oztn4"></mark>
0
譯者：AI研習社（季一帆）
雙語原文鏈接：https://www.yanxishe.com/TextTranslation/2719
前瞻
我花了近一年的時間寫《動手深度強化學習》一書，距離該書出版已經(jīng)過去半年了，在這段休整時間，我發(fā)現(xiàn)自己對強化學習的熱情已經(jīng)無法退卻。無論是研究不同的RL方法，或是復現(xiàn)論文代碼，對我而言是極大的樂趣。幸運的是，RL在各個領域均在迅速發(fā)展，很多有趣的主題值得探討。
引言
多數(shù)人對深度強化學習的認識主要集中在應用DRL進行游戲，這并不意外，因為Deep Mind在2015年首次應用DRL進行Atari系列游戲，并大獲成功。
事實證明，Atari系列套件與RL的結合簡直是天作之合，即使是現(xiàn)在，許多研究論文仍使用該套件來驗證自己的方法。隨著RL的發(fā)展，經(jīng)典的53種Atari游戲的挑戰(zhàn)性越來越小（在撰寫本文時，RL在一半以上的游戲表現(xiàn)超過人類），所以，現(xiàn)在的一些研究轉向更復雜的游戲，例如StarCraft和Dota2。
由于上述原因，會給人一種錯覺，即“ RL是用來玩游戲的”，事實顯然不是這樣。在我2018年6月出版的書中，我不僅介紹了RL在Atari游戲的應用，也介紹了其他領域的不同示例，包括股票交易（第8章），聊天機器人和NLP（第12章），自動駕駛（第13章），持續(xù)控制（第14-16章） ）和棋盤游戲（第18章）。
實際上，基于MDP的RL可以用于各種不同的領域，計算機游戲只是關于復雜決策的一個簡易且關注度高的領域。
在本文中，我將詳細介紹將RL應用于組合優(yōu)化領域的最新研究工作。本文對UCI（加利福尼亞大學歐文分校）的研究人員發(fā)表的論文“Solving the Rubik’s Cube Without Human Knowledge”進行解讀。除了論文解讀之外，我還使用PyTorch復現(xiàn)了論文，通過訓練模型和流程解讀實驗，并對論文方法進行改進。
下文我將結合代碼對論文的方法進行介紹，以加深對相關概念的理解。如果你只對理論方法感興趣，可以跳過代碼部分。
OK，現(xiàn)在開始吧！
我估計每個人都知道魔方是什么，所以我就不做過多魔方介紹了，而是將這部分的重點放在它與數(shù)學和計算機科學的聯(lián)系。如非特殊說明，本文中的“立方體”是指3x3經(jīng)典魔方。除了3x3經(jīng)典魔方，還有其他一些變體魔方，但3x3經(jīng)典魔方至今仍是最受歡迎的。
雖然看起來Rubik的3x3模型似乎非常簡單，但考慮到各種可能的旋轉轉換，這其實非常棘手。據(jù)計算，3x3經(jīng)典魔方旋轉狀態(tài)總共有4.33 × 101?種不同狀態(tài)。如果考慮一些魔方拼接出錯的情況，即模仿無法通過旋轉復原，只有拆解重新進行合理的拼接，那么總狀態(tài)增加約12倍（≈5.19×102?）。
所有狀態(tài)都可以通過各種旋轉組合得到。例如，在某種狀態(tài)下順時針旋轉魔方左側，就會達到一種新的狀態(tài)，從該狀態(tài)逆時針旋轉同一側就會回到原始狀態(tài)。另外，如果連續(xù)三次旋轉魔方左側，則回到原始狀態(tài)的最短路徑是再將魔方左側順時針旋轉一次，而不是逆時針旋轉三次（雖然這樣也可以，但卻不是最佳的） 。
由于3x3魔方有6個面，并每個面可以沿兩個方向旋轉，因此總共有12種旋轉方式。當然，直接旋轉半圈（在同一方向上連續(xù)兩次旋轉）也是可以的，但為簡單起見，我們將其視為兩次旋轉。
數(shù)學中，有一些領域專門研究這樣的對象，最典型的便是抽象代數(shù)。抽象代數(shù)是數(shù)學研究的一個重要方向，也是現(xiàn)代計算機理論基礎之一，主要研究抽象對象集及其代數(shù)操作。根據(jù)抽象代數(shù)，Rubik魔方是一個非常復雜的‘群’，有許多有趣的屬性。
但是魔方不只是簡單的狀態(tài)和變換，它還是不確定的，其主要目標是找到一個可以復原魔方的旋轉序列。這樣的問題可以通過組合優(yōu)化進行研究，組合優(yōu)化也是應用數(shù)學和理論計算機科學的一個典型子領域。該領域包含許多有價值的典型問題，例如：
旅行商問題：在圖中找到最短的路徑；
蛋白質(zhì)折疊模擬：尋找蛋白質(zhì)的3D結構；
資源分配：通過在消費者之間分配固定的資源，以獲得最佳目標。
還有其他一些類似的問題。這些問題的共同之處在于狀態(tài)空間特別大，從而導致通過遍歷所有可能組合以找到最佳解決方案是不可行的。Rubik魔方也屬于這類問題，該問題狀態(tài)空間為4.33×101?，想要通過蠻力求解幾乎不可能。
使組合優(yōu)化問題變得棘手的原因是，盡管我們非常清楚該怎樣達到問題的目標狀態(tài)，但實際上我們并沒有很好的解決方案。魔方問題尤其如此：在發(fā)明魔方之后，就確定了通過12種旋轉可以達到目標狀態(tài)，但Ern? Rubik花了大約一個月的時間才找到一種復原方法。如今，有了許多不同的魔方復原方法，包括入門方法、Jessica Fridrich方法和許多其他方法。
所有這些方法差異巨大。例如，入門方法需要記住5-7種旋轉序列旋轉大約100次才能還原魔方。與之形成對比的是，當前三階魔方還原的世界紀錄是4.22秒，這需要更少的步驟，但也要求挑戰(zhàn)者需要記憶和訓練大量的旋轉序列。Jessica Fridrich方法平均約需55個動作，但需要熟悉大約120個動作序列。
但是，最大的問題是：給定任意狀態(tài)的三階魔方，其還原最短動作序列是什么？十分遺憾，盡管三階魔方已經(jīng)有54年的歷史了，這個問題依然沒有答案。只有在2010年，Google的研究小組證明，解決任何魔方狀態(tài)所需的最小移動量為20，該數(shù)字也稱為‘上帝之數(shù)’。當然，這只是一個平均數(shù)字，最佳解決方案可能要短一些，也就是說，復原很多魔方平均需要20步移動，但某個狀態(tài)可能不需要任何移動（已復原狀態(tài)）。
但是，上述研究僅證明了最少平均移動量，卻沒有找到實際的解決方案。如何找到任何給定狀態(tài)的最優(yōu)解仍然是一個懸而未決的問題。
在該論文之前，魔方復原問題主要有兩個研究方向：
使用群論方法，顯著減小要搜索的狀態(tài)空間。這種方法種最典型的包括Kociemba算法；
使用蠻力搜索以及人工定義的啟發(fā)式搜索，使搜索指向最有可能的方向。典型的如Korth算法，該算法使用A *搜索和大型模式數(shù)據(jù)庫避免選擇錯誤的方向。
本文介紹了第三種方法：通過在海量不同狀態(tài)的魔方數(shù)據(jù)集上訓練神經(jīng)網(wǎng)絡，獲得求解狀態(tài)方向的策略。該訓練不需要提供任何先驗知識，僅需要魔方數(shù)據(jù)集（不是物理魔方，而是計算機模型）。這是其與上述兩種方法的最大不同：前兩種方法需要大量的領域知識，并以計算機編碼進行定義。
后續(xù)章節(jié)是新的論文方法的詳細介紹。
我們從數(shù)據(jù)表示開始介紹。在三階魔方問題中，我們首先對動作和狀態(tài)以某種方式進行編碼。
此處的動作是指魔方在任何狀態(tài)下可能的旋轉，前文已經(jīng)說過，我們總共只有12個動作。對于3階魔方，共有左，右，上，下，前和后六個側面可以旋轉。而對每一面，有兩種不同的操作，即該側的順時針和逆時針旋轉（90°或–90°）。一個很小但非常重要的細節(jié)是，當需要旋轉的面朝向你時，你能方便的進行操作。例如，你可以哦容易的旋轉正面，但對于背面而言，總是有些不太習慣。
根據(jù)上述說明，動作名稱可以根部不同側面的首字母做出以下定義。如右側的順時針旋轉命名為R；至于逆時針的動作，可能會使用不同的符號，包括R'/r/r?。第一種和最后一種表示法對于計算機代碼而言不太友好，因此我使用了小寫字母來表示動作的逆時針旋轉。這樣，右側面的兩個動作是R和r，左側面的兩個動作為L和l，依此類推。
在我的代碼中，動作空間是通過python枚舉實現(xiàn)的，其中每個動作映射為唯一的整數(shù)。
狀態(tài)是指三階魔方當前的排列組合方式，正如前文介紹的，該狀態(tài)空間極其龐大（4.33×101?個不同狀態(tài)）。但除了要面對海量的狀態(tài)，我們在選擇特定的狀態(tài)表示形式時，還要考慮到以下這些要求：
避免冗余：在極端情況下，我們可以通過記錄每側每個貼紙的顏色來表示魔方的狀態(tài)。但是，如果你計算一下這些組合的數(shù)量，會發(fā)現(xiàn)它等于6?*?=6??≈2.25×103?，遠遠大于三階魔方的狀態(tài)空間大小，這意味著這種表示形式是高度冗余的，例如，魔方兩側中心對稱的情況。至于為什么得到6?*?，很簡單：三階魔方有6個面，每個面除了中心塊外有8個小立方體，所以總共有48個貼面，每個貼面可用6種顏色之一上色。
內(nèi)存效率：在后續(xù)的訓練和模型應用過程中，我們需要將大量魔方集的不同狀態(tài)保存在內(nèi)存中，這可能會影響流程效率。因此，我們希望表示形式盡可能緊湊。
轉換性能：另一方面，我們需要對某一狀態(tài)進行所有可能的旋轉操作，并且要求這些操作快速完成。如果在內(nèi)存中的狀態(tài)表示非常緊湊（例如使用位編碼），這會導致魔方側面的每一次旋轉需要進行冗長的解壓縮過程，嚴重影響訓練速度。
適宜的神經(jīng)網(wǎng)絡：就像其他機器學習、深度學習實例中那樣，并非每個數(shù)據(jù)表示都符合神經(jīng)網(wǎng)絡的輸入格式。在NLP中通常使用字符或單詞嵌入，在CV中將圖像從jpeg解碼為原始像素，Random Forests則需要對數(shù)據(jù)進行大量特征設計等。
在本文中，使用獨熱編碼將三階魔方的每個狀態(tài)表示為20×24張量。接下來以下圖為例，對這種表示方式進行說明。
將魔方中需要關注的面標為白色
上圖中，我們用白色標記了我們需要關注的魔方模塊，其余部分（藍色）是冗余的，不需過多關注。我們都知道，3x3魔方由三種類型的模塊組成：8個三色的角塊，12個兩色的側邊塊和6個單色的中心塊。
雖然不太明顯，但實際上根本不需要過多關注中心塊，因為它們不能更改其相對位置，只能整體旋轉。因此，對于中心塊，我們只需就其位置達成一致就可以。例如，在我的實現(xiàn)中，白色面總是在頂部，前面是紅色，左邊是綠色，依此類推。這使得數(shù)據(jù)集狀態(tài)的部分固定，意味著將魔方上所有可能的旋轉被視為同一狀態(tài)。
由于無需關注中心塊，所以在上圖中所有中心塊都是藍色。那其余藍色是怎么回事呢？這是因為每種特殊的立方模塊（角塊或側變塊）的顏色組合都是固定的。例如，根據(jù)上述對魔方前后左右各方向的定義（頂部為白色，紅色為正面等等），左上角塊一定是綠色、白色和紅色，其他立體塊不會有這三種顏色的組合。 側邊塊也是如此。
因此，要找到某個特定模塊的位置，我們只需要知道其某個面的位置即可。一般來說，你可以在側邊塊或角塊選擇一個面進行跟蹤關注，但是一旦選定，就要堅持下去。如上圖所示，我們選擇在頂部跟蹤八個立方塊貼面，從底部跟蹤八個貼面，以及四個側邊塊貼面，兩個在正面，兩個在背面。這樣，我們需要跟蹤關注的總計有20個貼面。
那么，張量維度中的“ 24”是從哪里來的？我們總共要跟蹤20種不同的貼面，但是由于魔方旋轉，它們可能出現(xiàn)在不同的位置，至于具體位置，這取決于要跟蹤的立體塊的類型。以角塊開始說明，我們總共有8個角塊，旋轉魔方可以按任何順序對它們進行重新排列。因此，任何一個角塊都可能出現(xiàn)在8個角中的任何一個位置。此外，每個角塊也可以旋轉，例如，這會使“綠色、白色、紅色”對應的角塊有以下三種可能的方向：
白色在頂部，綠色在左面，紅色在前面；
綠色在頂部，紅色在左面，白色在前面；
紅色在頂部，白色在左面，綠色在前面；
因此，為精確表示角塊的位置和方向，我們得到8×3=24種不同的組合。
至于12個側面塊，由于它們只有兩個貼面，因此只能有兩個方向。也得到24種組合，只不過是通過12×2=24計算得到的。最后，我們要跟蹤20個立方塊，8個角塊和12個側邊塊，每個立方塊有24個可能的位置。
獨熱編碼是指當前對象的位置為1且其他位置為0，該編碼可以輸入神經(jīng)網(wǎng)絡進行處理。因此，本文中狀態(tài)的最終表示形式為20×24的張量。
考慮到冗余情況，這種表示方式非常接近總狀態(tài)空間，其可能的組合數(shù)量為242?≈4.02×102?。雖然它仍遠大于魔方的狀態(tài)空間，但是這種方式要比比對每個貼面的所有顏色進行編碼要好得多。冗余得原因是魔方旋轉自身得屬性，如不可能只旋轉一個角塊或是一個側邊塊，每次旋轉總是會轉一個面。
好了，數(shù)學知識就介紹這么多，如果你想了解更多，推薦Alexander Frey和David Singmaster撰寫的著作“Handbook of Cubic Math”。
細心的讀者可能會注意到，這樣的魔方狀態(tài)的張量表示有一個重大缺點：內(nèi)存效率低下。實際上，如果將狀態(tài)表示為20×24的浮點張量，我們浪費了4×20×24=1920字節(jié)的內(nèi)存，考慮到在訓練過程中需要表示數(shù)千種狀態(tài)，這會導致數(shù)百萬字節(jié)內(nèi)存的損耗。為了克服這個問題，在本文的實現(xiàn)中，我使用兩種表示形式：一種是張量，用做神經(jīng)網(wǎng)絡輸入；另一種是更緊湊的表示形式，以便更長久地存儲不同的狀態(tài)。我們將這種緊湊狀態(tài)保存為一系列列表，根據(jù)角塊和側邊面的排列及其方向進行編碼。這種表示方式不僅具有更高的內(nèi)存效率（160字節(jié)），而且使魔方的轉換也更加方便。
更多細節(jié)參見該模塊，緊湊狀態(tài)見函數(shù)namedtuple，神經(jīng)網(wǎng)絡張量表示見函數(shù)encode_inplace。
現(xiàn)在我們已經(jīng)知道了三階魔方的狀態(tài)是如何以20×24張量編碼的，下面我會介紹本文使用的神經(jīng)網(wǎng)絡結構及其訓練方法。
下圖是神經(jīng)網(wǎng)絡結構（取自原論文）：
該神經(jīng)網(wǎng)絡將魔方狀態(tài)的20×24張量表示作為輸入，并產(chǎn)生兩個輸出：
策略。由12個數(shù)字組成，表示行動的概率分布；
值。使用一個標量表示對狀態(tài)的評估，具體含義見下文。
在輸入和輸出之間，神經(jīng)網(wǎng)絡由若干ELU激活函數(shù)的全連接層。在我的代碼實現(xiàn)中，網(wǎng)絡結構與此處并無差異，詳見此處。
可以看到，網(wǎng)絡非常簡單：策略告訴我們對當前狀態(tài)進行何種轉換，值用于評價狀態(tài)的好壞程度。那么，最大的問題就是：如何訓練網(wǎng)絡？
論文提出的訓練方法是“ Auto-Didactic Iterations”（簡稱“ ADI”），該方法也簡潔明了。從目標狀態(tài)（復原的魔方）開始，執(zhí)行一些預定義的長度為N的隨機變換序列（文中給出了N個狀態(tài)的序列）。對序列中的每個狀態(tài)，一次執(zhí)行以下過程：
將所有可能的變換（總共12個）應用于狀態(tài)s；
將這12個狀態(tài)傳遞給當前的神經(jīng)網(wǎng)絡，以輸出值。這樣就得到s的12個子狀態(tài)的值；
根據(jù)v? = max?(v(s?,a)+R(A(s?,a)))計算狀態(tài)的目標值，其中A(s, a)是對s執(zhí)行動作a之后的新狀態(tài)；如果s是目標狀態(tài)，則R(s)為1，否則為0；
狀態(tài)s的目標策略使用相同的公式進行計算，不同的是我們選擇最大值，即p? = argmax? (v(s?,a)+R(A(s?,a)))。這僅意味著目標策略只有在最大值的子狀態(tài)時取值為1，否則為0。
具體過程見下圖。生成序列為x?，x?…，以魔方x?為例進行詳細說明，對狀態(tài)x?，通過上述公式確定策略和值目標。
通過該過程，我們可以生成任意數(shù)量的訓練數(shù)據(jù)。
假設我們已經(jīng)通過上述過程訓練得到模型，那么如何使用模型來復原魔方呢？根據(jù)網(wǎng)絡結構，我們很容易想到這樣的方法（但不幸的是該方法并不可行）：
向模型提供要解決的三階魔方的當前狀態(tài)；
根據(jù)策略選擇最大可能的動作（或從結果分布中采樣）；
對模型執(zhí)行該動作；
重復上述過程，知道魔方復原。
看上去這樣是可以奏效的，但是在實踐中，這樣的方法卻行不通。主要原因是模型質(zhì)量不過關。由于狀態(tài)空間巨大，加上神經(jīng)網(wǎng)絡特性，對于所有輸入狀態(tài)，不可能經(jīng)過訓練使得NN返回準確的最佳動作。也就是說，模型并沒有告訴我們明確的求解思路，只是向我們提出值得探索的方向，但這些方向可能使我們更接近解決方案，也有可能會引起誤導。因為在訓練過程中，不可能處理所有可能狀態(tài)。要知道，即使使用GPU以每秒處理數(shù)十萬狀態(tài)的速度進行訓練，對于4.33×101?的狀態(tài)空間，也需要經(jīng)過一個月的訓練時間。因此，在訓練中我們只取狀態(tài)空間的一小部分，大約為0.0000005％，這就要求我們使用更復雜的方法。
有一種非常適用的方法，即“蒙特卡洛樹搜索”，簡稱MCTS。該方法有很多變體，但總體思路很簡單，可以與眾所周知的蠻力搜索方法（如“廣度優(yōu)先搜索BFS”或“深度優(yōu)先搜索DFS”）對比來進行說明。在BFS和DFS中，我們嘗試所有可能的動作，并探索通過這些動作獲得的所有狀態(tài)對狀態(tài)空間進行詳盡搜索。可以發(fā)現(xiàn)，這種方式是上述過程的另一個極端。
MCTS在這兩種極端之間進行折衷：我們想要執(zhí)行搜索，并且存在一些值得關注的信息，但是，某些情況下信息可能是不可靠的噪聲或錯誤，有時信息也可能提供正確的方向，從而加快搜索過程。
正如上文提到的，MCTS是一類方法，不同方法在具體細節(jié)和特征方面有所不同，本文使用的是UCT方法（Upper Confidence bound1 applied to Trees）。該方法在樹上操作，其中節(jié)點是狀態(tài)，邊是動作，將所有狀態(tài)聯(lián)系起來。在多數(shù)情況下，整個樹是非常巨大的，因此我們不會試圖構建整個樹，只是構建其中的一小部分。首先，讓我們從一棵由單個節(jié)點組成的樹開始，也就是我們的當前狀態(tài)。
每執(zhí)行一步MCTS，都要沿著樹探索某些路徑，一般可以面對以下兩種選擇：
當前節(jié)點是葉節(jié)點；
當前節(jié)點在樹的中間，并具有子節(jié)點。
對于葉節(jié)點，通過對狀態(tài)執(zhí)行所有可能的動作對其進行“擴展”，并檢查所有結果狀態(tài)是否為目標狀態(tài)（如果找到了魔方復原的目標狀態(tài)，則搜索完成）。然后，將葉節(jié)點狀態(tài)傳遞給模型，輸出值和策略，將其存儲備用。
如果當前節(jié)點不是葉節(jié)點，那么我們能夠知道該節(jié)點的子節(jié)點（可到達狀態(tài)），并從網(wǎng)絡獲得值和策略輸出。因此，我們需要決定選擇哪條路徑（換句話說，探索哪種行動最優(yōu)）。這一決定極其重要，甚至稱得上是強化學習方法的基石，即“探索-利用問題”。一方面，神經(jīng)網(wǎng)絡的策略告訴我們該怎么做，另一方面，對于策略出錯的情況，可以通過探索周圍的狀態(tài)來解決。但由于狀態(tài)空間巨大，不能一直探索，這就要求我們在這兩者之間保持平衡，這直接影響著搜索性能和結果。
為解決這個問題，對于每個狀態(tài)，我們?yōu)槊總€可能的動作（共12個）設置計數(shù)器，每次在搜索過程中選擇某一動作，相應計數(shù)器就會增加。在決定采取特定動作時，可以通過計數(shù)器進行判定，即某一動作的執(zhí)行次數(shù)越多，將來選擇的可能性就越小。
此外，模型返回的值也用于輔助決策，即從當前狀態(tài)的值及其子節(jié)點狀態(tài)的值中選擇最大值進行跟蹤。根據(jù)這樣的模型，可以從父節(jié)點的狀態(tài)找到最可能的路徑。
總而言之，對于非葉節(jié)點狀態(tài)，通過以下公式選擇要執(zhí)行的動作：
其中，N(s,a)是狀態(tài)s選擇動作a的次數(shù)，P(s,a)是模型為狀態(tài)s返回的策略，W(s,a)是模型根據(jù)狀態(tài)s的分支a下所有子節(jié)點狀態(tài)返回的最大值。
重復此過程，直到找到解決方案或時間耗盡。為加快此過程，MCTS通常以并行方式進行，利用多個線程同時執(zhí)行多個搜索。在這種情況下，可以從A(t)中減去一些額外損失，以防止多個線程探索相同路徑。
為使用MCTS樹得到復原方案，論文作者提出兩種方法：
na?ve：得到目標狀態(tài)后，使用從根狀態(tài)開始的路徑作為復原方案；
BFS方法：得到目標狀態(tài)后，對MCTS樹執(zhí)行BFS，以找到從根到此狀態(tài)的最短路徑。
論文提到，第二種方法找到的復原方案比第一種方案更短，這并不奇怪，因為MCTS過程的隨機性，在第一種復原方案路徑中可能引入了無用的循環(huán)。
論文的結果令人印象深刻。在使用三個GPU并行訓練了44小時之后，網(wǎng)絡學會了類似甚至超過人工復原魔方的方案。最終，將本文模型DeepCube已與先前介紹的兩種求解方法進行了比較，分別是Kociemba two-staged solver 和Korf IDA*。
為驗證本文方法的效率，論文使用640個隨機打亂的魔方對不同方法分別進行測試，并設置最大求解步驟為1000步，最大求解時間為1小時，實現(xiàn)發(fā)現(xiàn)DeepCube和Kociemba方法均能在限制步驟和時間內(nèi)復原魔方。 具體而言，Kociemba求解速度非常快，其中值僅為一秒鐘，但是由于依賴人工定義規(guī)則，其求解并不總是最短的。DeepCube方法花費了更多的時間，中值約為10分鐘，但在55％的情況，該方法會比Kociemba得到更好的復原方案，即更少的步驟。從我個人的角度來看，55％雖然不足以說NN明顯更好，但至少證明該方法還不錯。下圖（摘自論文）顯示了所有求解方法的復原步數(shù)分布。可以看到，由于復原時間較長，在1000步魔方復原測試中沒有比較Korf求解方法，但為了將DeepCube與Korf求解方法的性能進行比較，論文進一步設計了更容易的15步魔方復原測試集。
好的，現(xiàn)在我們開始介紹代碼實現(xiàn)。在本部分中，我將簡要介紹代碼方案及一些關鍵設計，但在此之前，我還是要先強調(diào)一些事情：
我不是該項目的研究人員，因此這段代碼只是想要復現(xiàn)論文的方法。但不幸的是，由于論文沒有提供確切的超參數(shù)信息，因此我進行了大量猜測和試驗，但實現(xiàn)結果與論文的結果依然存在較大差異。
同時，我試圖以通用方式實施所有操作來簡化實驗。例如，有關魔方狀態(tài)和轉換的詳細信息不做詳細展示，僅僅通過添加一個新模塊來抽象化3x3魔方問題。在我的代碼中，分別對2x2魔方和3x3魔方進行實驗，但類似這樣有固定可預測動作集的、環(huán)境完全可見的問題都可以通過這樣的方式進行解決。下一節(jié)會做詳細說明。
相比代碼性能，我更關注代碼的可讀性與簡潔性，當然，對于不引入過多復雜性與成本消耗就能提高模型性能的操作，我在代碼中還是保留了它們。例如，僅通過分割魔方數(shù)據(jù)集和正向網(wǎng)絡傳遞，就可以將訓練過程加快5倍。但是，如果需要將大多數(shù)內(nèi)容重構為多GPU和多線程模式，我為簡單起見就沒有這樣做。典型的就是MCTS進程，通常采用多線程代碼實現(xiàn)，加快模型速度，但這就需要處理進程之間的同步問題。我沒考慮那么多，只是以串行方式進行MCTS，僅對批量搜索進行了簡單優(yōu)化。
綜上，我的代碼由以下幾部分組成：
魔方環(huán)境，用于定義觀察/狀態(tài)空間、可能的動作以及網(wǎng)絡狀態(tài)的表示，見libcube / cubes模塊；
神經(jīng)網(wǎng)絡，包括要訓練的模型、訓練樣本的生成和循環(huán)訓練過程。見the training tool和libcube / model.py模塊；
魔方復原方法, 見the solver tool和libcube/mcts.py；
其他一些不同組件，例如超參數(shù)的配置文件和魔方數(shù)據(jù)生成文件等。
正如前文介紹的，組合優(yōu)化可不是個小問題，而且種類繁多，即使單就魔方而言，也包含數(shù)十種變體，包括2x2x2、3x3x3和4x4x4Rubick魔方，以及Square-1，Pyraminx等。本文介紹的方法不依賴于預定義的領域知識、動作集和狀態(tài)空間大小，具有較強的適用性。具體而言，求解魔方問題基于以下假設：
環(huán)境狀態(tài)必須是完全可觀察的，根據(jù)觀察結果可以區(qū)分不同狀態(tài)。在魔方問題中，我們可以觀察到魔方所有面的狀態(tài)，因此該問題符合我們的假設。但對于類似撲克牌這樣的問題，我們是看不到對手的牌的，本文方法就不再適用了。
動作的數(shù)量是離散且有限的。在魔方復原問題中，我們只需執(zhí)行12中動作，這符合假設。但是對操作空間是“旋轉角度α∈[-120°…+ 120°]”這樣的非離散動作的問題，就需要不同的處理方法了。
環(huán)境的準確建模。換句話說，我們要能夠回答以下問題：“對狀態(tài)s采取行動a會產(chǎn)生什么結果？”。如果無法解決這樣的問題，ADI和MCTS方法都會失效。這個要求對于實現(xiàn)模型是及其必要的。然而，對于大多數(shù)問題，并不存在這樣的模型，或者模型的輸出非常嘈雜，但在象棋或圍棋之類的游戲中，游戲規(guī)則即是這樣的符合要求的模型。
領域確定性。即對相同狀態(tài)的相同動作會得到相同的最終狀態(tài)。不過我覺得，即使采取隨機行動也應該會起作用，但也不一定。
為了使我們的方法可以很方便的遷移到非3x3魔方的問題，我將所有具體的環(huán)境信息都移到了一個單獨模塊，并通過抽象接口CubeEnv與其余代碼進行聯(lián)系（見此處）。通過這樣的方式，每個環(huán)境都有一個名稱，指定環(huán)境名稱即可使用相應的的環(huán)境類型。目前，我們定義了兩種不同的環(huán)境：經(jīng)典三階魔方cube3x3和二階魔方cube2x2。
如果你要使用自己的魔方數(shù)據(jù)或其他不同的環(huán)境，只需要修改該模塊，通過接口即可在其它代碼中使用你自定義的環(huán)境。
模型訓練過程見train.py和libcube/model.py。為簡化實驗，同時增強實驗的可重復性，在單獨的ini文件中設置訓練的所有參數(shù)，包括：
要使用的環(huán)境的名稱，我們提供了cube2x2和cube3x3兩個環(huán)境；
運行名稱，在TensorBoard的名稱和目錄中顯示，并用于保存模型；
ADI的目標值計算方法。本代碼提供兩種計算方式：一種是原論文的方法，另一種是我改進的方法。實驗表明，我的改進方法收斂更加穩(wěn)定；
訓練參數(shù)，包括batch、是否使用CUDA、學習率、LR衰減等。
可以在ini文件夾查看我的實驗設置。訓練過程中，TensorBoard參數(shù)被寫入runs文件夾，并將最優(yōu)模型保存到saves文件。
訓練的結果是一個帶有網(wǎng)絡權重的模型文件。根據(jù)模型可以使用MCTS方法復原魔方，具體實現(xiàn)見solver.py和libcube/mcts.py模塊。
其中，求解器可用于不同模式：
復原一個雜亂魔方。該魔方由一系列由逗號分隔的動作索引打亂，該序列由-p選項傳遞。例如，-p 1,6,1是依次執(zhí)行第二個動作、第七個動作、第二個動作來打亂魔方。動作執(zhí)行是面向特定環(huán)境的，通過-e選項傳遞，在魔方環(huán)境模塊可以找到帶有索引的動作。例如，2x2魔方的動作1,6,1分別表示L，R'，L變換。
從文本文件（每行代表一個魔方數(shù)據(jù)）讀取排列并進行復原。文件名通過-i選項傳遞。我在cubes_tests文件夾提供了幾個示例，此外，你還可以使用gen_cubes.py生成自己的數(shù)據(jù)集。
生成更多步驟的打亂魔方并進行復原。
執(zhí)行復雜的系列打亂測試，并對其復原，然后將結果寫入csv文件。通過-o選項可以啟用此模式，這可用于評估模型的質(zhì)量，但同時也需要花費更多的時間。一旦選擇該選項，就會生成測試結果圖。
在所有情況下，都需要使用-e選項來傳遞環(huán)境名稱，并使用-m選項傳遞模型文件。此外，還有其他參數(shù)可以調(diào)整MCTS、時間或搜索步長等，在此不做過多贅述。
一開始我已經(jīng)說過，我不是論文的研究人員，因此本工作僅僅是復現(xiàn)論文并進行簡單實驗。但是，原論文沒有提供相關方法的詳細信息，例如超參數(shù)，在訓練過程中對魔方打亂的步數(shù)，收斂性等等。為獲取這些信息，我已向論文作者發(fā)送了一封電子郵件，但至今未收到他們的回復。
因此，我進行大量的實驗，但實驗結果與論文結果仍存在較大差異。首先，原始方法的收斂非常不穩(wěn)定，即使降低學習率和增大batch，訓練依然不穩(wěn)定，值損失呈指數(shù)增長，如下圖所示。
經(jīng)過多次實驗，我認為導致這種現(xiàn)象的原因是原始方法中值目標是錯誤的。
確實如此，在公式v? = max?(v(s, a) + R(A(s, a)))中，網(wǎng)絡返回的值v(s,a)總是與實際獎勵R(s)相加，即使對目標狀態(tài)也是這樣。這樣，網(wǎng)絡返回的實際值可以是-100、10?或3.1415。這樣大的差異對神經(jīng)網(wǎng)絡極不友好，尤其是MSE值目標。
為此，我做了以下修改，將目標狀態(tài)值設為0：
具體而言，指定參數(shù)value_targets_method = zero_goal_value而不是默認的value_targets_method = paper，你可以在ini文件中選擇該新的目標函數(shù)。
通過這種簡單修改，訓練過程模型可以更快地收斂穩(wěn)定狀態(tài)，見下圖。
原論文中，使用三個Titan XP GPU并行訓練了44小時，在這個過程中，模型總計看過約80億魔方狀態(tài)。根據(jù)這樣的敘述，可以得到訓練速度約等于每秒查看50000魔方狀態(tài)。我的實現(xiàn)在單個GTX 1080Ti上進行，其訓練速度為15000/秒，與論文差別不大。因此，使用論文的數(shù)據(jù)，在單個GPU上訓練一次大概需要6天時間，這使得實驗和超參數(shù)調(diào)整及其困難。
為解決這個問題，我設置了簡單的2x2魔方環(huán)境，只需一個小時的訓練時間。如果你也想繼續(xù)復現(xiàn)，可參見repo中的兩個ini文件：
cube2x2-paper-d200.ini：使用原論文中的值目標方法；
cube2x2-zero-goal-d200.ini：改進的0值目標計算方法。
在這兩種配置中，狀態(tài)批次均為10k，魔方打亂步驟為200，其他訓練參數(shù)也相同。
分別進行訓練后，生成了兩個模型（模型文件）：
原論文方法的損失為0.18184；
改進0值方法的損失為0.014547。
實驗表明，模型損失越小，成功率越高，可用于復原更多打亂步驟的魔方。兩種模型的實驗結果如圖所示。
接下來對魔方復原過程中的MCTS步驟進行對比。如下圖所示，改進的0目標模型通常以更少的步驟復原魔方，也就是說，該模型學到更優(yōu)的復原策略。
最后，比較不同魔方復原方法的長度。下圖繪制了na?ve和BFS方案的長度。從圖中可以看出，na?ve方法的長度要比BFS長約10倍，這表明調(diào)整MCTS參數(shù)可以改善模型性能。同時還可以發(fā)現(xiàn)，“零目標”模型的解決方案比原論文模型更長，其原因可能是前一種方法不存在更長的復原路徑。
3x3魔方的模型訓練過程要復雜的多，所以在這里僅進行簡單介紹。但即使只是簡單的實驗，也表明0值目標函數(shù)可以極大地提高訓練穩(wěn)定性和模型質(zhì)量。另外，三階魔方訓練一次大約需要20個小時，想要進行大量實驗需要花費很多時間和耐心。
正是由于上述原因，我的實驗結果不如論文所示結果，我得到的最佳模型僅解決12-15步的亂序魔方復原問題，對于更復雜的問題則無能為力。如果你想獲得更好的效果，可能使用更多CPU內(nèi)核+并行MCTS來提升模型性能。為了獲得數(shù)據(jù)，我將搜索過程限制在10分鐘內(nèi)，并對每個亂序干擾生成五個隨機干擾。
下圖是論文方法與改進的零目標值方法的比較。
下圖所示為找到的最佳解決方案的長度。圖示表明兩點：第一，在10-15干擾深度范圍內(nèi)，“零目標”方法求解長度大于論文的，這意味著模型雖然沒有找到生成測試數(shù)據(jù)的干擾序列，但發(fā)現(xiàn)了更長其他解決方法；第二，對于12-18深度范圍，原論文方法找到比干擾序列更短的解決方案，可能的原因是生成了簡并測試序列。
針對上述研究，有許多其他方法可提升模型性能，改進實驗結果。比如：
更詳細的輸入和更復雜的神經(jīng)網(wǎng)絡。由于魔方問題非常復雜，僅僅通過簡單的前饋神經(jīng)網(wǎng)絡并不能獲得最佳模型，考慮卷積網(wǎng)絡可能會提升模型的學習能力；
訓練期間的振蕩和不穩(wěn)定性在RL問題中十分常見，這可能是步間相關性導致的。通常的解決方法是，在使用策略網(wǎng)絡學習引導值時引入目標網(wǎng)絡；
引入臨時緩沖區(qū)可提高訓練速度；
實驗表明，樣本加權（與擾亂深度成反比）有助于獲得更好的策略，該策略知道如何解決擾亂魔方問題，但這也可能使對更深狀態(tài)的學習過程變慢。為此，可以使用自適應權重，以減少其在后續(xù)訓練階段的影響；
在訓練過程中使用熵損失來正則化學習策略；
2x2魔方的訓練模型沒有考慮到魔方問題中存在的不動中間塊，因此整個二階魔方都可以旋轉。由于二階魔方的狀態(tài)空間很小，所以無需考慮冗余的相同狀態(tài)，但對于4x4魔方來說，去冗余至關重要；
多次實驗尋找更好的訓練參數(shù)和MCTS參數(shù)。
感謝你的閱讀，期待你的評論！本文的PDF文件可從此處下載。
AI研習社是AI學術青年和AI開發(fā)者技術交流的在線社區(qū)。我們與高校、學術機構和產(chǎn)業(yè)界合作，通過提供學習、實戰(zhàn)和求職服務，為AI學術青年和開發(fā)者的交流互助和職業(yè)發(fā)展打造一站式平臺，致力成為中國最大的科技創(chuàng)新人才聚集地。
如果，你也是位熱愛分享的AI愛好者。歡迎與譯站一起，學習新知，分享成長。
