基于CNN模型的亞馬遜棋搜索算法設計*

北京信息科技大學計算機學院 李若溪 高銘

亞馬遜棋AI搜索算法包括蒙特卡洛搜索算法、改進后的α-β剪枝算法，極大極小搜素算法，經檢驗發現蒙特卡洛搜索算法取得較好的成果，但原有的搜索算法由于搜索的博弈樹層數為固定值，會產生超時或搜索層數過少造成搜索不完全的問題，嘗試使用CNN模型優化原有的亞馬遜棋搜索算法。設計一個基于CNN模型的優化器，該優化器將當前棋盤的權值作為輸入層，進行三層卷積，輸出層為當前局面下的最優層數。在同等計算力條件下，采用蒙特卡洛與α-β剪枝算法，令采用CNN模型優化后的搜索算法與固定搜索層數的算法進行對弈，前者的不敗率為73.4%。經過實驗，發現通過CNN模型自動生成搜索層數的算法對勝率產生了較好的影響。

亞馬遜棋發明于1988年，是一種兩人棋。一個完整的亞馬遜棋局面包括棋盤、棋子、箭，博弈系統包括：落子生成器、落子搜索引擎以及局面得分的評估函數。生成器針對已下的棋局的局面，結合落子的搜索引擎對下一步一定范圍內的節點數進行搜索，利用評估函數對每個節點進行評分，返回給落子的生成器進行下棋。綜上而言，對勝率產生影響的主要因素是搜索算法與評估函數，亞馬遜棋的局面評估函數主要包括以下三個特征的評估值，分別為Territory、Position、Mobility，而搜素算法包括搜索層數與搜索方式，搜索層數的優化為本文的主要研究內容。

最初，大多數強大的亞馬遜程序都使用傳統的基于極小值的算法，這類程序有Invader和Amazong。這種搜索方法編譯簡單，容易操作，但是由于亞馬遜棋博弈樹深度大，遍歷的代價極大，即使采取α-β剪枝進行改進，也無法有效解決其耗費大量時間的瓶頸問題。

隨后，由于蒙特卡洛的算法在圍棋中的優異表現，亞馬遜棋也引用了此種技術。蒙特卡洛搜索算法的基本思想是通過迭代的、隨機的或者其他更為智能的方法，對每個樣本進行隨機采樣，從而找到最佳走法。但由于蒙特卡洛搜索算法本質是一種隨機算法，不可避免的出現過擬合的問題。

而后，人們又對基本的蒙特卡洛算法作出改進，包括向前剪枝和停止蒙特卡洛模擬結束過早的問題。改進步驟包括找到合適的評價功能后逐步拓寬，最終選擇正確的評價功能；找尋合適的停止隨機模擬的時刻。主要的措施為從UCT樹的根開始找到一條路徑，通過沿著樹向下，選擇具有最高的擴張價值的節點來獲得葉節點，再從這個葉節點和對應位置運行一個隨機模擬裝置，將該葉節點的子葉子添加到UCT樹中。而是否展開葉節點通常基于該節點被訪問的次數，一個節點的展開值等于所有仿真的獲勝百分比。

1 基于CNN模型的搜索層數優化器

原有的結合α-β剪枝的蒙特卡洛搜索算法在策略上過于保守，針對于不同的可擴展節點數所遍歷的博弈樹層數是固定的。上限節點數不但需要根據不同性能的電腦不斷調試找到極限值，且由于特定節點數的搜索層數都是固定的為了避免極端情況超時問題的發生，所以需限制搜索層數。在此種情況下的搜索效果會大大降低，以犧牲勝率換取足夠時間。針對以上問題，嘗試使用CNN模型自動得出當前局面下的最優搜索層數

1.1 CNN輸入層

該CNN模型（如圖1所示）由輸入層，3個卷積核和輸出層構成，神經網絡的輸入為10×10×1的棋盤數據，輸出為一個1×1×1的最優層數值。其中輸入的10×10×1的棋盤信息相當于輸入一個10維度的方陣，這個矩陣中每個數值的表示方式為：

圖1 CNN模型圖Fig.1 CNN model diagram

W

t表示到目前為止比賽進行的時間，單位為秒；900表示在正規的亞馬遜棋博弈中一方的下棋總時長為15分鐘，轉換為秒數為900s。由于已經對弈所占的時長越長，意味著剩余的時間越短，在較少的時間中為了確保比賽不會出現超時問題，就需要依照時間降低對應的權值。

n表示棋盤在該位置獲勝搜索時搜索的層數，采用蒙特卡洛算法進行模擬搜索。蒙特卡洛樹搜索是一種基于樹的數據結構，可以在搜素空間巨大的情況下仍具有一定效果的啟發式算法，其通過選擇一個結點后進行擴展，模擬游戲進行直到得到游戲結果，最后通過反向傳播返回到達游戲結果搜索的層數n。如果這個位置已經放置了障礙物或存在棋子，則證明這個位置已經搜索完全所以直接令層數n為0。

1.2 CNN卷積層

