解出「狐狸与羊」：用置换索引把 2⁴¹ 个局面全部算完
来源：blog.sesse.net — 2026-11-13
📋 概述
作者用约一千行无依赖代码，为北欧棋盘游戏「狐狸与羊」（halatafl）做了完备解：33 格棋盘，20 只羊对 2 只狐狸。结论是完美走法下羊必胜，19 只羊（侧翼少一只）也能赢，18 只且羊先手同样赢；9 只羊是能强制求和的下限。实现上用两张 64 位位图表示羊与狐狸，用组合数系统给局面做无冲突编号，每个局面只存 2 比特胜负，靠 mmap 处理超过 256GB 内存的表，最终跑约 36 小时。
🔑 核心要点
- 位图表示：羊、狐各一张 64 位图，多出来的一位存「轮到谁走」，配合 POPCNT 与位扫描指令。
- 局面数略超 2⁴¹，每局面 2 比特（羊胜/狐胜/和/非法），总量 329,870,110,455 字节。
- 用左右镜像取较小序号做规范化，把要算的局面砍掉一半；再按狐狸落点预分块，省掉约 95% 的浪费。
- 求值不用深搜而是一轮轮传播已知胜负，每块 40 到 80 轮；作者承认改成逆向分析能快十倍，但没必要。
- 只存 WDL 没有距离信息，于是另写 alpha-beta 用 bitbase 引导，找约 20 半层内的必胜线。
💡 金句
The sheep win with perfect play, even with only 19 sheep (remove one on the flank), or 18 if they are allowed to go first.
← 返回 Lobsters 首页
👍 0
👎 0