愛恩斯坦棋靜態(tài)攻防策略的研究

周文敏 李淑琴

摘要：近些年來，愛恩斯坦棋作為一個在中國剛剛興起不久的棋類游戲，其計算機博弈算法的研究還相對較少。該文嘗試使用靜態(tài)算法來讓程序做出一個相對有利于我方的走棋路線，也著力實現(xiàn)一個基于枚舉和靜態(tài)分析策略的靜態(tài)算法，并且提供一個參考的局面評估算法。經(jīng)過大量模擬實驗證明，該算法具有一定的有效性和實用性。

關(guān)鍵詞：靜態(tài)算法；愛恩斯坦棋；枚舉；人工智能

中圖分類號：TP301 文獻標識碼：A 文章編號：1009-3044（2014）05-1027-05

The Research of Static Algorithms in WTN Chess

ZHOU Wen-min， LI Shu-qin

（ Computer School of Beijing Information Science and Technology University， Beijing 100101， China）

Abstract： In recent years，WTN chess is just emerging as a computer game of National Computer Games Competition in China which lacks of algorithm research. This paper tries to research how to use static algorithm to make a relatively right choice to move pieces.This paper also achieves a static algorithm based on enumeration and static analysis strategies， and provides an algorithm of situation assessment.It is demonstrated that the algorithm is effective and useful.

Key words： static algorithm；WTN chess；enumeration；artificial intelligence

計算機博弈是人工智能領(lǐng)域一個極其重要且最具挑戰(zhàn)性的研究方向之一[1]， 計算機博弈算法具有形式多樣、算法種類紛繁、算法應(yīng)用面廣泛、算法涉及領(lǐng)域全面等諸多特點。計算機博弈算法的研究為人工智能領(lǐng)域擴充了很多新的實用的算法，豐富了計算機科學領(lǐng)域的理論成果。在過去的幾十年里，世界各地的學者致力于研究各種棋牌類游戲的博弈算法，并取得了不少舉世矚目的研究成果，譬如說1997年IBM公司的“深藍”戰(zhàn)勝國際著名象棋大師卡斯帕羅夫的消息轟動世界，其他很多棋類的算法都已達到了世界冠軍級的水準。現(xiàn)如今，很多大型的軟件開發(fā)公司都將中國象棋等棋類的算法研究作為面試成績的參考之一，比如微軟中國公司曾經(jīng)在面試中出過中國象棋的將帥問題，要求只用一個變量輸出將帥的所有合法位置[2]。其它許多大型公司也出過類似這樣的計算機博弈中的具有挑戰(zhàn)性的問題?？梢娙斯ぶ悄茴I(lǐng)域的研究越來越廣泛，越來越多的編程愛好者開始著力于計算機棋類博弈算法的研究。該文就新產(chǎn)生的棋種之一愛恩斯坦棋的靜態(tài)的攻擊和防守算法做一個相對系統(tǒng)的研究，提供一個相對可行的策略。

1 愛恩斯坦棋簡介

愛恩斯坦棋由Ingo Alth?fer[3]發(fā)明并且于2004年問世，是一個新產(chǎn)生的棋類游戲。愛恩斯坦棋目前是國際計算機奧林匹克大賽競賽項目，并于2012 年首次作為中國計算機博弈大賽[4]的比賽項目。愛恩斯坦棋規(guī)則為：

1）棋盤為5×5的方格形棋盤，方格為棋位，左上角為紅方出發(fā)區(qū)；右下角為藍方出發(fā)區(qū)，如（圖1）所示；

2）紅藍方各有6枚方塊形棋子，分別標有數(shù)字1—6。開局時雙方棋子在出發(fā)區(qū)的棋位可以隨意擺放；

3）雙方輪流擲骰子，然后走動與骰子顯示數(shù)字相對應(yīng)的棋子。如果相對應(yīng)的棋子已從棋盤上移出，便可走動大于或小于此數(shù)字的并與此數(shù)字最接近的棋子；

