Bubble Breaker Game Solver лучше, чем жадный?

Question

Для умственного упражнения я решил попробовать игру «Разрушитель пузырей», которую можно найти на многих мобильных телефонах, а также пример, приведенный здесь: Bubble Break Game

• Случайная (N, M, C) доска состоит из N строк x M столбцов с цветами C
• Цель состоит в том, чтобы получить наивысший балл, выбрав последовательность пузырьковых групп, которая в итоге приводит к наивысшему баллу
• Группа пузырьков - это 2 или более пузырьков одного цвета, которые расположены рядом друг с другом в направлении x или y. Диагонали не в счет
• Когда группа выбрана, пузырьки исчезают, любые отверстия сначала заполняются пузырьками сверху, т. Е. Сдвигаются вниз, затем любые отверстия заполняются смещением вправо
• Оценка группы пузырьков = n * (n - 1), где n - количество пузырьков в группе пузырьков

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

Некоторые из идей, которые я использую, включают нормализованное запоминание. Когда доска решена, мы сохраняем доску и лучший результат в таблице воспоминаний.

Я создаю прототип в python , который показывает, что (2,15,5) доска требует 8859 досок для решения примерно за 3 секунды. Плата (3,15,5) занимает 12,384,726 досок за 50 минут на сервере. Скорость решения составляет ~ 3k-4k досок / сек и постепенно уменьшается, поскольку поиск по памятникам занимает больше времени. Таблица мемоизации увеличивается до 5 692 482 досок и достигает 6 713 566 раз.

Какие другие подходы могут дать высокие результаты, кроме исчерпывающего поиска?

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

Спасибо Дэвиду Локку за публикацию ссылки на бумагу, в которой говорится о решателе окон, который использует эвристику прогнозирования постоянной глубины.

Answer 1

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

Answer 2

Я почти закончил писать свою версию "решателя" на Java. Он выполняет как исчерпывающий поиск, для которого требуются большие возрасты, так и направленный поиск, основанный на «пуле» возможных путей, который обрезается после каждого поколения, и фитнес-функцию, используемую для сокращения пула. Я просто пытаюсь настроить фитнес-функцию сейчас ...

Обновление - теперь доступно на http://bubblesolver.sourceforge.net/

Answer 3

В моей шахматной программе я использую некоторые идеи, которые, вероятно, могут быть адаптированы к этой проблеме.

• Порядок перемещения. Сначала найди все возможные ходы, хранить их в списке, и сортировать их по некоторым эвристический. Сначала «лучшие», «плохие» последние. Например, это может быть функцией размера группы (предпочитают среднего размера группы), или количество смежных цвета, группы и т. д.

• Итеративное углубление. Вместо запустить чистый поиск в глубину, отрезок поиска после определенного глубоко и использовать некоторые эвристические для оценки результат. Теперь исследуйте дерево с «лучшими» ходами первыми.

• Обрезка. Не ищите ходы, которые кажется "очевидно" плохим, согласно некоторые, опять же, эвристические. Это включает в себя риск того, что вы не найдете оптимальное решение больше, но в зависимости от вашей эвристики вы будете очень вероятно, найти его гораздо раньше.

• Хеш-таблицы. Не нужно хранить каждый доска, с которой вы столкнулись, просто помните определенное число и перезаписать старше из них.

Answer 4

Вы можете перевести эту проблему в задачу поиска кратчайшего пути на графе. http://en.wikipedia.org/wiki/Shortest_path_problem

Я бы попробовал с A *, а эвристика включала бы количество островов.

Answer 5

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

Динамическое программирование обсуждается в Руководство по проектированию алгоритмов , но в Интернете также много обсуждается. Вот хорошее вступление: http://20bits.com/articles/introduction-to-dynamic-programming/

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

Answer 6

Я думаю, вы могли бы попробовать поиск по ветке и связать со следующей идеей:

1. Учитывая состояние игры S, вы переходите на S, разбивая его на m наборов Si, где каждый Si - это состояние после выполнения законного хода всех m законных ходов с учетом состояния S

2. Вам нужны две функции U (S) и L (S), которые вычисляют нижнюю и верхнюю границы соответственно заданного состояния S.

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

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

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

Answer 7

Это не моя область знаний, но я бы хотел порекомендовать вам книгу. Получите копию Руководства по разработке алгоритма от Стивена Скиены. У этого есть целый список различных алгоритмов, и как только вы прочитаете его, вы можете использовать его в качестве ссылки. Если ничего другого, это поможет вам рассмотреть ваши варианты.