游戏解决算法（Buttonia，灯泡变体）

Question

游戏解决算法（Buttonia，灯泡变体）

algorithmmathxorsolver

6

我正在尝试创建一个游戏算法的可解性函数。基本上，这个函数会针对给定的游戏返回true或false，判断它是否可以被解决。

这个游戏是Buttonia.com（目前还没有实现该算法），一种类似熄灯游戏的游戏。你有一个按钮网格，每次按下一个按钮都会改变一些相邻按钮的状态。目前，我生成一个随机的游戏配置，然后尽可能地应用启发式方法。其余的则通过暴力搜索来解决。

到目前为止，我的进展是创建了一组方程来模拟游戏。由于每个按钮需要改变奇数次状态才能最终处于关闭状态，因此它的方程式如下：

button_A = 1 - (button_1 + button_2 + ... + button_X) % 2

其中，button_1到button_X是对button_A产生影响的按钮状态。如果有些按钮不依赖于其他按钮，则可以立即解决它们。对于剩下的情况，我会尝试一种配置，直到出现冲突，然后回溯。

目前，这个算法适用于较小的游戏配置。我已经测试了从3x3游戏到10x10大小的游戏。其中6x6是实际游戏的上限。

这些方程式大大减少了暴力搜索的范围，使其变得实用。可能有一种纯数学方法来解决这个方程组。

以下是使用ASCII字符展示的3x3游戏（来自buttonia.com/?game=2964）：

||#
-o-
+#|

Legend:
o = affect only self
- = affect left and right neighbors
| = affect above and below neighbors
+ = affect left, right, above and below neighbors
# = affect all 8 surrounding neighbors

解决方案，按照以下顺序点击: (0,0), (2,0), (1,2), (0,1), (1,1), (2,1)

这个游戏的方程式:

Button_0_0 = 1 - (0) % 2
Button_1_0 = 1 - (Button_2_0) % 2
Button_2_0 = 1 - (0) % 2
Button_0_1 = 1 - (Button_0_0 + Button_0_2 + Button_1_2) % 2
Button_1_1 = 1 - (Button_1_0 + Button_2_0 + Button_0_1 + Button_2_1 + Button_1_2) % 2
Button_2_1 = 1 - (Button_2_0 + Button_1_2 + Button_2_2) % 2
Button_0_2 = 1 - (Button_1_2) % 2
Button_1_2 = 1 - (Button_0_2) % 2
Button_2_2 = 1 - (Button_1_2) % 2

可能的解决方案：

改变数学函数以避免需要模数，让我们能够将左侧的项移到右侧，创建我们需要使用高斯方法的整洁矩阵设置。因此，前两个方程式分别转换为：

-1 = -1*B00 +  0*B10 +  0*B20 +  0*B01 +  0*B11 +  0*B21 +  0*B02 +  0*B12 +  0*B22
-1 =  0*B00 + -1*B10 + -1*B20 +  0*B01 +  0*B11 +  0*B21 +  0*B02 +  0*B12 +  0*B22

在这里讨论了解决方案：使用自定义运算符的高斯消元

接近成功。几乎可以发布完整的解决方案：翻转二进制网络

- Killroy

2

我是不是唯一一个觉得这个地址听起来像色情网站的人？=] - Ed James

我敢打赌，一些Perl大师可以用正则表达式解决这个问题xD。 - fortran

1

说实话，那个游戏挺有趣的，但你需要在顶部加上一些解释文字，我花了一两分钟才弄清楚该怎么做！=D - Ed James

很快它将被替换为只显示可解游戏的版本。可解性算法是实用的。这是一个理论问题，关于如何“正确地”解决它，而不需要搜索。 - Killroy

5个回答

2

与其从一个随机状态开始，不如通过翻转随机开关来生成起始位置，即从已解决的状态向后推导出起始状态。这样你只会生成可解的拼图。

- Matt Howells

我所说的随机状态是指随机游戏。起始状态始终为所有按钮都处于未按下状态，目标状态始终为所有按钮都处于按下状态。由于状态是对称的，因此从全部未按下或全部按下开始并没有区别。解决方案始终是一个位图（开/关地图），其中显示哪些按钮需要按下，哪些不需要。 - Killroy

1

我明白了，所以你只是想确定一个给定的NxM网格是否可解？ - Matt Howells

是的。恰巧，我的当前可解算法也会返回解决方案。基本上我想确保我只向玩家呈现可解的游戏。 - Killroy

1

这看起来几乎像一组线性方程（除了模2），因此您可能可以适应解决这些方程的常规技术之一，例如在矩阵形式中对系统进行行约简 (维基百科)。

- Jon

谢谢，我会看看这些的。问题在于取模运算！也许我可以以某种方式消除它，但我不知道怎么做。 - Killroy

0