4）紅方棋子走動方向為向右、向下、向右下，每次走動一格；藍方棋子走動方向為向左、向上、向左上，每次走動一格；

5）如果在棋子走動的目標棋位上有棋子，則要將該棋子從棋盤上移出（吃掉）。有時吃掉本方棋子也是一種策略，因為可以增加其它棋子走動的機會與靈活性；

6）率先到達對方出發(fā)區(qū)角點或?qū)Ψ狡遄尤砍缘舻囊环将@勝；

7）對弈結(jié)果只有勝負，沒有和棋。

8）每盤每方用時3分鐘，超時判負；每輪雙方對陣最多7盤，輪流先手（甲方一四五盤先手，乙方二三六七盤先手），兩盤中間不休息，先勝4盤為勝方。

圖1 愛恩斯坦棋棋盤

由于愛恩斯坦棋走每一步棋之前都需要擲骰子以確定走動的棋子的編號，隨機性對棋局的影響很大。該文力圖構(gòu)造一個算法以減少由于擲骰子的數(shù)不同從而給棋局帶來的不利影響，增加其有利的影響，使棋局向著盡可能使我方獲勝的方向發(fā)展。

2 愛恩斯坦棋之靜態(tài)攻擊策略

本文的算法主要采用靜態(tài)算法。此算法基于枚舉和貪心策略。棋局中將假設(shè)我方是藍方，敵方為紅方。進攻的總體策略是根據(jù)走棋的棋子的周圍棋子的布局情況確定是否向前攻擊以及攻擊的方向。

定義1：周圍棋子數(shù)

指我方（藍方）某個棋子左邊、左上方和正上方的棋子數(shù)目之和，取值范圍為0-3。例如：某愛恩斯坦棋棋盤布局如（圖2）所示，假設(shè)選定的棋子為藍5，那么它周圍的棋子數(shù)目為2。即左方的藍6和正上方的藍4。

圖2 愛恩斯坦棋某個棋盤布局

定義2：主對角線：主對角線是指愛恩斯坦棋棋盤（5*5）的矩陣中從左上角到右下角的連線。

定義3：副對角線：副對角線是指愛恩斯坦棋棋盤（5*5）的矩陣中從左下角到右上角的連線。

定義4：敵人總數(shù)目：敵人總數(shù)目是指敵方（紅方）的所有棋子的數(shù)量之和，取值范圍在0-6之間。

定義5：出發(fā)點：對于我方來說，右下角的格子為我方的出發(fā)點；對于敵方來說，左上角的格子為敵方的出發(fā)點。

定義6：終點：對于我方來說，左上角的格子為我方的終點；對于敵方來說，右下角的格子為敵方的終點。換句話說，我方出發(fā)點為敵方終點，敵方出發(fā)點為我方終點。

定義7：周圍敵人數(shù)：周圍的所有棋子中敵方棋子的數(shù)量。

定義8：周圍我方棋子數(shù)：周圍的所有棋子中我方棋子的數(shù)量。

定義9：失去全殲?zāi)芰Γ杭磾撤街辽儆幸粋€棋子不能被我方任意一棋子吃掉，此時我方不能以全殲的方式贏取敵方。

1）離終點只有一步的情況

此種情況最簡單，當我方被選中的棋子到達第一行第二列、第二行第一列或者第二行第二列的時候，只需要再走一步就能到達終點贏取勝利。此時，不管周圍有幾個敵方棋子或者是我方其它棋子，都不去吃它們，而朝著終點走一步贏取勝利。

如（圖3）所示，假設(shè)當前我方被選中的棋子是藍4，此時藍4可以不去管周圍的敵人，直接朝著終點走一步獲得勝利。具體的三種情況見（圖4）。

圖3 走一步就能獲勝的情況

圖4 走一步就能獲勝的三種情況（空白處可以有任意棋子或者無棋子）

