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

Question

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

Укажите временную сложность (большой-O) вашего подхода в терминах N, размер сетки (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, так что любые связанные соседние (horiz/vert) узлы нового цвета будут ассимилироваться в форму, а 1 pt на каждый усваиваемый узел добавляется к вашему счету. Задачей подсчета является заполнение каждой сетки в виде нескольких поворотов, как это возможно, например. если вы сделаете это за 16 оборотов, то ваши 9 неиспользованных ходов => 2 * 9 MULTIPLIER умножат ваш общий накопленный балл.

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

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

Answer 1

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

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

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

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

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

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

Я оставлю запись для вас.

Answer 2

1. , если вы можете, устранить цвет.
2. выбрал цвет, который генерирует больше новых соседей для вас!
3. шаг Гото 1.

Answer 3

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

Answer 4

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

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

Answer 5

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

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

Answer 6

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

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

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

Answer 7

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

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