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 ^_^).

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

Хорошо ли вы знаете физику (часть 2)

А вот и вторая порция вопросов по физике, для тех кто выжил после первой части. Ответы на них, а также много другой интересной и полезной информации вы можете найти почитав "Элементарный учебник по физике" под ред. Г. С. Ландсберга.

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

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

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

- Как работает пульверизатор?

- Какая форма тела наиболее аэродинамична при скоростях меньше скорости звука? Почему?

- Почему на быстроходных судах нос часто делают "бульбообразным" в месте где он погружается в воду?

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

- Почему закрученый футбольный мяч летит по изогнутой траэктории?

- Как меняется диаметр отверстия в чугунной кухонной печи, когда печь нагревается?

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

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

- Можно ли создать вечный двигатель? Почему?

- Можно ли разжечь костер в условиях невесомости при наличии воздуха? Допустим нам удалось скрепить все дрова чтобы они не разлетались.

- Где температура накаленного волоска электролампы выше: у поверхности волоска, или в середине его?

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

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

- Почему при накачивании воздуха в велосипедную шину насос заметно нагревается?

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

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

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

- Что происходит с мыльной пленкой когда она лопается? Куда она исчезает?

- Как может мыльный пузырь, состоящий из тончайшей пленки, довольно долго не лопаться? И почему же все таки он лопается?

- Чем обуславливается то, что некоторые материалы смачиваются водой, а другие нет? Например: кожа смачивается водой, а жир не смачивается, именно поэтому жирную тарелку мыть так трудно.

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

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

- Почему если опустить в ведро с водой тряпку одним концом и зафиксировать в таком положении, то через некоторое время мы увидим что тряпка стала мокрой выше того уровня до которого ее опустили?

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

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

- Почему чистая, но сырая вода отличается по вкусу, от такой же воды после того как ее прокипятить?

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

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

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

- Знаете ли вы что стекло это жидкость? Как же так, ведь оно твердое?

- В сахарном производстве для ускорения выделения крупинок сахара из сахарного сиропа к нему примешивают сахарную пудру. Почему это приводит к цели?

- При плавлении плотность большинства веществ уменьшается. Однако у воды происходит наоборот - увеличение плотности. Почему это так?

- Что придает резине свойство эластичности?

- Как во время мороза можно получить из соленой воды пресную?

- Иногда тротуары зимой посыпают солью, и от этого снег тает. Почему? Где ноги будут стыть больше: на заснеженном тротуаре или на таком же труаре, посыпанном солью?

- Почему пружинные динамометры после длительного употребления начинают давать неверные показания?

- Почему тетрадку легко согнуть в прямом положении, и очень тяжело если она свернута трубочкой?

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

- Известно что при заданной температуре давление пара некоторой жидкости не может быть больше определенного постоянного значения для данной температуры. Такой пар называют насыщеным. А почему все таки давление пара не может быть еще больше?

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

- Какова природа пузырьков в кипящей воде? Если это воздух то откуда он берется в таких колличествах?

- Почему закипающая вода "шумит"?

- Где вода закипит быстрее у подножья горы или на ее вершине? Какие факторы надо учесть чтобы правильно ответить на этот вопрос?

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

- Почему во время дождя становится заметно холоднее?

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

- Что собой представляет тума? Как и когда он образовывается?

- Можно ли водяной пар нагретый до очень большой температуры (скажем > 1000 градусов по цельсию) сжать настолько чтобы он перешел в жидкое состояние?

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

- Почему в горах, чем выше, тем воздух холоднее?

- Как образовываются облака? Какова механика образования капель дождя?

- Какая причина образования ветра?

Хорошо ли вы знаете физику (часть 1)

Интересная наука - физика. Широта и многообразие происходящих в мире явлений просто завораживает, как и то, насколько изящно можно объяснить эти явление с точки зрения науки. По прочтении первого тома Ландсберга "Элементарный учебник физики" захотелось выложить список интересных вопросов, знание ответов на которые расширят границы понимания нашего мира. Те кто считают что они разбираются в физике, или изучали ее раньше, или думают что они хорошо понимают физику чисто интуитивно, могут за одно проверить себя. Вопросы подбирал такие чтобы не надо было особо считать и знать формулы. Ответ достаточно сформулировать словами вкратце, хотя наверняка если копать глубоко, то по многим вопросом можно написать целый трактат :). Некоторые вопросы придумывал сам, а некоторые как есть взял прямо из книжки или переформулировал. Сразу предупреждаю, что на некоторые вопросы кажутся простыми, но если потянуть за ниточку, то раскрывается целый пласт знаний о каком либо классе явлений. Так что мой совет - будьте вдумчивы.. Итак, поехали!


