動態(tài)混合局面評估MCTS 算法在愛恩斯坦棋中的應(yīng)用

宋英健，侯榮旭，孫嘉榮，史廣闊

（沈陽工程學(xué)院 信息學(xué)院，遼寧 沈陽 110136）

計算機博弈是研究人工智能領(lǐng)域的一個重要分支，同時也是各個科研領(lǐng)域方面重點研究的對象，其目的是構(gòu)建一個具有AI智能的算法，使之可以像人類選手一樣進行對戰(zhàn)、博弈［1］。計算機博弈程序一般由評估函數(shù)與優(yōu)化搜索算法兩部分組成，同時配有棋局評估、法生成、開局庫與殘局庫開發(fā)、博弈樹搜索、系統(tǒng)測試及參數(shù)優(yōu)化等核心技術(shù)要點［2］。

1 愛恩斯坦棋介紹

愛恩斯坦棋是2004 年由德國人英戈·阿爾托夫發(fā)明的一種雙人非完備信息類博弈游戲。棋盤為5×5 的方格形棋盤，每一個方格代表一個棋位，棋盤的左上角為紅方棋子位置，棋盤的右下角為藍(lán)方棋子位置；雙方共持有6 枚棋子，棋子序號為1～6，順序在雙方出發(fā)區(qū)棋位可以無序任意放置；對局開始由紅方先拋出骰子，移動棋子的標(biāo)號與骰子點數(shù)相對應(yīng)，如果棋盤中不存在與骰子點數(shù)相對應(yīng)的棋子，則可以順著點數(shù)向上或者向下查找，選擇與之最相近的點數(shù)，移動該枚棋子；雙方移動規(guī)則為紅方只能移動目標(biāo)棋子朝右方、下方、斜下方移動，藍(lán)方只能移動目標(biāo)棋子朝左方、上方、斜上方移動；在棋子移動的目標(biāo)棋位上如有棋子(不論敵我)，則移動本方棋子來覆蓋該枚棋子，被覆蓋的棋子從棋盤中移除。勝利的條件有兩種，分別為移動到對方對角點和全殲對方棋子，愛恩斯坦棋無平局出現(xiàn)。

2 算法設(shè)計

對于構(gòu)建一個計算機博弈算法，估值函數(shù)與搜索算法是不可或缺的。對于愛恩斯坦棋博弈系統(tǒng)來說，一方獲勝的條件為吃掉對方全部棋子或到達對方對角線，通過完全模擬算法可以精準(zhǔn)地預(yù)測棋子的目標(biāo)棋位，從而獲得勝利。模擬算法雖好，但是局限性也很大，主要受制于計算機的硬件性能?，F(xiàn)有的計算機無法在短時間內(nèi)計算出目標(biāo)結(jié)果。所以，一般要對所使用的搜索算法加以改進。傳統(tǒng)的搜索算法有很多種，如完全模擬算法、MCTS 算法、MAX-MIN 算法等。不同于傳統(tǒng)的圍棋、象棋等完備信息類游戲，愛恩斯坦棋中移動棋子需要投擲骰子，根據(jù)骰子的點數(shù)來確定移動的棋子。所以，對于帶有隨機性質(zhì)的問題，Monte-Carlo 算法的適用度較其他傳統(tǒng)算法更加契合，通過Monte-Carlo 算法，不需要模擬出所有的對局局面，僅需要有限次模擬抽樣就可以獲得較為準(zhǔn)確的結(jié)果。

評估函數(shù)的好壞可以決定程序的落子位置。傳統(tǒng)的靜態(tài)評估局限性較大，這種局限性往往體現(xiàn)在對弈后期，程序并不能有效地判斷出當(dāng)前局面的最佳落子位置，程序的判斷力往往不如人腦的判斷力，這顯然是不合理的。在此基礎(chǔ)上提出了一種動態(tài)混合局面評估函數(shù)。經(jīng)過多次對弈實驗可知，使用改進評估函數(shù)的程序在后期的失誤率要遠(yuǎn)遠(yuǎn)低于使用普通靜態(tài)評估函數(shù)下的失誤率。

