范博奇， 丁 濛,2， 張芳梓

(1 北京信息科技大學(xué) 計(jì)算機(jī)學(xué)院， 北京 100101; 2 北京信息科技大學(xué) 感知與計(jì)算智能聯(lián)合實(shí)驗(yàn)室， 北京 100101)

引言

愛因斯坦棋[1]是2004年由德國中部耶拿鎮(zhèn)數(shù)學(xué)教授Ingo Alth?fer獨(dú)創(chuàng)推出的兩人骰棋類游戲。該棋種作為一種完全信息博弈項(xiàng)目，具有較高的隨機(jī)性，看似是一個憑借運(yùn)氣的小游戲，背后卻隱藏著較深的計(jì)算決策過程。

目前，國內(nèi)愛恩斯坦棋規(guī)則與國際奧林匹克計(jì)算機(jī)博弈大賽的愛恩斯坦棋規(guī)則保持一致，棋盤為5×5的方格形棋盤，方格為棋位，左上角為紅方出發(fā)區(qū)；右下角為藍(lán)方出發(fā)區(qū)，棋盤設(shè)計(jì)如圖1所示。

在計(jì)算機(jī)博弈軟件的設(shè)計(jì)中，一個優(yōu)良的評估策略往往是博弈取勝的關(guān)鍵，因其可為搜索過程的具體實(shí)現(xiàn)提供計(jì)算的基礎(chǔ)。文獻(xiàn)[2]設(shè)計(jì)了一種靜態(tài)的攻防策略；文獻(xiàn)[3]提出了偏向進(jìn)攻的評估函數(shù)來削弱隨機(jī)性帶來的影響；文獻(xiàn)[4]考慮到了棋子全殲的情況，建立了攻守兼?zhèn)涞墓乐岛瘮?shù)進(jìn)行決策。本文在文獻(xiàn)[3]考慮進(jìn)攻的基礎(chǔ)上，對防守的情況展開綜合分析，設(shè)計(jì)提出了一種新的評估策略。

1 評估策略的設(shè)計(jì)

愛恩斯坦棋的勝利方式分為率先占據(jù)敵方角落位和全殲對手棋子兩種。經(jīng)過大量的測試表明，以全殲對手棋子達(dá)到勝利條件的概率很低，所以研究中盡可能地將決策的目光投向角落位置上，盡快占據(jù)敵方角落點(diǎn)并防止敵方占據(jù)己方角落點(diǎn)，主要考慮了棋盤位置的價值和敵方棋子的位置。

本文針對愛恩斯坦棋的規(guī)則設(shè)計(jì)了評估函數(shù)，包括進(jìn)攻與防守兩個因素。其中，進(jìn)攻是指尋求最短路徑盡快到達(dá)敵方角落點(diǎn)，防守則是指在己方處于劣勢的情況下，以保守的方式行棋，避免己方角落點(diǎn)被敵方到達(dá)或者己方被全殲。計(jì)算公式如下所示：

Value=k1×Attack+k2×Defense

(1)

其中，Value表示行棋走法中選擇的評價估值；Attack表示進(jìn)攻值；Defense表示防守值；k1、k2表示相應(yīng)的參數(shù)。

由于愛恩斯坦棋策略中以全殲敵方棋子達(dá)到勝利的實(shí)現(xiàn)性遠(yuǎn)小于占據(jù)地方角落點(diǎn)的可能性，所以本文將著重討論占據(jù)與防止被占據(jù)角落點(diǎn)的情況。

1.1 棋子進(jìn)攻值的設(shè)定

愛恩斯坦棋行棋的棋子由每次擲出的骰子數(shù)決定，棋子的價值主要由棋子被選中的概率和棋盤相應(yīng)位置的價值而確定。以己方作為左上方紅方為例，率先占據(jù)右下角落位置為獲勝。進(jìn)攻策略的評估函數(shù)主要是根據(jù)棋盤不同位置設(shè)定的權(quán)重以及對敵方棋子的判斷綜合形成。