- Если бы можно было создать на земле идеальную сеть интернета, то может ли пинг между 2 любыми точками на планете быть меньше 5 мс?

- Почему упасть на мерзлую землю больнее и опаснее чем на снег?

- Почему когда толкаешь тяжелый предмет типа ящика, то сложнее всего сдвинуть его с мертвой точки, а потом уже толкать становится легче?

- Чем отличается вес от массы?

- Предположим что человек неподвижно стоит на весах. Потом он резко приседает. Как будет изменяться показания весов во время приседания?

- Человек стоит на асфальте. Какие силы не дают ему провалиться и падать к центру земли?

- Какая сила является причиной движения автомобиля?

- деформируется ли деревянный стол под весом карандаша лежащего на нем?

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

- Почему хрупкие вещи при перевозке укладывают в стружки?

- Чем сопротивление среды (газа или жидкости) похоже на силу трения возникающую между твердыми телами, а чем не похоже?

- Как опытным путем найти центр тяжести небольшого продолговатого предмета (который можно взять в руки).

- Как опытным путем найти центр тяжести плоского предмета со сложной формой?

- Карандаш с воткнутым в него ножиком находится в состоянии устойчивого равновесия - объясните это явление.

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

- Опишите силы которые действуют со стороны ножа на разрезаемый предмет и как они соотносятся с силами которые
прикладываются к ножу.

- Что такое энергия в физике? Существуют ли в природе нечто материальное, что можно считать "чистой" энергией?

- Можно ли сказать что если нагретое тело лежит в состоянии покоя и охлаждается, то оно совершает работу?

- Почему амортизатор шасси самолета делают не слишком жестким?

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

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

- Почему спринтеры намного более атлетичные, чем бегуны на дальние дистанции, а метатели ядра еще более крупные?

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

- Почему крупногабаритные вращающиеся детали имеют предельную частоту вращения значительно меньшую чем детали с малым радиусом вращения?

- Пусть имеется железная ось к которой жестко приварен под прямым углом цельный железный стержень. Одинаково ли будет деформироваться (растягиваться) стержень на всей длине при быстром вращении оси?

- Почему когда трамвай поворачивает пассажиры не чувствуют действия инерции от центростремительного ускорения?

- Что является причиной возникновения силы инерции.

- Почему Земля немного сплюснута у полюсов?

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

- Как положение луны влияет на приливы и отливы, и почему они происходят?

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

- Почему погруженный в жидкость предмет всплывает если его масса меньше массы вытесненной жидкости? Зависит ли скорость всплытия от формы тела?

- Каким образом можно переместить судно из одного водоема в другой который расположен на другом уровне по высоте?

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

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

- Как объяснить что сила действующая на дно сосуда, в зависимости от формы сосуда, может быть больше или меньше веса жидкости, содержащейся в сосуде? Ведь сила, действующая со стороны сосуда на жидкость, должна уравновешивать вес жидкости.

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

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

- Какие условия должны выполняться чтобы корабль не переворачивало на бок во время плавания?

- Почему подводная лодка легшая на мягкий грунт иногда не может оторваться от него даже сбросив весь балласт воды?

- Будет ли всплывать деревянный брусок в воде в условиях невесомости? Почему?

- Выльется ли вода из бутылки запрокинутой верх ногами и погруженной горлышком в другую емкость с водой на несколько миллиметров?

- Нормальное давление воздуха 1 атмосфера равно давлению 10 метрового столба воды. Почему же человек не чувствует этого,  казалось бы, чудовищного давления?


(продолжение следует...)

Ms Pac-man vs Ghosts Competition WCCI 2012

Узнал о конкурсе от Memetix-а на форуме Google AI contest.
Решил принять участие по нескольких причинам:
- боты пишутся на java, а это моя родная стихия.
- Google AI Contest закончился.
- написать AI для старой известной игрушки - это ли не круто?
- в конкурсе уже учавствовал Memetix (на то время 1е место). По Google AI Contest я знал что он достойный соперник и хотелось побить его :P

Можно сказать это был мой первый опыт написания минимакса (не знаю насколько хорошо получилось).

Об игре.

