Java, Scala, .NET, Lisp, Python, IDE's, Hibernate, MATLAB, Mathematica, Physics & Other

воскресенье, 14 декабря 2014 г.

Warlight AI Challenge

Думаю самое время открыть немного подробностей про устройство бота GreenTea, написанного для Warligh AI Challenge. Но вначале немного об самой игре Warlight и конкурсе.

Об игре

Warlight - бесплатная стратегическая онлайн игра подобная Risk-у. Появилась если не ошибаюсь около 2010 года, постоянно развивается и уже обросла мощным сообществом игроков.


Это карта Small Earth, Вообще же карт существует огромное множество и энтузиасты постоянно создают новые. По сути карта - это связный граф. Он побит на подмножества (чаще всего не пересекающиеся) называемые бонусами. Например на карте выше можно видеть такие бонусы как Южная Америка (2), Африка (3), Европа (5), Азия (7), Северная Америка (5), Австралия (2). Цифры в скобках - величина бонуса, об этом дальше. Игра начинается с того что каждому из игроков предлагается выбрать начальные регионы для себя. В отличие от шахмат, где игроки ходят по очереди, тут ходы делаются одновременно. Обычно в игре людей на ход отводится по 5 минут, хотя настройки времени могут быть любые.  Итак, после выбора начальных регионов, каждый игрок подтверждает свой выбор, движек игры разруливает коллизии (тут не буду вдаваться в детали как) и начинается игра. Конечная цель - уничтожить противника. Каждый ход у игрока есть величина прироста, обычно начальный прирост 5. Прирост - это кол-во армий, которые можно поставить на любых своих регионах. И нужно поставить обязательно все - перенести на следующий ход часть не разрешается. С каждого своего региона можно сделать ход армиями на смежный регион. Все движения армиями логически можно разделить на такие категории:
1. Развитие. После захвата бонуса (владения всеми его регионами) прирост игрока увеличивается на величину бонуса. Поэтому захват бонусов это первостепенная цель в начале игры.
2. Защита. Если бонус захвачен, то его нужно защитить, иначе враг может пробить один из регионов, и тогда мы бонус потерям. Также имеет смысл защищать свой регион если он мешает противнику захватить бонус.
3. Атака. Атака может быть направлена как на уничтожение противника так и на подрыв его бонусов. И то и другое приближает к победе.

Пример игры на карте Turkey. Тут баталия в самом разгаре и пока неясно кто выиграет:


В течении хода можно сделать много движений армиями. Каждое движение будет совершаться в том порядке, в котором они были заказаны.
При заказе движения армиями мы выбираем регион с которого двигаться, целевой смежный регион и кол-во армий. При воспроизведении ходов успех движения армиями зависит от того сколько армий двигалось, и сколько армий было в целевом регионе. Например, если двигалось 5 армий а в целевом нейтральном регионе было только 2 армии, то шанс захватить целевой регион близок к 100%. Если же в атаке было 50 армий, а в защите стояло тоже 50 вражеских армий, то шанс захвата 0%, кроме того атакующие еще и потеряют больше, потому что защищающиеся всегда имеют небольшое преимущество в бою. Вообще же в игре много рандома, однако настройки каждой игры можно гибко конфигурировать, вплоть до полного исключения всех случайных факторов.

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

О конкурсе

Задача соревнования - написать бота который будет играть в Warligh. Призы - хорошие :)
€ 1024 - 1 место
€ 512 - 2 место
€ 256 - 3 место
...
€ 8 - 8 место

Взаимодействие с движком осуществляется через стандартный input / output. Поэтому язык написания бота может быть любой. Разработчики конкурса откликаются и добавляют новые - если их просят.

На ход бот может использовать не более 2 секунд.

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

В первой части наибольшим недостатком было то что все действие происходило только на 1 карте Small Earth (см.выше). Поэтому большинство топовых стратегий были заточены именно под эту карту.

О написании AI для Warlight

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

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

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

Бот GreenTea

Этот бот изначально писался не привязываясь к какой-то конкретной карте. Именно этим я думаю обусловлено только 2 место в финале и на ладдере. 1 место использует стратегию, вручную оптимизированную под карту Small Earth. У меня не было задачи выиграть любой ценой. Целью я для себя ставил написание универсально крепкого бота, который играет более менее адекватно, и не делает глупых ошибок которые бы никогда не совершил хороший игрок в Warlight.

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

GameSimulator

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

AttackAnalyzer

Реализует расчеты для атак. Отвечает на вопросы такие как:
  • какая вероятность захватить регион с заданным кол-вом атакующих армий и заданным кол-вом защитников.
  • какие будут средние потери при атаке с обеих сторон.
  • что если повторить атаку N раз, принимая во внимание известные приросты атакующего и защищающегося - то в конечном итоге регион будет захвачен? И какие будут потери с обеих сторон?

ExpandAI

Занимается всем связанным с захватом бонусов:
  • вычисление какие бонусы следует захватывать в первую очередь.
  • из всех возможных способов захвата бонуса выбирает наиболее быстрый и оптимальный путь
  • вычисляет оптимальный способ захвата нескольких бонусов одновременно.

RegionPairAnalysis

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

StrategicScoresAnalyzer

Вначале идентифицирует так называемые стеки армий, у себя и у противника. Стек - это достаточно большое кол-во армий находящихся в одном регионе. Потом для найденных самых больших стеков, строит симуляции возможных ходов, на N (до 4) ходов вперед. Для каждого пути движения стеков полностью симулирует игру и дает оценку конечной позиции. Таким образом находятся оптимальные движения стеками, как для защиты своих бонусов, так и для атаки бонусов противника. Вообще это наиболее сложная и заоптимизированная часть бота. Если у нас к примеру 3 стека, и для каждого найдено 100 вариантов путей на 4 хода, то это уже 3 млн. вариантов перебора, что, очевидно, слишком много. Надо или уменьшать глубину или отсекать несущественные варианты.

ForecastGameEngine

Используется внутри StrategicScoreAnalyzer для симуляции игры с заданными маршрутами движения стеков и последующей оценкой позиции.

BattleAI

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

Warligh AI Challenge 2!

Наконец, после долгого перерыва,  Warligh AI Challenge 2 уже в стадии Beta,  На этот раз главная фишка в том, что карты генерируются случайно!



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

Постоянные читатели