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

воскресенье, 5 декабря 2010 г.

Google AI Challenge 2010 - Planet Wars

Вот и закончилось соревнование Google AI Challenge - Planet Wars организованное Клубом компьютерных наук университета Ватерлоо (University of Waterloo Computer Science Club) в котором мне посчастливилось принять участие. Продолжалось сие действо на протяжении 3 месяцев с 10 сентября по 1 декабря 2010 года. Более 4600 ботов с 112 различных стран практически непрерывно сражались на виртуальных боевых аренах официальных серверов (а также на множестве неофициальных) за звание сильнейшего бота. Я рад что мой ботик GreenTea занял почетное 8-е место в мире, и 1-е по Украине (!). В этом посте я бы хотел рассказать про то как мне, совсем обычному программисту удалось достичь такого, довольно неплохого результата. Т.е. расскажу о техническом подходе, об эволюции идей и немного о хронологии разворачивающихся событий. Но в начале пару слов о самой игре.


Механика

Суть игры сводится к следующему: необходимо написать сильнейший алгоритм игры в захват планет Planet Wars. Механика игры довольно проста:
- Карта состоит из планет расположенных на 2 мерной плоскости.
- Расстояние между планетами i и j целая величина, вычисляется по формуле
Lij = ceil( sqrt[(x2 - x1)^2 + (y2 - y1)^2] )
(ceil - отбрасывает дробную часть от чилса)
- Каждая планета обладает так называемым «приростом» g, он определяет, сколько кораблей производится на данной планете за 1 ход. Прирост может быть от 0 до 5. Чтобы корабли производились планету необходимо захватить.
- Оба игрока появляются каждый на своей планете со 100 кораблями и приростом в 5. Причем, карта является симметричной с точки зрения игроков, т.е. они находятся в равных начальных условиях.
- Остальные планеты являются нейтральными и охраняются нейтральным флотом.
- Каждый ход игрок, должен сделать выбор: на какую планету, и в каком количестве послать флот, или не посылать его вообще.
- Будучи выпущенным, флот, каждый ход преодолевает расстояние в 1. Т.е. он достигнет целевой планеты ровно через Lij ходов.
- Чтобы захватить планету, грубо говоря, нужно чтобы ее достиг флот в размере c+1, где c – это количество кораблей на планете в данный момент.
Вот примерно такая механика. Кое-где, намеренно упростил и умолчал про тонкости, дабы не перегружать текст.
Забыл также добавить, что игра пошаговая, причем шаги делаются «одновременно». Игрок 1 делает ход, затем игрок 2 делает ход не зная о ходе первого игрока. Игровой движок обрабатывает ходы и потом заново ходят игроки, и так далее.. Победа присуждается тому кто первый уничтожит все корабли соперника или обойдет по количеству кораблей через 200 ходов. Поражение досрочно засчитывается тому кто: упал с ошибкой, сделал ошибочный ход или превысил минимальный лимит времени на ход (кажется, была 1 секунда)
В начале хода каждый игрок знает расположение всех планет, приросты, и расположение всех летящих флотов. Это входные данные. А дальше.. Огромный выбор вариантов и простор для деятельности. Что делать: атаковать, защищаться, захватывать нейтральные планеты? Поначалу было не очень понятно, за что и хвататься. Если захватывать планеты, то в какой последовательности? Если атаковать, то, сколько кораблей посылать в атаку? А может и не атаковать вовсе... Какой должна быть оптимальная модель защиты? Какими вообще должны быть критерии выбора оптимального хода?..

Первый бот
Поскольку я имею некоторое представление о шахматных алгоритмах, первая идея была реализовать бота с использованием организованного перебора ходов. Идея надо сказать довольно безумная, если учесть какое огромное число всевозможных ходов есть в распоряжении у бота. В шахматах идет порядка до 30-40 ходов. Тут даже и представить страшно.. Поэтому реализовал скромный компромиссный вариант: в начале делается некий предварительный отбор разумного количества «не глупых» ходов, они прогоняются через некую оценочную функцию и выбирается наилучший. В множество входов входят захватывающие, защитные и атакующие ходы, а какой уже выбрать – остается на совести оценивающей функции. Такая простая и незатейливая архитектура первого бота. И еще отдельно рассчитывается первый ход – т.е. необходимо захватить как можно больше нейтральных планет и при этом не ослабить защиту начальной планеты.