本文的設(shè)計(jì)原理是棋子的進(jìn)攻值由棋盤相應(yīng)位置的價值和敵方棋子的位置而確定，而邊界值的棋子價值又應(yīng)該略大于距離相同非邊界值棋子價值。具體計(jì)算如公式(2)所示：

Attack[i][j]=boardvalue[i][j]-P[a]*distance

(2)

其中，i,j表示己方被骰子搖中的棋子可行棋的3個位置的坐標(biāo)；Attack[i][j]為攻擊值；boardvalue[i][j]表示棋盤不同位置的權(quán)重；a為敵方棋子編號；P[a]為該走法位置上的敵方棋子下一步行棋的概率；distance為該位置距己方角落點(diǎn)的最短距離。當(dāng)該行棋位置無敵方棋子時，P[a]為0。

綜上，給出了不同位置排定分布的棋子價值boardvalue[i][j]，如圖2所示。

圖1愛恩斯坦棋棋盤圖2棋子分布價值

Fig.1ChessboardofEinsteinchessFig.2Thevaluedistributionofchess

圖2表示當(dāng)己方身處右下方時，在不同位置所分布的權(quán)重。若設(shè)從某一位置到敵方角落點(diǎn)的最短步數(shù)為n，則以24-n次冪作為權(quán)重分布在棋盤上，權(quán)重最高的是到達(dá)對方角落點(diǎn)路徑最短的。對于己方來說，目標(biāo)是到達(dá)左上角的點(diǎn)，因此越靠近該點(diǎn)，權(quán)重就越大。本文采選的是已占據(jù)角落點(diǎn)為目標(biāo)的評估策略，所以在靠近敵方腹地時考慮到了因吃掉敵方棋子導(dǎo)致敵方骰子帶來的隨機(jī)性變小，從而對己方不利這一因素，添加了下一回合敵方棋子行動的概率值和該位置距己方角落點(diǎn)的最短距離兩個變量，以便于綜合衡定局面形勢。而角落點(diǎn)位置為勝利的絕對先決條件，為此將該點(diǎn)的棋子權(quán)重改換為一個超過Value最大值的權(quán)重。此外，本文認(rèn)定處在邊界位置的棋子價值更高，原因解析如圖3所示。

由圖3可知，藍(lán)1和藍(lán)3距離對面角落點(diǎn)位置距離都是2，但是對于藍(lán)3來說，因其同時面對紅5和紅3兩個棋子的威脅，而藍(lán)1只面對紅5的威脅。因此可知，對于處在邊界位置的棋子，將只會受到來自上方或者下方的棋子威脅(取決于初始位置)，而處在其他非邊界位置的棋子，則會受到來自3個方向的棋子威脅，更不容易突破包圍圈到達(dá)敵方角落點(diǎn)位置。所以在設(shè)置棋子價值的時候，邊界位置的權(quán)值會偏高一些。

1.2 棋子防守值的設(shè)定

過程中，在斟酌防守層面設(shè)定時，一方面要建立動態(tài)的評估函數(shù)，另一方面要對特殊情況進(jìn)行靜態(tài)評估，保障該博弈系統(tǒng)的穩(wěn)定性。

同時，不能僅僅關(guān)注本方棋子占據(jù)對面角落位置這一點(diǎn)，當(dāng)對面棋子前進(jìn)到己方腹地，對己方的角落位置產(chǎn)生足夠威脅時，就要研究設(shè)計(jì)對敵方棋子的威脅排除了。

1.2.1 動態(tài)防守策略

本文的應(yīng)對策略是，當(dāng)有敵方棋子距離己方角落位置還有2步或者1步時，且己方棋子下一步行棋走法中有可吃掉敵方該棋子的局面，則此步走法計(jì)算防守值，否則防守值為0。防守值需基于敵方視角的棋盤價值而靈活設(shè)定。對其數(shù)學(xué)描述，可如式(3)所示：

Defense[i][j]=boardvalue[4-i][4-j]

(3)

若己方棋盤為右下角一方的話，此時己方相應(yīng)的棋盤估值就要遵照敵方視角的敵方估值進(jìn)行計(jì)算，根據(jù)己方棋子鄰近位置的敵方棋子的價值來運(yùn)作行棋，在受到不同位置棋子威脅的時候，選擇其中最大的威脅位置予以行棋展開防守。

