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. До встречи в бою :)

6 comments:

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

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

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

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

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

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

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

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

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

    ReplyDelete
  5. VarangaOfficial - варанга официальный сайт - проверенные и достоверные факты. Воспользовавшись данным ресурсом, вы сможете узнать исчерпывающую информацию касающуюся представленного средства. Увидеть данные о проведенных клинических исследований, прочесть реальные отзывы пациентов и медицинского персонала. Ознакомиться с инструкцией по использованию, прочесть об особенностях и методах работы мази, осмыслить, в чем заключаются особенности работы крема Варанга, где можно купить оригинальный сертифицированный препарат и, как избежать покупки подделки. Мы скурпулезно проверяем размещаемые данные. Предоставляем нашим пользователям сведения, которые берутся только из надежных источников. Если вы обнаружили признаки грибкового поражения стоп или же долго и безрезультатно стараетесь излечиться от этого коварного, неприятного недуга, на нашем сайте вы отыщете быстрый и легкий способ устранения проблемы. Приобщайтесь и живите здоровой полноценной жизнью. Теперь все ответы можно отыскать на одном сайте.

    ReplyDelete