Инструменты
На выбор организаторы предложили 4 языка: C++, C#, Java, Python, хотя текстовое api игрового движка (через stdin, stdout) позволяет использовать в принципе любые языки программирования. В стартовом пакете поставляется движок игры и простой визуализатор для просмотра повтора боя по его логу.
Я выбрал язык Java как наиболее знакомый.
Среда разработки: IntelliJ IDEA 9.
Система контроля версий: нет, т.к. планировалось большое количество мелких изменений в сравнительно небольшом коде, который весь умещается в голове. А если что, можно откатить изменения, используя локальную историю IntelliJ IDEA. [Сейчас я считаю, что это была скорее ошибка..]

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

Тестирование
Считал и считаю до сих пор, что 80% успеха в подобного рода соревнованиях - это хорошо поставленный и организованный процесс тестирования улучшений. Ждать пока бот отыграет вменяемое количество партий на официальном сервере – долго. О существовании неофициального tcp сервера поначалу даже не догадывался, ботов других игроков у меня не было (таким делятся с большой неохотой, и только с самыми близкими знакомыми) поэтому оставался один вариант - тестировать против своего же бота. Если улучшение показывает прирост числа побед на наборе карт, то значит улучшение хорошее – принимаем; если же показывается ухудшение результатов – отклоняем. Главное преимущество в скорости. За 2-15 минут в зависимости от быстродействия бота можно прогнать тест из 200 карт и сразу дать предварительное заключение – стало хорошо или плохо. Написал perl-овый скрипт (впоследствии, много его улучшал) который проводил такого рода тестирования и после каждой игры выдавал промежуточную статистику: кол-во сыгранных игр, из них побед новой версии, поражений, ничьих, и процент побед новой версии. Со временем докрутил одновременный запуск игр в 4 потоках, что на моем 4-х ядернике ускорило тесты примерно в 1.45 раза. Пример вывода скрипта для теста на 99 картах
. . .
-------------------------------------------
Game 98 [Map: "./maps/map98.txt" - 1 ]
Winner: 2
TurnsCount: 164
Player1 Statistics: 62 / 34 / 2 (64.28% scores)
################################################################....................................
################################################################....................................

Average turns to win/loose: 137/146
-------------------------------------------
Game 99 [Map: "./maps/map99.txt" - 1 ]
Winner: 2
TurnsCount: 179
Player1 Statistics: 62 / 35 / 2 (63.63% scores)
###############################################################.....................................
###############################################################.....................................

Average turns to win/loose: 137/147
-------------------------------------------
All win maps: 1, 2, 3, 4, 5, 6, 9, 10, 11, 12, 15, 17, 18, 20, 22, 24, 25, 26, 27, 28, 29, 31, 32, 34, 35, 36, 37, 38, 3
9, 40, 41, 42, 43, 45, 46, 48, 49, 50, 54, 55, 56, 57, 58, 59, 64, 66, 67, 71, 75, 76, 77, 78, 81, 84, 85, 88, 90, 91, 9
2, 94, 95, 96
All loose maps: 8, 13, 14, 16, 19, 21, 23, 33, 44, 47, 51, 52, 53, 60, 61, 62, 63, 65, 68, 69, 70, 72, 73, 74, 79, 80, 8
2, 83, 86, 87, 89, 93, 97, 98, 99
-------------------------------------------------
Time 7 : 24

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

