面向搜索時(shí)間受限的完全信息博弈UCT算法改進(jìn)研究

張宜放　孟坤　蔣志文　高世靜　張?zhí)N瀚

摘要：針對(duì)完全信息博弈中搜索時(shí)間受限的算法設(shè)計(jì)問(wèn)題，在考慮博弈模型不同特點(diǎn)及對(duì)結(jié)局影響程度的基礎(chǔ)上，提出了分階段的算法模型，給出了三階段博弈算法設(shè)計(jì)方法。通過(guò)改造影響搜索策略的目標(biāo)函數(shù)，使得在時(shí)間受限的前提下，能夠方便控制每一階段均更有效地搜索出較好策略，并給出相應(yīng)的算法實(shí)現(xiàn)與分析。以點(diǎn)格棋為對(duì)象，給出了通過(guò)改造UCT算法中UCB公式的實(shí)現(xiàn)思路，設(shè)計(jì)了方向引導(dǎo)控制策略、多種算法混合、二進(jìn)制壓縮和并行化處理等技巧，有效提升了算法的效率和穩(wěn)定性，并通過(guò)試驗(yàn)驗(yàn)證了所給出方法的有效性和效率。

關(guān)鍵詞：UCT算法優(yōu)化;三階段模型;點(diǎn)格棋

中圖分類號(hào)：TP301.6? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2021）04-0195-06

Abstract： To deal with the algorithm design of the Time-Constrained problem in the complete information game， based on the different characteristics of the game model and the degree of influence on the outcome， a staged algorithm model is proposed and a three-stage game algorithm design is given. By transforming the user's reward function that affects the search strategy， under the premise of limited time， it is convenient to control each stage to search for better strategies more effectively， and to give corresponding algorithm implementation and analysis. The realization idea of the UCB formula in the UCT algorithm is given based on Dots and Boxes， and the techniques of direction guiding control strategy， multiple algorithm mixing， binary compression， and parallel processing are designed， which effectively improves the efficiency and stability of the algorithm. The effectiveness and efficiency of the proposed method were verified by experiments.

Key words： Optimization of UCT algorithm; Three-stage model; Dots and boxes

博弈模型常被用來(lái)刻畫(huà)多主體獨(dú)立參與、行為相互制約的問(wèn)題[1]，目的在于計(jì)算給定用戶最優(yōu)收益的行為策略，根據(jù)博弈參與者對(duì)其他參與者潛在行為集合信息的知曉多少，博弈模型被分為完全信息博弈和非完全信息博弈[2]。當(dāng)前，博弈模型已經(jīng)被廣泛用于經(jīng)濟(jì)政策制定、管理策略設(shè)計(jì)、通信調(diào)度算法研發(fā)，以及網(wǎng)絡(luò)協(xié)議設(shè)計(jì)等場(chǎng)景，也是人工智能算法設(shè)計(jì)的模型工具之一。然而，用戶收益函數(shù)（Users reward function）定義的多樣性制約了博弈模型的策略計(jì)算，即使針對(duì)完全信息博弈模型，尚缺乏得到博弈模型顯式均衡策略的通用方法[3]，因此，高效近似解的計(jì)算方法成為計(jì)算機(jī)學(xué)科研究的重要方向。

以博弈模型的人工智能算法設(shè)計(jì)為例，當(dāng)前主要采用的研究思路為基于博弈樹(shù)搜索最優(yōu)策略路徑，典型算法包括α-β剪枝搜索[4]（α-βpruning，α-β）和蒙特卡洛樹(shù)搜索[5]（Monte Carlo Tree Search，MCTS）。α-β搜索算法主要依賴基于收益函數(shù)回溯計(jì)算的局面收益評(píng)估函數(shù)，通過(guò)剪去非占優(yōu)分枝減少搜索空間，進(jìn)而得到最優(yōu)策略。蒙特卡洛樹(shù)搜索旨在通過(guò)大量仿真，使用收益統(tǒng)計(jì)值替代局面收益函數(shù)評(píng)估，進(jìn)而貪婪地得到給定局面下的最優(yōu)策略。由于，實(shí)施過(guò)程中對(duì)經(jīng)驗(yàn)知識(shí)依賴程度的不同，蒙特卡洛樹(shù)搜索更具備可擴(kuò)展性，因此，在人工智能算法設(shè)計(jì)中蒙特卡洛樹(shù)搜索的應(yīng)用更為廣泛。由于足夠多的仿真次數(shù)是MCTS準(zhǔn)確性的根本保證，較好地實(shí)踐算法均需要較長(zhǎng)的仿真（訓(xùn)練）時(shí)間，效率和準(zhǔn)確性成為MCTS難以兼顧的兩個(gè)對(duì)立方面[6]，因此，提高上述兩方面指標(biāo)的MCTS算法成為重要研究方向。具有代表性地，UCT（Upper Confidence Bound Apply to Tree）算法[7]中使用UCB公式，在UCB值的引導(dǎo)下實(shí)現(xiàn)了更有針對(duì)性的仿真搜索，較大程度地提高了收斂到最優(yōu)策略的效率，并在諸多問(wèn)題中得到應(yīng)用。但是，針對(duì)時(shí)間受限的博弈AI算法設(shè)計(jì)問(wèn)題，相關(guān)的研究成果還較為有限，主要采用強(qiáng)制停止搜索、使用當(dāng)前值近似替代的方法，算法準(zhǔn)確度難以得到保障。

