基于點格棋的UCT 算法研究與分析

張宜放， 孟 坤，2

（1 北京信息科技大學 計算機學院， 北京100101； 2 北京信息科技大學 感知與計算智能聯合實驗室， 北京100101）

0 引 言

最初，基于深度優先的極大極小搜索算法［1］被用作計算機博弈系統中博弈樹搜索［2］的通用策略。隨后著名的α－β 剪枝［3］被提出并得到廣泛使用，進行α－β 剪枝的極大極小值搜索被稱為α－β 搜索。以α－β 搜索為基礎，衍生出了一些優秀的改進算法，如PVS［4］、MTD（f）［5］等基于搜索空間的局部性原理進行搜索窗口優化的算法，和數據質量敏感的各種啟發式或非啟發式置換表優化方法［6］。 在無法進行完全搜索的情況下，α－β 搜索的實際效果非常依賴其局面評估函數。 長久以來，α－β 搜索的局面評估函數由專家經驗與精巧的數據結構結合而成，使其算法難以快速應用到無法被完全搜索覆蓋的計算機博弈問題中。

為了避免α－β 搜索過程尤其是其局面評估過程對游戲經驗的依賴［7］，各類蒙特卡洛樹搜索（Monte Carlo Tree Search，MCTS）算法應運而生。 通過大量隨機仿真對局來模擬客觀的局面勝率，進而解決博弈中局面評估難問題，具有很好的通用性和可控性。 然而MCTS 算法也苦于其天然的統計性質，搜索過程中需要在客觀統計與偏好挖掘兩個傾向之間尋求平衡，使得MCTS 在大量隨機模擬中，不可避 免 地 包 含 了 大 量 冗 余 計 算［8］。 UCT 算 法（Upper Confidence Bound Apply to Tree）作為蒙特卡洛算法的一種延展［9］，通過UCB 公式引導探索方向，很好地對探索和開發進行了平衡，減少了冗余計算。

UCT 的算法減少了人類關于點格棋博弈技巧和知識的了解水平對博弈系統智力水平的束縛，以求時AI 擺脫“人”的影響。 本文以點格棋為載體，通過對比α－β 算法，從算法本身對估值函數的依賴性、階段控制和并行化3 個方面具體分析了UCT 算法的優勢所在，并針對UCT 算法中存在的不足之處提出了改進策略。

1 UCB 公式

1.1 UCB 公式描述

假設有一個擁有K 只手柄的賭博機，對于每一個手臂，都有一個未知的基于隨機數的獎勵函數?？梢宰龅膭幼魇沁x擇并拉下其中一只手柄，而由此賺取隨機數量的錢。 問題是如何根據當前已掌握的每只手柄的收益情況來決定下次拉下哪只手柄［10］。

分析可知，對于不同手臂其所能賺取的錢是不一樣的，多次拉同一個手臂其所能賺取的錢也是不一樣的。 玩家可以根據之前所累積的知識，拉下某只已開發過的手臂；也可以選擇去探索未開發手臂，獲得未知數量的錢。 如果不停開發已知手臂而不去探索未知手臂，就可能會錯過收益率更高的手臂；若不停探索未知手臂，就可能出現收益率一直小于當前已知最高收益率手臂，后悔值越來越大。

因此該問題可以簡化為探索和開發之間的矛盾問題，即在可接受的后悔值范圍內平衡探索未知手臂和開發當前收益率最高手臂之間的矛盾關系。

對于該問題模型，UCB 算法提出了一種解決方式，具體步驟如下：

（1）首先將所有手臂都嘗試拉一次；

（2）選擇使如下公式最大化的手臂：

式中，Xi表示第i 只手臂的平均收益值；Ti表示第i只手臂被探索的次數；N 表示總共探索的次數。 這個公式被稱作UCB 公式。

（3）拉下該手臂，更新公式（1）中對應手臂的UCBi值。 此時Xi和Ti會發生變化，N ＋1；

（4）重復步驟（2）；

對于UCB 公式（1），可以將其拆分為2 部分，分別是Xi和前項為當前開發項，表示該手臂過去開發的平均表現；后項為探索項，做為調整值表示該手臂被探索的價值。 其累加和為當前對這條手臂的評價值。

UCB 算法即利用當前掌握的知識加上調整值來平衡開發與探索之間的矛盾。 在每次做出選擇時，UCB 算法會挑選當前擁有最大評價值的手柄。其中的探索項調整值會隨著手柄被選擇次數的增加而減少，以便在選擇手柄時，不過分拘泥已有的表現，適當探索其它的手柄，從而在開發和探索之間取得平衡。

1.2 UCB 公式改進

