Вот и закончилось соревнование 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 - отбрасывает дробную часть от чилса)
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-ой, а с несколькими прошлыми версиями. А лучше против всех версий. Тут надо выбрать разумный компромисс между надежностью и временем тестирования. Только тестами против многих версий своего бота, можно отличить действительно хорошие универсальные улучшения, от фантомных. Очевидно тест против разных ботов намного лучше, чем тест даже против многих версий своего бота, потому что отсеиваются улучшения, которые эксплуатируют какие-то баги/странности/особенности поведения своего бота, а значит, не в полной мере универсальны.
TCP – server
Полезная вещь. Надо было использовать с самого начала.
Хаос улучшений
По мере тестирования против нескольких старых версий стало все труднее держать в голове проценты побед против каждой из версий. Да и количество всевозможных улучшений/фиксов росло с каждым днем. В связи с этим начал использовать для контроля улучшений 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)
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 хода – магическое число, однако оно показало лучшие результаты на тестах).
На многих картах есть планеты, которые находятся по центру карты – т.е. на равном расстоянии от начальных планет. В картах с центральной симметрией их может быть от 1 до 5 (!). Это спорные планеты, и захватывать их опасно, потому что они тут же будут перехвачены противником. Допустим, в центре находится планета с приростом 5 и защитой 10. Захватывать ее опасно. Рядом находится другая планета с приростом 2 и защитой 20 – захватывать ее не опасно. Бот видит всю эту ситуацию и решает, как компромисс, захватить вторую планету – таким образом, давая противнику отличную возможность захватить центральную планету и отбить ее у меня уже не получится, т.к. я спалил 21 корабль на захват второй планеты. В данной ситуации боту следовало бы выжидать. Вот примерно на исключения таких ситуаций направлена стратегия осторожного захвата нейтральных планет. Расчет производится таким образом, что вначале я определяю самую интересную планету для атаки врага для случая, если я ничего не захватываю. Потом симулирую захват и перебором по всем планетам опять нахожу самую интересную планету для атаки врага. И если вдруг, грубо говоря, вторая атака является более «разрушительной» для меня, то данный захват планеты производить опасно. Причем в качестве целей для виртуальной вражеской атаки могут выступать и нейтральные планеты. Степень разрушительности я определяю как соотношение всех моих кораблей ко всем вражеским в конце симуляции виртуальной атаки (кстати говоря, длинна симуляции составляет 33 хода – магическое число, однако оно показало лучшие результаты на тестах).
Ночь последнего дня
28го ноября в 8:00 по киевскому времени официальное завершение выставления новых версий бота. Было это примерно в 3 ночи, я вяло просматривал поражения своего бота на tcp сервере. И мое внимание привлекла одна игра, где начальные планеты расположены близко. Мой бот начинает атаковать врага, еще раз атакует и теряет начальную планету. Это грубая ошибка, означающая, что где-то в коде бага в функции оценки защиты. Начал копать – действительно ошибка. Когда на вражескую планету летят мои атакующие флоты атаки, я не правильно рассчитывал возможность контратаки с такой планеты. Пофиксил, начал тестить и… О чудо! бот стал играть значительно сильнее. Причем на всех наборах карт, и против всех более старых версий. Примерно на 5% больше побед, чем было. Я прилежно все дотестил, в 5 часов утра залил новую версию на официальный сервер и лег спать.
Финал
На следующий день начался финальный турнир. Рейтинги всех игроков были сброшены, дабы не повлиять на результат. Поначалу я, конечно, был удивлен, что мой бот поднялся и уверенно держится на 4 позиции, подчас с легкостью разрывая признанных авторитетов из топ 10. Да что там, я был в шоке! До этого последнего фикса мое место было стабильно в районе 20 – 30. А тут такое… Потом к моему огорчению плавно спустился до 8 места. Ну ничего, все заслужено… Побеждает сильнейший!
Эпилог
Надеюсь, мой опыт окажется полезным для тех, кто сможет прочитать этот пост. В частности я имею в виду то, как бы поставлен процесс разработки. Может быть, читая этот отчет вы увидели, что я делал какие-то глупости, не замечал каких то очевидных вещей, если это так, мне будет интересно услышать критику. Кстати, следующее соревнование планируется в 2011 году ;).
Исходный код и jar файл бота.
Исходный код и jar файл бота.
