中國(guó)象棋屬于EXPTIME-complete問(wèn)題

高強(qiáng)，徐心和

(東北大學(xué)信息科學(xué)與工程學(xué)院，沈陽(yáng) 110004)

中國(guó)象棋屬于EXPTIME-complete問(wèn)題

高強(qiáng)，徐心和

(東北大學(xué)信息科學(xué)與工程學(xué)院，沈陽(yáng) 110004)

尋找棋類游戲的理想解是計(jì)算機(jī)博弈研究的目標(biāo)，而計(jì)算復(fù)雜性是不可逾越的障礙。首先介紹了計(jì)算復(fù)雜性類中的EXPTIME-complete問(wèn)題及它的一個(gè)實(shí)例——G3游戲。構(gòu)建了一個(gè)n×n中國(guó)象棋的歸約模型，模型由6部分組成，分別為布爾控制器、開(kāi)關(guān)、子句通道與文字通道的交叉區(qū)域、兌子區(qū)域、延遲區(qū)域及九宮。在該模型上模擬進(jìn)行G3游戲，并最終證明了G3游戲可多項(xiàng)式時(shí)間內(nèi)歸約到n×n的中國(guó)象棋，從而證明了n×n的中國(guó)象棋屬于EXPTIME-complete問(wèn)題。

計(jì)算機(jī)博弈;中國(guó)象棋;計(jì)算復(fù)雜性;指數(shù)時(shí)間的完全問(wèn)題;歸約

計(jì)算機(jī)博弈是讓計(jì)算機(jī)給出著法，能夠下棋，屬于人工智能學(xué)科極具挑戰(zhàn)性的研究領(lǐng)域。計(jì)算機(jī)博弈的最高境界是找到該棋種的理想解，即不敗解。而計(jì)算機(jī)博弈的最大困難和無(wú)法逾越的障礙是求解問(wèn)題過(guò)程中的計(jì)算復(fù)雜性。通過(guò)對(duì)問(wèn)題的計(jì)算復(fù)雜性進(jìn)行分類可以了解該問(wèn)題被求解的難易程度，如果問(wèn)題被證明是難解的(例如NP-complete、PSPACE-complete及EXPTIME-complete)，則不必將大量的精力花費(fèi)在尋找問(wèn)題的解析解上，而只能去尋求某種近似解。國(guó)外有很多學(xué)者在研究計(jì)算機(jī)博弈問(wèn)題的計(jì)算復(fù)雜性，國(guó)際象棋［1］和西洋跳棋［2］被證明屬于EXPTIME-complete問(wèn)題。這2個(gè)棋種的計(jì)算復(fù)雜性證明在構(gòu)建模型的過(guò)程中，都用到了一個(gè)已被證明為EXPTIME-complete的G3游戲［3］。圍棋被證明屬于PSPACE-hard問(wèn)題［4］(圍棋也被懷疑屬于EXPTIME-complete問(wèn)題［1］)，五子棋［5］、六子棋［6］、奧賽羅棋［7］被證明屬于PSPACE-complete問(wèn)題。這些棋種的計(jì)算復(fù)雜性證明都用到了廣義地理學(xué)游戲(generalized geography game)［8］。亞馬遜被證明屬于PSPACE-complete問(wèn)題［9］，在證明過(guò)程中，它采用了一種公式博弈(formula game［8］)方法。

中國(guó)象棋是一種歷史悠久的棋類游戲。在兵種及走法方面，它與國(guó)際象棋有許多相似之處。9 ×10的中國(guó)象棋與8×8的國(guó)際象棋在狀態(tài)空間復(fù)雜度、博弈樹(shù)復(fù)雜度方面的比較見(jiàn)表1［10］。

表1 中國(guó)象棋與國(guó)際象棋的復(fù)雜度比較(數(shù)據(jù)以10為底)

由表1可見(jiàn):中國(guó)象棋的復(fù)雜度與國(guó)際象棋的復(fù)雜度相當(dāng)，既然n×n的國(guó)際象棋已被證明屬于EXPTIME-complete問(wèn)題，所以有理由推測(cè)n×n的中國(guó)象棋也應(yīng)屬于EXPTIME-complete問(wèn)題。

