四國軍棋游戲復(fù)雜度研究

鄧 紅

（無錫機(jī)電高等職業(yè)技術(shù)學(xué)校，江蘇 無錫 214028）

0 引言

目前，對(duì)于部分完全信息游戲，已經(jīng)得到了理論解，如五子棋[1]、四子棋[2]、西洋跳棋[3]；對(duì)于一些狀態(tài)復(fù)雜度較高的完全信息游戲，如中國象棋、國際象棋和圍棋等，研究人員也開發(fā)出了可以戰(zhàn)勝人類頂級(jí)玩家的程序，完全信息游戲的研究不斷取得新突破[4]。而在非完全信息游戲研究方面，除少數(shù)較為簡單的游戲外，較為復(fù)雜的非完全信息游戲，還未出現(xiàn)可以完全戰(zhàn)勝人類頂級(jí)玩家的程序。四國軍棋游戲是典型的非完全信息游戲。國內(nèi)的研究人員已經(jīng)對(duì)四國軍棋的博弈問題進(jìn)行了一些研究[5-8]，提出了如多棋子協(xié)同博弈、UCT 算法應(yīng)用、定式庫的設(shè)計(jì)和研究、無約束推理、有約束推理等辦法，但四國軍棋的空間和時(shí)間復(fù)雜度較高，導(dǎo)致四國軍棋的研究較為困難，因此有必要通過理論研究，對(duì)非完全信息游戲復(fù)雜度進(jìn)行分析，為非完全信息游戲的破解提供支撐。

1 完全信息游戲復(fù)雜度的研究情況

1.1 狀態(tài)復(fù)雜度

狀態(tài)復(fù)雜度是指游戲?qū)?zhàn)過程中出現(xiàn)的所有局面的總數(shù)。國內(nèi)外對(duì)完全信息游戲的研究較早，一些比較經(jīng)典的游戲，如國際象棋、中國象棋、日本將棋和圍棋[9-11]，均有研究人員對(duì)其狀態(tài)復(fù)雜度進(jìn)行了相關(guān)研究，如表1 所示。

表1 常見游戲的狀態(tài)復(fù)雜度

以圍棋為例，圍棋共有19×19 即361 個(gè)位置，每個(gè)位置上可以是黑子、白子或者空置，所以圍棋的狀態(tài)復(fù)雜度為3361≈10172。該估算方法包含了一些圍棋規(guī)則不允許的狀態(tài)和不可能出現(xiàn)的狀態(tài)，即10172是圍棋出現(xiàn)的所有狀態(tài)的上限，完全信息游戲狀態(tài)復(fù)雜度計(jì)算方法如公式（1）所示。

其中，SSC 為狀態(tài)復(fù)雜度，S 為每個(gè)位置可能的狀態(tài)數(shù)，L 表示位置總數(shù)。

表1 為常見游戲的狀態(tài)復(fù)雜度，由于圍棋的棋盤較大、規(guī)則靈活，導(dǎo)致其狀態(tài)復(fù)雜度最高、且無法精密計(jì)算出合法局面。在2007 年，Jonathan-Schaeffer 等[3]通過證據(jù)計(jì)算法等得到了西洋跳棋的理論解，并計(jì)算出西洋跳棋共有5×1020個(gè)合法的局面。

每個(gè)完全信息游戲的棋盤大小、游戲規(guī)則、棋子種類、棋子個(gè)數(shù)等各不相同。對(duì)于較為簡單的游戲，計(jì)算機(jī)程序可以計(jì)算出所有的局面，因此計(jì)算機(jī)程序可以處于不敗之地。而對(duì)于較為復(fù)雜的游戲[12-13]，如圍棋、象棋等，計(jì)算機(jī)還沒有能力計(jì)算出可能出現(xiàn)的所有局面，因此只能粗略估算可能的局面總數(shù)，增加了計(jì)算機(jī)程序設(shè)計(jì)的難度。

1.2 博弈樹復(fù)雜度

