Pull to refresh

Google AI Challenge две недели спустя

Reading time 10 min
Views 2K
Как многие уже знают, недавно началось Google AI Challenge — соревнование по созданию ботов для игры Planet Wars, проводимое университетом Ватерлоо и поддерживаемое Google. Вчера подошла к концу уже вторая (из девяти) неделя с момента официального старта. Соревнование всё больше начинает напоминать гонку вооружений, и если в начале для попадания в топ 50 было достаточно бота, который в большинстве случаев просто обыгрывал примеры из стартового набора, то теперь прийдётся постараться. О том как это можно сделать, а также о новостях турнира под катом.

Сообщество

Первые недели были ознаменованы проблемами у организаторов: это и производительность сервера, и случаи «грязной» игры, различные конфликты стартовых наборов и рабочего окружения у пользователей, проблемы с отправкой кода 12-13 числа. Но, к их чести, всё решалось достаточно быстро. Ну или почти всё… До сих пор каждый бот играет в среднем около раза в час, а значит, для того чтобы понять как изменения в коде отразились на рейтинге, приходится ждать день-два (на следующей неделе возможно добавят ещё один сервер). Частично эта проблема решается неофициальным TCP-сервером к которому можно подключать бота напрямую со своего компьютера. Частота игр при этом значительно увеличивается и, как плюс, появляется возможность сохранять у себя отладочные данные. Основной недостаток в том, что на сервере нет большинства топовых ботов, поэтому результаты имеют смысл лишь на время тестирования или переработки кода. И последняя из новостей: за это время к списку из поддерживаемых C++, C#, Java и Python были добавлены долгожданные Lisp, Haskell, OCaml и CoffeeScript, а также малоизвестная экзотика: PHP, Perl, Javascript и Ruby (или всё было наоборот?).

Теперь немного об утилитах, которые были созданы участниками. Оговорюсь что это взгляд со стороны пользователя Linux и специфичные для Windows вещи здесь отсутствуют. Итак:
  • JBotManager — запись и просмотр игр, клиент для TCP сервера, позволяет не разбираться с командной строкой и будет полезна в самом начале
  • Генератор карт с GUI-фронтэндом
  • визуализаторы, которые уже не пересчитать:
    • PlanetWars pastebin позволяет загружать вывод PlayGame.jar и просматривать его онлайн
    • движок с визуализатором, переписанный на С++ — просто быстрее работает
    • ещё один, сделанный на Qt — отображает номера планет и их приросты
    • и последний на основе HTML5 — конвертирует вывод движка к формату официального Javascript плеера, работает из командной строки
  • удобный костыль для отладки — конвертирует вывод движка в набор данных, которые бот получал в процессе игры. Подав эти данные на вход бота можно запустить его без движка в режиме отладки. Работает, конечно же, только для ботов с однозначным поведением
  • многопоточный скрипт на Python для тестирования ботов

О разработке ботов

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

Симуляция