2）我方棋子失去全殲?zāi)芰Φ那闆r

當敵方某一個或幾個棋子不能夠被我方任意棋子吃掉的情況下，我方就不能用全殲的方式贏取對方。換句話說，我方此時不應(yīng)該吃對方任意一個棋子，因為吃對方棋子既不可能以全部殲滅的方式贏取對方，又給對方的棋子增加了靈活性，增加了他們贏得比賽的機會。

當這種情況出現(xiàn)的時候，我方被選中棋子要朝著終點的最短距離前進，即能斜著走就斜著走，如果到達某一邊界了就只能橫著向左走或者豎著向上走。如（圖5）所示的一種失去全殲?zāi)芰Φ那闆r。

圖5 失去全殲?zāi)芰Φ那闆r

在（圖5）中所示的一種失去全殲?zāi)芰Φ那闆r，紅5已經(jīng)不能被我方的任意一個棋子吃掉，此時假設(shè)我方選中的棋子是藍5，藍5到達終點的最少步數(shù)是3，那么此時藍5走豎直上方和斜上方都可以。但是如果走斜上方把紅4吃掉了，紅方的靈活性就提高了，所以此時藍5最好的方案就是豎直向上走，避開紅4，在不影響到達終點的步數(shù)的同時還可以防止對方的靈活性增加。

3）避開我方棋子的情況

當我方棋子總數(shù)目小于等于3的時候，我方如果繼續(xù)把自己的棋子吃掉的話，雖然可以提高靈活性，但是會造成我方被敵方全殲的危險。如（圖6）所示的15種情況，我方被選中的棋子需要避開我方的其它棋子，前提是我方的總棋子數(shù)目小于等于3。

圖6 避開我方棋子的情況

情況1：我方被選中棋子的斜上方有我方其它棋子，這個時候需要避開我方棋子。（大前提是我方的總棋子數(shù)目小于等于3，下同。）這種情況下，應(yīng)該橫著走左方或者豎著走上方，具體這兩種走法走哪種要根據(jù)下文中的局面評估算法來評定。

情況2：直接走斜線，因為這樣到達終點的速度最快，又不會使我方的棋子數(shù)目減少，防止被對方全殲的危險。

情況3： 與情況2類似。

情況4： 當斜方向有我方棋子而豎直方向或者橫方向（對應(yīng)情況5）有敵方棋子的時候，我方不去斜著走吃掉自己的棋子，理由同上。此時如果我方?jīng)]有失去全殲?zāi)芰Φ那闆r下可以把對方的棋子吃掉（對應(yīng)情況4則向上豎著走），如果我方已經(jīng)失去了全殲?zāi)芰?，則需要橫著向左走向空白位置。

情況5： 與情況4類似。

情況6： 如果敵人只有這么一個，可以將敵人吃掉以全殲的方式獲得勝利，否則的話走斜對角線方向走向空白位置。

情況7： 與情況6類似。

情況8： 如果斜對角走把敵方棋子吃掉不會大大增加敵方棋子靈活性則斜著走，反之則走向空白區(qū)域。是否增加敵方靈活性需要根據(jù)局面評估算法判斷。

情況9： 與情況8類似。

情況10： 吃掉任意一個敵人均可，此時是橫著向左吃敵人還是豎著向上吃敵人要根據(jù)下文提到的局面評估算法來判斷。

情況11： 斜著走把敵人吃掉。

情況12： 與情況11類似。

情況13： 斜著走把敵人吃掉。

情況14： 橫著向左走把敵人吃掉。

情況15： 豎著向上走把敵人吃掉。

4） 主動吃掉對方棋子的情況

當敵方的棋子數(shù)目只有一個的時候，將其吃掉就可以以全殲的方式獲得本局勝利。

