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

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

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

1 愛(ài)恩斯坦棋介紹

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

2 算法設(shè)計(jì)

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

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

2.1 愛(ài)恩斯坦棋常用算法

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

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

2.2 Monte-Carlo算法

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

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

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

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

2.3 動(dòng)態(tài)混合局面評(píng)估函數(shù)

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

2.3.1 棋子移動(dòng)概率計(jì)算

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

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

2.3.2 棋子距離計(jì)算

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

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

2.3.3 棋子動(dòng)態(tài)價(jià)值計(jì)算

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

2.3.4 進(jìn)攻值計(jì)算

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

2.3.5 威脅值計(jì)算

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

2.3.6 動(dòng)態(tài)混合評(píng)估總體估值計(jì)算

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

3 動(dòng)態(tài)混合局面評(píng)估MCTS算法

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

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

4 分析比較

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

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

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

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

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

4.2 實(shí)驗(yàn)分析

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

4.3 結(jié)果分析

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

圖3 對(duì)弈實(shí)驗(yàn)數(shù)據(jù)

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

5 結(jié)論

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

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