✋ 👨🏾‍🍳 🛢️ Kaboom：一个不寻常的工匠 ✋🏻 🍨 😍

小时候，我一周三次坐在父亲的工作上一个半小时。我被允许去一台计算机，那里的娱乐场所只有一个工兵和油漆。我厌倦了快速绘制，但是渴望开放整个领域而不是爆炸，促使我寻找玩此游戏的新方法。许多年后，我无意间偶然发现了一篇有趣的文章，内容是关于一个工兵的克隆，无法通过。我建议您熟悉一下它。这是关于Kaboom的发展的故事，Kaboom是传奇的《扫雷》游戏的复制品，带有自己的热情。

《扫雷》是很早以前就以电脑游戏的标准出现的。但是在我看来，大多数人都记得Windows早期版本中的游戏。我从来都不擅长Minesweeper，但有时会演奏。有些人打得更认真。对于那些想要振作起来的人，我建议您观看Minesweeper-The Movie。

理念

最近，我有一个主意：如果您必须在更智能的计算机上玩《扫雷》，该怎么办？

通常，地雷的位置是在游戏开始时确定的（但是这里有一些技巧-例如，因此您不会失去第一次点击的感觉）。但是，如果尚未事先确定地雷的位置，并且游戏可以在游戏开始后选择地雷的位置，该怎么办？

那将是非常残酷的：如果单击可能包含地雷的正方形，它将始终包含地雷！因此，您必须事先证明正方形是安全的。

在上图中，标记有点的单元格中没有地雷，保证带有感叹号的单元格中也没有地雷。问号意味着不确定性：也许，如果您打开更多的单元格，则可以计算是否在其中隐藏了地雷；

另一方面，有些情况下您必须猜测：

在较低的单元格中有一个地雷。但是其中哪一个，是不可能理解的。您必须选择其中之一。但是根据我刚才所说的情况，这将意味着一定的死亡！我本来希望游戏残酷，但现在显然已经输了。
因此，我将稍微改变一下想法。您可以猜测，但前提是没有剩余的安全单元。因此，游戏将是残酷的，但却是公平的。

换一种说法：

, .
, , .
, :
1. , , .
2. , , .

如何实现这样的游戏？我可以尝试计算所有可能的字段，但这是不现实的：即使是很小的10x10字段也意味着2 ^ 100个可能性。仅选择完全包含N min的那些没有帮助。

幸运的是，我不必担心整个领域。我们对与标签不相邻的地雷一无所知。我只对边界上的那些感兴趣，其余的可以很偶然地确定。

然后，我可以根据标签计算边界上地雷位置的所有选项。回溯（backtracking）-一种很好的技术，它使您可以对所有组合进行排序，但是一旦我们确定分支无法计算，它就会迅速撤退。

上图显示了边界处地雷的两个可能位置。结合它们，我们将了解保证哪些单元为空或开采的。

我还需要跟踪地雷的总数。因此，该位置实际上看起来像是“在边界5分钟，在外部5分钟”。这很重要，因为否则我可能会在边界创建太多地雷（或太少！）。

因此，我有所有选择。玩家决定打开笼子时会发生什么？

选择一个随机选项（一个满足“残酷但公平”规则的选项）。这将确定地雷在边界上的位置。
随机散布那些留在边界之外的人。
如果所选单元格中存在地雷，则游戏结束。
除此以外：
1. 为已识别的单元格定义一个新标签
2. 显示为0的其他单元格
3. , ! .

对于小田野，这是正常现象。通常只有几种可能的组合...等等，这是什么？

不好了！

不知何故，我设法解锁了1800万个可能的矿场。我的Firefox吞噬了12 GB的内存，打开一个单元需要半分钟。显然，我需要一个更好的算法。

可能有人会注意到《扫雷》是一款NP完全游戏，因此无法避免呈指数增长的时间。在一般情况下，这是正确的-有些职位需要很多时间才能计算出来。但对于一小部分地区，这是可行的。