Есть поле в виде симметричного лабиринта. На котором появляется пакмен и 4 призрака. Цель пакмана это сьесть все таблетки на поле и не попасться в лапы призракам. Цель призраков - догнать пакмена. Всего у пакмена 3 жизни. Когда пакмен сьедает все таблетки на поле начинается следуюущая карта. Всего 4 типа карт, и после завершения 4ой игра снова стартует с 1ой и тд. Кроме того на каждой карте есть 4 таблетки силы - после сьедания которых призраки становятся синими и в 2 раза более медленными. Пока они в таком состояии (200 ходов) пакмен может их догнать и сьесть.
Очки
1 обычная таблетка: 10 очков
1 таблетка силы: 50 очков
очки за сьеденых привидений от 1 таблеки: 200 (за 1е), 400 (2е), 800 (3е), 1600 (4е)
Таким образом выгодно после сьедения таблетки силы поймать и сьесть как можно больше призраков.

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

О конкурсе.

Это периодическое соревнование на тему PacMan vs Ghosts, которое происходит с интервалом раз в пол года. Каждую новую итерацию что то добавляют, усовершенствуют правила, движок, и тд.
Цели игры состоит в том чтобы написать алгоритм управления PacMan -ом или Привидениями, которые его ловят. Т.е. можно создавать ботов двух типов. На ход отводится 40 миллисекунд, и если бот не укладывается в это время то берется его прошлый ход. Если же в данный момент прошлый ход совершить не получится тогда движок делает случайный возможный ход за бота. Организаторы внесли не большие коррективы в правила для того чтобы не допустить некоторых жульнических стратегий. А именно если призраки сознательно блокируют некоторе участки карты что пакмен физически не может добраться до таблеток то игра может продолжаться бесконечно. Чтобы избежать этого по истечении 3000 ходов на 1 карте Пакмен получает половину очков со всех оставшихся таблеток на карте и начинается следующая карта.. Что-ж, справедливо.
Более подробно о правилах можно почитать на на сайте.

Развитие GreenTea.
Участие начал примерно за 50 дней до дедлана и сконцентрировался на алгоритме для призраков. Всего было 3 реализации.

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

Первый минимакс.
Случайно заметил в игре инетересную особенность, то что приведения не могут разворачиваться на 180 градусов. Только вперед, вправо или влево. Не знаю было ли это в оригинальных правилах игры, но для пакмена это можно сказать единственный шанс выжить. Он 1 а призраков 4 - но зато они менее маневренные. Что это дает? А то что ветвлений в ходах становится на много-много меньше. Раз меньше ветвлений - значит можно просчитать все позиции точно на большую глубину. Идея минимакса была очевидна и я начал изучать классы движка игры, а именно класс Game, хранящий состояние игры.  Как выяснилось этот класс был, можно сказать, старательно оптимизирован по используемой памяти, для того чтобы можно было хранить больше обьектов Game и легче их копировать. Что-ж, все было для начала работы, и я бодренько приступил к реализации своего первого минимакса. На первую версию ушло около 2 дней. Было в ней кучу багов, которые я постепенно выпиливал, но все таки работала уже лучше чем наивная реализация  через поиск в ширину. Основным преимуществом использования класса Game из игрового движка было то что он точно просчитывает следующий ход, ведет учет всех таблеток, очков и тд. Т.е. достаточно в каждой ноде дерева поиска хранить 1 экземпляр класса Game чтобы потом при генерации ходов получать из него новые экземпляры Game и помещать в чайлдовые узлы дерева. Статический анализ позиции на глубине 0 я делал все тем же поиском в ширину, который использовал в первой реализации.

Второй минимакс.
Сигналом, что я делаю что-то не так, было то, что на сервере мой алгоритм хотя и был в топ 10, все же не показывал отличных результатов как тот же Memetix. Анализ партий показал что глубина поиска у меня примерно под 30 ходов, а это не так уж и много если учесть что в ширину карта занимает 100 ходов. У Memetix-а глубина была побольше. По моим приблизительным прикидкам где то 40-60. Профилирование кода показало, что больше всего времени занимает как это ни странно копирование объекта Game выполнение
хода в том же Game. Так же я был немного шокирован тем насколько интенсивно работает сборщик мусора. Он практически захлебывался от потока объектов Game вышедших из употребления. Также много времени занимал статический анализ позиции поиском в ширину (со временем я его облегчил, но все равно было медленно). Напрашивалось более легковесное решение. Более легкие узлы дерева поиска, упрощенное выполнение хода для генерации следующих ходов. И я выкинул Game! Вместо него завел несколько классов: ComplexMove состоящий из хода пакмена и массива ходов призраков. Position позиция пакмена и массив позиций привидений, в последствиии были добавлены массив времени пока призраков можно съесть и массив времени пока призраки в логове. Учет сьеденных таблекок вообще не вел, т.к. посчитал что это будет слишком расточительно по памяти - а толку от него не много. Статический анализ позиции сделал намного проще: рассчитывались несколько параметров вроде: среднее растояние от пакмена до приведений, минимальное расстояние до привидения, среднее расстояние между привидениями (лучше больше - чтобы они не кучковались) и тд. И все эти простые оценки с некоторыми весами суммировались в общую оценку. Постепенно исправлялись баги и мой бот начал набирать обороты на сервере - закрепился где-то в районе
топ 3, а глубина поиска возросла где-то в среднем до 40.