博弈樹復(fù)雜度是某個(gè)游戲所有不同游戲路徑的數(shù)目。博弈樹復(fù)雜度比狀態(tài)復(fù)雜度要大得多，因?yàn)橥粋€(gè)狀態(tài)可以對(duì)應(yīng)不同的博弈順序。以井字棋游戲?yàn)槔ㄈ鐖D1 所示），當(dāng)盤面中有兩個(gè)X 和一個(gè)O 時(shí)，如果第一個(gè)玩家下X 的位置不同，則可能由不同的方式組成。

圖1 井字棋

研究人員通常使用平均合法移動(dòng)數(shù)目和平均游戲長度相乘的積，來估算博弈樹復(fù)雜度的下限[14]，完全信息游戲的博弈樹復(fù)雜度計(jì)算方法如公式（2）所示。

其中，GTC 為博弈樹復(fù)雜度，b 為玩家每回合可用的平均合法移動(dòng)數(shù)，p 表示平均游戲長度。

根據(jù)下棋的經(jīng)驗(yàn)，國際象棋和圍棋每次平均合法移動(dòng)數(shù)分別為35 和250[15]；平均游戲長度分別為80 和150。根據(jù)公式（2）推算，國際象棋的博弈樹復(fù)雜度為3580≈10123，即10123；圍棋的博弈樹復(fù)雜度為250150≈10360，即10360。常見的完全信息游戲的博弈樹復(fù)雜度如表2 所示。

表2 常見游戲的博弈樹復(fù)雜度

2 非完全信息游戲復(fù)雜度的研究

2.1 非完全信息游戲的特點(diǎn)

完全信息游戲的信息和規(guī)則對(duì)所有人都是透明的，是研究機(jī)器博弈理想的試驗(yàn)田。近年來，研究人員發(fā)現(xiàn)非完全信息游戲能更好地模擬現(xiàn)實(shí)世界，研究成果有助于解決實(shí)際問題，本文以典型的不完全信息游戲牌棋類為例，總結(jié)出不完全信息游戲有下述幾個(gè)特點(diǎn)。

（1）掌握有限信息。玩家一般只掌握己方的信息，不清楚對(duì)手和友軍的信息。（2）狀態(tài)復(fù)雜度和博弈樹復(fù)雜度較高。因?yàn)樾畔⑷笔?，一方?duì)整個(gè)局面的判斷不準(zhǔn)確，導(dǎo)致游戲復(fù)雜度大幅增加。（3）存在諸多不確定性。玩家掌握的信息可能是錯(cuò)誤的，根據(jù)錯(cuò)誤信息推算出的結(jié)果也是不準(zhǔn)確的。（4）合作較為困難。友軍之間掌握的信息不對(duì)稱，戰(zhàn)略和戰(zhàn)術(shù)意圖不一致，導(dǎo)致相互合作較為困難。（5）貼近現(xiàn)實(shí)世界。不完全信息游戲相較于完全信息游戲，更好地模仿了現(xiàn)實(shí)世界場景，不僅考驗(yàn)玩家的技術(shù)，也考驗(yàn)其心理素質(zhì)。

四國軍棋游戲是典型的非完全信息游戲，其特點(diǎn)如下：（1）棋子初始擺放限制較少，對(duì)棋子行走的規(guī)則限制少；（2）棋盤較大，共四方，每方共30個(gè)棋位（5 個(gè)行營、9 個(gè)公路棋位、16 個(gè)鐵路棋位），公共部分鐵路棋位9 個(gè)，合計(jì)129 個(gè)棋位；（3）棋子種類和數(shù)量多，每方有12 種25 個(gè)棋子，四方合計(jì)有100 個(gè)棋子。

2.2 四國軍棋游戲的狀態(tài)復(fù)雜度

