梅 險(xiǎn)，陳泳吉，何 哲，潘子翔，陳姝含，周 霖

(哈爾濱理工大學(xué) a.計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院;b.測(cè)控技術(shù)與通信工程學(xué)院，哈爾濱 150080)

愛恩斯坦棋[1]是一個(gè)以隨機(jī)性為主要特征的博弈項(xiàng)目，對(duì)于所有參與者具有信息對(duì)稱的特性。建立棋局?jǐn)?shù)據(jù)庫(kù)是一種能夠靜態(tài)保存棋局狀態(tài)及對(duì)應(yīng)棋局勝率的方法。對(duì)于愛恩斯坦棋的棋局?jǐn)?shù)據(jù)庫(kù)如何調(diào)用倒推逆向分析算法來有效“窮盡”棋局的狀況，取其中部分局面生成殘局庫(kù)，是本文主要的研究方向。

在博弈對(duì)局中隨著對(duì)局的進(jìn)行，棋盤棋子數(shù)量逐漸減少的相關(guān)棋類最終不存在平局的情況，我們稱這些棋種是收斂的。將愛恩斯坦棋作為這類棋種實(shí)現(xiàn)殘局?jǐn)?shù)據(jù)庫(kù)的標(biāo)志性代表。

“殘局”是對(duì)雙方棋子均已行動(dòng)但雙方仍然處于對(duì)峙狀態(tài)的一種描述，我們可以在有限的內(nèi)存中存儲(chǔ)殘局?jǐn)?shù)據(jù)構(gòu)建成為殘局?jǐn)?shù)據(jù)庫(kù)。對(duì)于完全信息博弈項(xiàng)目在博弈雙方完全理性的情況下，一個(gè)局面最終的勝負(fù)是確定的，殘局?jǐn)?shù)據(jù)庫(kù)僅需存儲(chǔ)每個(gè)局面使用搜索算法與逆向分析之后最終的勝負(fù)情況[2-3]，而對(duì)于愛恩斯坦棋的特性，必須存儲(chǔ)一個(gè)局面的勝率，通過比較不同局面的勝率去選擇最優(yōu)走法[4]。

殘局?jǐn)?shù)據(jù)庫(kù)的存在能夠大大降低勝率評(píng)估時(shí)的計(jì)算復(fù)雜度。此外，由殘局?jǐn)?shù)據(jù)庫(kù)得到的勝率是真實(shí)的勝率，其精確度遠(yuǎn)高于通過算法對(duì)勝率的估計(jì)，因此，可以將搜索算法同殘局?jǐn)?shù)據(jù)庫(kù)進(jìn)行有效結(jié)合，從而提高對(duì)局的最終勝率[5]。

在本文中，通過推導(dǎo)逆向分析代碼，實(shí)現(xiàn)在各方棋子數(shù)量均不超過3的情況下的倒推計(jì)算，建立殘局?jǐn)?shù)據(jù)庫(kù)。最終通過實(shí)驗(yàn)證明，倒推算法生成的殘局?jǐn)?shù)據(jù)庫(kù)能夠有效提高搜索算法效率[6-7]。

1 局面勝率的倒推公式

局面勝率分為“已走勝率”和“未走勝率”，對(duì)局雙方均有此概念定義，以下概念描述以己方為例。

“己方已走勝率”指己方落子后形成局面的勝率。“己方已走勝率”對(duì)應(yīng)的局面為己方達(dá)成勝利條件的局面。

“己方未走勝率”指對(duì)方剛走完，己方尚未行動(dòng)時(shí)己方的勝率?！凹悍轿醋邉俾省睂?duì)應(yīng)的局面為對(duì)方達(dá)成勝利條件的局面(為了理論上的對(duì)應(yīng)，認(rèn)為對(duì)方達(dá)成勝利條件的情況下，存在己方處于未走且己方勝率為0的狀態(tài))。同時(shí)，“己方未走勝率”所描述的局面是己方尚未擲骰子時(shí)的狀態(tài)，已經(jīng)擲骰子的狀態(tài)另有概念。

為了區(qū)分玩家未走時(shí)骰子的情況，將擲骰子后的勝率稱為“擲后勝率”。玩家對(duì)局時(shí)要在此狀態(tài)下做出決策?！皵S后勝率”的計(jì)算除了須知局面信息外，還須結(jié)合骰子的點(diǎn)數(shù)。