Фантомные улучшения
Итак я видел 2 пути улучшения бота.
1) Улучшение предварительного выбора ходов.
2) Улучшение оценивающей функции.
Пытался идти двумя путями одновременно. И постепенно пришел к такому: в множество предварительных ходов попадали:
1) Пустой ход. Ничего не делать.
2) защитные ходы. Это такие флоты, после отправления которых, предотвращается захват нашей планеты.
3) Захват нейтральных планет (с 1 моей планеты, с нескольких моих планет)
4) Атакующие ходы – после которых противник вынужден защищаться, чтобы не потерять свои планеты.
Оценочная функция работала следующим образом.
1) Для каждой планеты высчитывалась проекция всех летящих на нее флотов. В итоге получался массив с количеством кораблей на N ходов вперед.
2) Для каждой планеты суммировалось «влияние» всех остальных планет на нее саму учитывая расстояние и владельца. Если расстояние равно d то массив «влияния» надо сместить на d позиций вправо. Если планета своя – то влияние со знаком «+» если вражеская – со знаком «-».
3) Влияние на все наши и вражеские планеты хитрым образом суммировалось, и получалась итоговая оценка.
Выбираются ходы дающие максимум на оценочной функции.
Сейчас страшно подумать, как такое могло работать. Но оно РАБОТАЛО! И до некоторых пор показывало даже неплохие результаты. Бот около недели в сентябре крутился в топ 20.
Первая проблема появилась неожиданно. Случайно, решил потестить не с прошлой, а с позапрошлой версией своего бота. И выяснился любопытный факт.
Процент побед прошлой с позапрошлой - 70%.
Текущей с прошлой- 65%.
Текущей с позапрошлой: 40% (!!!).
Это просто не укладывалось в голове. Как !?! Камень, ножницы, бумага.. Стал копаться – непонятно. Но урок был усвоен. Чтобы не попадать в локальные минимумы надо тестить не с 1-ой, а с несколькими прошлыми версиями. А лучше против всех версий. Тут надо выбрать разумный компромисс между надежностью и временем тестирования. Только тестами против многих версий своего бота, можно отличить действительно хорошие универсальные улучшения, от фантомных. Очевидно тест против разных ботов намного лучше, чем тест даже против многих версий своего бота, потому что отсеиваются улучшения, которые эксплуатируют какие-то баги/странности/особенности поведения своего бота, а значит, не в полной мере универсальны.

TCPserver
Полезная вещь. Надо было использовать с самого начала.

Хаос улучшений
По мере тестирования против нескольких старых версий стало все труднее держать в голове проценты побед против каждой из версий. Да и количество всевозможных улучшений/фиксов росло с каждым днем. В связи с этим начал использовать для контроля улучшений excel таблицы в Google Docs. Сделал 3 таблицы:
1) Версии: перечень всех версий, улучшений которые входят в каждую из них, и процент побед над предыдущей версией.
2) Улучшения. Состоит из колонок: id улучшения, краткое описание, прирост % побед.
3) Тестирования: первый игрок, второй игрок, процент побед 1 игрока, набор карт.
Недостатки такой системы:
1) Нет привязки id улучшения к конкретному коду – приходилось держать в голове. Если бы была система контроля версий, было бы проще.
2) Результаты тестирования необходимо забивать вручную. Т.е. запускать тесты по очереди и руками дополнять таблицу. Если учесть что тесты каждый примерно по 5 минут, и для надежности проходил их против нескольких ботов и на разных картах, то получается надо довольно подолгу втыкать в то в тестовый скрипт, то в excel таблицу попеременно.
Но это я уже сейчас хорошо осознаю недостатки.. Тогда и таблиц вполне хватало.

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

Второй бот
Выкинул код первого бота. Неделю отдыхал, смотрел, как играют топовые боты. А потом начал потихоньку переписывать все с нуля.
Первое что, более пристально обратил внимание на ботов, которые посылали флоты к передовым планетам (пионером в такой тактике был американец dmj111). В этом действительно есть смысл, т.к. передовые планеты вероятнее всего подвергнутся удару врага первыми, а значит должны быть хорошо защищены. Но наивная реализация такой поддержки, когда посылаются все флоты сзади – куда-то вперед – ничего не дает. Надо знать точно, сколько кораблей и куда посылать. И посылать только туда где они требуются. Моя идея заключалась в том, чтобы поделить защиту на 2 уровня. Так и назвал, защита уровня 1 и 2:
1) Защита от текущих атак противника. Поскольку в начале хода известны положения всех летящих флотов, то высчитать, сколько кораблей и на каком ходе понадобится для того, чтобы не дать захватить планету - тривиальная задача.
2) Защита от возможных атак противника. Тут сложнее и интереснее. Не известно, как будет атаковать противник. Для пущей безопасности логичнее всего рассчитать самый плохой вариант, атаку со всех вражеских планет. Но в случае такой атаки следует также учесть и возможную защиту – также со всех своих планет. И если в итоге оказывается, что при гипотетической атаке отбиться не получится – то следовательно планета уже сейчас нуждается в кораблях поддержки. В количестве необходимом для обеспечения защиты от виртуальной атаки.
Когда высчитаны потребности в кораблях для защиты 1 и 2 необходимо переслать флот с планет, которые в такой защите не нуждаются – т.е. имеют свободные корабли. Задача похожа на транспортную, только немного другая.
Формально описывается следующим образом:
имеется n планет со свободными кораблями. k планет под атакой.
Si - свободных кораблей в планете источнике
Dj - необходимо получить планете приемнику
max(Lj) - максимальное время, через которое необходимо получить корабли - иначе планету захватят
Lij - расстояние от i до j. Это целое число и оно определят время, через которое долетит флот.
Cij - кол-во кораблей, которые нужно послать с планеты i на планету j.
То-есть ищем матрицу
Gj - прирост планеты j.
получаются такие ограничения:
1) Cij = 0 , если Lij > max(Lj) - нет смысла посылать корабли, если они не успеют дойти.
2) sum_j Cij <= Si– нельзя послать больше кораблей, чем есть на планете.
3) sum_i Cij <= Dj - нет смысла посылать больше кораблей, чем необходимо для обеспечения защиты.
и нужно максимизировать функцию
F = sum_j Gj , где j такие, для которых выполняются условия: sum_i Cij = Dj .
Точного решения для данной задачи так сходу придумать не удалось. Но в принципе в игре будут доминировать частные случаи, когда атакуют одну планету, ну пусть несколько планет одновременно. А для таких случаев подойдет более простое и грубое решение, которое я и реализовал в коде. Пересказывать его подробно не буду. Вкратце: защищаемые планеты перебираются в порядке убывания значимости и каждой из них посылаются корабли с ближайших планет. С помощью данной функции я рассчитывал необходимые флоты для защиты уровня 1, 2 и для захвата нейтральных планет (небольшая хитрость – представляем, что нейтральные планеты мои и нуждаются в защите).

