一種生成殘局?jǐn)?shù)據(jù)庫的倒推算法

梅 險，陳泳吉，何 哲，潘子翔，陳姝含，周 霖

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

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

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

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

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

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

1 局面勝率的倒推公式

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

“己方已走勝率”指己方落子后形成局面的勝率?！凹悍揭炎邉俾省睂?yīng)的局面為己方達成勝利條件的局面。

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

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

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

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

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

(1)

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

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

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

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

(2)

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

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

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

(3)

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

為了表述方便，將紅方作為己方，藍方作為對方。

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

(4)

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

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

(5)

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

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

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

(6)

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

2 倒推的架構(gòu)

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

圖3 棋盤位置編號示意圖

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

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

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

3 倒推的過程

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

(7)

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

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

(8)

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

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

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

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

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

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

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

(9)

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

圖6 倒推局面生成流程

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

4 針對殘局庫的倒推

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

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

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

5 殘局庫的有效性驗證

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

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

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

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

圖8 引入殘局庫前后獲勝概率

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

6 結(jié)論

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