基于上述問(wèn)題，本文針對(duì)時(shí)間受限的完全信息博弈AI算法設(shè)計(jì)問(wèn)題，提出了一種基于UCT算法UCB（Upper Confidence Bound）公式的改進(jìn)方案，引入了平衡系數(shù)C，實(shí)現(xiàn)對(duì)不同階段探索與開(kāi)發(fā)比例的動(dòng)態(tài)調(diào)整策略;引入貪心系數(shù)G，利用經(jīng)驗(yàn)對(duì)UCT探索過(guò)程進(jìn)行方向引導(dǎo)，加快收斂速度，適應(yīng)了時(shí)間受限的情景。此外，通過(guò)對(duì)完全信息博弈的博弈過(guò)程研究，提出一種三階段模型，針對(duì)不同階段的特點(diǎn)設(shè)計(jì)不同控制策略，并輔以算法并行化處理方法、局面二進(jìn)制壓縮等多種優(yōu)化策略和技巧，極大地提升了算法性能，實(shí)現(xiàn)兼顧準(zhǔn)確性和效率的優(yōu)化UCT三階段模型。

1 UCT算法優(yōu)化

1.1 公式改進(jìn)——引入平衡系數(shù)和貪心系數(shù)

UCB公式最初是針對(duì)K臂賭博機(jī)問(wèn)題提出的[8]，目的是平衡開(kāi)發(fā)與探索之間的關(guān)系。應(yīng)用于博弈領(lǐng)域時(shí)，在以當(dāng)前局面為根節(jié)點(diǎn)建立的博弈樹(shù)中共有i個(gè)分支，用UCBi表示對(duì)第i個(gè)分支的評(píng)估值。

式中，Xi為第i個(gè)分支的平均收益值，Ti為第i個(gè)分支被探索的次數(shù)，N為總探索次數(shù)。公式中前項(xiàng)Xi為開(kāi)發(fā)項(xiàng)，表示該分支過(guò)去開(kāi)發(fā)的平均表現(xiàn)，后項(xiàng)式[2lnNTi]為探索項(xiàng)調(diào)整值，表示該分支被探索的價(jià)值，最終通過(guò)開(kāi)發(fā)項(xiàng)和探索項(xiàng)的加和作為當(dāng)前該分支的綜合評(píng)價(jià)值，來(lái)平衡開(kāi)發(fā)與探索之間的關(guān)系[9]。

由于開(kāi)發(fā)與探索間的比例關(guān)系依賴具體問(wèn)題，針對(duì)不同問(wèn)題有不同的比例選擇，因此設(shè)計(jì)在UCB公式探索項(xiàng)部分引入平衡系數(shù)C，以動(dòng)態(tài)地改變開(kāi)發(fā)和探索間的比例關(guān)系。同時(shí)在針對(duì)時(shí)間受限N值較小情況下，探索項(xiàng)對(duì)整體評(píng)價(jià)影響大、探索收斂速度慢等問(wèn)題，引入貪心系數(shù)G，對(duì)仿真方向進(jìn)行引導(dǎo)，加速收斂過(guò)程，減少冗余計(jì)算。

改進(jìn)后的公式如下所示：

應(yīng)用UCB公式的UCT算法在搜索策略上類似廣度優(yōu)先遍歷，通過(guò)在同一廣度方向上的不斷向下延展保證UCB值的準(zhǔn)確性;而延展的深度則決定估值函數(shù)評(píng)估值的準(zhǔn)確性，直接影響UCB公式前項(xiàng)Xi值。加大搜索深度，意味著單次仿真時(shí)間呈指數(shù)級(jí)增長(zhǎng)，仿真次數(shù)N大幅下降，后項(xiàng)式對(duì)UCB值的影響幅度增大。通過(guò)設(shè)計(jì)時(shí)間參數(shù)h，直接影響仿真次數(shù);設(shè)計(jì)深度參數(shù)t調(diào)整搜索深度，間接影響仿真次數(shù)。要在可接受的時(shí)間范圍內(nèi)平衡仿真次數(shù)和搜索深度，就需要針對(duì)不同模型進(jìn)行大量的測(cè)試和參數(shù)調(diào)整。

算法1 加入時(shí)間參數(shù)t和深度參數(shù)h的優(yōu)化算法

輸入：當(dāng)前局面信息。

輸出：最優(yōu)解對(duì)應(yīng)邊。

1） 以當(dāng)前局面創(chuàng)建根節(jié)點(diǎn)root

2） while 有時(shí)間剩余t

3） Node <- Node_root

4） while 當(dāng)前搜索深度 < h and 非葉節(jié)點(diǎn)

5） 為當(dāng)前Node節(jié)點(diǎn)創(chuàng)建子節(jié)點(diǎn)

6） 使用公式（2）計(jì)算每個(gè)子節(jié)點(diǎn)UCBi值

7） Node <- 使UCBi值最大化的子節(jié)點(diǎn)

8） end while

9） 使用估值函數(shù)對(duì)當(dāng)前Node給出客觀評(píng)價(jià)值value

10） while Node ！= root

11） 更新Node節(jié)點(diǎn)在公式（2）中的Xi值

12） Node <- 父節(jié)點(diǎn)

13） end while

14） end while

15）選擇根節(jié)點(diǎn)中使公式（2）UCBi值最大化的子節(jié)點(diǎn)對(duì)應(yīng)邊輸出

1.2 探索方向控制策略

