PacMan: какие виды эвристики используются в основном?

Question

Кроме A *, BFS, DFS и т. Д., Какие еще хорошие алгоритмы / эвристики для поиска путей широко используются в Pacman? Я не думаю, что те, что я упомянул, сработают, если pacman найдет больше одного плода.

Мне нужны хорошие алгоритмы поиска пути, которые PacMan может использовать, чтобы закончить лабиринт с наименьшим возможным количеством шагов. Я пытался найти ориентир, но пока не повезло. A * с манхэттенским расстоянием упоминается повсеместно, но он будет работать только с лабиринтами, у которых есть только один (или два? Или, может быть, несколько?) Фруктов.

Кстати, для простоты, при условии, что вокруг нет призраков.

Некоторые примеры из оригинальных задач PacMan: Первый , Второй и Третий

Answer 1

Эвристика, которая сработала для меня, если вы знаете вид лабиринта:

1. Найдите реальное расстояние между двумя самыми далекими на данный момент фруктами в лабиринте - назовем это x.
2. Найтиреальное расстояние от текущей позиции Пакмана до ближайших двух предыдущих фруктов - назовем это y.

Тогда ответ будет просто: x + y.

Обратите внимание, что реальные расстоянияэто не манхэттенские расстояния, а real расстояния в лабиринте - вы можете рассчитать это (даже если пересчитать, если хотите), потому что вы знаете вид лабиринта (вы знаете все стены, ...).Эта информация (реальное расстояние между двумя точками в лабиринте) статична, потому что стены не меняются.

Интерпретация этой формулы x + y может выглядеть примерно так:

• x - в любом случае вам придется пройти это расстояние, по крайней мере, в конце
• y - пока вы находитесь в двух самых дальних фруктах, лучше собирать еду рядом с ней, чтобы вам не пришлось возвращаться

Если вы решаете это как часть проекта класса AI Беркли, для вычисления реального расстояния между двумя точками вы можете использовать функцию mazeDistance(pos1, pos2, gameState), которая уже реализована и использует вашу реализацию bfs.Кроме того, эта эвристика является допустимой и последовательной , по крайней мере для их тестовых случаев.Кстати, с помощью этой эвристики мне удалось расширить только 376 узлов в trickySearch лабиринте.

Answer 2

Ваш комментарий говорит, что вы ищете кратчайший путь .Эта проблема является вариацией TSP на плоском графике и, таким образом, NP-Hard .

Возможная эвристическая функция для A*, которая может решить проблему, ноне допустимо [таким образом, найденный путь не гарантированно будет оптимальным]:

Сумма расстояний в Манхэттене от всех фруктов до агента.

Вы также можете использовать допустимую эвристику, #fruits - но это займет много времени.

Если вы ищете оптимальный, ну, это сложно.Вы можете попробовать все перестановки фруктов и проверить общее расстояние, которое вам нужно пройти.Это решение учитывает факторного числа плодов , и если оно больше 20 - с наивной грубой силой - это займет слишком много времени.Вы можете как-то улучшить его, уменьшив проблему до TSP , и использовать решение с динамическим программированием, которое также является экспоненциальным, или некоторые эвристические решения для TSP.

---

Можно такжеулучшить недопустимое эвристическое решение, чтобы обеспечить алгоритм в любое время :

итеративный запуск A* с убывающей эвристической функцией :h(v) = h'(v) / m, где h' - эвристическая функция на последней итерации A *, а m > 1.Это гарантирует, что в какой-то момент ваша эвристическая функция h будет допустимой - и найденное решение будет оптимальным.Однако ожидается, что каждая итерация займет намного больше времени, чем предыдущая [экспоненциально длиннее ..]

Answer 3

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

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

Итак, вкратце: эвристический = mazeDistance (моя позиция, по оценкамближайшая еда) + пропущенные баллы

Это было допустимо и последовательно.С этим я расширил 5500 узлов и получил 5/4 на FoodHeuristic.https://github.com/sukritiverma1996/Intro-to-AI-course

Answer 4

Я знаю, что это старо, но, вероятно, есть много других людей, которые хотят решить эту проблему (это часть бесплатного ИИ-класса Беркли).Есть много предложений о грубой силе, поэтому я внесу довольно простое предложение, которое будет довольно близко и ДОСТУПНО :

1. Найти ближайший фрукт
2. Удалите этот фрукт из списка оставшихся фруктов и добавьте расстояние к итогу
3. Найдите ближайший фрукт к этому фрукту
4. , вернитесь к шагу 2 и повторяйте, пока не останется больше фруктов
5. вернуть сумму

edit: Предыдущее утверждение, что это допустимая эвристика, неверно.Извините!

Answer 5

Вы можете перебрать его для небольшого количества фруктов в лабиринте разумного размера.

• Создать график с узлом для каждого кусочка фруктов в лабиринте.
• Использование* Или аналогичный, чтобы найти расстояние между каждой парой фруктов.(Вам понадобится O(n^2) прогонов A *, чтобы получить все попарные расстояния между n фруктами.)
• Свяжите узлы (фрукты) в графе с ребрами, взвешенными по расстоянию.
• Найдите самый дешевый цикл на графике (посещение всех узлов хотя бы один раз) методом грубой силы.См. Самая низкая стоимость путешествия на полном графике.

Answer 6

Предполагается, что это для AI проекта Беркли:

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

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

Для получения более подробной информации, см. Это сообщение .

Answer 7

в данном игровом состоянии, скажем, md(x) - это манхэттенское расстояние от pacman до узла x, рассмотрим minmd(X) как функцию, которая возвращает xmin st md(xmin)<=md(x) для всех x в X,пусть X будет набором продуктов, которые pacman должен есть.

Тогда подумайте - если вы подумаете об отдыхе в вашем pacman-мире, в котором нет стен, pacman не может пройти меньше чем md(xmin) где xmin=minmd(X) есть какой-нибудь фрукт, а затем, если он хочет съесть другой фрукт, он должен пойти не менее чем md(xmin1), где xmin1=minmd(X-{xmin}) и так далее.верните сумму пройденного mds pacman от xmin до xmin1 до xmin2 и так далее, и так как это оптимальное решение для релаксации, вы получите великолепную допустимую и cosistent эвристическую функцию!

Еще один момент, на который стоит обратить внимание, это то, что вы даже можете улучшить эвристику, если учесть стены, это гораздо более сложная проблема, поэтому я не стал вдаваться в подробности, но я заметил, что если вы связали pacman в прямоугольниксо следующим оптимальным плодом ему придется заплатить еще как минимум 2 действия, если между ними будет какая-то ПОЛНАЯ вертикальная или горизонтальная линия стены, потому что ему придется выйти из ограничивающего прямоугольника и снова войти в него, выполнив при этом как минимум 2 действия.для каждой такой стены.Это может быть дополнительно изучено, и вы также можете найти больше специальных функций в этом прямоугольнике.

Answer 8

Если вы хотите уменьшить количество расширенных узлов и не заботитесь о времени выполнения, я бы рекомендовал использовать Минимальное связующее дерево, стоимость ребра должна быть mazeDistance и использовать priorityQueue, каждый раз добавляя узел в посещаемый узел. ищите ближайший узел к только что добавленному узлу, а затем добавляйте его к посещенному узлу, пока весь пищевой узел не будет добавлен в посещаемый узел. Если вы работаете с проблемой курса ИИ, развернутый узел должен быть очень низким.