python - 点和框求解算法

Question

我目前正在开发一个“dots and boxes”程序，其中的输入由计算机自动生成，而我们的输出就是我们要采取的行动。我将与另一位玩家(他们的算法)竞争。

我将点和框板表​​示为 Python 中的矩阵。赢得比赛是重中之重:算法效率不是那么重要。

在给定棋盘的情况下，是否有一个最好的、不复杂的算法来自动确定我们应该采取什么行动？

附言- 如果你愿意，你不需要在代码中给我任何东西......英文算法是完全可以接受的。

Answer 1

我认为 minimax 不是点和框算法的最佳选择。关于这个游戏的完整故事你真的需要阅读这本书 The Dots and Boxes Game: Sophisticated Child's Play by Elwyn R. Berlekamp ，但我会在这里给你一个简短的总结。

Berlekamp 提出了许多有力的意见。第一个是双重交叉策略，我假设您知道(在 Wikipedia page on the game 中有描述)。

第二个是长链的奇偶校验规则。这是基于关于大多数玩得好的游戏的三个事实:

1. 长链将在游戏的最后结束。
2. 除最后一个链外，每个链中都会有一个双叉。
3. 首先必须在任何长链中玩的玩家输掉游戏。

加上您开始的点数加上双叉数等于游戏回合数的限制。所以如果有 16 个点开始，并且有一个双十字，就会有 17 个圈。 (在大多数游戏中，这意味着第一个玩家将获胜。)

这极大地简化了对游戏中期位置的分析。例如，考虑这个局面有 16 个点和 11 步棋(Berlekamp 书中的问题 3.3)。这里最好的一步是什么？

好吧，如果有两条长链，就会有一个双叉，游戏会在另外六步(16 + 1 = 11 + 6)之后结束，走的玩家输。但如果只有一条长链，则不会出现双叉，游戏将在再走五步(16 + 0 = 11 + 5)后结束，先走的玩家获胜。那么要移动的玩家如何保证只有一条长链呢？唯一获胜的一步是牺牲两个盒子:

Minimax 本来可以找到这一着法，但需要做更多的工作。

第三个也是最有力的观察是点和框是一个 impartial game :无论轮到谁下，可用的着法都是相同的，并且在游戏过程中出现的典型位置(即包含盒子的长链)它也是一个 normal game :最后移动的玩家获胜。这些属性的组合意味着可以使用 Sprague–Grundy theory 静态分析位置。

这是一个使用 Berlekamp 书中的图 25 的示例，说明了这种方法的强大之处。

此位置有 33 种可能的走法，一场玩得好的游戏会持续大约 20 步，所以如果 minimax 能够在合理的时间内完成其分析，我会感到惊讶。但是这个位置有一个长链(上半部分六个方格的链)所以它可以静态分析。该位置分为三 block ，其值为 nimbers :

这些数字可以通过动态规划在时间 O(2ⁿ) 中针对剩余 n 步的位置计算出来，您将可能无论如何都想缓存许多常见小位置的结果。

数字使用异或相加:*1 + *4 + *2 = *7。所以唯一获胜的举动(将 nim-sum 减少到 *0 的举动)是将 *4 更改为 *3(因此位置总和为 *1 + *3 + *2 = *0)。三个红色虚线移动中的任何一个都获胜:

---

编辑添加:我知道这个摘要并没有真正构成一个算法，而且还有很多问题没有得到解答。对于某些答案，您可以阅读 Berlekamp 的书。但是在开局时有一点差距:链式计数和 Sprague-Grundy 理论实际上只在中局和残局中实用。对于开头，您需要尝试一些新的东西:如果是我，我很想尝试 Monte Carlo tree search 直到链条可以被计数的程度。这种技术为围棋游戏创造了奇迹，在这里也可能会产生效果。