中國象棋狀態總數

中國象棋有多少種狀態？

此問題並未有統一的答案。

定義問題

首先，定義一個子問題：給定若干棋子之後，在棋盤上有多少种放置方法？

最終的答案可以用偽代碼來進行描述。

枚舉每種棋子的個數，然後將它們放置在棋盤上，統計總數即為答案。

上面這種偽代碼方式只適合描述問題，用這種思路直接求解卻不如下面這種方式。

求解方法

先擺放限制比較多的棋子

1. 將
2. 士
3. 相
4. 卒
5. 車馬炮

三對互相影響

1.將影響士

2.將影響相

3.相影響卒

程序大體框架

def 將(): s = 0 for 紅將 in range(9): for 黑將 in range(9): s += 士(紅將, 黑將) return sdef 士(紅將, 黑將): s = 0 for 紅士 in 紅士可去的全部位置: for 黑士 in 黑士可去的全部位置: s += 相(紅將, 黑將, 紅方空白格點數, 黑方空白格點數) return sdef 相(紅將, 黑將, 紅方空白格點數, 黑方空白格點數): s = 0 for 紅相 in 紅相可去的全部位置: for 黑相 in 黑相可去的全部位置: s += 卒(紅相佔據卒位的個數, 黑相佔據卒位的個數, 紅方空白格點數, 黑方空白格點數) return sdef 卒(紅相佔據卒位的個數, 黑相佔據卒位的個數, 紅方空白格點數, 黑方空白格點數): s = 0 for 紅卒 in 紅卒可去的全部位置: for 黑卒 in 黑卒可去的全部位置: s += 車馬炮(紅方空白格點數, 黑方空白格點數) return sdef 車馬炮(紅方空白格點數, 黑方空白格點數): s = 0 for 紅車 in range(3): for 黑車 in range(3): for 紅炮 in range(3): for 黑炮 in range(3): for 紅馬 in range(3): for 黑馬 in range(3): s += 一道簡單的排列組合問題(紅方空白格點數, 黑方空白格點數, 紅車, 黑車, 紅炮, 黑炮, 紅馬, 黑馬) return s

流程圖

具體實現