本文在第1節(jié)分析了EXPTIME-complete問(wèn)題及它的一個(gè)典型實(shí)例——G3游戲。根據(jù)計(jì)算復(fù)雜性類中完全問(wèn)題的定義［1］，首先在第2節(jié)證明了n×n的中國(guó)象棋屬于EXPTIME問(wèn)題，然后在第3節(jié)重點(diǎn)構(gòu)建了一個(gè)n×n中國(guó)象棋的歸約模型，并在此模型上模擬進(jìn)行G3游戲，證明了G3游戲可在多項(xiàng)式時(shí)間內(nèi)歸約到n×n中國(guó)象棋，從而證明了n×n中國(guó)象棋屬于EXPTIME-complete問(wèn)題。為了保證論述的嚴(yán)密性，第4節(jié)給出了歸約模型中不恰當(dāng)走法的分析。第5節(jié)對(duì)于此證明的完全性給出了論證。

1 EXPTIME-complete問(wèn)題

EXPTIME問(wèn)題的定義該復(fù)雜性類是一些確定型問(wèn)題的集合，這些問(wèn)題可以使用確定型圖靈機(jī)在O(2p(n))的時(shí)間內(nèi)解決，這里的p(n)代表n的某個(gè)多項(xiàng)式。屬于該復(fù)雜性的問(wèn)題，它的難度不小于P，NP，NP-complete以及空間復(fù)雜性類(PSPACE和PSPACE-complete)［11］。而EXPTIME-complete問(wèn)題是EXPTIME復(fù)雜性類中最難的問(wèn)題，其定義可參考其他復(fù)雜性類完全問(wèn)題的定義［1］，如下:

一個(gè)問(wèn)題B屬于EXPTIME-complete，如果它滿足2個(gè)條件:

1)B屬于EXPTIME;

2)每個(gè)屬于EXPTIME的問(wèn)題在多項(xiàng)式時(shí)間內(nèi)可以歸約到B。

常見(jiàn)的屬于EXPTIME-complete問(wèn)題的有停機(jī)問(wèn)題［8］、簡(jiǎn)潔電路問(wèn)題［11］、G3游戲等。

該游戲中的每個(gè)局面(position)是一個(gè)4元組(τ，R-LOSE(X，Y)，B-LOSE(X，Y)，α)，其中τ∈{R，B}，它表示當(dāng)前走棋方，R-LOSE=C11∨C12∨C13∨…∨C1p和B-LOSE=C21∨C22∨C23∨…∨C2q是屬于12DNF的布爾公式，其中每個(gè)C1i(1≤i≤p)和C2j(1≤j≤q)是最多12個(gè)文字之間的與運(yùn)算，每個(gè)文字是集合X(Y)中的一個(gè)變量。例如:z 或ˉz(變量z的非運(yùn)算);α是對(duì)X∪Y的一個(gè)賦值，如X={x1，x2，x3}，Y={y1，y2，y3}，則X∪Y= {x1，x2，x3，y1，y2，y3}。對(duì)X∪Y賦值，就是對(duì)該集合中的各個(gè)元素賦值為0或1。比賽雙方交替進(jìn)行，R方或B方通過(guò)改變集合X和Y中的一個(gè)變量的值進(jìn)行走棋。更精確地，R方能夠從局面(R，R-LOSE(X，Y)，B-LOSE(X，Y)，α)下棋到局面(B，R-LOSE(X，Y)，B-LOSE(X，Y)，α')，當(dāng)且僅當(dāng)α與α'不同，并且在α的賦值下，R-LOSE(X，Y)的布爾值為false。如果在R(B)走了若干步后，公式R-LOSE(B-LOSE)值為true，那么R(B)失敗。在文獻(xiàn)［3］中，該游戲被證明屬于EXPTIME-complete問(wèn)題。此游戲的規(guī)則與許多棋類游戲有類似之處。比如，在游戲中有2個(gè)參與方，通過(guò)判斷布爾公式R-LOSE(B-LOSE)的值是否為真來(lái)判斷某方是否輸棋(也就是說(shuō)，這2個(gè)布爾公式可以看作是棋類游戲中的估值函數(shù))。4元組中的α就是雙方兵力的集合，從α對(duì)應(yīng)的4元組到α'對(duì)應(yīng)的4元組可以看作是棋類游戲中的一個(gè)走法。因此，選用G3游戲來(lái)構(gòu)造機(jī)器博弈問(wèn)題的歸約模型是非常合適的。

2 對(duì)于中國(guó)象棋計(jì)算復(fù)雜性的證明

本文的主要工作是證明對(duì)于任意的一個(gè)n×n的中國(guó)象棋局面，判定黑方(紅方)是否能夠獲勝的問(wèn)題屬于EXPTIME-complete。根據(jù)計(jì)算復(fù)雜性類complete問(wèn)題的定義［1］，證明廣義化的中國(guó)象棋屬于EXPTIME-complete的步驟如下:

1)證明廣義化的中國(guó)象棋屬于EXPTIME;

