基于點(diǎn)格棋的UCT 算法研究與分析

張宜放， 孟 坤，2

（1 北京信息科技大學(xué) 計算機(jī)學(xué)院， 北京100101； 2 北京信息科技大學(xué) 感知與計算智能聯(lián)合實(shí)驗(yàn)室， 北京100101）

0 引 言

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

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

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

1 UCB 公式

1.1 UCB 公式描述

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

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

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

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

（1）首先將所有手臂都嘗試?yán)淮危?/p>

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

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

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

（4）重復(fù)步驟（2）；

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

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

1.2 UCB 公式改進(jìn)

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

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

2 UCT 算法——UCB Apply To Tree

UCT 算法基于蒙特卡洛樹搜索算法，并利用UCB 公式來增量擴(kuò)展搜索狀態(tài)，通過多次仿真來找到當(dāng)前結(jié)點(diǎn)的最優(yōu)分支［9］。

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

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

（1）以當(dāng)前局面為根結(jié)點(diǎn)；

（2）生成根結(jié)點(diǎn)的所有子結(jié)點(diǎn)；

（3）利用UCB 公式（2）計算每個子結(jié)點(diǎn)的UCBi值，選擇最大評價值的子結(jié)點(diǎn)進(jìn)行探索；

（4）若該結(jié)點(diǎn)非葉結(jié)點(diǎn)且搜索深度未達(dá)到預(yù)設(shè)深度k，將當(dāng)前結(jié)點(diǎn)作為根結(jié)點(diǎn)重復(fù)步驟（2）；

（5）直到遇到葉結(jié)點(diǎn)或搜索深度達(dá)到預(yù)設(shè)深度k，將當(dāng)前局面評估值或勝負(fù)結(jié)果逐級回溯，更新每一級祖先結(jié)點(diǎn)的UCBi值；

（6）否則，對這個葉結(jié)點(diǎn)進(jìn)行模擬對局，得到勝負(fù)結(jié)果，將這個收益按更新到該結(jié)點(diǎn)及其每一級祖先結(jié)點(diǎn)上去；

（7）回到步驟（1）（除非時間結(jié)束或者達(dá)到預(yù)設(shè)循環(huán)次數(shù)）；

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

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

3.1 對估值函數(shù)的依賴性

3.1.1 極大極小搜索算法

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

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

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

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

3.1.2 估值函數(shù)與α－β 剪枝算法

估值函數(shù)是為了對當(dāng)前局面做出定量分析而設(shè)計的，其根據(jù)當(dāng)前局面的優(yōu)劣給出局面的評估值，必勝為1 必敗為0，一般情況介于0－1 之間。 估值函數(shù)多是由該領(lǐng)域的專家，通過對局面某些特征值分析后得出的結(jié)論，可以視為人類經(jīng)驗(yàn)的總結(jié)。

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

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

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

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

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

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

3.2 搜索控制策略對比

3.2.1 α－β 算法

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

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

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

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

3.2.2 UCT 仿真

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

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

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

UCT 算法還可以直接通過仿真方向來判斷是否已經(jīng)找到最優(yōu)分支。 不同于剪枝算法找到最優(yōu)解的策略，UCT 算法的核心目的是找到最優(yōu)分支，那么可以預(yù)設(shè)在達(dá)到一定仿真次數(shù)后，若某一分支被多次仿真后UCB 值仍高居不下（某方向仿真次數(shù)越多調(diào)整項(xiàng)值越小，UCB 值越接近真實(shí)評估值），就可以認(rèn)為該分支為最優(yōu)分支。

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

3.3 UCT 算法的并行化優(yōu)勢

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

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

由于鎖機(jī)制的存在，實(shí)際應(yīng)用中每次模擬并不完全獨(dú)立，因而性能的優(yōu)化效果會有所減弱。

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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