全球熱推薦：保存象棋棋盤信息，需要多少比特？我只用139-167位二進(jìn)制

2023-04-24 08:26:06來源：騰訊云

如何存儲當(dāng)前棋局

方案有3種：

(相關(guān)資料圖)

象棋一共32個棋子，每個棋子有91種狀態(tài)：死亡或位于0-89中任一位置。所以用長度為32的列表即可，每個數(shù)的值域是0-90，其中90代表死亡。死亡的棋子不再占用空間，使用類似map的結(jié)構(gòu)，key是棋子id，value是棋子位置（0-89）。壓縮空間的方案：將帥個子有9個可能在的位置，只需要0-9即可表示，需要至多5位二進(jìn)制。士有5種位置，每個士只需要至多3位二進(jìn)制。以此類推……占用空間最少。

分析方案一：數(shù)組長度為32，每個數(shù)組項目是個uint8，總共8 * 32 = 256 位。

分析方案二：在棋子多的時候，占用空間較多，所以存儲空間的大小不太穩(wěn)定。

方案三占用空間少，但是開發(fā)成本也較高，需要開發(fā)者去拼接二進(jìn)制位。

今天我們探討方案三。

前綴碼

引入一個概念：Prefix-Free Code，也可以叫 Prefix Code，它來源于信息論學(xué)科，維基百科：en.wikipedia.org/wiki/Prefix… 描述如下：

A prefix codeis a type of code system distinguished by its possession of the "prefix property", which requires that there is no whole code word in the system that is a prefix (initial segment) of any other code word in the system. It is trivially true for fixed-length code, so only a point of consideration in variable-length code.

For example, a code with code words {9, 55} has the prefix property; a code consisting of {9, 5, 59, 55} does not, because "5" is a prefix of "59" and also of "55". A prefix code is a uniquely decodable code: given a complete and accurate sequence, a receiver can identify each word without requiring a special marker between words. However, there are uniquely decodable codes that are not prefix codes; for instance, the reverse of a prefix code is still uniquely decodable (it is a suffix code), but it is not necessarily a prefix code.

它舉了個例子，針對集合{9, 5, 59, 55}就不是 prefix code，因為「5」有二義性，遇到5后，不知道該結(jié)束流程，還是繼續(xù)讀取后面的9或5。

哈夫曼編碼 Huffman Coding

信息論中有個經(jīng)典問題：給定一篇文章，如何用最短的二進(jìn)制編碼它。

解決方案就是：找出出現(xiàn)的所有單詞集合（例如：I am good good good，出現(xiàn)了3個單詞），計算每個單詞出現(xiàn)頻率，以某種方式，構(gòu)造每個單詞對應(yīng)的二進(jìn)制編碼，滿足條件：基于前綴就能知道它代表哪個單詞。然后我們把這些前綴拼在一起，就成功編碼了（并且是可以解碼的）。

例如這種編碼 good = 0, I = 10, am = 11，文章就表示為1011000。

這是最簡短的編碼了。構(gòu)造方法就是通過構(gòu)造一顆哈夫曼樹，算法如下：

針對每一個單詞（或組合），都有一個對應(yīng)的頻數(shù)，作為頻數(shù)表。如果當(dāng)前只有1個，就進(jìn)入4，否則進(jìn)入2。找到頻數(shù)最低的2個，作為表示一個組合，他們對應(yīng)的頻數(shù)就是兩個單詞（或組合）的頻數(shù)之和，加入頻數(shù)表（同時刪除這2個單詞或組合各自的頻數(shù)）。選取的2個單詞（或組合），分別作為左子樹和右子樹，組成一個樹。進(jìn)入1?，F(xiàn)在得到了一個二叉樹（叫做哈夫曼樹），每個葉子結(jié)點代表一個單詞。規(guī)定左分叉為0，右分叉為1，這個單詞對應(yīng)的 Prefix Code就是根節(jié)點到它的路徑。

例如上述編碼對應(yīng)的哈夫曼樹就是：

對于象棋的啟發(fā)

回到象棋棋盤狀態(tài)的問題：

將帥有10個位置（包括死亡狀態(tài)）。士有6個位置（包括死亡狀態(tài)）。象有8個位置（包括死亡狀態(tài)）。馬有91個位置（包括死亡狀態(tài)）。車有91個位置（包括死亡狀態(tài)）。炮有91個位置（包括死亡狀態(tài)）。兵有48個位置（包括死亡狀態(tài)）。

不妨假設(shè)他們出現(xiàn)在各個位置的頻率都一致，不難構(gòu)造出對應(yīng)的編碼。（這樣的編碼是比較穩(wěn)定的，無論棋局變成什么樣子，存儲占用空間都不會太大）

10個位置，需要3-4位。6個位置，需要2-3位。8個位置，需要3位。48個位置，需要4-5位。91個位置，需要6-7位。

這樣算下來，保存一個象棋的棋子位置信息，最少需要:

(3+2*2+3*2+6*6+4*5)*2=138位，再用1位保存該誰下棋了，總共至少需要139位。至多需要(4+3*2+3*2+7*6+5*5)*2=166位，再用1位保存該誰下棋了，總共至多需要167位。

有辦法實現(xiàn)嗎？

上面說的很理想，如何實現(xiàn)呢？

我們以10個位置的情況，來探討通用的編碼生成方法。首先根據(jù)哈夫曼樹，可以構(gòu)造這樣的編碼：

000代表0001代表1010代表2011代表3100代表4101代表51100代表61110代表71101代表81111代表9

隨后容易發(fā)現(xiàn)這樣的規(guī)律：

至于0-5，用3位二進(jìn)制編碼即可。至于6-7，我們需要在3位的6(110)和7(111)末尾新增0。至于8-9我們需要在3位的6和7末尾新增1。

可以利用數(shù)學(xué)歸納法，歸納總結(jié)出這樣的算法：

針對X個位置的情況，計算Log2(X)，分別向下取整和向上取整，得到A和B。如果A=B，則用A位二進(jìn)制表示這X個數(shù)即可，直接轉(zhuǎn)換進(jìn)制。如果A0至2^A-1-(X-2^A)；用B位二進(jìn)制表示其它位置；針對位置2^A-(X-2^A)至2^A-1，編碼為A位的進(jìn)制轉(zhuǎn)換，并在末尾拼接一位0（共計B位）；針對其它位置，編碼為位置減去(X-2^A)再轉(zhuǎn)換二進(jìn)制，并在末尾拼接一位1（共計B位）。

可以發(fā)現(xiàn)，這種算法，位置編號小的比位置編號大的少了一位。也就是說，我們應(yīng)該盡量把出現(xiàn)頻率較高的位置放在前面。

生成各棋子的位置列表

const RedAllCandidates = new Array(90).fill(0).map((a, i) => 89 - i);const BlackAllCandidates = new Array(90).fill(0).map((a, i) => i);const RedSoliderCandidates = new Array(45).fill(0).map((a, i) => 44 - i);const BlackSoliderCandidates = new Array(45).fill(0).map((a, i) => 45 + i);// 分別是將、士、士、……const PieceCandidates = [  [85, 86, 84, 76, 77, 75, 67, 68, 66, 127],  [127, 86, 84, 76, 68, 66],  [127, 84, 86, 76, 66, 68],  [127, 87, 67, 71, 51, 83, 47, 63],  [127, 83, 67, 63, 47, 87, 51, 71],  [127, ...RedAllCandidates],  [127, ...RedAllCandidates],  [127, ...RedAllCandidates],  [127, ...RedAllCandidates],  [127, ...RedAllCandidates],  [127, ...RedAllCandidates],  [127, 62, 53, ...RedSoliderCandidates],  [127, 60, 51, ...RedSoliderCandidates],  [127, 58, 49, ...RedSoliderCandidates],  [127, 56, 47, ...RedSoliderCandidates],  [127, 54, 45, ...RedSoliderCandidates],  [4, 3, 5, 13, 12, 14, 22, 21, 23, 127],  [127, 3, 5, 13, 21, 23],  [127, 5, 3, 13, 23, 21],  [127, 2, 22, 18, 38, 6, 42, 26],  [127, 6, 22, 26, 42, 2, 38, 18],  [127, ...BlackAllCandidates],  [127, ...BlackAllCandidates],  [127, ...BlackAllCandidates],  [127, ...BlackAllCandidates],  [127, ...BlackAllCandidates],  [127, ...BlackAllCandidates],  [127, 27, 36, ...BlackSoliderCandidates],  [127, 29, 38, ...BlackSoliderCandidates],  [127, 31, 40, ...BlackSoliderCandidates],  [127, 33, 42, ...BlackSoliderCandidates],  [127, 35, 44, ...BlackSoliderCandidates],];

解釋：

我可以把將帥的「死亡」（127）調(diào)整到了最后一位，因為他們死亡是非常罕見的，這樣可以節(jié)約2bit空間。我刻意把棋子常見位置放在了數(shù)組前幾位，尤其是將帥、士、兵，這樣可以節(jié)約幾bit空間。兵的位置，紅色和黑色不同，剛過河的一排放在前面，離河遠(yuǎn)的位置放在后面，可以節(jié)約幾bit空間。

提前計算log

為了提高效率，我應(yīng)該避免在JS中計算Math.log2，而要提前定義好運算結(jié)果。

const ceilLog2Map = new Map([  [1, 0],  [2, 1],  [3, 2],  [4, 2],  [6, 3],  [8, 3],  [10, 4],  [17, 5],  [48, 6],  [91, 7],]);const floorLog2Map = new Map([  [1, 0],  [2, 1],  [3, 1],  [4, 2],  [6, 2],  [8, 3],  [10, 3],  [17, 4],  [48, 5],  [91, 6],]);

