保存象棋棋盘信息，需要多少比特？我只用139-167位二进制_观热点
如何存储当前棋局
方案有3种：
象棋一共32个棋子，每个棋子有91种状态：死亡或位于0-89中任一位置。所以用长度为32的列表即可，每个数的值域是0-90，其中90代表死亡。死亡的棋子不再占用空间，使用类似map的结构，key是棋子id，value是棋子位置（0-89）。压缩空间的方案：将帅个子有9个可能在的位置，只需要0-9即可表示，需要至多5位二进制。士有5种位置，每个士只需要至多3位二进制。以此类推……占用空间最少。分析方案一：数组长度为32，每个数组项目是个uint8，总共8 * 32 = 256 位。
分析方案二：在棋子多的时候，占用空间较多，所以存储空间的大小不太稳定。
(资料图)
方案三占用空间少，但是开发成本也较高，需要开发者去拼接二进制位。
今天我们探讨方案三。
前缀码
引入一个概念：Prefix-Free Code，也可以叫 Prefix Code，它来源于信息论学科，维基百科：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后，不知道该结束流程，还是继续读取后面的9或5。
哈夫曼编码 Huffman Coding
信息论中有个经典问题：给定一篇文章，如何用最短的二进制编码它。
解决方案就是：找出出现的所有单词集合（例如：I am good good good，出现了3个单词），计算每个单词出现频率，以某种方式，构造每个单词对应的二进制编码，满足条件：基于前缀就能知道它代表哪个单词。然后我们把这些前缀拼在一起，就成功编码了（并且是可以解码的）。
例如这种编码 good = 0, I = 10, am = 11，文章就表示为1011000。
这是最简短的编码了。构造方法就是通过构造一颗哈夫曼树，算法如下：
针对每一个单词（或组合），都有一个对应的频数，作为频数表。如果当前只有1个，就进入4，否则进入2。找到频数最低的2个，作为表示一个组合，他们对应的频数就是两个单词（或组合）的频数之和，加入频数表（同时删除这2个单词或组合各自的频数）。选取的2个单词（或组合），分别作为左子树和右子树，组成一个树。进入1。现在得到了一个二叉树（叫做哈夫曼树），每个叶子结点代表一个单词。规定左分叉为0，右分叉为1，这个单词对应的Prefix Code就是根节点到它的路径。例如上述编码对应的哈夫曼树就是：
对于象棋的启发
回到象棋棋盘状态的问题：
将帅有10个位置（包括死亡状态）。士有6个位置（包括死亡状态）。象有8个位置（包括死亡状态）。马有91个位置（包括死亡状态）。车有91个位置（包括死亡状态）。炮有91个位置（包括死亡状态）。兵有48个位置（包括死亡状态）。不妨假设他们出现在各个位置的频率都一致，不难构造出对应的编码。（这样的编码是比较稳定的，无论棋局变成什么样子，存储占用空间都不会太大）
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位。
有办法实现吗？
上面说的很理想，如何实现呢？
我们以10个位置的情况，来探讨通用的编码生成方法。首先根据哈夫曼树，可以构造这样的编码：
000代表0001代表1010代表2011代表3100代表4101代表51100代表61110代表71101代表81111代表9随后容易发现这样的规律：
至于0-5，用3位二进制编码即可。至于6-7，我们需要在3位的6(110)和7(111)末尾新增0。至于8-9我们需要在3位的6和7末尾新增1。可以利用数学归纳法，归纳总结出这样的算法：
针对X个位置的情况，计算Log2(X)，分别向下取整和向上取整，得到A和B。如果A=B，则用A位二进制表示这X个数即可，直接转换进制。如果A2^A-1-(X-2^A)；用B位二进制表示其它位置；针对位置2^A-(X-2^A)至2^A-1，编码为A位的进制转换，并在末尾拼接一位0（共计B位）；针对其它位置，编码为位置减去(X-2^A)再转换二进制，并在末尾拼接一位1（共计B位）。可以发现，这种算法，位置编号小的比位置编号大的少了一位。也就是说，我们应该尽量把出现频率较高的位置放在前面。
生成各棋子的位置列表
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）调整到了最后一位，因为他们死亡是非常罕见的，这样可以节约2bit空间。我刻意把棋子常见位置放在了数组前几位，尤其是将帅、士、兵，这样可以节约几bit空间。兵的位置，红色和黑色不同，刚过河的一排放在前面，离河远的位置放在后面，可以节约几bit空间。提前计算log
为了提高效率，我应该避免在JS中计算Math.log2，而要提前定义好运算结果。
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],]);按照编码规则encode
基于文章《JS 按自定义格式 拼接二进制串 解析二进制串》提到的concatBits函数，我写了concatFlexibleBits函数：
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规则，就是按照上面提到的算法实现的。不过多解释了。
按照编码规则decode
基于文章《JS 按自定义格式 拼接二进制串 解析二进制串》的readBits函数，我写了readFlexibleBits函数：
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规则，是按照上面算法解析的。先读取floorLog位，如果总位置数就是2的次方，则结束。如果读取到的数比较小，也结束。如果读取到的数超过某个临界值，就需要多读取一位，决定它代表谁。
结论
方案三可以实现，并且比方案一节约了35%-45%的空间。
关于性能：编码、解码逻辑全都位于用户浏览器中执行，对服务器无影响，浏览器也会在人感知不到的耗时内运算完。
有什么用？
我在开发《象棋》时，期望通过URL来分享棋局。我希望分享的URL能永久有效，而且不喜欢给服务器太多债务（不采用token+数据库存储棋盘信息）。那么URL中必须包含完整的棋盘信息。
如果把棋盘信息存到URL中，那么URL越短，越好。
例如：game.hullqin.cn/xq?p=gSQCL5P5oIDhCFJCIBJ4eQCAkX8&r=86pU6-4nbSh38OCojLarcupWOb1rXw&s=1 ，点开后就能立马展现某场对局。
这个URL里，保存了棋盘所有棋子信息、所有历史记录（10个回合即20步）。方便大家保存、分享。
保存历史记录，也是通过类似的手段实现的，占用空间非常小（长度两百的字符串，足够存储大部分常规对局的历史记录）。
欢迎观看 【可以「旋转棋盘」的联机象棋】 - 哔哩哔哩
写在最后
我是HullQin，公众号线下聚会游戏的作者（欢迎关注我，交个朋友）。转发本文前需获得作者HullQin授权。我独立开发了《联机桌游合集》，是个网页，可以很方便的跟朋友联机玩UNO、飞行棋、斗地主、五子棋、一夜狼、狼人杀、象棋、德国心脏病、达芬奇密码等游戏，不收费无广告。还开发了《Dice Crush》参加Game Jam 2022。喜欢可以关注我噢～我有空了会分享做游戏的相关技术，会在这个专栏里分享：《教你做小游戏》。
关键词：