Делаем пакмена.
Сделать реализацию пакмена из имеющейся для призраков оказалось делом нескольких часов. По суди достаточно было взять из лучшего хода - ход для пакмена. Сам алгоритм остался почти неизменным. Основными отличиями было то что для призраков взятие силовой таблетки оценивалось всегда в 0 очков (чтобы призраки были более агрессивны, даже если пакмен близок к ней), а для пакмена оно высчитывалось по расстояниям до призраков. Грубо говоря если расстояния большие - то брать не стоит. А если маленькие - тогда брать, т.к. можно будет догнать ослабленных призраков.

Странные баги пакмена.
Иногда пакмен совершал странные суицидальные ходы, когда за ним гнались по пятам. Хотя убежать можно было. Об этой проблеме я подробно изложил на форуме конкурса. Кратко говоря, это случалось из-за того что временами срабатывал сборщик мусора в самый ответственный момент. Время сборки может быть от 50 до 500 мс. А это 1-10 игровых ходов.. Не правильный ход очень критичен для пакмена - потому что он означает мгновенную смерть, и не так важен для привидений (не словили сейчас - словим потом). Ирония в том что сборка мусора оставленного ботом призраков может повлиять на вызов сборщика мусора, что приведет к неправильному ходу пакмена (поскольку боты в начале конкурса запускались в 1 виртуальной машине). Таким образом можно непреднамеренно жульничать за призраков. Потом эту проблему немного облегчили тем что добавили возможность выставлять результирующий ход для бота до завершения хода (40 мс), предохраняя от ситуации что из-за сборщика мусора этот ход не будет найден вообще. А возможность косвенного влияния ботов друг на друга из-за сборщика мусора кардинально решили разделением выполнения ботов по разным виртуальным машинам. Эта проблема заставила задуматься.. Готов ли я поиграть в русскую рулетку с пулей в виде сборщика мусора? Он может сработать а может не сработать -ситуация не из приятных..

Оптимизация работы с памятью.
Профилирование памяти показало что даже выкинув класс Game из узла дерева поиска, нагрузка на систему памяти и сборщик мусора была очень большая. Не удивительно, каждые 40 мс выкидывалось в трубу почти половина дерева. В котором может быть до 20000 узлов. И все это надо принять и обработать в сборщике мусора. Идея это исправить была следующая. Зачем пересоздавать узлы поиска, если их можно повторно использовать? Мне известно место где где я удаляю более не действительное поддерево дерева поиска - в начале каждого хода. Значит в этом месте можно просто пройтись рекурсивно по этому поддереву и положить каждый из его узлов в пул. А потом вместо того чтобы каждый раз создавать новый узел просто запросить свободный узел из пула. Я быстро реализовал эту идею и потом еще потратил уйму времени чтобы найти в коде "утечки" в других местах. Всякие создания временных списков/массивов. Все это ушло в статические переменные,  которые использовались повторно. Да, получившийся код не является образцом ООП, но зато он эффективен в плане использования памяти. Эта оптимизация очень существенно сказалась на игре бота - он стал более стабилен, в среднем стал создавать больше узлов и просчитывать больше позиций.

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

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

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

Эпилог
Посмотрим чем все это закончится. Пока я считаю что у моей команды призраков есть неплохие шансы взять 1е место. Но и соперники тоже очень сильные. Все будет зависеть от отдельных игр с топ ботами пакменов. В этом компоненте кажется мой бот не очень силен. Пакмен GreenTea сейчас в районе 10 го места - на него я не рассчитываю. Все таки основные силы были брошены на призраков.
Хотелось бы поблагодарить разработчиков движка за хорошую работу - класс Game написан замечательно, все основные операции кешируется.. в общем все продумано как следует. Молодцы ребята. На форуме отвечают оперативно и к советам игроков - прислушиваются. Получил удовольствие от участия, за что им большое спасибо :)