2)構(gòu)造一個(gè)歸約模型，使得G3游戲可歸約到中國(guó)象棋;

3)證明此歸約可在多項(xiàng)式時(shí)間內(nèi)完成。

2.1 中國(guó)象棋的廣義化

對(duì)于固定棋盤(pán)規(guī)模的博弈問(wèn)題(如9×10的中國(guó)象棋或8×8的國(guó)際象棋)，可能出現(xiàn)的局面數(shù)是有窮的，即產(chǎn)生的局面數(shù)是一個(gè)常量。而研究問(wèn)題的計(jì)算復(fù)雜性時(shí)采用的是漸近法，用此方法來(lái)度量復(fù)雜性隨著問(wèn)題規(guī)模的增加而變化的增長(zhǎng)率。因此，需要將問(wèn)題的規(guī)模廣義化，即規(guī)模是任意大的［8］。對(duì)于中國(guó)象棋的廣義化，要保證各個(gè)棋子的走法不變，雙方的帥(將)只能有1個(gè)，不能廣義化為多個(gè)，帥(將)和士不能出“九宮”(由于棋盤(pán)被廣義化，所以原來(lái)九宮的規(guī)模也被擴(kuò)大了)。

2.2 n×n的中國(guó)象棋屬于EXPTIME問(wèn)題

該證明比較簡(jiǎn)單，可以進(jìn)行粗略計(jì)算。假設(shè)計(jì)算機(jī)處理象棋的一個(gè)局面需要一個(gè)單位時(shí)間，則n×n的中國(guó)象棋可能產(chǎn)生的局面總和就是其被求解所需總時(shí)間的上限值。中國(guó)象棋的雙方兵種之和為14，則n×n個(gè)交叉點(diǎn)的中國(guó)象棋所能產(chǎn)生的局面總數(shù)上限為15n×n。由此得證，n×n的中國(guó)象棋屬于EXPTIME問(wèn)題。

3 歸約模型的構(gòu)建

本文給出一個(gè)n×n的中國(guó)象棋局面(實(shí)例)，并在此局面上模擬進(jìn)行任意一個(gè)G3游戲。所構(gòu)建的歸約模型(即局面)遵循的主要思想是:在該模型上能夠模擬進(jìn)行G3游戲，并對(duì)G3游戲所包含的變量適當(dāng)?shù)刭x值，確保它們所在的子句為true，進(jìn)而使得G3游戲在n×n中國(guó)象棋棋盤(pán)上能夠被求解;雙方都采用車作為進(jìn)攻的棋子，在走棋過(guò)程中，將出現(xiàn)吃子和兌子的情況，最終通過(guò)計(jì)算吃掉對(duì)方的帥(將)所需的總的步數(shù)判定哪一方需要的步數(shù)更少，那么該走棋方先于對(duì)方獲勝。也就是說(shuō)，在這個(gè)構(gòu)建的局面上，G3游戲中的某個(gè)走棋方存在一種贏棋策略，當(dāng)且僅當(dāng)中國(guó)象棋的某個(gè)走棋方在此給定的局面中存在一種贏棋策略。

3.1 歸約模型中各構(gòu)件的說(shuō)明

為了在n×n中國(guó)象棋的歸約模型上模擬G3游戲，構(gòu)建此模型的過(guò)程中，既要考慮G3游戲的特點(diǎn)，也不能違反中國(guó)象棋的走棋規(guī)則。本文所構(gòu)建的歸約模型主要包括布爾控制器、開(kāi)關(guān)、子句通道、兌子區(qū)域、延遲區(qū)域和九宮，這6個(gè)構(gòu)件組成了一個(gè)n×n中國(guó)象棋的特定局面。

3.1.1 布爾控制器

