Казино Игра Мурави

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

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

Иллюстрация BFS для множественных источников (автор BenJackson):

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

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

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

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

Детали, позволявшие существенно улучшить игру, выглядели достаточно тривиально:

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

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

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

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

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

Финалы

День первый

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

День второй

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

День третий

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

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

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

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

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

Ошибки

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

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

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

Организация

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

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


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

На последок немножко Ant-Art-а в исполнении Мурашки.

Всех с наступающим и удачи на соревнованиях!