面向搜索時間受限的完全信息博弈UCT算法改進研究

張宜放　孟坤　蔣志文　高世靜　張蘊瀚

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

關鍵詞：UCT算法優化;三階段模型;點格棋

中圖分類號：TP301.6? ? ? 文獻標識碼：A

文章編號：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

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

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

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

1 UCT算法優化

1.1 公式改進——引入平衡系數和貪心系數

UCB公式最初是針對K臂賭博機問題提出的[8]，目的是平衡開發與探索之間的關系。應用于博弈領域時，在以當前局面為根節點建立的博弈樹中共有i個分支，用UCBi表示對第i個分支的評估值。

式中，Xi為第i個分支的平均收益值，Ti為第i個分支被探索的次數，N為總探索次數。公式中前項Xi為開發項，表示該分支過去開發的平均表現，后項式[2lnNTi]為探索項調整值，表示該分支被探索的價值，最終通過開發項和探索項的加和作為當前該分支的綜合評價值，來平衡開發與探索之間的關系[9]。

由于開發與探索間的比例關系依賴具體問題，針對不同問題有不同的比例選擇，因此設計在UCB公式探索項部分引入平衡系數C，以動態地改變開發和探索間的比例關系。同時在針對時間受限N值較小情況下，探索項對整體評價影響大、探索收斂速度慢等問題，引入貪心系數G，對仿真方向進行引導，加速收斂過程，減少冗余計算。

改進后的公式如下所示：

應用UCB公式的UCT算法在搜索策略上類似廣度優先遍歷，通過在同一廣度方向上的不斷向下延展保證UCB值的準確性;而延展的深度則決定估值函數評估值的準確性，直接影響UCB公式前項Xi值。加大搜索深度，意味著單次仿真時間呈指數級增長，仿真次數N大幅下降，后項式對UCB值的影響幅度增大。通過設計時間參數h，直接影響仿真次數;設計深度參數t調整搜索深度，間接影響仿真次數。要在可接受的時間范圍內平衡仿真次數和搜索深度，就需要針對不同模型進行大量的測試和參數調整。

算法1 加入時間參數t和深度參數h的優化算法

輸入：當前局面信息。

輸出：最優解對應邊。

1） 以當前局面創建根節點root

2） while 有時間剩余t

3） Node <- Node_root

4） while 當前搜索深度 < h and 非葉節點

5） 為當前Node節點創建子節點

6） 使用公式（2）計算每個子節點UCBi值

7） Node <- 使UCBi值最大化的子節點

8） end while

9） 使用估值函數對當前Node給出客觀評價值value

10） while Node ！= root

11） 更新Node節點在公式（2）中的Xi值

12） Node <- 父節點

13） end while

14） end while

15）選擇根節點中使公式（2）UCBi值最大化的子節點對應邊輸出

1.2 探索方向控制策略

UCT 的任意時間終止特性是傳統的搜索算法所無法比擬的[10]。它可以在算法執行過程中的任何時間突然終止算法，并返回一個較理想的結果。當然如果給予更為充分的時間的話，算法結果會非常逼近實際的最優值。但這一點在α-β搜索中是絕對行不通的，當使用迭代控制突然中斷α-β搜索程序時，某些處于根節點之下第一層的節點甚至可能還沒有被探索過，此時搜索程序返回的結果和實際的最優解相距甚遠。

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

UCT算法可以直接通過仿真探索方向來判斷是否已經找到最優分支。不同于剪枝搜索算法找到最優解的策略，UCT算法的核心目的是找到最優分支。針對UCB公式，隨著某一分支探索次數的增加，探索項調整值的大小會逐漸趨近于0，公式UCB值也越來越接近該分支的真實評估值。

