用于解决游戏“Globs”/ flood fill /“FloodIt”的算法和数据结构 [英] Algorithm and data structure for solving the game "Globs"/flood fill/"FloodIt"

问题描述

提出解决游戏全球的算法和数据结构（ http：// www .deadwhale.com / play.php？game = 131 ）。这是一种非常有趣的方式。

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.

根据N 说明您的方法的时空复杂性（big-O） ，网格的大小（N> = 14）。

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正确地指出这个游戏也被称为FloodIt，而Smashery给了一个3个月前，他在下面的链接中提到，所有的人都建议修剪/贪婪，只有1个前瞻，给出次优解。）

(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.)

游戏生成一个随机正方形nnn节点的网格，其中每个节点被着色为六种颜色之一（Grn = 1，Ylw = 2，Red = 3，Blu = 4，Pur = 5，Orn = 6）。 1级具有9x9格，然后n每级增加，最高可达14.
每级可以占用25圈，否则你输了。
在每一个回合你会选择哪个颜色来改变左上方的节点到例如。 Grn->红色，使得新颜色的任何连接的相邻（水平/垂直）节点被吸收成一个形状，并且每个节点被吸收的1 pt被添加到你的分数。
评分目标是尽可能多地完成每个网格，例如如果你这样做了16圈，那么你的9个未使用的移动=> 2 * 9 MULTIPLIER乘以你的总积分。

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.

显然，有很多方法来分解这个，14x14网格的递归回溯的默认选择是可行的竞争者;
这有什么其他类型的数据结构吗？一个* ？
不要挂起最优化，我想知道是否有一个足够好的算法。

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.

（我以为可能是一个
虽然我的肉体自己打进了3.5E + 12。）

(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.)

推荐答案

这个游戏真的抓住了我的兴趣，所以我花了几天的时间。

This game really grabbed my interest, so I spent a couple of days working on it.

我注意到的第一件事是，容易显示，在第一板（在某些情况下可能是2）之后，提高分数的最快方法是使用乘数。因此，我建立了一个系统，目标是以最少的步骤解决每个板。我开始想要使用A *，因为它通常是为这些类型的搜索问题建立的...但是，这个问题仍然是一个doozie。

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.

在谈论A *时，它的有效性可以减少您对启发式估计的选择。越接近实际距离的猜测，为了达到目标，必须扩展的节点越少。对于这个问题，我经历了一些估计的想法，但其中大多数都打破了A *规则，这是你不能超过估计实际距离，否则你打破A *的最优性。

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*.

然而有一些工作。这个线程中的其他人已经公布了只剩下剩余颜色的数量作为估计，这是可以接受的，因为它不能估计（您必须为每个剩余颜色至少改变一次颜色，而不是主要洪水区域的一部分。这个启发式的问题在于它估计实际距离很差，例如第一步，通常有一个颜色数量的估计，6.它通常扩展为2个移动，每个移动通常有一个估计为7 ，等等，这个深度为5级，板尺寸为10x10，大多数叶子的估计为11.这个启发式基本上是一个广泛的第一搜索的实现，直到你从你的4到5个移动这不是很有效率，在我自己的测试中，指数大概在9板左右，在解决方案中通常需要大约14次移动，应该注意的是，我的解决方案是非常高的水平，但并不太在意对

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.

问题是，A *只有在每个步骤对整体解决方案的实际距离进行显着改进时才是真正的好处。直接看问题，你可能不会找到一个好的启发式，可以做得比这更好，而不用估计成本。但是，如果将问题转化为另一个问题，更好的启发式将会跳出来。启发式的剩余颜色数正在回答问题，剩余的可能移动的最小数量是多少。对于这个问题的答案，我问自己板上的哪一个位置需要达到最大的步数？我结束了对我的启发式的答案对于右下角有多少步骤。通过运行另一个A *搜索，这更容易实现，该搜索更符合查找地图方向，然后计算解决方案中的步数。我意识到这是董事会上的一个任意选择，但是在我的单处理器测试机上花费相当多的时间在测试和运行A *上运行得很好。

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.

只有右下角成为淹水区域的一部分，这种单独的启发式趋势才会崩溃，因此最终结果为MAX（右下角最小步长，不是主要洪水的一部分） 。这最终能够在一秒钟内实现一些非常大的电路板尺寸，我的高级别实现。

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.

这篇关于用于解决游戏“Globs”/ flood fill /“FloodIt”的算法和数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！