愛恩斯坦棋評估策略的研究

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

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

引言

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

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

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

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

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

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

Value=k1×Attack+k2×Defense

(1)

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

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

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

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

本文的設(shè)計原理是棋子的進(jìn)攻值由棋盤相應(yīng)位置的價值和敵方棋子的位置而確定，而邊界值的棋子價值又應(yīng)該略大于距離相同非邊界值棋子價值。具體計算如公式(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為該位置距己方角落點的最短距離。當(dāng)該行棋位置無敵方棋子時，P[a]為0。

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

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

Fig.1ChessboardofEinsteinchessFig.2Thevaluedistributionofchess

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

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

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

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

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

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

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

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

(3)

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

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 評估策略實現(xiàn)流程

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

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

3 實驗結(jié)果與分析

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

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

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

4 結(jié)束語

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

[1] 中國人工智能學(xué)會機(jī)器博弈專業(yè)委員會. 愛恩斯坦棋項目規(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ī)與應(yīng)用,2017,7(1):69-70，75.

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