在到達一定仿真次數后（蒙特卡洛算法具有統計性質，必須保證一定的統計量UCB值才具有較高的可信度），某一分支被多次仿真UCB值仍高居不下，認為收斂過程已經完成并判斷該分支為最優分支。如果算法已經計算出了當前的最優分支，則其UCB值僅前項Xi值就應遠大于剩余分支綜合評價UCB值，算法的仿真方向也被一直引導向該分支探索，此時剩余時間內的探索將均被限制在該分支，對該分支后續的探索也不會影響根節點的決斷，成為不必要的冗余計算，此時可以直接終止算法。

1.3 二進制壓縮技術

二進制壓縮技術[11]可以將棋盤矩陣轉換成位圖存儲，有效減少存儲空間，減小算法的內存壓力，為并行化提供保障。其實現原理是將復雜數據結構表示的棋盤矩陣抽象、分離成多個bool數組，對數組中的數據分別予以不同權值，壓縮成多個二進制數表示。

對于一個m×n大小的棋盤，首先對棋盤上所有的點位編號為1至m×n號，對第i號點賦予權值2i-1，k表示當前點的二進制狀態，并利用如下公式計算出bool矩陣的二進制壓縮值：

由于多數非完全信息博弈棋盤較大，無法壓縮存儲在一個二進制數中，實際使用時需分別用多個二進制數表示一組點。以c++編程為例，其語法定義的無符號長整型最大存儲長度為8字節，所以將相鄰64個點劃分為一組進行壓縮。此時壓縮值遞推公式如下：

式中m、n分別表示被壓縮棋盤的長和寬，t表示壓縮所需的二進制數下標最大值，B0至Bt分別表示對應點組的壓縮值。最終將m×n大小的bool矩陣壓縮成t+1個長整型數。

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

對于二進制壓縮技術，其優勢在于使棋盤占用存儲空間下降，壓縮效率高，且以位圖方式存儲，在轉移出原始棋盤時不會損失局面信息。該技術主要適用于棋盤規模大，棋子狀態（種類）少的棋類局面存儲中，棋盤規模越大，棋子狀態越少，壓縮效率越高。但對于小規模多狀態棋類棋盤，如國際象棋、象棋等棋子種類較多的棋類，原始棋盤分離狀態后轉化的bool矩陣數量過多，壓縮的效率會大幅下降。

1.4 并行化處理

UCT算法主要以模擬對局為主，每次選擇、擴展、模擬、回溯的過程相對獨立[12]，所以將其做并行化處理，每一個線程負責一次UCT模擬過程，共同維護更新同一棵搜索樹[13]。

在擁有多個CPU核心的情況下，通過并行的展開多個線程，分別進行不同對局模擬。某一線程在模擬完成后，先給公共資源區（整棵博弈樹）加X鎖，修改部分節點UCB值，該線程再展開下一輪模擬。這一過程中不需要訪問博弈樹的線程仍可以繼續工作。

對于傳統剪枝函數，它不像UCT仿真在整次模擬結束后才更新節點權值，而是在每一次回溯時更新父節點權值。在做并行化時，它的每一個線程對公共資源區的訪問頻率更高，導致公共資源區被頻繁加鎖，其他線程等待時間增加，CPU利用率下降。也是由于鎖機制的存在，實際應用中每次模擬并不完全獨立，因而性能的優化效果會有所減弱。

因為CPU進程調度的不可預知性，無法預知什么時候會出現死鎖。而現在大多數博弈程序均采用前后端分離的設計模式，前端界面只負責接受對方和己方走棋輸入，后端進行下一步走棋的計算。為預防算法因死鎖崩潰的情況發生，本文利用二進制壓縮技術局面存儲數據量小且能轉譯出完整棋盤的特點，設計前端重傳請求算法，在超過規定時限未收到后端回復時即認為并行算法部分發生死鎖，前端重傳一次局面參數，重新請求后端做并行計算，因而不會因死鎖而導致整個博弈程序的崩潰。后端算法也需完成局面與過程的分離，在接受任意一個局面輸入的情況下計算下一步，而不依賴之前的博弈過程。

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

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

本章針對完全信息博弈中搜索時間受限的算法設計問題，將整個博弈過程分為開局 、中局和殘局三個階段[14]。

