python - 点和框求解算法

Question

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

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

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

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

Answer 1

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

Berlekamp 提出了许多有力的意见。第一个是双重交叉策略，我假设你知道（它在游戏的维基百科页面中有描述）。

二是长链奇偶校验规则。这是从大多数出色游戏的三个事实得出的：

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

加上你开始的点数加上双叉的数量等于游戏中的回合数的限制。所以如果开始有十六个点，并且有一个双十字，那么就会有十七个回合。（在大多数游戏中，这意味着第一个玩家将获胜。）

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

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

Minimax 会发现这一举措，但需要做更多的工作。

第三个也是最有力的观察是点和盒子是一种不偏不倚的游戏：无论轮到谁玩，以及在游戏过程中出现的典型位置（即包含长链的位置），可用的移动都是相同的盒子）这也是一个正常的游戏：最后移动的玩家获胜。这些属性的组合意味着可以使用Sprague-Grundy 理论静态分析位置。

下面是一个使用 Berlekamp 书中的图 25 来说明这种方法的强大功能的示例。

在这个位置有 33 种可能的移动，一个玩得好的游戏会持续大约 20 多个移动，所以如果 minimax 在合理的时间内完成分析是可行的，我会感到惊讶。但是该位置有一个长链（上半部分的六个正方形链），因此可以静态分析。该位置分为三个部分，其值为nimbers：

对于剩余n步的位置，可以通过动态规划在时间 O(2 ⁿ )中计算这些 nimber ，并且无论如何您可能希望缓存许多常见小位置的结果。

Nimbers 使用异或相加：*1 + *4 + *2 = *7。因此，唯一获胜的举动（将 nim-sum 减少到 *0 的举动）是将 *4 更改为 *3（因此头寸总和为 *1 + *3 + *2 = *0）。三个虚线红色动作中的任何一个都会获胜：

---

编辑补充：我知道这个总结并没有真正构成这样的算法，并且留下了很多没有答案的问题。对于一些答案，您可以阅读 Berlekamp 的书。但在开局方面有一点差距：链数和斯普拉格-格兰迪理论实际上只在中局和残局中实用。对于开幕式，你需要尝试一些新的东西：如果是我，我很想尝试蒙特卡洛树搜索，直到可以数出链条。这种技术为围棋游戏创造了奇迹，在这里也可能很有成效。

Answer 2

我认为Gareth上面的答案非常好，但只是补充一下（我没有任何声誉可以添加评论），根据以下内容，点和框（至少通过草图）被证明是 np-hard： arxiv。 org/pdf/cs/0106019v2.pdf

我写了一个 javascript 版本的点和框，试图结合上面提到的策略dotsandboxes.org。它不是最好的（尚未包含 Gareth 提到的所有技术），但图形很好，它击败了大多数人类和其他实现 :) 随意查看代码，还有其他一些其他链接人民版的游戏，你可以训练你的。

Answer 3

这个游戏是零和游戏，所以我建议使用min-max 算法。深蓝使用该算法在国际象棋中赢得卡斯帕罗夫。

创建您的启发式函数，它评估游戏的每个状态，并将其用作 min-max 算法的评估函数。

您还可以通过使用alpha-beta prunning来提高 min-max 。

min-max 的想法是彻底搜索所有可能的移动[通常到一定深度，因为你需要经过的状态在深度的数量上是指数级的]，并选择最好的移动，假设你的对手也要去做出他最好的举动。

ps

赢得比赛是重中之重：算法效率并不那么重要。

它们紧密相连，因为您的算法越高效，您将能够检查可能的解决方案，以获得更好的深度，并且您获胜的机会就越大。请注意，在无限时间的情况下，您可以探索整个游戏树并从每个游戏状态中提出获胜策略。然而——探索整个游戏树可能是不现实的。