Необходимо знать что произойдёт с любой из планет через несколько ходов, с учётом приростов и летящих кораблей. Без этого невозможно корректно оценивать стоимость защиты или нападения. В упрощённом виде (без учёта правила одновременного нападения на нейтральную планету) это может выглядеть так:
public void simulate() {
    // List<Fleet> fleets - флоты, летящие к планете target
    if (fleets.size() == 0)
        return;
    sortFleets();
 
    // переменные с текущим рассчитываемым состоянием
    int owner = target.owner;
    int shipCount = target.shipCount;
    // хранит текущий обрабатываемый ход для аккумуляции результатов
    int lastGrowth = 0;
 
    for (int i = 0; i < fleets.size(); i++) {
        // если результаты хода подсчитаны - сохранить состояние
        if (lastGrowth < fleets.get(i).turnsRemaining) {
            if (> 0)
                states.add(new PlanetState(shipCount, owner, lastGrowth));
            // прирост только на планетах игроков
            if (target.owner > 0)
            shipCount += target.growthRate *
                    (fleets.get(i).turnsRemaining - lastGrowth);
            // этот ход далее будет рассчитан
            lastGrowth = fleets.get(i).turnsRemaining;
        }
        if (owner != fleets.get(i).owner)
            shipCount -= fleets.get(i).numShips;
        else
            shipCount += fleets.get(i).numShips;
        // смена владельца
        if (shipCount < 0) {
            shipCount *= -1;
            owner = fleets.get(i).owner;
        }
        if (i == fleets.size() - 1)
            states.add(new PlanetState(shipCount, owner, lastGrowth));
    }
}
Кстати, код с кириллическими комментариями не компилируется на сервере, поэтому будьте внимательны перед отправкой. После того как изменения состояний рассчитаны, получить прогноз на любой ход достаточно просто:
public PlanetState getInfoForTurn(int turn) {
    int growth = target.growthRate;
    // случаи когда не было входящих флотов и
    // когда запрос идёт для хода до прибытия первого флота
    if (states.size() == 0 || states.get(0).turn > turn) {
        // на нейтральных планетах нет прироста
        if (target.owner == 0) 
            growth = 0;
        return new PlanetState(target.shipCount + turn * growth,
                target.owner, turn);
    }
    int last = states.size() - 1;
    // ход после прибытия последнего флота
    if (turn >= states.get(last).turn) {
        if (states.get(last).owner == 0)
            growth = 0;
        return new PlanetState(states.get(last).shipCount +
                (turn - states.get(last).turn) * growth,
                states.get(last).owner, turn);
    }
    // ход между прибытием первого и последнего флотов
    for (int i = 1; i <= last; i++)
        if (states.get(i).turn > turn) {
            if (states.get(i - 1).owner == 0)
                growth = 0;
            return new PlanetState(states.get(i - 1).shipCount +
                    (turn - states.get(i - 1).turn) * growth,
                    states.get(i - 1).owner, turn);
        }
    return null;
}

Ведение логов

Во-первых это один из способов получения отладочной информации и «правильный» лог анализировать удобнее, чем визуализацию в плеере (хотя они не взаимоисключают друг друга: на официальном форуме проскакивали ссылки на патчи, позволяющие отображать отладочную информацию в плеере). А во-вторых логи позволяют проводить пакетную проверку результатов игр. Вообще, автоматизация тестирования экономит массу времени и нервов.

Переключение стилей игры

Уже слышу возражения. На самом деле вы правы, можно и обойтись… но то что правилами рагламентирована длительность игры (200 ходов), то что в дебюте проще брутфорсить, а также различия в размере карт вынуждают менять стиль. Например:
if (myPlanets.size() < 4)
    mode = BotMode.bmStart;
else if (myPower > enemyPower * 3 && turn > 50)
    mode = BotMode.bmFinishHim;
else if (turn > 180 || myPower * 5 < enemyPower * 4)
    mode = BotMode.bmRegenerate;
else 
    mode = BotMode.bmNormal;

Оценочные функции

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

Стандартные приёмы

Кроме, очевидно, атак, желательно реализовать такие стандартными приёмы как:
  • перехват нападения на нейтральную планету. Идея в том, чтобы послать флот в такой момент, чтобы он долетел на следующий ход после захвата планеты соперником. В этом случае вы получаете её по минимально возможной цене;
  • защита собственных планет. Тут пригодится симуляция. Рассчитав на каком ходу вашу планету захватят и какова будет итоговая численность кораблей, вам будет достаточно выслать перекрывающее количество с ближайших планет для защиты;
  • рашинг спорных планет. Когда оба бота достаточно умны чтобы защищать свои планеты и нападать на выгодные чужие, появляются точки, за которые идёт борьба, а флоты, посылаемые на них противниками уравновешиваются. Именно для таких случаев нужно уметь рассчитывать предел «волны» которую оппонент сможет отразить и, конечно же, предоставить ему чуть больше;
  • перенос флотов с отдалённых планет. Это решает проблему больших карт, когда фронт действий уходит за пределы радиуса, по которому вы выбираете источники для отправки флотов, а планеты оставшиеся за ним, просто наращивают мощь, но никуда её не направляют. Простейший способ — считать сколько флотов отправлено с каждой из планет и отправлять с тех планет где это число нулевое к тем где оно больше с учётом расстояния.

