点和盒子问题的解决算法

Question

我目前正在开发一个 "dots and boxes" 程序，其中输入由计算机自动生成，我们的输出是我们将要采取的动作。我将与另一个玩家（他们的算法）竞争。

我在 Python 中使用矩阵表示点和框棋盘。赢得比赛是最重要的：算法效率并不那么重要。

是否有一种最佳、不复杂的算法，可以自动找出给定棋盘应该采取的动作?

P.S. - 如果你愿意，你不需要用代码给我任何东西...英文算法完全可以接受。

- Casey Patton

Answer 1

我认为极小化极大算法不是点格棋游戏的最佳选择。如果你真的想了解这个游戏的全部故事，你需要阅读 Elwyn R. Berlekamp 的书 The Dots and Boxes Game: Sophisticated Child's Play，但我会在这里给你一个简要的概述。

Berlekamp 提出了一些有力的观察结果。第一个是 双重交叉策略，我假设你已经知道了（它在 Wikipedia 上的游戏页面 中有描述）。

第二个是关于长链的 奇偶规则。这是从关于绝大多数精彩比赛的三个事实中得出的：

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ⁿ)内计算出来，您可能希望为许多常见的小位置缓存结果。

Nimbers使用异或进行加法：*1 + *4 + *2 = *7。因此，唯一的获胜策略（将nim-sum减少到*0的策略）是将*4更改为*3（使得位置总和为*1 + *3 + *2 = *0）。其中任何一个三个点的红色移动都是获胜的。

---

编辑补充：我知道这个总结并不真正构成一个算法，并且留下了很多问题。对于其中的一些答案，您可以阅读Berlekamp的书。但是在开局时有点困难：链计数和Sprague-Grundy理论在中盘和结束时才实际可行。对于开局，您需要尝试一些新的东西：如果是我，我会尝试使用蒙特卡罗树搜索直到可以计算出链的数量。这种技术在围棋游戏中效果非常好，这里也可能会有所收获。

- Gareth Rees

---

+1 为回答问题点赞。非常好的回答。我只在和表弟玩的时候遇到过双重交叉符号。 - gbulmer

这个答案太棒了。有很多很多东西需要我学习。维基百科，我来啦宝贝。 - narengi

不错。这个网站还有一些关于点与方格游戏策略以及与组合博弈理论的关系的有用信息：**http://wccanard.wetpaint.com/** - ypercubeᵀᴹ

斯普雷格-格伦迪理论在这里不适用，因为在点与方格游戏中，玩家通过获得最高分数来获胜。如果最后一个移动的玩家得分低于对手的得分，则他将输掉比赛。 - angelvet

@angelvet：请看我的回答中的“第三个观察”，其中解释了大多数Dots and Boxes位置都有长链，因此是“正常”的，这意味着最后一个玩家获胜。这就是为什么Sprague-Grundy理论适用于这些位置的原因。 - Gareth Rees

Answer 2

我认为Gareth在上面的回答非常好，但是补充一下（我没有足够的声望来添加评论），点与盒子已经被证明是np-hard的（至少有一个草图）, 参考这篇文章: arxiv.org/pdf/cs/0106019v2.pdf

我编写了一个JavaScript版本的点与盒子游戏，试图将上面提到的策略结合起来 dotsandboxes.org。虽然它不是可用的最佳版本（尚未包含Gareth提到的所有技巧），但图形很好，而且它可以打败大多数人类和其他实现 :) 欢迎查看代码，也有一些其他人版本的游戏，你可以用来训练自己的技能。

- Ossie

Answer 3

这个游戏是零和博弈，因此我建议使用极小极大算法。这个算法被深蓝用来在国际象棋中击败卡斯帕罗夫。

创建你的启发式函数，评估每个游戏状态，并将其用作极小极大算法的评估函数。

你还可以通过使用Alpha-Beta剪枝来改进极小极大算法。

极小极大算法的思想是彻底搜索所有可能的移动 [通常是一定深度内，因为需要遍历的状态数与深度呈指数关系]，并选择最佳移动，假设对手也会做出他最好的可能移动。 p.s.

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

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

- amit

---

这是一个很好的建议，但对于我的项目来说似乎太复杂了。 - Casey Patton

@CaseyPatton：如果没有已知的启发式算法可以完美地指导最佳游戏策略，那么你肯定会输给一个能够执行此操作的程序，即使是通过暴力搜索也需要这样做。 - ninjagecko

@CaseyPatton：这是几乎所有零和游戏中最好且最常用的算法。现今代理程序之间的区别在于所使用的启发式方法，而不是是否使用该算法。此外，我相信你可以在网上找到一个现有的Python实现，而且实现min-max算法也并不难。 - amit

@CaseyPatton听起来很复杂，但实际上可以很简单。你只需要一个函数来评估你在给定游戏配置中的位置。它可以是你拥有的方块数减去对手方块数的差。然后从你的位置建立可能的移动，并计算最大化你位置质量的路径。然后选择这条路径。一旦你有了一个简单的实现，你应该尝试改进状态评估函数，并尝试优化你的树以避免计算无用的路径。 - Simon Bergot

这个答案好像没有代码可以复制粘贴，为什么它在最上面？ - user37309