Solving the board game Quoridor
a day ago
- 该文章提出了一种新颖的技术，在使用普通笔记本电脑的情况下，能够解决几乎所有面积≤28（如5x5、8x3、7x4）的Quoridor棋盘配置中大多数墙体数量的情况。
- 主要结果包括：奇数高度的棋盘并非总是后手获胜（在墙体充足时变为先手获胜），偶数高度的棋盘一致为先手获胜，并且存在强制平局（例如8x3棋盘带3堵墙）。
- 游戏的复杂性源于规则禁止墙体完全阻挡棋子的目标路径，导致高分支因子和评估困难；作者采用位棋盘（bitboards）、置换表和墙体合法性启发式优化。
- 一项突破性优化预先计算了所有可能的墙体配置（5x5棋盘达250万种）和合法性位棋盘，从而实现了廉价的合法性检查，并在数分钟内解决了5x5棋盘。
- 作者通过修改带迭代加深和(0,∞)alpha-beta边界的negamax算法，意外地重新发明了证明数搜索（proof-number search），并提出了未来工作方向，例如枚举墙体前沿或分治瓷砖。