由于開發與探索之間的比例依賴于具體問題，對于不同的問題有不同的比例選擇，所以在公式中的探索項引入常系數C，以改變開發和探索之間的比例［11］。 改進后的UCB 公式如下所示：

以點格棋為例，在前期布局時給予UCB 公式（2）較大的常數C 值，盡量給每一種走法探索的機會；而漸入中局，一定要獲取當前局面的最優解，選擇表現最好收益率最高的分支走棋，此時減小公式中的C 值，在開發與探索的平衡中漸漸偏向開發收益率最高的手臂。

2 UCT 算法——UCB Apply To Tree

UCT 算法基于蒙特卡洛樹搜索算法，并利用UCB 公式來增量擴展搜索狀態，通過多次仿真來找到當前結點的最優分支［9］。

假設已經建立了一棵龐大無比的博弈樹，其葉結點包含了全部n 層的n 的階乘種對局。 利用UCT算法搜索整棵樹從根結點開始的前k 層，在模擬到第k 層時給出估值函數來評價當前局面，必勝為1必敗為0，評估值作為這次探索的收益值X，逐層回溯更新父結點的UCB 值。 若達到葉結點，表示棋局結束，直接返回勝負值1／0 做為收益Xi。

將UCT 算法簡化描述成如下步驟：

（1）以當前局面為根結點；

（2）生成根結點的所有子結點；

（3）利用UCB 公式（2）計算每個子結點的UCBi值，選擇最大評價值的子結點進行探索；

（4）若該結點非葉結點且搜索深度未達到預設深度k，將當前結點作為根結點重復步驟（2）；

（5）直到遇到葉結點或搜索深度達到預設深度k，將當前局面評估值或勝負結果逐級回溯，更新每一級祖先結點的UCBi值；

（6）否則，對這個葉結點進行模擬對局，得到勝負結果，將這個收益按更新到該結點及其每一級祖先結點上去；

（7）回到步驟（1）（除非時間結束或者達到預設循環次數）；

（8）從根結點的子結點中挑選使公式（2）最大化的，作為下一步AI 走棋的選擇。

3 UCT 算法與α－β 剪枝算法對比

3.1 對估值函數的依賴性

3.1.1 極大極小搜索算法

極大極小搜索算法是大多數傳統算法，如α－β剪枝算法的理論基礎［2］。 其是一種對人類思維的模仿，在機器對某個局面進行分析的時候，假設一方總選擇使自己優勢最大化的一步，而對手選擇使自己損失最小化的一步。 如圖1 所示。

圖1 極大極小搜索樹Fig.1 MAX－MIN Search Tree

以當前局面建立根結點，使用深度優先遍歷整棵搜索樹。 在每次到達葉結點或搜索深度達到預設深度進行回溯時，對父結點進行判斷，如果父結點輪到我方走棋，則判斷子結點評估值是否大于父結點當前記錄最優評估值，若大于則更新，并記錄該子結點為當前我方最優解；反之輪到對手走棋，則判斷當前子結點評估值是否小于當前父結點當前記錄最優評估值，若小于則更新，并記錄該子結點為當前對方最優解。 輪到我方走棋的父結點最優評估值初始為負無窮，對方則為正無窮。 直到回溯到根結點，選擇當前所有子結點中評估值最高的結點作為我方下一步走棋選擇即可。

而由極大極小搜索算法衍生出的α－β 剪枝等傳統算法，是在對博弈樹進行遍歷時所使用的剪枝策略，通過減去不可能選擇的分支來提高搜索的效率，可以看做是對極大極小算法的改進和擴展。

3.1.2 估值函數與α－β 剪枝算法

估值函數是為了對當前局面做出定量分析而設計的，其根據當前局面的優劣給出局面的評估值，必勝為1 必敗為0，一般情況介于0－1 之間。 估值函數多是由該領域的專家，通過對局面某些特征值分析后得出的結論，可以視為人類經驗的總結。

但人類的計算能力也是有限的，當人類計算至某一局面時，會自發地給出一個局面的感性評價來判斷是否要選擇走這一步，而估值函數所做就是在模擬計算機計算到一定深度的局面時，給出對該局面定性的分析從輔助AI 決定下一步的走法選擇。

在人類棋手之間，勝負的關鍵在于計算能力和比賽經驗，計算能力越強算的越深，對局面的分析也就越準確，經驗越豐富的棋手對局面的判斷越準確也就更可能主導局勢的發展。 對計算機同理，在無法進行硬件性能（算力）提升的前提下，估值函數對局面分析的準確性將直接主導極大極小搜索算法的水平，是否能在有限的搜索深度下找到最準確的解。但對于從初始局面構建的一棵博弈樹，其結點數隨著深度的增大呈指數級上升。 那么在無法完全遍歷整棵博弈樹時，仍非常依賴估值函數。

