Знакомьтесь, наш герой

В игре участники управляли вот этим милахой. Он двигался внутри 3D-лабиринта, подчиняясь командам игроков.

В результате, робот должен был добраться до клетки с выходом, однако, где именно находится выход, игроки не знали.

Алгоритмы поиска пути

Алгоритмы поиска пути в графе (а лабиринт – это граф) довольно хорошо известны, но сложность заключалась именно в том, что мы не могли применить алгоритм поиска оптимального пути, такой, как алгоритм Дийкстры, или алгоритм А*, поскольку они опираются на известное расположение выхода и строятся в направлении выхода. Кроме того, эти алгоритмы используют волновой принцип поиска, как будто у вас сразу тысяча роботов бежит во всех направлениях сразу.

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

Поэтому, задача была не на поиск кратчайшего пути, а на поиск какого-нибудь, который удастся отыскать. Алгоритмов, которые решают эту задачу, по-сути всего два, но я не хочу спойлерить, вы сможете нагуглить их, если захотите сыграть.

Правила

Подробно правила игрового мира описаны на сайте игры https://game.oscript.io здесь же я вкратце опишу основные принципы.

Робот сообщает алгоритму игрока то, что он видит в данный момент. Игрок может переместить робота в том или ином направлении, ориентируясь на информацию, переданную роботом. Например, робот говорит: «у меня слева стена, спереди стена, справа коридор». Игрок принимает решение и говорит роботу «иди направо». Кроме того, в игре присутствуют метки. Метка – это надпись на полу, которыми участники помечали уже пройденные пути.

Бонусы

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

Карты

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

Взаимодействие с сервером игры было сделано на базе телеграм-бота, в который нужно было отправить файл с решением (алгоритм на 1Script), сервер запускал это на большой карте и возвращал в бота результат прогона. Разумеется, могли быть и ошибки в коде управления, тогда наш герой трагично погибал из-за необработанного исключения.

Алгоритмы игроков

Первые решения участники прислали к концу первого дня конференции и они были довольно медленные и я, как приславший ориентировочное решение «от админа» был на первом месте, а присланные решения – далеко позади меня. Но, парни только входили во вкус, а что развернулось позже – достойно отдельного рассказа!

Пример управляющего скрипта

// Основным методом является предопределенный метод ПринятьРешение.
// В нем вы перемещаете игрока по лабиринту, основываясь на том, что вокруг него
// И возвращая действия, которые ему надо выполнить.
//
// Параметры:
//  Окружение: Соответствие
//      Ключ: Направление (тип: перечисление Направления)
//      Значение: Структура
//          - ВидКлетки (тип: перечисление ВидыКлеток)
//          - Предметы: Массив меток или бонусов на клетке
//
//    В окружении всегда 5 элементов:
//      - Спереди: Вид клетки и предметы перед игроком
//      - Слева: Вид клетки и предметы слева от игрока
//      - Справа: Вид клетки и предметы справа от игрока
//      - Сзади: Вид клетки и предметы позади игрока
//      - Здесь: Вид клетки на которой стоит игрок и предметы на этой клетке
//  Действия: Специальный объект, методы которого возвращают команды (решения) которые игрок принял
//      Методы: 
//          - Идти[Вперед|Влево|Вправо|Назад]()
//          - Повернуться[Влево|Вправо]()
//          - Развернуться()
//          - ОставитьМетку(Направление, Надпись)
//          - УбратьМетку(Направление, Надпись)
//      Подробнее см. документацию.
//
// BSLLS:UnusedLocalMethod-off
Функция ПринятьРешение(пОкружение, пДействия)

    СообщитьВидимое(Направления.Спереди, Окружение);
    СообщитьВидимое(Направления.Справа, Окружение);
    СообщитьВидимое(Направления.Слева, Окружение);
    СообщитьВидимое(Направления.Сзади, Окружение);

    Возврат Действия.ИдтиВперед();

КонецФункции

Процедура СообщитьВидимое(Знач Направление, Знач Окружение)
    Сообщить("" + Направление + ":" + Окружение[Направление].ВидКлетки);
КонецПроцедуры

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

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

Просчет организатора (меня)

Придумывая игру я столкнулся с дилеммой: во-первых, задание не должно быть слишком простым, иначе будет неинтересно, во-вторых, оно должно быть достаточно легким, чтобы его можно было решить между делом, в кулуарах мероприятия или в номере гостиницы. И баланс между простотой и сложностью привел к тому, что попыток было неограниченное число. Запоминался всегда наилучший результат, поэтому можно было прислать 20, 30, 40 попыток, подобрав таким «псевдогенетическим» алгоритмом наиболее короткий путь. Как сказал мне Иван Лосев – на таких соревнованиях хак условий игры это, считай, обязательная вещь, все стремятся именно выжать из условий то, что не предусмотрели организаторы. Так и получилось.

Несекретный секрет

Довольно быстро игроки раскусили, как выглядит секретная карта, ведь ее было видно на воспроизведении прогона, но я сразу сообщил в чате, что просто подбор ходов «налево-налево-направо-вперед» это читерство и приниматься не будет. В итоге, все решения хоть и опирались на известные особенности конкретной зачетной карты, но все же были универсальными честными алгоритмами. Битва пошла за доли секунд игрового времени. Кто научит робота проходить карту, но так, чтобы он выбирал более короткий маршрут?

Битва титанов

Второй и третий день конференции прошел в заваливании телеграм бота решениями, которые из-за рандомизации ходов должны были стать лучше или хуже предыдущих, но т.к. учитывался наилучший результат, то спамить бота было безопасно. Пришлось мне срочно вводить таймаут на принимаемые решения. Это охладило пыл некоторых участников, которые к тому моменту автоматизировали отправку одного и того же решения раз за разом. Количество спама снизилось, а участники вынуждены были еще немного подумать над алгоритмами.

Весь второй и третий день шла битва между Сергеем Батановым и Иваном Лосевым, а на пятки им наступали Алексей Федосеенко и Сергей Доровских.

Рейтинг был публичным и все участники могли в любое время посмотреть на свой результат и результат конкурентов. Посмотреть на него можете и вы, по ссылке https://game.oscript.io/ui/rating

В итоге, в назначенное время прием решений ботом был прекращен, а итоговая таблица зафиксировала победителей. Тройка лидеров получила призы от Инфостарта, а Сергей Батанов, занявший первое место – почетную статуэтку победителя от меня лично.

Я тоже хочу поиграть!

Нет ничего проще, телеграм-бот все еще принимает решения. Заходите на game.oscript.io, скачивайте клиента игры и присылайте ваши решения.

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

Кроме того, я добавил ограничение в 10 попыток, кажется, что так веселее. Удачи вам и веселых забегов!