周文敏 李淑琴

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

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

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

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

1 愛恩斯坦棋簡介

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

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

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

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

4）紅方棋子走動(dòng)方向?yàn)橄蛴?、向下、向右下，每次走?dòng)一格；藍(lán)方棋子走動(dòng)方向?yàn)橄蜃?、向上、向左上，每次走?dòng)一格；

5）如果在棋子走動(dòng)的目標(biāo)棋位上有棋子，則要將該棋子從棋盤上移出（吃掉）。有時(shí)吃掉本方棋子也是一種策略，因?yàn)榭梢栽黾悠渌遄幼邉?dòng)的機(jī)會(huì)與靈活性；

6）率先到達(dá)對(duì)方出發(fā)區(qū)角點(diǎn)或?qū)?duì)方棋子全部吃掉的一方獲勝；

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

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

圖1 愛恩斯坦棋棋盤

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

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

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

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

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

圖2 愛恩斯坦棋某個(gè)棋盤布局

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

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

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

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

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

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

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

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

1）離終點(diǎn)只有一步的情況

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

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

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

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

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

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

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

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

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

3）避開我方棋子的情況

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

圖6 避開我方棋子的情況

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

情況2：直接走斜線，因?yàn)檫@樣到達(dá)終點(diǎn)的速度最快，又不會(huì)使我方的棋子數(shù)目減少，防止被對(duì)方全殲的危險(xiǎn)。

情況3： 與情況2類似。

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

情況5： 與情況4類似。

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

情況7： 與情況6類似。

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

情況9： 與情況8類似。

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

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

情況12： 與情況11類似。

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

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

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

4） 主動(dòng)吃掉對(duì)方棋子的情況

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

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

圖7 主動(dòng)吃對(duì)方棋子的情況

情況1：當(dāng)上面和左邊的兩個(gè)敵人都可以被吃掉的時(shí)候，選擇吃掉對(duì)敵方靈活性影響不大的棋子。

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

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

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

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

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

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

圖8 走一步以后碰到兩個(gè)敵人包圍的情況（紅點(diǎn)表示走了某一步后到達(dá)的位置）

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

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

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

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

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

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

圖9 初始棋盤布置

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

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

5 愛恩斯坦棋之局面評(píng)估算法

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

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

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

6 總結(jié)

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

參考文獻(xiàn)：

[1] 徐心和， 王驕. 中國象棋計(jì)算機(jī)博弈關(guān)鍵技術(shù)分析[J]. 小型微型計(jì)算機(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] 王驕， 徐心和. 計(jì)算機(jī)博弈： 人工智能的前沿領(lǐng)域： 全國大學(xué)生計(jì)算機(jī)博弈大賽[J]. 計(jì)算機(jī)教育， 2012（7）： 14-18.