一個(gè)布爾控制器(boolean controller，BC)的作用是實(shí)現(xiàn)對(duì)G3游戲的4元組中的一個(gè)布爾變量賦值(true或false)。圖1顯示了紅方布爾控制器(red boolean controller，RBC)的基本結(jié)構(gòu)，其中包含的棋子有紅兵、紅相、紅車、紅馬、紅炮、黑車;包含文字(與G3游戲的子句所包含的文字對(duì)應(yīng))通道即x通道和～x通道，以及一個(gè)紅方的時(shí)鐘通道(red clock channel)。只要將該圖旋轉(zhuǎn)180°，并將各個(gè)位置上的棋子由紅兵換成黑卒、紅相換成黑相、紅車換成黑車、紅馬換成黑馬、紅炮換成黑炮、黑車換成紅車等，就能得到Black Boolean controller(BBC)的結(jié)構(gòu)。在一個(gè)布爾控制器中，只有1個(gè)紅相和2個(gè)車(一個(gè)紅方、一個(gè)黑方)可以主動(dòng)走棋，其他棋子處于僵局狀態(tài)，不能主動(dòng)走棋，但根據(jù)各個(gè)棋子的走法規(guī)則，它們可以被動(dòng)地吃子。由這些棋子構(gòu)成的區(qū)域迫使雙方的車經(jīng)由給定的通道離開(kāi)布爾控制器，在Red Boolean controller中，若黑方的車吃掉了紅方的棋子，則它將立即被鄰近的紅方棋子吃掉，從而使紅方可以經(jīng)由正常的通道離開(kāi)布爾控制器，并最終獲勝;若有一方的車不經(jīng)由正常通道離開(kāi)布爾控制器(例如，黑方的車第一步?jīng)]有直接走到x通道或～x通道的橫向虛線處，而是只走了一格)，那么對(duì)方的車同樣可經(jīng)由正常的通道離開(kāi)布爾控制器，并最終可能先于對(duì)方獲勝。這種不恰當(dāng)?shù)淖叻▽⒃诤竺嬲鹿?jié)詳細(xì)論述。

開(kāi)始時(shí)，紅方的相必須先走出一步，它只有2個(gè)走法(即圖中的2個(gè)虛線位置)，這2個(gè)走法決定了黑方的車是從x通道還是～x通道離開(kāi)布爾控制器。若紅相移動(dòng)到南方(即下方)的虛線位置，則黑車可從x通道離開(kāi)，說(shuō)明該布爾控制器對(duì)變量x賦值為true;相反，若紅相移動(dòng)到北方(即上方)的虛線位置，則黑車從～x通道離開(kāi)，說(shuō)明該布爾控制器對(duì)變量x賦值為false。如前所述，紅相走一步，然后黑車走一步到達(dá)x通道或～x通道的橫向虛線處;接下來(lái)輪到紅方的車走棋，它可以從東北角的x通道或～x通道離開(kāi)，也可以從北方的Red clock channel(時(shí)鐘通道)離開(kāi)此布爾控制器。

圖1 紅方的布爾控制器

3.1.2 開(kāi)關(guān)(switch)

開(kāi)關(guān)的作用是確保只有一個(gè)對(duì)方的車能到達(dá)子句通道，并確保對(duì)方的車無(wú)法從子句通道再進(jìn)入BC。圖2顯示了開(kāi)關(guān)的基本結(jié)構(gòu)。同樣，由紅馬、紅兵、紅相和紅炮組成的區(qū)域是一個(gè)僵局，它們不能主動(dòng)移動(dòng)，但根據(jù)各個(gè)棋子的走法規(guī)則，它們可以吃對(duì)方的棋子。

當(dāng)有黑方的車從RBC到達(dá)開(kāi)關(guān)時(shí)，黑車將按照紅方棋子形成的通道走棋，途中將吃掉攔在通道上的一個(gè)紅馬，然后安全地離開(kāi)開(kāi)關(guān)，到達(dá)子句通道。如果黑方的車在吃掉紅馬后，打算反向走棋并返回布爾控制器，此時(shí)被吃掉的紅馬的東南方的紅相將走棋到西北角處，這樣紅相原來(lái)位置左側(cè)的若干個(gè)紅方的炮(此處炮的數(shù)量大于或等于G3游戲所包含的變量的總數(shù))將封鎖住紅相右側(cè)的通道，使得黑方的車無(wú)法返回布爾控制器。同樣，子句通道中的黑車也無(wú)法經(jīng)由開(kāi)關(guān)返回布爾控制器。

圖2 紅方的開(kāi)關(guān)

3.1.3 子句通道(C1i-channels)

子句通道對(duì)應(yīng)G3游戲中布爾公式R-LOSE (B-LOSE)所包含的子句C1i或C2j。根據(jù)G3游戲的定義，每個(gè)子句包含若干個(gè)文字，這些文字的“與”運(yùn)算的值就是該子句的運(yùn)算結(jié)果。圖3顯示了各個(gè)子句通道與各個(gè)文字通道形成的交叉結(jié)構(gòu)。

