解决棋盘游戏QuoridorSolving the board game Quoridor

这篇论文在解决棋盘游戏 Quoridor 方面显著提升了现有技术水平。我描述了一种新技术，使普通笔记本电脑能够完全解决几乎所有面积≤28的棋盘配置（例如5x5、8x3、7x4等）在大多数墙数量下的情况。

背景

我在2014年首次接触到棋盘游戏Quoridor，立刻被它吸引。

每隔几年我都会用周末时间重新研究Quoridor，编写不同形式的AI机器人来玩它。这个周末，我取得了一项突破，使得AI机器人不仅更强，而且能更完整地解决问题。

规则

这个游戏非常简单：

这条最后规则带来了所有性能复杂性。你可能计划堵住朋友直行的路线——迫使他绕远路——但他放了一面墙切断了长路径，现在你堵短路径就变成非法操作了！

"棋子跳过对手棋子"的规则产生了有趣的奇偶性/zugzwang局面。

除了典型的9x9棋盘和10面墙外，许多论文分析了更小尺寸棋盘和更少墙的情况，因为完整的游戏目前还难以处理。

主要成果

奇偶优势 vs 节奏优势

许多人推测由于棋子跳跃的奇偶性，奇数高度棋盘可能是后手必胜。这项研究表明奇数高度Quoridor棋盘并非总是后手必胜。

在墙很少时总是后手必胜，但通常在足够多的墙时会转为先手必胜。例如，5x5棋盘在双方≤4面墙时是后手必胜，＞4面墙时是先手必胜。

直觉上，奇数高度棋盘对后手有跳跃奇偶优势，但先手仍保持节奏优势，足够多的墙会使先手的节奏优势压倒后手的跳跃优势。

下面讨论了一些值得注意的例外情况。

相关研究发现，偶数高度棋盘在所有墙数量下都是先手必胜，因为先手同时拥有跳跃奇偶优势和节奏优势。

强制平局

已知通过重复可以构造强制平局，但本研究证明8x3棋盘（双方各3面墙）从初始位置就是平局。

双方只需永远左右交替移动。如果任何一方偏离这种重复策略，另一方就能强制获胜，因此最优策略是通过重复实现平局。

特殊几何形状

某些几何形状会出现异常结果。例如：

4x7棋盘在0或1面墙时后手必胜，2面墙时先手必胜，3面墙又变回后手必胜，更多墙时先手必胜。

7x3棋盘在任何墙数量下都不会变为先手必胜。

3x5棋盘在所有墙数量下都是后手必胜，除了3面墙时。

8x3棋盘在所有墙数量下都是后手必胜，除了3面墙时（如上所述是平局）。

完整结果表格

注：偶数高度棋盘已省略，它们在所有墙数量和几何形状下都是先手必胜。

可以通过运行本仓库中的代码复现本研究的结果。较小的配置几乎瞬间完成，表格中最大的配置在我的 M3 MacBook Pro 上需要长达 30 分钟。我有 128GB 内存，而最大配置会占用其中相当一部分来存储所有预计算数据和转置表。

复杂度

Quoridor 有两个主要复杂化因素。

“完全封锁目标非法”规则使得枚举合法移动变得困难。简单地，你必须在每个候选移动上进行路径搜索。这意味着移动生成速度比国际象棋慢几个数量级。

加剧这一问题的还有较高的分支因子。在任意回合中，通常有 4 个兵移动和约 100 种可能的墙移动。因此，不仅检查墙移动的合法性非常缓慢，而且它们的数量也非常庞大。

这种巨大的分支因子使得朴素的 alpha-beta negamax 算法表现不佳。要让机器人搜索到深度 6 左右，需要付出相当多的努力。

除了巨大的分支因子，地平线效应更难处理。在国际象棋中，你可以通过静默搜索轻松应对地平线效应，即只搜索“有趣”的移动（例如吃子、将军），直到没有这样的移动为止，此时局面变为“安静”。

而在 Quoridor 中，几乎没有安静的局面，因为可以在任何时候在棋盘的任何位置放置墙壁。

除了无法太深入搜索外，一旦达到某个深度，评估局面真的很难。你有短路径，很好——它能被切断吗？你能阻止它吗？你有墙，很棒——你能否有效利用它们，还是对手处于一条安全走廊，不会被墙影响？等等。

所有这些复杂性让我认为 Quoridor 非常适合 AlphaZero 类型的算法，这种算法在高分支因子和复杂评估函数的游戏中大放异彩。

杂项优化技巧

多年来开发 Quoridor 机器人时积累的一些技巧。有些高度特定于 Quoridor，其他则像计算机国际象棋社区中众所周知的方法。这些技巧并未全部用于完整求解器，但依然对一般 Quoridor 机器人具有参考价值或适用性。

墙合法性启发式

如果你在开放区域放置一个孤立的墙，总是可以绕过它，因此无需进行合法性检查。

进一步地，如果放置的墙仅与另一堵墙（或棋盘边缘）在一个点接触，也总是可以绕过它，因此无需进行合法性检查。

只有当墙在三个接触点中有至少两个与其他墙或边缘接触时，才需要进行合法性检查。

大多数墙是合法的

你的评估函数几乎肯定使用路径长度作为输入。这需要运行路径算法。

由于你已经在叶节点评估函数中执行此操作，因此在所有移动生成过程中应跳过它。移动是合法的！

只需递归假设所有墙移动都是合法的，如果在叶节点发现哎呀我们进入了非法分支也没关系，只需返回 null 而不是分数来标记该节点无效即可。