在開局方面，四國軍棋和中國象棋比較相似，對(duì)戰(zhàn)各方首先進(jìn)行排兵布陣，四個(gè)方位的玩家需要將己方棋子排列在25 個(gè)棋位上（5 個(gè)行營不放棋子），開局時(shí)盤面上棋子最多（4 個(gè)玩家×25 個(gè)棋子/方=100 顆棋子），狀態(tài)最為復(fù)雜，開局后棋子逐漸減少，狀態(tài)復(fù)雜度降低。

首先分析一個(gè)玩家的狀態(tài)復(fù)雜度，其棋位上可能是四個(gè)玩家中的任意一種棋子，再推理出整個(gè)游戲的狀態(tài)復(fù)雜度，即非完全信息游戲的狀態(tài)復(fù)雜度，如公式（3）所示。

其中，SSC 為狀態(tài)復(fù)雜度，S 為玩家每個(gè)位置上可能的狀態(tài)數(shù)，L 表示位置總數(shù)，N 為玩家數(shù)。

四國軍棋游戲中，任一棋位上的棋子可能是己方12 種棋子，也可能是其他三方的12 種棋子；一方的位置總數(shù)為30 個(gè)。由此推算出四國軍棋的狀態(tài)復(fù)雜度為（12×4）4×30≈10201。

對(duì)比表1 中其他游戲的狀態(tài)復(fù)雜度，四國軍棋的狀態(tài)復(fù)雜最高，計(jì)算機(jī)不可能使用完全列舉法來求理論解，因此必須結(jié)合四國軍棋游戲特點(diǎn)，尋找出相應(yīng)的狀態(tài)分析辦法來求解。

2.3 四國軍棋游戲的博弈樹復(fù)雜度

四國軍棋游戲中，玩家知道己方棋子類型，再通過行棋規(guī)則、拼殺結(jié)果獲取另外三方棋子的部分信息，棋盤上所有棋子類型共48 種，結(jié)合完全信息游戲中博弈樹復(fù)雜度的計(jì)算規(guī)則，得出非完全信息游戲的博弈樹復(fù)雜度，如公式（4）所示。

其中，GTC 為博弈樹復(fù)雜度，S 為玩家每個(gè)位置可能的狀態(tài)數(shù)，b 為玩家每回合可用的平均合法移動(dòng)數(shù)，p 表示平均游戲長度，N 為玩家數(shù)。

四國軍棋游戲的平均分支為90，平均一局共有120 步[15]，根據(jù)公式（4），推算出四國軍棋的博弈樹復(fù)雜度：（48/4×90）120≈10360。對(duì)比表2 中其他游戲的博弈樹復(fù)雜度，四國軍棋和圍棋的博弈樹復(fù)雜度最高為10360，遠(yuǎn)高于其他棋牌類游戲。

四國軍棋游戲的博弈樹復(fù)雜度和圍棋相同，雖然目前沒有計(jì)算機(jī)程序和搜索算法可以遍歷其博弈樹的所有節(jié)點(diǎn)，但是已經(jīng)出現(xiàn)的完全信息游戲-圍棋程序AlphaGo 和不完全信息游戲-日本麻將SUPIX 程序，戰(zhàn)力均能和人類頂級(jí)玩家相媲美，研究人員可以結(jié)合深度學(xué)習(xí)，開發(fā)出越來越強(qiáng)的四國軍棋游戲程序。

3 結(jié)語

本文通過完全信息游戲中狀態(tài)復(fù)雜度和博弈樹復(fù)雜度，總結(jié)出完全信息游戲復(fù)雜度的計(jì)算方法，再結(jié)合非完全信息游戲特點(diǎn)，提出非完全信息游戲的復(fù)雜度計(jì)算方法，并推算出四國軍棋游戲有序的狀態(tài)和博弈樹復(fù)雜度。非完全信息游戲更接近現(xiàn)實(shí)世界，而四國軍棋游戲是一種典型的非完全信息游戲，推算出四國軍棋游戲復(fù)雜度，有助于四國軍棋游戲的破解，可為解決現(xiàn)實(shí)生活中的很多復(fù)雜問題提供參考。