使用AI解决益智游戏 [英] Solving a puzzle game using AI

问题描述

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

I have made a puzzle where the player slides blocks around to goals - the rules are fairly simple:

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

1. Only one slider block may move at a time
2. The object is to move the slider blocks into goal nodes - you only need to fill the goal nodes, not necessarily get all slider blocks into the goal nodes.
3. If the slider block slides on ice, it will continue moving in that direction until it is stopped or moved
4. If the slider block hits something solid (concrete, another block) it stops and can be moved again (not into the concrete, obviously)
5. If the slider block slides onto wood, it stops on the wood and can be moved
6. If the slider block slides onto a goal node, it can no longer be moved
7. The block can be moved by certain blocks, for example, an arrow block pushes the block in that direction
8. There are switch blocks which enable "doors", which can be moved on to in order to open, and to close, these "doors"
9. There are button blocks which operate similarly to switches except that they must have a block on them to activate the "doors"
10. When doors are closed, they act like concrete. When doors are open, they act like ice.

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

I think that's the rules covered. Here are some screenshots:

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

Here the player must move blocks so that they must hit each other in order to solve the puzzle.

处于近乎解决状态的难题.请注意，该街区如何撞到另一个街区并停止了

The puzzle in it's near-solved state. Note how the block has hit another block and stopped

这是另一个难题，其中包括推块机制:

Here is another puzzle which has the push block mechanic included:

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

If we slide the top right block downward, the following happens:

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

As you can see, the block has been moved to the left when it hit the arrow block, and stopped on top of the wood block.

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

I would like to write an AI solution that solves these puzzles - I was thinking that it would be some kind of depth-first search, but I don't have much idea of where to start. Any pointers in making this happen would be a great thing!

推荐答案

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

Your problem is a classical instance of State-Space search problem. There are different algorithms that can be used based on the characteristics of your particular instance.

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

Regardless of your particular instance you need to have defined four components:

1. 初始状态，您遇到的问题是初始配置
2. 一个函数，该函数返回从空间的任何状态可到达的所有可能状态，在您遇到的问题中，可到达状态是可移动滑块获得的拼图的所有可能配置.当一个状态到达其可访问状态时，该状态被称为扩展状态.
3. 目标测试，一种确定给定状态是否为目标状态的函数，在您遇到的问题中，您将检查是否填充了所有目标块，
4. 一种成本函数，它给出了从一种状态传递到另一种状态的成本，从而使您的算法可以选择执行最佳行动.就您而言，我认为您可以为每个操作使用1的恒定值，并搜索要达到某一目标状态要执行的最少操作数.

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

Since your problem can be defined in terms of these four components your problem can be solved with one of the following algorithms:

1. 宽度优先搜索(BFS):我们首先测试是否状态是目标状态(显然不是针对非平凡的问题)，然后我们扩展初始状态，测试其每个可达状态，如果不是，则扩展每个这些状态，依此类推…… 可以使用队列来实现.
2. 深度优先搜索(DFS):从初始状态开始，进行测试确定目标，然后扩展邻居状态，测试目标，扩展该状态，等等，直到状态空间的最深层次. 可以使用堆栈来实现.

1. Breadth-first search (BFS): We start by testing whether the initial state is a goal state (obviously not for non-trivial problems), then we expand the initial state, test each of its reachable states, if not, expand each these states, and so on going for levels... It can be implemented using a queue.
2. Depth-fisrt search (DFS): Starting with the initial state, test for goal, then expand a neighbour state, test for goal, the expand that state, and so on going down to the deepest levels of the state space. This can be implemented with a stack.

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

To evaluate which algorithm is the most appropriate we can consider these factors:

1. 完备性:是否可以保证算法在存在时会找到解决方案?
2. 最优性:算法可以找到最优解吗?
3. 时间复杂度:需要多长时间?
4. 空间复杂性:需要多少内存?

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

If we consider the BFS strategy we can see that it is complete since it systematically explores the state space by levels, it is optimal only if the cost function does not decrease when the depth of a state increases (this is our case, since all the actions have a constant cost). Now it comes the bad news: assume that the expansion of each node can give at most http://latex.codecogs.com/png.download?b states, and the first solution is at depth , then you will need to store and expand at most states.

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

In the case of DFS we must consider that it can be stuck searching in a path for a lot of time (potentially infinite) when a different choice could lead to a solution somewhere near. So when the state space is infinite this algorithm is neither complete nor optimal. If we consider as the maximum depth of the state space, we will get a space complexity of at most , whereas the time complexity remains exponential: .

那么，我们该怎么办?我们可以混合使用这两种策略，并使用迭代加深深度优先搜索.在此搜索中，我们将迭代运行DFS，将最大深度限制为从0开始到最大深度级别.此方法具有两种搜索策略的优点:空间复杂度，其中是第一个最佳解决方案的深度，时间(我们不能做得更好)，它是完整的(它将找到解决方案，因为它会逐级迭代地探索所有状态)，并且它是最优的(假定成本函数随路径长度的增加而不变)，这与BFS相同的原因相同最佳.

So, what can we do? We can mix these two strategies and use the Iterative Deepening depth first search. In this search we will run iteratively a DFS limiting the maximum depth starting from 0 to a maximum depth level. This method has the advantages of both search strategies: space complexity, where is the depth of the first optimal solution, time (we can't do better), it is complete (it will find a solution because it iteratively explores all states by levels) and it is optimal (assuming the cost function is nondecreasing with path length) for the same reasons BFS is optimal.

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

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

Note: obviously there exist other uninformed strategies, but as stated on the book IDDFS is a good choice for uninformed search problems where you don't have additional information on the search space. Refer to the book for other types of search strategies, for example informed search, were have an idea of how far is a goal state from the current state.

这篇关于使用AI解决益智游戏的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！