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

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



среда, 12 сентября 2012 г.

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

среда, 5 сентября 2012 г.

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

суббота, 26 мая 2012 г.

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 написан замечательно, все основные операции кешируется.. в общем все продумано как следует. Молодцы ребята. На форуме отвечают оперативно и к советам игроков - прислушиваются. Получил удовольствие от участия, за что им большое спасибо :)




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