Узнал о конкурсе от Memetix-а на форуме Google AI contest.
Решил принять участие по нескольких причинам:
- боты пишутся на java, а это моя родная стихия.
- Google AI Contest закончился.
- написать AI для старой известной игрушки - это ли не круто?
- в конкурсе уже учавствовал Memetix (на то время 1е место). По Google AI Contest я знал что он достойный соперник и хотелось побить его :P
Можно сказать это был мой первый опыт написания минимакса (не знаю насколько хорошо получилось).
Об игре.
Очки
1 обычная таблетка: 10 очков
1 таблетка силы: 50 очков
очки за сьеденых привидений от 1 таблеки: 200 (за 1е), 400 (2е), 800 (3е), 1600 (4е)
Таким образом выгодно после сьедения таблетки силы поймать и сьесть как можно больше призраков.
После сьедения привидение отправляется в логово - и спустя некоторое кол-во ходов выползает наружу.
О конкурсе.
Это периодическое соревнование на тему PacMan vs Ghosts, которое происходит с интервалом раз в пол года. Каждую новую итерацию что то добавляют, усовершенствуют правила, движок, и тд.Цели игры состоит в том чтобы написать алгоритм управления PacMan -ом или Привидениями, которые его ловят. Т.е. можно создавать ботов двух типов. На ход отводится 40 миллисекунд, и если бот не укладывается в это время то берется его прошлый ход. Если же в данный момент прошлый ход совершить не получится тогда движок делает случайный возможный ход за бота. Организаторы внесли не большие коррективы в правила для того чтобы не допустить некоторых жульнических стратегий. А именно если призраки сознательно блокируют некоторе участки карты что пакмен физически не может добраться до таблеток то игра может продолжаться бесконечно. Чтобы избежать этого по истечении 3000 ходов на 1 карте Пакмен получает половину очков со всех оставшихся таблеток на карте и начинается следующая карта.. Что-ж, справедливо.
Более подробно о правилах можно почитать на на сайте.
Развитие GreenTea.
Участие начал примерно за 50 дней до дедлана и сконцентрировался на алгоритме для призраков. Всего было 3 реализации.
Наивная реализация.
Наученный Муравьями, в которых рулил поиск в ширину, мне показалось, что и в этой игре данный алгоритм может быть полезен. Идея довольно проста. В начале хода анализируется вся карта для каждой возможной комбинации ходов пакмана и призраков. Анализ хода включает в себя пускание волн поиска в ширину для памена и привидений. Там где волна поиска в ширину натыкается на волы привидений - она останавливается. Всего же поиск осуществляется максимально для некой фиксированной глубины - скажем - в 100 ходов. Так вот, чем больше будет площадь пройденная волной поиска для пакмена - тем лучше для него - и соответственно хуже для призраков. Значит для приведений надо выбрать такой ход для которых при любом ходе пакмена площадь волны поиска пакмена будет минимальной. Данный алгоритм довольно уверенно рвал стартового пакмена, однако против топовых ботов - без шансов - всегда они умудрялись как то ускользнуть. В принципе понятно почему так происходило. Алгоритм то приближенный.
Первый минимакс.
Случайно заметил в игре инетересную особенность, то что приведения не могут разворачиваться на 180 градусов. Только вперед, вправо или влево. Не знаю было ли это в оригинальных правилах игры, но для пакмена это можно сказать единственный шанс выжить. Он 1 а призраков 4 - но зато они менее маневренные. Что это дает? А то что ветвлений в ходах становится на много-много меньше. Раз меньше ветвлений - значит можно просчитать все позиции точно на большую глубину. Идея минимакса была очевидна и я начал изучать классы движка игры, а именно класс Game, хранящий состояние игры. Как выяснилось этот класс был, можно сказать, старательно оптимизирован по используемой памяти, для того чтобы можно было хранить больше обьектов Game и легче их копировать. Что-ж, все было для начала работы, и я бодренько приступил к реализации своего первого минимакса. На первую версию ушло около 2 дней. Было в ней кучу багов, которые я постепенно выпиливал, но все таки работала уже лучше чем наивная реализация через поиск в ширину. Основным преимуществом использования класса Game из игрового движка было то что он точно просчитывает следующий ход, ведет учет всех таблеток, очков и тд. Т.е. достаточно в каждой ноде дерева поиска хранить 1 экземпляр класса Game чтобы потом при генерации ходов получать из него новые экземпляры Game и помещать в чайлдовые узлы дерева. Статический анализ позиции на глубине 0 я делал все тем же поиском в ширину, который использовал в первой реализации.
Второй минимакс.
Сигналом, что я делаю что-то не так, было то, что на сервере мой алгоритм хотя и был в топ 10, все же не показывал отличных результатов как тот же Memetix. Анализ партий показал что глубина поиска у меня примерно под 30 ходов, а это не так уж и много если учесть что в ширину карта занимает 100 ходов. У Memetix-а глубина была побольше. По моим приблизительным прикидкам где то 40-60. Профилирование кода показало, что больше всего времени занимает как это ни странно копирование объекта Game выполнение
хода в том же Game. Так же я был немного шокирован тем насколько интенсивно работает сборщик мусора. Он практически захлебывался от потока объектов Game вышедших из употребления. Также много времени занимал статический анализ позиции поиском в ширину (со временем я его облегчил, но все равно было медленно). Напрашивалось более легковесное решение. Более легкие узлы дерева поиска, упрощенное выполнение хода для генерации следующих ходов. И я выкинул Game! Вместо него завел несколько классов: ComplexMove состоящий из хода пакмена и массива ходов призраков. Position позиция пакмена и массив позиций привидений, в последствиии были добавлены массив времени пока призраков можно съесть и массив времени пока призраки в логове. Учет сьеденных таблекок вообще не вел, т.к. посчитал что это будет слишком расточительно по памяти - а толку от него не много. Статический анализ позиции сделал намного проще: рассчитывались несколько параметров вроде: среднее растояние от пакмена до приведений, минимальное расстояние до привидения, среднее расстояние между привидениями (лучше больше - чтобы они не кучковались) и тд. И все эти простые оценки с некоторыми весами суммировались в общую оценку. Постепенно исправлялись баги и мой бот начал набирать обороты на сервере - закрепился где-то в районе
топ 3, а глубина поиска возросла где-то в среднем до 40.
Делаем пакмена.
Сделать реализацию пакмена из имеющейся для призраков оказалось делом нескольких часов. По суди достаточно было взять из лучшего хода - ход для пакмена. Сам алгоритм остался почти неизменным. Основными отличиями было то что для призраков взятие силовой таблетки оценивалось всегда в 0 очков (чтобы призраки были более агрессивны, даже если пакмен близок к ней), а для пакмена оно высчитывалось по расстояниям до призраков. Грубо говоря если расстояния большие - то брать не стоит. А если маленькие - тогда брать, т.к. можно будет догнать ослабленных призраков.
Странные баги пакмена.
Иногда пакмен совершал странные суицидальные ходы, когда за ним гнались по пятам. Хотя убежать можно было. Об этой проблеме я подробно изложил на форуме конкурса. Кратко говоря, это случалось из-за того что временами срабатывал сборщик мусора в самый ответственный момент. Время сборки может быть от 50 до 500 мс. А это 1-10 игровых ходов.. Не правильный ход очень критичен для пакмена - потому что он означает мгновенную смерть, и не так важен для привидений (не словили сейчас - словим потом). Ирония в том что сборка мусора оставленного ботом призраков может повлиять на вызов сборщика мусора, что приведет к неправильному ходу пакмена (поскольку боты в начале конкурса запускались в 1 виртуальной машине). Таким образом можно непреднамеренно жульничать за призраков. Потом эту проблему немного облегчили тем что добавили возможность выставлять результирующий ход для бота до завершения хода (40 мс), предохраняя от ситуации что из-за сборщика мусора этот ход не будет найден вообще. А возможность косвенного влияния ботов друг на друга из-за сборщика мусора кардинально решили разделением выполнения ботов по разным виртуальным машинам. Эта проблема заставила задуматься.. Готов ли я поиграть в русскую рулетку с пулей в виде сборщика мусора? Он может сработать а может не сработать -ситуация не из приятных..
Оптимизация работы с памятью.
Профилирование памяти показало что даже выкинув класс Game из узла дерева поиска, нагрузка на систему памяти и сборщик мусора была очень большая. Не удивительно, каждые 40 мс выкидывалось в трубу почти половина дерева. В котором может быть до 20000 узлов. И все это надо принять и обработать в сборщике мусора. Идея это исправить была следующая. Зачем пересоздавать узлы поиска, если их можно повторно использовать? Мне известно место где где я удаляю более не действительное поддерево дерева поиска - в начале каждого хода. Значит в этом месте можно просто пройтись рекурсивно по этому поддереву и положить каждый из его узлов в пул. А потом вместо того чтобы каждый раз создавать новый узел просто запросить свободный узел из пула. Я быстро реализовал эту идею и потом еще потратил уйму времени чтобы найти в коде "утечки" в других местах. Всякие создания временных списков/массивов. Все это ушло в статические переменные, которые использовались повторно. Да, получившийся код не является образцом ООП, но зато он эффективен в плане использования памяти. Эта оптимизация очень существенно сказалась на игре бота - он стал более стабилен, в среднем стал создавать больше узлов и просчитывать больше позиций.
Улучшения связанные с генерацией ходов
В узле дерева поиска, в фазе генерации ходов, если призрак находится на расстоянии более 100 ходов от пакмена то в фазе генерации ходов он всегда совершает 1 ход - по направлению к пакмену. Это уменьшает ветвление минимакса.
Также при генерации ходов пакмен делает не все из возможных ходов - если текущее положение не перекресток, то он двигается только прямо, как и призрак. На перекрестках же, или перед таблетками силы пакмен может повернуть в любом направлении. Эта небольшая оптимизация сильно уменьшила ветвление минимакса, без существенных потерь (как мне показалось).
Одно из последних улучшений заключалась в том пакмен не поворачивает в некотором направлении, если в коридоре на него движется призрак. Это проверяется заранее в той же фазе генерации ходов.
Другие замечания по минимаксу
Глубина поиска растет постепенно, это позволит находить лучший ход вначале на малой глубине (это считается очень быстро). Потом постепенное наращивание глубины с использованием того же дерева поиска в виде отправной точки.
Так и не догадался как прикрутить оптимизацию вроде альфа бета отсечения. Т.е. я считаю все ветки. Трудно это сделать потому что если в шахматах ходы совершаются по очереди то тут они делаются одновременно. Также аргументом против альфа беты есть то, что если мы, к примеру, отбросим некоторую ветку, то не факт что там нету ходов для призраков которые неотвратимо ловят пакмена. Или я просто не вник в альфа-бету как следует. Будет интересно посмотреть сумел ли кто-то ее реализовать в данной задаче.
Эпилог
Посмотрим чем все это закончится. Пока я считаю что у моей команды призраков есть неплохие шансы взять 1е место. Но и соперники тоже очень сильные. Все будет зависеть от отдельных игр с топ ботами пакменов. В этом компоненте кажется мой бот не очень силен. Пакмен GreenTea сейчас в районе 10 го места - на него я не рассчитываю. Все таки основные силы были брошены на призраков.
Хотелось бы поблагодарить разработчиков движка за хорошую работу - класс Game написан замечательно, все основные операции кешируется.. в общем все продумано как следует. Молодцы ребята. На форуме отвечают оперативно и к советам игроков - прислушиваются. Получил удовольствие от участия, за что им большое спасибо :)
Комментариев нет:
Отправить комментарий