3.1.3 UCT 算法與α－β 剪枝算法在估值函數依賴性方面的對比

假設有一個非常精確的估值函數，能以100%正確率給出當前任意局面的評估值，那么只需要將其應用到任意搜索算法中去，AI 每步必定能準確算出評估值最大的一步，使一方優勢最大化，且這一步必定正確。 很顯然這樣的估值函數是不存在的，其總會存在些誤差，對某些特定局面的評估值不那么準確。 那么此時，對某一局面的判斷失誤，會被逐層回傳父結點，對整個局面的判斷誤差被逐層放大至根結點，導致人們做出錯誤的選擇。 所以，估值函數的參數也是影響機器棋力的一大重要因素。

對于α－β 剪枝算法所采用的搜索策略，每個局面只會被模擬一次，一旦這個由估值函數引發的錯誤值更新了父結點的數據，就會被逐層回傳，導致根結點認為在這一分支發現了更優的一步，從而引起判斷的失誤。 對于UCT 算法，每個局面有多次被模擬到的機會，父結點的回溯策略也不是簡單的返回評估值最大的結點，而是返回具有最優分支的結點。換句話說，即便在某一分支中估值函數給出了錯誤的判斷，只要其它分支表現的足夠好，UCB 值較大，AI 也不會選擇具有最優解的錯誤分支。 舉例而言，當AI 算到走1 號邊能有一個必勝的局面，而走2 號邊會出現90%的優勢局面，α－β 剪枝算法會選擇前者，而UCT 算法會選擇后者。 對于α－β 剪枝算法，如果選擇1 號邊出現的唯一必勝局面評估值有誤，將會直接進入錯誤的分支。 對于UCT 算法，無論1號邊的必勝局面正確與否，都不會影響最終的選擇；而假如2 號邊模擬的局面中存在某些局面有誤，也不會大幅度改變該分支的勝率（就目前來看機器1 min 仿真次數可以在十萬至百萬級別，僅幾個局面的錯誤判斷幾乎不會影響AI 對整體局勢的判斷）。

α－β 剪枝算法所要找到的是具有最優解的分支，而UCT 算法則是為了尋找表現最好的分支，即便最優解可能不在該分支。 在估值函數表現不穩定或不夠準確時，就很難直觀的找到最優解，而使用UCT 算法可以很好地中和估值函數帶來的誤差，引導程序向整體局面更優的方向走棋。

3.2 搜索控制策略對比

3.2.1 α－β 算法

α－β 剪枝算法的控制策略主要依靠搜索深度和迭代次數2 種：

一般用于區分局面的階段，如開局、中期、殘局階段，傳統剪枝算法使用的是搜索深度控制策略。當搜索深度越深，估值函數的準確性就越高，當搜索到葉結點時，就不需要估值函數直接反饋比賽勝負即可，此時完全不存在估值函數造成的誤差；但搜索層數越深迭代次數也就越多，耗時越多。

相比于搜索深度控制，迭代次數控制更像一種無奈之舉。 在沒辦法大量剪枝的時候，強制在達到規定迭代次數的時候終止程序，以確保不浪費過多的時間。 迭代控制有一定不可預知性，可能在還沒進入最優解，所在分支迭代就結束了，但至少可以保證在不超時的情況下，選擇一個次優解。 所以一般剪枝算法在設計時，都會在深度控制之外設置迭代控制，作為“保險裝置”。

對于α－β 剪枝算法，當算法被迭代控制直接中斷時，未探索的分支相當于被剪枝，其狀態樹尚未生成也就無從判斷是否錯過最優解。 而且同一時刻，剪枝算法對子結點探索程度不相同，強行終止算法可能會出現某一子結點已完成探索而仍有子結點未開始探索的情況發生。 所以剪枝算法在設計之初就必須規劃好時間和搜索深度的分配，但對于點格棋，局面可能存在大量等價邊［12］剪枝，實際應用中根本無法判斷程序在某一階段探索一定深度所需消耗的時間。

3.2.2 UCT 仿真

UCT 算法的控制策略可以分為搜索深度、仿真次數、仿真方向3 種：

前2 種控制方法思路基本同剪枝算法，不同的是剪枝算法是迭代次數，而UCT 算法是仿真次數（或者說是模擬對局的次數）。 但迭代次數的控制實質上是用限制迭代次數去控制時間，而UCT 算法則是直接控制時間去限制仿真次數，在進行調整時會更加靈活。

UCT 算法中可以通過改變UCB 公式來進行搜索方向的引導。 通過調整平衡系數和修正收益大小，都可以直接影響根結點對仿真方向的判斷，從而達到提前收斂或是增加搜索廣度的效果，相比α－β剪枝搜索的按序遍歷而言，調整和控制更加靈活。

