六子棋是和棋:首个公开发表的解
要点
- 六子棋已完成强解:覆盖全部 42,372,745 个可达局面,结果是和棋。这是首个公开发表的解。
- 十六种第一手落子全部导向和棋,但对应着的考验各不相同:第一手下在角上,十五种应着中有八种会输;下在边中点上,则没有一种会输。
- 只有 8% 的局面是和棋。其余局面中,已有一方占据胜势。
- 整个残局库能放进内存,在笔记本电脑上约一分钟解完,并能在你的网页浏览器里运行。
莫里斯棋是一族三连棋类。你先把棋子放到由线组成的棋盘上,再沿线移动它们;你的三枚棋子落在一条标记线上就构成三连,可以借此移除对手的一枚棋子。把对手的棋子压到少于三枚,你就赢了。
九子棋是其中最有名的,三十多年前就已解出:Ralph Gasser 在 1993 年强解了它,双方最佳着法下为和棋;Gévay 和 Danner 在 2014 年计算了这一族棋类的扩展解。
六子棋就是同一个棋盘去掉外圈,它出现在每一份莫里斯棋变体清单上,却不在求解论文中。
打开最佳着法局面浏览器 → 对着残局库走任意变化:每一着都按双方最佳着法下的结果着色,绿色为胜,灰色为和,红色为负。规模开关可以在每方四枚、五枚和六枚棋子之间切换。
游戏
六子棋的棋盘由两个同心正方形组成,四条边的中点由线相连:共 16 个点,没有对角线。它就是去掉外层正方形的九子棋棋盘。
每名玩家有六枚棋子。先是落子阶段,双方轮流把棋子放到空点上;十二枚全部落下后,进入走子阶段,棋子沿线移到相邻的空点。你的三枚棋子落在一条标记线上(任一正方形的边)就构成三连;每完成一个三连,就移除一枚不在三连中的敌方棋子,除非敌方棋子全都在三连中。棋子少于三枚,或轮到你走却无子可动时,你就输了。
我求解的是不允许飞子的标准规则:只剩三枚棋子的一方仍然一次只走一步。飞子(只剩三子的一方可以跳到任意空点)会改变着法树;单独求解后也是和棋,所以结果在两种约定下都成立。
结果
六子棋已完成强解:残局库保存了每个可达局面的值,所以从任何局面出发都能走出双方最佳着法。我从终局局面出发,在整个游戏范围内反向推算,构建出了这个残局库。
开局是和棋,白方的十六种第一手落子都能保持和棋。
| 项目 | 数值 |
|---|---|
| 可达局面 | 42,372,745 |
| 胜 / 和 / 负(行棋方) | 23,392,364 / 3,459,385 / 15,520,996 |
同一棋盘在棋子更少时也是和棋:
| 每方棋子数 | 可达局面 | 开局 |
|---|---|---|
| 4 | 4,111,151 | 和棋 |
| 5 | 17,844,721 | 和棋 |
| 6 | 42,372,745 | 和棋 |
这是首个公开发表的解,不能证明是史上第一个。学术工作(Gasser 1996;Gévay 和 Danner 2014)和开源求解器 Malom 与 Sanmill 都没有涉及六子棋,这些求解器覆盖了九子棋、十二子棋、Lasker Morris 和 Morabaraba,但没有六子棋。所以我公开了残局库和求解器,任何人都可以核查。
全部 4200 万个局面都能放进内存,所以在笔记本电脑上约一分钟就能解完,不需要外部存储。三个独立的求解器结果一致,每方四枚和五枚棋子的变体结果也相互吻合;如果存在一个更小的已解莫里斯棋,它能提供的交叉验证也就是这样。
主要发现
没有哪一种开局是败着,但应着是一场考验。第一手下在边中点,对手的十五种应着都还是和棋。第一手下在角上,十五种应着中有八种会输。第一手下在外圈角上后,结果按圈分开:外圈其余的点都是和棋,内圈的点全部会输。
和棋之路很窄。游戏从开局起就是和棋,但和棋局面很少:4200 万个中只有 350 万个,约 8%。在其余 92% 的局面中,一方已经必胜或必败。
这一族棋类以对角线为界。六子棋与九子棋、Lasker Morris 一样是和棋。先手胜的只有 Morabaraba,它也是唯一加入对角三连的变体。
九子棋已被解决了吗?
是的,而且已有三十多年。Ralph Gasser 强解了九子棋:双方最佳着法下为和棋,他在 1993 年的一份 ETH 技术报告中公布了结果,并于 1996 年在 Games of No Chance 中写成 Solving Nine Men’s Morris 一文。两个年份都有人引用;1993 年是求解,1996 年是论文。
Gévay 和 Danner 后来在 2014 年计算了这一族棋类的超强解和扩展解,开源求解器 Malom 和 Sanmill 覆盖了九子棋、十二子棋和 Lasker Morris。
六子棋就是那块空白。补上之后,这一族棋类的情况如下:
| 变体 | 结果 | 首次求解 |
|---|---|---|
| 三子棋 | 先手胜 | 民间流传 |
| 六子棋 | 和棋 | Liou,2026 |
| 九子棋 | 和棋 | Gasser,1993 |
| Lasker Morris | 和棋 | Stahlhacke,2003 |
| Morabaraba | 先手胜 | Gévay,2015 |
每种变体的结构化记录,包括引用和复杂度数据,都在 solved-games 里。
结语
六子棋是和棋,它的残局库小到可以放进内存并整体分发,所以上面的局面浏览器能在你的网页浏览器里运行完整的解。九子棋要大数千倍,需要逐片求解;从零复现它已知的和棋结论是这个引擎的下一个目标,这更多是一个规模问题,而不是新结果。
资源:
- 六子棋局面浏览器:对着残局库走任意变化,每一着都标注为胜、负或和。
- game-solver:逆向分析求解器和莫里斯棋插件,残局库作为发布文件提供。
- solved-games:已被解决的游戏的结构化登记表,这一结果已收录其中。
- Gasser,Solving Nine Men’s Morris(Games of No Chance,1996):规模更大的同族棋类。
- Gévay 与 Danner,Calculating Ultra-Strong and Extended Solutions for Nine Men’s Morris, Morabaraba, and Lasker Morris(2014)。