在益智游戏中检测“没有更多动作”

Question

我在Flash中写了一个小游戏，现在我正在用C＃编写新编程经验进行重新编码。然而，这一次，我希望能够实现检测电网何时不可能解决的想法。这更像是一个概念性的难题，然后我会采取任何你可能拥有的资源。

游戏包括在地图周围向上，向下，向左或向右移动玩家，并推动周围的街区。当没有更多的某些种类的块时，该级别获胜。然而，很容易发现自己处于一个不再可解的地图中。例如，如果玩家开始陷入一圈墙块，那么根本无法解决这个问题。

对不起，抽象的问题，但有没有人有任何提示呢？

Answer 1

你基本上有两种选择。两者都有优点和缺点，因此您可能希望将两者的想法结合到您的解决方案中。

选项1：写一个启发式

想一想其使游戏不可能解决的情况下（如被卡在壁块的环）。检测到这种情况，并在发生这种情况时立即打印出“不再采取行动”。您可以考虑和实施的情境越多，算法就越好。

优点：方便快捷。

缺点：有些情况下游戏无法解决，但你的算法没有检测到它。

选项2：写求解

写，以你的游戏的状态程序（其中是玩家，这里是块等），输出的步骤列表可以采取解决游戏（或null或一些其他特殊的价值，当没有解决方案了 - 这是你的“没有更多的举动”的情况下）。

如何实现这样的事情取决于游戏的确切规则。一个简单的方法是在Game Tree上执行Breadth-First Search：树中的每个节点都是一个游戏状态，节点之间的每个弧线都是玩家可能采取的动作（向上移动，向下移动等）。

优点：这可以可靠地检测游戏何时不能再赢。另外，这个程序可以用来在玩家卡住时给玩家提示。

缺点：根据游戏的复杂程度，计算解决方案可能需要很长时间。对于非常简单的游戏，这可以工作;对于一些简单的游戏来说，这可能需要很长的时间，对于比较复杂的游戏，例如国际象棋或跳棋，这是非常困难或不可能的。

Answer 2

对于任何情况总是有蛮力的方式 - 只需制作玩家可以制作的整个移动树。如果他们中的任何一个都不能赢，那么这场比赛是不可能赢的。

当然，对于像纸牌游戏这样的游戏，您应该只考虑用户所知道的内容，而不是游戏中的任何隐藏元素 - 一些纸牌游戏根本不可能开始，但玩家不应该知道这一点。对于其他更复杂的游戏，蛮力并不合适，因为树需要很长的时间才能生成。在这些情况下，您需要找到常见模式并检测这些模式。

对不起，这对于任何特定的答案都有点太模糊。但这些是我的提示。

Answer 3

您收到关于查找游戏是否可解的答案，但是，在我看来，您只是想查看是否有任何法律动作离开了，这更容易。

当然，没有关于游戏的描述，不可能给你任何具体的建议，但只要拿@ Heinzi的建议，记住你只是想看看是否有任何合法的举动。所以如果你真的可以建立一个非空的Game Tree，那么还有一些合法的举动。

Answer 4

我需要类似的一次。我做了一个随机生成的迷宫，需要知道是否有可能解决它...

我做了一个测试，测试所有可能的解决方案。游戏区域（2D）的大小为10 * 14，玩家可以在4个方向上移动（如在游戏中）。我的游戏就是从A点到B点。从某种角度来说，你的游戏大致相同，它将把块从A点移动到B点。我将从块的当前位置开始，然后制作一个算法尝试在每个方向上移动它。如果任何方向可能的块我会添加瓷砖（谁我试图移动块）到一个列表包含所有尚未测试的瓷砖，需要测试...

因此，基本上从一个瓷砖开始...测试4个方向......然后测试可能移动到的瓷砖。因此，如果可以将块移到右侧，那么您需要测试是否可以将块从块移到右侧到其他位置。要跟踪您测试过的图块，在图块中添加一个变量，告诉它是否进行了测试，以及“可能到达”且尚未测试的图块列表。