Нейтральные планеты
Нейтральные планеты надо захватывать уверенно, но не жадничать. Т.к. если посылать все силы в захват нейтралов, то не останется кораблей для защиты. Очевидно, что сразу необходимо захватывать планеты, которые дают больший прирост и с меньшим нейтральным флотом. И еще по возможности чтобы они были поближе. Если, например, сравнить захват 2 одинаковых планет с приростом 5 и защитой в 30 нейтральных кораблей, но одна из них находится на расстоянии 4, а другая на расстоянии 8 ходов, то пока флот будет лететь ко второй планете в первой может уже построится 20 кораблей (если бы мы захватывали ее в первую очередь). Рейтинг нейтральной планеты высчитывается по формуле:
R = growth / (shipsCount+distance(x,y)*growth)
Где distance(x,y) – расстояние до «центра тяжести» моих планет.

Последующие проблемы и их решение:
1) Есть шанс, что противник может перехватить захватываемую планету. Чтобы не допустить этого, я симулирую захват и рассчитываю, как могут развиваться события дальнейшим образом. Если у врага есть шанс перехватить и удержать планету, то такая планета исключается из списка захватываемых.
2) При захвате нейтральных планет кораблей хватает только для захвата планет с низким рейтингом. Если, к примеру, подождать 5 ходов, то можно накопить на более крутые планеты. Если бот не умеет ждать, то сразу расходует кучу кораблей на всякие не интересные планеты (с приростом 1, 2) и не успевает восстановиться, чтобы отбить атаки. Решение заключалось в том, чтобы сделать минимальный допустимый рейтинг планет, ниже которого планеты даже не рассматриваются как кандидаты на захват.
3) После решение проблемы 2 возникла такая ситуация, что противник успевал захватывать в самом начале на 1 планету больше – как раз ту, что я посчитал не интересной и не захватывал вообще. И в долгосрочной перспективе наличие этой планеты дает преимущество. Решение такое: по мере накопления кораблей на моих планетах порог минимального рейтинга постепенно снижается и со временем все малоинтересные нейтральные планеты тоже захватываются.
4) Частный случай, карты, в которых когда игроки как бы находятся на 2 раздельных планетарных островках/кластерах, между которыми приличное расстояние. Опасаться атак в таких случаях не стоит. Как правило, когда вражеский флот долетает до моего «островка» уже успевают подстроиться корабли для защиты. При таком расположении планет планка минимального рейтинга должна снижаться еще быстрее. Т.к. если этого не сделать - 100% поражение через 200 ходов по количеству кораблей.
При данной схеме захвата нейтральный планет, а также учитывая защиту уровня 2, отпала необходимость как-то отдельно высчитывать первый ход бота.

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

