Как создать лучшего бота для игры в стиле Dota — интервью с победителем соревнования Russian AI Cup

Недавно закончился финальный раунд ежегодного чемпионата Russian AI Cup — организуемого Mail.Ru ежегодного конкурса, на котором участники пишут ИИ для победы в выбранной организаторами компьютерной игре. В этом году задачей было написание бота-волшебника в игре, подобной Dota 2. Мы пообщались с победителем — Антоном Чумаченко — и узнали, что же именно помогло ему выиграть.

Антон Чумаченко

победитель Russian AI Cup 2016

Привет, Антон. Какие в целом впечатления у тебя от соревнования?

В этом году специфика задания была таковой, что первая стратегия могла побеждать вторую, вторая — третью, а третья — с легкостью одерживать победу над первой. И задание оказалось гораздо шире в количестве разных аспектов, чем в предыдущие годы. Поэтому до самого финала нужно было пристально наблюдать за стратегиями других участников и писать новую порцию кода, если они находили контрмеры для твоей стратегии. Победа далась нелегко и в какой-то степени благодаря везению, так как отрыв от 2-ого места составил всего лишь 4 балла, а от 3-его — 6 баллов (у Антона 1250 баллов в финале — прим.ред).

У тебя уже был опыт участия в Russian AI Cup?

Да, я участвовал во всех чемпионатах Russian Ai Cup, начиная с 2012-ого года, и каждый раз результат был все выше и выше. Лучшим результатом до этого года у меня было 8-ое место в 2015-ом году. Переломным оказалось задание, где нужно было запрограммировать управление хоккеистами, потому что на тот момент мне казалось, что мои знания и способности существенно ниже, чем у участников, занимающих первые 30–50 мест в подобных соревнованиях. И первое место в песочнице (сразу после победителей финала) подарило мне вместе с ценным подарком веру в собственные силы и в то, что выучить что-то и улучшить свои способности никогда не поздно.

Как ты проектировал свою стратегию?

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

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

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

Помогло ли умение играть в DOTA, на которую похож формат игры?

Умение играть в доту помогло, но косвенно: был повышенный интерес в самом начале соревнования, вследствие чего быстро забрался в верхнюю часть песочницы. А дальше уже дополнительно подстегивало желание не потерять набранных позиций. Также считаю, что помог победить опыт настройки баланса и подбор коэффициентов, который я получил при написании пары своих небольших игрушек. В данном чемпионате были достаточно важны эвристические предположения, такие как “пойти за бонусом на 37-ой секунде или на 38-ой”. Математически все аспекты данного чемпионата запрограммировать было очень сложно, так как время ограничено.

Ты писал свою стратегию на C++, почему выбор оказался таким?

C++ я выбрал потому, что большинство крупных работ выполнял именно на нем, также не хотел упираться в лимит по времени, отведенный на стратегию, если вдруг будут какие-то сложные вычисления. Хотя особенности С++ я использовал мало, поэтому не так уж и важно, на каком языке писать. Лучше выбрать тот инструмент, для которого не потребуется каждые 15 минут лезть в гугл и искать примеры инициализации массивов. Правда, это утверждение хорошо подходит, если цель — занять место повыше. А целью может быть еще и изучение нового языка (такое наблюдалось у некоторых из участников).

Как можно подготовиться к этому соревнованию?

Заранее глобально подготовиться сложно. В целом могу посоветовать побольше изучить теорию графов, в частности поиск путей, и перебор с отсечением (это наиболее популярные виды алгоритмов, которые использовались на прошедших 5-ти Russian AI Cup). Также полезным будет прочтение статей победителей прошлых лет и изучение их кода. Хорошо потренироваться в написании ботов можно на сайте www.codingame.com. Еще раз повторюсь, что написание своего визуализатора увеличивает скорость отладки. Я для его написания использовал OpenGL, но, возможно, кому-то будет более комфортно использовать другие средства для отрисовки простой графики.

Порекомендуешь принять участие в чемпионате?

Конечно, оно того стоит! Неважно, какое место я занимал: 1-ое или 200-ое — во время чемпионата я получал массу удовольствия, отличную разминку для мозгов, дополнительные знания и навыки, а также знакомился с собратьями по интересам.

Благодарим Антона за предоставленное интервью.

Игры, для прохождения которых нужно писать программный код, в последнее время набирают популярность. Помимо участия в Russian AI Cup, “поиграть в программирование” дают возможность и другие компьютерные игры: мы собрали подборку игрушек, которые подойдут новичкам, а также коллекцию проектов, которые приглянутся уже более опытным программистам.

А о написании искусственного интеллекта для прохождения игры у нас есть целый цикл статей: в нем рассказывается о написании ИИ для игры в хоккей.