Какой алгоритм я должен использовать для этой игровой задачи?
У меня есть игра-головоломка на основе сетки, основанная на состояниях. Мне нужен алгоритм, который может найти решение для каждого игрового уровня. Уровень игры начинается в определенном состоянии и заканчивается в уникальном, хорошо известном состоянии, поэтому мне нужно найти путь перехода из начального состояния в конечное.
Каждый объект в игровой сетке можно перемещать в 4 направлениях и останавливать только при столкновении с другим объектом; и каждый ход представляет собой уникальное, четко определенное состояние. Уровень игры решен, когда все объекты расположены в заранее определенных местах, что является частью игры-головоломки. Правила игры чрезвычайно просты, но найти решение для уровня кажется очень сложным.
Спецификация проблемы
- Каждое состояние не может быть случайно предсказано или сгенерировано. Оно должно происходить из (быть потомком) другого предыдущего состояния.
- Не существует эффективного способа измерить, насколько мы близки к целевому состоянию. Мы знаем, что достигли конца, только когда находим его.
- Возможных состояний может быть слишком много. В среднем на каждый уровень игры приходится около 32^100 возможных состояний.
- Многие государства имеют производные состояния, которые также являются их наследственными состояниями. Например, мы можем застрять в цикле, который никогда не заканчивается.
- Мы не можем пройти состояния от цели к начальному состоянию, т. е. мы не можем вернуться назад.
- Многие состояния могут привести к тупику, где невозможно достичь конечного состояния.
- Количество состояний на уровень ограничено — т.е. количество перемещений объекта на уровень игры ограничено, поэтому найденное решение должно быть в пределах этого лимита.
Что я пробовал
- Я попробовал пользовательский алгоритм грубой силы на основе дерева, но возможных состояний слишком много. Этот алгоритм хорошо работает для более простых игровых уровней и может найти кратчайший путь между двумя состояниями. Однако для сложных игровых уровней (а таких уровней большинство) этот алгоритм не работает, потому что это перебор.
- Я попробовал генетические алгоритмы. Хотя не существует эффективного способа измерить, насколько мы близки к целевому состоянию, есть некоторая оценка, которую можно получить, когда определенные объекты перемещаются определенным образом. Более высокий балл означает, что мы ближе к конечному состоянию, но также можем завести нас в тупик, что и происходит в большинстве случаев, поскольку игровые уровни специально разработаны для этого. Я использовал этот показатель в качестве меры физической подготовки. Генетический алгоритм более-менее хорошо работает на простых игровых уровнях, но ненадежен на большинстве сложных. Кроме того, из-за характера проблемы я не могу придумать, как реализовать кроссовер; и мутацию также очень сложно реализовать.
- Я рассматривал (но не пробовал) некоторые алгоритмы поиска пути, такие как A*, но они полагаются на вопрос «насколько мы близки к цели?» свойство, которого эта проблема на самом деле не имеет.
Итак, перед лицом такой проблемы существует ли алгоритм, который является хорошим кандидатом для поиска решений для этих игровых уровней? Я полагаю, что для этого хорошо подошли бы подходы глубокого обучения, но это было бы слишком для этой игры, поскольку аппаратные ресурсы несколько ограничены.
РЕДАКТИРОВАТЬ 1 — Пример сторонней игры
Игра, которую я делаю, по идее похожа на эту игру. Эта игра основана на игре под названием Q, которую я знаю только по старому сотовому телефону Sony Ericsson — одной из первых моделей сотовых телефонов с цветным экраном. Игра, которую я привожу в качестве примера, находится в Microsoft Store и является единственной копией, которую я смог найти; Я не мог найти онлайн-версию, извините за это. Игра, над которой я работаю, имеет те же правила, но имеет дополнительные объекты, которые добавляют другие правила, чтобы сделать игру более интересной (например, объекты, которые заставляют шары останавливаться, объекты, которые заставляют шары менять направление и т. д.).
Если вы играете в нее, вы можете заметить, что человек решает ее, в основном, используя разум, потому что каждый уровень имеет разную геометрию стен, некоторые шары нужно вставлять в свои слоты в определенном порядке, чтобы уровень можно было решить, и т. д. , С дополнительными объектами, которые добавляют больше сложности, решение уровней требует от человека понимания некоторых ключевых ингредиентов, характерных для этого уровня. Например, иногда мяч застревает в каком-то месте, и ключ может использовать один из других шаров вместе, чтобы вытащить его оттуда. Есть несколько основных стратегий, которые полезны для большинства уровней, но сами по себе они не могут решить уровни. Самые простые уровни довольно легко решить, но есть такие (обычно самые интересные), которые требуют от человека сообразительности, разума и некоторого творчества, чтобы поместить все шарики в соответствующие слоты.
К сожалению, игра, над которой я работаю, находится в стадии разработки и еще не работает в визуальной части, поэтому я пока не могу использовать ее в качестве примера.
РЕДАКТИРОВАТЬ 2 — Некоторые примеры игровых уровней
Мне удалось сделать несколько фотографий некоторых уровней для игры. Они следующие, в порядке жесткости (ну, более или менее):
Этот уровень достаточно прост. Шарики можно забивать в квадраты соответствующего цвета, как в примере игры стороннего производителя выше.
Этот уровень не очень сложный, но мина в центре усложняет его. Мины — это объекты, над которыми нельзя перемещаться, иначе вы проиграете.
Этот уровень сложен, потому что шары застревают в геометрии уровня, и ключом к успеху является избегание забивания шаров. Чтобы решить этот уровень, необходимо тесное сотрудничество между всеми шарами.
Этот уровень ограничен максимум 60 ходами. Это то, что делает это немного сложнее. Магниты заставляют шары останавливаться при перемещении, но они расходуются (т.е. одноразовое использование). Квадрат в центре — это слот Iris — в него можно забить любой шар. Ключом к решению этого уровня за максимальное количество ходов является разумный выбор маршрутов мячей.
Это самый сложный уровень в этих примерах. Сапоги (выбираемый предмет) после использования добавляют 10 дополнительных ходов к лимиту ходов. Три предмета ботинка добавляют в общей сложности 30 дополнительных ходов. Чтобы решить уровень, вам нужно их потреблять, иначе у вас закончатся ходы. Но если вы пойдете за ботинками, вам также придется потратить несколько ходов, так что это требует тщательной стратегии. Маленькие мозги и X2 — это просто необязательные предметы, которые дают некоторый балл.
Моей первой мыслью для решения этой проблемы действительно была A*
Я не могу сказать, осуществимо это или нет, так как это действительно зависит от количества состояний, количества шагов, чтобы туда добраться, и от того, насколько хорошо эвристика работает для этой конкретной проблемы. Пример уровня поможет.Я рассматривал (но не пробовал) некоторые алгоритмы поиска пути, такие как A*, но они полагаются на вопрос «насколько мы близки к цели?» свойство, которого эта проблема на самом деле не имеет.
Я хочу бросить вам вызов здесь. Что вам нужно, так это хорошая эвристика, чтобы дать вам нижнюю границу количества ходов, необходимых для перехода к решению.
Предполагая, что ваша игра похожа на эту игру, существуют разные способы использования эвристик, обеспечивающих более низкие оценки.
Некоторые из них могут включать в себя более простые алгоритмы решения проблем.
Одной из таких эвристик может быть:
Для каждой фигуры рассчитайте минимальное количество ходов, чтобы довести ее до целевого состояния, при условии, что все остальные фигуры расставлены наиболее удобным образом.
Сумма ходов, необходимых для каждой фигуры, является нижней границей общего количества необходимых ходов.
Будет ли этого достаточно, чтобы найти решение в вашем конкретном случае, трудно сказать без конкретного примера.