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

воскресенье, 2 декабря 2012 г.

Russian AI Cup 2012 - Tanks

UPD. Исходный код бота

В этом году посчастливилось принять участие в увлекательнейшем соревновании по программированию - Russian AI Cup. Тема - бои танков. Традиционно, задача участника используя данное организаторами API написать алгоритм управления ботом, выигрывающего игру у ботов других участников.

Узнал об этом соревновании от своего коллеги по работе SpookyCookie. С самого начала были амбиции занять первое место, но все оказалось очень не просто :) Однако, обо всем по порядку.

Краткое описание игрового мира

Имеется прямоугольное двухмерное поле на котором появляются танки. Танки могут двигаться, поворачиваться, стрелять, все как положено. Тривиальная формулировка игровой задачи - уничтожить вражеские танки или хотя бы нанести им максимальный урон, при этом не погибнуть и по возможности получить как можно меньше урона от врагов. За нанесенный урон даются очки, и побеждает тот, кто набрал больше всего очков. Урон делится на 2 типа: урон по здоровью экипажа, и по броне. Повреждая здоровье экипажа тем самым уменьшается эффективность танка, так что при минимальном здоровье скорость движения и скорострельность уменьшаются в 2 раза по сравнению с полным здоровьем. Однако чтобы причинить вред экипажу надо пробить броню. Чтобы это сделать необходимо чтобы снаряд вошел на большой скорости и по возможности под более прямым углом к поверхности брони. Если броня не пробивается, то снаряд наносит урон только по броне. Причем, если снаряд попадает под углом, более 60 градусов к нормали, то происходит рикошет, и урон не наносится. Да, чуть не забыл, разные стороны танка имеют разную толщину брони: фронтальная - самая толста, боковая - тоньше, и задняя - самая тонкая.
Танк считается уничтоженным если:
  1.  Здоровье экипажа падет до нуля.
  2.  Прочность брони падает до нуля.
Кроме того на поле в случайных местах время от времени появляются бонусы:
  1. Здоровье - исцеляет экипаж на некоторую величину.
  2. Броня - исправляет повреждения брони танка.
  3. Амуниция - дает 3 бронебойных снаряда, которые отличаются тем что они: медленнее обычных снарядов. Не рикошетят. Обладают большей бронебойностью. И наносят существенно больше * урона как броне так и здоровью экипажа. 
* не хочу нагружать точными цифрами, их вы можете найти в спецификации к игре.

Отличия от robocode

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

 Режимы игры

1) 6x1 - на поле 6 ботов и каждый сам за себя, и против всех.


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

2) 3х2 - 3 команды по 2 танка.
В этом режиме также велик фактор случайности, по аналогичной причине.

3) 2x3 - 2 команды по 3 танка.


Наиболее честная форма, если не считать асимметричность появления бонусов.

Причем режимы игры отрывались по мере развития соревнования. После 1 тура отборов открылся режим 2. После 2 тура - режим 3.

Чемпионат.

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

1 раунд отборов (10 по 11 ноября 2012, при том что началось соревнование 30 октября).
На него допускаются 900 лучших по результатам песочницы. Далее следуют два 12ти часовых этапа с промежутком в 24 часа в которых боты встречаются случайным образом. Режим игры только 6х1.

После раунда 1 открывается режим 2х3.

2 раунд отборов (с 17 по 18 ноября 2012 года).
Допускаются 300 прошедших 1 раунд + 45 лучших по рейтингу из песочницы из не прошедших раунд 1 (это поблажка была сделана намеренно в обход изначальных правил, для того чтобы поддерживать интерес тех кто по какой то причине не прошел раунд 1). Бои 2х3 в результате которых отбираются 50 лучших стратегий.

После раунда 2 открывается режим 3х2.

Финал (с 24 по 25 ноября 2012 года).
50 лучших встречаются в боях 3х2 волнами, причем в одной волне каждый бот встречается 1 раз с остальными 49 ботами. Аналогично раундам 1 и 2 проводится в 2 этапа по 12 часов с перерывом в 24 часа.