2.1 愛恩斯坦棋常用算法

在傳統(tǒng)的機器博弈中常被提到的算法有α-β剪枝算法、Monte-Carlo 算法、極大值極小值算法等。在全國大學(xué)生計算機博弈大賽中，大多數(shù)參賽選手的參賽程序均采用了α-β 剪枝算法或Monte-Carlo算法。棋力的高低與雙方對算法的優(yōu)化和硬件設(shè)備的性能有較大關(guān)系。

經(jīng)過多種實驗，Monte-Carlo 算法的搜索次數(shù)可自定并且搜索時間也可以進行設(shè)置。該算法在愛恩斯坦棋中通過有限次模擬對局后，計算出棋子移動的勝率，最終決定落子選擇和落子方向。但此做法有一較大缺點，在模擬過程中雙方完全隨機移動，在有限次完全隨機模擬中可能會得到與預(yù)期相差較大的移動結(jié)果，而且由于程序?qū)Ψ郊傧霝橥耆S機算法，程序計算得到的勝率偏高，這會影響程序的判斷力并做出錯誤的決定。將Monte-Carlo算法優(yōu)化改進與混合局面評估函數(shù)綜合應(yīng)用后，將會得到更加精確的結(jié)果，從而有效提高棋力。

2.2 Monte-Carlo算法

Monte-Carlo 算法又被稱為模擬統(tǒng)計算法，其中最簡單、最基本、最重要的一個概率分布是（0，1）上的矩形分布［3］。在C++中，采取隨機模擬的方式來實現(xiàn)Monte-Carlo 算法。通過設(shè)置模擬次數(shù)，在搜索過程中不斷地對雙方進行完全隨機模擬對弈，通過模擬對弈的勝場來計算模擬的勝率，模擬的次數(shù)越多，得到的勝率就越精確，最后經(jīng)過勝率對比來篩選勝率最高的決策，從而達到有利于己方的局面。

在愛恩斯坦棋中，棋子的移動取決于骰子數(shù)。Monte-Carlo 算法可以用于優(yōu)化模擬算法，用有限次模擬來進行抽樣，從而獲得較為準(zhǔn)確的數(shù)據(jù)。以紅方為例，骰子點數(shù)為4，程序首先判斷4對應(yīng)的棋子是否存活，如果存活則選中，反之則向上或向下遍歷尋找與之最相近的棋子；若設(shè)置模擬次數(shù)為5 000，程序先取得當(dāng)前棋子的所有著法，然后對所有著法的勝率進行判斷比較。如正右方勝利次數(shù)為2 000，正下方勝利次數(shù)為100，右下方勝利次數(shù)為4 999，則正右方勝率為40%，正下方勝率為2%，右下方勝率為99%，通過比較勝率可以得到當(dāng)前局面棋子4向右下方移動為最優(yōu)走法。

本文中采用C++為編程語言，設(shè)置參數(shù)MC_CONSTANT 為模擬的總次數(shù)，設(shè)Eva 為模擬對弈中紅方勝利的總次數(shù)，則勝率p（Eva）=Eva/MC_CONSTANT。設(shè)k為在MCTS 中模擬出正確決策的次數(shù)，ε為任意大小的正數(shù)，則

式（1）證明了當(dāng)n趨于無窮大的時候，概率k/n收斂于s'/s。

2.3 動態(tài)混合局面評估函數(shù)

在程序運行過程中，需要有一個評估函數(shù)來對當(dāng)前局面進行判斷，從而得出最優(yōu)落子點。傳統(tǒng)的靜態(tài)評估函數(shù)具有片面的特點。本文設(shè)計了一種動態(tài)混合局面評估函數(shù)，提出了進攻值、威脅值及距離價值的概念，通過多方面的混合評估來最終確定棋子的價值。

