Q學習實現亞馬遜棋評估函數自調參

邱虹坤,王浩宇,王亞杰

(1.沈陽航空航天大學 計算機學院, 沈陽 110136； 2.沈陽航空航天大學 工程訓練中心, 沈陽 110136)

0 引言

計算機博弈是人工智能領域的重要研究方向之一。近年來，計算機博弈的快速發展引起了國內外專家學者的高度關注。亞馬遜棋正是一種新興的計算機博弈棋種，它是一種兩人完全信息動態博弈游戲。棋子的移動方式類似于國際象棋中皇后的走法，同時具有很強的領土控制特色[1-3]。

評估函數是亞馬遜棋博弈程序中最為核心的部分之一，其作用是評估當前棋局局面的優劣性并為其打分。該分數作為后續博弈樹搜索等一系列操作的基礎，評估函數是否合理將直接影響到整個程序的棋力。對于亞馬遜棋評估函數中的一些關鍵參數，目前主要通過人工方法，根據經驗反復進行實驗調參后才能確定，這種方法效率較低且精確度無法保證。一些學者的研究表明，通過引入強化學習的方式，可在一定程度上提高調參的效率和精確性[4-5]。

本文采用強化學習中Q學習的思路，設計了一種能實現評估函數自主調參的網絡模型。相較于傳統調參方法，該模型節省了大量的人力與時間，并且通過自主訓練，對參數的調節也更加精確合理。

1 強化學習和Q學習

1.1 強化學習

在監督學習方式中，數據集的精確性很大程度上決定了訓練結果的優劣性。然而在某些情況下，要生成大量準確合理的教師數據是十分困難的，如對棋盤博弈游戲或電子游戲的訓練等。相比之下，強化學習更能勝任這些工作。強化學習是指在一連串行動的最后進行評價的學習方式。它不依賴于海量數據集的指導，而是通過不斷與環境交互，總結經驗并對行為的好壞進行評價打分，基于這些評價來推進學習[6-8]。該評價值被稱之為獎賞(reward)。當強化學習到達某結果并獲得獎賞時，與之關聯的每一個行動都將被分配一定獎賞，以此來更新學習網絡。

1.2 Q學習(Q-learning)

Q學習是最重要的強化學習算法之一，在該學習框架中，定義學習對象為Q值(Q-value)，代表選擇下一個行動的指標數值集合，通常建立一個Q表格來存儲。Q學習的最大特點在于將動態規劃與蒙特卡洛方法結合，用于計算強化學習的整個馬爾科夫獎勵過程，得出最優策略[9-10]。其中馬爾科夫過程又稱馬爾科夫鏈，指一系列不依賴于歷史，僅根據當前來決定未來的狀態集合，組成的無記憶的隨機過程。而獎勵過程則是在其基礎上引入了獎勵系數與衰減系數，因而可計算出某獎勵鏈條上的收獲(Return)[11]。

在訓練初期，Q值被隨機分配，此時相當于隨機選擇行動。在更新Q值時可以遵循以下規則：在行動獲得獎賞時，增加與其相關行動的Q值；在沒有獲得獎賞時，利用與下一狀態相關聯行動的Q值來更新當前Q值[12]。如式(1)所示。

Q(St,at)=Q(St,at)+

α(r+γmaxQ(St+1,at+1)-Q(St,at))

(1)

其中：s、a分別代表t時刻的狀態以及選擇的行動，r、γ、α分別代表獲得的獎勵值、折扣率以及學習系數[13]。學習系數是用于調節學習速率的常數，一般取0.1左右；折扣率的引入用于避免產生狀態的無限循環，一般取0.9左右[14]。

2 亞馬遜棋評估函數設計

