Открытое соревнование по программированию искусственного интеллекта

Проект

Песочница

Раунд 1

Раунд 2

Финал

Песочница (на 20 декабря 2015 г.)

Последние комментарии

1 ноября 15:44: AlexeyN написал комментарий в посте Планы по развитию чемпионата
1 ноября 11:24: tyamgin написал комментарий в посте Планы по развитию чемпионата
1 ноября 10:35: tyamgin написал комментарий в посте Планы по развитию чемпионата
31 октября 18:17: AlexeyN написал комментарий в посте Планы по развитию чемпионата
31 октября 18:15: AlexeyN написал комментарий в посте Планы по развитию чемпионата
31 октября 14:38: amurushkin написал комментарий в посте Планы по развитию чемпионата

Группа ВКонтакте

Russian AI Cup 2015 News - Выпуск №7 (от Романа Удовиченко)

Седьмой выпуск новостей от участника Romka:



sergeif

sergeif

?????-?????????

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

21.12.2015 22:25:42
SKolotienko

SKolotienko

Москва

Я так понимаю, что один из существенных недостатков такого подхода - большая “инертность” контрольных точек. Из-за этого, если происходит что-то непредвиденное, чтобы нашлась новая “хорошая” траектория, должно пройти какое-то относительно большое время. А если не повезёт (а на видео такое происходит часто), то выбирается траектория со столкновением. Но большинство карт (особенно “ручных”, в т.ч. _ud1) можно пройти вообще без столкновений и на достаточно высокой скорости.

21.12.2015 22:34:04
Valdemar

Valdemar

Университет ИТМО

Спасибо за выпуск, подход в стратегии интересный.

Вопрос: как именно двигаются точки? Просто +- какое-то расстояние в случайную сторону? Но ведь в таком случае мы можем попасть в локальный максимум.

И сколько таких траекторий строится за 1 тик?

21.12.2015 23:11:07
Romka

Romka

Яндекс

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

На каждом тике у нас есть множество текущих активных точек – это точки, принадлежащие тайлам, по которым проходит текущая траектория. Далее я прохожу несколько раз по этому множеству и пытаюсь рандомно двигать каждую из точек. При этом траектория может начать проходить по другим тайлам – это ок, в таком случае множество активных точек изменяется соответствующим образом. Получившуюся траекторию я оцениваю, как и большинство участников, по набору параметров: взяли ли бонусы и какие, попали ли в лужу, попал ли в нас снаряд, насколько сильно продвинулись по трассе, врезались ли в стенки. Если после случайного движения точки стало хуже, то возвращаю точку назад, если лучше – оставляю, как есть. За один тик удавалось перебрать 30-40 изменений точек с моделированием траектории на 177 тиков вперёд + 20 попыток изменить точки так, чтобы успешно применить нитро.

В идею я пытался заложить следующий смысл: я хочу иметь возможность случайно изменять кусок траектории, оставляя остальную часть в сохранности. Я рассчитывал, что при случайном изменении какой-то точки в середине траектории я вернусь к прошлой траектории, нацеливаясь на следующую по порядку точку – то есть, некий аналог сплайнов. Однако, кажется, на практике так чаще не получалось, чем получалось, и траектории менялись довольно сильно при изменении одной точки. Наверное, стоило не лениться и заставить себя написать какие-нибудь честные сплайны.

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

Ага, так и есть. Я пытался с этим бороться с помощью костыля вида “если траектории получаются совсем плохие – попробуем переместить все точки обратно в центр тайлов и заново подвигаем их”. Иногда это спасало. А ещё один существенный недостаток – склонность к застреванию в локальных минимумах, из которых не всегда можно выбраться перемещением одной контрольной точки, сколько ты их рандомно ни двигай, не говоря уже о том, что “сколько угодно” двигать нельзя – только пару десятков раз за тик.

21.12.2015 23:21:38
271828182845904

271828182845904

МГУ им. М.В. Ломоносова

йоху, я попал в новости! xD

22.12.2015 12:46:33
santa324

santa324

Москва

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

22.12.2015 12:59:22
altais

altais

Competentum

Очень крутая штука это визуализатор! А ты планируешь выложить его в открытый доступ? Очень интересно было бы поиграться с ним :)

22.12.2015 13:36:29
planB

planB

Реутов

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

23.12.2015 15:06:09