Алгоритм и структура данных для решения игры "Глобы" /заливка залива / "FloodIt"

Предложите алгоритм и структуру данных для решения игры Globs (http://www.deadwhale.com/play.php?game=131). Это довольно забавно в уродливом виде.

Укажите сложность временного пространства (большой-O) вашего подхода в терминах N, размер сетки (N >= 14). Предпочтительные эффективные алгоритмы с низкой сложностью.

(MatrixFrog правильно указывает, что эта игра также известна как FloodIt, и Smashery дал решение 3 месяца назад в ссылке, которую он цитирует ниже. Все, что вы говорите, предлагая обрезку/жадность только с одним взглядом, что дает субоптимальные решения.)

Игра генерирует случайную квадратную сетку узлов nxn, где каждый node окрашен в один из шести цветов (Grn = 1, Ylw = 2, Red = 3, Blu = 4, Pur = 5, Orn = 6), Уровень 1 имеет сетку 9x9, затем n увеличивает каждый уровень, до 14. На каждом уровне вы можете взять до 25 оборотов, иначе проиграете. На каждом шагу вы выбираете, какой цвет изменить в верхнем левом node, например. Grn- > Red, так что любые связанные соседние (горизонтальные/вертикальные) узлы нового цвета усваиваются в форме, а 1 pt за node - ADDED добавляется к вашему счету. Цель подсчета состоит в том, чтобы завершить каждую сетку за несколько ходов, например, если вы сделаете это за 16 оборотов, то ваши 9 неиспользованных ходов = > 2 * 9 MULTIPLIER умножат ваш общий накопленный балл.

Очевидно, есть много способов разложить это, и выбор по умолчанию рекурсивного обратного трассировки с сеткой 14x14 является жизнеспособным соперником; К каким другим типам данных это относится? A *? Не зацикливайтесь на оптимальности, мне интересно, есть ли алгоритм "достаточно хорошего".

(Я думал, что это забавный проект, чтобы закодировать робота и получить глупые результаты. Хотя я набрал 3.5E + 12 всего своим самосознанием fleshware.)

Ответ 1

Эта игра действительно привлекла мой интерес, поэтому я потратил пару дней на это.

Первое, что я заметил, заключается в том, что легко показать, что после первой платы (возможно, в некоторых случаях 2) самый быстрый способ поднять счет - с помощью множителя. Из-за этого я построил систему с целью решения каждой доски в наименьшее количество шагов. Я начал использовать A *, потому что он, как правило, построен только для этих типов проблем поиска... однако эта проблема все же оказалась doozie.

Говоря об A *, эффективность этого действительно сводится к выбору эвристической оценки. Чем ближе вы догадаетесь о фактическом расстоянии, тем меньше узлов, которые нужно будет расширить, чтобы достичь цели. Для этой проблемы я рассмотрел ряд идей для оценки, но большинство из них нарушили правило A *, которое заключается в том, что вы НЕ можете оценить фактическое расстояние, иначе вы нарушите оптимальность A *.

Однако есть некоторые из них. Другие в этой теме опубликовали только количество оставшихся цветов в качестве оценки, что допустимо, потому что оно не может быть оценено (вы должны менять цвета хотя бы один раз за каждый оставшийся цвет, не являющийся частью основной области "наводнения". проблема с этой эвристикой заключается в том, что она очень плохо оценивает фактическое расстояние. Возьмем, к примеру, первый ход, который обычно оценивает количество цветов, 6. Он часто расширяется на 2 шага, каждый из которых обычно имеет оценку 7, и т.д. и т.д. Возьмите эти 5 уровней в глубину и размер доски 10x10, у большинства листьев есть оценка 11. Эта эвристика - это в основном реализация первого поиска по ширине, пока вы не достигнете 4 или 5 шагов от вашего Это не очень эффективно, и в моих собственных тестах экспоненты управляют размером около 9, что часто требует около 14 шагов в решении. Следует отметить, что мое решение было очень высоким, однако, к спеку.

Проблема в том, что A * действительно хорош только тогда, когда каждый шаг значительно улучшает фактическое расстояние общего решения. Если смотреть на проблему напрямую, вы, вероятно, не найдете хорошей эвристики, которая может сделать намного лучше, чем это, без оценки стоимости. Однако, если вы превратите проблему в другую проблему, вы сможете вырваться из нее лучше эвристики. Эвристическое "количество оставшихся цветов" отвечает на вопрос, каково наименьшее количество возможных ходов. Чтобы ответить на этот вопрос, я спросил себя: "Какое место на доске требует максимального количества шагов"? В итоге я решил ответить на вопрос "сколько шагов в нижнем правом углу" для моей эвристики. Это довольно легко реализовать, запустив еще один поиск A *, который больше похож на поиск направлений карты, а затем подсчет количества шагов в решении. Я понимаю, что это произвольная точка на доске для выбора, однако она неплохо работала при тестировании и запуске A * на каждой оставшейся точке занимала довольно много времени на моей тестовой машине с одним процессором.

Только эта эвристика имела тенденцию к краху после того, как нижний правый угол стал частью затопленной области, поэтому конечным результатом был MAX (нижний правый угол мин. шагов, количество оставшихся цветов не было частью основного потока). Это, наконец, позволило достичь некоторых очень больших размеров платы за секунду с моей реализацией на высоком уровне.

Я оставлю настройки записи для вас.

Ответ 2

Другой подход - использовать генетические алгоритмы. Поскольку любое (частичное) решение состоит из списка цветов, оно очень хорошо переносится на ген. Функция фитнеса может быть чем-то вроде 4-кратного связанного компонента минус количество используемых цветов (длина гена).

Я пробовал это на платах 10x10 в Mathematica, с очень не оптимизированным алгоритмом, и получил короткое решение довольно быстро. Я не утверждаю, что это оптимально, но при достаточном времени случайность в процессе мутации генов гарантирует, что в конечном итоге вы получите оптимальное решение.

Ответ 3

Учитывая фиксированное начальное состояние и ограниченное количество ходов, я думаю, вы можете полностью изучить дерево решений. Для каждого раунда существует всего 5 возможных ходов и расточительных ходов (выбор цвета, который не будет "глотать" всех соседей, что-то-всегда) может быть устранен по мере создания дерева. Как только дерево решений будет построено, я думаю, что вы могли бы исследовать значение точки для каждого пути, но если вам нужна была большая оптимизация, A * определенно приблизит вас.

Для каждого раунда я бы имел базовое состояние как матрицу бит-массивов для состояния неглазурованных местоположений (так как цвет больше не имеет значения в местах, где вы могли сохранить память в своей структуре данных состояния, оставив цветовые биты) и значение точки для каждого решения. Тогда ваш алгоритм A * или ширины может просто максимизировать значения пути как обычно. Сохраните путь, и как только ваш анализ будет завершен, выполните все определенные шаги.

Ответ 4

если можно, устраните цвет.
выбрал цвет, создающий для вас новые соседи!
перейти к шагу 1.

Ответ 5

Рекурсивный поиск грубой силы найдет максимальный балл. У вас должно быть не более 5 ^ 25 конечных состояний. Многие промежуточные состояния будут эквивалентны; возможно, быстрее распознать их и обрезать пространство поиска дубликатов. Следите за самым высоким счетом, найденным в процессе поиска, а также по пути (последовательности ходов), который требуется, чтобы добраться туда.

Ответ 6

Хорошая эвристика - это создание цветной карты расстояния. Например. текущее наводнение находится на нулевом расстоянии. Группа цветов, связанных с квадратом на расстоянии "i", находится на расстоянии "i + 1".

Затем, посмотрите, сколько цветов находится на максимальном расстоянии. Нам нужны максимальные расстояния, чтобы устранить один цвет на максимальном расстоянии, и нам нужно дополнительное движение, чтобы устранить каждый дополнительный цвет на максимальном расстоянии. Если все цвета не находятся на максимальном расстоянии, рассмотрите цвета на предыдущем расстоянии, которые еще не были устранены. Мы могли бы устранить один из этих цветов при выполнении движений "максимального расстояния", но нам понадобится переход, чтобы устранить каждый дополнительный цвет.

Это дает довольно хорошую оценку. На начальном положении 14x14 доски я получаю оценки от 17 до 18, в то время как для оптимального решения требуется от 20 до 22 ходов. Плата 14x14 обычно может быть решена с этой нижней границей, глядя на около 10 000 позиций на плате. (Использование оптимизации движения, устраняющего цвет, если такой ход доступен.)

Ответ 7

Другая оптимизация заключается в том, что есть некоторые цветовые капли, которые не нужно принимать сразу. На графике расстояний сети могут быть листы, в которых один цветной блок не имеет другого соседа. Этот цветной капля не нужно снимать до самого дальнего капли того же цвета. Используя этот подход, мы можем настроить карту расстояния, чтобы получить минимальное время, в которое должен быть сделан цветной кадр.

Для некоторых позиций на борту мы сможем показать, что подходящий цвет не нужно брать на следующий ход. Мы можем избежать этого цвета и уменьшить коэффициент ветвления.