根據亞馬遜棋的游戲規則，游戲一方的最終目的是用自己的棋子和障礙擋住對手的棋子，因此一般采取占領領土或阻塞對手路線的思路來設計評估功能[15]。亞馬遜棋評估函數的設計主要是基于kingmove和Queenmove走法。Queen走法是按照國際象棋中的皇后走法，可以向橫豎斜對角8個方向走直線，只要路徑上沒有障礙就可以沿直線一直走；king走法則是按照國際象棋中的國王走法，即只能向8個方向走一格。設t1、t2為territory特征值，代表雙方對空閑區域的控制能力的評估值；c1、c2為位置position 特征值，用于反映雙方對空格控制權的差值特征。a、b、c參數是根據棋局進行程度w而不斷變換的權重，用于動態控制在不同棋局進度下各個特征值對結果的影響[16]。此外，為避免出現區域浪費情況(某空區域被圍堵，不可再被使用)，定義參數S用于判斷當前步法是否會產生該種區域的出現(稱為缺陷區域)。需要注意，這里的“S”與式(1)中的“S”含義不同。式(1)中“S”代表強化學習模型中t時刻的狀態；而這里的“S”是為避免出現區域浪費情況而在亞馬遜棋評估函數中引入的參數。綜上，可以得出評估函數的最終表達式，如式(2)所示。

Value=a×t1+b×t2/2+

c×((c1+c2)/2)+S

(2)

a、b、c3個權重系數的確定對最終估值精度有至關重要的作用。一個根據經驗確定的權重與進度系數w的映射關系如式(3)所示[17]。其中，X值與Y值是決定評估準確性較為關鍵的參數，也是該評估函數中主要調參對象。

(3)

此外，雖然通過計算當前局面的領土特征值和棋子的靈活度等參數可以得到一個較為精確的評估價值，但有時仍會存在偏差，可以采用一種更為簡單直觀的方式來校準一下最終估值。通過“自對弈”的思路進行矯正，即以當前局面為基礎，電腦控制雙方隨機走棋(在一個輔助棋盤中)，在合理時間內進行大量對局，從而計算出勝率。隨機下棋雖然無規律性，但是模擬速度快。當進行大量模擬時也能一定程度上反映當前局面的優劣性。將模擬出的勝率與評估函數結果相結合即可達到調整效果。

3 Q學習調參模型

3.1 調參模型設計

本文主要的調參對象即為式(3)中的X值與Y值，可以采用迭代的思路實現自動調參，簡單來說就是對X參數或Y參數分別進行增大或減小，。首先定義2個數值C1、C2，分別代表對X、Y進行加或減操作時的變化值。以X、Y的具體數值代表當前狀態，而變更數值的方式則稱為“行動”。因此，結合一般手動調參的方法，對于每種情況都有6種后續可能的行動，如表1所示。表中前4種行為對應的就是“增大X”“減小X”“增大Y”以及“減小Y”。而5、6號行動的引入分別對C2進行加操作以及對C1進行減操作，目的是避免發生多次行動后的參數恰好未發生變化，導致調參陷入死循環。對此，建立一個三層六叉樹作為整體學習訓練框架，共43個結點，如圖1所示。

表1 后續行動方式

圖1 三層訓練網絡結點關系圖

模型利用對局的勝負情況來確定是否進行獎賞。首先記錄下初始的參數值：X0、Y0，而后經過一系列行動選擇后獲得新的參數值：X1、Y1。將新舊參數帶入博弈程序中調用，并進行數局對弈[18]。若新參數的勝率大于舊參數，則可以認為這是一種較好的調參策略，并對該行動路徑上所有結點的Q值進行獎賞操作。之后再重新選擇行動，獲得新的X1、Y1并進行獎賞評估。反復執行此過程后，最終會得到一條較為穩定的，Q值相對較高的行動路線[19]。按照該行動路線更新評估函數參數，即代表完成了一次調參操作。之后初始化整個訓練模型，以更新后的評估參數為基礎，進行新一輪訓練。如此反復以達到自調參的目的。整個訓練流程如圖2所示。

圖2 訓練流程框圖

3.2 調參模型實現

調參模型是在博弈程序的基礎上構造而成。首先定義節點型結構體node，內容包括每個結點的Q值，對X參數和Y參數所進行的操作，以及其6個孩子結點，可利用一個數組存儲。定義全局變量Weight，用于存放參數值；定義一個整形數組path，用于存放選擇過的行動路徑。

程序主要包括3個功能函數：為模型初始化、行動判斷、Q值更新。模型初始化時要求對所有結點信息進行初始化，包括Q值的隨機分配、行動定義以及孩子結點的鏈接等。行動選擇的基本思路是優先選擇Q值最大的行動，但可能會出現某一高Q值行動被反復選擇，同時其他行動無法得到訓練的情況。該問題可以通過ε-貪心法(ε-greedy)的思路解決。首先確定一個ε值并生成一個0～1的隨機數，若該隨機數小于ε，則忽略Q值進行隨機行動選擇；若大于ε，則選取Qmax行動[20]。