按照編碼規(guī)則encode

基于文章《JS 按自定義格式拼接二進(jìn)制串解析二進(jìn)制串》提到的concatBits函數(shù)，我寫了concatFlexibleBits函數(shù)：

function concatFlexibleBits(current: number, offset: number, candidateIndex: number, candidateLength: number): [number, number, number[]] {  const floorLog = floorLog2Map.get(candidateLength)!;  const ceilLog = ceilLog2Map.get(candidateLength)!;  const last = 2 ** floorLog;  const beyond = candidateLength - last;  if (floorLog === ceilLog || candidateIndex < last - beyond) {    return concatBits(current, offset, candidateIndex, floorLog);  }  let newCurrent = current;  let newOffset = offset;  const array: number[] = [];  let newUint8: number[];  if (candidateIndex < last) {    [newCurrent, newOffset, newUint8] = concatBits(newCurrent, newOffset, candidateIndex, floorLog);    array.push(...newUint8);    [newCurrent, newOffset, newUint8] = concatBits(newCurrent, newOffset, 0, 1);    array.push(...newUint8);  } else {    [newCurrent, newOffset, newUint8] = concatBits(newCurrent, newOffset, candidateIndex - beyond, floorLog);    array.push(...newUint8);    [newCurrent, newOffset, newUint8] = concatBits(newCurrent, newOffset, 1, 1);    array.push(...newUint8);  }  return [newCurrent, newOffset, array];}

這里encode規(guī)則，就是按照上面提到的算法實現(xiàn)的。不過多解釋了。

按照編碼規(guī)則decode

基于文章《JS 按自定義格式拼接二進(jìn)制串解析二進(jìn)制串》的readBits函數(shù)，我寫了readFlexibleBits函數(shù)：

function readFlexibleBits(array: Uint8Array, bitsOffset: number, candidateLength: number) {  const floorLog = floorLog2Map.get(candidateLength)!;  const ceilLog = ceilLog2Map.get(candidateLength)!;  const last = 2 ** floorLog;  const beyond = candidateLength - last;  const [number, offset] = readBits(array, bitsOffset, floorLog);  if (floorLog === ceilLog || number < last - beyond) {    return [number, offset];  }  const [current, offset2] = readBits(array, offset, 1);  if (current) {    return [number + beyond, offset2];  }  return [number, offset2];}

這里decode規(guī)則，是按照上面算法解析的。先讀取floorLog位，如果總位置數(shù)就是2的次方，則結(jié)束。如果讀取到的數(shù)比較小，也結(jié)束。如果讀取到的數(shù)超過某個臨界值，就需要多讀取一位，決定它代表誰。

結(jié)論

方案三可以實現(xiàn)，并且比方案一節(jié)約了35%-45%的空間。

關(guān)于性能：編碼、解碼邏輯全都位于用戶瀏覽器中執(zhí)行，對服務(wù)器無影響，瀏覽器也會在人感知不到的耗時內(nèi)運算完。

有什么用？

我在開發(fā)《象棋》時，期望通過URL來分享棋局。我希望分享的URL能永久有效，而且不喜歡給服務(wù)器太多債務(wù)（不采用token+數(shù)據(jù)庫存儲棋盤信息）。那么URL中必須包含完整的棋盤信息。

如果把棋盤信息存到URL中，那么URL越短，越好。

例如：game.hullqin.cn/xq?p=gSQCL5P5oIDhCFJCIBJ4eQCAkX8&r=86pU6-4nbSh38OCojLarcupWOb1rXw&s=1 ，點開后就能立馬展現(xiàn)某場對局。

這個URL里，保存了棋盤所有棋子信息、所有歷史記錄（10個回合即20步）。方便大家保存、分享。

保存歷史記錄，也是通過類似的手段實現(xiàn)的，占用空間非常?。ㄩL度兩百的字符串，足夠存儲大部分常規(guī)對局的歷史記錄）。

歡迎觀看【可以「旋轉(zhuǎn)棋盤」的聯(lián)機(jī)象棋】 - 嗶哩嗶哩

寫在最后

我是HullQin，公眾號線下聚會游戲的作者（歡迎關(guān)注我，交個朋友）。轉(zhuǎn)發(fā)本文前需獲得作者HullQin授權(quán)。我獨立開發(fā)了《聯(lián)機(jī)桌游合集》，是個網(wǎng)頁，可以很方便的跟朋友聯(lián)機(jī)玩UNO、飛行棋、斗地主、五子棋、一夜狼、狼人殺、象棋、德國心臟病、達(dá)芬奇密碼等游戲，不收費無廣告。還開發(fā)了《Dice Crush》參加Game Jam 2022。喜歡可以關(guān)注我噢～我有空了會分享做游戲的相關(guān)技術(shù)，會在這個專欄里分享：《教你做小游戲》。

關(guān)鍵詞：