English version of this post
Пока пишу этот пост финалы Google AI Conteset 2011 - Ants в самом разгаре. Организаторы постепенно отключают более слабых ботов чтобы более сильные имели возможность больше поиграть. Судя по таймеру расположенному на сайте http://ants.aichallenge.org до объявления победителя остается, 1 день 5 часов 35 минут и 5, 4, 3, 2.. секунд.
Ах да, о чем это я. В данный момент мой бот GreenTea пребывает на 3ем месте из 7897. О нем и пойдет речь в данном посте. Даже не знаю с чего лучше начать, столько труда и времени было в него вложено, с самой первой беты, когда еще не было нор.. уже тогда я начал.
Так получилось что в этом году фаза бета версии затянулась непростительно долго. Это сильно подорвало мою веру в энтузиазм и open source. Потом внезапно разработчики написали на сайте Sponsored by Google и очень резко засуетились, начали шевелится и что-то коммитить. Ну что ж, хорошо хоть так :) - я уж было подумал что так и заглохнет на стадии беты.. И все это время беты (уже не помню сколько, 4 месяца?) я кодил, что-то потихоньку допиливал и улучшал.
За что люблю этот тип соревнования, то что времени - МНОГО! Можно не спеша, не торопясь сесть, все продумать, поробовать, протестировать, поменять.. еще 5 раз поменять, еще протестировать, и т.д. Вобщем, наслаждаться программированием в моем понимании :)
Начну по порядку, и постараюсь придерживаться хронологии событий.
Механика игры.
Имеется замкнутая сама на себя прямоугольная карта определенного размера. Замкнутая в том смысле что уходишь влево - приходишь справа, уходишь вниз - приходишь сверху и т.п. Каждый игрок начинает с некоторым количеством начальных нор и 1 муравьем возле каждой норы. Каждая клетка поля может быть либо землей, либо непроходимой для муравья водой. Муравьи должны собирать еду - за каждый собранный кусочек из случайно норы появляется новый муравей. Он видит в неком радиусе, так что заранее не известно что за ним - нужно исследовать. Еда появляется случайным образом. Если муравьи разных игроков после хода оказались в радиусе атаки, то происходит бой между ними. Правила разрешения боя обьяснить не так уж просто, достаточно сказать что в среднем, меньше убитых муравьев окажется у того игрока, чьих муравьев оказалось больше в бою. Чтобы захватить нору надо на нее стать. За убитую нору дают 2 очка. За потерю своей норы отнимают 1 очко. Так что если если выбор захватить вражескую нору или потерять свою следует предпочитать первое, только если своих нор >1. На каждом ходу бот должен выбрать куда походить каждым из муравьев. Да забыл сказать что карты симметричные, и еда появляется также симметрично для всех, чтобы было по честному. Все! Вот такие не хитрые правила. В отличии от войны планет, где толком не понятно было что делать и как ходить, данную игру легче разбить на подзадачи и решать их по отдельности. Ну к примеру очевидно что надо бежать за едой, равномерно распространяться по карте и наваливаться на врагов большим количеством своих муравьев. Но в том то прикол, что легче и понятней стало всем, а поэтому из-за большей конкуренции сложность ни капельки не убавилась.
Мой инстументарий.
Java. Я - java разработчик. Этот язык достаточно прост и быстр. Позволяет с большой скоростью фигачить тонны кода (если надо реализовать какую-то свежую идею) не заботясь о каких-то системных вещах типа утечек памяти (привет C++ !!).
Поэтому для написания бота выбрал джаву. Где-то в средине беты ради веселья попытался переключится на lisp sbcl. Не получилось.. Мой алгоритм поиска пути, идентично релизованный на лиспе работал в 5 раз медленнее чем на java. Возможно это от моего не достаточно хорошего знания лиспа...
IntelliJ idea Comunity edition. Замечательная среда разработки. Нареканий в процессе работы практически не было. Один раз слетел кеш, и весь код пестрел якобы "ошибками" компиляции. Пришлось почистить кеш руками и перезапустить.
git. Системы контроля версии мне очень не хватало в Planet Wars. Ошибки были учтены и я сразу начал коммитить в git. Он меня покорил своим богатством возможностей и скоростью работы (по сравнению с svn).
Скрипты на perl. В прошлом соревновании Planet Wars я наваял скрипты для автоматического тестирования своего бота со своим же ботом более старой версии. Грех было не воспользоваться ими! Правда пришлось немного переделать скрипт чтобы приспособить его к картам с несколькими игроками в так называемом режиме FFA (Free For All) - каждый сам за себя.
Например:
После 3 игры FFA бот:
- выиграл у 1.5 ботов и прогирал 4.5 ботам (+ 0.5 прибавляется к победам и поражениям за ничью)
- Набрал 0 очков, 2.16 - среднее кол-во очков у остальных ботов.
И суммарная информация:
- побед за все игры: 4.5 (45%),
- поражеий - 5.5
- очков в сумме набрано за все игры: 4 (52.2%),
- сумма средних очков по всем оппонентам: 3.66.
Подобная информация выводится после каждой игры. Таким образом можно протестировать стал ли бот действительно играть лучше в играх типа FFA или нет.
Таблицы в google documents. Там я вел учет сделанным улучшениям, версиям бота и тестированию этих версий друг с дружкой, на разных наборах карт, и при различных режимах появления еды.
Sampling profiler hprof. Эта штуковина сыграла мне большую службу. Забегая на перед, примерно за 2 недели до конца, мой бот еще очень много падал по таймауту (превысил 500 мс отведенных на ход). Я не мог понять почему это происходит. С первого взгляда код чист и идеален, прогон входных данных взятых с игры на которых бот отвалился по таймауту показывает что бот успевает сделать ход ( к примеру за 300мс ). Так почему же он падает на сайте? Я уже начал думать всякую мистику, типа сборшик мусора запускается по среди игры в произвольное время, и выполнение приостанавливается. Возможно это отчасти и правда, но дело оказалось проще. Как то неожиданно наткнулся на hprof. Он вешается как агент к java-е (как то так -agentlib:hprof=cpu=samples,interval=10,depth=10), и в процессе работы (в моем случае это прогон данных поступавших на вход боту, к примеру на 200 ходах игры) собирает статистику где управление задерживается чаще всего. И с помощью этого нашел много достаточно не очевидных мест, работавших медленно. Какой то старинный код который можно было в 10 раз упростить! - та много чего. В результате после моих фиксов бот стал работать примерно на 40% быстрее и все таймауты на официальном сайте пропали.
Рождение и эволюция.
Молодые не помнят, а я помню, что начиналось все на открытых картах. Муравьи были кочевниками и не имели нор. Да и зачем норы если муравей рождается из кусочка еды? На таких свободных паздбищах проходило детство и юность GreenTea. В начале, когда он был еще совсем мал, ходил за едой по прямой линии то и дело натыкаясь на стенки. Порою застрянет в в них, трепыхается а вырваться не может. Потом научилсяходить находить кратчайший путь к еде..
Первое что реализовал это равномерное расхождение по открытой карте. Правило идти туда где нет моих муравьев реализуется достаточно просто. Находим N ближайших муравьев и строим вектора от них к текущему муравью. Приводим каждый вектор к размеру 10 (магическая константа). Следующий ход следует сделать в направлении суммарного результирующего вектора. N может варьировать. чем она больше тем более плавным будет расхождение муравьев, но требует больших затрат на вычисления, что начинает быть заметным на поздних стадиях при больших количествах муравьев.
Потом был поиск пути. В гугл честно не смотрел, пытался сообразить сам. Первый алгоритм получился жадным, рекурсивным, и надо признать, не очень быстрым. Но этого было вполне себе достаточно для начала.
Но не долго продолжалось беззаботное детство на свободных просторах. То и дело вокруг начали появляться другие муравьи, также хорошо умеющие искать еду идя не по прямой линии а кратчайшим путем, и они почему то не хотели жить в мире..
Второе что я реализовал это калькулятор боя. Дело в том что во время беты правила разрешения боя были еще не стабильны, как и радиус атаки. Поэтому надо было написать что-то более менее универсальное, чтобы потом не переписывать лишний раз. Я не придумал ничего умнее чем перебор всех возможных ходов для своих и вражеских муравьев которые могут столкнуться в бою. И выбор из всех возможных комбинаций моих ходов такой, чтобы не нашлось вражеского хода способного одним махом погубить мою группу бойцов. Если таких "безопасных" ходов несколько, то из них выбирается такой, который, так скажем, создает наибольшее количество проблем для соперника. Тоесть, двумя словами, ищется самый агрессивный из самых безопасных ходов. Эти два понятия чаще всего взаимоисключающие, но безопасность всегда стоит на первом месте. Изначально калькулятор боя был настроен на группы муравьев (моих + вражеских) не больше 7. Это максимально 5^(7)=78125 возможных ходов. На практике, при наличии рядом стоящих муравьев, и воды комбинаций конечно меньше. Если будет 8 - то это гарантированный таймаут.
И поняли муравьи что вместе они сила. И начали истреблять врагов, рубить в капусту, без жалости и злости.
Насколько помню калькулятор боя в сочетании с поиском пути и равномерным распространением дал то, что муравей GreenTea сразу поднялся в топы на бета версии сайта. Редко какой соперник мог выдержать бешеного микро которое просто работало идеально, ведь перебирались все возможные ходы! Для групп муравьев >8 был написан примитивнейший алгоритм. Но он включался довольно редко, т.к. для отрытых картах редко скапливается действительно большое количество муравьев, хотя так было до поры до времени (об этом ниже).
Улучшения.
Кто то может со мной не согласится, но мне кажется что муравьев отличает от войны планет то, что улучшения делать значительно легче. Происходит это от того, что когда смотришь повтор боя - сразу видно где ботом была допущена ошибка. Вобщем-то так и производилось большинство улучшений: смотрим повтор "ага - тут затупил и потерял муравья, тут криво пошел, тут собрался в кучу хотя надо было расходится в разные стороны и искать еду.." В планетах была жесткая математика и точный подсчет. Одна ошибка - и все, конец. Тут же можно ошибаться по несколько раз, можно совершать хорошие ходы а можно и средние, и это еще не означает проигрыш. Но все таки побеждает тот, кто совершает меньше ошибок.
Всего, судя по таблице в google docs-е у моего бота с начала беты было 76 улучшений. Каждое из которых было протестировано на разных наборах карт и при разных распределениях еды и давало примерно от 3% до 15% прироста количества побед в боях 1 на 1 со старой версией без улучшения, и от 1% до 10% побед в боях FFA.
Попробую привести тут самые значимые улучшения начиная с беты, когда еще не было нор. Почему именно оттуда - потому что там было сделано много важных улучшений которые в последствии повлияли на отличную игру на открытых картах, даже при наличии нор.
u4. Улучшение поиска пути - найденный путь должен больше напоминать прямую линию.
Хех. Моя первая корявая реализация поиска пути находила кратчайший путь но он на глаз оказывался слегка кривоватым.
u6. При поиске еды и противников использовать для расчета расстояния использовать
честный минимально возможный путь.
u9. Калькулятор боя
О нем см. выше.
u11 Собирать еду перед атакой.
Скорость роста популяции зависит от текущего его размера. Поэтому критически важно как можно быстрее получить нового муравья. Чем раньше мы его получим тем больше нас будет и тем быстрее можно собирать еду и получать новых муравьев. Именно поэтому так важно даже посреди боя оторвать одного муравья чтобы он пошел и подобрал еду.
u14 В калькуляторе боя пропускать повторяющиеся позиции. Этим можно значительно ускорить перебор и поднять макс кол-во муравьев до 8.
Реализовал это следующим образом. Для каждой позиции муравьев подсчитывалась ее хеш функция, на основании конечных позиций муравьев. И хранил Hashset уже обработанных позиций. После каждой новой генерации ходов смотрим если хеш позиции уникальный - обрабатываем, нет - пропускаем. Правда, мне так и не удалось придумать хорошую функцию для высчитывания хеша. То есть в редких (а может и не очень редких) случаях получалось что разные позиции давали одинаковый хеш и это полностью портило результат. В итоге пришлось вернуть полный перебор и максимальное кол-во муравьев в группе до 7.
u18 При распространении учитывать 4 вместо 3 своих муравьев.
То есть отталкивающие вектора проводятся от 4 муравьев. Это сделало рисунок распространения более гладким и довольно неплохо повысило процент побед.
u21 В калькуляторе боя учитывать муравьев которые совершили движение, а также муравьев которые родились после захвата еды..
Муравьи которые совершили движение это те которые например походили по направлению к еде.
u26 Предохранитель от таймаутов.
В некоторых местах кода делается проверка сколько времени осталось. Если больше чем 90% времени потрачено то выбрасывается исключение которое потом перехватывается и бот аккуратно завершает ход.
u25 Переделка алгоритма поиска пути.
Убрал рекурсию в алгоритме поиска пути и сделал нечто такое что мне интуитивно казалось эффективным. В последствии оказалось что это стало очень похоже на A* :)
u27 Последний шаг к еде делать с расчетом чтобы оказаться ближе к другому видимому кусочку пищи и дальше от своих.
Довольно тонкое улучшение. Отдельно рассчитывать с какой стороны подойти к еде при ее захвате.
u29 Если враг захватывает еду первым то не двигаться к такой еде. Если спорная ситуация - значит засылать еще одного своего муравья в догонку.
u35 Избегание вражеских муравьев если на карте есть больше 2 опасных вражеских бота.
Если бот со всех сторон зажат врагами то вступать в бой и размениваться крайне не выгодно. Т.к. все силы бота будут распыляться между несколькими противниками. А боты которые не агресивничали будут расти и в конце концов просто перемассят. Атаковать нужно только если это 100% безопасно.
И вот мы подошли к стадии поздней беты. Она запомнилась всем доминированием немецкого бота mathis. Этот бот был хорош в больших замесах. Он выстраивал можно сказать идеальную цепочку из муравьев, и не допускал случайных потерь (типа там один муравей выскочил вперед и погиб). И потом эта линия просто раздавливала всех. А моя боевая система перебора оказалась бессильна потому что не в состоянии обработать большое кол-во муравьев. Упрощенная система атаки никуда не годилась. Муравьи на линии таких фронтов действовали в целом как неорганизованное стадо, ходили в разнобой и допускали много ошибок. Еще его отличала агрессивность с которой он отжимал муравьев внутри своей территории. Мой же в то время, как и многие другие боты был практически не агрессивным в этом плане. Получается что mathis делал полностью безопасную зону и постепенно расширял ее подминая других как катком. На тот момент я не мог придумать как законтрить такую брутальную тактику. С моей стороны еще было много небольших улучшений о которых упоминать не стоит.
Примерно с таким багажом подбираемся к концу беты и официальному старту Google AI Challenge - Ants 2011.
С официальным стартом появились норы и новый тип карт - лабиринты. И сразу повылазило множество проблем:
- Стратегия распространения с помощью векторов не работала на лабиринтах. Чаще всего муравьи забивались где-то в районе норы.
- Начались жестокие тормоза как только кол-во муравьев превышало штук 50. Это от того что почти все запуски поиска пути, которых было много, не заканчивались быстро, а плутали по запутанным ходам.
Последующие улучшения:
Улучшения версии 2.1
Новый способ распространения по лабиринту. Это был ужас, но работало лучше чем расхождение по векторам и не тормозило.. Суть улучшения в следующем. Заводится карта видимости. Каждая клетка которой соответствует точке на карте. Каждый новый ход моего муравья поиском в ширину искалась так называемая область видимости. И в этой области видимости я повышал счетчик каждой клетки на 1. Причем карта видимости не сбрасывается между ходами. Таким образом в тех зонах где муравьев было много образовывается зона с большими значениями счетчиков видимости. И при выборе хода муравей идет в ту точку где значение счетчика видимости меньше. Таким образом муравьи не тупят в одном месте а стараются переползать все дальше от норы.
Главное было переключится на такой режим в картах типа лабиринта. Сделал я это следующим образом - собираю статистику всех прогонов поиска кратчайшего пути. И если среди найденных кратчайших путей грубо говоря попадается много в обход каких-то препятствий и мало путей напрямик - значит это скорее всего лабиринт.
Защита нор.
Моя защита нор довольно не замысловатая: как только вражеский муравей оказывается на расстоянии N шагов до норы, все ближайшие мои муравьи на него набрасываются. N было долгое время 25, под конец 15, возможно стоило еще уменьшить.
Однако, защищая свои норы важно понять что делать это стоит особенно активно только если
1) осталась 1 нора.
2) на карте много своих муравьев.
На карте с несколькими норами не надо сразу кидаться их все защищать. Т.к. бот потеряет на этом много времени, а другие просто найдут больше еды и задавят числом.
Т.е. защита нор включается при условии если осталась 1 нора или моих мураьвев > K*колввоНор (где К - магическая константа равная 10).
u54 Новый тип атаки attackMedium
Это была первая попытка сделать что то лучше чем простая атака. Чтобы воевать с тем же mathis-ом.
u56 Улучшение взятия целей. Теперь проверяется кратчайший путь до всех свободных муравьев в области доступных клеток.
Можно назвать это зачатком поиска в ширину (BFS). От каждого кусочка еды в неком радиусе выполняется поиск в ширину. К еде будем идти только в том случае если в результате этого поиска были найдены мои муравьи.
u70 1) Много улучшений производительности. 2) Во время взятия еды муравей теперь может пойти к более дальнему скоплению еды чем к близайшему 1 кусочку, если это движение будет отдалять его от скопления.
На финишной прямой.
Неделя до начала финалов. На официальном сервере и на tcp сервере доминирует немецкий бот xathis. Его 1я версия появилась где то спустя неделю после официального старта и сразу захватила лидерство. Потом уже почти под конец появилась 2я версия - и порвала всех еще раз с большим отрывом. А где же mathis пропал?
Я взял отпуск на эту неделю чтобы сделать последнее усилие.
Недостаток текущего распространения по лабиринту с кумулятивной картой видимости заключался в том, что муравьи часто забивались в тупики и не могли из них выбраться. Получается это естественным образом потому что в дальних тупиках поначалу много неисследованных клеток, все туда идут, а путь назад уже хорошо изучен - и получается что назад уже никак.
Решил попробовать сделать больший упор на поиск в ширину. Идея в следующем.. Имеется несколько типов целей. Каждая цель обладает своим приоритетом. Вокруг целей одного типа начинают расходится волны поиска в ширину, причем каждая клетка повышает значение на карте приоритетов. Значение приоритета в обратной квадратичной зависимости от дальности до цели. Типы целей:
- краевые точки на карте видимости - они ведут в неисследованные зоны.
- вражеские муравьи.
- вражеские норы.
- точки которые более 20 ходов не были видимы, но находятся внутри уже исследованной зоны - там могла появится новая еда, которую нужно собрать.
Таким образом после 4 проходов поиска в ширину карта окрашивается приоритетами, которые повышаются чем ближе клетка находится к одной из цели (или к нескольким сразу). Остается только взять муравья, найти в радиусе видимости точку с наибольшим приоритетом и пойти к ней. Это улучшение дало действительно ощутимый прирост силы. Хотя я считаю что до конца так и не успел нормально все отточить и подобрать оптимальные коэффициенты для разных типов целей.
Последние выходные перед финалом.
Это были самые жаркие дни за последние несколько месяцев. Я пытался сообразить лучшую систему боя для больших скоплений муравьев. Продвигался вперед с помощью юнит тестов. Находил в повторах ситуацию с ошибкой, делал соответствующий юнит тест и пытался как то фиксить. Код получился ужасным, но удалось пофиксить тестов 15, и не завалить предыдущие :). Это улучшение дало 60%-70% побед против старой версии в режиме 1х1. И до 10% в режиме FFA. Если учесть что старая версия поднялась до 2 места на официальном сервере, у меня были большие ожидания перед началом финалов!
Что не успел.
И все таки конечная боевая система оказалась далеко не так хороша как у xathis-а. Чтобы понять это достаточно посмотреть несколько игр с ним.
Также мне не нравится как я исследую уже освоенные земли в поисках еды в режиме распространения по лабиринту с помощью карты приоритетов. Мне кажется лучше было бы иметь равномерную сетку покрытия разведчиками как у xathis-а или tetrapohedron-а. И чтобы разведчики динамически могли становится в бой если это надо.
Пора заканчивать. Статья и так получилась не маленькая :)
Хочу сказать спасибо Роме Ищенко :), моему коллеге по работе, с которым мы вместе устраивали мозговые штурмы в обед, обдумывая новые возможности улучшений.
Код бота и jar-ник..
UPD. А вот так все кончилось.
Пока пишу этот пост финалы Google AI Conteset 2011 - Ants в самом разгаре. Организаторы постепенно отключают более слабых ботов чтобы более сильные имели возможность больше поиграть. Судя по таймеру расположенному на сайте http://ants.aichallenge.org до объявления победителя остается, 1 день 5 часов 35 минут и 5, 4, 3, 2.. секунд.
Ах да, о чем это я. В данный момент мой бот GreenTea пребывает на 3ем месте из 7897. О нем и пойдет речь в данном посте. Даже не знаю с чего лучше начать, столько труда и времени было в него вложено, с самой первой беты, когда еще не было нор.. уже тогда я начал.
Так получилось что в этом году фаза бета версии затянулась непростительно долго. Это сильно подорвало мою веру в энтузиазм и open source. Потом внезапно разработчики написали на сайте Sponsored by Google и очень резко засуетились, начали шевелится и что-то коммитить. Ну что ж, хорошо хоть так :) - я уж было подумал что так и заглохнет на стадии беты.. И все это время беты (уже не помню сколько, 4 месяца?) я кодил, что-то потихоньку допиливал и улучшал.
За что люблю этот тип соревнования, то что времени - МНОГО! Можно не спеша, не торопясь сесть, все продумать, поробовать, протестировать, поменять.. еще 5 раз поменять, еще протестировать, и т.д. Вобщем, наслаждаться программированием в моем понимании :)
Начну по порядку, и постараюсь придерживаться хронологии событий.
Механика игры.
Имеется замкнутая сама на себя прямоугольная карта определенного размера. Замкнутая в том смысле что уходишь влево - приходишь справа, уходишь вниз - приходишь сверху и т.п. Каждый игрок начинает с некоторым количеством начальных нор и 1 муравьем возле каждой норы. Каждая клетка поля может быть либо землей, либо непроходимой для муравья водой. Муравьи должны собирать еду - за каждый собранный кусочек из случайно норы появляется новый муравей. Он видит в неком радиусе, так что заранее не известно что за ним - нужно исследовать. Еда появляется случайным образом. Если муравьи разных игроков после хода оказались в радиусе атаки, то происходит бой между ними. Правила разрешения боя обьяснить не так уж просто, достаточно сказать что в среднем, меньше убитых муравьев окажется у того игрока, чьих муравьев оказалось больше в бою. Чтобы захватить нору надо на нее стать. За убитую нору дают 2 очка. За потерю своей норы отнимают 1 очко. Так что если если выбор захватить вражескую нору или потерять свою следует предпочитать первое, только если своих нор >1. На каждом ходу бот должен выбрать куда походить каждым из муравьев. Да забыл сказать что карты симметричные, и еда появляется также симметрично для всех, чтобы было по честному. Все! Вот такие не хитрые правила. В отличии от войны планет, где толком не понятно было что делать и как ходить, данную игру легче разбить на подзадачи и решать их по отдельности. Ну к примеру очевидно что надо бежать за едой, равномерно распространяться по карте и наваливаться на врагов большим количеством своих муравьев. Но в том то прикол, что легче и понятней стало всем, а поэтому из-за большей конкуренции сложность ни капельки не убавилась.
Мой инстументарий.
Java. Я - java разработчик. Этот язык достаточно прост и быстр. Позволяет с большой скоростью фигачить тонны кода (если надо реализовать какую-то свежую идею) не заботясь о каких-то системных вещах типа утечек памяти (привет C++ !!).
Поэтому для написания бота выбрал джаву. Где-то в средине беты ради веселья попытался переключится на lisp sbcl. Не получилось.. Мой алгоритм поиска пути, идентично релизованный на лиспе работал в 5 раз медленнее чем на java. Возможно это от моего не достаточно хорошего знания лиспа...
IntelliJ idea Comunity edition. Замечательная среда разработки. Нареканий в процессе работы практически не было. Один раз слетел кеш, и весь код пестрел якобы "ошибками" компиляции. Пришлось почистить кеш руками и перезапустить.
git. Системы контроля версии мне очень не хватало в Planet Wars. Ошибки были учтены и я сразу начал коммитить в git. Он меня покорил своим богатством возможностей и скоростью работы (по сравнению с svn).
Скрипты на perl. В прошлом соревновании Planet Wars я наваял скрипты для автоматического тестирования своего бота со своим же ботом более старой версии. Грех было не воспользоваться ими! Правда пришлось немного переделать скрипт чтобы приспособить его к картам с несколькими игроками в так называемом режиме FFA (Free For All) - каждый сам за себя.
Например:
- выиграл у 1.5 ботов и прогирал 4.5 ботам (+ 0.5 прибавляется к победам и поражениям за ничью)
- Набрал 0 очков, 2.16 - среднее кол-во очков у остальных ботов.
И суммарная информация:
- побед за все игры: 4.5 (45%),
- поражеий - 5.5
- очков в сумме набрано за все игры: 4 (52.2%),
- сумма средних очков по всем оппонентам: 3.66.
Подобная информация выводится после каждой игры. Таким образом можно протестировать стал ли бот действительно играть лучше в играх типа FFA или нет.
Таблицы в google documents. Там я вел учет сделанным улучшениям, версиям бота и тестированию этих версий друг с дружкой, на разных наборах карт, и при различных режимах появления еды.
Sampling profiler hprof. Эта штуковина сыграла мне большую службу. Забегая на перед, примерно за 2 недели до конца, мой бот еще очень много падал по таймауту (превысил 500 мс отведенных на ход). Я не мог понять почему это происходит. С первого взгляда код чист и идеален, прогон входных данных взятых с игры на которых бот отвалился по таймауту показывает что бот успевает сделать ход ( к примеру за 300мс ). Так почему же он падает на сайте? Я уже начал думать всякую мистику, типа сборшик мусора запускается по среди игры в произвольное время, и выполнение приостанавливается. Возможно это отчасти и правда, но дело оказалось проще. Как то неожиданно наткнулся на hprof. Он вешается как агент к java-е (как то так -agentlib:hprof=cpu=samples,interval=10,depth=10), и в процессе работы (в моем случае это прогон данных поступавших на вход боту, к примеру на 200 ходах игры) собирает статистику где управление задерживается чаще всего. И с помощью этого нашел много достаточно не очевидных мест, работавших медленно. Какой то старинный код который можно было в 10 раз упростить! - та много чего. В результате после моих фиксов бот стал работать примерно на 40% быстрее и все таймауты на официальном сайте пропали.
Рождение и эволюция.
Молодые не помнят, а я помню, что начиналось все на открытых картах. Муравьи были кочевниками и не имели нор. Да и зачем норы если муравей рождается из кусочка еды? На таких свободных паздбищах проходило детство и юность GreenTea. В начале, когда он был еще совсем мал, ходил за едой по прямой линии то и дело натыкаясь на стенки. Порою застрянет в в них, трепыхается а вырваться не может. Потом научился
Первое что реализовал это равномерное расхождение по открытой карте. Правило идти туда где нет моих муравьев реализуется достаточно просто. Находим N ближайших муравьев и строим вектора от них к текущему муравью. Приводим каждый вектор к размеру 10 (магическая константа). Следующий ход следует сделать в направлении суммарного результирующего вектора. N может варьировать. чем она больше тем более плавным будет расхождение муравьев, но требует больших затрат на вычисления, что начинает быть заметным на поздних стадиях при больших количествах муравьев.
На рисунке схематично показано как действуют векторы для одного муравья. Следующий ход будет - вверх. Это похоже на то как действуют силы отталкивания между микро частицами газа..
Потом был поиск пути. В гугл честно не смотрел, пытался сообразить сам. Первый алгоритм получился жадным, рекурсивным, и надо признать, не очень быстрым. Но этого было вполне себе достаточно для начала.
Но не долго продолжалось беззаботное детство на свободных просторах. То и дело вокруг начали появляться другие муравьи, также хорошо умеющие искать еду идя не по прямой линии а кратчайшим путем, и они почему то не хотели жить в мире..
Второе что я реализовал это калькулятор боя. Дело в том что во время беты правила разрешения боя были еще не стабильны, как и радиус атаки. Поэтому надо было написать что-то более менее универсальное, чтобы потом не переписывать лишний раз. Я не придумал ничего умнее чем перебор всех возможных ходов для своих и вражеских муравьев которые могут столкнуться в бою. И выбор из всех возможных комбинаций моих ходов такой, чтобы не нашлось вражеского хода способного одним махом погубить мою группу бойцов. Если таких "безопасных" ходов несколько, то из них выбирается такой, который, так скажем, создает наибольшее количество проблем для соперника. Тоесть, двумя словами, ищется самый агрессивный из самых безопасных ходов. Эти два понятия чаще всего взаимоисключающие, но безопасность всегда стоит на первом месте. Изначально калькулятор боя был настроен на группы муравьев (моих + вражеских) не больше 7. Это максимально 5^(7)=78125 возможных ходов. На практике, при наличии рядом стоящих муравьев, и воды комбинаций конечно меньше. Если будет 8 - то это гарантированный таймаут.
И поняли муравьи что вместе они сила. И начали истреблять врагов, рубить в капусту, без жалости и злости.
Насколько помню калькулятор боя в сочетании с поиском пути и равномерным распространением дал то, что муравей GreenTea сразу поднялся в топы на бета версии сайта. Редко какой соперник мог выдержать бешеного микро которое просто работало идеально, ведь перебирались все возможные ходы! Для групп муравьев >8 был написан примитивнейший алгоритм. Но он включался довольно редко, т.к. для отрытых картах редко скапливается действительно большое количество муравьев, хотя так было до поры до времени (об этом ниже).
Улучшения.
Кто то может со мной не согласится, но мне кажется что муравьев отличает от войны планет то, что улучшения делать значительно легче. Происходит это от того, что когда смотришь повтор боя - сразу видно где ботом была допущена ошибка. Вобщем-то так и производилось большинство улучшений: смотрим повтор "ага - тут затупил и потерял муравья, тут криво пошел, тут собрался в кучу хотя надо было расходится в разные стороны и искать еду.." В планетах была жесткая математика и точный подсчет. Одна ошибка - и все, конец. Тут же можно ошибаться по несколько раз, можно совершать хорошие ходы а можно и средние, и это еще не означает проигрыш. Но все таки побеждает тот, кто совершает меньше ошибок.
Всего, судя по таблице в google docs-е у моего бота с начала беты было 76 улучшений. Каждое из которых было протестировано на разных наборах карт и при разных распределениях еды и давало примерно от 3% до 15% прироста количества побед в боях 1 на 1 со старой версией без улучшения, и от 1% до 10% побед в боях FFA.
Попробую привести тут самые значимые улучшения начиная с беты, когда еще не было нор. Почему именно оттуда - потому что там было сделано много важных улучшений которые в последствии повлияли на отличную игру на открытых картах, даже при наличии нор.
u4. Улучшение поиска пути - найденный путь должен больше напоминать прямую линию.
Хех. Моя первая корявая реализация поиска пути находила кратчайший путь но он на глаз оказывался слегка кривоватым.
Красным показан старый кривой путь к еде. Зеленым - правильный путь. Хотя визуально это не видно но оба пути имеют одинаковую длину считая по клеткам.
u6. При поиске еды и противников использовать для расчета расстояния использовать
честный минимально возможный путь.
Красным показано неправильно рассчитанное расстояние до еды. Зеленым - реальный кратчайший путь. Как видим враг успевает добраться до еды быстрее. Следовательно нам уже идти за ней и тратить ходы нет смысла.
u9. Калькулятор боя
О нем см. выше.
u11 Собирать еду перед атакой.
Скорость роста популяции зависит от текущего его размера. Поэтому критически важно как можно быстрее получить нового муравья. Чем раньше мы его получим тем больше нас будет и тем быстрее можно собирать еду и получать новых муравьев. Именно поэтому так важно даже посреди боя оторвать одного муравья чтобы он пошел и подобрал еду.
u14 В калькуляторе боя пропускать повторяющиеся позиции. Этим можно значительно ускорить перебор и поднять макс кол-во муравьев до 8.
Реализовал это следующим образом. Для каждой позиции муравьев подсчитывалась ее хеш функция, на основании конечных позиций муравьев. И хранил Hashset уже обработанных позиций. После каждой новой генерации ходов смотрим если хеш позиции уникальный - обрабатываем, нет - пропускаем. Правда, мне так и не удалось придумать хорошую функцию для высчитывания хеша. То есть в редких (а может и не очень редких) случаях получалось что разные позиции давали одинаковый хеш и это полностью портило результат. В итоге пришлось вернуть полный перебор и максимальное кол-во муравьев в группе до 7.
u18 При распространении учитывать 4 вместо 3 своих муравьев.
То есть отталкивающие вектора проводятся от 4 муравьев. Это сделало рисунок распространения более гладким и довольно неплохо повысило процент побед.
u21 В калькуляторе боя учитывать муравьев которые совершили движение, а также муравьев которые родились после захвата еды..
Муравьи которые совершили движение это те которые например походили по направлению к еде.
u26 Предохранитель от таймаутов.
В некоторых местах кода делается проверка сколько времени осталось. Если больше чем 90% времени потрачено то выбрасывается исключение которое потом перехватывается и бот аккуратно завершает ход.
u25 Переделка алгоритма поиска пути.
Убрал рекурсию в алгоритме поиска пути и сделал нечто такое что мне интуитивно казалось эффективным. В последствии оказалось что это стало очень похоже на A* :)
u27 Последний шаг к еде делать с расчетом чтобы оказаться ближе к другому видимому кусочку пищи и дальше от своих.
Довольно тонкое улучшение. Отдельно рассчитывать с какой стороны подойти к еде при ее захвате.
Ход вправо сделать лучше по двум причинам. 1) это приближает к другому кусочку еды, за которым не идут другие муравьи. 2) Это отдаляет от моего муравья. Тем самым расширяя границы обзора - а значит и захваченную территорию.
u29 Если враг захватывает еду первым то не двигаться к такой еде. Если спорная ситуация - значит засылать еще одного своего муравья в догонку.
Моделируется ситуация захвата еды. Как видим первый муравей когда пойдет и попробует взять еду ему помешает муравей соперника и произойдет взаимная аннигиляция. И тут на подхвате будет второй муравей. Важно чтобы он оказался как можно ближе, поэтому ход по направлению к еде должен делать прямо сейчас.
u35 Избегание вражеских муравьев если на карте есть больше 2 опасных вражеских бота.
Если бот со всех сторон зажат врагами то вступать в бой и размениваться крайне не выгодно. Т.к. все силы бота будут распыляться между несколькими противниками. А боты которые не агресивничали будут расти и в конце концов просто перемассят. Атаковать нужно только если это 100% безопасно.
И вот мы подошли к стадии поздней беты. Она запомнилась всем доминированием немецкого бота mathis. Этот бот был хорош в больших замесах. Он выстраивал можно сказать идеальную цепочку из муравьев, и не допускал случайных потерь (типа там один муравей выскочил вперед и погиб). И потом эта линия просто раздавливала всех. А моя боевая система перебора оказалась бессильна потому что не в состоянии обработать большое кол-во муравьев. Упрощенная система атаки никуда не годилась. Муравьи на линии таких фронтов действовали в целом как неорганизованное стадо, ходили в разнобой и допускали много ошибок. Еще его отличала агрессивность с которой он отжимал муравьев внутри своей территории. Мой же в то время, как и многие другие боты был практически не агрессивным в этом плане. Получается что mathis делал полностью безопасную зону и постепенно расширял ее подминая других как катком. На тот момент я не мог придумать как законтрить такую брутальную тактику. С моей стороны еще было много небольших улучшений о которых упоминать не стоит.
Примерно с таким багажом подбираемся к концу беты и официальному старту Google AI Challenge - Ants 2011.
С официальным стартом появились норы и новый тип карт - лабиринты. И сразу повылазило множество проблем:
- Стратегия распространения с помощью векторов не работала на лабиринтах. Чаще всего муравьи забивались где-то в районе норы.
- Начались жестокие тормоза как только кол-во муравьев превышало штук 50. Это от того что почти все запуски поиска пути, которых было много, не заканчивались быстро, а плутали по запутанным ходам.
Последующие улучшения:
Улучшения версии 2.1
Новый способ распространения по лабиринту. Это был ужас, но работало лучше чем расхождение по векторам и не тормозило.. Суть улучшения в следующем. Заводится карта видимости. Каждая клетка которой соответствует точке на карте. Каждый новый ход моего муравья поиском в ширину искалась так называемая область видимости. И в этой области видимости я повышал счетчик каждой клетки на 1. Причем карта видимости не сбрасывается между ходами. Таким образом в тех зонах где муравьев было много образовывается зона с большими значениями счетчиков видимости. И при выборе хода муравей идет в ту точку где значение счетчика видимости меньше. Таким образом муравьи не тупят в одном месте а стараются переползать все дальше от норы.
Главное было переключится на такой режим в картах типа лабиринта. Сделал я это следующим образом - собираю статистику всех прогонов поиска кратчайшего пути. И если среди найденных кратчайших путей грубо говоря попадается много в обход каких-то препятствий и мало путей напрямик - значит это скорее всего лабиринт.
Защита нор.
Моя защита нор довольно не замысловатая: как только вражеский муравей оказывается на расстоянии N шагов до норы, все ближайшие мои муравьи на него набрасываются. N было долгое время 25, под конец 15, возможно стоило еще уменьшить.
Однако, защищая свои норы важно понять что делать это стоит особенно активно только если
1) осталась 1 нора.
2) на карте много своих муравьев.
На карте с несколькими норами не надо сразу кидаться их все защищать. Т.к. бот потеряет на этом много времени, а другие просто найдут больше еды и задавят числом.
Т.е. защита нор включается при условии если осталась 1 нора или моих мураьвев > K*колввоНор (где К - магическая константа равная 10).
u54 Новый тип атаки attackMedium
Это была первая попытка сделать что то лучше чем простая атака. Чтобы воевать с тем же mathis-ом.
u56 Улучшение взятия целей. Теперь проверяется кратчайший путь до всех свободных муравьев в области доступных клеток.
Можно назвать это зачатком поиска в ширину (BFS). От каждого кусочка еды в неком радиусе выполняется поиск в ширину. К еде будем идти только в том случае если в результате этого поиска были найдены мои муравьи.
u70 1) Много улучшений производительности. 2) Во время взятия еды муравей теперь может пойти к более дальнему скоплению еды чем к близайшему 1 кусочку, если это движение будет отдалять его от скопления.
Немного лучше в такой ситуации пойти за дальней группой еды.
На финишной прямой.
Неделя до начала финалов. На официальном сервере и на tcp сервере доминирует немецкий бот xathis. Его 1я версия появилась где то спустя неделю после официального старта и сразу захватила лидерство. Потом уже почти под конец появилась 2я версия - и порвала всех еще раз с большим отрывом. А где же mathis пропал?
Я взял отпуск на эту неделю чтобы сделать последнее усилие.
Недостаток текущего распространения по лабиринту с кумулятивной картой видимости заключался в том, что муравьи часто забивались в тупики и не могли из них выбраться. Получается это естественным образом потому что в дальних тупиках поначалу много неисследованных клеток, все туда идут, а путь назад уже хорошо изучен - и получается что назад уже никак.
Решил попробовать сделать больший упор на поиск в ширину. Идея в следующем.. Имеется несколько типов целей. Каждая цель обладает своим приоритетом. Вокруг целей одного типа начинают расходится волны поиска в ширину, причем каждая клетка повышает значение на карте приоритетов. Значение приоритета в обратной квадратичной зависимости от дальности до цели. Типы целей:
- краевые точки на карте видимости - они ведут в неисследованные зоны.
- вражеские муравьи.
- вражеские норы.
- точки которые более 20 ходов не были видимы, но находятся внутри уже исследованной зоны - там могла появится новая еда, которую нужно собрать.
Таким образом после 4 проходов поиска в ширину карта окрашивается приоритетами, которые повышаются чем ближе клетка находится к одной из цели (или к нескольким сразу). Остается только взять муравья, найти в радиусе видимости точку с наибольшим приоритетом и пойти к ней. Это улучшение дало действительно ощутимый прирост силы. Хотя я считаю что до конца так и не успел нормально все отточить и подобрать оптимальные коэффициенты для разных типов целей.
Последние выходные перед финалом.
Это были самые жаркие дни за последние несколько месяцев. Я пытался сообразить лучшую систему боя для больших скоплений муравьев. Продвигался вперед с помощью юнит тестов. Находил в повторах ситуацию с ошибкой, делал соответствующий юнит тест и пытался как то фиксить. Код получился ужасным, но удалось пофиксить тестов 15, и не завалить предыдущие :). Это улучшение дало 60%-70% побед против старой версии в режиме 1х1. И до 10% в режиме FFA. Если учесть что старая версия поднялась до 2 места на официальном сервере, у меня были большие ожидания перед началом финалов!
Что не успел.
И все таки конечная боевая система оказалась далеко не так хороша как у xathis-а. Чтобы понять это достаточно посмотреть несколько игр с ним.
Также мне не нравится как я исследую уже освоенные земли в поисках еды в режиме распространения по лабиринту с помощью карты приоритетов. Мне кажется лучше было бы иметь равномерную сетку покрытия разведчиками как у xathis-а или tetrapohedron-а. И чтобы разведчики динамически могли становится в бой если это надо.
Пора заканчивать. Статья и так получилась не маленькая :)
Хочу сказать спасибо Роме Ищенко :), моему коллеге по работе, с которым мы вместе устраивали мозговые штурмы в обед, обдумывая новые возможности улучшений.
Код бота и jar-ник..
UPD. А вот так все кончилось.