我不需要记住所有组合。我什至不需要计算所有组合。所需要的只是一种方法：

检查电池是否安全，危险或模糊，
(, , ).

我将自己使用SAT解算器，而不是亲自尝试这些选项。这些工具采用由逻辑变量组成的公式并查找使该公式为真的一组值。对于我们的任务而言，这是一种虚构但非常有效的方法。SMT求解器是一

类功能更强大的软件，可与更广泛的值和公式一起使用，例如一阶逻辑（量化器），数组，整数等。这将至少帮助定义一些整数的方程式。但是我需要在浏览器中可用的工具。人们设法将一些复杂的工具（例如Z3Prover）移植到浏览器中，但WebAssembly版本的重量很大17 MB，这太多了。

我找到了MiniSat，这是由Joel Galenson为Javascript编译的小型SAT求解器。编译后的文件仅占用200 KB，因此我使用它。

CNF公式

SAT求解器使用合取范式（CNF）。 CNF的公式是“或与”，例如：

(a | ~ b | ~ c) & (c | d ~ e) & f

您可以将句子逻辑的任何公式（变量，也可以不是隐式）转换为CNF，因此它是一种通用格式。

我们怎么用它？假设我们有一个董事会：如果我为未知单元格创建变量（顺时针：x1，x2，x3），它们将必须满足以下方程式：但是如何在CNF中表示“变量之和为2”？我发现了一种方法，正如我后来了解到的那样，它称为“二项式编码”，是最简单的编码。您应该考虑所有可能的变量子集。例如，您需要以下公式：

? ? 1
2 ? 1

1 + 2 + 3 = 2
2 + 3 = 1
2 + 3 = 1 ( )

x1 + x2 + x3 = 2

对于2个变量的每个子集，至少一个为真。这样可以确保金额大于1。
(x1 | x2) & (x1 | x3) & (x2 | x3)
至少一个变量为假。这样可以确保数量少于3。
(~ x1 | ~ x2 | ~ x3)

对x2 + x3 = 1我来说，我需要一组类似的公式：

至少一个变量是正确的： (x2 | x3)
至少一个变量为false (~ x2 | ~ x3)。

结合起来，我得到了6分的CNF公式。在标准DIMACS格式中：所有位置线均以0结尾，并且负号标记为负号。如果将其连接到MiniSat（自己尝试），则会得到：这意味着MiniSat找到了x1和x2为true且x3为false的解决方案。董事会的样子是这样的：整个程序稍微复杂一点：这只是一个解决方案，还有另一个解决方案。因此，要确定x1，x2，x3是否可以为true（或false），则需要发出更多请求。我需要问：“鉴于上述公式以及x1，这可行吗？上面的公式以及〜x1“怎么样？

SAT 1 2 -3

! ! 1
2 . 1

编码意味着我需要找到一组变量的所有可能组合（例如3的所有子集）。但是，对于该方程式，最多只能有8个变量，因此该公式通常足够小，以便MiniSat可以快速求解。

最小追踪

不幸的是，这不是一个完整的解决方案！我仍然需要跟踪剩余的地雷数量。某些组合是不可能的，因为否则您可以创建超出允许范围的地雷，并且将无法获胜。

实际上，相反的情况也是可能的：如果地雷太少，游戏将结束，因为没有东西可放置。

因此，我需要在SAT公式中指出“地雷的数量不少于X并且不超过Y”。起初我以为我可以在所有组合中使用该技巧。不幸的是，它不能很好地处理大量数据。如果有20个单元格和10分钟，那么将数字连接到二项式系数后，我们发现组合的数量已经是6位数字！

因此，我发现还有许多其他方法可以将变量总和编码为SAT公式。您需要创建一个将各个变量组合在一起的架构。例如，参见StackExchange上的此答案或本答案。

最后，我从Olivier Baillot和Yasin Bufhad 撰写的题为“具有布尔基数约束的有效CNF编码”的文章中实现了这一想法。我们看到一棵树，该树递归地添加一元数（或对位进行排序，以便每个人都从头开始）：