Путь GreenTea.

В первый же день как узнал о соревновании 30 октября, после работы, скачал стартовый пакет и начал кодить без остановки 8 часов. В 3 ночи упал без сил, но труд не прошел зря, и на следующий день с удивлением обнаружил своего бота то-ли на 1 то-ли на 2 месте. Это было очень обнадеживающее начало, но счастье не длилось долго.

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

Первая версия бота умела делать многие базовые вещи *:
  1. Двигаться к заданной точке передом или задом (в зависимости от того, как развернуться быстрее)  - брать ближайшие бонусы
  2.  Проверять, что на пути бота/пули нет препятствий для движения.  По началу, для простоты расчетов, все объекты считались кругами с определенным радиусом.
  3. Двигаться изначально в ближайший угол и сидеть там 1000 тиков =)  Подсмотрел эту стратегию у SkyHawk. 
  4. Поворачивать дуло в направлении цели и стрелять туда, где она сейчас находится.
  5. Поворачиваться боком к ближайшему танку у которого дуло направлено на меня и двигаться пока не доеду до препятствия. И потом назад.. В общем, такое волнообразное движения для снижения вероятности попасть в меня.
  6. Стрельба на ход движения танка. Совсем не многие умели уворачиваться от нее в первый день ;)
* тут, и дальше, перечисляю только самые важные и существенные  улучшения. На самом деле их было в несколько раз больше.

Осознание

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

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

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

Последующие улучшения:
  1.  Разбиение объекта игры Unit на сегменты, с возможностью дальнейшей работы с ними. Например можно точно проверить пересекаются ли тела. Или пересекает ли путь снаряда какие-либо помехи.
  2. Выбор наилучшей цели по очкам. На очки влияют: возможность пролета снаряда от танка до цели, расстояние (линейно, чем больше тем меньше очков), угол поворота дула до цели (линейно, чем больше тем меньше очков).
  3. Выбор лучшего бонуса по очкам. На очки влияют много факторов, основные это доступность бонуса для танка, расстояние и полезность данного бонуса в конкретный момент времени (например аптечку брать не нужно если экипаж полностью здоров).
  4. Плавные повороты при движении до цели. Грубо говоря, чем меньше оставшийся угол поворота, тем меньше должна быть разность мощностей подаваемая на гусеницы.

Легкая паника.

Насколько я помню через несколько дней бот начал сдавать позиции. И опустился в район 10-го места. Анализируя повторы было видно что во первых: очень влияет начальное положение. Позициям на 3 и 9 часах дальше других ехать в угол, они чаще оказываются под перекрестным огнем. Во вторых: после окончания 1000 тиков бот часто выезжал суицидально куда нибудь в самую гущу и легко расстреливался. На этом этапе не было проверки или расчета того где опасно а где нет. Едем туда, куда несут гусеницы :) В качестве костыльного решения добавил время от времени отъезд к позиции возле бортика, самой дальней от всех врагов.

Другие улучшения:
  1. Дополнительный приоритет атаки по танку который атакует меня. А то обидно было смотреть на ситуации когда атакую одного, которому до меня нет дела, а в это время, в бочину, практически в упор расстреливает другой.
  2. Подсчет в какую часть корпуса летит снаряд и как можно от этого лучше увернуться.
  3. Установка танка под угол 45 градусов.к противнику, чтобы повысить вероятность рикошета снаряда или, в крайнем случае, чтобы снаряд пробивал броню реже. Это улучшение в последствии я убирал и снова добавлял много раз, пока таки в конце не убрал совсем.
  4. При увороте от снарядов подкручиваться в такую сторону, чтобы повысить вероятность рикошета. Это улучшение потребовало нескольких часов медитации с ручкой и тетрадой, и рассмотрения всех возможных ситуаций подлета снаряда к корпусу, для всех сторон танка. Причем надо было еще учитывать текущее движение танка.

Соперники усиливаются

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

Другие улучшения:

  1. goAndKill. Если остался 1 на 1 с врагом и у меня есть преимущество по здоровью экипажа или по бронебойным снарядам тогда надо подъехать в упор и убить.
  2. Больший приоритет на собирание ближних бонусов которые жизненно необходимы в текущий момент.
В какой-то момент стало понятно, что уворачиваться от летящих в танк снарядов можно следующим образом.
  1. Проверяем в какую часть корпуса попадает снаряд.
  2. Имитируем движение вперед на полном ходу, и движение назад на полном ходу. И смотрим попадает ли снаряд в эту часть корпуса в первом и втором случаях. Если в каком то не попадает - то и двигаться в ту сторону.
Единственным вопросом является как посчитать изменение скорости танка при движении вперед и назад. Ведь организаторы не предоставили формул физики.. Пришлось ставить эксперименты! Я намерял значения изменения скорости по тикам игры. Получилось 2 таблицы. Первая для движения вперед, вторая для движения назад. Таблица имела 2 колонки <текущая скорость> <скорость на следующем тике>. Потом по этим данным в математическом пакете MATLAB построил полиномы 6 порядка, интерполирующие заданные точки. Получилось конечно не очень точно, но достаточно точно на первых порах. Для снарядов же заметил что для обычного снаряда для получения скорости на следующем тике надо умножить текущую скорость на 0.995 а для бронебойного снаряда на 0.99, поэтому и полиномы строить не надо. На основании всего этого были написаны функции нахождения позиции танка и снаряда через заданное кол-во игровых тиков.

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

Раунд 1


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

Главным недочетом моего бота было все же движение не по позиции. Заезды в опасные места, где он расстреливался с разных сторон. И ведь для этого соперники не должны быть сильными... Поэтому во время второй части раунда 1 я реализовал нечто, под названием тактическая карта. Идея в следующем. Разносторонне анализируются разные точки карты. В суммарную оценку точки входят: близость к врагам, к бонусам, направление дул танков, их здоровье (в будущем, количество параметров сильно увеличилось). Также анализируется точка к которой находится сам танк и выбирается то направление движение, которая ведет к лучшую позицию. Причем по пути движения танк не должен пересекать худшие позиции. Это очевидно, т.к. если для того чтобы взять бонус надо проехать зону в которую направлены стволы многих танков, то туда ехать точно не надо! В итоге танк стал намного более острожным, ну а старая версия без этого улучшения заняла только 20-е место в раунде 1.

Код - плохой.

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

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

Можно сказать случайно, набрел в интернете на обсуждение игры в котором приводились точные формулы движения вперед и назад. Они оказались очень простые - линейная зависимость =). Фейспалм конечно.. но что поделать, пришлось заменить свои жуткие полиномы 6 степени. Не знаю, честно ли я поступил или нет, украв формулы. С одной стороны без них мой бот был бы далеко не таким сильным. С другой стороны - голых формул мало, и ими надо еще удачно воспользоваться. Поэтому я не считаю, что совершил какое-то великое преступление воспользовавшись этими формулами, не выводя их самолично. Так же видел ссылку на точные формулы движения с учетом поворотов (!).. Но в то время еще не знал как ими воспользоваться, и поэтому забил.

Дальнейшие улучшения:

  1. Добавил в тактическую карту штраф если мои танки находятся слишком далеко или слишком близко друг к другу. Потому что если они близко то сложнее уворачиваться, а если далеко то могут перебить по одиночке.
  2. Расстрел бонуса аптечки который может быть взят врагом. Это улучшение в части боев было полезно, а в части вредило мне. Но казалось что полезнее оно все таки чаще.
  3. Повышенный приоритет атаки цели, которую атакует танк напарник.
  4. Фикс баги, что точки за бонусами считались очень безопасными для бота. В результате этой тактической ошибки бонус появившийся по среди карты мог приманить моих ботов, и после взятия танки оказывались в ужасном положении перекрестного обстрела.
  5. Реализовал функцию расстояния между двумя отрезками. С ее помощью существенно улучшил увороты.

За что отдельно спасибо организаторам, так это за своевременную реакцию на критику игроков и быстрое исправление недочетов. В боях 3х2 было 1 заведомо лучшая позиция, на 3х часах, т.к. боты появившиеся в ней имели больше простора для маневра, занимали правую часть карты, в то время как другие 2 пары воевали слева. И обычно пара на 3х часах побеждала. Было решено поворачивать начальные расположения ботов на случайный угол. При этом в виду прямоугольности карты по прежнему остались хорошие позиции и плохие, но в то же время появились и промежуточные позиции, так что сильные бот все равно мог затащить находясь в них. То же касается боев 6х1 где плохими считались позиции на 3х и 9ти часах.

Раунд 2

Второй раунд стал для меня наиболее провальным. Занял на нем только 39 место. С удивлением смотрел как совершенно не известные мне боты (не из топа песочницы) опережают моего. В голове не укладывалось как такое возможно и что я делаю не так..  Напомню, что порогом прохождения в финал было 50 место. Так что чуть не вылетел)

А с неизвестными ботами получилась вот какая история. Дело в том что система рейтинга плохо реагирует на изменение силы бота. Так что если бот был долго слабым, и стабилизировался на среднем рейтинге, то после выкладывания сильной версии, даже если она будет постоянно выигрывать, подниматься рейтинг будет очень не значительно. Вот эти то боты и притаились в засаде.. С заниженным рейтингом, но силой игры топовых ботов.

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

Большие планы

Чего то в моей голове засело число - 2 декабря. Якобы время финала. Я так был в уверен в этом  что даже не перепроверил. А раз времени до финала так много, то почему бы к примеру не переписать своего бота? Чтобы было все четко, меньше мусора, больше полезного кода в котором я уверен. Также были идеи оперировать при программировании ботом более высокоуровневыми понятиями. Приведу выдержку из своих записей по этому поводу:

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

- написать функцию проверки опасности позиции.
- написать функцию поиска позиции обстрела.
- написать функцию поиска безопасного пути и перемещения по нему.

суть алгоритма состоит в 
1. поиск безопасной позиции, движение к ней
2. находясь в безопасной позиции совершить безопасной перемещение в позицию обстрела. Из возможных позиций обстрела выбирать ту которая:
* ближайшая к текущему танку
* временно безопасная
* хорошая
после выстрела - возврат в безопасную позицию, если:
* позиция была опасна
* эта позиция под обстрелом нескольких вражеских танков.

И еще успею все протестировать. Замечательная идея! Два дня я рефакторил и кромсал код. На сайт решил не заходить, чтобы не отвлекаться и полностью посвятить себя кодированию. Через 2 дня, все таки захожу на сайт, и вижу: "до финала осталось 3 дня 4 минуты..".  Слегка прифигел. Вспомнил не злым тихим словом организаторов (хотя как оказалось они не виноваты).. Понял что уже не успею воплотить все свои идеи. Так же понял что работать с данным кодом дальше нельзя, слишком он покромсаный и неоттестированный. И с *okayface* вернулся к старой версии (кстати для контроля кода использую git). Два дня были потеряны.

3 дня

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

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

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

Во второй день взял отпуск на работе с твердым намерением сделать побольше в этот день. Но что? И где-то маленький чертенок на правом плече начал нашептывать "точные формулы движения".. что? "точные формулы движения, помнишь?" Да  но.. Хе-хе-хе. И в голове созрел дьявольский план. 
  1. Берем точные формулы учитывающие повороты, а не только движения вперед и назад.
  2. При расчете уворота от снаряда: генерируем все возможные (ну не все, на самом деле 24 варианта) варианты подачи мощности на гусеницы. Т.е. (1 1), (-1 -1), (1, 0.5) (1, 0) .... и т.д. И полностью симулируем движение танка и снарядов.. Тот вариант подачи мощности который словит меньше всего урона - лучший вариант для уворота. Причем во время симуляции еще можно подсчитать точный урон, с учетом пробивания брони и рикошетов.
Наблюдая за боями некоторых топовых ботов я понял, что похожая система работает и у них. Т.к. от некоторых выстрелов уворачивались безупречно четко, без точного расчета тут не обойтись.

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

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

