如何解决“扫雷”（并使它变得更好）

《扫雷》是一款具有简单规则的简单游戏，但是其某些配置带来了一些有趣的困难。 在本文中，我们将创建一个复杂性越来越高的Minesweeper解算器，并思考随着帮助水平的逐步提高，游戏动态如何变化。 最后，我们将开发具有更多有趣游戏玩法的新版本游戏。

本地推理：相邻地雷为零

在原始游戏中 ，使用了一种自动机制：当玩家打开一个单元时，旁边没有地雷，游戏引擎将打开所有相邻的单元。 这不会对游戏造成威胁，因此您可以放心地让计算机来进行游戏，而且情况本身对于玩家是显而易见的，并且不会干扰游戏过程。

这种推理完全是局部的：仅考虑一个单元格信息来决定下一步操作。

如果没有这种自动帮助，很难想象游戏会变得更糟。 尝试玩这样的游戏，以了解在不自动打开单元的情况下该游戏如何进行[在原始文章中，所有示例都是交互式的] ：

基于环境的本地考虑

对于新玩家来说，很容易理解，如果相邻地雷的数量（即单元格中显示的数量）等于未发现的相邻单元格的数量，那么所有这些单元格都必须是地雷，因此您需要在其上标记。 类似地，当相邻地雷的数量等于相邻标志的数量时，其余未发现的相邻单元必须为空。

在这些规则中，考虑了一个单元格以及相邻单元格的状态（打开/选中）。

手动执行这些规则可能很有趣。 如果添加计时器，播放器将开始学习如何快速而准确地应用它们。 这将扫雷器变成了反应游戏 。 如果我们自动执行这些规则会怎样？


这种自动化有一个有趣的副作用-选中该框可能会立即导致致命的后果。

否则，我们可能会遇到可分为三类的情况：

1. 通过应用自动规则完全解决了游戏
2. 复杂情况需要更多单元格进行推理
3. 游戏中没有逻辑前进方式的状态-玩家只能偶然地选择，可能要考虑到概率。

情况1看起来很美，但是如果它出现得太频繁，就不会特别有趣。 如果没有自动解决方案，这样的游戏会更好吗？ 也许不是； 即使手动解决，这种游戏也非常简单，并且玩家对玩没有困难的游戏并不特别感兴趣。 当然，尽管在反应游戏中总是有困难：您需要尽快行动。

情况2对我来说似乎很有吸引力，我们将精力更多地放在解决逻辑条件上，减少精确瞄准和按下正确按钮的时间。 这使Sapper更像是一个积极的难题 。

情况3完全破坏了所有乐趣。 但是，我听说有些人喜欢随机玩游戏 。

是否可以摆脱情况3？

完整的解决方案：全局推理

为了对游戏状态所必需的所有逻辑条件进行算法检测，我们需要对游戏的所有状态进行详尽的搜索。 扫雷机被证明是完成NP的任务 。 以下是游戏状态的一个小但有趣且说明性的示例，只有一个逻辑解决方案，但是要找到它，您必须考虑整个游戏状态：


是否可以搜索游戏的整个状态空间？ s状态存在多少种变化？

鉴于：

w =场宽

h =场高

k =分钟数

n = w

则可能的状态数s为

$$

$$s = \开始{pmatrix} n \\ k \结束{pmatrix}$$

对于“初级”，“业余”和“专业”标准级别，这使我们：

$$

$$s_b = \开始{pmatrix} 8 * 8 \\ 10 \结束{pmatrix} = 151473214816$$

$$

$$s_i = \开始{pmatrix} 16 * 16 \\ 40 \结束{pmatrix} = 1.050 * 10 ^ {47}$$

$$

$$s_e = \开始{pmatrix} 30 * 16 \\ 99 \结束{pmatrix} = 5.602 * 10 ^ {104}$$

我们知道，幼稚的方法在这里完全不合适。 让我们看看一个朴素的算法看起来如何，并找出它是否可以优化为可行的算法。

天真的算法

该算法的任务是找到给定字段状态所需的所有逻辑条件。 通过仔细考虑解决方案很难实现这一目标； 计算机在快速执行一系列愚蠢的动作方面做得更好。

我们可以做什么“愚蠢的”：为所有剩余的地雷生成所有可能的地雷位置排列。 如果这样的排列对应于所有开放数字，那么它将是游戏的正确解决方案。 然后，我们研究所有可能的排列，找到所有可能的解决方案，但仍然不知道哪个是正确的。