Последующие события
Новая архитектура бота на удивление оказалось гораздо лучше предыдущей, даже больше чем я ожидал. Уже 3я версия второго бота сравнялась по силе с первым, а 4я обошла его с большим отрывом.
Дальнейшие улучшения:
· Кластерная атака. Недостатком стандартной атаки является то, что для атаки выбирается 1 цель. Иногда, оказывается выгодно одновременно атаковать несколько планет. Например ситуация когда очень большой флот захватывает вражескую планету и вокруг много вражеских планет фактически без защиты. Важно распознать такую ситуацию и атаковать как можно большее число планет. Особенностью кластерной атаки является, то, что в атаку на каждую из планет посылается такое количество кораблей, чтобы у соперника не было хода предотвращающего захват планет, он может только отвоевать их будущем. Такой агрессивный стиль атаки находит применение в затяжных боях, когда боты идут в размен крупными пачками флотов.

· Защита уровня 3. Анализируя поражения, я выделил особый класс ситуаций, когда у соперника идет быстрое наращивание сил к передовой планете. В таких ситуациях моя оценка защиты 2 (защита от потенциальной атаки) до какого-то момента показывает, что моя фронтальная планета под защитой и все хорошо. Но, поскольку соперник продолжает подводить корабли, а я этого не делаю, в один момент возникает острая необходимость в защите 2, но подвести корабли я уже не успеваю… Поэтому я добавил оценку изменения уровня защиты 2. И если это изменение не в мою пользу, то посылаются дополнительные флоты поддержки. Другими словами, если, к примеру, в ходе №20 одна из моих планет после моделирования гипотетической атаки имеет 50 кораблей. А в ходе №21 после моделирования уже 20 кораблей, то, хотя на ходе 21 ей еще не угрожает опасность, но можно предположить, что на ходе №22 этот показатель уже будет -10 кораблей – то есть планета будет почти точно захвачена. Поэтому надо уже на ходе 21 послать 30 кораблей поддержки.
· Избыточная защита уровня 1. Если планету атакуют и ей угрожает опасность, то включается механизм защиты от атаки, это я уже описывал выше. Но сколько кораблей посылать в защиту? Очевидно, чтобы не дать захватить планету. Минимально это такое количество кораблей, чтобы по прибытии вражеских флотов на планете оставалось хотя бы 0 кораблей. Но вполне вероятно, что раз противник уже стал атаковать планету, значит, он попытается продолжить атаку. А следовательно, имеет смысл послать сразу чуть больше кораблей (у меня это в 1.5 раза больше минимально необходимого), чтобы компенсировать возможные будущие атаки. Может показаться, что это довольно спорное улучшение, однако оно добавляет свой процент побед в общую копилку.
· Промежуточные остановки в атаке. Первый момент, если расстояния между планетами достаточно большие, то посылая множество кораблей со всех планет на одну из вражеских планет, мы тем самым на время выключаем их из игры. Поскольку летящий флот никак не может помочь планетам, кроме той, куда он направляется. Второй момент, противник сразу видит все планы – куда направляются флоты, и может заранее подготовить защиту. Оба этих негативных эффекта можно сгладить если вместо того чтобы послать корабли сразу на вражескую планету, отправить их на свою планету, которая находится на пути следования к вражеской (может быть не прямо на пути, а с небольшими отклонениями). Таким образом, происходит постепенное приближение к цели. Появляются новые точки принятия решений - когда флот прибудет на промежуточную планету возможно ситуация игры изменится, и этими кораблями надо будет распорядиться иначе. И противнику чтобы обнаружить опасность будущей атаки надо будет выполнить дополнительные вычисления, что не все боты умеют делать.

· Фикс багов. Ну и конечно ничто так не улучшило моего бота как фикс багов в уже существующем коде :). Баги всегда разнообразны, коварны, и не стоит их недооценивать. Иногда можно забраковать какую-то отличную идею из-за того что реализация содержала неочевидные ошибки. Пару раз было, что фикс багов приводил к ухудшению игры :).

На финишной прямой
Время конкурса потихоньку утекало. Бот крутился в первой 30-ке на официальном сервере, и уверенно выступал на tcp сервере. Постепенно старые лидеры сменялись новыми. Первое место мертвой хваткой держал венгр bocsimacko. Его супер бот был вообще в принципе не досягаем: 88-95% побед на tcp сервере. Ну а мой бот, хотя и выступал довольно неплохо, содержал массу недостатков, которые я прекрасно видел, но был не в силах исправить. Фундаментальным недостатком являлось то, что все действия выполняются в рамках шести последовательных фаз:

1) Защита уровня 1.
2) Кластерная атака.
3) Защита уровня 2.
4) Защита уровня 3.
5) Захват нейтральных планет.
6) Атака.

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