Google AI Challenge 2011 - Ants

English version of this post

Пока пишу этот пост финалы Google AI Conteset 2011 - Ants в самом разгаре. Организаторы постепенно отключают более слабых ботов чтобы более сильные имели возможность больше поиграть. Судя по таймеру расположенному на сайте http://ants.aichallenge.org до объявления победителя остается, 1 день 5 часов 35 минут и 5, 4, 3, 2.. секунд.

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

Так получилось что в этом году фаза бета версии затянулась непростительно долго.  Это сильно подорвало мою веру в энтузиазм и open source. Потом внезапно разработчики написали на сайте Sponsored by Google и очень резко засуетились, начали шевелится и что-то коммитить. Ну что ж, хорошо хоть так :) - я уж было подумал что так и заглохнет на стадии беты.. И все это время беты (уже не помню сколько, 4 месяца?)  я кодил, что-то потихоньку допиливал и улучшал.

За что люблю этот тип соревнования, то что времени - МНОГО! Можно не спеша, не торопясь сесть, все продумать, поробовать, протестировать, поменять.. еще 5 раз поменять, еще протестировать, и т.д. Вобщем, наслаждаться программированием в моем понимании :)

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

Механика игры.
Имеется замкнутая сама на себя прямоугольная карта определенного размера. Замкнутая в том смысле что уходишь влево - приходишь справа, уходишь вниз - приходишь сверху и т.п. Каждый игрок начинает с некоторым количеством начальных нор и 1 муравьем возле каждой норы. Каждая клетка поля может быть либо землей, либо непроходимой для муравья водой. Муравьи должны собирать еду - за каждый собранный кусочек из случайно норы появляется новый муравей. Он видит в неком радиусе, так что заранее не известно что за ним - нужно исследовать. Еда появляется случайным образом. Если муравьи разных игроков после хода оказались в радиусе атаки, то происходит бой между ними. Правила разрешения боя обьяснить   не так уж просто, достаточно сказать что в среднем, меньше убитых муравьев окажется у того игрока, чьих муравьев оказалось больше в бою. Чтобы захватить нору надо на нее стать. За убитую нору дают 2 очка. За потерю своей норы отнимают 1 очко. Так что если если выбор захватить вражескую нору или потерять свою следует предпочитать первое, только если своих нор >1. На каждом ходу бот должен выбрать куда походить каждым из муравьев. Да забыл сказать что карты симметричные, и еда появляется также симметрично для всех, чтобы было  по честному. Все! Вот такие не хитрые правила. В отличии от войны планет, где толком не понятно было что делать и как ходить, данную игру легче разбить на подзадачи и решать их по отдельности. Ну к примеру очевидно что надо бежать за едой, равномерно распространяться по карте и наваливаться на врагов большим количеством своих муравьев. Но в том то прикол, что легче и понятней стало всем, а поэтому из-за большей конкуренции сложность ни капельки не убавилась.

Мой инстументарий.

Java. Я - java разработчик. Этот язык достаточно прост и быстр. Позволяет с большой скоростью фигачить тонны кода (если надо реализовать какую-то свежую идею) не заботясь о каких-то системных вещах типа утечек памяти (привет C++ !!).
Поэтому для написания бота выбрал джаву.  Где-то в средине беты ради веселья попытался переключится на lisp sbcl. Не получилось.. Мой алгоритм поиска пути, идентично релизованный на лиспе работал в 5 раз медленнее чем на java. Возможно это от моего не достаточно хорошего знания лиспа...

IntelliJ idea Comunity edition. Замечательная среда разработки. Нареканий в процессе работы практически не было. Один раз слетел кеш, и весь код пестрел якобы "ошибками" компиляции. Пришлось почистить кеш руками и перезапустить.

git. Системы контроля версии мне очень не хватало в Planet Wars. Ошибки были учтены и я сразу начал коммитить в git. Он меня покорил своим богатством возможностей и скоростью работы (по сравнению с svn).

Скрипты на perl. В прошлом соревновании Planet Wars я наваял скрипты для автоматического тестирования своего бота со своим же ботом более старой версии. Грех было не воспользоваться ими! Правда пришлось немного переделать скрипт чтобы приспособить его к картам с несколькими игроками в так называемом режиме FFA (Free For All) - каждый сам за себя.
Например:

После 3 игры FFA бот:
- выиграл у 1.5 ботов и прогирал 4.5 ботам (+ 0.5 прибавляется к победам и поражениям за ничью)
- Набрал 0 очков, 2.16 - среднее кол-во очков у остальных ботов.
И суммарная информация:
- побед за все игры: 4.5 (45%),
- поражеий - 5.5
- очков в сумме набрано за все игры: 4 (52.2%),
- сумма средних очков по всем оппонентам: 3.66.
Подобная информация выводится после каждой игры. Таким образом можно протестировать стал ли бот действительно играть лучше в играх типа FFA или нет.

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

Sampling profiler hprof. Эта штуковина сыграла мне большую службу. Забегая на перед, примерно за 2 недели до конца, мой бот еще очень много падал по таймауту (превысил 500 мс отведенных на ход). Я не мог понять почему это происходит. С первого взгляда код чист и идеален, прогон входных данных взятых с игры на которых бот отвалился по таймауту показывает что бот успевает сделать ход ( к примеру за 300мс ). Так почему же он падает на сайте? Я уже начал думать всякую мистику, типа сборшик мусора запускается по среди игры в произвольное время, и выполнение приостанавливается. Возможно это отчасти и правда, но дело оказалось проще. Как то неожиданно наткнулся на hprof. Он вешается как агент к java-е (как то так -agentlib:hprof=cpu=samples,interval=10,depth=10), и в процессе работы (в моем случае это прогон данных поступавших на вход боту, к примеру на 200 ходах игры) собирает статистику где управление задерживается чаще всего. И с помощью этого нашел много достаточно не очевидных мест, работавших медленно. Какой то старинный код который можно было в 10 раз упростить! - та много чего.  В результате после моих фиксов бот стал работать примерно на 40% быстрее и все таймауты на официальном сайте пропали.

Рождение и эволюция.

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


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

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

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

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


Второе что я реализовал это калькулятор боя. Дело в том что во время беты правила разрешения боя были еще не стабильны, как и радиус атаки. Поэтому надо было написать что-то более менее универсальное, чтобы потом не переписывать лишний раз. Я не придумал ничего умнее чем перебор всех возможных ходов для своих и вражеских муравьев которые могут столкнуться в бою. И выбор из всех возможных комбинаций моих ходов такой, чтобы не нашлось вражеского хода способного одним махом погубить мою группу бойцов. Если таких "безопасных" ходов несколько, то из них выбирается такой, который, так скажем, создает наибольшее количество проблем для соперника. Тоесть, двумя словами, ищется самый агрессивный из самых безопасных ходов. Эти два понятия чаще всего взаимоисключающие, но безопасность всегда стоит на первом месте. Изначально калькулятор боя был настроен на группы муравьев (моих + вражеских) не больше 7. Это максимально 5^(7)=78125 возможных ходов. На практике, при наличии рядом стоящих муравьев, и воды комбинаций конечно меньше. Если будет 8 - то это гарантированный таймаут.

И поняли муравьи что вместе они сила. И начали истреблять врагов, рубить в капусту, без жалости и злости.


Насколько помню калькулятор боя в сочетании с поиском пути и равномерным распространением дал то, что муравей GreenTea сразу поднялся в топы на бета версии сайта. Редко какой соперник мог выдержать бешеного микро которое просто работало идеально, ведь перебирались все возможные ходы! Для групп муравьев >8 был написан примитивнейший алгоритм. Но он включался довольно редко, т.к. для отрытых картах редко скапливается действительно большое количество муравьев, хотя так было до поры до времени (об этом ниже).

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

Всего, судя по таблице в google docs-е  у моего бота с начала беты было 76 улучшений. Каждое из которых было протестировано на разных наборах карт и при разных распределениях еды и давало примерно от 3% до 15% прироста количества побед в боях 1 на 1 со старой версией без улучшения, и от 1% до 10% побед в боях FFA.
Попробую привести тут самые значимые улучшения начиная с беты, когда еще не было нор. Почему именно оттуда - потому что там было сделано много важных улучшений которые в последствии повлияли на отличную игру на открытых картах, даже при наличии нор.

u4. Улучшение поиска пути - найденный путь должен больше напоминать прямую линию.
Хех. Моя первая корявая реализация поиска пути находила кратчайший путь но он на глаз оказывался слегка кривоватым.

Красным показан старый кривой путь к еде. Зеленым - правильный путь. Хотя визуально это не видно но оба пути имеют одинаковую длину считая по клеткам.

