使用AI解决益智游戏

Question

我已经做了一个谜题,玩家滑动到目标 - 规则相当简单:

1. 一次只能移动一个滑块
2. 目标是将滑块移动到目标节点 - 您只需要填充目标节点,而不必将所有滑块块放入目标节点.
3. 如果滑块在冰上滑动,它将继续沿该方向移动,直到它停止或移动
4. 如果滑块遇到坚固的东西(混凝土,另一个块)它会停止并且可以再次移动(显然不是进入混凝土)
5. 如果滑块滑到木头上,它会停在木头上并可以移动
6. 如果滑块滑动到目标节点上,则无法再移动它
7. 块可以通过某些块移动,例如,箭头块在该方向上推动块
8. 有一些开关块可以启用"门",可以移动到门上以打开和关闭这些"门"
9. 按钮块的操作类似于开关,除了它们必须有一个块以激活"门"
10. 当门关闭时,它们就像混凝土一样.当门打开时,它们就像冰一样.

我认为这是规则所涵盖的.以下是一些截图:

在这里玩家必须移动块,以便他们必须互相击打以解决难题.

其中的难题是近乎解决的状态.注意块是如何击中另一个块并停止的

这是另一个包含推块功能的谜题:

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

如您所见,当块碰到箭头块时,块已移动到左侧,并停在木块顶部.

我想编写一个解决这些难题的AI解决方案 - 我认为这将是某种深度优先搜索,但我不知道从哪里开始.实现这一目标的任何指针都将是一件好事!

Answer 1

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

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

1. 初始状态,在您的问题中初始配置
2. 返回从空间的任何状态可到达的所有可能状态的函数,在您的问题中,可达状态是可以通过移动滑块获得的拼图的所有可能配置.当访问其可到达状态时,状态被扩展.
3. 目标测试,一个确定给定状态是否为目标状态的函数,在您的问题中,您将检查是否所有目标块都已填充,
4. 一种成本函数,它提供从一个状态传递到另一个状态的成本,允许您的算法选择要执行的最佳操作.在您的情况下,我认为您可以为每个操作使用常量值1,并搜索要执行的最小操作数以达到其中一个目标状态.

由于可以根据这四个组件定义问题,因此可以使用以下算法之一解决问题:

1. 广度优先搜索(BFS):我们首先测试初始状态是否是目标状态(显然不是非平凡问题),然后我们扩展初始状态,测试每个可达状态,如果不是,则扩展每个状态状态,等等等级......可以使用队列来实现.
2. 深度搜索(DFS):从初始状态开始,测试目标,然后扩展邻居状态,测试目标,扩展状态,等等,直到状态空间的最深层.这可以用堆栈实现.

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

1. 完整性:是否保证算法在存在时找到解决方案？
2. 最优性:算法能找到最优解吗？
3. 时间复杂性:需要多长时间？
4. 空间复杂性:它需要多少内存？

如果我们考虑BFS策略,我们可以看到它是完整的,因为它系统地按层次探索状态空间,只有当状态的深度增加时成本函数没有减少时才是最优的(这是我们的情况,因为所有的行动有不变的成本).现在它出现了坏消息:假设每个节点的扩展最多可以提供http://latex.codecogs.com/png.download?b状态,并且第一个解决方案是深入的,那么你最多需要存储和扩展 状态.

在DFS的情况下,我们必须考虑当一个不同的选择可能导致某处附近的解决方案时,它可能会在路径中停留很长时间(可能是无限的).因此,当状态空间是无限的时,该算法既不完整也不优化.如果我们考虑 作为状态空间的最大深度,我们将获得最多的空间复杂度 ,而时间复杂性仍然是指数级的: .

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

参考:人工智能:一种现代方法

注意:显然存在其他不明确的策略,但正如书中所述,IDDFS是不知情的搜索问题的理想选择,其中您没有关于搜索空间的其他信息.有关其他类型的搜索策略,例如知情搜索,请参阅本书,了解目标状态与当前状态的距离.