Всем привет!

Два самых заметных программистских сообщества в УрФУ — это спортивное программирование в УрФУ и CTF. Про СП мы писали много, а развитием CTF у нас занимается команда УрФУ по CTF Хакердом, она же является организатором первых всероссийских соревнований ruCTF.

Сегодня я расскажу про относительно новое для нас сообщество разработчиков игровых стратегий, члены которого пишут ботов для соревнований. Боты должны побеждать в играх, выполняя задачи или обыгрывая ботов других участников. Участвовать в играх и соревнованиях можно на платформах вроде AI Cup, TCO Maraphone и CodinGame.

Обычные алгоритмические приемы из ICPC в игровых стратегиях не работают, потому что или задачи NP-трудны и оптимального полиномиального решения для них нет, или есть конкуренты, наличие которых делает соревнование непредсказуемым.

Сообщество молодое, но результаты (крутые!) уже есть

В мае 2020 года на CodinGame прошел очередной контест — Spring Challenge 2020. В нем приняли участие более 5000 программистов из разных стран. На протяжении 10 дней они писали ботов для модифицированной игры Pacman. Каждый игрок управлял одновременно несколькими пакманами разных типов (камень — ножницы — бумага). Пакманы могли поедать друг друга и конфеты, разбросанные по полю (картинку с ним я прикрепил в начале поста). Побеждал тот, кто съест больше всего. Чтобы было интереснее, организаторы сделали игру с неполной информацией: пакманы видели противника только по прямой до конца коридора. В результате приходилось по косвенной информации предсказывать действия соперника.

В мае 2020 года организаторы соревнования впервые составили не только личный зачет, но и отдельные рейтинги по компаниям и университетам. И тут есть чем похвастаться и УрФУ, и Контуру :)

По итогам контеста команда студентов и выпускников УрФУ заняла второе место в мире среди образовательных учреждений, а команда программистов из Контура — второе среди мировых компаний.

В ноябре прошёл ещё один контест — Fall Challenge 2020, по результатам которого Контур снова стал вторым в мировом рейтинге компаний. УрФУ выступил чуть хуже: мы стали седьмыми в мировом рейтинге университетов, зато снова заняли первое место по России (обогнали, например, МФТИ, МГУ, ИТМО и МГТУ им. Н.Э. Баумана).

6 мая стартует следующий большой контест — Spring Challenge 2021. Регистрация уже открыта, можно записаться и принять участие в соревновании :)

Что мы делаем для развития сообщества

В 2018 году мы создали курс «Алгоритмы, играющие в игры», который помогает готовиться к соревнованиям. Расскажу, как мы к этому пришли.

В Контуре довольно давно (с 2015 года) существует небольшая «тусовка» разработчиков игровых стратегий. Ребята участвуют в соревнованиях, придумывают идеи, проверяют их на практике и учатся доводить до рабочего состояния. Один из активных «тусовщиков» — Павел Егоров, преподаватель и руководитель ФИИТ, руководитель отдела обучения Контура. Именно он является создателем и преподавателем курса «Алгоритмы, играющие в игры».

В семестр курс изучают порядка 20 студентов. Занятия проводятся раз в неделю в формате семинаров. В курсе рассматриваются типичные алгоритмы и техники, позволяющие программировать ботов на высоком уровне, а потом проверять их в деле, сражаясь с крутыми соперниками за попадание в топ рейтинга. Помните Spring Challenge 2020, про который я говорил чуть выше? В нем участвовали 7 студентов курса, и 1 из них закончил соревнование в бронзовой лиге, 4 — в серебряной, а 1 — в легендарной (и занял второе место среди всех участников из УрФУ)!

Структура курса

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

Курс «Алгоритмы, играющие в игры» сочетает в себе теорию и практику. Перед тем, как участвовать в играх и соревнованиях, студенты с преподавателем несколько занятий разбирают теорию (методы случайного поиска, поиска по восхождениям и т.п.) и тренируются на классических задачах. В начале каждой такой пары преподаватель «вбрасывает» проблему, а ребята пытаются придумать ее решение.

Например. Имеется несколько грузовиков с ограниченной вместимостью по объему; также имеется набор коробок с определенным весом и объемом. Необходимо распределить коробки по грузовикам так, чтобы минимизировать разброс весов у грузовиков.

Да, это вариация задачи о рюкзаке.

Студенты предлагают разные подходы к решению задачи, а модератор задает наводящие вопросы, подталкивает к правильным мыслям, помогает осознать происходящее. Как правило, к концу занятия ребята изобретают нужное решение задачи, по пути частенько выдумывая и какие-то самобытные интересные идеи. Такие «выдуманные» алгоритмы запоминаются и понимаются гораздо лучше, чем куски кода из учебников и интернета.