如上所述，黑方的車從RBC經(jīng)由開(kāi)關(guān)到達(dá)子句通道，只有子句包含的文字的值為真(如x)時(shí)，黑車才可以停在對(duì)應(yīng)的值為真的文字通道(x通道)與該子句通道的交叉點(diǎn)處，并經(jīng)由此子句通道到達(dá)兌子區(qū)域(exchanging chess zone);否則黑車無(wú)法停在文字通道與子句通道的交叉點(diǎn)處，如圖3所示。假設(shè)子句C11不包含ˉx，如果黑車經(jīng)由ˉx通道停在此文字通道與C11通道的交叉點(diǎn)處，此時(shí)黑車將被西南方的紅馬吃掉，從而無(wú)法安全到達(dá)兌子區(qū)域(exchanging chess zone)，最終紅方將獲勝。此處的一些不恰當(dāng)走法將在后面章節(jié)詳細(xì)論述。

假設(shè)某個(gè)子句包含的變量總數(shù)為p，如該子句通道與文字通道的交叉點(diǎn)處安全地停有p個(gè)黑方的車，則這p個(gè)黑車向東移動(dòng)至兌子區(qū)域。

圖3 子句通道與文字通道的交叉結(jié)構(gòu)

3.1.4 兌子區(qū)域

如果某個(gè)子句通道上停有與該子句所包含的文字?jǐn)?shù)相同的黑方的車，則這些車經(jīng)由該子句通道到達(dá)兌子區(qū)域。如圖4所示，在兌子區(qū)域的通道上有一個(gè)紅方的馬，該棋子受到正上方若干個(gè)紅炮的保護(hù)，因此雙方開(kāi)始兌子，直到最后一個(gè)紅方的炮被黑車吃掉。其中紅炮的個(gè)數(shù)為p-x，p為該子句所包含的文字?jǐn)?shù)，x為奇數(shù)且1≤x＜p。剩下的黑方的車安全地到達(dá)九宮(nine-palace)。

圖4 兌子區(qū)域

3.1.5 九宮和延遲區(qū)域

九宮和延遲區(qū)域(delay zone)是歸約模型中的最后2個(gè)構(gòu)件。在中國(guó)象棋中，九宮是帥(將)和士活動(dòng)的區(qū)域，也是最后一道防線。對(duì)于n×n的中國(guó)象棋，該區(qū)域的帥(將)仍然只有一個(gè)，士的數(shù)量為多個(gè)，士只能在九宮中活動(dòng)，它的走法為斜走斜吃，且每次只能走一格。圖5顯示了九宮的基本結(jié)構(gòu)(圖中未顯示帥的位置)，若干個(gè)黑方的車到達(dá)九宮，將與九宮中的士進(jìn)行兌子，并最終吃掉紅方的帥。此處子句通道連接的九宮共有2× (x-1)個(gè)士。

延遲區(qū)域與Clock channel相連接，如圖6所示，是一列馬，馬的數(shù)量為12k-5。其中，k為G3游戲?qū)?yīng)的4元組中子句包含的最大文字?jǐn)?shù)，即1≤k≤12。車吃掉若干個(gè)馬之后，可直接吃掉對(duì)方的帥(將)。

圖5 九宮

圖6 延遲區(qū)域

每個(gè)構(gòu)件中，由若干個(gè)棋子構(gòu)成的區(qū)域，迫使黑方的車沿著這些區(qū)域形成的通道向另一個(gè)構(gòu)件前進(jìn)。為了防止若干個(gè)黑方的車未按照設(shè)計(jì)好的通道走棋，而是去吃掉區(qū)域中的棋子并沖破這些區(qū)域，這些區(qū)域要足夠厚。它的厚度是子句中所包含的最大文字?jǐn)?shù)的13倍，即13k。由3.2節(jié)可知，黑方達(dá)到這個(gè)步數(shù)時(shí)，紅方可先于黑方獲勝。

3.2 贏棋策略