對(duì)于一方“擲前未走”的狀態(tài)，另一方就是“已走”狀態(tài)，2種狀態(tài)相互對(duì)應(yīng)，因此將“擲前未走”狀態(tài)下的勝率稱為“未走勝率”，而“擲后未走”是便于整體計(jì)算的一種中間狀態(tài)。雙方勝率的相關(guān)計(jì)算同理。狀態(tài)的轉(zhuǎn)換關(guān)系如圖1所示。

圖1 狀態(tài)的轉(zhuǎn)換關(guān)系

愛恩斯坦棋屬于零和博弈，且不存在平局的情況，因此在同一局面下雙方勝率之和為1。對(duì)應(yīng)一方的“已走”狀態(tài)下就是另一方的“擲前未走”狀態(tài)，那么已走狀態(tài)下勝率為“已走勝率”，對(duì)應(yīng)對(duì)方的“未走勝率”。即在某一局面B下，設(shè)已走狀態(tài)為a，未走狀態(tài)為b，己方為W，對(duì)方為W′，則己方已走勝率等于1減去對(duì)方未走勝率的差：

(1)

在本文中，等于骰子數(shù)的己方棋子存活時(shí)，該棋子稱為上子，當(dāng)棋子已不存在時(shí)，大于骰子數(shù)的最接近存活己方棋子稱為上子；小于骰子數(shù)最接近且存在的己方棋子稱為下子。對(duì)于每方可以走的棋子均有橫走、豎走、斜走3種走法。

以u(píng)、d分別代表點(diǎn)數(shù)p對(duì)應(yīng)的上子和下子，h、s、x分別代表橫走、豎走、斜走(對(duì)于紅方為向右、向下、向右下；對(duì)于藍(lán)方為向左，向上，向左上)，那么對(duì)于集合B(1)(p)元素最多為B(1)(p)={Bpuh，Bpus，Bpux，Bpdh，Bpds，Bpdx}(如Bpuh代表在B局面下點(diǎn)數(shù)p的上子橫走所形成的局面)，且其中一些元素可能由于無下子、走法越過棋盤邊界等情況導(dǎo)致其不存在于場(chǎng)上。

擲后勝率：符號(hào)設(shè)為Wr，為當(dāng)前局面B與骰子數(shù)p下每種可行走法后形成新局面的已走勝率Wa的最大值，即Wr(B，p)=maxWa(B(1)(p))；對(duì)方同理，Wr′(B，p)=maxWa′(B(1)(p))。

“擲前未走”狀態(tài)下對(duì)應(yīng)“未走勝率”，擲得每個(gè)骰子點(diǎn)數(shù)的概率相同，擲出骰子后轉(zhuǎn)換“擲后未走”狀態(tài)，“擲后勝率”對(duì)應(yīng)“未走勝率”，那么未走勝率的數(shù)學(xué)期望就是當(dāng)前局面點(diǎn)數(shù)1到6擲后勝率的平均值，設(shè)當(dāng)前局面B下的未走勝率為Wb，則

(2)

式(2)建立了在某一局面B下“已走勝率Wa”“未走勝率Wb”“擲后勝率Wr”這三者中任意兩者之間的互化關(guān)系，其中“已走勝率Wa”和“未走勝率Wb”兩者的互化包含了敵我雙方的勝率互化(圖2)。

圖2 各勝率的互化關(guān)系

對(duì)于3種勝率互化的式子聯(lián)立可得：

(3)

式中，可視B為B(0)，即走0步后形成局面的單個(gè)元素的集合。B(0)若設(shè)定為己方為“未走”狀態(tài)，對(duì)方為“已走”狀態(tài)，則B(1)(p)為雙方走了1步后對(duì)B(0)的雙方狀態(tài)進(jìn)行交換后的狀態(tài)，即B(1)(p)的狀態(tài)變?yōu)榧悍綖椤耙炎摺?，?duì)方變?yōu)椤拔醋摺钡臓顟B(tài)，以此類推，每步后的局面集合都對(duì)上一步的雙方狀態(tài)進(jìn)行交換。

