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