在敵方當前總棋子數(shù)目多于一個的前提下，如果此時我方被選中的棋子周圍的一個敵人離我方起點步數(shù)在兩步以內(nèi)，則應(yīng)該把它吃掉。如果有不止一個敵人到我方的起點不超過兩步，則視它們對我方的威脅程度選擇吃哪個棋子。優(yōu)先吃掉離我方終點最近的并且可以吃到的棋子，當有兩個或三個棋子都可以被我方被選中的棋子吃掉的時候，則根據(jù)具體情況選擇吃掉的棋子。具體情況如（圖7）所示。

圖7 主動吃對方棋子的情況

情況1：當上面和左邊的兩個敵人都可以被吃掉的時候，選擇吃掉對敵方靈活性影響不大的棋子。

情況2：當斜方向和正上方都有敵方棋子的時候，優(yōu)先選擇吃斜方向上的棋子，這樣可以使我方的棋子更接近敵方的起點。

情況3：處理方法與情況2類似。

情況4：首先考慮吃掉斜方向的棋子是否可以大大增強敵方的靈活性，如果吃掉斜方向的棋子后大大增強了敵方的靈活性，那么吃掉斜方向的棋子對我方而言就得不償失了。所以，吃掉斜方向的棋子可以大大增強敵方靈活性的時候，優(yōu)先選擇吃橫方向或者豎直方向的棋子。反之，吃掉斜方向的棋子。

3 愛恩斯坦棋之靜態(tài)防守策略

當我方被選中的棋子走某一步之后會碰到被敵方三個棋子包圍的情況，那么這一步就千萬不要走，否則的話等于是羊入虎口。

當我方被選中的棋子走某一步之后會碰到被敵方兩個棋子包圍的情況，是否可以走這步，需要具體情況具體分析，情況如（圖8）所示。

圖8 走一步以后碰到兩個敵人包圍的情況（紅點表示走了某一步后到達的位置）

當紅A和紅B兩個棋子（A和B代表該棋子上的數(shù)字）數(shù)字的絕對值之差不超過3，那么此時如果將我方棋子移動到紅點位置，很有可能被紅A或者紅B吃掉。所以這種情況下出于防守思維的考慮，不應(yīng)將我方被選中的棋子移動到紅點位置。

4 愛恩斯坦棋之初始布局設(shè)計

由于愛恩斯坦棋本身是一種依靠骰子來決定棋子移動的棋種，因此能夠讓棋子本身更為靈活移動就極為重要了。本次采取的策略是以犧牲一小部分棋子為代價來換取一定的靈活性，但不會為了絕對的靈活性而導致自身處于危險的境地。

對我方的棋子分別登記編號，則對應(yīng)的邊緣的三個棋子將作為被吃掉的棋子來換取靈活性。當初始的骰子置為內(nèi)部的三個棋子時，采取吃掉周圍的棋子來換取靈活性。吃掉的最大的棋子個數(shù)應(yīng)該為三個，此時具有相對較大的靈活性，而且比較穩(wěn)固，避免了被全盤吃掉的危險。而且三個棋子的狀態(tài)在攻擊和防守均具有一定的優(yōu)勢。

經(jīng)過探究發(fā)現(xiàn)初始局面應(yīng)該保證吃掉后的棋盤只剩下1， 3， 5時，（或者只剩下2，4，6，總之最好是間斷序列。）此時可以獲得更多的靈活性，同樣的一個骰子的點數(shù)可以選擇移動兩個棋子，而且此時一個棋子移動的概率也會大大增加，此時能夠獲得非常理想的效果。

本策略我方采取的初始棋局布置如（圖9）所示。

圖9 初始棋盤布置

將2，4，6布置在外面從而方便1，3，5棋子吃掉它，獲取一定的靈活性，如果運氣比較差一直投擲的是比較恒定的外圍的棋子，那么其移動將會以接近終點的方式進行，此時可以對此靈活策略進行調(diào)整，改為進攻模式，即其他棋子防止對先鋒棋子自殘，維持先鋒棋子的優(yōu)勢。

