Sunday, October 31, 2010

Google AI Challenge

Недавно из блога Плахова узнал про конкурс 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 ноября, так что у вас есть все шансы попробовать.

Несколько полезных ссылок:

Ну, и прочитайте алгоритм, который предлагает Плахов и обсуждение различных стратегий на форумах. Я там не знаю названий половины алгоритмов. Shame on me, в общем.

Кстати, если вы решите использовать C#, то учтите, что на сервере Mono 1.2.6, а это значит, что вы можете использовать только C# 2.0. Организаторов уже давно просили поставить на сервер Mono 2.0 (поддержка C# 3.5), однако те злобно морозятся. Не хотят плодить конкурентов, наверно ;) Подробнее здесь.

Ну, и напоследок. Если есть вопросы – спрашивайте. Если решите поучаствовать, мой аккаунт – AlexMerle. До встречи в бою :)

5 comments:

  1. Запости сорцы на GitHub =) Я бы тоже хотел, но как раз сейчас совсем нет времени =(

    ReplyDelete
  2. ОК, чуть позже запощу. Хотя там пока нет ничего особо интересного.

    Если тебе интересен базовый алгоритм, могу расписать подробнее.

    ReplyDelete
  3. Где-то так:

    На первых ходах захватываем самые "жирные" в плане прироста населения планеты.

    Далее на каждом ходу:
    1. Подсчитывается угроза для каждой планеты от войск противника, учитывая не только уже летящие флота, но и потенциально опасные, сидящие на ближащих планетах.
    2. Подсчитывается количество "доступных" войск на каждой планете с учетом защиты своей планеты (самозащита).
    3. Если планете недостаточно своих ресурсов для защиты, на нее высылается необходимое количество войск с ближащих планет (коллективная защита)
    4. Оставшиеся войска идут в атаку на ближащую планету.

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

    Вот вкратце и все.

    ReplyDelete
  4. думаю, в публикации сорсов нет необходимости - в стартерките уже есть рабочий бот с реализацией базовой стратегии

    ReplyDelete