u6. При поиске еды и противников использовать для расчета расстояния использовать 
честный минимально возможный путь. 

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

u9. Калькулятор боя
О нем см. выше.

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

u14 В калькуляторе боя пропускать повторяющиеся позиции. Этим можно значительно ускорить перебор и поднять макс кол-во муравьев до 8.
Реализовал это следующим образом. Для каждой позиции муравьев подсчитывалась ее хеш функция, на основании конечных позиций муравьев. И хранил Hashset уже обработанных позиций. После каждой новой генерации ходов смотрим если хеш позиции уникальный - обрабатываем, нет - пропускаем. Правда, мне так и не удалось придумать хорошую функцию для высчитывания хеша. То есть в редких (а может и не очень редких) случаях получалось что разные позиции давали одинаковый хеш и это полностью портило результат. В итоге пришлось вернуть полный перебор и максимальное кол-во муравьев в группе до 7.

u18 При распространении учитывать 4 вместо 3 своих муравьев.
То есть отталкивающие вектора проводятся от 4 муравьев. Это сделало рисунок распространения более гладким и довольно неплохо повысило процент побед.

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

u26 Предохранитель от таймаутов.
В некоторых местах кода делается проверка сколько времени осталось. Если больше чем 90% времени потрачено то выбрасывается исключение которое потом перехватывается и бот аккуратно завершает ход.

u25 Переделка алгоритма поиска пути.
Убрал рекурсию в алгоритме поиска пути и сделал нечто такое что мне интуитивно казалось эффективным. В последствии оказалось что это стало очень похоже на A*  :)

u27 Последний шаг к еде делать с расчетом чтобы оказаться ближе к другому видимому кусочку пищи и дальше от своих.
Довольно тонкое улучшение. Отдельно рассчитывать с какой стороны подойти к еде при ее захвате.

Ход вправо сделать лучше по двум причинам. 1) это приближает к другому кусочку еды, за которым не идут другие муравьи. 2) Это отдаляет от моего муравья. Тем самым расширяя границы обзора - а значит и захваченную территорию.

u29 Если враг захватывает еду первым то не двигаться к такой еде. Если спорная ситуация - значит засылать еще одного своего муравья в догонку.

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

u35 Избегание вражеских муравьев если на карте есть больше 2 опасных вражеских бота.
Если бот со всех сторон зажат врагами то вступать в бой и размениваться крайне не выгодно. Т.к. все силы бота будут распыляться между несколькими противниками. А боты которые не агресивничали будут расти и в конце концов просто перемассят. Атаковать нужно только если это 100%  безопасно.
И вот мы подошли к стадии поздней беты. Она запомнилась всем доминированием немецкого бота mathis. Этот бот был хорош в больших замесах. Он выстраивал можно сказать идеальную цепочку из муравьев, и не допускал случайных потерь (типа там один муравей выскочил вперед и погиб). И потом эта линия просто раздавливала всех. А моя боевая система перебора оказалась бессильна потому что не в состоянии обработать большое кол-во муравьев. Упрощенная система атаки никуда не годилась. Муравьи на линии таких фронтов действовали в целом как неорганизованное стадо, ходили в разнобой и допускали много ошибок. Еще его отличала агрессивность с которой он отжимал муравьев внутри своей территории. Мой же в то время, как и многие другие боты был практически не агрессивным в этом плане. Получается что mathis делал полностью безопасную зону и постепенно расширял ее подминая других как катком. На тот момент я не мог придумать как законтрить такую брутальную тактику. С моей стороны еще было много небольших улучшений о которых упоминать не стоит.

Примерно с таким багажом подбираемся к концу беты и официальному старту Google AI Challenge - Ants 2011.

С официальным стартом появились норы и новый тип карт - лабиринты. И сразу повылазило  множество проблем:
- Стратегия распространения с помощью векторов не работала на лабиринтах. Чаще всего муравьи забивались где-то в районе норы.
- Начались жестокие тормоза как только кол-во муравьев превышало штук 50. Это от того что почти все запуски поиска пути, которых было много, не заканчивались быстро, а плутали по запутанным ходам.

