Недавно из блога Плахова узнал про конкурс Google AI Challenge. Конкурс очень интересный, и битвы топ-ботов очень впечатляют (для примера: один, два и три). В результате меня так зацепила простота идеи и в то же время сложность алгоритмов, что я тоже решил попробовать свои силы.
Google AI Challenge – это конкурс, в котором соревнуются не люди, а запрограммированные боты. Правила очень просты и основаны на игре Galcon. Есть двухмерная карта с планетами, каждая из которых характеризуется двумя параметрами: количеством войск и их приростом за ход. Планеты могут быть нейтральными, а могут принадлежать одному из двух соперников. Количество войск на нейтральных планетах не увеличивается. За ход одна или несколько планет могут отправить несколько флотов с определенным количеством войск в направлении других планет. На карте учитываются расстояния между планетами, поэтому на то, чтобы долететь, каждому флоту требуется несколько ходов. При прибытии флота на нейтральную или вражескую планету происходит схватка, в которой побеждает тот, у кого больше войск. Таким образом, чтобы захватить планету, нужно отправить на нее флот или несколько флотов с количеством войск на 1 больше, чем у противника. В то же время не нужно забывать, что за время прибытия вашего флота на планету количество войск на ней может увеличиться как за счет прироста населения, так и за счет быстро переброшенных войск противника. Это если вкратце, на самом деле количество вариантов бесконечно велико и это-то и составляет прелесть конкурса.
Писать ботов можно почти на любом языке программирования, включая даже JavaScript и PHP. Стартовые наборы (стартовый бот + соперники) есть для Java, Python, C++ и C#. Для остальных языков придется писать стартового бота самому.
Немного о своем текущем опыте. На данный момент я засабмитил вторую версию бота. Первую – в четверг, вторую – сегодня (воскресенье).
Первую версию я писал три вечера и основной целью было добиться, чтобы он научился побеждать 5 тестовых ботов на 100 картах (доступны в стартовом наборе) в большинстве случаев. Если описывать алгоритм в общем, то бот умел делать оптимальные первые хода, захватывая нейтральные планеты, защищать свои планеты (только самозащита на данном этапе) и очень неоптимально атаковать противника. Такого простого алгоритма оказалось достаточно, чтобы побеждать тестовых ботов в 99-100 случаях из ста. И этого оказалось достаточно, чтобы будучи засабмиченным в контест мой бот попал в топ-800, болтаясь там между 600 и 800 местами. К слову, на данный момент соперников чуть меньше 4000.
Во второй версии я научил бота коллективной защите и пофиксил пару багов. Это то, чего ему очень не хватало в битвах с соперниками. Конечно, это не даст ему возможность попасть в топ-100, но, надеюсь, он поднимется на 100-200 мест вверх.
В планах написание более серьезной версии, в которой бот научится оценивать перспективы захвата различных планет и будет принимать более оптимальные решения в плане отправки войск. А также – реализация атаки через свои и нейтральные планеты, учет фронтовых планет и пара алгоритмов контратак. Если же у меня хватит свободного времени завернуть это все в анализ дерева возможных ходов для просмотра будущего на несколько десятков ходов вперед – с этим можно будет претендовать и на топ-100.
В соревновании очень своеобразное ранжирование. Моего первого бота судьба сходу свела с ботом из 4-й сотни и после победы он сразу попал в топ-300. Затем, правда, был долгий путь вниз, пока он не сбалансировался в районе 700-го места. Второй же бот попал на товарища с 3100-какого-то места и после победы поднялся всего лишь на 3000-ю позицию. Не возникает сомнений, что за пару дней схваток он поднимется выше как минимум до того же 700-го места, но все-таки процесс выбора первого боя немного странноват. Random, что ли?
Если я вас заинтересовал, то сообщаю главную информацию. Соревнование будет длится еще почти целый месяц (!), до 27 ноября, так что у вас есть все шансы попробовать.
Несколько полезных ссылок:
- Сайт контеста: http://ai-contest.com/
- Секция форума, посвященная стратегии: http://ai-contest.com/forum/viewforum.php?f=17
- Отличная программа для тестирования своего бота: http://ai-contest.com/forum/viewtopic.php?f=18&t=748
Ну, и прочитайте алгоритм, который предлагает Плахов и обсуждение различных стратегий на форумах. Я там не знаю названий половины алгоритмов. Shame on me, в общем.
Кстати, если вы решите использовать C#, то учтите, что на сервере Mono 1.2.6, а это значит, что вы можете использовать только C# 2.0. Организаторов уже давно просили поставить на сервер Mono 2.0 (поддержка C# 3.5), однако те злобно морозятся. Не хотят плодить конкурентов, наверно ;) Подробнее здесь.
Ну, и напоследок. Если есть вопросы – спрашивайте. Если решите поучаствовать, мой аккаунт – AlexMerle. До встречи в бою :)