"""按照「將，士，相，卒，車馬炮」的順序進行布子，求中國象棋的總狀態數"""import mathc_table = {} # 組合數def c(x, y): # 從x個數裡面挑選y個 k = (x, y) if not k in c_table: s = 1 for i in range(1, y + 1): s = s * (x + 1 - i) / i c_table[k] = s return c_table[k]"""0 1 23 4 56 7 8將的九個位置0，2，4，6，8表示將在士位上1表示將在相位上"""def get_jiang(): s = 0 for r_jiang in range(9): for b_jiang in range(9): s += get_shi(r_jiang, b_jiang) return sshi = {}def get_shi(r_jiang, b_jiang): k = (r_jiang, b_jiang) if not k in shi: s = 0 for r_shi in range(3): for b_shi in range(3): ss = 1 if r_jiang in [0, 2, 4, 6, 8]: # 將在士位上 ss *= c(4, r_shi) else: # 將不在士位 ss *= c(5, r_shi) if b_jiang in [0, 2, 4, 6, 8]: ss *= c(4, b_shi) else: ss *= c(5, b_shi) ss *= get_xiang(r_jiang, b_jiang, r_space=45 - 1 - r_shi, b_space=45 - 1 - b_shi) s += ss shi[k] = s return shi[k]xiang = {}"""相的位置只跟未過河卒和老將有關係相位++0+++1+++++++++++2+++3+++4+++++++++++5+++6++來一個第7位置，表示相死了"""def get_xiang(r_jiang, b_jiang, r_space, b_space): k = (r_jiang, b_jiang, r_space, b_space) if not k in xiang: s = 0 for r_xiang1 in range(8): # 對於相的8種位置，其中第7個位置表示相死了 for r_xiang2 in range(r_xiang1, 8): # 考慮兩個相是等價的，所以r_xaing2的位置始終大於r_xiang1的位置，除非r_xiang1死了 for b_xiang1 in range(8): for b_xiang2 in range(b_xiang1, 8): if r_xiang1 == r_xiang2 and r_xiang1 != 7: continue if b_xiang1 == b_xiang2 and b_xiang1 != 7: continue if (r_xiang1 == 3 or r_xiang2 == 3) and r_jiang == 1: continue if (b_xiang1 == 3 or b_xiang2 == 3) and b_jiang == 1: continue r_xiang_count = (r_xiang1 != 7) + (r_xiang2 != 7) b_xiang_count = (b_xiang1 != 7) + (b_xiang2 != 7) # 佔用卒位的個數 r_xiang_zu = (r_xiang1 < 2) + (r_xiang2 < 2) b_xiang_zu = (b_xiang1 < 2) + (b_xiang2 < 2) ss = 1 ss *= get_zu(r_xiang_zu, b_xiang_zu, r_space - r_xiang_count, b_space - b_xiang_count) s += ss xiang[k] = s return xiang[k]zu = {}# 5列卒子位置，每列有兩個卒位，被相佔了used列，需要布下zu個卒子def place_zu(used, zu): s = 0 for i in range(min(used, zu) + 1): # 有i個放在了used的列上，他們就不自由了，必然只有一种放法 # 有zu-i個比較自由，每個卒自由度為2，從5-used列中選擇zu-i列進行擺放 s += 2 ** (zu - i) * c(5 - used, zu - i) return sdef get_zu(r_xiang_zu, b_xiang_zu, r_space, b_space): k = (r_xiang_zu, b_xiang_zu, r_space, b_space) if not k in zu: s = 0 for r_zu in range(6): for b_zu in range(6): for r_zu_river in range(6 - r_zu): # 因為是range，所以是6-r_zu for b_zu_river in range(6 - b_zu): ss = 1 ss *= place_zu(r_xiang_zu, r_zu) ss *= place_zu(b_xiang_zu, b_zu) ss *= c(r_space - r_zu, b_zu_river) * c(b_space - b_zu, r_zu_river) ss *= get_jv_ma_pao(b_space + r_space - r_zu - r_zu_river - b_zu - b_zu_river) s += ss zu[k] = s return zu[k]jv_ma_pao = {}def get_jv_ma_pao(a): if not a in jv_ma_pao: s = 0 for r_jv in range(3): for b_jv in range(3): for r_ma in range(3): for b_ma in range(3): for r_pao in range(3): for b_pao in range(3): t = a ss = 1 ss *= c(t, r_jv) t -= r_jv ss *= c(t, b_jv) t -= b_jv ss *= c(t, r_ma) t -= r_ma ss *= c(t, b_ma) t -= b_ma ss *= c(t, r_pao) t -= r_pao ss *= c(t, b_pao) t -= b_pao s += ss jv_ma_pao[a] = s return jv_ma_pao[a]s = get_jiang()print("狀態數", s, "=10^{}".format(math.log10(s)))bits_per_state = math.log2(s)print("定長編碼，每個狀態的bit數", bits_per_state)space = bits_per_state * sprint("定長編碼存儲全部狀態所需空間", space / 8 / 1024 / 1024 / 1024 / 1024, "TB")

實驗結果

經過實驗，我們得出了中國象棋狀態總數的具體數值，用科學計數法表示為 ，這個結果遠遠小於前人文獻中的數值。在引文1中，中國象棋狀態總數為 。引文2中，徐心和、王驕在《中國象棋計算機博弈關鍵技術分析》中給出的答案是 。這些文獻中並沒有給出準確的中國象棋狀態計算方法而僅僅給出一個數值。根據本文實驗結果，前人結果可以說是太粗略了。

如果用定長編碼來描述中國象棋的一個狀態，只需對中國象棋狀態總數取以2為底的對數，得到結果132.47bit，這就是描述一個狀態最少需要的bit數。如果將中國象棋全部狀態存儲下來，只需要將狀態佔用bit數乘以狀態個數，結果為 TB。