为了乐趣和利润而压缩国际象棋走法

主要观点:作者通过新技巧将 Chess moves 压缩至比原有方法约 2.5 倍更高效,介绍了多种编码方式以减少 Chess moves 存储所需空间,如对棋子、捕获、目标方格等的编码优化,还提到 PGNs 的压缩以及该改进对数据库大小和查询速度的影响等。
关键信息:

  • 原有 Chess 记法 Qxf7 需 4 字节(32 位),实际只需 10 位。
  • 第一遍编码方式需 29 位(约 3.5 字节),不够好。
  • 利用前 3 位编码常见城堡移动 O-OO-O-O
  • 除城堡外需 6 位编码目标方格, pawn 移动时部分情况可减少位数。
  • 用 1 位确定移动是否“特殊”,节省大量位。
  • 晋升只需 2 位编码晋升棋子。
  • 用 2 位编码歧义,多数情况用 3 位编码 rank 或 file ,极少用 6 位编码整个方格。
  • 对 PGNs 压缩效果显著,可将 759 字节压缩至 195 字节,节省 74%。
  • 此改进预计使数据库大小减少约 70%,查询速度提升约 3 倍,编码/解码速度虽有开销但对整体影响小。
    重要细节:
  • 编码文件或 rank 需 3 位(8 种可能),编码棋子需 3 位(6 种可能),编码方格需 6 位(64 种可能)。
  • 各种移动编码方式的具体示例及代码实现,如不同棋子移动的编码、pawn 捕获的编码等。
  • 对不同 Chess move 压缩前后的位数对比及节省比例。
  • PGNs 中每个 move 间有 1 字节空格,每个 full move 间至少有 3 字节空格。
阅读 10
0 条评论