UCT 的任意時(shí)間終止特性是傳統(tǒng)的搜索算法所無(wú)法比擬的[10]。它可以在算法執(zhí)行過(guò)程中的任何時(shí)間突然終止算法，并返回一個(gè)較理想的結(jié)果。當(dāng)然如果給予更為充分的時(shí)間的話，算法結(jié)果會(huì)非常逼近實(shí)際的最優(yōu)值。但這一點(diǎn)在α-β搜索中是絕對(duì)行不通的，當(dāng)使用迭代控制突然中斷α-β搜索程序時(shí)，某些處于根節(jié)點(diǎn)之下第一層的節(jié)點(diǎn)甚至可能還沒(méi)有被探索過(guò)，此時(shí)搜索程序返回的結(jié)果和實(shí)際的最優(yōu)解相距甚遠(yuǎn)。

利用UCT算法可以在任何時(shí)刻直接終止的特性，本文提出一種探索方向控制策略，當(dāng)判斷程序已經(jīng)得到當(dāng)前最優(yōu)解時(shí)提前終止算法，以減少冗余計(jì)算，間接加大搜索深度。

UCT算法可以直接通過(guò)仿真探索方向來(lái)判斷是否已經(jīng)找到最優(yōu)分支。不同于剪枝搜索算法找到最優(yōu)解的策略，UCT算法的核心目的是找到最優(yōu)分支。針對(duì)UCB公式，隨著某一分支探索次數(shù)的增加，探索項(xiàng)調(diào)整值的大小會(huì)逐漸趨近于0，公式UCB值也越來(lái)越接近該分支的真實(shí)評(píng)估值。

在到達(dá)一定仿真次數(shù)后（蒙特卡洛算法具有統(tǒng)計(jì)性質(zhì)，必須保證一定的統(tǒng)計(jì)量UCB值才具有較高的可信度），某一分支被多次仿真UCB值仍高居不下，認(rèn)為收斂過(guò)程已經(jīng)完成并判斷該分支為最優(yōu)分支。如果算法已經(jīng)計(jì)算出了當(dāng)前的最優(yōu)分支，則其UCB值僅前項(xiàng)Xi值就應(yīng)遠(yuǎn)大于剩余分支綜合評(píng)價(jià)UCB值，算法的仿真方向也被一直引導(dǎo)向該分支探索，此時(shí)剩余時(shí)間內(nèi)的探索將均被限制在該分支，對(duì)該分支后續(xù)的探索也不會(huì)影響根節(jié)點(diǎn)的決斷，成為不必要的冗余計(jì)算，此時(shí)可以直接終止算法。

1.3 二進(jìn)制壓縮技術(shù)

二進(jìn)制壓縮技術(shù)[11]可以將棋盤矩陣轉(zhuǎn)換成位圖存儲(chǔ)，有效減少存儲(chǔ)空間，減小算法的內(nèi)存壓力，為并行化提供保障。其實(shí)現(xiàn)原理是將復(fù)雜數(shù)據(jù)結(jié)構(gòu)表示的棋盤矩陣抽象、分離成多個(gè)bool數(shù)組，對(duì)數(shù)組中的數(shù)據(jù)分別予以不同權(quán)值，壓縮成多個(gè)二進(jìn)制數(shù)表示。

對(duì)于一個(gè)m×n大小的棋盤，首先對(duì)棋盤上所有的點(diǎn)位編號(hào)為1至m×n號(hào)，對(duì)第i號(hào)點(diǎn)賦予權(quán)值2i-1，k表示當(dāng)前點(diǎn)的二進(jìn)制狀態(tài)，并利用如下公式計(jì)算出bool矩陣的二進(jìn)制壓縮值：

由于多數(shù)非完全信息博弈棋盤較大，無(wú)法壓縮存儲(chǔ)在一個(gè)二進(jìn)制數(shù)中，實(shí)際使用時(shí)需分別用多個(gè)二進(jìn)制數(shù)表示一組點(diǎn)。以c++編程為例，其語(yǔ)法定義的無(wú)符號(hào)長(zhǎng)整型最大存儲(chǔ)長(zhǎng)度為8字節(jié)，所以將相鄰64個(gè)點(diǎn)劃分為一組進(jìn)行壓縮。此時(shí)壓縮值遞推公式如下：

式中m、n分別表示被壓縮棋盤的長(zhǎng)和寬，t表示壓縮所需的二進(jìn)制數(shù)下標(biāo)最大值，B0至Bt分別表示對(duì)應(yīng)點(diǎn)組的壓縮值。最終將m×n大小的bool矩陣壓縮成t+1個(gè)長(zhǎng)整型數(shù)。

以圍棋棋盤為例，它是一個(gè)二維19×19的三狀態(tài)數(shù)組，三種狀態(tài)分別是該點(diǎn)未被填子、被黑棋填子和被白棋填子。首先將棋盤數(shù)組的三種狀態(tài)分離，設(shè)黑棋所占點(diǎn)位和白棋所占點(diǎn)位兩個(gè)二維兩狀態(tài)矩陣，矩陣的大小為19×19，其對(duì)應(yīng)項(xiàng)表示原始棋盤上該點(diǎn)有沒(méi)有被黑棋（白棋）填子，0表示未被占領(lǐng)1表示被黑棋（白棋）填子，兩數(shù)組相加值為0的部分即為未被黑白雙方填子的部分，這樣就把一個(gè)復(fù)雜的int數(shù)組轉(zhuǎn)化成了兩個(gè)bool數(shù)組。取m、n等于19，利用公式（3）計(jì)算出t值為5，分別用B0至Bt公式組計(jì)算出黑棋、白棋點(diǎn)位矩陣的壓縮值即可。這樣就把一個(gè)19×19大小的二維三狀態(tài)矩陣壓縮成了12個(gè)長(zhǎng)整數(shù)，存儲(chǔ)效率提升93%。