Судя по боям на сайте сила бота возросла просто чудовищно.. Вот что значит точный расчет. Впрочем, были боты которые по прежнему убивали моего практически без шансов:
  • Mr. Smile - с убийственной тактикой ближнего боя.
  • Hohol - закончивший на 49 месте во втором раунде, и очень сильно улучшивший своего бота сейчас - мастер дальнего боя.
  • Commandos - сбалансированный агрессивный бот средней дистанции.
  • Megabyte - мастер дальнего боя.
  • Milanin - мастер позиционного боя и выверенных выстрелов.
  • SDil - сбалансированный бот предпочитающий дальние дистанции.
В 3ий день я добавил больше ради фана сбивание в полете опасных вражеских снарядов. Не надеясь, что это улучшение будет очень полезным. А также сделал проверку чтобы своим снарядом не попадать случайно по снаряду выпущенному напарником (а такое случалось частенько). Впрочем, моя симуляция полета снаряда почему то оказалась не совсем точной, и бот время от времени сбивал свои же снаряды, хотя и реже чем раньше. 

Финал

Какой бы не была хорошей симуляция но она все же была немного сыровата, и после первой части финала бот занял всего 11 место с 66% побед.
В перерыв перед второй частью были такие улучшения:

  1. Уклонения от снарядов выпущенных с упреждением так же, с помощью симуляции уклонения. Получается так, что один и тот же алгоритм запускается при уклонении от снарядов летящий прямо в танк, и от снарядов летящих с упреждением. Причем алгоритм учитывает все снаряды летящие в данный момент, до момента пока они не по врезаются или не остановятся.
  2. Уклонение от снарядов которые находятся близко к корпусу. Это включает ситуацию когда танк уворачивается от снаряда за счет вращения, и он уже увернулся - но снаряд еще очень близко, и если продолжить вращаться в том же направлении то можно словить его опять. Аналогично - включается симуляция уклонения от всех снарядов.
  3. Из различных способов уворота выбирается тот который дает меньше рикошетов.
  4. Исправлена ошибка когда танк стремясь сбить опасный снаряд попадал по своему напарнику.
После этих улучшений к моему удивлению бот стал еще заметно сильнее. Из непобедимых соперников остались только Mr. Smile и Hohol. Но ирония состоит в том, что отставание после первой части по очкам от лидеров была настолько большая, что догнать было просто не возможно. В итоге всего лишь 9-е место.

Результаты после 1ой части:
№ | Участник | Бои | Побед  | Рейтинг 
1  Mr.Smile 784 92% 1446
2  Hohol 784 89% 1379
3  Milanin 784 83% 1302
4  Megabyte 784 83% 1290
5  SDil 784 82% 1279
6  Romka 784 80% 1249
7  Commandos 784 79% 1234
8  valex 784 75% 1168
9  slazenger 784 73% 1148
10  eax 784 70% 1102
11  GreenTea 784 69% 1075                      

После второй части:
1  Mr.Smile 1617 91% 2939
2  Hohol 1617 88% 2811
3  Milanin 1617 84% 2706
4  SDil 1617 84% 2694
5  Megabyte 1617 82% 2649
6  Romka 1617 79% 2548
7  Commandos 1617 78% 2530
8  valex 1617 78% 2508
9  GreenTea 1617 77% 2470
10  eax 1617 73% 2356
11  slazenger 1617 72% 2315                      

Можно ради интереса подсчитать сколько бы у меня было примерно очков если бы в первой части бот был бы таким же сильным, как и во второй. В первой части бот за бой набирал в среднем 1.37 очка, во второй - 1.67 очка. За 1617 игр это 2707 очков ~ 3, 4 место.

Конец?

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

На десерт предлагаю посмотреть на визуализацию тактической карты (Java FX). Видео идет рывками, потому что в разные моменты времени просчет тактической карты тормозит по разному :) В игре бот анализирует не все точки на карте а только часть из тех, которые видимы ему.