假设您建立了一个方程系统并尽力解决了它们，但某些行在方程的左侧全部为0（我将方程表示为增广矩阵）。假设您尝试在Z2环中解决该系统（在这种特定情况下，实际上意味着唯一的变化是1 + 1 = 0，否则一切保持不变...因此我们需要的唯一运算符是XOR），并最终得到以下矩阵：

正如您在此示例中所看到的，第4行全部为0，这意味着我们没有得到答案。但是请这样考虑：全0的一行意味着该变量不会影响解决方案。那实际上这是一个不好的措辞...它只是意味着它们可以有任何值（而且我们很幸运，因为所有值都表示1或0，不像实数...所以这意味着我们对于这个系统有2个解决方案）。

原因在于：您需要知道的是，在此时右侧的列仍然包含您游戏的有效解决方案。让我们以第一行为例。它说

button_0 + button_3 = 1

但我们知道按钮3可以是任何东西（因为第3行都是0）。此时，按钮3为0（第3行最右侧的列此时为0），因此我们现在知道它的含义是：

button_0 + 0 = 1

我们知道button_0的值为1。因此，在这个系统中，即使我们无法直接找到button_3的值，我们仍然有一个有效的解决方案。

上面生成的矩阵足以检查可解性。如果一行包含所有的0，则基本上是在说

nothing = nothing

或者，为了更好地理解为什么这样可以工作，

0x = 0

这是有道理的，系统仍然有效。但是，如果我们遇到一行除了最右边的位以外都是0的情况，即

0000 1

那就是说

0x = 1

这是不可能的，因此我们现在知道系统无法解决，因为我们无法解决这种不可能的情况。

因此，简而言之，尽力解决方程，如果您无法准确找出某些变量是什么，也不用担心，只要您在任何时候都没有遇到我刚提到的不可能行，则游戏是可解的。

但是，如果我们想要系统的最短解决方案呢？在这里，我们必须检查所有可能的解决方案。我们有一个可以是任何值的button_3，这意味着第3列中的任何1都意味着包含它的行受button_3的影响。所以假设我们想要检查使用button_3的解决方案是否更短。我们创建另一个矩阵，但现在将button_3设置为1（因为我们早先已经确定它可以是任何东西，并且我们已经有了一个0，所以现在我们检查1）。我们现在得到以下矩阵：

我们尽可能地减少了它，现在得到了这个矩阵：

这仍然是一个有效的解决方案，但我们可以看到该解决方案更长（需要3次按键而不是2次），因此我们将其丢弃。我们必须对找到的每个将行设置为全部为0的排列执行此操作。因此，如果我们有x行都是0，则系统有x^2个解，并且我们必须检查所有这些解。

- Cedric Mamo

0

由于这不是一个有时间限制的问题（假设它可以在一天内完成），我可能会选择深度受限的广度优先搜索，对每个可能的移动进行一次搜索，然后对每个移动后继续进行搜索。

虽然速度较慢，但几乎可以保证找到答案，如果有的话！

- Ed James

这是可以解决的。我甚至有广泛的统计数据支持它。我的当前实现可以在Javascript下的Chrome 3中找到一个可解决的6x6，平均约为400ms，最长时间为1300ms。问题在于该算法无法很好地扩展到更大的游戏配置。一个真正的算术解决方案可能会更好！ - Killroy

好的，如果您打算使搜索空间更大，那么它将无法很好地进行扩展，我同意。回答有效地被撤回了 =] - Ed James

此外，由于每当玩家想要玩新游戏时都需要解决这个问题，因此时间非常紧迫，而他们正在等待。而且这可能会发生在资源受限的设备上，比如手机。 - Killroy

1

这真的是个问题吗？为什么不在服务器端构建一个大型的已知可解谜题库，然后把它们分发出去呢？如果你随机分配它们，并且库足够庞大，则可以有效地记忆求解器的任务。这将完全避免在客户端中运行javascript求解器的需要。 - ire_and_curses

1

哦，我以为游戏每天只更换一次，我的错！不过我同意Ire的想法，预解决的谜题会很有意义。如果你可以在15秒内解决一个谜题，那么你可以快速建立一个库，并且将它们存储在某种矩阵格式中也很容易。 - Ed James

显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- starblue · Accepted Answer

这是一个在F₂上的线性方程组，它包含两个元素0和1。

您可以像解普通线性方程组一样解决它，但必须进行模2运算。

编辑：对于这种情况，线性代数的工作方式与实数完全相同，只需要替换操作：

- 加法和减法变为异或，即0 + 0 = 0，0 + 1 = 1，1 + 1 = 0。 - 乘法变为AND：0 * 0 = 0，0 * 1 = 0，1 * 1 = 1。 - 只能除以1。

方程中的所有系数和未知数的可能值都是0或1。

因此，模数不是像您写的那样附加在方程组外面，而是隐含在操作中。

如果您的方程组无解，则会得到一个方程0 = 1，显然无解。