История победы на ежегодном соревновании Russian AI Cup 2017

    Всем привет! Хочу рассказать про историю своей победы в ежегодном соревновании по написанию игровых ботов Russian AI Cup, в 2017. В финале бот выиграл 98% игр, что, как оказалось, наивысший результат по финалам среди всех годов проведения чемпионата. Также занял 1-е место в песочнице по завершению её работы, в пике переходя за 4000 очков рейтинга.



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

    О задаче этого года уже было подробно написано тут. Вкратце: это война большим количеством юнитов разных типов: танки, бтр, ремонтные машины, истребители, вертолеты. Изначально дается 500 единиц техники, но можно захватывать заводы и производить новую технику без ограничений. Эта тематика меня сразу заинтересовала, т.к. раньше любил играть в стратежки вроде Dune (еще на приставке Sega), Red Alert, Star Craft 1 & 2.

    Выступаю не первый год, и не только в Russian AI Cup-е, под ником GreenTea. Может быть кто-то по помнит меня по ants.aichallenge.org, отчет.

    О подходе в этом году. Подход был серьезный, можно даже сказать профессиональный :)

    • Не проморгать начало, лучше начать сразу с беты.
    • Использовать наработки с прошлых чемпионатов: это всякие утилитные классы вроде точки, вектора, отрезка, всякие самописные математические функции.
    • Настроить локально среду для тестирования бота.
    • Взять отпуск на пару недель чемпионата, чтобы максимально погрузиться в процесс.
    • Много работать, жертвовать практически всем свободным временем. Это хадкор да, но что поделать.

    В этом году было больше всего жалоб от людей, что мол “очень сложно”. Управление тяжелое. Надо написать много вспомогательного кода, чтобы научить бота делать даже простейшие вещи — это так. Например, не было такой штуки как автоматический поиск пути для юнитов. Так, чтобы указал конечную точку для движения, и больше не думать, а юниты сами объедут все препятствия. Такого не было. Юниты двигаются по прямой натыкаются на других юнитов и стоят… Борьба с застряваниями — это была постоянная боль.

    Далее, возможные команды боту имитируют действия, которые выполняет человек, играя в стратегию. А именно: выделение юнитов в прямоугольную рамку, послать выделенных юнитов через атаку, назначить / выделить группу и тд. Плюс к этому, количество действий жестко лимитировано. Выполнять действия в таком виде гораздо сложнее, чем напрямую назначать команды каждому отдельному юниту. Это привело к тому, что очень многие участники не вышли ни во что более сложнее, чем просто собрать всех юнитов в одну кучу, перемешать хорошенько и отправить на ближайшего врага. Позднее это эволюционировало в создание очень аккуратно построенной фаланги (в народе — бутерброд), которая медленно ползла на врага и сделать что-либо с ней очень сложно. Но суть осталась та же. В RTS это называется death ball, т.е. шар юнитов который убивает все на своем пути. Организаторы даже ввели возможность нанесения ядерного удара, чтобы таким бутербродам жилось не так легко — ведь в куче юниты более уязвимы. Но, как оказалось, “правильный” бутерброд не особо боится ядерных ударов, потому что ремонтные машинки успевают его “вылечить”.

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

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

    Изначально было понятно, что бутерброд — это гиблое дело, потому что при введении зданий, которые надо захватывать, он просто не успеет собраться и что либо захватить. Поэтому начал с разбиения на группы. Решил что в каждой у меня будет по 25 юнитов. Итого 20 штук. Почему такой размер? Это дает хорошую мобильность, трудно нанести большой ущерб ядерной бомбой. Также 25 юнитов по размеру хорошо вписываются в игровую клетку (поле было 32 на 32 клетки). Чуть позднее истребители были объединены в одну пачку 100 юнитов, т.к. в таком виде они имеют наибольшую ударную мощь, и в то же время практически не бояться ядерных ударов.

    Далее учим группы двигаться. Важно чтобы при движении они не натыкались друг на друга. Решил аппроксимировать группу кругом, который содержит всех юнитов. А именно кругом, потому что коллизии для кругов считать проще всего. Коллизии можно считать 2мя способами:

    • Геометрически, сравнивая на сколько сближаются отрезки пути при движении групп. С этого способа я начал.
    • Симуляцией: с некоторым шагом имитируем движение всех групп, и проверяем не столкнулись ли они. Этот способ лучше, т.к. учитывает динамику движения. Правда, чтобы симуляция не тормозила, пришлось использовать шаг в 30 тиков.

    Теперь вопрос куда двигаться. Для этого применяем метод потенциальных полей (ПП), суть которого заключается в том, что хорошие позиции должны притягивать группу, а плохие — наоборот отталкивать. Размер анализируемой клетки по методу ПП я взял 32 на 32, потому что в неё хорошо помещается группа размером 25 юнитов а также на клетки такого же размера разделяется карта погоды и ландшафта. Далее вопрос как же оценить, позицию, стоит ли в неё идти или нет?
    Ниже приведу все параметры, которые я учитывал при оценке клетки на момент финала:

    • Позиция на поле: хорошо быть ближе к центру, плохо на краях и очень плохо в углах.
    • Тип местности и погода: эти параметры влияют на характеристики юнитов, поэтому избегаем плохой погоды и трудно проходимой местности.
    • Расстояние до других групп: не подходить слишком близко во избежание коллизий. При обнаружении коллизии — выписываем максимальный штраф.
    • Бой с врагом: могу ли в данной клетке уничтожить противника, или он уничтожит меня?
    • Захват фабрик: насколько близко клетка находится к зданию, которое можно захватить.
    • Разведка: сколько клеток могу увидеть находясь в данной, учитывая как давно их не видел.
    • [для воздушных юнитов] Починка: подлететь к машинкам ремонта и починить повреждения — это хорошо.
    • [для ремонтных машинок] Починка: подъехать к битым летающим юнитам.
    • [для истребителя наводчика ядерки] Подлететь к самой большой куче врагов и наводить на неё ядерный удар.



    На скрине выше визуализация ПП для бтр (оранжевого цвета), которая уже была написана после финалов. В этом году я как то совсем обошелся без визуализации. Константы для формул прикидывал в уме, проверял в дебагере, и оно как-то сходу все заработало.

    Вообще процесс улучшения бота был таким:

    • Внимательно смотрим на игры бота на сайте или локально, и находим места, где бот действует нерационально. Если таких мест много, записываем, чтобы не забыть.
    • При выборе реализации улучшения, стараемся рассмотреть несколько способов, и выбираем тот, который скажем так “наименее костыльный”.
    • Работаем над улучшением и сверяем с предыдущей версией бота, до тех пор, пока новая версия не будет стабильно чаще побеждать. Для проверки стабильности брал штук 20 разных карт, прогонял в localrunner-е и подсчитывал количество побед новой версии. Все бои просматривал, чтобы воочию убедиться что улучшение работает как надо.
    • Делаем коммит и сохраняем новую версию как последнюю, с которой будем тестировать. Заливаем то что получилось на сайт.
    • Если во время локально просмотра боя находится бага, то из-за фиксированного seed и отсутствия рандома в движке её сразу можно воспроизвести, продебажить и починить. Кстати, ни разу не использовал утилиту repeater для поиска багов.

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

    Хорошо, потенциальные поля у нас есть. Далее вопрос в том, в каком порядке двигаться? Действия ведь ограничены. Какая группа должна походить первой? Расчет такой:

    • Сканируем все клетки в неком радиусе от группы и находим клетку с наибольшим количеством очков bestScore.
    • Вычисляем количество очков currentScore клетки, куда данная группа уже направляется (если она двигается), или текущей клетки (если стоит на месте).
    • scoreDiff = bestScore — currentScore

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

    Несколько слов о боевой системе. Она довольно примитивно симулирует исход битвы, с заданным количеством единиц техники с обеих сторон. Причем если допустим имеется 2 танка с процентом прочности 0.5 оба, то симулятор боя просто суммирует все HP и считает что это 1 целый танк. Бой длится по раундам. Каждый раунд атакует каждая из сторон, и повреждения вычитаются. Причем если в группе соперника имеется несколько типов юнитов, то стреляет по каждому типу по очереди. Бой заканчивается, когда нанесенный урон обеих сторон равен 0, что происходит например когда одна из групп убивает другую, или с одной стороны остались танки, а с другой истребители, и они не могут атаковать друг друга. Как можно заметить, система довольно не точная, но зато очень быстрая, и в большинстве случаев довольно адекватно предсказывает исход боя. Для симулятора боя писал юнит тесты. Кстати очень грубый тест производительности показывает, что бой, где с одной стороны 25 танков и 25 ремонтных машинок, а с другой 25 танков, просчитывается 100000 раз за 519 мс, или 19 просчетов за 1 мс, что довольно неплохо. Попытки хоть немного увеличить точность данной системы привели к непомерному увеличению времени вычисления, и я на это дело забил.

    При оценке боя в клетке берется радиус боя равный 2 радиусам группы. С одной стороны — все мое что есть в радиусе + юниты группы, с другой стороны — все что есть у противника радиусе боя. И скармливается это все симулятору боя. На выходе получаем структуру с информацией: урон минус потери, количество юнитов с обеих сторон после боя, конечный раунд.

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

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

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

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

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

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

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

    Итак, было:
    Пачка if-ов
    ПП
    Пачка if-ов


    Стало:
    Стратегия 1
    Стратегия 2

    Стратегия N


    Каждая стратегия наследуется от класса BattleStrategy, имеет тип enum BattleStrategyType, должна реализовать метод abstract boolean apply(Move move);
    Все стратегии существуют в 1 экземпляре, содержаться в списке и вызываются последовательно, от более к менее приоритетным. Если метод apply вернул true, значит стратегия сделала ход, и дальше по списку стратегии не рассматриваем. Если же false — значит текущая стратегия не считает необходимым применяться на данном тике, и можно попробовать следующую. Далее привожу весь список стратегий на момент финала, от более к менее приоритетным.

    AvoidNuclearStrike — уклонение от ядерных ударов.
    CreateGroups — создание групп из свободных юнитов на фабриках, при срабатывании определенных условий.
    CreateScouts — создание истребителей разведчиков, которые могут выполнять функции наводчика ядерной бомбы.
    DoNuclearStrike — нанесение ядерного удара.
    FactoryProduction — заказ производства юнитов нужного типа на фабрике.
    JoinGroups — объединение 2 групп в одну если общее количество групп слишком возросло.
    Pack — уплотнение юнитов в группе, так чтобы её радиус уменьшился, это делает бой более эффективным.
    TurnToEnemy — повернуть группу широкой частью к противнику.
    JoinCollidedGroups — соединение групп, которые случайно врезались друг в друга и запутались.
    CoptersStrategy — стратегия убегания вертолетов за бмп в случае опасности от вражеских истребителей.
    FightersStrategy — стратегия погони истребителями за вражескими вертолетами, а также защиты танков и ремонтных машинок от вертолетов.
    FactoryDefence — защита фабрик от захвата, когда враг приближается к ним слишком близко.
    FacilityCapture — захват фабрик, с возможностью переназначения целей захвата если ситуация на поле боя меняется
    KillProduction — уничтожение беззащитных вражеских юнитов, которые производятся на фабрике.
    PotentialField — То самое старое ПП, которое практически не поменялось с момента 1го раунда. Как видите, является наименее приоритетной стратегией.

    Ну а пока писались все эти стратегии, перед вторым раундом, я со спокойствием наблюдал, как мой бот, мелкими группам без проблем разносит оппонентов в режиме “со строениями”. И казалось, что никто даже и близко ничего не может противопоставить и в таком же виде оно дойдет до финала. Пока не появился ud1. Он не разделял отряды так мелко, а использовал всего 5 штук, по 100 на каждый тип юнита. Помню как в серии боев со мной — победил все. Я был в шоке. Как же так, начал разбираться. Оказалось что организаторы подрезали скорость захвата фабрик, и мои маленькие группы слишком медленно их захватывали. Переделал стратегию захвата фабрик чтобы одновременно могло захватывать сразу 2 группы, и ситуация против ud1 вроде на время нормализовалась. Но через несколько дней опять двадцать пять! После внимательного изучения повторов пришел к выводу, что мои группы слишком бояться его больших групп, постоянно отступают, сдают уже захваченные фабрики, а перехватить его фабрики тоже не хватает силенок, потому что там уже успевают построится танки… Буквально в тот же вечер принял решение не делить так мелко. И сделал из танков, бмп и ремонтных машинок 3 большие пачки по 100 юнитов. Изначально меня останавливала от такого шага боязнь что большие группы будут сильно уязвимы для ядерного удара. Но, как показала практика, захват и удержание фабрик на начальном этапе — больше влияет на исход боя. Плюс на фабриках тоже начал строить танки, как более универсальный юнит. Вертолеты хоть и мощнее против земли, но медленнее строятся и слишком уязвимы от истребителей. Тесты с прошлой версией своего бота показали полную доминацию новой версии.

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

    public interface GroupStrategyTrigger {
      boolean isShouldApply();
      boolean apply(Move move);
    }

    Метод isShouldApply() вызывается стратегией у всех групп, которые в данный момент выполняют данную стратегию, и которые имеют триггеры. Если isShouldApply() возвращает true, то вызывается apply. Если и apply возвращает true, то значит стратегия совершила свой ход из триггера, и ход завершается. Если после выполнения apply триггер не поменялся, то он удаляется. Триггер может из apply() вернуть false и служить чисто в качестве выключателя стратегии для группы, при наступлении некоего условия, чтобы она снова могла рассматриваться менее приоритетными стратегиями. Это все позволяет выполнять сложные цепочки действий, нанизывая триггеры как бусы. Например совершить движение группой — это не так просто, вначале надо удостоверится что она выбрана.

    selectAndCallTrigger(movedGroup, move, new SelectGroupActionStrategyTrigger() {
      @Override
      public boolean apply(Move move) {
         performMoveAction(movedGroup, target, target, move);
      }
    });
    

    Метод selectAndCallTrigger(), который повсеместно используется, проверяет выбрана ли группа. Если да, до триггер выполняется сразу, а если нет то действие CLEAR_AND_SELECT выполняется на этом тике, а переданный триггер на следующем, когда придет время сделать ход, и управление дойдет до этой стратегии. Если после выделения группы более приоритетная стратегия перехватывает управление и тоже совершает выделение уже другой группы, то триггер SelectGroupActionStrategyTrigger текущей стратегии удаляется, но случается такое не очень часто. Это лишь простейший пример. В объединении групп например используется 3 вложенных триггера. Преимущество этого подхода в том, что вся логика относящаяся к стратегии расположена в одном отдельном файле, нет кучи if-ов и выглядит как последовательность действий разделенная условиями в isShouldApply(). И как результат — позволяет очень быстро колбасить новые стратегии, не ломая и не затрагивая остальные.

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

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

    public boolean isCanSafelyMoveToPoint(Group g, Point target) {
      prepareCachesForGroup(g);
      return !isHasCollisions(g, target) && !isGroupInDanger(g) && calcBattleScoreOnPath(g, target) >= 0;
    }

    Идем к примеру захватывать фабрику, и каждый ход проверяем все группы, которые двигаются, используя триггер — “путь к цели свободен и безопасен?” Если нет — то завершаем стратегию для группы.

    После введения тумана войны, практически не переделывал бота. Добавил только запоминание позиций вражеских юнитов, где видел их раньше. У истребителей разведчиков добавил дополнительный приоритет “просветить” клетки со скрытыми вражескими юнитами. Если разведка показала, что в клетке больше нет скрытых юнитов — то полностью убираем их, как будто их убили.

    Другие хитрости

    Для того, чтобы бот сразу не тратил все действия, а потом не провисал без команд, было сделано, чтобы отведенные действия тратились равномерно в течении 60 тиков.

    Когда у противника остается 100 тиков для следующего ядерного удара, каждое следующее действие выполняем на 1 тик позже чем могли бы. Это помогает “зарезервировать” некоторое количество действий перед ядерным ударом чтобы развести юнитов в стороны.

    Движение на ход противнику. Если ПП приказывает идти в клетку, и в ней есть юниты противника, которых группа может атаковать, то движение совершается не в центр клетки. По среднему вектору движения юнитов противника и расстоянию до них прогнозируется точка по ходу его движения, в которой можно их перехватить. И группа отправляется сразу в эту откорректированную точку.

    В бою важно чтобы юниты стояли как можно более плотно прижаты друг к другу, без пустот. Это дает более сконцентрированный огонь. Погода и ландшафт влияют на скорость юнитов, и если ничего не предпринимать плотная начальная формация группы постепенно распадается, вытягивается… Чтобы определить плотность, можно поделить площадь круга содержащего группу, на суммарную площадь юнитов. Результат до 3 — я считал терпимым. От 3 до 5 — разреженно. Больше 5 — сильно разрежена.

    Можно бороться с этим двумя способами:

    • Периодически делать команду SCALE внутрь группы. Иногда он плохо срабатывает, потому что юниты выстраиваются в длинные колбаски которые блокируют движение.

      Тогда после сжатия можно выполнить раскрутку вокруг центра группы, и потом снова сжатие. Так повторять несколько раз. Но и так не всегда помогает, т.к. юниты имеют свойство застревать даже при вращении.
    • Изначально, пока группа сжата, всегда двигаться ею с минимальной скоростью на текущем пути движения. Т.е. например если путь истребителей пролегает только по клеткам ясной погоды — то скорость не ограничивается, если там есть хотя бы одна клетка с грозой, то сразу при движении выставляется скорость для грозовой погоды. При таком подходе группа почти гарантировано не распадется. Этот подход я использовал для воздушных юнитов. Но не для земли, т.к. для земли важна максимальная скорость, для быстрого захвата строений. Авиация же здания не захватывает и скорости у неё и так достаточно.

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

    Каждый ход стратегия захвата зданий строит некий “оптимальный” план захвата. “Оптимальный” в кавычках, потому что это очень грубая и приблизительная оптимальность, и совершенствовать её можно было бы еще долго. Потом стратегия сверяет с текущим выполнением, в порядке по убыванию приоритетности захвата. Если обнаруживается отклонение от “оптимального” плана — то выполнение тут же корректируется. Таким образом стратегия захвата чутко реагирует на изменяющуюся на поле боя ситуацию.

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

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

    Чего не хватает данному боту чтобы достичь совершенства?

    Нет синхронных атак несколькими группами. Допустим, если у меня есть 2 группы по 30 танков, а у противника между ними 1 группировка в 40 танков, то они каждая по отдельности будут бояться. А в идеале должны были бы одновременно напасть с разных сторон. Казалось бы довольно очевидное для человека рациональное поведение, но так и не сообразил как это проще запрограммировать. Слишком много на этот маневр времени тратить не хотел, поэтому откладывал на потом, но так руки и не дошли.

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

    Плохое микро в бою за счет примитивного анализатора боя. Это было наглядно продемонстрировано ботом Milanin, который в плане миро выше всех на 2 головы. Он, управляя фалангами из 20 танков и 20 ремонтных машинок, умудряется иногда без потерь перестрелять превосходящие силы, умело двигаясь и вращая эти фаланги танками в сторону противника. К сожалению у Milanin-а очень медленный начальных захват карты из-за сборки тех самых смешанных фаланг. Поэтому даже не самый топовый бот может его задавить чисто количеством юнитов, произведенных на более быстро захваченных фабриках.

    Заключение

    В итоге у меня получился на мой взгляд довольно крепко сбитый бот, с отсутствием откровенно слабых мест. Когда смотрю повторы, не замечаю слишком критичных ошибок. Чего-то сверх гениального в нем нет. До начала финалов не был уверен что выиграю, т.к. в тестовых играх с другими топами, такими как Adler, oreshnik, Milanin — результаты были нестабильными. Но, как оказалось, очень неожиданно для меня самого — первое место с большим отрывом.

    Исходный код бота доступен тут.
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 50

      +2
      Поздравляю с победой!
      +1
      Спасибо за интересный рассказ и деятельное участие!
        0
        Эта статья может быть интересна… интересующимся тематикой AI

        А где тут AI? Кучка if'ов?

          +7
          AI — внутри классов стратегии, а что там — из статьи не видно. Вообще, разве не «кучка if'ов» стоит за любыми действиями нормального интеллекта, по крайней мере, в рациональной его части?
            +7
            Конечно нет. Все же в 2017 знают, что AI == TensorFlow.
              +7
              Термин искусственный интеллект — довольно многогранен. Написание игровых ботов, это одна из граней. Вы наверно путаете с машинным обучением, которого тут действительно нет.
                –2

                Цитаты из вашей же ссылки:


                Бот использует нечёткую логику, нейронные сети и машины конечных состояний для того чтобы «думать».

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

                Для менее сложных ботов, таким является любое событие, на которое они не запрограммированы реагировать.

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

                  0
                  Описанный вами бот способен делать только то, на что он запрограммирован

                  Именно так — грубо говоря «использует машины конечных состояний». Боты для компьютерных игр в основном так и пишутся.
                    +1
                    Боты для компьютерных игр в основном так и пишутся

                    Мои боты: этот и этот — другие :)
                      +1
                      И всё же никогда не видел, чтобы под соревнование с достаточно ограниченным количеством времени и более-менее ясными правилами (которые, правда, меняются, но не сильно) писали бота, где основное в принятии решений ложилось на ML. Если речь идёт про топовые места, конечно.

                      Буду даже рад (и не только я), если поделитесь ссылкой на такое событие.
                +1
                А откуда ему тут взяться, если даже нельзя подключать сборки? Львиная доля времени тратится на то, чтобы, грубо говоря, запрограммировать умножение вектора на число.
                Использовать наработки с прошлых чемпионатов: это всякие утилитные классы вроде точки, вектора, отрезка, всякие самописные математические функции.

                Справедливости ради стоит заметить, что в большинстве игр тоже кучка if-ов. Исходники не посмотреть, но готов поставить, что редко где встретится даже минимакс или автоматы.
                  0
                  Исходники не посмотреть

                  Ну почему не посмотреть? Нпр., Quake и др. классические игры Дж. Кармака лежат в открытом доступе.
                +3
                Поздравляю с победой.
                Мда уж, такое количество идей, стратегий, кода и времени — титанический труд.
                Я то думал мои 20 классов: самописные корутины, драйвера, динамический ПП(от 16х16 до 512х512) + А* для поиска путей воизбежании коллизий + часов 30 времени — это слишком много. В очередной раз убеждаюсь, что нужно брать отпуск с 7 ноября и плотно подсаживать себя на РАИК
                  0
                  Причем если допустим имеется 2 танка с процентом прочности 0.5 оба, то симулятор боя просто суммирует все HP и считает что это 1 целый танк.

                  А почему так? Ведь это же 1 единица прочности, но 2 единицы урона!
                  Причем если в группе соперника имеется несколько типов юнитов, то стреляет по каждому типу по очереди.

                  Интересно, а как выбирается очередность?
                  Например, в реальном боевом налете, реальной авиацией, я имею ввиду — приоритетной задачей всегда является уничтожение ПВО противника, а уже потом — собственно нанесение ущерба противника. Т.е. ПВО давят не считаясь с потерями, и только когда оно подавлено — приступают к штурмовке. А здесь как?
                    0
                    А почему так? Ведь это же 1 единица прочности, но 2 единицы урона!

                    Совершенно верно! Когда пытался учесть не только суммарное hp, но и колличество юнитов — внезапно начал выходить за лимит времени. Поэтому бросил эту затею. Похоже текущая боевая система оказалась хорошим компромиссом между быстродействием и точностью, и позволила выделить больше времени на другие вещи.

                    Интересно, а как выбирается очередность?

                    В финальной версии есть стратегия управление истребителями c высоким приоритетом, и одно из её заданий — это погоня за вражескими вертолетами, которые в данном конкурсе пресдтавляли наибольшую опасность.
                    +1
                    Отличный подход к делу, молодец что не растерялся на старте!
                    Бот на с++?
                      +2
                      Спасибо, бот на java
                      +5

                      Напомнило


                      if (goingToCrash) { 
                          dont(); 
                      }
                        0
                        Привет. Помню тебя еще по PlanetWars. Поздравляю с победой! было интересно изучить описание твоей стратегии.
                          0
                          Не проморгать начало, лучше начать сразу с беты.


                          Что верно то верно. Получил письмо за 5 дней до первого раунда, посмотрел условия, пару игр соревнующихся в песочнице, да закрыл.
                            0
                            А есть возможность локально у себя погонять против вашего бота? В Local runner возможно противником поставить вашего бота?
                              0
                              Да, там в репозитории есть версии бота. Берите 26, вроде последняя. Это обычный jar который запускается с помощью java 8
                              +1
                              Эх, вот на этой строчке:
                              Помню как ходил около часа по квартире кругами, и перебирал в голове разные способы организации кода.
                              прямо за душу взяло. Я хоть и не тратил на соревнования отпуск, но тоже помучился с организацией кода. Еще в магах придумал использовать понятие «миссии» — сходить за руной, похилиться, дефать базу, атаковать. Правда топ был далек, но все равно интересно время провел :)
                                0
                                Весьма интересный рассказ, тоже думал поучаствовать, но времени так и не получилось найти.
                                Откуда столько интересных решений по ИИ?) Читаешь книги какие?) Можешь посоветовать, как к теме игрового ИИ подбираться на примере текущего AI Cup?)

                                Ещё конечно было-бы интересно узнать, использовал ли кто-то подходы вроде Reinforcement Learning (машинное обучение в целом) в этом чемпионате)
                                  0
                                  Могу посоветовать «Искусственный интеллект, Современный подход» Стюарт Рассел и Питер Норвиг. Книга фундаментальная — большая и сложная. Сам читал выборочно.
                                  0
                                  Поздравляю с победой.
                                  И позвольте вопрос: если я правильно понял, Альфа-бета не использовался. Почему? Это классический подход ИИ для антагонистических игр.
                                    0
                                    Спасибо. Альфа-бета отсечения, это оптимизация для алгоритма Минимакс, который используется в пошаговых играх, где соперники делают ход поочередно. Данная задача не относится к такому типу игр.
                                      –1
                                      Минимакс, который используется в пошаговых играх, где соперники делают ход поочередно. Данная задача не относится к такому типу игр.
                                      См. Википедию:

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

                                        Минимакс в данном случае достаточно сложно применить в виду большой ветвистости. Другими словами слишком много вариантов действий (атаковать, отступать, куда атаковать, куда отступать, кидать ли бомбу, объединять ли в отряд). Т.е. как минимум нужны эвристики или другие способы уменьшить ветвистость. Но глубина просчета всеравно наврятли будет достаточно большой. Возможно в данном раскладе тут мог подойти MCTS лучше.
                                        Тем не менее, в игровом ИИ достачно большое разнообразие подходов, которые имеют свои плюсы и минусы в разных задачах (в т.ч. не стоит забывать про сложность имплементации, т.к. время ограниченно и участие идивидуальное). Данный конкурс показал, что в текущих условиях разработки и игрового мира подход автора статьи оказался наиболее оптимальным из всех, которые опробовали другие участники.

                                          0
                                          Минимакс в данном случае достаточно сложно применить в виду большой ветвистости.
                                          А в шахматах не сложно? Понятно, что нужно отсекать ветви.
                                          Тем не менее, в игровом ИИ достачно большое разнообразие подходов, которые имеют свои плюсы и минусы в разных задачах (в т.ч. не стоит забывать про сложность имплементации, т.к. время ограниченно и участие идивидуальное). Данный конкурс показал, что в текущих условиях разработки и игрового мира подход автора статьи оказался наиболее оптимальным из всех, которые опробовали другие участники.
                                          Какое отношение ИИ к сложности имплементации? Никто не спорит, что автор статьи отлично справился с заданием. А вот что касается организаторов, то ИМХО можно было сделать функции более высокого уровня, чтобы участники занимались ИИ, а не организацией элементарных действий юнитов.
                                            0
                                            В шахматах не сложно — как раз-таки потому, что сравнительно мало ветвей, соответственно несложно просчитать достаточно глубоко. Именно поэтому в го минимакс применить сложнее — ветвей слишком много, глубина выходит недостаточной.
                                              0
                                              несложно просчитать достаточно глубоко
                                              В шахматах «достаточно» зависит от силы противника (человека или программы). Гарантированно достаточно удается посчитать в крестиках и ноликах 3х3 — там у программы невозможно выиграть. А в Го, нпр., я играю настолько плохо, что простые программы из «интернетов» меня легко обыгрывают.
                                    +1
                                    Поздравляю с победой! Титанический труд проделан.
                                    В этом году был такой необычный способ управления (нет возможности микроконтроля) что я надеялся кто-нибудь попробует бота на нейронке сделать.
                                    Было бы очень любопытно посмотреть на что он способен был бы и смог ли бы тягаться с такой серьезной ручной реализацией.
                                      +1
                                      Спасибо! Жаль ты в этом году не поучавствовал. Мне вот тоже интересно, можно ли было бы сделать что-то похожее на бота TouchAI с применением машинного обучения. Чтобы без групп, без ПП, а чисто управляемый хаос юнитов :)
                                      –3
                                      можно ли было бы сделать что-то похожее на бота TouchAI с применением машинного обучения
                                      И обучения нет… Где же ИИ? Отсутсвие ИИ заслуг победителя не умаляет, а вот устроители ИМХО быстрого и удобного выхода на AI не обеспечили. Жаль :(
                                        –3
                                        Я спросил недостаточно громко? Преспрашиваю: ГДЕ ИИ? И ЗА ЧТО МНЕ МИНУС???
                                          –3
                                          А можно еще минус? А то у минусатора слов нет — одни негативные эмоции, опасные появлением комплекса неполноценности. (Хочу просто спасти такого бесценного участника!)
                                            –2
                                            Спасибо за минус. Вам полегчало? Аргументы не появились? — Если нет, то не огорчайтесь, аргументировать не каждому дано — минусовать проще :)))
                                            (Надеюсь, что над этими минусами не только я посмеюсь — такой забавный минусатор попался!)
                                              0
                                              Уважаемый, здесь так не принято.
                                                –1
                                                Как не принято?
                                                И как принято? — Говорить «уважаемый», как в кабаке 100 лет назад. И разбрасывать минусы не в силах объяснить причину. М.б. Вы серьезный форум с какой-то соц.сетью перепутали?
                                            +1

                                            ИИ перед вами (имхо). Довольно часто в этом соревновании возникают дискуссии по поводу того, что если в решениях нет машинного обучения или нейронок "хотя бы", то это не ИИ. "Что считать ИИ?" — тема достаточно философская. Мое личное мнение, что, в контексте данных соревнований, искуственным интелектом можно назвать программу, которая выполняет задачи, которые традиционно считаются прерогативой человека (играет в игру), не привязываясь к внутреннему устройству.
                                            А уж победит тот бот, который лучше подстроился под условия игрового мира и критерии оценки.

                                              0
                                              Здесь пример игры, где без ИИ оказалось проще. И предложено определение ИИ без философии.
                                              А уж победит тот бот, который лучше подстроился под условия игрового мира и критерии оценки.
                                              А м.б. в первую очередь под условия недостатка времени? М.б. было бы больше времени при иной задаче — не возникало бы вопроса «где ИИ»?
                                            +1
                                            ИИ — понятие широкое. Шахматный ИИ, например, делали без всякого машинного обучения (классически, может сейчас и обучают..) — там эвристики и перебор. Но по большому счету любое обучение — это оптимизация а значит тоже перебор, только «на уровень выше».
                                            Представленный ИИ тоже делает различные переборы и моделирование. Разница только в количестве того что автоматически подбирается а что было подобрано вручную программистом.
                                              0
                                              В основе классических шахматных программ альфа-бета (АБ). Недаром я про АБ спосил выше. АБ хорошо изучен и обоснован, в его случае вопросов про ИИ не возникает. А тут чистая эвристика, которую по понятным причинам ни изучить толком, ни обосновать было невозможно. В этом принципиальная разница. Крайний пример: генератор случайных чисел. Его часто используют в играх, но никто не называет такой подход ИИ.
                                                +1
                                                Не вижу «принципиальной» разницы. Альфа-бета — не особо сложный алгоритм, шахматный алгоритм на одном АБ с тривиальными эвристиками будет очень слабый. Основные достижения в силе шахматного ИИ были достигнуты именно эвристиками, базами эндшпилей и т.п. И все это точно так же невозможно обосновать (попробуйте, например, обосновать эвристику в шахматах: на конце ветви АБ просчитывать 2 хода противника подряд..), но это не мешало использовать термин ИИ.
                                                Конечно это очень специализированное решение и из него турдно что-то взять для написания ИИ для другой игры. Но это не повод принижать ценность или интересность данного решения. Для такой игры вообще очень трудно придумать что-то универсальное, перебор и моделирование не работают при таких масштабах и количестве рандома.
                                                  0
                                                  Но это не повод принижать ценность или интересность данного решения
                                                  Никто не принижает. Никто не говорит, что ИИ лучше. Важно решить задачу, а будет это ИИ-решение или нет не столь важно. Поэтому вопрос в классификации. Нет смысла валить все в одну кучу и все сложные задачи называть ИИ.
                                                    0
                                                    PS
                                                    Для такой игры вообще очень трудно придумать что-то универсальное, перебор и моделирование не работают при таких масштабах и количестве рандома.
                                                    Так м.б. организаторам нужно было выбрать другую игру?
                                            0
                                            Ааа подскажите, пожалуйста, по потенциальным полям — вот стоит в дальнем углу противник.
                                            Он должен генерировать притягивающее потенциальное поле. Волнующие вопросы:

                                            1) Как подбирать значения эмиттера? Ставить какие-нибудь 10000, чтоб затухая на 1 по клетке волна гарантировано дошла до края карты? Возможно, просто что-то не так понимаю.

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

                                            Заранее огромное спасибо, тема очень интересная.
                                              0
                                              1) Можно ставить значение намного меньше, но затухать обратно пропорционально расстоянию, типа value / dist, или, если нужно более медленное затухание — value / log(dist), если более резкое, то value / dist^2, тут можно играться с различными формулами и смотреть что получается.
                                              2) Да, под каждый тип юнитов может быть свое множество потенциальных полей которые суммируются.

                                            Only users with full accounts can post comments. Log in, please.