Потренировавшись, студенты могут браться за большие задачи, им открывается возможность набирать баллы за курс, участвуя в соревнованиях на CodinGame. Эта платформа была выбрана для спецкурса, потому что на ней много разнообразных игр и соревнований: от самых простых, на которых можно набить руку, до сложных, где нужно писать ботов и предугадывать действия соперника. Любое решение на CodinGame сопровождается визуализацией в стиле видеоигр, а онлайн IDE поддерживает 27 языков программирования. А еще на платформе соревнуется автор курса и вся контуровская «тусовка» разработчиков игровых стратегий. Почему бы не писать контесты на одной платформе!

В 2020 году студенты в рамках курса приняли участие в двух соревнованиях:

• Ocean of Code — о нем поговорим в конце поста.
• Spring Challenge — тот самый майский контест.

В зачет в рамках курса шел и ещё один давно существующий контест на CodinGame:

• Code vs Zombie — контест, где нужно написать алгоритм убийства зомби, оптимизировав его так, чтобы возникающие в процессе комбо принесли игроку как можно больше очков.

У тех, кого индивидуальные соревнования пугают, была альтернативная возможность зарабатывать баллы за курс — исследование игр и алгоритмов. В команде из 3-4 студентов нужно было сформулировать гипотезы о том, какие алгоритмы сработают лучше — провести вычислительные эксперименты, сравнить разные подходы, проинтерпретировать результаты, сделать выводы, написать отчет. В итоге каждый студент самостоятельно выбирал, как именно он получит практику в этом курсе.

За задачи, контесты и исследования студенты получали 60% всех баллов семестра. Остальные 40% добирались на экзамене.

В заключение приведу примеры активностей курса: расскажу про одну задачу, одно исследование и одно соревнование.

Пример задачи: «Гоночки»

Есть машинка, которая двигается без трения. На каждом шаге ей можно указать ускорение (-1, 0 или 1) по обеим координатам. Машинка ездит по разным картам, на каждой из которых есть несколько флагов. Нужно проезжать машинкой по флагам в заданном порядке так, чтобы взять необходимое количество флагов за минимальное время. На некоторых картах есть препятствия, столкновение с которым досрочно заканчивает игру.

За каждый тест игрок получает количество очков, вычисляемое по формуле: 100*количество_взятых_флагов — потраченное_время. Студентам необходимо реализовать алгоритм решения задачи, набирающий максимум баллов на тестовом наборе карт. Задача является упрощенной версией «Coders Strike Back» с CodinGame.

Пример исследования: Race

Задача «Гоночки» (правда, с двумя машинками вместо одной) легла в основу исследования Race. Для его проведения студенты делились на команды по 3-4 человека, каждой из которых предлагалась своя вариация игры: машинки могли меняться скоростями, получали дополнительные возможности и т.д. Каждая команда придумывала свои подходы к программированию ботов, разрабатывала систему тестов и сравнивала качество работы алгоритмов в разных условиях. Результаты оформляли в отчете.

К примеру, здесь ребята исследовали первую модификацию игры и использовали подходы Random search и Preserve best. Синими точками обозначены флаги, серыми кругами — препятствия,красными «усиками» — варианты траекторий, а желтыми — траектории, выбранные машинками.

А тут можно увидеть, как использование тех же подходов заводит машинки в тупик.

Пример соревнования: Ocean of Code

Участники контеста должны управлять подводными лодками на карте 15х15, состоящей из воды и островов. Игроки не знают о расположении лодок друг друга, но имеют информацию о последних действиях противника, например, о перемещении на север или всплытии в определенном секторе.

На старте каждая лодка имеет по 6 очков. Цель игры — остаться с максимальным количеством очков и при этом нанести как можно больший урон лодке соперника. Набирать очки в процессе игры нельзя, их количество может только уменьшаться.

На каждом ходе лодкам доступны следующие действия:

• Переместиться на 1 клетку в заданном направлении (север, восток, юг, запад) и зарядить торпеду.
• Всплыть на поверхность. Это обнуляет путь лодки и разрешает движение по уже пройденным клеткам, но противникам становится виден сектор, в котором она всплывает.
• Выпустить торпеду не более чем на 4 ячейки в любую сторону. Ущерб от взрыва торпеды равен 2 очкам в клетке ее падения и 1 очку в соседних клетках. Торпеда может навредить не только противнику, но и самому участнику.

Игра длится 300 ходов. Участник проигрывает, если его лодка теряет все очки или совершает запрещенное действие: выходит за края карты, заходит на острова или дважды посещает одну и ту же клетку. После 300 ходов игра завершается победой участника с большим количеством очков.

Мне понравилось! Когда я смогу пройти курс?

Курс «Алгоритмы, играющие в игры» входит в основную программу первого курса алгоритмического бакалавриата, а также список спецкурсов, которые студенты ФИИТ могут выбрать для изучения во 2 семестре 3 и 4 курсов.