2.3.1 棋子移動概率計算

愛恩斯坦棋紅藍(lán)雙方各有6枚棋子，每枚棋子在初始被抽到的概率均為1/6，隨著對弈的進行，棋子陸續(xù)被覆蓋吃掉，此時與骰子點數(shù)相近的棋子概率將會上升。發(fā)生吃子后，其他棋子的靈活性將會得到提高。所以，在對弈中常常采取舍棄其他棋子的辦法來提高棋子的靈活性。每枚棋子被選中的幾率為

式中，P(i)為第i枚棋子被選中的幾率；i為紅方棋子的標(biāo)號；Cleft_die為棋子序號左側(cè)被吃子的數(shù)量；Cright_die為子序號右側(cè)被吃子的數(shù)量。

2.3.2 棋子距離計算

棋子的價值與棋子所處位置有關(guān)，價值隨著到對方對角的距離長短而改變，紅藍(lán)雙方的距離計算公式為

式中，D(i)為紅方棋子距對方對角距離；D(j)為藍(lán)方棋子距對方對角距離；loc()為紅藍(lán)雙方棋子當(dāng)前的坐標(biāo)。

2.3.3 棋子動態(tài)價值計算

根據(jù)對弈經(jīng)驗和其他參考文獻，棋子在邊界與其他位置的動態(tài)價值不同，在邊界的棋子距離對方對角的距離初始均為4，價值較小，但當(dāng)邊界的棋子距離縮短為2 時，棋子價值得到很大提升。棋子動態(tài)價值計算式為

2.3.4 進攻值計算

所謂進攻值是指當(dāng)前局面下我方棋子產(chǎn)生的總價值的期望，紅方進攻值為正數(shù)，藍(lán)方進攻值為負(fù)數(shù)，當(dāng)進攻值的絕對值越大時，說明當(dāng)前局面對己方越有利。進攻值的計算式為

2.3.5 威脅值計算

威脅值是指對方的棋子將會對本方的局面產(chǎn)生的不利估值，威脅值越大說明對己方越不利。威脅值的計算式為

2.3.6 動態(tài)混合評估總體估值計算

不同于傳統(tǒng)的評估函數(shù)，動態(tài)混合評估函數(shù)考慮了進攻值、威脅值及動態(tài)價值3 個方面因素，有效提高了程序的精準(zhǔn)性和智能性，總體評估為當(dāng)前局面所有棋子的綜合總價值。如果綜合總價值越大，說明局勢對紅方越有利；綜合總價值越小，說明對藍(lán)方越有利；當(dāng)綜合總價值為0 時，雙方局勢相同。綜合總價值的計算式為

3 動態(tài)混合局面評估MCTS算法

動態(tài)混合局面評估函數(shù)主要用來加強Monte-Carlo 算法。融合了動態(tài)混合局面評估函數(shù)的Monte-Carlo算法在模擬對弈的過程中能夠更加穩(wěn)定，減少隨機性，這在對弈的后期體現(xiàn)尤其明顯。在模擬對弈時不再單純地使用完全隨機模擬，要接入動態(tài)混合局面評估函數(shù)，篩選掉勝率明顯偏低的結(jié)點，提高了程序在單位時間內(nèi)搜索的效率。在程序進行選子落子決策時，傳統(tǒng)的評估函數(shù)僅看中進攻值，導(dǎo)致缺少防守能力；采取混合局面評估后，結(jié)合了進攻值、威脅值等多方面的因素，可以達到攻守兼?zhèn)涞男Ч?。動態(tài)混合局面評估函數(shù)MCTS 算法流程如圖1所示。

圖1 動態(tài)混合局面評估函數(shù)MCTS算法流程

4 分析比較

4.1 系統(tǒng)實現(xiàn)