如果你在内节点且第一个子节点返回 null，则进行路径检查以查看内节点是否非法，如果是则快速返回 null。

这种优化之所以有效，是因为 Quoridor 中的非法性是单调的。一旦进入非法状态，就无法到达合法状态。

Bitboards

标准 Quoridor 棋盘是 9x9 格的，但墙的长度为 2，因此只有 8x8 的位置可以放置墙。这意味着可以用一个 64 位整数表示所有水平墙，另一个 64 位整数表示所有垂直墙。现在只需少量操作即可获取候选的墙移动方案。

换位

换位表是一个简单的 2 倍优势。加入水平对称性可再获得 2 倍优势。由于棋盘状态仅需很少的比特数，甚至无需使用 Zobrist 哈希，可直接将其用作键值或仅需少量操作进行哈希。

求解

突破性优化

有一种技巧使得求解类似 5x5 Quoridor 的棋盘变得快速且简单，它基于以下两个观察：

即，对于每种墙状态，从每位玩家的终点行进行洪水填充，生成一个掩码，包含该玩家的棋子可以合法占据的所有格子。

这使得合法性检查极其廉价。要检查某墙移动是否合法，只需在表中查找该配置，并验证两位玩家的棋子是否在洪水填充的格子上。

以下是从一位玩家的视角展示合法状态与非法状态的示例棋盘。

结合其他技巧，我仅用笔记本电脑几分钟就完全解决了 5x5 Quoridor。

遗憾的是，此解决方案无法扩展到完整的 9x9 棋盘，后者有 1020 种可能的墙配置。

如果有人愿意投入资金，很可能只需花费几百美元的云计算成本就能解决下一个规模的棋盘问题。

6x6 棋盘并不真正有趣，因为几乎可以确保先手必胜（由于高度为偶数），但例如 7x5 棋盘可能会很有趣。

证明搜索

先前的工作主要集中在利用逆向分析来求解小型 Quoridor 变体。

此项工作主要采用一种与证明数搜索密切相关的算法，据我所知，这种算法似乎从未被应用于 Quoridor。

在进行这项研究之前，我并未了解证明数搜索，而是通过修改负极大值算法，无意中重新发明了它，直到其本质变为证明搜索。

最初我使用的是带 (-∞, ∞) alpha-beta 界限的正常迭代加深负极大值算法和胜负评估函数，但通过初始化为 (0, ∞) alpha-beta 界限，可获得更多的 beta-剪枝。

在每个深度，先假设先手获胜进行搜索，若未找到强制胜利，则假设后手获胜进行搜索，若仍未找到强制胜利，则在下一深度再次尝试。

由于这种结构，传统的 alpha-beta 技术如动作排序能显著加速搜索过程。

我进入这项研究时猜想该算法总是终止且起始位置不存在强制平局。我发现当最大深度不断上升时，8x3 棋盘上有 3 道墙存在强制平局，然后我添加了逆向求解器回退以证明平局。本文提到的各种优化使逆向分析在此规模下可行。

附加实现细节

在预计算所有墙配置及合法性掩码时，可以为任何墙配置预计算更多信息以进一步提升性能：

未来工作

枚举墙的前沿而非整个墙配置

你其实无需关心完整的墙状态。真正重要的是精确的非法前沿——即当前棋盘上导致非法性的最小墙集合。

由于非法性是单调的，一旦找到这样的最小集合，额外添加的墙不会使棋盘“更非法”。

因此更好的算法是枚举所有可能的最小非法前沿（而非所有墙配置），然后实现某种高效数据结构，快速检查任一非法前沿是否是当前墙状态的子集。

遗憾的是，即使能在纳秒级完成合法性检查，这种方法仍不足以解决9x9 Quoridor，分支因子仍然过高。

不过这种方法或许能扩展到6x6甚至7x7。

枚举所有可能路径而非墙

与其枚举所有可能的墙配置或前沿，不如枚举所有可能路径，再根据当前墙配置巧妙剪枝有效路径集合。若有效路径为空，则该状态非法。

我对此思考较少，但感觉可能有潜力。7x7棋盘上所有格子的路径数量尚可处理——仅几十亿条。

分治分块

或许可以将9x9棋盘划分为更小的块，例如九个3x3块。

然后预计算每个块的所有可能性。块的键由其墙配置+目标可达性决定，而块的可达性取决于其自身墙配置+邻居墙配置及邻居的可达性。

这样可将9x9寻路转化为3x3寻路，速度大概提升10倍。我不确定这对求解是否有用，但对游戏应该有帮助。

结语

我会隔几个月在淋浴时继续思考这个问题，希望能有新的洞见。

有趣的是，即使是顶级LLMs——即便被要求通宵在这个问题上训练——也远未达到这一洞察（已在codex CLI上用gpt-5.5-xhigh测试过）。将其保留为未公开评估很有趣，但公开发布也很有价值。未来LLMs能否超越这个结果，值得期待。

当然，我确实使用了编码助手来实现本项目最新版本的所有代码，只需提供上述高层次思路。我已实现足够多的Quoridor位棋盘，足以支撑一生，没有这些辅助工具，我不会花这么多时间重访这个项目。

呼吁他人参与

如果有自信能用几百美元云GPU训练类似AlphaZero的Quoridor bot的年轻人，请与我联系提案，我很乐意资助。我真的很好奇超人类水平的Quoridor会是什么样子。

开始游戏

快速配置 宽度 高度 每面墙 最大深度 思考秒数 玩家1 玩家2

空闲

配置棋盘并预计算表格。