Новый генератор карт
За 2 недели до конца соревнования организаторы переработали генератор карт, вызвав бурю возмущений со стороны игроков. Дело в том, что если первый генератор строил карты только с центральной симметрией, то во втором добавили осевую симметрию. Это было довольно весомым ударом по всем, в том числе и по моему боту.

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


На многих картах есть планеты, которые находятся по центру карты – т.е. на равном расстоянии от начальных планет. В картах с центральной симметрией их может быть от 1 до 5 (!). Это спорные планеты, и захватывать их опасно, потому что они тут же будут перехвачены противником. Допустим, в центре находится планета с приростом 5 и защитой 10. Захватывать ее опасно. Рядом находится другая планета с приростом 2 и защитой 20 – захватывать ее не опасно. Бот видит всю эту ситуацию и решает, как компромисс, захватить вторую планету – таким образом, давая противнику отличную возможность захватить центральную планету и отбить ее у меня уже не получится, т.к. я спалил 21 корабль на захват второй планеты. В данной ситуации боту следовало бы выжидать. Вот примерно на исключения таких ситуаций направлена стратегия осторожного захвата нейтральных планет. Расчет производится таким образом, что вначале я определяю самую интересную планету для атаки врага для случая, если я ничего не захватываю. Потом симулирую захват и перебором по всем планетам опять нахожу самую интересную планету для атаки врага. И если вдруг, грубо говоря, вторая атака является более «разрушительной» для меня, то данный захват планеты производить опасно. Причем в качестве целей для виртуальной вражеской атаки могут выступать и нейтральные планеты. Степень разрушительности я определяю как соотношение всех моих кораблей ко всем вражеским в конце симуляции виртуальной атаки (кстати говоря, длинна симуляции составляет 33 хода – магическое число, однако оно показало лучшие результаты на тестах).

Ночь последнего дня
28го ноября в 8:00 по киевскому времени официальное завершение выставления новых версий бота. Было это примерно в 3 ночи, я вяло просматривал поражения своего бота на tcp сервере. И мое внимание привлекла одна игра, где начальные планеты расположены близко. Мой бот начинает атаковать врага, еще раз атакует и теряет начальную планету. Это грубая ошибка, означающая, что где-то в коде бага в функции оценки защиты. Начал копать – действительно ошибка. Когда на вражескую планету летят мои атакующие флоты атаки, я не правильно рассчитывал возможность контратаки с такой планеты. Пофиксил, начал тестить и… О чудо! бот стал играть значительно сильнее. Причем на всех наборах карт, и против всех более старых версий. Примерно на 5% больше побед, чем было. Я прилежно все дотестил, в 5 часов утра залил новую версию на официальный сервер и лег спать.

Финал
На следующий день начался финальный турнир. Рейтинги всех игроков были сброшены, дабы не повлиять на результат. Поначалу я, конечно, был удивлен, что мой бот поднялся и уверенно держится на 4 позиции, подчас с легкостью разрывая признанных авторитетов из топ 10. Да что там, я был в шоке! До этого последнего фикса мое место было стабильно в районе 20 – 30. А тут такое… Потом к моему огорчению плавно спустился до 8 места. Ну ничего, все заслужено… Побеждает сильнейший!

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

воскресенье, 11 апреля 2010 г.

Как получить rownum в hql

Как получить rownum в hql

Предположим у вас есть серверное java приложение использующее hibernate с Oracle в качестве персистенс провайдера.

rownum это псевдоколонка в базе данных Oracle в которой храниться порядковый номер строки результата какого-либо select запроса. Бывает очень полезно получить например номер записи удовлетворяющей таким-то условиям, или взять из результирующего dataset-а строки в диапазоне от n до m. В общем, в ряде случаев rownum может очень пригодится.

Но вот беда, Hibernate Query Language (hql) не поддерживает rownum! Хуже того, нет эквивалента этой полезной фиче. Есть, конечно, возможность взять записи в диапазоне с помощью методов setFirstResult, setMaxResults в hibernate-овской Query, но это только половина фичи, а если хочется именно получить номер записи?

Вынужден вас огорчить - это невозмжно.
Но.. Как вы знаете, если очень хочется, и очень нужно, то нет ничего невозможного!
Ломать так ломать..

Умные дядьки на форумах советуют использовать native query которую можно сделать в том же EntityManager-е - нам это не подходит т.к. хотелось бы писать на hql-е а не на sql. В случае простых запросов можно, конечно, не поленится использовать sql, но в большом проекте, где hql запрос может создаваться динамически на основе десятков условий и опций, сгенерить подобный sql запрос может оказаться чересчур сложной задачей.