基于以上算法的研究，本文使用C++語言在vi‐sual studio 2019與Qt5.12.3環(huán)境下實現(xiàn)了一款基于動態(tài)混合局面評估MCTS算法的愛恩斯坦棋博弈系統(tǒng)。程序棋盤界面用QPainter 繪制，在Gps 類中，x1、x2、y1、y2 代表矩形區(qū)域。當(dāng)value 值為0 時，代表該區(qū)域沒有棋子；當(dāng)value值為正數(shù)時，代表是紅方的棋子；當(dāng)value值為負(fù)數(shù)時，代表是藍(lán)方的棋子。

棋子移動采用了mousePressEvent 事件。當(dāng)鼠標(biāo)進入5×5棋盤區(qū)域內(nèi)并單擊任意一枚棋子時，獲取該區(qū)域內(nèi)棋子的信息；如果鼠標(biāo)在5×5棋盤區(qū)域外單擊，則判斷當(dāng)前單擊無效。當(dāng)鼠標(biāo)移動事件觸發(fā)后，鼠標(biāo)在向左或向右移動時，被單擊棋子對應(yīng)區(qū)域的x1、x2、y1、y2 也會隨之增加或縮減。mouseReleaseEvent（鼠標(biāo)釋放事件）為當(dāng)鼠標(biāo)在某一個區(qū)域釋放時，首先判斷該棋子是否合法，如果該走法合法則成功移動棋子。

圖2 為本系統(tǒng)用QT 制作的主界面，主要分為棋盤和搜索算法兩部分。棋盤控制部分包括棋盤表示、界面交互、對局悔棋、對局計時、AI 勝算估值、歷史記錄及棋盤保存7 大部分。程序可以切換AI 算法并實現(xiàn)自對弈，在進行對局之后，可以自動生成棋譜和著法信息，方便統(tǒng)計比較。算法部分包括MCTS算法和動態(tài)混合局面評估MCTS算法。

圖2 愛恩斯坦棋博弈系統(tǒng)QT界面

4.2 實驗分析

本文實驗以表格數(shù)據(jù)和直方圖的形式展示Monte-Carlo算法與動態(tài)混合局面評估MCTS算法在愛恩斯坦棋中的應(yīng)用效果。本次對弈實驗以模擬次數(shù)MC_CONSTANT 和算法種類Type 為自變量，兩種算法的模擬次數(shù)設(shè)置為5 000次和10 000次。

4.3 結(jié)果分析

在實驗之后，記錄對弈的平均時長及勝率情況，制成的數(shù)據(jù)如圖3所示。實驗結(jié)果有效地驗證了動態(tài)混合局面評估MCTS算法相比于傳統(tǒng)的MCTS算法，在勝率和時間上均有較大的優(yōu)勢。若每局模擬次數(shù)固定為5 000，則動態(tài)混合局面評估MCTS 算法耗時為MCTS算法的73.5%，而勝率為64.5%。

圖3 對弈實驗數(shù)據(jù)

由此可得，在愛恩斯坦棋中，動態(tài)混合局面評估MCTS算法可以有效提高搜索效率和對弈勝率。

5 結(jié)論

本文采用動態(tài)混合評估函數(shù)代替?zhèn)鹘y(tǒng)評估函數(shù)，并將動態(tài)混合評估函數(shù)與Monte-Carlo 算法相結(jié)合，有效地提高了程序的智能性和效率。經(jīng)過改良后的算法考慮了對弈當(dāng)前局面的多種因素，不采取單一的棋盤估值，而是采取動態(tài)估值和總體估值來判斷當(dāng)前的局勢，從而使程序做出正確的決策，減少失誤和隨機性。

經(jīng)過結(jié)合后的算法勝率和搜索效率顯著高于傳統(tǒng)算法。在后續(xù)的工作學(xué)習(xí)中，也可以結(jié)合機器學(xué)習(xí)、深度學(xué)習(xí)等其他智能算法來進一步提高程序的AI等級，這也是值得深入研究的［4］。