mini-ai-2019

7 версий

1. python_only_ide - была сделана ещё до чемпионата, с ней можно поиграть в консоли

2. version_0 - переделанная первая версия так, чтобы она подходила для чемпионата (+ мелкие правки)

3. tree_test - версия на дереве через словари

4. version_1 - улучшенная версия 3)

5. version_2 - тут я отказался от собственно дерева

6. version_2_super - переделана с list на set где только было можно и стала работать быстрее

7. version_final - итоговая версия, с улучшениями и граалями

Как я принимал участие в mini russian AI 2019 (paper.io)

Итак, недавно закончился онлайн чемпионат по искусственному интеллекту mini russian AI cup 2019, который каждый год проводит Mail.ru, в котором я занял 21-е место, так и не добравшись до финала. Пока соревнования шли, в нашем телеграмм канале (@aicups) шло много интересных обсуждений и высказывалось много идей, так что в итоге я решил собрать всё самое интересное, что я смог вспомнить (писал я ботов на Python 3.6)

Вкратце о самом соревновании:

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

В общем-то, сразу из описания стало ясно, что бессмертие - залог большого числа очков, что и стало идеей для моей самой первой версии бота. Как посчитать безопасна ли клетка твоего маршрута? Можно рассчитать расстояние между противником и клеткой (благо, тут все расстояние прямоугольные, можно просто сложить разницу координат) и понять успеваешь ли ты до неё дойти, или нет, а можно поступить немного по-другому.

Первый бот.

(python_only_ide и version_0)

Основной вехой для этой (и вообще всех моих стратегий) стала карта времени достижения каждой конкретной клетки врагом, которая заполнялась волнами от клетки, в которой находится противник Ещё полезной оказалась такая же карта, но не от игрока, а от его территории.

Итак, как же работала моя самая первая версия:

1. Находим такие клетки, до которых можно дойти и вернуться из них (сумма значений карт времени для себя, построенных от игрока и от территории) быстрее, чем противник до них доберется.
2. Запоминаем эту клетку и двигаемся к ней по маршруту, строящемуся по своей же карте времени
3. когда добираемся до этой клетки, включается режим “домой” - по такому же принципу ищется кратчайший маршрут домой и бот движется по нему.
4. смотрим на чужие клетки “хвостов”. Если до них можно добраться быстрее, чем враг вернется к себе домой, или доберется до тебя - включается режим убийства и бот идёт в такую клетку.

В итоге был сделан вывод - карты времени плохо подходят для определения цели. Они не учитывает маршрут и часто неадекватно выбирает цель для захвата. Часто случалось так, что они выбирали вроде бы безопасную цель, но вот маршрут мог начаться около противника, и тот легко мог его съесть. Что ещё более важно - так как эта стратегия не учитывала маршруты, то она не знала какие территории она собирается захватить и как много очков они принесут. Мои попытки улучшить логику на идеях “лучше выбирать клетку, которая находится дальше от своей территории - возможно, это принесёт больше очков” особого успеха не дали, и я решил всё переделать.

Второй бот

(version_1_tree)

Что было самое важное в первом боте? Он не был бессмертным, его пути часто приводили к смерти. А для того, чтобы предсказывать съедят ли тебя или нет - нужно заранее знать свой маршрут. А для того чтобы знать лучший маршрут - хорошо бы знать все маршруты и то, как много очков они приносят. Да, я принял волевое решение искать свой маршрут Полным Перебором, а соперников оставить в виде времён достижимости.

Как я видел идею полного перебора? Бот где-то находится, представим что это узел графа. У него есть несколько доступных вариантов походить (в общем случае - три, за иключением хода, противоположному последнему), а значит из этого узла отходит 3 ребра, и так далее. Так как в этой игре для бота важно не только положение, но и путь, то мы почти никогда не можем прийти в один и тот же узел дважды - а значит проще всего представить этот граф деревом.

Сама идея бота казалась мне достаточно простой:

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

Сначала я пошёл нелегким путём - я создал свою систему деревьев, состоящих из вложенных друг в друга словарей, содержащих в себе много информации - даже слишком много.

