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

（沈陽工程學院 信息學院，遼寧 沈陽 110136）

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

1 愛恩斯坦棋介紹

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

2 算法設計

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

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

2.1 愛恩斯坦棋常用算法

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

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

2.2 Monte-Carlo算法

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

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

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

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

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

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

2.3.1 棋子移動概率計算

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

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

2.3.2 棋子距離計算

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

式中，D(i)為紅方棋子距對方對角距離；D(j)為藍方棋子距對方對角距離；loc()為紅藍雙方棋子當前的坐標。

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

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

2.3.4 進攻值計算

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

2.3.5 威脅值計算

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

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

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

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

動態(tài)混合局面評估函數(shù)主要用來加強Monte-Carlo 算法。融合了動態(tài)混合局面評估函數(shù)的Monte-Carlo算法在模擬對弈的過程中能夠更加穩(wěn)定，減少隨機性，這在對弈的后期體現(xiàn)尤其明顯。在模擬對弈時不再單純地使用完全隨機模擬，要接入動態(tài)混合局面評估函數(shù)，篩選掉勝率明顯偏低的結點，提高了程序在單位時間內(nèi)搜索的效率。在程序進行選子落子決策時，傳統(tǒng)的評估函數(shù)僅看中進攻值，導致缺少防守能力；采取混合局面評估后，結合了進攻值、威脅值等多方面的因素，可以達到攻守兼?zhèn)涞男Ч討B(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ū)域。當value 值為0 時，代表該區(qū)域沒有棋子；當value值為正數(shù)時，代表是紅方的棋子；當value值為負數(shù)時，代表是藍方的棋子。

棋子移動采用了mousePressEvent 事件。當鼠標進入5×5棋盤區(qū)域內(nèi)并單擊任意一枚棋子時，獲取該區(qū)域內(nèi)棋子的信息；如果鼠標在5×5棋盤區(qū)域外單擊，則判斷當前單擊無效。當鼠標移動事件觸發(fā)后，鼠標在向左或向右移動時，被單擊棋子對應區(qū)域的x1、x2、y1、y2 也會隨之增加或縮減。mouseReleaseEvent（鼠標釋放事件）為當鼠標在某一個區(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算法在愛恩斯坦棋中的應用效果。本次對弈實驗以模擬次數(shù)MC_CONSTANT 和算法種類Type 為自變量，兩種算法的模擬次數(shù)設置為5 000次和10 000次。

4.3 結果分析

在實驗之后，記錄對弈的平均時長及勝率情況，制成的數(shù)據(jù)如圖3所示。實驗結果有效地驗證了動態(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 結論

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

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