游戏解决算法(Buttonia,熄灯变体)

StackOverflow https://stackoverflow.com/questions/1211560

  •  06-07-2019
  •  | 
  •  

题

我试图创造一个有解功能的一个游戏，算法。基本上是一个函数，返回真正的或假定游戏，如果它是可以解决的或没有。

游戏是Buttonia.com (它并不实施的算法为然)，一种类型的灯出游戏。基本上你有一个网格按钮，其中每一个被按下时，将改变的状态，它的一些邻居。目前，我产生一个随机的游戏结构，然后申请启发式尽可能的。其余的是决定由的暴力行搜索。

我迄今为止取得的进展是建立一个系统的方程式模型的游戏。因为每个按钮需要改变态一个奇怪的次数在下降状态，这是公式将是这样的：

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

在button_1通过button_X是国家的按钮与影响button_A.一些按钮可以立即得到解决，如果他们不是依赖他人。对于剩下的，我尝试一种配置，直到我得到一个冲突，然后返回轨道。

目前这个算法的实用对于较小的配置的游戏。我已经测试了其从3x3游戏到尺寸的10×10。其中6×6是附近的一个上限，为实际发挥。

方程大大削减的搜索空间的暴力，使它实际的。有可能是一个纯粹的数学的方式解决系统的方程式。

样品3x3游戏在ascii码(从 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

所讨论的解决方案： 高斯消除与运营商定义

越来越近。几乎准备好后完全解决方案： 反二进制网络

有帮助吗？

解决方案

这是一个系统的线性方程超过F2, ，该段包含两个要素0和1。

你能解决它就像正常的线性等式，但你必须做的算术运算模2.

编辑： 线性代数为这种情况下作品完全一样真实的数字，除了，你得替代行动：

  • 加法和减法成为独家或者，即0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0.

  • 乘变，并且：0 * 0 = 0, 0 * 1 = 0, 1 * 1 = 1

  • 司只能通过一：0 / 1 = 0, 1 / 1 = 1.

所有的系数，在你的公式和可能的价值观的未知数是0或1。

所以模是不是拍拍外的方程式喜欢你写的，它是隐含在业务。

如果你的系统的方程是无解的你会得到一个公式0=1，这是显然不可以解决的。

其他提示

不是以随机状态开始，而是为什么不通过翻转随机开关来产生起始位置，即从解决状态向后工作到起始状态。这样你只会产生可解决的谜题。

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

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

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

假设您构建了一个方程组并尽可能地解决它们，但是某些行最终得到了等式左边的所有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个解决方案，我们必须检查所有这些。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top