new_leaf =     {'poi':  leaf['poi'],          #предполагаемое число очков в этом узле
                	'pos': new_pos,      	#положение на карте
                	'arr':  turn,        	#направление, с которым бот пришел в эту клетку
                	'cha': [],         		#изменения мира, произошедшие за это смещение
					                              #(изменения владельцев клеток)
               	  	'p_w': 0,          	  #предыдущий путь
                       	'chi': [],          	#дочерние узлы дерева
                	'par': leaf,        	#родительский узел
                	'tik':  leaf['tik']+5,        #время карты
                	'com': False        	#закончен ли обход по этому дереву, или нет

А для того, чтобы считать очки для маршрутов - я написал БФС-подобный алгоритм, который распространяется от границ карты, и выкидывает клетки, которые не принадлежат игроку. Когда такие клетки закончатся, это будет означать что всё оставшееся находится внутри замкнутого пути, и подлежит закраски (то есть - подсчёту очков)

После того, как я радостно запустил моего нового бота я обнаружил, что он работает ужасно долго - за необходимое время он мог перебрать всего лишь 6 ходов в глубину, а этого было явно недостаточно. Стал разбираться почему так получилось, и выяснил, что большая часть работы программы - порядка 99% - заливка (и очевидное отсечение “заливать только если бот с ничейной территории вернулся на свою” - уже работало).

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

У меня было два варианта, что делать:

1. сильно улучшить алгоритм закраски (например - закрашивать алгоритмом не всю карту, а только “активную” зону - расширять не от границ карты, а рассматривать прямоугольник, окружающий территорию игрока и его маршрут)
2. вообще не смотреть на закраску. А смотреть, например, на максимальную длину пути до возвращения (а план то звучит хорошо? Нужно подумать как это можно отслеживать)

Для второго варианта мне ничего путного в голову не пришло (ведь надо ещё и учитывать то, что за чужую территорию дают больше очков - а значит, нужно точно знать что внутри этой территории), а первый способ я реализовал, и результаты улучшились с 6 до 8-ми ходов. Вот только - в начале игры, а ближе к концу, когда территория и пути снова увеличивались - производительность снова падала. С грустными мыслями, около двух часов ночи я пошел спать, и тут…

Третий бот

(version_2, version_2_super, version_final)

Итак, пришло время третьего раза переписать всё почти с нуля. А всё почему? Потому что мне приснилось несколько гениальных идей разом.

Во-первых - я понял как можно отказаться от структуры дерева (после ночных оптимизаций затраты времени на закраску и обработку дерева сравнялись) Достаточно лишь сохранять текущий путь, и функцию, выдающие возможные варианты ходов в зависимости от пути. Грубо говоря для пути UUURU в общем случае есть 3 варианта следующего хода - up, right, left (down нет - потому что ботам запрещено разворачиваться на месте. И именно в таком порядке - потому что если заранее выбрать порядок, то можно представить, что весь путь - это число, которое можно увеличивать на 1). И тогда следующим путем, который мне нужно будет рассмотреть будет путь UUURR

Во-вторых - я сообразил как делать отсечения путей так, чтобы перебирать не так много вариантов. Достаточно лишь модифицировать поиск так, чтобы он строил пути прямоугольниками: из пути UUUUUUUR можно достраивать ходы r, l, d, но u - уже нельзя. Это отсечение уменьшило число узлов в дереве с 3^n до примерно 1.4^n и очень серьёзно повлияло на производительность в лучшую сторону, новый алгоритм считал примерно на 16 ходов в глубину, вряд ли больше вообще имело смысл.

Ну и что значит вообще 16 ходов в глубину? Это 16 ходов от текущего местоположения. Это значит, что когда бот сделает ход дальше, он сможет пересчитать и найти путь, который будет лучше (который, скорее всего в итоге будет чуть хуже чем путь сразу найденный на 17 ходов, но и чуть лучше чем текущий)

В-третьих - мне пришло в голову, что можно закрашивать ещё меньше, чем от прямоугольника в котором находится территория бота. Идём по пути, который прошел бот, закрашиваем все соседние с путём клетки Выбираем любую клетку, которая ближе всего к границам карты Выкидываем внешнюю границу пути Расширяем внутреннюю границу Получаем область, в которой нужно закрашивать

Правда, буквально в этот же день я уже понял, что с такой закраской будет много багов, и в итоге я и её переделал, но об этом чуть позже

В-четвертых - я наконец-то сделал новую версию карт достижимости, учитывающие бонусы скорости, подобранные противником (и также учитывал их для себя, разумеется)

Сделал некоторые дополнительные улучшения для упрощенной генерации путей и проверок на то, что имеет смысл закрашивать путь:

путь в виде UUUUUUUR для генерации возможных путей Путь в виде массива посещённых клеток Путь в виде строки 111110000001 где 1 или 0 - принадлежит ли соответсвующая клетка своей территории

И тогда проверка на “есть ли смысл закрашивать путь” выглядела всего лишь как “если В строке “1-0” есть 0 и после нулей есть 1” то путь выходил из своей территории и вернулся обратно, смысл закрашивать есть.

Ну и как вкратце должен выглядеть обновлённый алгоритм: В каждом узле дерева проверяю на то, можно ли что-то закрашивать, обновляю число очков, которые тут можно заработать Если из этого узла нельзя построить новых путей, то поднимаемся на узел выше Если можно построить - опускаемся на уровень ниже Сохраняю наилучший путь по метрике “число очков/длина пути” Делаю первый шаг из лучшего пути

Возможные пути выдаются в строгом порядке, так что для небольшой рандомизации, чтобы пути не “прилипали” к какой-то определенной стороне,я разрешаю выбирать путь с таким же количеством очков и той же длины, если монетка выпадет.

Ну и число очков, зарабатываемые стратегией считаются так: 1 очко за ничейную территорию 5 очков за чужую территорию 50 очков за возможность убить противника (встать ему на хвост) - скорее всего это так ни разу и не сработало Еще от 10 до 50 очков за подобранный бонус ускорения

И потом всё делится на длину пути, чтобы бот стремился иногда заканчивать свои походы

И обнуляю очки, если я подбираю бонус замедления - чтобы бот избегал этот бонус

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

Залив новую версию на сервер и поправив много странных багов (например, я не ожидал того что противник будет строить змейку длиной в >64 элемента - это сломало логику в построении новых карт достижимости, учитывающую скорости) - я выяснил что у моей (уже пятой) версии закраски есть один большой недостаток - она ломается, если на карте есть больше чем 1 мой островок и это нужно срочно исправлять В итоге, я модифицировал процедуру Shell (которая возвращает оболочку моей территории) так, чтобы она игнорировала куски территории, которых закраска точно не коснётся - то есть, они не касаются пройденного пути. (но это снова породило новые баги о которых я и не мог подумать)

Обнаружил, что моя стратегия падает если она находится слишком близко к противнику (1-2 клетки) и умирает - вставил заглушку функцией поиска возможных ходов, если поиск по дереву не даёт результатов

Ещё, почему-то, стратегия сильно зависала, когда несколько соперников умирало - когда я поднялся в рейтинге повыше, к более живучим соперникам, то всё заработало нормально. Были странные немного странные поиски путей:

Впрочем, и с этим ботом я вошел в предфинальный раунд (25% игроков) и у меня была ещё неделя на улучшения.

Мне пришло в голову, что можно попытаться ускорить часть проверок (и увеличить глубину переборов), запихав хотя бы ценность территории в массив заранее. Возможно, стоило также склеить все временные карты соперников в одну, для уменьшения числа проверок. Я наконец-то довёл алгоритм закраски до состояния, в котором не может быть багов.

Что действительно крутого я добавил за эту неделю:

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

Так как я не смог понять что влияет на периодические просадки производительности - я добавил динамическую глубину просчёта. Как это работает? Если суммарное время работы программы меньше положенного суммарного времени (TIME<TICKS*MAX_EXECUTION_TIME/MAX_TICKS_COUNT) то увеличиваем разрешённую глубину на один, иначе уменьшаем на 1 (но не меньше 8-ми тиков в глубину и не больше 20-ти)

Захардкодил безопасные ходы, если враг находится очень близко (в квадрате 3х3 с центром в игроке)

Очень долго думал, как бы заставить бота стараться подбирать те клетки, которые в макро игре приведут его ближе к вкусным клеткам врага (ведь они стоят в целых 5 раз дороже!) В итоге я вспомнил про карты времени, распространяемые от территорий врагов. Немножко модифицировал их, чтобы они возрастали наоборот в сторону территорий противников, нормировал их - и оно заработало.

Конечно, не обошлось и без некоторых весёлых багов

Но, в целом, оно работает.

В итоге всё равно несколько идей, которые так хотелось сделать и не сделал - увороты от пилы, подбирание пилы; подключение минимакса, если враг подходит слишком близко; поиграть с разными оценочными функциями.

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

Итоги

Итак, попробую подвести итоги с моей точки зрения:

Несмотря на то, что мои результаты не слишком уж и хорошие, я доволен ими, и вот почему: Хоть я и до этого пытался участвовать в таком чемпионате, там я слишком много времени потратил времени на идеи, и не так много времени на код - результат был очевиден. Еще этот “мини” чемпионат оказался довольно простым по правилам и порогу вхождения, так что конкуренция среди участвующих разгорелась нешуточная.

Что самое важное - даже я сам заметно ощущаю возросшее качество моего последнего бота, в сравнении с первым (хотя я больше горжусь алгоритмом заливки)

Чем я не доволен в своих результата: Во-первых, я не тратил время на поиск и отладку багов, которые в итоге случились у меня в финале. Скорее всего я бы мог подняться и выше. Во-вторых, очень важно было бы добавить хотя бы короткие (хода на 3-4) деревья для каждого противника, чтобы оценивать возможности убийства закраской, убийства пилами В-третьих, стоило хотя бы добавить небольшой бонус очками за подбор пилы - кода было бы едва на 5 строчек, а хуже бы точно не стало В-четвертых, нужно было задуматься над улучшенной картой достижимости, которая бы давала больше информации о том, откуда и во сколько вражеский бот бы вошел в клетку (возможно, как раз сделать эту карту не для больших клеток, а для микроклеток)