То что не можем сделать мы, отлично делает хибернет! Транслировать hql в sql - это его каждодневная задача. Итак, общая идея такова: берем наш суперсложный hql запрос, средствами хибернета перегоняем его в sql и результат встраиваем в виде подзапроса в довольно тривиальный sql запрос, который в конечном итоге и вытягивает rownum.

А теперь по пунктам:
  1. Преобразование hql в sql. Способ может не совсем легальный, но этот код работает - проверено. Несколько советов:

    • SessionFactory можно вытянуть из EntityManager-а: ((Session)entityManager.getDelegate()).getSessionFactory()
    • После преобразования вы можете с удивлением заметить, что все именованные параметры в запросе стали позиционными (т.е. в теле запроса появились вопросики .. ? .. ?.. вместо ваших .. :myParam1 .. :myParam2 ..). Возможно есть способ как-то допилять приведенный по ссылке код, запретить ему учинять это безобразие - я так и не разобрался. Вместо этого можно написать некий вспомогательный код который перед преобразованием "запомнит" расположение параметров и потом при формировании запроса выставит нужные значения параметров в правильных позициях.

  2. Собственно оберточный sql запрос вытягивающий rownum. Предположим что sql запрос полученный на предыдущем шаге хранится в стринге identifiersCriteriaNativeSql. Предположим также, что результатом предыдущего запроса является одна колонка - уникальные идентификаторы некой вашей сущности. Задача: получить rownum записи с заданным идентификатором.

    Результирующий sql запрос будет формироваться так:

    String firstColumnName = "col_0_0_"
    String subQuery = "select rownum as rn, " + firstColumnName + " from (" + identifiersCriteriaNativeSql + ")";
    String query = "select rn from (" + subQuery + ")" + " where " + firstColumnName + " = :identifierParameter";


    • Вы наверно обратили внимание на магическое "col_0_0_" - так хибернет обозвал первую колонку в select части identifiersCriteriaNativeSql, после преобразования из hql в sql - и это второе разочарование - все ваши алиасы были безвозвратно утеряны. Т.е. col_0_0_ указывает на id вашей сущности.
    • Второй непонятный момент может быть вызван двойной вложенностью запросов. Почему не просто

      String query = "select rownum from (" + identifiersCriteriaNativeSql + ")" + " where " + firstColumnName + " = :identifierParameter";

      А потому что в этом случае rownum будет всегда 1 - т.к. инициализация этой колонки происходит после наложение условий в where. Поэтому нужен еще один подзапрос subQuery без всяких условий.

Ура, работает!!!!......

суббота, 23 января 2010 г.

Осторожно: зомби атакуют!


Занимаясь своими повседневными делами люди забывают а реальной опасности, которая угрожает всем нам. Я говорю, конечно же, об атаке живых мертвецов, известных как зомби. Что делать если вдруг вирус, делающий из человека зомби, начнет распространятся среди людей? Как действовать отдельному человеку в такой ситуации? Какую стратегию, тактику применить людям чтобы выжить? Очевидно, все эти животрепещущие вопросы требует тщательного и серьезного исследования.. В заметке "Как убить зомби: Математика сопротивления" говорится о неком исследовании проведенном Робертом Смитом?. Выводы которые были получены в данной работе таковы: надо бить мертвяков решительно, и беспощадно. Совет конечно хорош, но звучит это так расплывчато и обобщенно.. А если зомби много, то может быть все-таки лучше бежать? А может надо использовать какую-то хитрость (ведь все же знают, что зомби тупые)? И если бить то чем? Например герой культового фильма "Живая мертвечина" очень оригинально догадался использовать против полчищ зомби газонокосилку.. Мне кажется, что проблема чисто математической модели атаки зомби в том, что в ней чрезвычайно трудно учесть разные тонкости и нюансы. Поэтому я решил построить модель программную. Реализована она была на языке java. Я попытался сделать эту модель как можно реалистичнее и ближе к тому, что может происходить на самом деле.