2.1 開局——UCT模擬結合貪心選擇策略

博弈開局走法較多，局面形勢不明朗，且各種走法差異性較小，隨機因素較大。而貪心算法時間復雜度小，效率高[15]，盡管求解可能是局部最優解但仍遠強于隨機。因此開局階段設計以UCT算法為主，結合貪心選擇策略作為蒙特卡洛模擬方向的引導，力求在短時間內計算出一個可接受的次優解。

當設計者以人類經驗判斷某步棋優勢或劣勢時（比如圍棋的送入虎口、國際象棋的送后），通過修改公式（2）中的貪心系數G來控制UCT仿真方向，使探索策略偏向探索優勢步，盡量不去模擬劣勢步以減少無意義的冗余計算。貪心算法的時間復雜度一般在常數級別，耗時可以忽略不計，不會影響后續UCT算法的仿真時間。

這是一種基于修正收益值的貪心策略，借由人類經驗來修正UCB值來引導仿真方向。但這種方式在中殘局并不適用，因為這兩階段存在很多棄子搶先的技術存在，貪心策略會影響程序對局面的判斷。

2.2 中局——優化UCT模擬

中局階段是分勝負的關鍵階段，在這個階段，局面復雜走法多樣，但每一步的處理都會對后續的局面發展產生很大的影響。在這一階段可以采用優化UCT算法，充分利用開局和殘局階段節省的時間，在關鍵步予以較長的運算時間。

但即便在三階段中，中局階段分配了最長的時限，也無法做到模擬完整個對局的同時保證對局數量，所以仍需考慮搜索深度與統計數據量的平衡問題?？紤]到UCT算法對估值函數的依賴性較小，可以中和部分估值函數錯誤帶來的誤差影響（對某一次探索的錯誤判斷不會大幅影響對該分支的UCB評價值），隨著中局的深入搜索深度可以慢慢減小。

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

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

2.3殘局——α-β剪枝

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

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

3 分階段優化博弈模型

上述算法改進策略及三階段模型均以點格棋為平臺實現并進行優化。

3.1 具體階段劃分與時間分配策略

（1）開局階段

開局階段主要指10步以前的走法，此時局面形勢不明朗，制勝的關鍵長鏈未形成，走法的隨機性較大。

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

1）非法邊，已落過子的邊，不可選擇

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

3） 失子邊，使對手下一步得子的邊

4）長鏈邊，長鏈中的得子邊

5）其它邊

這其中第四類長鏈邊雖然也屬于得子邊，但其相對復雜，涉及放棄得子強迫換手的操作，所以無法和第二類邊歸為一類討論。不過因為開局階段長鏈尚未形成，可以大膽假設在10步之前不存在第四類邊，那么允許的選擇就被限制在了得子邊、失子邊和其它邊。

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

開局階段不采用改進UCB公式中的開發探索平衡系數C（取C=1），此時開發與探索接近平衡即可，無需過度追求廣度上的均衡，也無須通過減小C值提前收斂。

（2）中局階段

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

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

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

對于時間分配，在中局階段采取內部細分階段的策略，關鍵步分配超過兩分鐘的時限，而在其余步分配30-60s的時限不等，通過較長的時限分配來保證關鍵步的質量。通過實驗觀察，受平衡系數C及時間分配策略影響10-16步UCT仿真次數在5W次左右，而在關鍵步16-24仿真次數超過55W次。

（3）殘局階段

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

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

在殘局階段，長鏈基本完全形成，局面上存在大量等價邊，原本高達30的階乘的算法復雜度很可能在高效剪枝的情況下減少至15的階乘甚至進入完全搜索可達的范圍，幾乎不存在估值函數誤差對剪枝算法帶來的影響。

3.2 二進制壓縮技術應用

對于點格棋棋盤，先將60條邊按水平邊和縱邊進行分類，分別進行編號H1-H30和V1-V30。設二進制數H、V，H的第一位表示H1的狀態，V的第一位表示V1的狀態，已被占領為1，未被占領為0，通過這種轉換來構成這兩個30位長的二進制數H、V。