UCT 算法還可以直接通過仿真方向來判斷是否已經找到最優分支。 不同于剪枝算法找到最優解的策略，UCT 算法的核心目的是找到最優分支，那么可以預設在達到一定仿真次數后，若某一分支被多次仿真后UCB 值仍高居不下（某方向仿真次數越多調整項值越小，UCB 值越接近真實評估值），就可以認為該分支為最優分支。

UCT 算法擁有傳統剪枝算法無可比擬的隨時中斷特性［13］。 在判斷時間不足時，使用UCT 算法的程序可以直接強制中斷，同時返回一個相對不錯的次優解。 這是由于蒙特卡洛模擬具有的天然統計性質，且搜索初期UCB 公式中仿真次數N 較小，后項探索項影響因素遠大于前項開發項，可大致認為對子結點的探索次數服從均勻分布，所以即便此時中斷算法，也不會出現某一分支幾乎未被探索而錯過最優解的情況。

3.3 UCT 算法的并行化優勢

UCT 算法主要以仿真模擬對局為主，非常適合做并行化［14］。 在擁有多個CPU 核心的情況下，通過并行的展開多個線程，分別進行不同對局模擬。某一線程在模擬完成后，先給公共資源區（整棵博弈樹）加X 鎖，修改部分結點UCB 值， 該線程再展開下一輪模擬［15］。 在這一過程中，不需要訪問博弈樹的線程仍可以繼續工作。 UCT 單次仿真平均用時見表1。

表1 UCT 單次仿真平均用時Tab.1 Average running time of UCT each simulation μs

由于鎖機制的存在，實際應用中每次模擬并不完全獨立，因而性能的優化效果會有所減弱。

對于α－β 剪枝算法，其搜索過程獨立性沒有UCT 仿真高，對公共資源區的使用也不像UCT 仿真在整次模擬結束后才加鎖更新結點權值，而是在每一次回溯時就更新父結點權值。 在做并行化時，其每一個線程對公共資源區的訪問頻率更高，導致公共資源區被頻繁加鎖，其它線程等待時間增加，CPU利用率下降，并行化的優化效果較弱。

4 實驗結果與分析

測試棋盤大小為6×6，比賽單方總時限為15 min。 6×6 點格棋棋盤共60 條邊，假設一方走30 步（會有得子連走情況，一方走棋未必為30 步），標準單步時限即為15 min／30 步，即30 s。

測試硬件環境如下：i7，6700HQ，主頻2.6GHz，內存12G，顯卡960M，四核八線程。

在使用相同估值函數且算法均完成并行化的情況下，將UCT 算法與α－β 剪枝算法實現的程序進行對弈測試。 30 s 蛙限不同算法對弈結果見表2。

進一步進行測試，分別給予程序5 s 和120 s 的不同時限進行對弈。 見表3 和表4。

表2 30 s 時限下不同算法對弈結果Tab.2 Game results of different algorithms within 30 s

表3 5 s 時限下不同算法對弈結果Tab.3 Game results of different algorithms within 5 s

表4 120 s 時限下不同算法對弈結果Tab.4 Game results of different algorithms within 120 s

由表3、表4 可以看出在估值函數不穩定且均使用相同估值函數的情況下，UCT 算法能明顯規避誤差，顯著提高勝率，尤其是在搜索時間較短時，UCT 算法的優勢越發明顯，其短時內可得到次優解和隨時中斷的特性被進一步放大。 當每步時限增大時，UCT 算法苦于蒙特卡洛模擬的固有問題，在大量統計量中難以避免的出現冗余計算，算法效率略顯下降，不過仍明顯強于α－β 剪枝算法。

5 結束語

計算機博弈是一個復雜和具有挑戰的課題，對與博弈論的學習和研究具有深遠的意義。 UCT 算法減少了人類關于點格棋博弈技巧和知識的了解水平對博弈系統智力水平的束縛，而機器博弈未來的發展方向，也正是讓機器實現自我博弈、自我學習，真正擺脫“人”的影響。 本文以點格棋為載體，通過對比α－β 算法，從算法本身對估值函數的依賴性、階段控制和并行化3 個方面分析了UCT 算法的優勢所在，并提出了改進策略。

此次研究雖小有成果，但仍存在一些不足有待進一步的研究和改進。 在通過UCB 公式中引入平衡系數后，該系數的設計方式偏向于動態調整，由AI 自發的根據當前局面判斷平衡開發與探索之間的比例關系，但目前仍無法設計出一套可準確調整平衡系數值的控制函數。 最終采用靜態控制的策略，通過理論分析和大量實驗得出各階段平衡系數的相對合理值。