一種生成殘局數據庫的倒推算法

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

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

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

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

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

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

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

1 局面勝率的倒推公式

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

“己方已走勝率”指己方落子后形成局面的勝率?！凹悍揭炎邉俾省睂木置鏋榧悍竭_成勝利條件的局面。

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

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

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

圖1 狀態的轉換關系

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

(1)

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

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

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

“擲前未走”狀態下對應“未走勝率”，擲得每個骰子點數的概率相同，擲出骰子后轉換“擲后未走”狀態，“擲后勝率”對應“未走勝率”，那么未走勝率的數學期望就是當前局面點數1到6擲后勝率的平均值，設當前局面B下的未走勝率為Wb，則

(2)

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

圖2 各勝率的互化關系

對于3種勝率互化的式子聯立可得：

(3)

式中，可視B為B(0)，即走0步后形成局面的單個元素的集合。B(0)若設定為己方為“未走”狀態，對方為“已走”狀態，則B(1)(p)為雙方走了1步后對B(0)的雙方狀態進行交換后的狀態，即B(1)(p)的狀態變為己方為“已走”，對方變為“未走”的狀態，以此類推，每步后的局面集合都對上一步的雙方狀態進行交換。

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

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

(4)

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

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

(5)

一方棋子對應的點數集合為p={1，2，3，4，5，6}，將B1(p)展開成集合，可以發現，對于一方連續的被移除棋子其對應點數集合PN={p1，p2,…,pn}，每個元素的上子相同，下子也相同。上子對應點數pu的可行走法為集合pN共有的上子可行走法{Bpuuh，Bpuus，Bpuux}，下子對應點數pd對應點數的可行走法為集合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)

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

2 倒推的架構

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

圖3 棋盤位置編號示意圖

“路徑”指當前局面不斷行棋直到游戲結束的具體走法。在一個路徑所代表的走法中，雙方移動的總步數就是該路徑的步數?！奥窂浇涍^該局面”指代路徑行棋中形成的局面；“路徑指向該局面”指代到游戲結束形成的局面。

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

圖4 復雜度行棋推進示意圖

3 倒推的過程

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

(7)

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

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

(8)

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

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

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

圖5 倒推局面節點示意圖

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

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

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

(9)

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

圖6 倒推局面生成流程

這是一個由復雜度倒推生成局面復雜度的過程。當以上過程完成后，所有定義的局面都計算得到其準確勝率。

4 針對殘局庫的倒推

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

愛恩斯坦棋殘局數據庫的局面數量僅與各方的棋子數有關，當殘局數據庫存儲每方3個棋子時，局面復雜度分布如表1所示。

表1 局面復雜度分布

5 殘局庫的有效性驗證

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

圖7 局面勝率測試結果

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

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

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

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

6 結論

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