Tuesday, April 08, 2014

Бомбим недругов с помощью A* search

Примерно год назад я прошел интересный онлайн курс от университета Berkley по основам искуственного интеллекта. Курс так и называется Artificial Intelligence (код CS188.1x). Было весело, лектор много юморил и в шутливой форме доходчиво объяснил много полезных алгоритмов и подходов к решению задач ИИ. В качестве лабораторных надо было написать бота для старой доброй игры Pacman, что было очень забавно.
Одним из первых базовых алгоритмов мы рассматривали A* search. Его я и применю в реализации бота для нашей игрушки bomberman. Кстати, программу, которая управляет персонажем игры правильнее называть агентом, а не ботом ;)

Вкратце что из себя представляет A* search.

Поиск А* - это алгоритм нахождения оптимального пути в графе. Хорошо подходит для поиска оптимального маршрута из пункта А в пункт Б. Я воспользуюсь известным примером "путешествие по Румынии" (tour by Romania), чтобы в 2х словах пояснить как это работает.
Задача. Нам нужно на йти кратчайший маршрут из города Арад (Arad) в Бухарест (Bucharest). Можно перебрать все варианты, но в случае большой карты это займет много времени.

Для реализации поиска с помощью A*, нам понадобится расчитать две величины для каждого пункта:
1. Эвристика. Расстояние от текущего города до Бухареста по прямой. На карте это расстояние не указано, оно есть в полной версии здесь.
2. Стоимость. Реальный пройденный километраж. Он обозначен на карте числами между пунктами.

Алгоритм


1. Берем все соседние с Арадом пункты (Zerind, Sibiu,Timisoara). Эти пункты называются successors.
2. Вычисляем эвристику для каждого пункта. Допустим для Zerind значение эвристики равно 374, для Sibiu 253, для Timisoara 329.
3. Складываем значение эвристики со стоимостью и помещаем successor в сортированную коллекцию. Эта сортированная коллекция в A* имеет название "фринж" (fringe). Т.е. соседние с Арадом пункты разместятся во фринже в таком порядке : Sibiu (253 + 140 = 393), Timisoara (329 + 118 = 447), Zerind (374 + 75 = 449).
4. Берем из фринжа первый пункт (Sibiu) и повторяем все, начиная с п.1 до тех пор пока мы не достигнем Бухареста или фринж не опустеет. Состояние "мы в Бухаресте" есть наша цель или по научному "goal state".

Здесь можно посмотреть пошаговое вычисление маршрута в задаче "tour by Romania": http://bit.ly/1hy3ezD

Важные свойства эвристики
1. Эвристика должна быть "допустимой" (admissible). 
\(\forall N, h(N) \leq C(N)\) 
где 
\( h(N) \) - значение эвристики в пункте n
\( C(N) \) - реальная стоимость из пункта n в goal state

2. Эвристика должна быть консистентной (consistent)
\( h(N) \leq C(N,P) + h(P) \) и \( h(G) = 0 \)
где 
\( h \) консистентная эвристика 
\( N \) любой пункт в графе 
\( P \) пункт, предидущий N 
\( C(N,P) \) стоимость перехода из пункта P в пункт N 

Реализация агента


Перед тем как сесть ваять код нужно ответить на несколько вопросов
- какие пункты считать "соседними" (successors) ?
- что будет нашей целью поиска (goal state) ?
- какую эвристику использовать ?
- как расчитывать стоимость передвижения?

Определяем соседей (successors)
Бомбермен может двигаться и ставить бомбы. Он так же может пропустить ход. 
Successor - это состояние игрового поля после того, как бомбермен сделает одно движение или поставит бомбу (или же пропустит ход). Так же нужно учитывать, что бомба взрывается через 5 секунд и ее осколки разлетаются в радиусе 3х шагов. 
Для состояния доски я создал класс GameState (ссылка на репозиторий). GameState может вернуть список доступных действий для бомбермена (метод getLegalActions) и вернуть новое состояние после того, как пойдет бомбермен (метод generateSuccessor(Action action))

Каким будет Goal state?
Поскольку A* - это алгоритм поиска, то надо определить что мы ищем. Я буду искать маршрут, где конечный пункт - забомбленый чертик (мы его зовем chopper).

Какую эвристику использовать?
Если я хочу забомбить ближайшего ко мне чертика, то в качестве эвристики для простоты можно использовать manhattan distance от бомбера к ближайшему чертику. Здесь, правда, пришлось немного пошаманить, т.к. после того, как бомбермен поставил бомбу пришлось быстро от нее убегать. Код эвристики реализовал в классе NearestChopperToBombHeuristic 

Как расчитывать стоимость передвижения?
Вообще расчет стоимости в данном случае - это задача не совсем тривиальная, т.к. необходимо учесть несколько параметров:
- "стоимость" установки бомбы. Т.е. должно быть выгоднее ставить бомбу ближе к чоперу
- передвижение бомбера (чтобы как минимум соответствовать эвристике)
- опасность быть убитым осколками
Можно еще учесть массу других параметров, например, таких как опасность быть съеденым или стоимость разбомбленной стенки и т.д. Но чем больше параметров, тем сложнее их использовать в общем подсчете стоимости поскольку приходится уравновешивать взаимоконфликтные вещи. Например уровень опасности быть съеденым запросто может конфликтовать со стоимостью установки бомбы. Ведь для того, чтобы поставить бомбу рядом с чертиком нужно рискнуть и подойти очень близко.
В общем со стоимостью пришлось немного поэкспериментировать. Пришлось даже написать небольшую песочницу, которая показывает найденный маршрут. Подсчет стоимости реализован в классе Problem, см. метод cost.

Что получилось

Нагляднее всего продемонстрируют картинки. Вот пара вариантов расчета из песочницы:




Для начала неплохо, но можно еще тюнить, подбирать коэффициенты и вводить новые параметры в функцию стоимости. Но налицо несколько ограничений:
- хорошо работает для статики. Хорошо, когда чоперы не пытаются тебя скушать, а другие соперники не подкладывают под тебя бомбы :). В случае, если это не так, приходится каждый раз расчитывать новый маршрут.
- Алгоритм не смотрит дальше Goal state. В случае бесконечной игры вариант "убить чертика, а там хоть трава не расти" часто заканчивается тем, что бомбермена съедают как только он поставил бомбу под чопером
- сложная функция стоимости. Как я уже указывал, в стоимость приходится закладывать множество параметров и искать баланс приоритетов между ними.

Ресурсы

1. Онлайн курс университета Беркли по ИИ Artificial Intelligence (код CS188.1x)
2. Пример "Tour by Romania" в формате PowerPoint можно скачать здесь
3. Тот же пример в формате PDF можно скачать здесь
4. Мой гитхаб репозиторий с исходниками (еще будет меняться:)) https://github.com/szelenin/bomberman
5. Онлайн игра bomberman на нашем игровом портале Codenjoy