6

我正在尝试为游戏算法创建一个可解性函数。基本上是一个函数，它为给定的游戏返回真或假，如果它是可解的。

该游戏是 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

此处讨论的解决方案：使用自定义运算符的高斯消除

越来越近。几乎准备好发布完整的解决方案：反转二进制网络

4

5 回答 5

4

这是一个关于 F 2的线性方程组，该场包含两个元素 0 和 1。

你可以像正常线性方程一样求解它，但你必须做算术模 2。

编辑： 这种情况下的线性代数的工作原理与实数完全相同，只是您必须替换操作：

  • 加减法变为异或，即 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0。

  • 乘法变为 AND：0 * 0 = 0, 0 * 1 = 0, 1 * 1 = 1

  • 只能除以一：0 / 1 = 0, 1 / 1 = 1。

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

所以模不是像你写的那样在方程的外部拍打，它隐含在运算中。

如果你的方程组不可解，你会得到一个方程 0 = 1，这显然是不可解的。

于 2009-07-31T10:33:48.067 回答
2

与其从随机状态开始，为什么不通过翻转随机开关来生成起始位置，即从已解决的状态向后工作到起始状态。这样你只能生成可解决的谜题。

于 2009-07-31T09:36:19.227 回答
1

这看起来几乎像一个线性方程组（除了 mod 2），因此您可能能够采用一种常规技术来解决这些问题 - 例如矩阵形式的系统行缩减（维基百科）。

于 2009-07-31T10:40:30.707 回答
0

由于这不是一个有时间限制的问题（好吧，假设它可以在不到一天的时间内完成），我可能会进行深度有限的广度优先搜索，将每个可能的移动放在一个级别上，然后每个移动从每一步开始。

它会很慢，但是几乎可以保证找到答案，如果有的话！

于 2009-07-31T10:36:22.040 回答
0

假设您构建了一个方程组并尽可能地求解它们，但有些行在方程的左侧最终全为 0（我将方程表示为增广矩阵）假设您试图求解系统在 Z2 环中（实际上，对于这个特定示例，这意味着唯一的变化是 1+1=0，否则一切都保持不变......我们需要的唯一运算符是 XOR）并最终得到以下矩阵：

1001 1
0100 1
0011 0
0000 0

正如您在此示例中看到的，第 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）。我们现在最终得到以下矩阵：

1001 1
0100 1
0011 0
0001 1

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

1000 0
0100 1
0010 1
0001 1

这仍然是一个有效的解决方案，但是我们可以看到解决方案更长（需要 3 次，而不是 2 次按钮按下），因此我们将其丢弃。对于将找到的所有行设置为全 0 到 1 的每个排列，我们都必须这样做。因此，如果我们有 x 行全为 0，那么系统就有 x^2 个解，我们必须检查所有这些。

于 2012-11-08T22:28:16.867 回答