圖7顯示了歸約模型的整體結(jié)構(gòu)，它構(gòu)成了n×n的中國(guó)象棋的一個(gè)局面。在此局面上模擬G3游戲，若有p(p為某個(gè)子句包含的文字的個(gè)數(shù)，文字形如x或～x)個(gè)黑車安全地停留在該子句通道上，說(shuō)明G3游戲已被求解;對(duì)于n×n的中國(guó)象棋，紅黑雙方通過(guò)吃掉對(duì)方的帥(將)所需步數(shù)的多少來(lái)判定是否先于對(duì)方獲勝。如前所述，第一步由布爾控制器中的紅相走棋，它只有2種走法，紅相的走棋決定了黑方的車從x或～x通道離開(kāi)布爾控制器。然后由布爾控制器中的黑車走棋，接下來(lái)輪到布爾控制器中的紅車走棋，它從東北角的x(～x)通道或者經(jīng)由Red Clock channel離開(kāi)布爾控制器，接下來(lái)黑方的車經(jīng)由開(kāi)關(guān)區(qū)域到達(dá)子句通道。如果某個(gè)子句通道上有p個(gè)黑方的車安全地停留在該通道上，說(shuō)明該子句的布爾值為真，即布爾公式R-LOSE為真，此時(shí)G3游戲已被求解。接下來(lái)須計(jì)算n×n的中國(guó)象棋是否被最終求解。

圖7 一個(gè)歸約模型的整體結(jié)構(gòu)，其中R-LOSE= C11∨C12，C11=x1∧～x2∧～y，C12=～x1∧x2;B-LOSE=C21∨C22，C21=x1∧y，C22=～y

3.2.1 黑方的贏棋策略

假設(shè)黑方的車從x或～x通道正常離開(kāi)布爾控制器，同一個(gè)布爾控制器中的紅車從Red Clock channel離開(kāi)。黑車離開(kāi)布爾控制器需要3步(如圖1所示)，經(jīng)由開(kāi)關(guān)到達(dá)子句通道需要6步(到達(dá)開(kāi)關(guān)的那一步與離開(kāi)布爾控制器的最后一步是同一步)，所以一個(gè)黑車到達(dá)子句通道共用掉m= 9步。當(dāng)某個(gè)子句通道C1i上已有p(p為該子句包含的文字的個(gè)數(shù)，1≤p≤k≤12，文字形如x或～x)個(gè)黑車，則這p個(gè)黑方的車將陸續(xù)到達(dá)兌子區(qū)域，并開(kāi)始與紅方兌子。兌子過(guò)程所需步數(shù)計(jì)算如下:p個(gè)黑車要吃掉1個(gè)攔在通道上的紅馬和p -x個(gè)紅炮，所以在兌子區(qū)域共用掉黑方p-x+1步。而剩下的x個(gè)黑車需要多走1步(經(jīng)過(guò)一個(gè)拐點(diǎn))順利到達(dá)九宮，九宮中共有2×(x-1)個(gè)士，每2個(gè)士能兌掉1個(gè)黑方的車，所以這里需要與士進(jìn)行兌子，吃掉2×(x-1)個(gè)士。而每吃掉2個(gè)士，還需再走一步吃掉另外的1個(gè)士，因此在九宮共用掉黑方2×(x-1)+2×(x-1)÷2-1= 3x-4步，最后剩下的1個(gè)黑車需要兩步吃掉對(duì)方的帥。綜上所述，黑方下完這盤(pán)棋共需要:m× p+p-x+1+x+3x-4+2=(m+1)×p+3x-1步，又m=9，所以總的步數(shù)為10p+3x-1。

下面計(jì)算紅方。在布爾控制器中，紅方的車經(jīng)由Red Clock channel離開(kāi)布爾控制器需要3步，同時(shí)紅相用掉1步。在兌子區(qū)域，紅方用p-x步吃掉對(duì)方p-x個(gè)車。在九宮中紅方的士吃掉對(duì)方x-1個(gè)車，所以在九宮兌子的過(guò)程中，紅方用了x-1步。紅方的車到達(dá)延遲區(qū)域，這里有12k-5個(gè)對(duì)方的馬，紅車吃掉這些馬之后，又用了2步吃掉對(duì)方的將。因此，紅方所需總的步數(shù)為:3 +1+p-x+x-1+12k-5+2=12k+p。因?yàn)? ≤p≤k≤12且1≤x≤p-1，所以紅方獲勝所需步數(shù)比黑方多1步。綜上所述，黑方必勝。

3．2．2 紅方的贏棋策略

黑方需要將p個(gè)車落在某個(gè)子句通道上，每個(gè)車到達(dá)子句通道需要m步，但有可能該子句通道對(duì)應(yīng)的子句C1i=0。例如:子句C11=x1∧x2∧y1，BBC中的黑象的走棋決定了變量y1的賦值，如果黑象的走棋使得在同一布爾控制器中的黑車從～y1離開(kāi)此布爾控制器，則說(shuō)明變量y1被賦值為false，則子句C11=0。因此，若子句C1i=0，則之前若干個(gè)停在該子句通道上的黑車(設(shè)為y個(gè))至少需要1步才能移動(dòng)到一個(gè)能使子句的值為真的通道上。若該子句通道所包含的文字?jǐn)?shù)為k(包含的最大文字?jǐn)?shù))，且該子句連接的兌子區(qū)域中的紅炮的數(shù)量為1(即x的值為k-1)，則黑方吃掉帥所需總的步數(shù)為10k+3(k-1)-1+y=13k-4+ y;紅方獲勝所需步數(shù)為12k+k=13k。因此，當(dāng)y＞4時(shí)，紅方先于黑方獲勝。

