用于解决游戏“Globs”/flood fill/“FloodIt”的算法和数据结构
建议解决游戏 Globs 的算法和数据结构 (http://www.deadwhale. com/play.php?game=131）。这以一种极客的方式非常有趣。
用 N 表示方法的时空复杂度 (big-O)，即网格的大小 (N>=14)。 首选低复杂度、足够高效的算法。
（MatrixFrog 正确地指出这个游戏也称为 FloodIt，Smashery 3 个月前在他引用的链接中给出了解决方案。所有你们建议的人修剪/贪婪仅具有 1 个前瞻，这给出了次优解决方案。）
游戏生成 nxn 节点的随机方形网格，其中每个节点的颜色为六种颜色之一（Grn = 1，Ylw = 2，Red = 3，Blu = 4） ，Pur=5，Orn=6)。第 1 级有 9x9 网格，然后每级 n 增加，直到 14。 每个关卡最多可以进行 25 个回合，否则你就输了。 在每一回合中，您选择将左上角节点更改为哪种颜色，例如 Grn->Red，这样新颜色的任何连接的相邻（水平/垂直）节点都会被同化为一个形状，并且每个被同化的节点会添加 1 pt到你的分数。 计分目标是在尽可能少的回合内完成每个网格，例如，如果您在 16 回合内完成，那么您的 9 次未使用的移动 => 2*9 乘以您的总累计分数。
显然，有很多方法可以分解这个问题，并且使用 14x14 网格的递归回溯的默认选择是一个可行的竞争者； 这还适用于哪些其他类型的数据结构？一个*？ 不要纠结于最优性，我想知道是否存在“足够好”的算法。
（我认为对机器人进行编码并获得愚蠢的高分可能是一个有趣的项目。 虽然我的成绩是3.5E+12，都是我肉身的。）
Suggest an algorithm and data structure for solving the game Globs (http://www.deadwhale.com/play.php?game=131). It's pretty fun in a geeky kind of way.
State the time-space complexity (big-O) of your approach in terms of N, the size of the grid (N>=14). Good-enough efficient algorithms with low complexity are preferred.
(MatrixFrog correctly points out this game is also known as FloodIt, and Smashery gave a solution 3 months ago in the link he cites below. All you dudes suggesting pruning/greedy with only 1 lookahead, that gives suboptimal solutions.)
The game generates a random square grid of nxn nodes, where each node is colored one of six colors (Grn=1, Ylw=2, Red=3, Blu=4, Pur=5, Orn=6). Level 1 has 9x9 grid, then n increases each level, up to 14.
Each level you can take up to 25 turns or else you lose.
On each turn you choose which color to change the top left node to e.g. Grn->Red, such that any connected adjacent (horiz/vert) nodes of the new color get assimilated into a shape, and 1 pt per node assimilated is ADDED to your score.
The scoring objective is to complete each grid in as few turns as possible, e.g. if you do it in 16 turns, then your 9 unused moves => 2*9 MULTIPLIER times your total accumulated score.
Obviously there are a ton of ways to decompose this, and the default choice of recursive backtracking with a 14x14 grid is a viable contender;
What other types of data structures does this lend itself to? A* ?
Don't get hung up on optimality, I'm wondering if there is a "good-enough" algorithm.
(I thought it might be a fun project to code up a robot and get silly-high scores.
Although I scored 3.5E+12 all by my fleshware self.)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
这个游戏确实引起了我的兴趣，所以我花了几天的时间来制作它。
我注意到的第一件事是，很容易表明，在第一个棋盘（在某些情况下可能是 2 个）之后，提高分数的最快方法是使用乘数。因此，我构建了一个系统，目标是用最少的步骤解决每个板问题。我开始想使用 A*，因为它通常是为这些类型的搜索问题而构建的……但是，这个问题仍然是一个棘手的问题。
当谈论 A* 时，它的有效性实际上归结为你对启发式估计的选择。你越接近猜测实际距离，为了达到目标而需要扩展的节点就越少。对于这个问题，我经历了很多估计的想法，但大多数都打破了A*规则，即你不能高估实际距离，否则你就破坏了A*的最优性。
然而，有一些是有效的。该线程中的其他人已经发布了关于仅将剩余颜色的数量作为估计的内容，这是可以接受的，因为它不能过度估计（您必须为不属于主要“洪水”区域的每种剩余颜色至少更改一次颜色。这种启发式的问题在于，它对实际距离的估计非常差，以第一个移动为例，它通常估计颜色数量为 6。它通常会扩展到 2 个移动，每个移动通常估计为 7。 ，依此类推，以 5 层深度为例，对于 10x10 的棋盘大小，大多数叶子的估计值为 11。这种启发式基本上是广度优先搜索的实现，直到您达到距您的 4 或 5 步以内。这不是很有效，在我自己的测试中，指数在棋盘尺寸 9 附近运行，这通常需要解决方案中的大约 14 步，但应该注意的是，我的解决方案水平非常高，并且没有引起太多注意。加快速度。
问题是，只有当每个步骤对整体解决方案的实际距离进行重大改进时，A* 才真正有效。直接查看问题，您可能找不到比这更好的启发式方法，而无需高估成本。然而，如果你将问题转化为另一个问题，更好的启发式方法就会跳出来。启发式的“剩余颜色数”正在回答这个问题：剩余的最小可能移动数是多少。为了回答这个问题，我问自己“棋盘上的哪个位置需要最多的步数才能到达”？我最终确定了“到右下角需要多少步”的启发式答案。通过运行另一个 A* 搜索来实现这一点相当容易，该搜索的工作方式更像是查找地图方向，然后计算解决方案中的步骤数。我意识到这是板上可以选择的任意点，但是它在测试中运行得很好，并且在我的单处理器测试机上在每个剩余点上运行 A* 花费了相当多的时间。
然而，在右下角成为淹没区域的一部分后，这种启发式本身就有崩溃的趋势，因此最终结果是 MAX（右下角最小步长，剩余不属于主要淹没部分的颜色数量）。通过我的高级实施，最终能够在一秒钟内实现一些非常大的电路板尺寸。
我将把记录设置留给你。
This game really grabbed my interest, so I spent a couple of days working on it.
The first thing I noticed, is that it is easy to show that after the first board (maybe 2 in some cases), the fastest way to raise the score is by using the multiplier. Because of this, I built a system with the goal of solving each board in the fewest number of steps. I started out wanting to use A* because it is generally built for just these types of search problems... however, this problem still turned out to be a doozie.
When talking about A*, the effectiveness of it really boils down your choice of heuristic estimation. The closer you get to guessing the actual distance, the fewer nodes that will have to be expanded in order to reach the goal. For this problem, I went through a number of ideas for estimation, but most of them broke the A* rule, which is that you can NOT over estimate the actual distance, or else you break the optimality of A*.
There are a few that work however. Others in this thread have posted about just taking the number of remaining colors as the estimation, which is admissible because it cannot over estimate (you have to change colors at least once for each remaining color not part of the main "flood" area. The problem with this heuristic is that it very poorly estimates the actual distance. Take for instance the first move, which generally has an estimation of the number of colors, 6. It often expands into 2 moves, each of which generally has an estimation of 7, and so on and so on. Take this 5 levels deep and for a board size of 10x10, most leafs have an estimation of 11. This heuristic is basically an implementation of a breadth first search until you reach within 4 or 5 moves from your goal. This is not very efficient and in my own tests, the exponents run a much around board size 9, which often requires about 14 moves in the solution. It should be noted my solution was very high level however and not much care was taken to speed things up.
The problem is that A* is really only good when each step makes a significant refinement to the actual distance of the overall solution. Looking at the problem directly, you probably wont find a good heuristic that can do much better than this without over estimating the cost. However, if you transform the problem into another problem, better heuristics jump out at you. The heuristic "number of colors remaining" is answering the question, what is the smallest number of possible moves remaining. To the answer that question, I asked myself "which spot on the board requires the maximum number of steps to get to"? I ended up settling on the answer to "how many steps is it to the bottom right corner" for my heuristic. This is fairly easy to implement by running another A* search that works more like finding map directions and then counting the number of steps in the solution. I realize this is an arbitrary point on the board to select, however it worked quite well in testing and running A* on every remaining point took a fair amount of time on my single processor test machine.
This heuristic alone had a tendency to collapse after the bottom right corner became part of the flooded area however, so the final result was MAX(bottom right corner min steps, number of colors remaining not part of main flood). This was finally able to achieve some very large board sizes in under a second with my high level implementation.
I'll leave the record setting to you.
考虑到固定的起始状态和有限的移动次数，我认为您可以充分探索决策树。对于每一轮，只有 5 种可能的移动，并且在构建树时可以消除浪费的移动（选择不会“笼罩”任何邻居的颜色）。一旦构建了决策树，我认为您可以探索每条路径的点值，但如果您需要更多优化，A* 肯定会让您接近。
对于每一轮，我将基本状态作为未通配位置的状态的位数组矩阵（因为颜色在通配位置中不再重要，您可以通过省略颜色位来节省状态数据结构上的内存）以及每个可能的决定的分值。然后你的 A* 或广度优先算法就可以像平常一样最大化路径值。保存路径，分析完成后，进行所有确定的移动。
Given the fixed starting state and limited number of moves I think you can fully explore a decision tree. For each round, there are only 5 possible moves and wasted moves (choosing a color that will not 'glob' any neighbors what-so-ever) can be eliminated as the tree is built. Once the decision tree is built I think you could explore the point value of each path but if you needed more optimization a A* would definitely get you close.
For each round, I would have the basic state as a matrix of bit arrays for the state of the unglobbed locations (since the color no longer matters in the globbed locations you could save memory on your state data structure by leaving off the color bits) and a point value for each decision possible. Then your A*, or breadth first algorithm can just maximize the path values as normal. Save the path, and once your analysis is complete, make all of the determined moves.
另一种方法是使用遗传算法。
由于任何（部分）解决方案都由颜色列表组成，因此它可以很好地转换为基因。适应度函数可能类似于连接分量的 4 倍减去所用颜色总数（基因长度）。
我在 Mathematica 的 10x10 板上尝试了这个，使用了非常非优化的算法，
并很快得到了一个简短的解决方案。
我并不是说它是最优的，但只要有足够的时间，基因突变过程中的随机性将确保你最终得到最优的解决方案。
Another approach is to use genetic algorithms.
Since any (partial) solution consists of a list of colors, it translates very nicely to a gene. A fitness function could be something like 4 times the connected component minus the number of colors used total (length of gene).
I tried this on 10x10 boards in Mathematica, with a very non-optimized algorithm,
and got a short solution rather quickly.
I do not claim it is optimal, but given enough time, the randomness in the process of mutating the genes will ensure that you eventually ends up with an optimal solution.
强力递归搜索将找到最大分数。您最多可以考虑 5^25 个结束状态。许多中间状态将是等效的；识别这些并修剪重复项的搜索空间可能会更快。跟踪您搜索时找到的最高分，以及到达那里所需的路径（移动顺序）。
A brute-force recursive search will find the maximum score. You have at most 5^25 ending states to consider. Many intermediate states will be equivalent; it may be faster to recognize these and prune the search space of duplicates. Keep track of the highest score found so far as you search, along with the path (sequence of moves) that it took to get there.
一个好的启发式方法是生成颜色连接距离图。例如，当前的洪水距离为零。连接到距离“i”的正方形的一组颜色的距离为“i+1”。
接下来，观察最大距离处有多少种颜色。我们需要最大距离移动来消除最大距离处的一种颜色，并且我们需要额外的移动来消除最大距离处的每种附加颜色。如果所有颜色都不在最大距离处，则考虑前一个距离处尚未消除的颜色。我们可能会在进行“最大距离”移动时消除其中一种颜色，但我们需要一次移动来消除每种额外的颜色。
这提供了一个相当好的估计。在最初的 14x14 棋盘位置上，我倾向于得到 17 到 18 步的估计，同时需要 20 到 22 步才能获得最佳解决方案。通常可以通过此下限来解决 14x14 棋盘问题，同时查看大约 10,000 个棋盘位置。 （如果可以的话，使用消除颜色的移动的优化。）
A good heuristic is to generate the color-connected distance map. E.g. the current flood is at distance zero. A group of colors connected to a square at distance 'i' is at distance 'i+1'.
Next, observe how many colors are at the maximum distance. We need maximum distance moves to eliminate one color at the maximum distance, and we need an additional move to eliminate each additional color at the maximum distance. If all colors are not at the maximum distance, consider the colors at the previous distance which have not yet been eliminated. We might eliminate one of these colors while making 'maximum distance' moves, but we will need a move to eliminate each additional color.
This provides a fairly good estimate. On the initial 14x14 board position, I tend to get estimates of 17 to 18 while needing 20 to 22 moves for an optimal solution. A 14x14 board can typically be solved, with this lower bound, while looking at about 10,000 board positions. (Using the optimization of making a move that eliminates a color if such a move is available.)
另一个优化是有一些颜色斑点不需要立即取出。网络距离图中可能存在叶子，其中一个颜色斑点没有进一步的邻居。直到最远的相同颜色的斑点才需要获取该颜色斑点。使用这种方法，我们可以调整距离图以获得必须拍摄颜色斑点的最短时间。
对于某些棋盘位置，我们将能够证明下一回合不需要采用符合条件的颜色。我们可以避免这种颜色并减少分支因子。
Another optimization is that there are some color blobs that do not need to be taken right away. There can be leafs in the network distance graph where one color blob does not have a further neighbor. This color blob doesn't need to be taken until the furthest blob of the same color. Using this approach, we can adjust the distance map to get the minimum time at which a color blob must be taken.
For some board positions, we will be able to show that an eligible color does not need to be taken on the next turn. We can avoid that color and reduce the branching factor.