為了表述方便，將紅方作為己方，藍(lán)方作為對(duì)方。

在進(jìn)行勝率推算時(shí)，可以保持以其中一方作為己方計(jì)算勝率，將雙方“局面互換”?！熬置婊Q”也包括“位置互換”和“顏色互換”。此時(shí)雙方的“已走勝率”“未走勝率”“擲后勝率”也都交換，這時(shí)計(jì)算互換后紅方的各勝率其實(shí)是計(jì)算藍(lán)方的各勝率。將局面B進(jìn)行局面互換后形成的新局面記作B′，則：

(4)

為了方便運(yùn)算，用B′(i)(pi)來表示紅方走了i步且每走一步都執(zhí)行局面互換時(shí)所形成局面集合。當(dāng)i為偶數(shù)，B′(i)(pi)=B(i)(pi)，當(dāng)i為奇數(shù)，B′(i)(pi)等于B(i)(pi)每個(gè)元素都進(jìn)行局面互換形成的集合。

在局面互換的條件下，根據(jù)式(3)，可得局面倒推的公式：

(5)

一方棋子對(duì)應(yīng)的點(diǎn)數(shù)集合為p={1，2，3，4，5，6}，將B1(p)展開成集合，可以發(fā)現(xiàn)，對(duì)于一方連續(xù)的被移除棋子其對(duì)應(yīng)點(diǎn)數(shù)集合PN={p1，p2,…,pn}，每個(gè)元素的上子相同，下子也相同。上子對(duì)應(yīng)點(diǎn)數(shù)pu的可行走法為集合pN共有的上子可行走法{Bpuuh，Bpuus，Bpuux}，下子對(duì)應(yīng)點(diǎn)數(shù)pd對(duì)應(yīng)點(diǎn)數(shù)的可行走法為集合PN共有的下子可行走法{Bpuuh，Bpdus，Bpdux}，由此集合PN共有可行走法的集合為{Bpuuh，Bpuus，Bpuux，Bpduh，Bpdus，Bpdux}

可知對(duì)于集合PN中任意一個(gè)元素px都有B(1)(pu)∪B(1)(pd)=B(1)(px)，那么：

maxWb(B(1)(px))=maxWb(B(1)(pu)∪B(1)(pd))

(6)

因此不需要對(duì)被移除棋子的勝率進(jìn)行單獨(dú)計(jì)算，將之轉(zhuǎn)化為棋上子或下子中最大未走勝率的倍率即可。于是設(shè)置未乘概率和倍率2個(gè)概念：當(dāng)一個(gè)己方棋子存活時(shí)，其未乘概率等于對(duì)應(yīng)的擲后勝率Wr(B，p)，否則等于0；初始每個(gè)棋子對(duì)應(yīng)倍率為0，若該棋子存活則其倍率+1，否則其上子和下子中未乘概率最大的棋子對(duì)應(yīng)的倍率+1，于是式子(2)可以化成以下偽代碼：

2 倒推的架構(gòu)

局面的數(shù)據(jù)以如下形式進(jìn)行組織：以一個(gè)12位的26進(jìn)制數(shù)代表一個(gè)局面，每一位分別代表雙方每個(gè)棋子{1，2，3，4，5，6，-1，-2，-3，-4，-5，-6}的位置，數(shù)字0～24代表對(duì)應(yīng)棋子在5*5棋盤上的位置，數(shù)字25代表對(duì)應(yīng)棋子已從棋盤上移除(圖3)。局面的情況對(duì)應(yīng)一個(gè)特定的26進(jìn)制數(shù)，該數(shù)可以作為勝率數(shù)組的下標(biāo)。

圖3 棋盤位置編號(hào)示意圖

“路徑”指當(dāng)前局面不斷行棋直到游戲結(jié)束的具體走法。在一個(gè)路徑所代表的走法中，雙方移動(dòng)的總步數(shù)就是該路徑的步數(shù)?！奥窂浇?jīng)過該局面”指代路徑行棋中形成的局面；“路徑指向該局面”指代到游戲結(jié)束形成的局面。

“局面復(fù)雜度C”：指在某一局面下，所有路徑的最大步數(shù)。路徑上經(jīng)過的每一個(gè)局面復(fù)雜度均比上一個(gè)局面對(duì)應(yīng)的復(fù)雜度低。如圖4所示。