4 不恰當(dāng)走法分析

4.1 紅方布爾控制器(RBC)中可能存在的不恰當(dāng)走法(BBC與RBC中可能出現(xiàn)的不恰當(dāng)走法類似)

1)RBC中的黑車第1步到達(dá)北面的x通道，若它下一步往東走，進(jìn)入Red Clock channel，在它吃掉1個(gè)紅方的馬后，將被上方的紅炮吃掉。南面的～x通道同理。

2)RBC中的黑車通過(guò)任何途徑都無(wú)法吃掉紅方的相;

3)RBC中只有雙方的2個(gè)車和紅方的相可以主動(dòng)走棋，其他棋子只能被動(dòng)吃子。例如:RBC中通道拐角處的紅馬若走到黑車的通道上，將被黑車吃掉，而黑車不會(huì)受到威脅。

4.2 子句通道與文字通道的交叉點(diǎn)處可能存在的不恰當(dāng)走法

黑方的車離開(kāi)開(kāi)關(guān)到達(dá)子句通道，只有其所在的通道對(duì)應(yīng)的文字在子句中為真時(shí)，黑車才能安全地停在文字通道與子句通道的交叉點(diǎn)處，否則將被交叉點(diǎn)西南方的紅馬吃掉。假設(shè)該紅馬吃掉黑車后，被同一子句通道上的其他黑車吃掉，則紅馬原來(lái)位置左側(cè)的紅炮將向東移動(dòng)到文字通道上。該紅炮由若干個(gè)西側(cè)的紅炮保護(hù)，防止交叉點(diǎn)上的黑車向另一個(gè)子句通道上移動(dòng)。若此黑車打算吃掉該紅炮，將被紅炮西側(cè)的另一個(gè)紅方的炮吃掉;若此黑車打算由此交叉點(diǎn)所在的文字通道反向沖入布爾控制器，則將被開(kāi)關(guān)中紅方的炮吃掉。

5 結(jié)論

根據(jù)各章節(jié)的論述及EXPTIME-complete問(wèn)題的定義，證明n×n的中國(guó)象棋屬于EXPTIME-complete問(wèn)題:

1)根據(jù)2.2節(jié)的論述，可知n×n的中國(guó)象棋屬于EXPTIME問(wèn)題。

2)根據(jù)第3節(jié)的論述，可知在模擬的過(guò)程中，采用的是任意的一個(gè)G3游戲?qū)嵗瑥亩f(shuō)明一個(gè)給定的n×n的中國(guó)象棋局面(構(gòu)建的歸約模型所形成的局面)可以求解任意的一個(gè)G3游戲的實(shí)例。也就是說(shuō)，存在這樣的一個(gè)歸約，可以將任意的一個(gè)G3游戲問(wèn)題轉(zhuǎn)換成n×n的中國(guó)象棋問(wèn)題。根據(jù)可歸約性的定義［8］:

問(wèn)題A是可歸約到問(wèn)題B的，如果存在可計(jì)算函數(shù)f:使得對(duì)每個(gè)w，w∈A，f(w)∈B，稱函數(shù)f 為A到B的歸約。

由此可說(shuō)明，G3游戲可歸約到n×n的中國(guó)象棋。再者，G3游戲已被證明屬于EXPTIME-complete問(wèn)題［3］，根據(jù)EXPTIME-complete問(wèn)題的定義可知，所有屬于EXPTIME的問(wèn)題都可歸約到G3游戲。根據(jù)歸約可傳遞的特性［8］可知:所有屬于EXPTIME的問(wèn)題都可歸約到n×n的中國(guó)象棋。

