六子棋是和棋:首个公开发表的解
Morris 是三连棋类游戏的统称。你先把棋子放到由线条构成的棋盘上,然后沿线滑动;三枚己方棋子连成标记线上的一行即构成三连,可以吃掉对方一枚棋子。把对方逼到不足三枚棋子,你就赢了。
九子棋是其中最有名的一种,三十多年前就已被解决:Ralph Gasser 在 1993 年强解了它,结论是双方最佳着法下和棋;Gévay 与 Danner 在 2014 年又计算了这一族游戏的扩展解。
六子棋用的是同一块棋盘去掉外圈,它出现在每一份 morris 变体清单上,却没出现在求解论文里。我强解了它:全部 42,372,745 个可达局面均为和棋。
打开最佳着法局面浏览器 → 你可以对着残局库走任意变化:每一着都按双方最佳着法下的结果着色,绿色为胜,灰色为和,红色为负。规模开关可在每方四子、五子、六子之间切换。
游戏规则
六子棋在两个同心正方形上进行,四条边的中点用线相连:共 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 万个局面都能装进内存,因此整个求解在一台笔记本上约一分钟即可完成,不需要外部存储。三个彼此独立的求解器给出一致结果,四子和五子变体的结果也互相吻合。若真有一个更小的已解 morris 变体,它提供的交叉验证也不过如此。
值得注意的发现
没有哪一步开局是漏着,但应手是道考题。每一种首着摆法都能和棋,但它们对应手的考验程度差别很大。摆在中点上,对手十五种应手全部和棋;摆在角上,十五种应手里有八种要输。在外圈角上摆子之后,分界正好沿着两个圈:外圈其余点和棋,整个内圈都输。
和棋是一条狭窄的通道。这盘棋从一开始就是和棋,但和棋局面很稀少:4200 万个局面里只有 350 万个,约占 8%。其余 92% 的局面中,总有一方已经稳赢或已经输定。
这一族游戏以对角线为分水岭。六子棋与九子棋、Lasker Morris 一样是和棋。唯一先手必胜的 Morabaraba,恰恰是唯一加入对角线三连的变体。
九子棋被解决了吗?
解决了,而且已经解决了三十多年。Ralph Gasser 强解了九子棋:双方最佳着法下和棋,这一结论发表于 1993 年的 ETH 技术报告,并在 1996 年以《Solving Nine Men’s Morris》为题收入 Games of No Chance。两个年份都常被引用: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:逆向求解器与 morris 插件,残局库作为发布附件提供。
- 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)。