在計算時首先對H1-H30和V1-V30邊分別賦予一個固定權值，n號邊對應權值為2n-1，k表示當前邊的狀態，利用如下公式分別計算H和V的值：

其中H、V分別存儲當前局面邊的狀態，S數組分別存儲己方和對方占據的格子數，Turn用來表示輪到哪一方走棋。通過二進制壓縮技術，將棋盤存儲最小化和唯一表示，同時不損失任何特征信息。

3.3 并行化優化

在利用二進制壓縮技術處理棋盤后，將其做并行化處理。

定義博弈樹中節點結構：

其中rwMutex為節點的讀寫鎖，parent指向父節點，board存儲當前節點局面。為保證節點的數據安全，當欲訪問某節點時需要獲得它的鎖和其父節點的鎖（若不為根節點）。因為必須同時得到訪問節點和其父節點的鎖，才能保證訪問的節點和其兄弟節點在選擇、擴展時不被修改。

4 實驗結果與分析

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

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

4.1 與α-β剪枝算法程序對弈

將基于點格棋設計的優化UCT三階段模型（下簡稱三階段模型）與使用相同估值函數的α-β剪枝算法對弈。

可以看出在估值函數不穩定且均使用相同估值函數時，UCT算法能明顯規避誤差，顯著提高勝率。

4.2 與深度學習算法訓練的神經網絡模型對弈

與使用深度學習訓練，水平相當于單步搜索500次純蒙特卡洛算法的神經網絡模型對弈。

深度學習的神經網絡訓練嚴重受限于外部條件，包括樣本質量、數量，硬件設備和訓練時間等，效果遠不如UCT算法。

4.3 優化后的UCT算法測試

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

優化UCT算法對整個博弈程序的棋力提高效果顯著。

5 結束語

計算機博弈是一個復雜和具有挑戰的課題，對與博弈論的學習和研究具有深遠的意義。本文提出了一種針對完全信息博弈的三階段模型，在多領域完全信息博弈問題中具有很強的通用性和實用性。并針對UCT算法提出了改進UCB公式、方向引導控制策略、多種算法混合、二進制壓縮和并行化處理等多種優化策略，完成了基于點格棋項目的算法實現，效果非常不錯。

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

目前非深度學習算法有兩個方向發展前景較好：

1）從算法設計角度減小估值函數不穩定帶來的影響;

2）使用神經網絡訓練得出估值函數。

前者只能減小估值函數的影響，如UCT算法，治標不治本，但成效快效果好;而后者需要大量數據集進行訓練，耗時久且對硬件要求高，在沒有高算力計算機的情況下很難出效果。

上文所述棋盤二進制壓縮理論，最初的設想不僅是用于節省內存和便于通信，還準備將其作為人工神經網絡的輸入進行訓練。二進制壓縮棋盤數據的另一優勢在于沒有信息丟失，每個輸入唯一對應于一種局面狀態，但問題是輸入信息量大，網絡規模大，運算速度慢，訓練難度大;如果使用傳統特征提取作為輸入，那么必定存在信息丟失，雖然能減小網絡規模、加快訓練速度，訓練效果肯定不如前者。

受各種條件限制，本文最終著眼于從博弈模型劃分、算法性能優化角度入手，弱化估值函數帶來的影響，沒有使用人工神經網絡。

參考文獻：

[1] 王元卓，于建業，邱雯，等.網絡群體行為的演化博弈模型與分析方法[J].計算機學報，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] 季輝，丁澤軍.雙人博弈問題中的蒙特卡洛樹搜索算法的改進[J].計算機科學，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，FischerP.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] 徐心和，王驕.中國象棋計算機博弈關鍵技術分析[J].小型微型計算機系統，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] 丁濛，張亦鵬，李淑琴.棋盤局面數據標定方法研究[J].計算機應用研究，2020，37（2）：470-472.

【通聯編輯：光文玲】