對(duì)于二進(jìn)制壓縮技術(shù)，其優(yōu)勢(shì)在于使棋盤占用存儲(chǔ)空間下降，壓縮效率高，且以位圖方式存儲(chǔ)，在轉(zhuǎn)移出原始棋盤時(shí)不會(huì)損失局面信息。該技術(shù)主要適用于棋盤規(guī)模大，棋子狀態(tài)（種類）少的棋類局面存儲(chǔ)中，棋盤規(guī)模越大，棋子狀態(tài)越少，壓縮效率越高。但對(duì)于小規(guī)模多狀態(tài)棋類棋盤，如國(guó)際象棋、象棋等棋子種類較多的棋類，原始棋盤分離狀態(tài)后轉(zhuǎn)化的bool矩陣數(shù)量過(guò)多，壓縮的效率會(huì)大幅下降。

1.4 并行化處理

UCT算法主要以模擬對(duì)局為主，每次選擇、擴(kuò)展、模擬、回溯的過(guò)程相對(duì)獨(dú)立[12]，所以將其做并行化處理，每一個(gè)線程負(fù)責(zé)一次UCT模擬過(guò)程，共同維護(hù)更新同一棵搜索樹(shù)[13]。

在擁有多個(gè)CPU核心的情況下，通過(guò)并行的展開(kāi)多個(gè)線程，分別進(jìn)行不同對(duì)局模擬。某一線程在模擬完成后，先給公共資源區(qū)（整棵博弈樹(shù)）加X(jué)鎖，修改部分節(jié)點(diǎn)UCB值，該線程再展開(kāi)下一輪模擬。這一過(guò)程中不需要訪問(wèn)博弈樹(shù)的線程仍可以繼續(xù)工作。

對(duì)于傳統(tǒng)剪枝函數(shù)，它不像UCT仿真在整次模擬結(jié)束后才更新節(jié)點(diǎn)權(quán)值，而是在每一次回溯時(shí)更新父節(jié)點(diǎn)權(quán)值。在做并行化時(shí)，它的每一個(gè)線程對(duì)公共資源區(qū)的訪問(wèn)頻率更高，導(dǎo)致公共資源區(qū)被頻繁加鎖，其他線程等待時(shí)間增加，CPU利用率下降。也是由于鎖機(jī)制的存在，實(shí)際應(yīng)用中每次模擬并不完全獨(dú)立，因而性能的優(yōu)化效果會(huì)有所減弱。

因?yàn)镃PU進(jìn)程調(diào)度的不可預(yù)知性，無(wú)法預(yù)知什么時(shí)候會(huì)出現(xiàn)死鎖。而現(xiàn)在大多數(shù)博弈程序均采用前后端分離的設(shè)計(jì)模式，前端界面只負(fù)責(zé)接受對(duì)方和己方走棋輸入，后端進(jìn)行下一步走棋的計(jì)算。為預(yù)防算法因死鎖崩潰的情況發(fā)生，本文利用二進(jìn)制壓縮技術(shù)局面存儲(chǔ)數(shù)據(jù)量小且能轉(zhuǎn)譯出完整棋盤的特點(diǎn)，設(shè)計(jì)前端重傳請(qǐng)求算法，在超過(guò)規(guī)定時(shí)限未收到后端回復(fù)時(shí)即認(rèn)為并行算法部分發(fā)生死鎖，前端重傳一次局面參數(shù)，重新請(qǐng)求后端做并行計(jì)算，因而不會(huì)因死鎖而導(dǎo)致整個(gè)博弈程序的崩潰。后端算法也需完成局面與過(guò)程的分離，在接受任意一個(gè)局面輸入的情況下計(jì)算下一步，而不依賴之前的博弈過(guò)程。

在算法完成并行化處理后，對(duì)內(nèi)存的需求量大大提升，而二進(jìn)制壓縮技術(shù)也很好地提供了一種能在不損失任何局面特征情況下的棋盤壓縮存儲(chǔ)方式，成功減小內(nèi)存壓力，為算法的并行化提供了切實(shí)保障。

2 完全信息博弈三階段模型

本章針對(duì)完全信息博弈中搜索時(shí)間受限的算法設(shè)計(jì)問(wèn)題，將整個(gè)博弈過(guò)程分為開(kāi)局 、中局和殘局三個(gè)階段[14]。

2.1 開(kāi)局——UCT模擬結(jié)合貪心選擇策略

博弈開(kāi)局走法較多，局面形勢(shì)不明朗，且各種走法差異性較小，隨機(jī)因素較大。而貪心算法時(shí)間復(fù)雜度小，效率高[15]，盡管求解可能是局部最優(yōu)解但仍遠(yuǎn)強(qiáng)于隨機(jī)。因此開(kāi)局階段設(shè)計(jì)以UCT算法為主，結(jié)合貪心選擇策略作為蒙特卡洛模擬方向的引導(dǎo)，力求在短時(shí)間內(nèi)計(jì)算出一個(gè)可接受的次優(yōu)解。