接下來(lái)需要估算第3節(jié)中構(gòu)建歸約模型所需要的時(shí)間。設(shè)m為4元組包含的變量總數(shù)，對(duì)于每個(gè)變量，在歸約模型中，需要用到1個(gè)布爾控制器、4個(gè)文字通道、4個(gè)開(kāi)關(guān)區(qū)域、1個(gè)Clock channel以及最多4個(gè)與文字通道交叉的子句通道(可能某個(gè)文字不存在于任何子句中，所以該文字通道不與任何子句通道交叉，如圖6所示)。各個(gè)組成部分都存在固定數(shù)量的處于僵局的各個(gè)棋子構(gòu)成的區(qū)域。前面已提到這種區(qū)域的厚度為13k，固定數(shù)量的區(qū)域形成的總厚度為O(k)，又因?yàn)楣灿衜個(gè)變量，所以此歸約模型的總規(guī)模可以記為O(m×k)。因此，此歸約模型可在多項(xiàng)式時(shí)間內(nèi)構(gòu)建完成。結(jié)合前面的論述得證:所有屬于EXPTIME的問(wèn)題都可在多項(xiàng)式時(shí)間內(nèi)歸約到n×n的中國(guó)象棋。

由以上兩點(diǎn)得證:n×n的中國(guó)象棋屬于EXPTIME-complete問(wèn)題。

［1］AVIEZW S.FRAENKEL.Computing a perfect strategy for n×n chess requires time exponential in n［J］.JOURNAL OF COMBINATORIAL THEORY，Series A 31，1981:199-214.

［2］Robson J M.N by N Checkers is EXPTIME complete ［J］.SIAM Journal on Computing，1984，13(2):252 -267.

［3］STOCKMEYER L J，CHANDRA A K.Provably difficult combinatorial games［J］.SIAM J.Compuf，1979(8):151 -174.

［4］Lichtenstein D，Sipser M.Go is polynomial-space hard ［J］.Journal of the ACM，1980(27):393-401.

［5］Reisch S.Gobang ist PSPACE-vollst?ndig(Gobang is PSPACE-complete)［J］.Acta Informatica，1980(13):59 -66.

［6］Ming Yu Hsieh，Shi-Chun Tsai.On the fairness and complexity of generalized k-in-a-row games［J］.Theoretical Computer Science，2007(385):88-100.

［7］Iwata S，Kasai T.The Othello game on an n×n board is PSPACE-complete［J］.Theoretical Computer Science，1994(123):329-340.

［8］Michael Sipser.Introduction to the Theory of Computation (Second Edition)［M］.China Machine Press，2006.

［9］Robert A.Hearn，Amazons is PSPACE-comp-lete［EB/ OL］.arXiv:cs.CC/0502013v1，2005.

［10］Yen Shi-Jim，Chen Jr-Chang，Yang Tai-Ning.COMPUTER CHINESE CHESS［Z］.ICCA，2004.

［11］Christos Papadimitriou.Computational Complexit-y［M］. ［S.l.］:Addison-Wesley，2001.

(責(zé)任編輯 楊黎麗)

Chinese Chess Being EXPTIME-complete

GAO Qiang，XU Xin-he
(College of Information Science and Engineering，Northeastern University，Shenyang 110004，China)

The main objective of research on computer game is looking for an ideal invincible solution of the board games.However，computational complexity is an insurmountable obstacle in the process of solving.Firstly，this article introduces EXPTIME-complete problem of computational complexity and an example of it，G3game.An n×n Chinese Chess position is constructed，and this position consists of six components which include Boolean controller，switch，the crossing of clause-channel and literal-channel，exchanging chess zone，delay zone and Nine-palace.G3game is simulated on the position，and hence it is proved that G3is reducible to n×n Chinese Chess in polynomial time，and then Chinese Chess is EXPTIME-complete.

computer games;Chinese chess;computational complexity;EXPTIME-complete;reducibility

TP301.5

A

1674-8425(2014)08-0085-07

10.3969/j.issn.1674-8425(z).2014.08.018

2014-03-26

國(guó)家自然科學(xué)基金資助項(xiàng)目(61370153)

高強(qiáng)(1980—)，男，遼寧沈陽(yáng)人，博士研究生，主要從事機(jī)器博弈、計(jì)算復(fù)雜性理論研究;徐心和(1940—)，男，黑龍江哈爾濱人，教授，博士生導(dǎo)師，主要從事控制理論與應(yīng)用、系統(tǒng)仿真、智能機(jī)器人、機(jī)器博弈等方面研究。

高強(qiáng)，徐心和.中國(guó)象棋屬于EXPTIME-complete問(wèn)題［J］.重慶理工大學(xué)學(xué)報(bào):自然科學(xué)版，2014(8):85 -91.

format:GAO Qiang，XU Xin-he.Chinese Chess Being EXPTIME-complete［J］.Journal of Chongqing University of Technology:Natural Science，2014(8):85-91.