Последующие улучшения:
Улучшения версии 2.1
Новый способ распространения по лабиринту. Это был ужас, но работало лучше чем расхождение по векторам и не тормозило.. Суть улучшения в следующем. Заводится карта видимости. Каждая клетка которой соответствует точке на карте. Каждый новый ход моего муравья поиском в ширину искалась так называемая область видимости. И в этой области видимости я повышал счетчик каждой клетки на 1. Причем карта видимости не сбрасывается между ходами. Таким образом в тех зонах где муравьев было много образовывается зона с большими значениями счетчиков видимости. И при выборе хода муравей идет в ту точку где значение счетчика видимости меньше. Таким образом муравьи не тупят в одном месте а стараются переползать все дальше от норы.
Главное было переключится на такой режим в картах типа лабиринта. Сделал я это следующим образом - собираю статистику всех прогонов поиска кратчайшего пути. И если среди найденных кратчайших путей грубо говоря попадается много в обход каких-то препятствий и мало путей напрямик - значит это скорее всего лабиринт.

Защита нор.
 Моя защита нор довольно не замысловатая: как только вражеский муравей оказывается на расстоянии N шагов до норы, все ближайшие мои муравьи на него набрасываются. N было долгое время 25, под конец 15, возможно стоило еще уменьшить.
Однако, защищая свои норы важно понять что делать это стоит особенно активно только если
1) осталась 1 нора.
2) на карте много своих муравьев.
На карте с несколькими норами не надо сразу кидаться их все защищать. Т.к. бот потеряет на этом много времени, а другие просто найдут больше еды и задавят числом.
Т.е. защита нор включается при условии если осталась 1 нора или моих мураьвев  > K*колввоНор (где К - магическая константа равная 10).

u54 Новый тип атаки attackMedium
Это была первая попытка сделать что то лучше чем простая атака. Чтобы воевать с тем же mathis-ом.

u56 Улучшение взятия целей. Теперь проверяется кратчайший путь до всех свободных муравьев в области доступных клеток.
Можно назвать это зачатком поиска в ширину  (BFS). От каждого кусочка еды в неком радиусе выполняется поиск в ширину.  К еде будем идти только в том случае если в результате этого поиска были найдены мои муравьи.

u70 1) Много улучшений производительности. 2) Во время взятия еды муравей теперь может пойти к более дальнему скоплению еды чем к близайшему 1 кусочку, если это движение будет отдалять его от скопления.

Немного лучше в такой ситуации пойти за дальней группой еды.

На финишной прямой.
Неделя до начала финалов. На официальном сервере и на tcp сервере доминирует немецкий бот xathis. Его 1я версия появилась где то спустя неделю после официального старта и сразу захватила лидерство. Потом уже почти под конец появилась  2я версия - и порвала всех еще раз с большим отрывом. А где же mathis пропал?
Я взял отпуск на эту неделю чтобы сделать последнее усилие.

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

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

Последние выходные перед финалом.
Это были самые жаркие дни за последние несколько месяцев. Я пытался сообразить лучшую систему боя для больших скоплений муравьев. Продвигался вперед с помощью юнит тестов. Находил в повторах ситуацию с ошибкой, делал соответствующий юнит тест и пытался как то фиксить. Код получился ужасным, но удалось пофиксить тестов 15, и не завалить предыдущие :). Это улучшение дало 60%-70% побед против старой версии в режиме 1х1. И до 10% в режиме FFA. Если учесть что старая версия поднялась до 2 места на официальном сервере, у меня были большие ожидания перед началом финалов!

Что не успел.
И все таки конечная боевая система оказалась далеко не так хороша как у xathis-а. Чтобы понять это достаточно посмотреть несколько игр с ним.
Также мне не нравится как я исследую уже освоенные земли в поисках еды в режиме распространения по лабиринту с помощью карты приоритетов. Мне кажется лучше было бы иметь равномерную сетку покрытия разведчиками как у xathis-а или tetrapohedron-а. И чтобы разведчики динамически могли становится в бой если это надо.

Пора заканчивать. Статья и так получилась не маленькая :)
Хочу сказать спасибо Роме Ищенко :), моему коллеге по работе, с которым мы вместе устраивали мозговые штурмы в обед, обдумывая новые возможности улучшений.

Код бота и jar-ник..

UPD.  А вот так все кончилось.

История: БЫЛО ЭТО В НЕ БОЛЬШОМ ГОРОДКЕ....

Не так давно я до слез смеялся с эпичного рассказа Жестокая голактика  якобы 14-ти летнего мальчика написавшего, его на конкурс.. Каким нужно быть больным человеком чтобы родить такое?!? А оказывается я сам ничуть не лучше. Ниже фотографии рукописи 18 летней давности (мне тогда было 7 лет..)

И тут творческая мысль юного писателя похоже иссякла.. :P