當(dāng)設(shè)計(jì)者以人類經(jīng)驗(yàn)判斷某步棋優(yōu)勢(shì)或劣勢(shì)時(shí)（比如圍棋的送入虎口、國(guó)際象棋的送后），通過(guò)修改公式（2）中的貪心系數(shù)G來(lái)控制UCT仿真方向，使探索策略偏向探索優(yōu)勢(shì)步，盡量不去模擬劣勢(shì)步以減少無(wú)意義的冗余計(jì)算。貪心算法的時(shí)間復(fù)雜度一般在常數(shù)級(jí)別，耗時(shí)可以忽略不計(jì)，不會(huì)影響后續(xù)UCT算法的仿真時(shí)間。

這是一種基于修正收益值的貪心策略，借由人類經(jīng)驗(yàn)來(lái)修正UCB值來(lái)引導(dǎo)仿真方向。但這種方式在中殘局并不適用，因?yàn)檫@兩階段存在很多棄子搶先的技術(shù)存在，貪心策略會(huì)影響程序?qū)置娴呐袛唷?/p>

2.2 中局——優(yōu)化UCT模擬

中局階段是分勝負(fù)的關(guān)鍵階段，在這個(gè)階段，局面復(fù)雜走法多樣，但每一步的處理都會(huì)對(duì)后續(xù)的局面發(fā)展產(chǎn)生很大的影響。在這一階段可以采用優(yōu)化UCT算法，充分利用開(kāi)局和殘局階段節(jié)省的時(shí)間，在關(guān)鍵步予以較長(zhǎng)的運(yùn)算時(shí)間。

但即便在三階段中，中局階段分配了最長(zhǎng)的時(shí)限，也無(wú)法做到模擬完整個(gè)對(duì)局的同時(shí)保證對(duì)局?jǐn)?shù)量，所以仍需考慮搜索深度與統(tǒng)計(jì)數(shù)據(jù)量的平衡問(wèn)題?？紤]到UCT算法對(duì)估值函數(shù)的依賴性較小，可以中和部分估值函數(shù)錯(cuò)誤帶來(lái)的誤差影響（對(duì)某一次探索的錯(cuò)誤判斷不會(huì)大幅影響對(duì)該分支的UCB評(píng)價(jià)值），隨著中局的深入搜索深度可以慢慢減小。

初入中局時(shí)應(yīng)以探索為主，通過(guò)使改進(jìn)UCB公式中平衡系數(shù)C取較大的值，以獲得更大的搜索廣度，盡可能給每一種走法以探索的機(jī)會(huì)，同時(shí)避免因單次仿真效果不佳而導(dǎo)致某一分支整體仿真次數(shù)過(guò)少的情況發(fā)生;隨著游戲的進(jìn)行，探索與開(kāi)發(fā)的天平逐漸向開(kāi)發(fā)傾斜，單次仿真搜索的深度要慢慢增加，減少在不必要的分支產(chǎn)生過(guò)多的冗余計(jì)算，因此C值應(yīng)逐漸減小。此時(shí)隨著UCB公式的收斂，探索方向也慢慢集中，增加的仿真對(duì)局?jǐn)?shù)也均限制在某幾步可能的最優(yōu)解中，算法的效率提升明顯。

中局階段存在關(guān)鍵步的問(wèn)題，而關(guān)鍵步也是整盤棋的勝負(fù)手。關(guān)鍵步走后將出現(xiàn)兩極分化現(xiàn)象，選擇的節(jié)點(diǎn)UCB值要么趨近正無(wú)窮要么幾乎為0（針對(duì)不存在和棋的完全信息博弈類游戲），游戲勝負(fù)已分。目前仍無(wú)法人為找出關(guān)鍵步的原理和具體數(shù)量，能進(jìn)行處理的主要是對(duì)關(guān)鍵步位置的測(cè)試和對(duì)該位置參數(shù)的調(diào)整，增加時(shí)限的分配和加大搜索深度等。

2.3殘局——α-β剪枝

在整盤棋接近尾聲時(shí)放棄UCT算法，選用α-β剪枝算法以節(jié)省時(shí)間，提高搜索效率。

殘局階段的處理較為簡(jiǎn)單，在博弈樹(shù)規(guī)模急劇減小，接近完全搜索（暴力破解）可達(dá)范圍時(shí)，只需選擇能最快搜索到較高深度的算法即可。由于蒙特卡洛算法的統(tǒng)計(jì)特性，在樣本量過(guò)少的情況下容易出現(xiàn)誤判（比如因UCB公式調(diào)整項(xiàng)過(guò)大引起的誤差），而保證樣本量又需要一定的仿真時(shí)間。反觀剪枝算法，它搜索時(shí)每個(gè)局面只模擬一次的優(yōu)勢(shì)在殘局體現(xiàn)了出來(lái)，在接近殘局時(shí)估值函數(shù)準(zhǔn)確性極高，或者說(shuō)已經(jīng)可以計(jì)算到最終局面就不需要估值函數(shù)了。當(dāng)計(jì)算結(jié)果準(zhǔn)確性提高上來(lái)后，剪枝算法速度快，耗時(shí)少，探索局面不重復(fù)且不會(huì)出現(xiàn)未探索到某種局面的情況，所以在殘局時(shí)選擇剪枝算法中效果最好的α-β剪枝算法。

3 分階段優(yōu)化博弈模型

上述算法改進(jìn)策略及三階段模型均以點(diǎn)格棋為平臺(tái)實(shí)現(xiàn)并進(jìn)行優(yōu)化。

3.1 具體階段劃分與時(shí)間分配策略

（1）開(kāi)局階段

開(kāi)局階段主要指10步以前的走法，此時(shí)局面形勢(shì)不明朗，制勝的關(guān)鍵長(zhǎng)鏈未形成，走法的隨機(jī)性較大。

先將所有邊分為以下幾類：

1）非法邊，已落過(guò)子的邊，不可選擇

2）得子邊，可以得子的邊

3） 失子邊，使對(duì)手下一步得子的邊

4）長(zhǎng)鏈邊，長(zhǎng)鏈中的得子邊

5）其它邊

這其中第四類長(zhǎng)鏈邊雖然也屬于得子邊，但其相對(duì)復(fù)雜，涉及放棄得子強(qiáng)迫換手的操作，所以無(wú)法和第二類邊歸為一類討論。不過(guò)因?yàn)殚_(kāi)局階段長(zhǎng)鏈尚未形成，可以大膽假設(shè)在10步之前不存在第四類邊，那么允許的選擇就被限制在了得子邊、失子邊和其它邊。

根據(jù)貪心策略將邊的優(yōu)先級(jí)設(shè)為得子邊>其他邊>失子邊，對(duì)得子邊UCB公式中的貪心系數(shù)G取0.2，對(duì)失子邊G取-0.05，其余邊G取0。對(duì)于優(yōu)勢(shì)走法，應(yīng)給予合理的收益值加成;但對(duì)于劣勢(shì)走法只做少許的收益修正，既降低該邊的評(píng)估值從而減少模擬次數(shù)，又不至于過(guò)分影響調(diào)整項(xiàng) 使得算法持續(xù)忽略對(duì)該分支的模擬。這樣就通過(guò)直接影響UCB公式強(qiáng)制加快算法收斂速度，在不超過(guò)十秒的極短時(shí)限內(nèi)獲得一個(gè)優(yōu)于純UCT模擬的次優(yōu)解。

開(kāi)局階段不采用改進(jìn)UCB公式中的開(kāi)發(fā)探索平衡系數(shù)C（取C=1），此時(shí)開(kāi)發(fā)與探索接近平衡即可，無(wú)需過(guò)度追求廣度上的均衡，也無(wú)須通過(guò)減小C值提前收斂。

（2）中局階段

中期局面的階段劃分相對(duì)復(fù)雜。根據(jù)以往下棋和比賽的經(jīng)驗(yàn)分析，點(diǎn)格棋大概在20步進(jìn)入中局，24-30步完成棋盤整個(gè)布局，形成制勝的長(zhǎng)鏈，此后已經(jīng)基本可以判斷勝負(fù)了。但在20步之前，一方可以選擇棄子斷鏈、換手等技術(shù)，引導(dǎo)對(duì)手在中局形成對(duì)己方有利的布局。

所以本文將中局布局的概念提前到16步，認(rèn)為16-20步為引導(dǎo)中局形勢(shì)變化的關(guān)鍵步，分配較長(zhǎng)的仿真時(shí)間，加大局面搜索深度，大量模擬該階段的布局，盡可能選取有利的分支。對(duì)于UCB公式的使用，中局階段直接舍棄貪心系數(shù)G，以防對(duì)手通過(guò)棄子斷鏈等技術(shù)引導(dǎo)我方陷入不利布局。而對(duì)于平衡系數(shù)C，采取緩慢減少的策略，從剛進(jìn)入中局布局的10-16步以探索為主，到中局關(guān)鍵步以對(duì)關(guān)鍵分支的開(kāi)發(fā)為主，通過(guò)快速減小C值將函數(shù)收斂，模擬方向集中。

在中局16-20步關(guān)鍵步過(guò)后，局面呈兩極分化，勝率要么接近正無(wú)窮要么幾乎為0（UCT算法中采用節(jié)點(diǎn)的UCB值即為勝率），可見(jiàn)前文對(duì)關(guān)鍵步的處理是非常正確的。那么在中局后續(xù)階段，只需保持上一階段最后使用的C值大小，慢慢增加搜索深度（隨局面深入算法復(fù)雜度減小）。

對(duì)于時(shí)間分配，在中局階段采取內(nèi)部細(xì)分階段的策略，關(guān)鍵步分配超過(guò)兩分鐘的時(shí)限，而在其余步分配30-60s的時(shí)限不等，通過(guò)較長(zhǎng)的時(shí)限分配來(lái)保證關(guān)鍵步的質(zhì)量。通過(guò)實(shí)驗(yàn)觀察，受平衡系數(shù)C及時(shí)間分配策略影響10-16步UCT仿真次數(shù)在5W次左右，而在關(guān)鍵步16-24仿真次數(shù)超過(guò)55W次。

（3）殘局階段

殘局階段主要指30步以后的走法，此時(shí)可以通過(guò)等價(jià)邊裁剪[16]的方式，提升剪枝算法的效率，更早的完成對(duì)局面的完全搜索。

在上述情況中，虛線所示的邊均為等價(jià)邊，走其中一條和另一條或多條的效果相同，在探索時(shí)僅需探索其中一條，剪掉其余等價(jià)邊所在分支即可。

在殘局階段，長(zhǎng)鏈基本完全形成，局面上存在大量等價(jià)邊，原本高達(dá)30的階乘的算法復(fù)雜度很可能在高效剪枝的情況下減少至15的階乘甚至進(jìn)入完全搜索可達(dá)的范圍，幾乎不存在估值函數(shù)誤差對(duì)剪枝算法帶來(lái)的影響。