Ниже привожу краткую характеристику модели:
  • Модель пошаговая. Каждый шаг соответствует периоду в 20 минут.
  • Есть 3 состояния: человек, инфицированный и зомби.
  • У человека и зомби есть определенное количество жизней.
  • Будучи инфицированным, человек каждый свой ход теряет некоторое количество здоровья (болеет), потом когда умирает, то превращается в зомби.
  • Чтобы убить зомби надо отсечь ему голову, но люди об этом вначале не знают. Т.е. зомби якобы подыхает, но если у него целая голова, то он быстро регенерирует и встает.
  • Вообще у людей есть 4 уровня осведомленности: ничего не знает, знает что зомби напали, знает уязвимое место зомби, знает как окончательно убить зомби.
  • Впервые завидев зомби люди в панике бегут.
  • Всех кого встретит такой напуганный человек тоже узнают что зомби напали.
  • Люди могут объединятся в группы.
  • Кроме того люди будут стараться искать оружие; с некоторой вероятностью находят: нож или ружье (других видов пока нету).
  • Зомби, если встречают друг друга тоже объединяются в стаи (вместе жрать веселее).
  • Если встретятся две группы людей и зомби, то люди прикидывают свои шансы и взависимости от коэффициента смелости атакуют или спасаются бегством.
  • Во время битвы первыми идут в бой самые здоровые, сильные и более опытные люди.
  • Если человека ранят, то с некоторой вероятностью он становится инфицированным.
  • Если человека убьют, то зомби могут питаться его трупом, восстанавливая свое здоровье.
  • Если человек в группе собственноручно прибил (убил не до конца) определенное количество зомби, то ему открывается информация о том, что уязвимой точкой является голова.
  • Этим знанием человек делится с другими людьми в группе. Зная уязвимую точку люди начинают сражаться более эффективно.
  • Если человек прибивает еще большее количество зомбаков, то ему открывается знание о том как убить зомби.
  • Одной из стратегией людей является изоляция зараженных. Изоляция это например запереть в каком-нибудь подвале. Положительная сторона - инфицированные, когда переродятся в зомби, окажутся закрытыми от внешнего мира и не смогут навредить никому. Отрицательная сторона - инфицированные все еще может драться за людей какое-то время, а в изоляции он бездействует.
  • Также модель учитывает разделение людей по полу и возрасту. Пол и возраст влияют на 4 характеристики: жизненные силы, выносливость, скорость и смелость.
На входе модели: начальное количество людей, зараженных и зомби, на выходе - скрипт для MATLAB который рисует графики показывающие динамику развития событий. Вот пример для села из 100 человек, 10 из которых инфицированы.



Синим - люди, зеленым - зараженные, красным - зомби. Из рисунка видно что модель отработала почти 120 шагов (40 часов). Поначалу люди сопротивлялись плохо, но потом к 65 шагу перехватили инициативу. Возможно к тому времени кто-то догадался где находится уязвимая точка зомби - это стало переломным моментом.






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



На этот раз люди были истреблены и все до единого превратились в ходячих мертвецов..

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



людей: 100
инфицированных: 10
запусков: 1000

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

Дальше предлагаю просто посмотреть и сравнить графики для разных начальных условий.


людей: 100
инфицированных: 5
запусков: 1000










людей: 100
инфицированных: 15
запусков: 1000










людей: 100
инфицированных: 10
запусков: 1000

* Все люди - мужчины.



людей: 100
инфицированных: 10
запусков: 1000

* Все люди - женщины.









людей: 100
инфицированных: 10
запусков: 1000

* Все люди - дети до 14 лет.









людей: 100
инфицированных: 10
запусков: 1000

* Все люди - в возрасте от 15 до 35 лет.









людей: 100
инфицированных: 10
запусков: 1000

* Все люди - в возрасте от 36 до 65 лет.








людей: 100
инфицированных: 10
запусков: 1000

* Все люди - в возрасте от 66 лет и старше.





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

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

людей: 100
инфицированных: 10
эпох ГА: 20
количество хромосом: 20
коэффициент мутации: 0.03
запусков: 500

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


результат:
* Общий коэффициент смелости: 1.127
* Шанс объединится в группу: 0.61, коэффициент увеличения: 0.03
* Шанс изолировать инфицированного: 0.94.

Судя по графикам результат не многим лучше чем результат при значениях по умолчанию (которые впрочем, случайно получились, довольно близкими к оптимальным) 1.0, 0.3, 0.03, 0.5 соответственно.

А теперь выводы человеческим языком: люди! если вас больше, не бойтесь. - действуйте решительно. Не спешите сразу объединятся в группы и идти на охоту, бейте тревогу! Обзвоните всех знакомых и предупредите их. И наконец, если человек заражен - немедленно изолируйте его, например заприте где нибудь, или свяжите и привяжите к стулу. От раненного бойца который вот-вот сам станет зомби мало толку.

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






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