如果在所有可能的解决方案中，在开放单元之间或标记为地雷的单元之间存在某些共同点，那么我们可以理解，这一共同点应该是当前领域正确决策的一部分。 而且实际上：不可能创建没有此类匹配元素的正确解决方案，否则我们会发现它们。

因此，我们可以找到该字段当前状态所需的所有逻辑条件。

有和没有限制的单元

上面的算法有一个明显的问题：需要研究的状态数。 但并非所有单元格都相同。 编号旁边的未打开的单元格显然限于该编号。 我们将这些单元称为有限单元。 其余的单元格我们将称为无限。

如果我们实现上述算法，但是我们只会在受限单元格的状态空间中进行搜索，而一旦打破限制，我们将立即返回，那么在许多游戏中，我们都可以在合理的时间内解决所有逻辑条件：


对于无限的单元，我们无法找出地雷的位置，因此从逻辑上我们会立即知道。 这意味着您可以将它们从计算中排除，而仅考虑露天号码旁边的地雷位置。

但是，我们知道一定数量的地雷可以进入许多无限的地雷。 如果有6分钟的限制单元格和4个限制单元格，则在有限的单元格中最多可以有4个地雷，也就是说，在无限的单元格中至少必须有2分钟。 按照相同的逻辑，有时我们可以确定所有无限单元都必须为空或都包含地雷。

在下面显示的情况下，我们知道所有地雷的位置，因此AI应该能够理解剩余的单元未被占用：


在以下情况下，我们不知道所有地雷的位置，但是我们可以理解，剩余的地雷必须放在左上角的两个单元之一中。 这意味着右下角剩余的单元格是空闲的：

随机版本

如果我们自动运行全局求解器，我们将获得随机优化的Minesweeper版本：


您可以将此版本中的游戏分为三类：

1. 玩家做出任意选择并获胜的游戏。
2. 玩家做出任意选择并输掉的游戏。
3. AI需要大量时间的游戏，玩家实际上可以使用推理。

显然，这是一个机会游戏。 这种游戏的吸引力是什么？ 在逻辑上，上面显示的游戏与此类似：


但是哪个随机游戏更好？ 似乎其他具有随机性的游戏的意义在于玩家的行为与赢/输之间存在复杂的关系。 为了抽奖，使用了复杂的机器，这些机器并不急于选择一个数字并通过显示该数字来进行整体展示。

也许自动决定的一个大领域是一个很好的游戏
假设玩家正在注视着所有单元的逐渐开放。

我们可以提出其他类型的游戏吗？

确定性版本

现在，我们有了一个能够从给定游戏状态确定所有逻辑步骤的AI。 有时他将无法找到合乎逻辑的步骤。 在这种情况下，玩家必须猜测，如果他不幸运，他可能会输。

如果我们添加另一个规则怎么办？ 如果游戏没有合理的前进方向，那么我们可以寻求帮助。 如果AI同意玩家无能为力，那么他会助您一臂之力。 否则，玩家立即输。 这可能很有趣。 这可以提供什么帮助？ 也许您需要打开一个单元，无论其中是否存在地雷：


因此，我们完全摆脱了可能会偶然失去的情况。

但是，有一个例外：仍然存在退化情况，即全局求解器无法在合理的时间内完成计算。 不幸的是，这是Minesweeper任务完成NP的必然结果。

“寻求帮助”按钮如何影响游戏玩法？ 这导致了一个事实，即游戏更多地关注逻辑。 这是“扫雷”的最“令人困惑”版本。 有人可能认为游戏会变得更容易，但实际上它变得越来越复杂。 现在没有任何错误可辩解，如果他错过了某件事，按钮会惩罚他。 没有按钮，很容易得出结论，您已经用尽了所有逻辑上的可能性，并且事件发展的唯一选择是尝试随机猜测。 但是由于按钮的存在，玩家在评估中必须正确。

总结

实施了完整的求解器“扫雷器”求解器后，我们可以创建游戏的一个变体，而不受诅咒的影响：现在，由于几乎要决定整个领域而必须偶然选择，因此不可能输掉。 这个版本与原始游戏的区别仅在于您需要随机猜测的那一刻，因此我可以认为它比原始游戏有趣得多。

此外，我们开发了一个游戏版本，可以自动解决简单的本地规则。 是否使用这种帮助由您决定。 它将游戏的重点从机械点击转变为更加令人困惑的游戏玩法。 同时，没有必要使用“寻求帮助”按钮提供的游戏性增强功能。