圖4 復(fù)雜度行棋推進(jìn)示意圖

3 倒推的過程

Wa({B′(1)(p)|1≤p≤6，p∈Z})均已生成是生成Wa(B)的充分條件，將以下函數(shù)稱為對(duì)局面或局面集合B的正推展開，其中已勝局面是指達(dá)成勝利條件之一的局面：

(7)

即取B局面互換條件下所有路徑中下一步所經(jīng)過的全部局面的集合。經(jīng)過正推展開得到的局面復(fù)雜度至少比原局面低1。當(dāng)一個(gè)局面正推展開所得到的局面集合中所有局面已走勝率均已得知時(shí)，則可根據(jù)式(5)算出原局面的對(duì)應(yīng)局面勝率。對(duì)于已知Wa({B′(1)(p)|1≤p≤6，p∈Z})，根據(jù)式(4)可計(jì)算Wa(B)，稱局面B為{B′(1)(p)|1≤p≤6，p∈Z}的倒推收斂，為正推展開的逆過程：

g-1({B′(1)(p)|1≤p≤6，p∈Z})=B

(8)

對(duì)當(dāng)前局面進(jìn)行正推展開得到的末節(jié)點(diǎn)進(jìn)行估值后，進(jìn)行倒推收斂得到當(dāng)前局面的估計(jì)勝率，這是愛恩斯坦棋使用極大極小值[8]算法構(gòu)建博弈樹的過程[9]。而對(duì)于UCT算法則是選擇性的正推展開與倒推收斂[10]。

當(dāng)對(duì)一個(gè)局面進(jìn)行多次正推展開，直至完全展開到每一條路徑的終點(diǎn)，最終會(huì)完全展開為一個(gè)已勝局面集合，而所有已勝局面對(duì)應(yīng)局面勝率均為1，即已知。因此，任意存在的局面均可從已勝局面集合中倒推收斂，生成其對(duì)應(yīng)勝率。

要生成Wa(B)，則需可倒推收斂于Wa(B)的局面先生成。這些所需局面相對(duì)于所收斂的局面來說，其對(duì)應(yīng)的局面復(fù)雜度更低。將達(dá)成勝利條件的己方已走局面的局面復(fù)雜度定為0，先生成所有局面復(fù)雜度的局面，再依次生成C=1的局面、C=2的局面、C=3的局面，以此類推[11]。如圖5所示。

圖5 倒推局面節(jié)點(diǎn)示意圖

局面復(fù)雜度最高的局面為開局局面(任意排列的開局局面復(fù)雜度是相同的)。局面復(fù)雜度與棋子點(diǎn)數(shù)、搖到的隨機(jī)數(shù)無關(guān)。在復(fù)雜度的視角里，局面只留下了己對(duì)方、位置2種屬性。將已勝局面用復(fù)雜度0標(biāo)記，把不存在局面用-1標(biāo)記，未生成局面用-2標(biāo)記。則局面復(fù)雜度標(biāo)記集合為{-2，-1，0，1，…，i}，其中i為開局的局面復(fù)雜度。

將得到的所有正推展開包含局面B的局面集合，稱為對(duì)B的倒推展開r(B)。這些局面包括了對(duì)于己方每個(gè)存活棋子在任意方向后退且不越過邊界、不與其他棋子重疊所得到的局面，以及在每種情況都有在原位置重新放置任一已被吃的棋子，然后經(jīng)過局面互換后得到的局面[12]。通過倒推展開局面B能夠找出所有局面復(fù)雜度可能比B對(duì)應(yīng)局面復(fù)雜度高1的局面。

r(B)={B1|B∈g(B1)}

(9)

在局面互換條件下的倒推過程中，將會(huì)以“臨時(shí)局面復(fù)雜度c”對(duì)每個(gè)局面進(jìn)行標(biāo)記，以方便計(jì)算?？傮w局面為有存儲(chǔ)、計(jì)算框架規(guī)定的所有存在局面與不存在局面的總和，在倒推前將總體局面標(biāo)記為c=-2。在對(duì)某個(gè)局面的臨時(shí)局面復(fù)雜度進(jìn)行重新標(biāo)記時(shí)，c=-1和c=0的局面不可被重新標(biāo)記。圖6為倒推時(shí)局面的生成流程。

圖6 倒推局面生成流程

這是一個(gè)由復(fù)雜度倒推生成局面復(fù)雜度的過程。當(dāng)以上過程完成后，所有定義的局面都計(jì)算得到其準(zhǔn)確勝率。

4 針對(duì)殘局庫(kù)的倒推

在當(dāng)前生成如此龐大的數(shù)據(jù)量不現(xiàn)實(shí)，將只生成和存儲(chǔ)部分已勝局面勝率數(shù)據(jù)作為殘局庫(kù)，利用存儲(chǔ)的部分?jǐn)?shù)據(jù)提高算法搜索效率與準(zhǔn)確性，只生成和存儲(chǔ)除指定的幾個(gè)棋子外其他棋子都已被吃的局面的勝率。在進(jìn)行倒推展開時(shí)，去除包含非局面組織棋子的局面，超出存儲(chǔ)范圍內(nèi)的局面將不會(huì)被生成[13-14]。

愛恩斯坦棋殘局?jǐn)?shù)據(jù)庫(kù)的局面數(shù)量?jī)H與各方的棋子數(shù)有關(guān)，當(dāng)殘局?jǐn)?shù)據(jù)庫(kù)存儲(chǔ)每方3個(gè)棋子時(shí)，局面復(fù)雜度分布如表1所示。

表1 局面復(fù)雜度分布

5 殘局庫(kù)的有效性驗(yàn)證

為了證實(shí)殘局庫(kù)的有效性與正確性，任意選取對(duì)局中的可窮舉殘局進(jìn)行測(cè)試，從殘局庫(kù)中提取對(duì)應(yīng)局面的已走勝率，與窮舉搜索算法結(jié)果對(duì)比，驗(yàn)證殘局庫(kù)數(shù)據(jù)的準(zhǔn)確性。例如在對(duì)局測(cè)試?yán)?，紅1向3個(gè)方向移動(dòng)后的形成局面的已走勝率如圖7所示。

圖7 局面勝率測(cè)試結(jié)果

在任意搜索算法可窮舉局面中，殘局庫(kù)中保存的局面數(shù)據(jù)與窮舉搜索算法得到的局面已走勝率數(shù)據(jù)完全相同，說明在可測(cè)試范圍內(nèi)。

將愛恩斯坦棋極大極小值α-β剪枝算法程序引入倒推算法獲取殘局庫(kù)設(shè)為實(shí)驗(yàn)組，并將原程序設(shè)為對(duì)照組，比較實(shí)驗(yàn)組和對(duì)照組在對(duì)抗其他程序時(shí)的獲勝概率。經(jīng)過實(shí)驗(yàn)得到如圖8所示的柱狀圖。

圖8 引入殘局庫(kù)前后獲勝概率

引入殘局庫(kù)后程序獲勝概率顯著增加，可知倒推算法生成的殘局?jǐn)?shù)據(jù)庫(kù)能夠幫助局面評(píng)估算法提升獲勝概率。

6 結(jié)論

不僅是愛恩斯坦棋，對(duì)于任意收斂的信息對(duì)稱博弈項(xiàng)目(包括隨機(jī)棋類博弈)，都能倒推生成殘局庫(kù)，甚至在存儲(chǔ)容量足夠的情況下生成全部局面。但受到數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)和容量的限制，愛恩斯坦棋倒推生成的殘局庫(kù)體量仍然不足。過去的研究中有使用逆向分析的方法獲取完全博弈項(xiàng)目局面情況的，但由于其博弈項(xiàng)目不具有隨機(jī)性，得到的局面情況若以勝率表示則非0即1，且推知?jiǎng)俾什恍枰?jì)算。首次在隨機(jī)博弈項(xiàng)目中詳細(xì)研究了倒推生成局面勝率的方法，設(shè)計(jì)了按照局面復(fù)雜度逐步推知局面勝率的計(jì)算過程。通過該研究發(fā)現(xiàn)，生成的愛恩斯坦棋殘局庫(kù)可幫助其他搜索算法減少搜索量、提高準(zhǔn)確性，以此提升算法的勝率。