Алгоритм и структура данных для решения игры “Шарики” / заливка / “FloodIt”
Предложите алгоритм и структуру данных для решения игровых Шариков (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-> Красный, такой, что любые связанные смежные (horiz/vert) узлы нового цвета ассимилируются в форму, и 1 ПБ на ассимилируемый узел ДОБАВЛЯЕТСЯ к Вашему счету. Цель выигрыша состоит в том, чтобы завершить каждую сетку в как можно меньшем количестве поворотов, например, если Вы делаете это в 16 поворотах, затем Ваши 9 неиспользованных перемещений => 2*9 раз МНОЖИТЕЛЯ Ваш общий накопленный счет.
Очевидно, существует тонна способов анализировать это и выбор по умолчанию рекурсивного отслеживания в обратном порядке с 14x14, сетка является жизнеспособным соперником; Чему другим типам структур данных это предоставляет себя?*? Не становитесь одержимыми оптимальностью, я задаюсь вопросом, существует ли "достаточно хороший" алгоритм.
(Я думал, что это мог бы быть забавный проект кодировать робот и получить глупые рекорды. Хотя я выиграл 3.5E+12 все моим fleshware сам.)
4 ответа
Эта игра действительно схватила свой интерес, поэтому я потратил пару дней, работающих над этим.
Первое, что я заметил, состоит в том, что легко показать, что после первой доски (может быть, 2 в некоторых случаях), самый быстрый способ повышения оценки - это с использованием множителя. Из-за этого я построил систему с целью решения каждой доски в течение всего наименьшего количества шагов. Я начал желание использовать *, потому что он обычно построен только для этих типов проблем поиска ... Однако эта проблема все еще оказалась Doozie.
При разговоре о *, эффективность его действительно сводится к вашему выбору эвристической оценки. Чем ближе вы догадаетесь до угадания фактического расстояния, тем меньше узлов, которые должны быть расширены, чтобы достичь цели. Для этой проблемы я прошел через ряд идеи для оценки, но большинство из них нарушили правило *, что вы не можете переоценить на фактическое расстояние, иначе вы нарушаете оптимальность a *.
Однако есть несколько, которые работают. Другие в этой теме опубликовались просто принять количество оставшихся цветов в качестве оценки, что допустимо, потому что он не может переоценить оценку (вы должны изменить цвета, по крайней мере, один раз для каждого оставшегося цвета, не являющейся частью основного «наводнения». Проблема с этим эвристическим является то, что она очень плохо оценивает фактическое расстояние. Принять, например, первый ход, который обычно имеет оценку количества цветов, 6. Это часто расширяется на 2 хода, каждый из которых обычно имеет оценку 7 И так далее и так далее. Возьмите это 5 уровней глубоко и для размера доски 10х10, большинство листьев имеют оценку 11. Эта эвристика является в основном реализацией широта первого поиска, пока вы не достигнете в течение 4 или 5 ходов Цель. Это не очень эффективно и в моих собственных испытаниях экспоненты сталкиваются с большим количеством вокруг размера 9 доска 9, что часто требует около 14 ходов в растворе. Следует отметить, что мое решение было очень высоким уровнем, однако не было принято чтобы ускорить тонко GS UP.
Проблема заключается в том, что A * действительно хорош только при каждом этапе значительное уточнение к фактическому расстоянию общего решения. Глядя на проблему напрямую, вы, вероятно, не найдете хорошего эвристика, которые могут сделать гораздо лучше, чем это без превышения оценки стоимости. Однако, если вы преобразуете проблему в другую проблему, лучшая эвристика выпрыгивает на вас. Эвристическое «количество оставшихся цветов» отвечает на вопрос, что такое наименьшее количество возможных движений. К ответ на этот вопрос я спросил себя «Какое место на доске требует максимального количества шагов, чтобы добраться до»? Я оказался урегулирован на ответ на «Сколько шагов в правом нижнем углу» для моего эвристика. Это довольно легко реализовать, запустив еще один поиск *, который работает больше похоже на поиск направлений на карте, а затем подсчитывать количество шагов в решении. Я понимаю, что это произвольная точка на плате, чтобы выбрать, однако он работал довольно хорошо в тестировании и запущении * на каждой оставшейся точке прошел достаточно времени на моем единственном тестировании процессора.
Единственная эвристическая была тенденция квалиться после того, как правый нижний угол стал частью затопленной зоны, поэтому окончательный результат был Макс (правый нижний углу мин, число цветов, оставшихся не частью основного наводнения). Это было, наконец, в состоянии достичь некоторых очень больших размеров доски ниже второго с моим высоким уровнем реализации.
Я оставлю настройки записи к вам.
- если можно, удалите цвет.
- выберите цвет, который создаст для вас больше новых соседей !
- goto step 1.
При рекурсивном переборе будет найден максимальный результат. У вас есть максимум 5^25 конечных состояний для рассмотрения. Многие промежуточные состояния будут эквивалентны; может быть быстрее распознать их и подрезать пространство поиска дубликатов. Отслеживайте наибольшее количество найденных баллов, а также путь (последовательность ходов), который вам понадобился, чтобы туда попасть
.Учитывая фиксированное стартовое состояние и ограниченное количество ходов, я думаю, что вы можете полностью изучить дерево решений. Для каждого раунда есть только 5 возможных ходов, и потраченные впустую ходы (выбирая цвет, который не будет "глотать" соседей, что бы ни случилось) могут быть устранены по мере построения дерева. После построения дерева решений я думаю, что вы могли бы исследовать значение точки в каждом пути, но если бы вам понадобилось больше оптимизации, A* определенно приблизил бы вас.
Для каждого раунда у меня было бы базовое состояние в виде матрицы битовых массивов для состояния не "глобусных" локаций (так как цвет больше не имеет значения в глобусных локациях, вы могли бы сохранить память в структуре данных о вашем состоянии, оставив биты цвета) и значение точки для каждого решения, которое возможно. Тогда ваш алгоритм A*, или первый алгоритм ширины, может просто максимизировать значения пути как обычно. Сохраните путь, и после завершения анализа сделайте все определенные перемещения.