中國象棋屬于EXPTIME-complete問題

高強，徐心和

(東北大學信息科學與工程學院，沈陽 110004)

中國象棋屬于EXPTIME-complete問題

高強，徐心和

(東北大學信息科學與工程學院，沈陽 110004)

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

計算機博弈;中國象棋;計算復雜性;指數時間的完全問題;歸約

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

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

表1 中國象棋與國際象棋的復雜度比較(數據以10為底)

由表1可見:中國象棋的復雜度與國際象棋的復雜度相當，既然n×n的國際象棋已被證明屬于EXPTIME-complete問題，所以有理由推測n×n的中國象棋也應屬于EXPTIME-complete問題。

本文在第1節分析了EXPTIME-complete問題及它的一個典型實例——G3游戲。根據計算復雜性類中完全問題的定義［1］，首先在第2節證明了n×n的中國象棋屬于EXPTIME問題，然后在第3節重點構建了一個n×n中國象棋的歸約模型，并在此模型上模擬進行G3游戲，證明了G3游戲可在多項式時間內歸約到n×n中國象棋，從而證明了n×n中國象棋屬于EXPTIME-complete問題。為了保證論述的嚴密性，第4節給出了歸約模型中不恰當走法的分析。第5節對于此證明的完全性給出了論證。

1 EXPTIME-complete問題

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

一個問題B屬于EXPTIME-complete，如果它滿足2個條件:

1)B屬于EXPTIME;

2)每個屬于EXPTIME的問題在多項式時間內可以歸約到B。

常見的屬于EXPTIME-complete問題的有停機問題［8］、簡潔電路問題［11］、G3游戲等。

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

2 對于中國象棋計算復雜性的證明

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

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

2)構造一個歸約模型，使得G3游戲可歸約到中國象棋;

3)證明此歸約可在多項式時間內完成。

2.1 中國象棋的廣義化

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

2.2 n×n的中國象棋屬于EXPTIME問題

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

3 歸約模型的構建

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

3.1 歸約模型中各構件的說明

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

3.1.1 布爾控制器

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

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

圖1 紅方的布爾控制器

3.1.2 開關(switch)

開關的作用是確保只有一個對方的車能到達子句通道，并確保對方的車無法從子句通道再進入BC。圖2顯示了開關的基本結構。同樣，由紅馬、紅兵、紅相和紅炮組成的區域是一個僵局，它們不能主動移動，但根據各個棋子的走法規則，它們可以吃對方的棋子。

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

圖2 紅方的開關

3.1.3 子句通道(C1i-channels)

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

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

假設某個子句包含的變量總數為p，如該子句通道與文字通道的交叉點處安全地停有p個黑方的車，則這p個黑車向東移動至兌子區域。

圖3 子句通道與文字通道的交叉結構

3.1.4 兌子區域

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

圖4 兌子區域

3.1.5 九宮和延遲區域

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

延遲區域與Clock channel相連接，如圖6所示，是一列馬，馬的數量為12k-5。其中，k為G3游戲對應的4元組中子句包含的最大文字數，即1≤k≤12。車吃掉若干個馬之后，可直接吃掉對方的帥(將)。

圖5 九宮

圖6 延遲區域

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

3.2 贏棋策略

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

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

3.2.1 黑方的贏棋策略

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

下面計算紅方。在布爾控制器中，紅方的車經由Red Clock channel離開布爾控制器需要3步，同時紅相用掉1步。在兌子區域，紅方用p-x步吃掉對方p-x個車。在九宮中紅方的士吃掉對方x-1個車，所以在九宮兌子的過程中，紅方用了x-1步。紅方的車到達延遲區域，這里有12k-5個對方的馬，紅車吃掉這些馬之后，又用了2步吃掉對方的將。因此，紅方所需總的步數為:3 +1+p-x+x-1+12k-5+2=12k+p。因為1 ≤p≤k≤12且1≤x≤p-1，所以紅方獲勝所需步數比黑方多1步。綜上所述，黑方必勝。

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

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

4 不恰當走法分析

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

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

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

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

4.2 子句通道與文字通道的交叉點處可能存在的不恰當走法

黑方的車離開開關到達子句通道，只有其所在的通道對應的文字在子句中為真時，黑車才能安全地停在文字通道與子句通道的交叉點處，否則將被交叉點西南方的紅馬吃掉。假設該紅馬吃掉黑車后，被同一子句通道上的其他黑車吃掉，則紅馬原來位置左側的紅炮將向東移動到文字通道上。該紅炮由若干個西側的紅炮保護，防止交叉點上的黑車向另一個子句通道上移動。若此黑車打算吃掉該紅炮，將被紅炮西側的另一個紅方的炮吃掉;若此黑車打算由此交叉點所在的文字通道反向沖入布爾控制器，則將被開關中紅方的炮吃掉。

5 結論

根據各章節的論述及EXPTIME-complete問題的定義，證明n×n的中國象棋屬于EXPTIME-complete問題:

1)根據2.2節的論述，可知n×n的中國象棋屬于EXPTIME問題。

2)根據第3節的論述，可知在模擬的過程中，采用的是任意的一個G3游戲實例，從而說明一個給定的n×n的中國象棋局面(構建的歸約模型所形成的局面)可以求解任意的一個G3游戲的實例。也就是說，存在這樣的一個歸約，可以將任意的一個G3游戲問題轉換成n×n的中國象棋問題。根據可歸約性的定義［8］:

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

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

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

由以上兩點得證:n×n的中國象棋屬于EXPTIME-complete問題。

［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.

(責任編輯 楊黎麗)

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

國家自然科學基金資助項目(61370153)

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

高強，徐心和.中國象棋屬于EXPTIME-complete問題［J］.重慶理工大學學報:自然科學版，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.