Модификация стартового набора

Желательно переписать предоставляемый организаторами код для парсинга и осуществления простейших операций с игровыми объектами. Судя по Java, стартовый набор написан действительно криво. Учитывая что язык и так не самый быстрый, лучше допилить. К слову, для многих языков уже есть модифицированные стартовые наборы где эти проблемы решены

Что же дальше?

Перечисленного выше с лихвой (пока что) хватает для попадания в топ 50. Дальше пригодятся оригинальные подходы и использование математического аппарата. Из основных направлений по которым можно развивать бота отмечу:
  1. История. Учёт результатов прошлых ходов позволяет следить за потоками, выявлять места концентрации трафика и реальные приросты по принципу
    realGrowth = growthRate + (fleetsInMy — fleetsInEnemy — fleetsOut) / historySize
  2. Анализ карты. В простейшем случае эта задача решается введением оценочной функции, которая учитывает среднее и минимальное расстояние до своих и чужих планет, приросты и количество кораблей на них. В случае посложнее возникают задачи поиска оптимального пути и максимального потока в графе.
  3. Анализ возможных ходов. После выбора целей, для каждой из них можно сгенерировать несколько наборов наиболее удачных планет с которых можно провести атаку. При этом для каждого набора будет иметься оценка эффективности и количество кораблей которое нужно отправить для захвата или защиты (причём это количество можно перераспределять между планетами). Возникает проблема выбора такого набор ходов, который при отправке доступного числа кораблей принесёт максимальную пользу. Это немного модифицированная задача упаковки.
  4. Выжидание. Есть боты, которые каждый ход весь прирост с каждой из планет отправляют по наиболее приоритетным направлениям. Возникает ощущение что все они «работают», но так ли это? Отправленные флоты гораздо проще обсчитать сопернику: у них уже есть цель в отличии от выжидающих. При этом появляется возможность дождаться такой цели, которую можно наверняка (ну или почти наверняка) захватить или наоборот остаться в обороне. Поэтому важно понимать что атака мелкими порциями скорее зло, потому что результата вы все равно не достигните пока общая масса не перевалит за некоторую отметку. Так почему бы не дождаться момента когда эта масса у вас накопится. И ещё один факт: отправленный флот до момента достижения цели находится вне игры, поэтому важно учитывать расстояния, чтобы не возникало ситуаций, когда атака превосходящими силами достигает цели к моменту когда вас стёрли в прах.
  5. Расчёты между ходами. По правилам таймаут для хода составляет 1000 мс и ботам нельзя использовать потоки. Зато можно считать в моменты, когда после завершения хода движок их обрабатывает. В эти моменты можно работать с историей, вычислять и кешировать величины которые редко изменяются (например, расстояния между планетами, потоки, приоритеты нейтральных планет и т.д.)

Заключение

И про «AI» в названии. Вряд ли имеет смысл использовать нейросети или генетические алгоритмы для реализации общей логики работы (для этого гораздо лучше подойдут процедурщина или многоагентные системы), но их можно применить для решения выделяемых задач поиска путей/потоков, распознавания и оценки целей, а также задач упаковки. Подходы, связанные с ИИ на данный момент никто не использует, или они не приносят значимых преимуществ, или пока что эвристический поиск для последующего брутфорса всё еще укладывается в таймауты и позволяет побеждать. В любом случае дальше будет ещё интереснее. Посмотрим, оправдает ли себя название через месяц-два. Надеюсь лишь, что после публикации количество русскоязычных участников увеличится.
Tags:
Hubs:
+75
Comments 35
Comments Comments 35

Articles