在该图的最后，您将获得一组排序的“输出”变量。要确认总和不小于X，请检查结果变量的前X个为1。要声明总和不大于Y，请检查结果变量的最后N-Y为0。

这比使用所有可能的组合要好得多，但是，该方案仍然不合理，因为它会生成句子Ө（N ^ 2）。当开孔数量大约为100时，游戏就会变得迟钝。我们可以进一步优化游戏。
减少请求

在研究问题时，我注意到可以减少对求解器的查询数量。我想确定所有单元的状态（即检查是否保证它们是危险的，安全的）。我使用一个简单的循环来做到这一点。假设董事会由公式F描述：

决定F & ~ x1检查x1是否可以为0
决定F & x1检查x1是否可以为1
决定 F & ~ x2 检查x2是否可以为0
决定F & x2检查x2是否可以为1
等等。

我注意到了什么？如果我得到F＆〜x1的解决方案，它还将包含所有其他变量的值。这已经回答了许多其他问题：如果解决方案包含x2 = 0，那么我不需要询问x2是否可以为0，因为我已经知道这一点。这使我可以将请求数量减少大约2-5倍。

快取

这不能解决由“计数”电路产生的庞大公式的问题。就像我说的那样，句子的数量大约为N ^2。在一个大的例子中，公式最多可以包含10,000个假设。

幸运的是，大多数时候我们知道许多细胞的确切含义。如果保证该单元格为空或保证已填充，则该值永远不会改变！这意味着我们可以缓存它，而不必将其包括在SAT公式中。一旦确定了单元的状态，就不再需要再次将其包括在计算中。只要未定义单元格，就将使用它们。

这种优化有些危险：我们不再有公式来确认整个电路板的正确性。如果其他所有操作均按计划进行，则不会有问题，但是会使错误跟踪复杂化。

另一个案例：在国外玩

您是否可以在该字段的开放区域和未开放区域之间的边界之外单击地图上的任意位置？

最初，我认为这与猜测相同：如果没有安全的储存格，您只需在字段中的任何位置单击即可。但是有些人觉得奇怪，这保证了一个空笼子的打开。

因此，我更改了游戏规则，以便始终惩罚边界外的点击。当然，除了比赛开始之外，因为整个局面都在“外面”。

但事实证明，还有另一种情况：如果所有边界字段都是致命的，该怎么办？您别无选择，只能透露一些其他信息。这种情况会使游戏从一开始就无法通行。因此，现在又有一个例外。在以下情况下，您可以在边界外玩耍：

3 . .
. . .
. . .

该字段未打开
开采的牢房可能位于边界上（在外部单击是安全的），或者
边界上的所有单元中都必须有炸弹（您必须单击外部）。

更新：由于限制有些人为，因此更改引起了争议。我添加了一个允许/禁止在这些条件下玩的开关。

全部

您可以在此处播放Kaboom 。尝试打开调试模式：它使游戏变得微不足道，但是很好地展示了它的工作方式。Github

源代码。他不是很帅。您可能也会对PuTTY的创建者Simon Tatham 的类似游戏感兴趣。它的版本有一个不同的转折：它总是可以解决而无需猜测。明智地玩！在Cloud4Y博客上阅读还有哪些有用的内容 → 银行如何“打破” → 个人隐私？不，他们没有听到 → 雪花大理论 → 虚拟EDGE路由器上的网络连接诊断 →

耐CRISPR-病毒建立庇护所，从DNA穿透酶保护基因组。

订阅我们的电报通道，所以你千万不要错过另一篇文章！我们每周写不超过两次，仅在商务上写。我们提醒您，创业公司可以获得100万卢布。来自Cloud4Y。希望者的条款和条件-在我们的网站上：bit.ly/2sj6dPK

Kaboom：一个不寻常的工匠

理念

CNF公式

最小追踪

快取

另一个案例：在国外玩

全部

More articles: