計畫成員 : 吳廸融 吳毅成
深度強化學習近年來在各個領域取得了許多突破進展，包括遊戲、機器人和自然語言處理等。在深度強化式學習的領域中，電腦遊戲被視為是一個理想的測試環境。因為遊戲的環境相對容易取得及控制，很適合檢驗深度強化式學習演算法並可進一步有效的知識擴展到更複雜的系統中。本項目的目標是研究和開發可應用於各種現實環境應用的深度強化式學習演算法。以下將介紹本計畫的研究主題及一些初步結果。
AlphaGo-like或AlphaZero-like方法
首先，我們提出了一個基於AlphaGo演算法的多標籤價值網路。雖然AlphaGo在圍棋中達到了超越人類頂尖玩家的水平，但它是基於黑貼7.5目的規則而設計的。貼目是黑棋提供白棋額外的目數，為了平衡在圍棋中黑棋先落子的優勢。為了能讓程式支持不同的圍棋貼目規則，我們提出了一種新的價值網絡結構，稱為多標籤價值網絡，其架構如圖1所示。多標籤價值網絡具有三個優點：（1）此網路能輸出不同目數的價值、（2）支持動態貼目、（3）此網路能降低均方誤差（Mean Squared Error）並提高程式強度，特別是對於讓子棋局。
接著，我們提出使用基於超參數自動優化方法(Population Based Training)來訓練我們的圍棋程式CGI。在訓練後，CGI對抗由臉書所開發的程式ELF OpenGo時獲得了74%的勝率。採用此方法，我們節省了至少10倍以上的計算資源。上述這些的方法發表在IEEE Transactions on Games和國際頂尖會議AAAI 2020中，並被多數電腦圍棋程式採用。
此外，我們也提出了一個基於蒙地卡羅搜尋樹程序的強度調整。隨著電腦程式在許多遊戲達到超越人類頂尖玩家水平，人類對於如何從這些電腦程式學習引起極大的興趣。然而，如何將程式的難度調整到合適的水平來促進學習是一個非常重要的議題。太弱的程式會導致玩家失去興趣，而太過困難的程式則會導致人類學習的挫折感。為了解決這個問題，我們提出了一種通用的方法來調整基於蒙特卡羅樹搜索(Monte Carlo Tree Search）的程式強度，通過一強度超參數(z)以及歸一化指數(softmax)來控制難度。在將此強度超參數應用到我們的電腦圍棋程式CGI後，該程式可以涵蓋從初學者到超越頂尖人類水平的棋力。此方法也發表在IEEE Computational Intelligence Magazine期刊以及AAAI 2019。
問題解決 (Problem Solving)
儘管深度強化學習已經展示了能在遊戲中學習到超越人類頂尖水平的啟發式(heuristics)的能力，但這些學習得到的啟發式並不總是精確(exact)的解答。在許多現實的應用中，不僅僅是強大的啟發式，更需要精確的操作，例如自駕車或應用醫療手術的機器手臂。因此，如何將學習得到的深度強化式學習啟發式和精確方法結合起來，實現完美解答是一個巨大的挑戰。為了應對這一挑戰，本計畫使用7路殺光圍棋(7x7 Killall-Go)當為研究問題解決的基準(benchmark)，並期望這些方法未來可以擴展到其他現實世界中的問題，例如數學定理證明(theorem proving)、零工式排程問題（job shop scheduling problems）和旅行業務員問題（traveling salesman problems）。此研究主題可以分為兩部分：設計高效的搜索方法以及開發更好的深度強化式學習算法。我們以下將分別介紹這兩部分。
首先，我們研究設計高效搜尋方法用於遊戲證明。過去許多研究人員致力於針對各種應用問題來設計特定的知識幫助搜尋演算法解決遊戲。然而，這種方法需要高度熟悉各種遊戲，並且無法輕易地推廣到其他領域。為了解決這個問題，我們提出了一種新的搜尋方法，稱為基於相關區域的搜尋（relevance zone-based search）。 此搜尋使用子樹之間的信息來減少搜索複雜度，並且基於搜索樹自動形成知識，進而不需要使用到太多人類知識。圖2為一個相關區域建構的例子。我們提出的基於相關區域搜尋方法可以在解19路圍棋死活題中達到最佳的結果，並成功解決了106個19x19的死活問題中的68個。此外，我們還設計了一個基於相關區域模式的置換表(transposition table)，並將解決的問題數從68題提高到了83題。這些結果也發表在AAAI 2022和IEEE Transactions on Games。
此外，我們研究開發更好的深度強化式學習演算法用於遊戲證明。雖然許多研究人員嘗試使用深度強化式學習的啟發式來幫助解決問題，但這些啟發式並不總是能有效幫助解決遊戲問題。因此，我們提出一種新的深度強化式學習訓練方法，修改AlphaZero演算法的訓練目標，使其目標為解題而非高勝率。我們訓練了一個證明成本網路(proof cost network)，其中證明成本是一種啟發式，用於估算解決問題所需的工作量。我們提出了兩種訓練目標：第一種是嘗試估計找到解題的最短路徑，第二種是直接估算證明成本。在我們的實驗中，證明成本網路表現皆優於傳統的深度強化式學習方法。在相同的時間限制下皆能解決更多的問題。這個結果也發表在ICRL 2022上。
為了進一步提高解決問題的效率，我們開發了一種新的在線學習(online learning)方法，在求解的過程中動態地調整啟發式。此方法的架構如圖3所示，包括一個管理者(manager)、許多工作者(worker)以及在線學習訓練器(trainer)。管理者維護一個以要解決的位置為根節點的搜索樹，並根據證明成本網路價值將工作分配給工作者。工作者也是遊戲求解器，嘗試在給定的有限計算資源內解決工作。在解題的同時，在線學習訓練會持續調整啟發式，蒐集證明搜索樹中較常出現的盤面來當作訓練樣本，用以找到更好的啟發式。通過我們的方法，我們成功地解決許多具有挑戰性的7路殺光圍棋開局。相比不使用在線學習方法的求解器，我們速度增快3.29倍。我們預期在更困難的問題將會增快更多倍。