1.2.2 靜態(tài)防守策略

當(dāng)己方棋子個數(shù)小于等于2，且有被敵方全殲的可能時，將優(yōu)先采取靜態(tài)防守策略，目的是減小己方棋子被敵方棋子吃掉的概率，直觀布局則可如圖4所示。

在圖4中，藍(lán)2離敵方角落位置距離值為2，此時如果向斜上方走，極易落入敵方紅2與紅5的包圍圈，己方棋子就會面臨被全殲的可能。此時應(yīng)該根據(jù)敵方下一回合中紅5或紅2行動的概率，選擇向左或者向上的行棋方式，避開“包圍圈”。但無論在何種棋局下，當(dāng)己方有任意一枚棋子距離敵方角落位置僅為一步的時候，均將選擇達(dá)到占據(jù)角落位置的勝利條件的走法。

圖3 對戰(zhàn)局勢 圖4 靜態(tài)防守棋局Fig. 3 The situation of confrontation Fig. 4 The chess game of static defense

2 評估策略實(shí)現(xiàn)流程

整個評估策略先從外部接收骰子數(shù)，根據(jù)棋盤上己方棋子情況選出可移動棋子和預(yù)期可行方案，再判斷是否滿足靜態(tài)防守策略條件，若滿足即根據(jù)相關(guān)局勢算出下回合擲到敵方棋子概率，并開啟走法選擇流程；若不滿足，則根據(jù)公式(1)計(jì)算評價估值，在比較所有走法的估值后選擇最大權(quán)值的走法，從而轉(zhuǎn)入輸出環(huán)節(jié)操作。分析后，可得設(shè)計(jì)步驟如圖5所示。

圖5 評估策略流程圖Fig. 5 The flow chart of evaluation strategy

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

本次愛恩斯坦棋項(xiàng)目結(jié)合了上文研究提出的進(jìn)攻+防守并結(jié)合靜態(tài)策略的評估策略，公式(1)中的k1、k2分別設(shè)為0.65和0.35,使用了Java語言編寫研發(fā)，在Windows環(huán)境下分別設(shè)計(jì)展開了50次實(shí)驗(yàn)?zāi)M，同時與表1中選用評估函數(shù)的程序進(jìn)行對照比較，運(yùn)行結(jié)果見表1。

表1 該博弈程序與其他程序的機(jī)機(jī)對戰(zhàn)對比表Tab. 1 Comparison of this program with other programs

由表1可知，在使用了新評估策略后，面對只使用進(jìn)攻策略評估函數(shù)的程序具備了很高的保障，在面對無靜態(tài)防守策略評估函數(shù)的程序也占有一定的勝率。該實(shí)驗(yàn)結(jié)果清晰證明了這種評估策略對勝利條件的實(shí)現(xiàn)有著積極有效的正向作用。

4 結(jié)束語

本文設(shè)計(jì)提出了一種新的愛恩斯坦棋評估策略，對棋子各位置價值融入了研究改進(jìn)，在實(shí)現(xiàn)了進(jìn)攻與防守評估函數(shù)的同時，添加了靜態(tài)層次的防守策略設(shè)計(jì)，達(dá)到了較好的效果。

[1] 中國人工智能學(xué)會機(jī)器博弈專業(yè)委員會. 愛恩斯坦棋項(xiàng)目規(guī)則[EB/OL]. [2016-08-14] .http://computergames.caai.cn/jsgz09.html.

[2] 周文敏,李淑琴. 愛恩斯坦棋靜態(tài)攻防策略的研究[J]. 電腦知識與技術(shù),2014,10(5):1027-1031.

[3] 黃恩一,丁濛. 基于愛恩斯坦棋削減隨機(jī)性影響的博弈算法研究[J]. 智能計(jì)算機(jī)與應(yīng)用,2017,7(1):69-70，75.

[4] 光洋. 愛恩斯坦棋計(jì)算機(jī)博弈系統(tǒng)的研究與實(shí)現(xiàn)[D]. 合肥：安徽大學(xué),2016.