Улучшения после финала

... Было всего одно. Выбор в качестве соперника ближайшего доступного бота находящегося в плохой позиции (которому трудно будет увернуться от выстрела). И только если не найден ни один такой враг то включается старая процедура выбора цели. Это улучшения на мой взгляд подняло силу игры бота в режиме 6х1 и 3х2, а также в 2х3 на соперниках атакующих в ближнем бою (хоть иногда начало получаться выигрывать у Mr.Smile ^_^).

Результаты песочницы



13 комментариев:

  1. Этот комментарий был удален автором.

    ОтветитьУдалить
  2. Хорошая стратегия, у меня тоже было много задумок, только после того как не прошел в финал (Раунд 2: 171 место - kuy), забил на стратегию, время не было, учёба..

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

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

    Не смотря на то, что я не пробился даже в топ-100 песочницы (153 место, AliEn), я сделал для себя важные выводы, касающиеся моего подхода к делу. Первое - дебагать все, второе - не лениться исследовать, третье - повышать уровень абстракции и искать решение на "поверхности", когда что-то идет не так, как задумывалось.

    От соревнования в восторге.

    ОтветитьУдалить
    Ответы
    1. По поводу багов, это мне еще прощлые Google AI contest-ы научили.. Сколько раз такое было, реализуешь что-нибудь. смотришь - плохо, все ужасно.. Потом через пару дней, блин! Да тут же явная бага! Куда же я смотрел!! И после фикса все отлично.. А бывает что и после фикса тоже плохо, и есть еще пару багов :) Главное не отчаиваться.
      Подход с крупными дискретными областями плох только тем, что будут проблемы на стыках областей.
      Я тоже получил огромное удовольствие от соревнования, побольше бы таких. Главное правильно поставить процесс, и все получится)

      Удалить
    2. Да, со стыками проблемы были: танк качался как маятник когда его брал на мушку один танк. А самая важное - танк, перебираясь в безопасный квадрат, частенько пересекал "горячие" области, попадая под обстрел. Для этого я решил при большом количестве врагов оставить только контурные квадраты, а центральные не использовать. Но когда танк оказывался в опасном положении, он перебирался через все поле к безопасному квадрату на другой стороне поля. Тут он запросто мог попасть под обстрел со всех сторон. Из-за этого пришлось ввести ограничение на дистанцию захватываемого квадрата. Это позволило по крайней мере не сливать бои 6x1 и рейтинг начал медленно ползти вверх..
      А вообще, стыд для меня, как физику, не проделать точный просчет уклонов и попаданий. Про вывод точных формул вообще мысли не было.

      Удалить
    3. Кстати, как вы сделали визуализацию тактической карты? Очень интересно.

      Удалить
    4. Приложение Java FX запускается в отдельном потоке, при каждом новом ходе бот дает Java FX приложению обьект World и текущий танк. А уже в гуи потоке запущен цикл который раз в милисекунду отрисовывает объект World и тактическую карту. Главное синхронизировать потоки чтобы World не поменялся посреди отрисовки. Все это можно посмотреть в исходниках (ссылка в начале статьи), чтобы работал отрисовщик надо расскомментировать несколько кусков кода в MyStrategy.java. Кстати Java FX использует аппаратное ускорение.. те тормоза на видео только из-за долгого вычисления тактической карты)

      Удалить
  4. Эх, а я упустил момент что кто-то хорошо разобрал физику и выложил точные формулы расчета, моя физика давала погрешность до 5%, особенно при поворотах:

    private Tank CalculateTankMovements(Tank tank, double leftTrackPower, double rightTrackPower, int turns, bool bounceFromBoundaries)
    {
    double deltaAngularSpeed, deltaSpeed;
    double angle = tank.Angle;
    double angularSpeed = tank.AngularSpeed;
    double x = tank.X;
    double y = tank.Y;
    double startX = x;
    double startY = y;
    double speedX = tank.SpeedX;
    double speedY = tank.SpeedY;
    double healthK = GetTankHealthK(tank);

    for (int q = 0; q < turns; q++)
    {
    angularSpeed *= tankAngleK;
    deltaAngularSpeed = ((leftTrackPower > 0 ? 1 : tank.EngineRearPowerFactor) * leftTrackPower - (rightTrackPower > 0 ? 1 : tank.EngineRearPowerFactor) * rightTrackPower) * tankMaxRotationAngle * healthK;
    angularSpeed += deltaAngularSpeed;
    angle += angularSpeed;

    speedX *= tankSpeedK; speedY *= tankSpeedK;
    deltaSpeed = ((leftTrackPower > 0 ? 1 : tank.EngineRearPowerFactor) * leftTrackPower + (rightTrackPower > 0 ? 1 : tank.EngineRearPowerFactor) * rightTrackPower) * tankMaxAcceleration * healthK;
    speedX += deltaSpeed * Math.Cos(angle - deltaAngularSpeed / 2);
    speedY += deltaSpeed * Math.Sin(angle - deltaAngularSpeed / 2);
    x += speedX;
    y += speedY;
    }

    // Уберем выход за пределы поля
    if (bounceFromBoundaries)
    {
    ...
    }

    return new Tank(tank.Id, tank.PlayerName, tank.TeammateIndex, x, y, speedX, speedY, angle, angularSpeed, tank.TurretRelativeAngle, tank.CrewHealth, tank.HullDurability, tank.ReloadingTime, Math.Max(tank.RemainingReloadingTime - turns, 0), tank.PremiumShellCount, tank.IsTeammate, tank.Type);
    }

    Ну и в стратегических фантазиях у меня явно были проблемы :) , в целом алгоритм у меня такой:

    Брал 13 направлений, типа:

    new double[]{-1, -1}, // backward
    new double[]{1, 1}, // forward
    new double[]{0, 0}, // stop

    new double[]{1, 0}, // left move
    new double[]{0, 1}, // right move

    и др.

    рассчитывал движение на 300 тиков вперед в каждом из этих 13 направлений, если при движении в определенном направлении в меня попадал снаряд и он не рикошетит, то добавлял к этому направлению сильный финальный штраф (HitPenalty). Также каждые 10 тиков в каждом из направлений вызывал функцию оценки позиции, которая проставляла данной точке штрафы и бонусы (PointScore) в зависимости от того за сколько ходов вражеские танки смогут прострелить эту точку и на сколько она для них "аппетитна" (может быть у врага под носом есть другой противник). Просчет точек в направлении останавливался как только вражеские танки имели возможность прострелить движение моего танка, но расчет возможности попадания снаряда продолжается до конца. В итоге выбирается направление движения с максимальной суммой: Max(PointScore) - HitPenalty.

    Если выясняется при этом что в любом из 13-и направлениях в меня не попадает снаряд (т.е. я не под обстрелом) и есть "полезный" бонус, к которому мой танк придет первым и бонус не под обстрелом - то я еду к бонусу.

    Атака (поворот дула и стрельба) у меня осуществлялась отдельно от движения, с упреждением и с попытками "совместной" стрельбы.

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

      Удалить
    2. Да, симуляция движения в 13-и направлениях (300 тиков максимум) + симуляция движения снарядов запускалась у меня каждый ход, но алгоритм был довольно быстр (комфортно было смотреть в локалраннере 3 своих танка с 3 смартгаями и 3 емптиплеерами).

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

      Расстояние до бонусов у меня тоже начально было заложено в PointScore :) но потом было вынесено отдельно, потому что в боях 2x3 танки ломились на бонусы и после взятия бонуса часто оказывались в "неудобной стратегической позиции" получали большую порцию снарядов, поэтому с бонусами было решено играть поосторожнее. Так это и осталось в песочнице, поэтому иногда проявлялась излишняя бонусная скромность :)

      Удалить
  5. Этот комментарий был удален автором.

    ОтветитьУдалить
  6. Хорошая статья. Опубликуйтесь на http://habrahabr.ru там много кто участвовал, а тут Вашу статью практически никто не видит.

    ОтветитьУдалить

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