3.2 二進(jìn)制壓縮技術(shù)應(yīng)用

對(duì)于點(diǎn)格棋棋盤，先將60條邊按水平邊和縱邊進(jìn)行分類，分別進(jìn)行編號(hào)H1-H30和V1-V30。設(shè)二進(jìn)制數(shù)H、V，H的第一位表示H1的狀態(tài)，V的第一位表示V1的狀態(tài)，已被占領(lǐng)為1，未被占領(lǐng)為0，通過(guò)這種轉(zhuǎn)換來(lái)構(gòu)成這兩個(gè)30位長(zhǎng)的二進(jìn)制數(shù)H、V。

在計(jì)算時(shí)首先對(duì)H1-H30和V1-V30邊分別賦予一個(gè)固定權(quán)值，n號(hào)邊對(duì)應(yīng)權(quán)值為2n-1，k表示當(dāng)前邊的狀態(tài)，利用如下公式分別計(jì)算H和V的值：

其中H、V分別存儲(chǔ)當(dāng)前局面邊的狀態(tài)，S數(shù)組分別存儲(chǔ)己方和對(duì)方占據(jù)的格子數(shù)，Turn用來(lái)表示輪到哪一方走棋。通過(guò)二進(jìn)制壓縮技術(shù)，將棋盤存儲(chǔ)最小化和唯一表示，同時(shí)不損失任何特征信息。

3.3 并行化優(yōu)化

在利用二進(jìn)制壓縮技術(shù)處理棋盤后，將其做并行化處理。

定義博弈樹(shù)中節(jié)點(diǎn)結(jié)構(gòu)：

其中rwMutex為節(jié)點(diǎn)的讀寫(xiě)鎖，parent指向父節(jié)點(diǎn)，board存儲(chǔ)當(dāng)前節(jié)點(diǎn)局面。為保證節(jié)點(diǎn)的數(shù)據(jù)安全，當(dāng)欲訪問(wèn)某節(jié)點(diǎn)時(shí)需要獲得它的鎖和其父節(jié)點(diǎn)的鎖（若不為根節(jié)點(diǎn)）。因?yàn)楸仨毻瑫r(shí)得到訪問(wèn)節(jié)點(diǎn)和其父節(jié)點(diǎn)的鎖，才能保證訪問(wèn)的節(jié)點(diǎn)和其兄弟節(jié)點(diǎn)在選擇、擴(kuò)展時(shí)不被修改。

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

測(cè)試棋盤大小為6×6，比賽單方總時(shí)限為15分鐘。6×6點(diǎn)格棋棋盤共60條邊，假設(shè)一方走30步（會(huì)有得子連走情況，一方走棋未必為30步），單步時(shí)限為15分鐘/30步，即30s。

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

4.1 與α-β剪枝算法程序?qū)?/p>

將基于點(diǎn)格棋設(shè)計(jì)的優(yōu)化UCT三階段模型（下簡(jiǎn)稱三階段模型）與使用相同估值函數(shù)的α-β剪枝算法對(duì)弈。

可以看出在估值函數(shù)不穩(wěn)定且均使用相同估值函數(shù)時(shí)，UCT算法能明顯規(guī)避誤差，顯著提高勝率。

4.2 與深度學(xué)習(xí)算法訓(xùn)練的神經(jīng)網(wǎng)絡(luò)模型對(duì)弈

與使用深度學(xué)習(xí)訓(xùn)練，水平相當(dāng)于單步搜索500次純蒙特卡洛算法的神經(jīng)網(wǎng)絡(luò)模型對(duì)弈。

深度學(xué)習(xí)的神經(jīng)網(wǎng)絡(luò)訓(xùn)練嚴(yán)重受限于外部條件，包括樣本質(zhì)量、數(shù)量，硬件設(shè)備和訓(xùn)練時(shí)間等，效果遠(yuǎn)不如UCT算法。

4.3 優(yōu)化后的UCT算法測(cè)試

優(yōu)化UCT算法不再采用統(tǒng)一分配每步時(shí)限，而是采用集中式統(tǒng)籌分配時(shí)間策略，所以不再為其設(shè)置單步時(shí)限。三階段模型中采用貪心策略、二進(jìn)制壓縮技術(shù)、α-β剪枝以及多種控制策略優(yōu)化的UCT算法與純UCT算法（均完成并行化），在使用相同估值函數(shù)的情況下進(jìn)行對(duì)弈。

優(yōu)化UCT算法對(duì)整個(gè)博弈程序的棋力提高效果顯著。

5 結(jié)束語(yǔ)

計(jì)算機(jī)博弈是一個(gè)復(fù)雜和具有挑戰(zhàn)的課題，對(duì)與博弈論的學(xué)習(xí)和研究具有深遠(yuǎn)的意義。本文提出了一種針對(duì)完全信息博弈的三階段模型，在多領(lǐng)域完全信息博弈問(wèn)題中具有很強(qiáng)的通用性和實(shí)用性。并針對(duì)UCT算法提出了改進(jìn)UCB公式、方向引導(dǎo)控制策略、多種算法混合、二進(jìn)制壓縮和并行化處理等多種優(yōu)化策略，完成了基于點(diǎn)格棋項(xiàng)目的算法實(shí)現(xiàn)，效果非常不錯(cuò)。

