artificial-intelligence - 使用AI解决益智游戏

Question

我犯了一个难题，玩家可以将障碍滑向目标-规则非常简单:

一次只能移动一个滑块

目的是将滑块移入目标节点-您只需要填充目标节点，而不必将所有滑块移入目标节点。

如果滑块在冰上滑动，它将继续沿该方向移动，直到停止或移动

如果滑块块碰到了坚固的东西(混凝土，另一个块)，它将停止并且可以再次移动(显然，不能移入具体位置)

如果滑块在木头上滑动，它会停在木头上并且可以移动

如果滑块移动到目标节点上，则无法再移动

该块可以移动某些块，例如，箭头块将那个块推向该方向

有启用“门”的开关块，可以将其打开以打开和关闭这些“门”。

除了可以激活“门”

的按钮块外，其他按钮块的操作与开关类似

当门关闭时，它们的作用就像混凝土一样。当门打开时，它们就像冰一样。

我认为这是涵盖的规则。以下是一些屏幕截图:

在这里，玩家必须移动积木，以便他们必须互相击打才能解决难题。

难题已近解决。注意该区块是如何撞到另一个区块并停止的

这是另一个带有推块机械手的难题:

如果我们将右上方的块向下滑动，则会发生以下情况:

如您所见，该方块在碰到箭头方块时已移至左侧，并停在了木头方块的顶部。

我想写一个可以解决这些难题的AI解决方案-我当时以为这是某种深度优先的搜索，但是我对从哪里开始并不了解。任何实现这一目标的指针都是一件好事!

Answer 1

您的问题是状态空间搜索问题的经典实例。根据您的特定实例的特征，可以使用不同的算法。

无论您的特定实例如何，都需要定义四个组件:

初始状态，您的问题中的初始配置

一个函数，该函数返回从空间的任何状态可到达的所有可能状态，在您遇到的问题中，可到达状态是可移动滑块获得的拼图的所有可能配置。当访问其可达状态时，该状态被称为扩展状态。

一个目标测试，一个确定给定状态是否为目标状态的函数，在您的问题中，您将检查是否所有目标块都已填充，

一个成本函数，它给出从一种状态传递到另一种状态的成本，使您的算法可以选择执行最佳的动作。对于您的情况，我认为您可以为每个操作使用1的恒定值，并搜索要达到目标状态之一的最少操作数。

由于您的问题可以通过这四个部分来定义，因此可以使用以下算法之一解决问题:

Breadth-first search(BFS):我们首先测试初始状态是否为目标状态(显然不是针对非平凡问题)，然后扩展初始状态，测试其每个可达状态，如果不是，则扩展每个这些状态，以此类推...
可以使用队列来实现。

Depth-fisrt search(DFS):从初始状态开始，测试目标，然后扩展邻居状态，测试目标，扩展该状态，等等，直到状态空间的最深层次。
这可以通过堆栈来实现。

要评估哪种算法最合适，我们可以考虑以下因素:

完整性:是否可以保证算法在存在时会找到解决方案？

最优性:该算法可以找到最优解吗？

时间复杂度:需要多长时间？

空间复杂度:需要多少内存？

如果我们考虑BFS策略，我们可以看到它是完整的，因为它系统地逐级探索状态空间，只有当状态深度增加时成本函数不减小时，这才是最优的(这是我们的情况，因为所有动作的费用不变)。现在有个坏消息:假设每个节点的扩展最多可以给出 http://latex.codecogs.com/png.download?b状态，并且第一个解决方案是depth，那么您将需要存储和扩展大多数状态。

对于DFS，我们必须考虑到，当不同的选择可能导致某个解决方案在附近时，它可能会长时间停留在路径中(可能是无限的)。因此，当状态空间为无限时，该算法既不完整也不最优。如果我们将其视为状态空间的最大深度，则空间复杂度最多为，而时间复杂度则保持指数级:。

所以，我们能做些什么？我们可以混合使用这两种策略，并使用 Iterative Deepening depth first search。在此搜索中，我们将迭代运行DFS，将最大深度限制为从0开始到最大深度级别。该方法具有两种搜索策略的优势:空间复杂度，第一个最佳解决方案的深度在哪里，时间(我们不能做得更好)，它是完整的(它将找到解决方案，因为它迭代地探索了所有状态) )，并且由于相同的原因，BFS最佳，因此它是最佳的(假设成本函数不随路径长度的增加而递减)。

参考: Artificial intelligence: a modern approach

注意:很明显，还有其他一些不了解情况的策略，但是正如书中所述，IDDFS是不了解情况的搜索问题的理想选择，因为在这些情况下您没有关于搜索空间的其他信息。有关其他类型的搜索策略(例如知情搜索)，请参考本书，以了解目标状态与当前状态之间的距离。