将井字棋编码进 15 位
把井字棋尽可能紧凑地编码，会变成一场信息论的游乐场：人们从简单的三进制表示（9 个格子需要 15 位）一路探索到通过枚举所有合法可达状态把它压到 13 位。还有人进一步尝试用不到 20 位编码整盘历史，或利用对称性与最优策略剪掉不可能或冗余的状态，同时争论这种压缩究竟何时有用、何时只是让代码更复杂。讨论中还顺带提到查找表与算法编码的取舍、能进化出完美玩家的遗传算法，以及与象棋、四子棋和机械谜题等更复杂游戏的类比。
棋盘状态编码与比特数
- 文章主体将一个井字棋棋盘编码为 9 个三进制数字 → 15 位。
- 多位评论者展示了进一步压缩：
- 计算所有可达的合法棋盘得到 5,478 个状态，因此不考虑对称性时 13 位就足够了。
- 一种实现通过组合编码将棋盘编码到 [0, 6045]（“先选择被填充的格子，再从中选择 O 的位置”），同样只需 13 位。
- 还有人指出，朴素的“765 个状态只需 10 位”方案是假设棋盘已经做了对称去重；真实对局还需要额外比特来表示朝向（旋转/翻转），这会把需求推回到大约 13 位。
对称性、合法性与边界情况
- 处理对称性很棘手：有些棋盘需要 3 位来消除旋转+镜像的歧义，有些更少，有些则不需要（完全对称）。
- 只统计“合法、可达”的棋盘（符合轮流落子且在有人获胜后不再继续下子）是必要的；最初的脚本在对角线胜利判断上有 bug，导致计数略有偏高。
- 还存在不可达状态（双方都出现连线获胜，或彼此分离的多个胜利），这些都必须排除。
编码完整对局历史
- 有多种方案可以编码整盘对局过程：
- 简单的阶乘上界：对所有落子排列，9! ≈ 19 位；剔除无效对局只节省大约 1 位。
- 一位评论者严谨地论证，18 位无法编码所有可能的序列（至少需要 19 位）；另一个 18 位方案则被指出错误地使用了“空余”的比特模式。
- 其他想法：
- 可变长度编码，在有人获胜时立即停止。
- 利用对称性减少首步选择（角/边/中心等价）。
策略、AI 与人类对弈
- 讨论了 minimax 博弈：最优对弈至少可保平局；也有人认为，对人类对手来说，非 minimax 的“设陷阱”策略可能更容易赢。
- 还出现了一些历史/教育系统：基于 matchbox 的强化学习器、布尔逻辑策略、在所有游戏状态上进化的遗传算法。
表示法、查找表与权衡
- 围绕查找表是否算“作弊”展开争论：条件链和数组在功能上是等价的；有人建议按数据+代码的总比特数来评判方案。
- 也有人指出，即使存在 10 位的规范编码，实际系统仍可能保留一个映射表，转换到更方便的 13–18 位结构。
- 还澄清了三位数字与比特的关系：9 个 trit 可以装进 15 个二进制位；并不需要假设有三进制硬件。