卷積層是CNN的核心，局部連接和權值共享是卷積層獨有特點，該模型卷積層由三個卷積核組成，卷積核大小分別為5×5，5×5以及4×4。為了保證信息的完整性，確保重要信息不被丟失選擇Padding為1。卷積核通過在上一層的特征圖上不斷移動進行卷積運算，從而得到提取出的特征。其中，在同一層的卷積核移動中，權值實現共享。卷積層對應的計算公式如下：

在訓練過程中，不斷調整卷積核中權值和偏置，使網絡性能達到最優。最后經過三層卷積得到的數值N表示在當前棋盤下的最優搜索層數，由于這個數據是通過卷積神經網絡自動生成，能有效避免搜素層數過多出現的超時情況與搜索層數太少而降低勝率的情況。

2 模型訓練與測試

由于建立蒙特卡洛搜索樹的過程中會產生很多的局面，所以利用程序自對弈的過程，使其不斷建立蒙特卡洛搜索樹，并產生大量的局面，數據集則來源于整個自對弈過程中所有的局面。采用按比例劃分，數據集的總量為81742572條，其中選擇85%為訓練集，共69,481,186條，剩下的15%為測試集，共12,261,386條。

根據搜索的過程中，擴展節點的層數來劃分不同的類別，因為程序的設置，為了保證搜索的精準度和利益最大化，程序設置搜索層數為3以上，3以下暫時不考慮。經過統計可以得出：3到7層的占比分別為：54.48%、26.11%、16.30%、2.91%、0.2%。

其中三層與七層之間的比為272∶1,可以看為數據不平衡，搜索到七層的局面數量太少。而樣本不平衡會使得分類模型存在很嚴重的偏向性，從而使模型產生較嚴重的誤差，所以針對不平衡分類選擇以下兩種方法解決。

其一為繼續增大數據集，因為機器學習是使用現有的數據多整個數據的分布進行估計，因此更多的數據往往能夠得到更多的分布信息，以及更好分布估計，但是經過多次再次采樣對弈之后發現搜索層數多到第七層的次數更加少，甚至比原本的更加不平衡。

因為第七層的特殊性，對其進行過采樣需要耗費大量的人力以及時間，又因為第七層對整體影響較小，所以使用欠采樣加人工產生數據樣本的方法來解決樣本分類的不平衡。使用系統的構造人工數據樣本的方法SMOTE(Synthetic Minority Over-sampling Technique)。

首先通過刪除一半量的三層搜索，以達到趨向平衡的目的，接著進行欠采樣。進行完欠采樣后，搜索三層和搜索七層的比為136∶1，可見數據集在某種程度上仍然是不平衡的。所以繼續使用Smote過采樣算法補充第七層的不足。在Python中通過導入Imlbearn庫中的過采樣方法中的SMOTE接口

數據值無需過大，只需要多層搜索時對模型的影響較小即可最終結果比為10∶1左右。當前數據某種程度上來說是平衡的，所以更新完數據集之后就可以進行下一階段的模型訓練。

最終的數據集3至7層的數量分別為：22267433、21343349、13321549、2378911、2275699。再從61,588,941中分取85%作為訓練集，訓練數據為52,350,600。

在六核十二線程主頻為2.6GHz的電腦下訓練，每個Epoch要訓練的局面數量是52350600，訓練集具有的Batch數目是799次，總的訓練時間為27天。

3 實驗結果

由于原程序已經擁有著法生成器，搜索器，棋盤生成以及獲勝判定等函數，所以為了獲取實驗數據，只需要使其不斷地自對弈，即可獲得大量可觀測的棋局。

最終，在六核十二線程主頻為2.6GHz的電腦下用7241個棋盤的訓練集對該卷積神經網絡的模型進行訓練，通過多次的訓練與反復疊加得到卷積核，再選擇2000個棋盤的測試集進行測試，總共獲勝的棋盤局數為1446，獲勝率為72.3%，平局23盤，不敗率為73.4%：

經過算法調整和模型訓練，使原程序變成并行的算法，預計2000盤中會有10盤因為各種原因導致搜索超時，即便是設置了超時不超時，但依舊留有10場的保守估計，而真實結果則是沒有超時現象發生。

在2000個棋盤的測試結果中，模型訓練過后的算法相比于原算法來說，勝率達到了72.3%，這說明了訓練過后的算法相比于原來的算法能保持著穩定的勝率，而且在平均勝子數目上，經過訓練的新算法的平均勝子數為1.65，與預期的2相差不多，有差別的原因是在先后手以及原算法某些特定的落子下，導致訓練后的算法某幾步思考時間過長，而平均勝子數達到了1.65這說明了算法的提升的，證明了模型的訓練是成功的。

4 結論

通過數據顯示可以認為，在使用自動生成搜索層數的模型效果優于同等條件下層數固定的模型。但是由于訓練集的有限和時間限制可能使訓練出的卷積核沒有達到較為完美的效果，后續仍存在改進與優化的空間。

這種優化器的思想不僅可以在亞馬遜棋中使用，在同樣具有盤根錯雜的圍棋博弈樹下也可采用類似的方法，但由于圍棋自身的復雜性不建議用蒙特卡洛算法搜索出結果，局面表明我方占有優勢即可。