Как я участвовал в Russian AI Cup (кубок по искусственному интеллекту от mail.ru)

Russian AI Cup это соревнования для программистов, где нужно запрограммировать гоночную машинку чтобы она хорошо ездила по трассе. Каждый участник пишет стратегию для своей машинки, после чего стратегии соревнуются друг с другом на сервере. Кто лучше проехал трассу тот и выиграл.
Тут видео, одного из моих заездов:

Вообще это конечно соревнования для студентов, у которых много времени, ну меня это, как-то зацепило, когда я прочитал одну из майлрушных email-рассылок, даже пришлось зарегиться на портале it.mail.ru. Кстати молодцы майлрушники, портальчик у них не плохой, и как я понял, они собираются часто устаивать соревнования по программированию. В общем, как-то вечером делать было нечего, оставалось одна неделя до первого раунда и я решился. Ко всему прочему в качестве языка программирования можно была выбирать любой в том числе, мой любимый Ruby и я засел. Пришлось познакомиться с JRuby, так как это все под виртуальном машиной Java запускается. На входе для работы тебе дается инструкция около 60 страниц с описанием основным правил и описанием классов и методов.

инструкция Russian AI Cup

Описание классов и методов достаточно понятное, школьник может разобраться.

Описание классов

Стратегия представляет собой файл на любом из следующих языков (Java, C++, C#, Python, Ruby, Pascal даже был Scala). Основная часть народа наяривала на Java, C++, C#, на питоне было много, руби редко.

Стратегия на Ruby

Логика написания стратегии очень простая. По всему пути трассы есть waypoint-ы, которые требуется посетить. Есть методы для поворота руля move.wheel-turn, педаль газа move.engine-power и педаль тормоза move.brake. Первая моя стратегия была такой я получал следующий waypoint me.next_waypoint-index высчитывал угол между текущим моим положением me.angle и требуемым направлением движения (текущий тайл и тайл следующего waypointа). Кстати тайл это квадратик, каждая трасса состоит и тайлов, каждый тайл может быть одного из видов: пусто, верт-прямая, перекресток Т-образный перекресток и т.п. Машинка ездила очень не плохо, когда трасса была квадратом :) и все соседние waypoint-ы лежали на одной прямой. Однако когда трассы стали сложнее и следующий waypoint находился за стенкой, мой багги ехал прямиком в стену... что было грустно.

Очень интересно было отслеживать рейтинг в режиме реального времени. Готовую стратегию я закачивал на сайт http://russianaicup.ru/ и там 1-2 раза в час я участвовал в заездах, которые автоматически создавались системой. Пипец, это было мега интересно и волнительно смотреть, как твоя машинка начинает лучше ездить после закачки новой версии стратегии на сайт. Реально программировать было также интересно как играть в Heroes of Might and Magic 3, на втором курсе универа.. мега интересно. Жаль нельзя чтобы работа так вставляла :)

мой рейтинг

мои заезды

Еще одним вызовом было пройти в первый раунд. Туда допускалось только 900 лучших из 1700 участников. Оставалось 2 дня до начала этапа а я был на 1100 месте. Пришлось писать навигацию. Суть навигации была в том что по двух точкам: текущей и следующему waypoint-у мне нужно было стоить кратчайший путь. Для этого пришлось написать несколько методов, в частности connected-v?, который проверял что из одного тайла я могу проехать в соседний. Дальше я делал перебор по всем рядом лежащим тайлам (их четыре сверху, снизу, слева и справа) и проверял connected-v? . Если тайлы соединены то я добавлять новый путь и т.д. В итоге у меня рос массив из путей, до тех пор пока я не добирался до нужного waypointа и этот путь я брал как кратчайший, в общем-то перебор обычный, но пришлось помучиться пару вечеров. А потом самое приятное - рост рейтинга :) 850 место и я прошел в 1-й райнд! Походу были разные приколы с построением маршрута, заканчивалась память и алгоритм умирал на картах с множественным ветвлением, машинка застрявала и не ехала. В общем я еще улучшил алгоритм сделал выезд из заторов, сделал стрельбу по другим и использование нитры. Теперь красота!!

После всего этого мой рейтинг подрос, я поднялся до 750 места. Однако дальше все сложнее :) а времени мало, в общем я решил не жадничать и оставить призы (среди которых кстати Макбуки за 1-3 места, и iPad Air 2 за 4-6 места) пацанам (да кстати ни одной девушки, кроме японки я там не видел гы-гы), студентам нужнее.

В общем на самом деле было мега интересно и приятно поучаствовать в таком соревновании. Пусть я не выиграл, зато получил массу приятных эмоций и попрактиковался в JRuby :)

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

Жаль что я сгорел.. в конце, но это не помешало мне занять первое место :)