在己方的危險區(qū)域（靠近終點一格和二格的位置），采取優(yōu)先消滅對方危險棋子的策略，即此時應(yīng)盡可能吃掉對方的棋子來消除危險，而在危險區(qū)域以外，將以優(yōu)先走到終點為主。同時要注意的是如果對方只剩下一個棋子的時候，應(yīng)該采用同樣的消滅對方的策略。

5 愛恩斯坦棋之局面評估算法

愛恩斯坦棋的靜態(tài)評估策略主要集中在骰子選數(shù)函數(shù)上，因為骰子數(shù)是固定的，每一輪一旦骰子擲出，如果棋盤上有骰子數(shù)對應(yīng)的棋子的時候，那么就別無選擇地走那個棋子。所以只有在骰子數(shù)對應(yīng)的棋子被吃掉，此時才可以就近選擇兩邊的棋子。根據(jù)規(guī)則，如果骰子數(shù)對應(yīng)的棋子被吃掉了，那么可以選擇其數(shù)字兩端與其最接近的數(shù)的棋子，比如2和3被吃掉了，那么此時如果1和4都存在并且骰子數(shù)為2或者3的時候，走1號棋子和走4號棋子都是符合規(guī)則的。有一種情況，比如1，2，3號棋子都被吃掉了，4，5和6在棋盤上，如果骰子數(shù)是1，2或者是3，那么此時都只能走4號棋子，不能認為數(shù)軸是循環(huán)的，即不能認為6在1的左邊。那么當有兩個棋子都可以選的時候，選擇誰更能讓自己贏的概率大呢？我們可以通過做大量的模擬實驗總結(jié)規(guī)律，然后得出一套評分法則，即誰更有優(yōu)勢就讓誰的分數(shù)多一些，通過分數(shù)對比，選擇更合適的棋子走棋。下面是本文的評分標準，僅供參考。

走一步就可以到達終點加10000分。橫豎斜三個方向之一有敵人且敵人距離我方起點只有一步，敵人再走一步就能獲勝加5000分。走兩步能到達終點加1000分。敵人距離我方起點兩步以內(nèi)加500分。其他情況根據(jù)坐標位置計分。

選擇棋子的具體實現(xiàn)流程為：首先，當骰子數(shù)對應(yīng)的棋子已經(jīng)被吃掉的時候，上下分別搜索離其最近的棋子；然后，通過算法選出兩個可以走棋的棋子；再通過評估函數(shù)計算出這兩個棋子相應(yīng)的分值，分值高的棋子為本輪走棋棋子。

6 總結(jié)

經(jīng)過大量模擬實驗，該策略在和隨機策略的比賽試驗中，具有明顯的優(yōu)勢，并且該策略輔助應(yīng)用于“東大杯第二屆全國大學生計算機博弈大賽暨第六屆全國計算機博弈錦標賽”愛恩斯坦棋項目的比賽中，在這項比賽中本組成員獲得了一等獎的好成績，側(cè)面證實了這種策略具有一定的優(yōu)越性和實用性。今后我們會繼續(xù)完善和加強對靜態(tài)攻防策略的研究。

參考文獻：

[1] 徐心和， 王驕. 中國象棋計算機博弈關(guān)鍵技術(shù)分析[J]. 小型微型計算機系統(tǒng)， 2006， 27（6）： 961-969.

[2] 《編程之美》小組. 《編程之美》： 中國象棋將帥問題[J]，北京：電子工業(yè)出版社2008.3.

[3] Alth?fer， I. On the origins of EinStein würfelt nicht！[EB/OL]. Http：//www.althofer.de/origins-of-ewn.html.

[4] 王驕， 徐心和. 計算機博弈： 人工智能的前沿領(lǐng)域： 全國大學生計算機博弈大賽[J]. 計算機教育， 2012（7）： 14-18.