此次研究雖小有成果，但仍存在一些不足有待進(jìn)一步的研究和改進(jìn)，其中最主要就是對(duì)估值函數(shù)的處理。無(wú)論是蒙特卡洛算法還是傳統(tǒng)剪枝算法，都無(wú)法擺脫程序本身對(duì)估值函數(shù)的依賴，估值函數(shù)的好壞也完全左右程序棋力的強(qiáng)弱。而目前大部分估值函數(shù)仍舊由專家給出，嚴(yán)重依賴專家的水平，AI也無(wú)法擺脫“人”的影響，實(shí)現(xiàn)真正的智能。

目前非深度學(xué)習(xí)算法有兩個(gè)方向發(fā)展前景較好：

1）從算法設(shè)計(jì)角度減小估值函數(shù)不穩(wěn)定帶來(lái)的影響;

2）使用神經(jīng)網(wǎng)絡(luò)訓(xùn)練得出估值函數(shù)。

前者只能減小估值函數(shù)的影響，如UCT算法，治標(biāo)不治本，但成效快效果好;而后者需要大量數(shù)據(jù)集進(jìn)行訓(xùn)練，耗時(shí)久且對(duì)硬件要求高，在沒(méi)有高算力計(jì)算機(jī)的情況下很難出效果。

上文所述棋盤二進(jìn)制壓縮理論，最初的設(shè)想不僅是用于節(jié)省內(nèi)存和便于通信，還準(zhǔn)備將其作為人工神經(jīng)網(wǎng)絡(luò)的輸入進(jìn)行訓(xùn)練。二進(jìn)制壓縮棋盤數(shù)據(jù)的另一優(yōu)勢(shì)在于沒(méi)有信息丟失，每個(gè)輸入唯一對(duì)應(yīng)于一種局面狀態(tài)，但問(wèn)題是輸入信息量大，網(wǎng)絡(luò)規(guī)模大，運(yùn)算速度慢，訓(xùn)練難度大;如果使用傳統(tǒng)特征提取作為輸入，那么必定存在信息丟失，雖然能減小網(wǎng)絡(luò)規(guī)模、加快訓(xùn)練速度，訓(xùn)練效果肯定不如前者。

受各種條件限制，本文最終著眼于從博弈模型劃分、算法性能優(yōu)化角度入手，弱化估值函數(shù)帶來(lái)的影響，沒(méi)有使用人工神經(jīng)網(wǎng)絡(luò)。

參考文獻(xiàn)：

[1] 王元卓，于建業(yè)，邱雯，等.網(wǎng)絡(luò)群體行為的演化博弈模型與分析方法[J].計(jì)算機(jī)學(xué)報(bào)，2015，38（2）：282-300.

[2] SandholmT.Thestate of solving large incomplete-information games，andapplication to poker[J].AI Magazine，2010，31（4）：13-32.

[3] O. Baran， M. Kasal. Modeling of the Simultaneous Influence of the Thermal Noise and the Phase Noise in Space Communication Systems[J]. Radioengineering， 2010， 19（4）.

[4] Knuth D E，Moore R W.An analysis of alpha-beta pruning[J].Artificial Intelligence，1975，6（4）：293-326.

[5] Silver D，HuangA，Maddison C J，etal.Mastering the game of Go with deep neural networks and tree search[J].Nature，2016，529（7587）：484-489.

[6] 季輝，丁澤軍.雙人博弈問(wèn)題中的蒙特卡洛樹(shù)搜索算法的改進(jìn)[J].計(jì)算機(jī)科學(xué)，2018，45（1）：140-143.

[7] Gelly S， Wang Y， Teytaud O， et al. Modification of UCT with patterns in Monte-Carlo Go[J]. 2006..

[8] Auer P，Cesa-Bianchi N，F(xiàn)ischerP.Finite-time analysis of the multiarmed bandit problem[J].Machine Learning，2002，47（2/3）：235-256.

[9] Gelly S， Wang Y. Exploration exploitation in go： UCT for Monte-Carlo go[C]//NIPS： Neural Information Processing Systems Conference On-line trading of Exploration and Exploitation Workshop. 2006.

[10] YimengZhuang. Improving Monte-Carlo tree search for dots-and-boxes with a novel board representation and artificial neural networks[J]. IEEE CIG， 2015：314-321.

[11] KamstraL.The design of linear binary wavelet transforms and their application to binary image compression[C]//2003，3：241-244.

[12] Coquelin， Pierre-Arnaud， and RmiMunos.Bandit algorithms for treesearch[J].arXiv preprint cs/0703062 （2007）

[13]Chaslot G M J B，Winands M H M，Van Den H J ， et al.Parallel Monte-Carlo tree search[J]. Lecture Notes in Computer Science，2008， 5131：60-71.

[14] 徐心和，王驕.中國(guó)象棋計(jì)算機(jī)博弈關(guān)鍵技術(shù)分析[J].小型微型計(jì)算機(jī)系統(tǒng)，2006，27（6）：961-969.

[15] Wei XJ，Ye PX.Efficiency of orthogonal super greedy algorithm under the restricted isometry property[J].Journal of Inequalities and Applications，2019，2019：124.

[16] 丁濛，張亦鵬，李淑琴.棋盤局面數(shù)據(jù)標(biāo)定方法研究[J].計(jì)算機(jī)應(yīng)用研究，2020，37（2）：470-472.

【通聯(lián)編輯：光文玲】