AI Challenge 2011 Ants. Глазами участника Murashka (15-е место)

Турнир привлекал своей простотой и собрал широкую аудиторию. Идея пришлась по вкусу и старшеклассникам и умудренным опытом гуру, помнящим еще чемпионат мира по компьютерным шахматам 1972-го года.

Используемые лидерами алгоритмы были примерно одинаковые, базовых было два — поиск в ширину (BFS), для определения ближайшего пути к дальним целям и минимакс в ближнем бою. Дьявол скрывался в правильной методике выбора целей и тонкой настройке деталей.

Иллюстрация BFS для множественных источников (автор BenJackson):
image
Для отыскания деталей, влияющих на результат, нужно было проделать много теоретической и экспериментальной работы.
Для быстрой реализации иметь простое, легко модифицируемое ядро алгоритма.
Для настройки быстрые и точные тесты, позволяющие определить полезность нововведения (процентов 70, казалось бы, полезных изменений влияли негативно).
Но на момент старта я всего этого не знал и, исходя из беглого анализа форума, начал бороться с таймлимитом. В итоге родился быстрый, но громоздкий и совсем не удобный для экспериментирования вариант поиска в ширину. Первая версия была готова за несколько дней, умела только собирать еду, но легко забиралась в Top 100 на официальном сервере.

Алгоритм столкновения с противником

Хотелось чего-то большого и чистого, но, в конце концов, реализовалось усеченным минимаксом и совсем неплохо работало.
Каждый ход предрассчитывались 5 карт в предположении, что противник будет двигаться всеми муравьями в одном направлении или стоять на месте. Дальше карта разбивалась на квадраты 5*5 клеток и мои муравьи, попадающие в зону атаки (5 штук максимум), двигались всеми возможными способами. Полученные результаты собирались минимаксом в оценку и выбиралась наиболее благоприятная комбинация ходов. Для более правильной обработки стыков сама сетка 5*5 тоже немного сдвигалась каждый ход.

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

Детали, позволявшие существенно улучшить игру, выглядели достаточно тривиально:
  • не стоять на своем хиле, если больше нечем заняться или под атакой
  • не давить друг друга
  • отступать к своему хилу
  • обходить атакованные клетки
  • приоритетно атаковать врагов, подошедших слишком близко к хилу
  • в процессе атаки двигаться к еде (иначе зависали напротив врага)
  • в игре один на один вести себя агрессивнее.


За 2 недели до дедлайна

Попробовал реализовать схему предложенную Memetix-ом (итоговое 10-е место)
По алгоритму предлагалось каждой клетке на карте дать ценность, согласно расстоянию от цели. Это чудесно уложилось бы мне в алгоритм атаки – я просто добавлял бы ценность к общей оценке и минимаксом получил бы лучшую комбинацию. Но сходу ничего хорошего не получилось – сбор еды был хуже чем у имеющейся версии и победить кучкование муравьев в местах пересечения «полей» даже после разнообразных танцев с отталкиванием не удалось. На допиливание метода времени не оставалось. Решено было оставить как есть и довести до ума имеющийся код.

День перед дедлайном

Подбираются последние коэффициенты. На TCP сервере круглосуточно висят 8(4+4) копий с двумя разными наборами констант. Впрочем определить кто лучше это не помогает – постоянные таймауты из-за большого количества игроков или при приближении к лимиту в 200 муравьев (команды на сервер идут долго). К тому же разброс в классе ботов не позволяет алгоритму оценки корректно определить рейтинг. Тестовый набор карт тоже показывает противоречивые результаты, поэтому в финал уходит слегка более агрессивная (из за техники смещения маски 5 на 5 при расчете атаки) версия. Также в последний момент прикручен бонус за движение в сторону еды в момент атаки. Тесты дружно клялись, что это полезно.
Официальный сервер в хаосе, большинство основных участников ресабмитятся с последними изменениями.

Финалы

День первый

4 игры без неожиданностей. Выбор соперников случаен.
Игры идут очень медленно.

День второй

Начиная с 5-й партии организаторами включен алгоритм оценки рейтинга TrueSkill – рейтинг состоит из двух коэффициентов: mu — собственно рейтинг и sigma — отражающий уверенность системы в рейтинге. Общий рейтинг равен mu-3*sigma. Соперники подбираются с близким рейтингом и с меньшим sigma. На практике это привело к тому, что из-за больших sigma топовые боты играют намного реже остальных.
Для Мурашки 5-я партия закончилась тем, что, пройдя под прикрытием тумана войны, на маленькой бедной карте бот, не входящий в первые две сотни, украл единственный хил. Итого -4 к mu и место в пятой сотне. Казино открыто с шиком.
Рейтинг некоторых игроков считается с ошибками. Ошибки в очередной раз исправляются, сервера рестартуют.
Игры идут еще медленнее.

День третий

Стартовые пакеты с удовольствием наиграли по 20 игр друг с другом, лидеры взирают на них с завистью и 6-ю играми в активе. Организаторы меняют алгоритм выбора соперников, чтобы выровнять количество игр, после чего включают отсечение до 5000-го места. А к вечеру до 3000-го и продлевают соревнование на полтора дня. Аллилуйя!

День четвертый

Отсечение в 2000 и 1000 мест.
Российская команда teapotahedron на расстоянии одной игры от xathis-а, все в предвкушении смены лидера… не судьба.
Мурашка мирно шебуршится в 20-ке.

День пятый – завершающий

Отсечение в 500 мест.
teapotahedron уходит вниз (финиш на 5-м месте).
Зато сценарий предыдущего дня повторяется с украинцем GreenTea. На этот раз успешно — смена лидера действительно произошла за 2 часа до остановки серверов. К тому же алгоритм выбора соперников дал очередной сбой, подобрав участника за пределами лимита отсечения в 500, и выделил всю серверную мощность на компенсацию не сыгранных им партий – весь топ пол часа внимательно сосет лапу.
Но чуда не произошло, xathis уверенно и заслужено вернул себе первое место, с чем его и поздравляю.
Мурашка, занимавшая за пару часов до финиша 14-е место, последней игрой в очной встрече опередила японца Komaki. И в то же время была пройдена российскими SDil_ -ом и meduz-ой. Опять же казино, но все могло быть и хуже — 15-е место для данного набора карт неплохой результат.

Ошибки

Быстрый, но громоздкий код усложнил модификацию и приземлил полет фантазии.
Много времени потеряно на попытку разрешения битвы не минимаксом.
Мало внимания уделено грамотному определению целей и распределению муравьев между ними. Муравьи имели тенденцию сбиваться в кучи напротив группы противников, вместо того, чтобы сходить туда, где врагов нет и захватить карту.
Хождение строем определенно дало бы преимущество, но как грамотно и быстро его реализовать в голову не пришло.
Первоначальное распределение было не эффективным. Чем ближе к хилу, тем чаще могла меняться дальняя цель в результате муравьи дергались, не зная куда им податься.

Заметки на будущее

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

Организация

Идея отличная, работа проделана огромная, организаторы заслуживают всяческих благодарностей. Без погрешностей тоже не обошлось, но мы живем в неидеальном мире.
Спорным решением было оставить в соревновании ботов из стартового пакета. Организаторов можно понять – хотелось задекларировать массовость. Но при более чем скромных вычислительных мощностях это доставляло неудобства реальным участникам. Впрочем, ошибка признана и на будущее обещали фильтровать.
Набор карт с сильно нестабильными результатами тоже не совсем понятен, ведь очевидно, что ошибок, которые нужно будет исправить TrueSkill-у и так достаточно.
Резкие всплески и падения в рейтингах, вероятно, тоже заслуга набора карт и особенностей алгоритма выбора, который не был достаточно случаен. Моя версия такова, что внутри общего набора финальных карт сформировались кластеры, которые резко выгодны одним ботам и не выгодны другим. Едва система рейтинга, оцениваемая TrueSkill, приходила в равновесное состояние, алгоритм выбора карт натыкался на очередную такую комбинацию и за 5-10 игр перемешивал таблицу. Сигма ближе к концу сжалась до минимума, уже ни на что не влияла и компенсировать всплески не могла.

Финальный рейтинг


Отчет победителя

На последок немножко Ant-Art-а в исполнении Мурашки.
image
Всех с наступающим и удачи на соревнованиях!

Similar posts

Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 19

    +4
    Поздравляю! Ты крут чувак!

    У меня 543 место ) неплохо, учитывая что спортивным программированием никогда не занимался, и в алгоритмах не силён.
    Для поиска пути реализовал A*, а вот для боевой составляющей ничего толком не смог придумать, просто примерный просчёт превосходства сил (своих и противника) вокруг каждого муравья. Теперь хоть услышал про minimax )) думаю ещё пригодится )
      0
      Тоже использовал A*, только совместил с чем-то вроде «транспортной сети» для уменьшения расчетов. Получилось забавно, особенно когда карта полностью ей покрывалась. Но опять же т.к. не было потом достаточно времени, до ума не довел.
      +1
      Поздравляю с отличным результатом.

      Я на 173, хотя участвовал еще в бете и после старта даже поднимался в первую десятку. Под конец нe было возможности инвестировать достаточно времени, чтобы успевать за прогрессом :)
        +3
        Спасибо за поздравления :)
        Реально крут был xathis, есть смысл покурить его код, потому что он был явно сильнее остальных. И код Memetix-а, потому что он простой и эффективный, при том что его профессия психотерапевт.
          0
          Парни, что это вообще за конкурс, где почитать какой-нить обзор хороший про него?
          +1
          А я на 24! Было мега круто. Очень рад, что принимал участие в соревнованиях.
            +2
            Было круто.
            Я дотянул до 65 места.
            Жду следующих соревнований.
            Появилось много свободного времени и какаято странная пустота.
              +1
              Ага, как будто что-то отняли и потерялся смысл жизни :)
              0
              Карты после дедлайна были такие же, как и до?
                0
                Я не заметил разницы.
                  0
                  Было три типа карт — лабиринт, ячеечный лабиринт и открытые карты с вкраплениями воды.
                  Из финала исключили ячеечный лабиринт со структурой 0-0-0-0 где контакт был только с ближайшими двумя соперниками… а я их так любил. Частично карты генерировались непосредственно перед финалами, частично были известными. Пропорция — каких типов карт будет сколько, тоже стала известна в день финала.
                  0
                  Так и не придумал как хорошо прикрутить минимакс. Поэтому битвы были только по количеству «наших» и «чужих». Но этого хватило для 6го места (lazarant).
                    0
                    Во, опиши свой алгоритм в отдельной статье. Я думаю многим будет интересно.
                      0
                      У тебя было грамотное распределение по карте, мне этого сильно нехватало.
                      0
                      а когда будет следующий этап?
                        0
                        Организаторы хотели бы делать пару раз в год. Муравьи сильно затянулись и получилось раз в год.
                        +2
                        brunneng.blogspot.com/ — Блог GreenTea — 2 место

                        Only users with full accounts can post comments. Log in, please.