Q值更新主要基于式(1)進行計算，將學習系數設為0.1，折扣率設為0.9。首先執行新舊參數的自對弈功能，通過對弈結果判斷是否獎賞。如果能獲得獎賞，則將獎賞按比例加到Q值上；若不能，則從下一狀態所能選擇的行動中對應的Q值，將最大值按比例加到Q值上。由于葉子結點后無其他行動可選擇，因此對于模型第二層和第三層的Q值更新需要分別采取上述2種計算方法。

在實際調參過程中,Q值會影響程序調參的方法，從而得出不同的參數X和Y。而X與Y會進一步影響整個評估函數中不同參數的權重比，最終得出評估函數的計算最終結果Value。

4 實驗測試

首先初始化訓練參數。設評估函數模型中待調整的參數X、Y初值分別為5和20。對于訓練模型的每次調參操作中，訓練次數為10 000次，即模型在每次調參前需要更新10 000次網絡Q值。以黑方棋子作為調參測試對象。規定每次自對弈的局數為5局，即若黑方獲勝2局以上即可獲得獎賞。為了加快調參速度，限制了較淺的搜索深度以及較短的搜索時間。在對弈時，除了雙方程序評估函數的參數不同之外，其內部算法和邏輯結構等部分完全相同。

對模型進行第一次調參訓練，從中隨機抽取并跟蹤了6個結點的Q值變換過程，分別為網絡第二層的3號、5號結點以及第三層的結點20號、22號、33號和36號結點，結果如圖3、圖4所示。可見,當訓練次數為1 000時，Q值仍處于動態變化之中，在后期開始出現收斂的趨勢。而當訓練次數達10 000次時，各結點的Q值已處在一個相對穩定的區間內波動，從而可以認為此時的網絡已經訓練的較為充分。

圖3 訓練1 000次時節點Q值變化曲線

圖4 訓練10 000次時節點Q值變化曲線

因此，針對本次訓練的6個結點而言，得出的行動路線是5號結點至33號結點，最終的調參步驟應是先進行5號結點操作(X=X+C1、Y=Y+C2)，之后進行33號結點操作(X=X、Y=Y+C1)。重復上述調參步驟，進行數次調參后最終參數X與Y的變化情況分別如圖5、圖6所示。可見，在訓練過程中X、Y的值逐漸收斂并趨于穩定。訓練結束后，X值由最初的5被調整為3，而Y值由最初的20被調整為19.2。

圖5 參數X調整情況

圖6 參數Y調整情況

理論上，在單次調參操作中進行更多的網絡訓練(即Q值更新)，程序會選擇更加合理的調參行動。然而，每次的調參操作對整體評估函數參數的影響是有限的，且每次執行調參后該網絡模型都會被重置初始化。因此，在單次調參中對網絡進行過多的訓練，性價比顯得不高。應結合具體的硬件設備和程序本身來確定一個較為合適的單次調參訓練次數，盡可能多地完成調參操作，而避免花費大量的時間在僅僅一次的調參操作內。這樣，調參的效果會更加明顯，調參的整體效率也會更高。

為驗證程序整體棋力水平，該程序參加了中國計算機博弈錦標賽。在比賽過程中，相較其他程序而言，其最大特點是對棋盤空位的利用率很高，能更有效地利用自己目前所占有的區域。在與強隊進行比賽時，雙方棋力相差不大，我方憑借對棋盤空位的充分利用，最終靠細微優勢打敗對手，如圖7所示，黑棋為我方棋子。最終該程序取得了季軍的成績，說明該程序棋力優于大部分傳統博弈程序，同時調參的效果也得到了體現。

圖7 對弈終局局面

5 結論

結合Q學習的思想，構建了一個亞馬遜棋評估函數自調參強化學習模型。克服了傳統人工調參方式耗時耗力的缺點，實現了調試的自動化，同時對棋力的提升起到了一定效果。該思路不僅適用于亞馬遜棋的調參工作，對于類似的完全信息博弈類棋種依然適用。