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

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

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

引言

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

目前，國內愛恩斯坦棋規則與國際奧林匹克計算機博弈大賽的愛恩斯坦棋規則保持一致，棋盤為5×5的方格形棋盤，方格為棋位，左上角為紅方出發區；右下角為藍方出發區，棋盤設計如圖1所示。

在計算機博弈軟件的設計中，一個優良的評估策略往往是博弈取勝的關鍵，因其可為搜索過程的具體實現提供計算的基礎。文獻[2]設計了一種靜態的攻防策略；文獻[3]提出了偏向進攻的評估函數來削弱隨機性帶來的影響；文獻[4]考慮到了棋子全殲的情況，建立了攻守兼備的估值函數進行決策。本文在文獻[3]考慮進攻的基礎上，對防守的情況展開綜合分析，設計提出了一種新的評估策略。

1 評估策略的設計

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

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

Value=k1×Attack+k2×Defense

(1)

其中，Value表示行棋走法中選擇的評價估值；Attack表示進攻值；Defense表示防守值；k1、k2表示相應的參數。

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

1.1 棋子進攻值的設定

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

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

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

(2)

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

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

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

Fig.1ChessboardofEinsteinchessFig.2Thevaluedistributionofchess

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

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

1.2 棋子防守值的設定

過程中，在斟酌防守層面設定時，一方面要建立動態的評估函數，另一方面要對特殊情況進行靜態評估，保障該博弈系統的穩定性。

同時，不能僅僅關注本方棋子占據對面角落位置這一點，當對面棋子前進到己方腹地，對己方的角落位置產生足夠威脅時，就要研究設計對敵方棋子的威脅排除了。

1.2.1 動態防守策略

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

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

(3)

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

1.2.2 靜態防守策略

當己方棋子個數小于等于2，且有被敵方全殲的可能時，將優先采取靜態防守策略，目的是減小己方棋子被敵方棋子吃掉的概率，直觀布局則可如圖4所示。

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

圖3 對戰局勢 圖4 靜態防守棋局Fig. 3 The situation of confrontation Fig. 4 The chess game of static defense

2 評估策略實現流程

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

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

3 實驗結果與分析

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

表1 該博弈程序與其他程序的機機對戰對比表Tab. 1 Comparison of this program with other programs

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

4 結束語

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

[1] 中國人工智能學會機器博弈專業委員會. 愛恩斯坦棋項目規則[EB/OL]. [2016-08-14] .http://computergames.caai.cn/jsgz09.html.

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

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

[4] 光洋. 愛恩斯坦棋計算機博弈系統的研究與實現[D]. 合肥：安徽大學,2016.