Праздничный забег роботов OneScript Maze Challenge

28.10.24

Разработка - OneScript

Отгремел Infostart Tech Event 2024, топовое событие в мире 1С-разработки, традиционно проходящее в Санкт-Петербурге. Ваш покорный слуга в этот раз отмечал там 10-летний юбилей проекта OneScript. Отмечание проводилось в форме игры-соревнования по забегу роботов в лабиринте. Участники пытались написать алгоритм движения робота на языке 1С и сделать это быстрее других. О том, как это было – под катом.

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

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

 

 

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

 

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

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

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

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

 

Правила

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

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

 

Бонусы

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

 

 

Карты

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

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

 

 

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

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

 

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

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

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

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

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

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

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

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

 

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

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

 

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

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

 

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

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

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

 

Сергей Батанов

dmpas

339,8578

Иван Лосев

LosevI

345,1989

Алексей Федосеенко

Fedos

350,5498

Сергей Доровских

Serj1C

360,1411

 

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

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

 

 

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

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

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

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

infostartevent onescript роботы

См. также

OneScript Программист Бесплатно (free)

OneScript – это скриптовый движок для автоматизации всего и вся. О том, как OneScript помогает в разработке скриптов на языке 1С, пойдет речь в статье.

10.10.2024    2145    ardn    1    

6

Инструментарий разработчика OneScript Программист Руководитель проекта Бесплатно (free)

Все мы хотя бы раз работали с конструктором запросов. Результатом его работы является синтаксически верный запрос, оформленный по некоторому стандарту. Нравится - не нравится, а привыкаешь быстро, и на запрос, написанный руками, уже не хочется смотреть... А почему бы не попробовать сделать то же самое с исходным кодом 1С? Ну я и попробовал...

23.09.2024    579    0    stopa85    4    

5

Групповая разработка (Git, хранилище) OneScript Программист Платформа 1С v8.3 Бесплатно (free)

Скрипт для работы с SonarQube и локальным репозиторием Git.<br> Цель проекта – возможность выполнить быструю проверку качества кода перед тем, как помещать доработки в рабочее хранилище. В Sonar и Git выгружается не вся конфигурация, а только объекты из заданного списка.<br> https://github.com/vkrivov/go/

02.07.2024    3335    vkrivov@yandex.ru    8    

19

DevOps и автоматизация разработки OneScript Системный администратор Программист Стажер Бесплатно (free)

Рассмотрим создание самоформирующейся документации через комментарии и соглашения: как это сделать и зачем, с описанием полного цикла от исходников конфигурации до странички в интернете

17.06.2024    4980    bayselonarrend    5    

61

OneScript Программист Стажер Бесплатно (free)

Поговорим про меню, спиннеры, прогресс-бары и прочие свистелки для CLI приложений на OneScript

20.05.2024    2881    bayselonarrend    18    

70

Групповая разработка (Git, хранилище) OneScript Системный администратор Программист Бесплатно (free)

Сегодня мы посмотрим на Github Actions - встроенный инструментарий Github для автоматизации рабочих процессов. Разберем, что это такое, зачем и причем тут OneScript.

25.03.2024    2470    bayselonarrend    3    

42

DevOps и автоматизация разработки Групповая разработка (Git, хранилище) OneScript Системный администратор Программист Платформа 1С v8.3 Бесплатно (free)

Продолжение истории с прокси хранилища, но уже не на HTTP, а на TCP и без падений по памяти веб-сервера. Проверяем комментарии хранилища, вызываем веб-хуки, старты пайплайнов, gitsync по событию помещения версии в хранилище. И все это полностью на знакомом и понятном OneScript.

17.01.2024    5104    kamisov    23    

63

OneScript Программист Бесплатно (free)

Думаете, на OneScript неудобно создавать сложные инфраструктурные приложения? Ошибаетесь. Благодаря фреймворку ОСень за последний год экосистема библиотек, упрощающих написание собственных приложений, существенно выросла. Расскажем о самых передовых технологиях OneScript. Спойлер: будет много рефлексии, мета-аннотаций, желудей, напильников и дубов с завязями.

21.11.2023    4349    NikitaIvanchenko    16    

48
Комментарии
Подписаться на ответы Инфостарт бот Сортировка: Древо развёрнутое
Свернуть все
1. dmpas 418 28.10.24 09:14 Сейчас в теме
Это было незабываемо! Спасибо!
2. John_d 5885 28.10.24 09:47 Сейчас в теме
Решал похожую задачу на Yandex cup 2021
https://infostart.ru/1c/articles/1528864/
3. SerVer1C 808 28.10.24 13:00 Сейчас в теме
Недавно пробежал

Андрей, спасибо за увлекательный челендж!
Прикрепленные файлы:
Evil Beaver; +1 Ответить
4. EYakovlev 28.10.24 15:32 Сейчас в теме
Инфостарт прекрасное мероприятие! А с этаким развлечением было вдвойне приятно. Спасибо! Признаюсь, на докладе еще решил что буду гонять робота. Но, с Onescript до этого дела не имел. Т.к. я люблю гулять по Петербугру, то до робота добрался только во второй вечер. Взялся за дело бегло ознакомившись с мануалами, за что потом и поплатился. Т.к. были нюансы которые я пропустил. Я не планировал играть на результат. Просто получить рабочий алгоритм и слегка познакомиться с OneScript. Хотя что с ним знакомиться? Для конечного программиста это просто скриптовый язык в синтаксисе 1с, в данной задаче. В итоге, в первый вечер я не успел отловить все недочеты,а далее вечера были заняты. И робот у меня вышел из большой тестовой карты уже в воскресенье утром перед выездом из гостинницы.
Никаких хитрых решений я не применял. Если зачетную карту можно прогнать, хорошо. Будет любопытно узнать результат.
artbear; Evil Beaver; +2 Ответить
5. artbear 1563 29.10.24 14:58 Сейчас в теме
Отличное мероприятие получилось. Андрей, тебе большое спасибо за движок соревнования!
Serg O.; Evil Beaver; +2 Ответить
6. Serg O. 296 29.10.24 22:37 Сейчас в теме
Небольшая ошибка на сайте игры - на странице
https://game.oscript.io/syntax/Decision.html

РешениеПоставитьМетку = Решения.ОставитьМетку(Направления.Слева, "Я тут уже был");
РешениеПойтиВлево = Решения.ИдтиВлево();

ошибка при компиляции с этими решениями, при попытке установить метку
Решения = Новый Решения; или Решения = Новый Решения();
так же не помогает, а нужно использовать переменную Действия
из примера https://game.oscript.io/syntax/VisibleEnvironment.html
7. Evil Beaver 8237 30.10.24 12:29 Сейчас в теме
(6) это не ошибка, а скорее, не очень понятный пример, спасибо, что подсветили. Вопрос в том, как называется параметр метода ПринятьРешения. Если назвать его "Решения", то пример будет компилироваться.
8. Serg O. 296 30.10.24 15:29 Сейчас в теме
(7) да, наверное не ошибка, но для "начинающих" понять Oscipt с его собственными Классами - немного сложно. Первое, что приходит в голову - создать экземпляр класса, а он почему-то не создаётся.
Решения = Новый Решения - почему-то не работает так.

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

Кто не очень хочет/умеет в Visual Studio Code - помогает отладка с помощью Сообщить(..) в ключевых местах

В общем вроде отладил, 3-ий лабиринт рекорд пока 119,939
(старт с левого приоритета и с 2-мя ускорителями из комнат: 1,429 скорости и Бонусом ко времени в последней комнате, а старт с правого приоритета и 2-мя ускорителями 1,25х и 2х скорости почти в 2 раза дольше получился 210,533 - все тупики собирает)
Ещё помучаюсь пару дней... и попробую в супер-секретный лабиринт кинуть решение.

Спасибо за челлендж, очень прикольно и интересно :)

и да ещё небольшое уточнение - в тестовых лабиринтах +0,020 за 1 метку, а не 0,2 как в описании на сайте.
и на вход-выход из комнаты надо 4-6 ходов, а не 3-4
9. Evil Beaver 8237 30.10.24 15:42 Сейчас в теме
(8) секретных лабиринтов больше нет, они все видны в списке выбора карт в клиенте игры
11. Serg O. 296 31.10.24 12:57 Сейчас в теме
(9) да, спасибо, прошёл регистрацию через Telegram-Bot а и они появились.
Действительно рейтинг 340-360 ... впечатляет !

простые алгоритмы (и немного модифицированные со сменой приоритета левый - правый)
дают 600-700 ходов (это с заходом в комнаты и несколькими ускорителями!)
на карте Ivent 2024 лучший вариант у меня показывает 623,995 (между 11 и 12 местом)
остальной "тюнинг" явно какой-то хитрый с подбором смены право-лево на развилках.

@EvilBeaver классная связка Unity и Oscript, не планируется ещё что-нибудь подобное ?
"не понял как это сделано, но очень интересно"
10. EYakovlev 31.10.24 10:51 Сейчас в теме
(6) Вот именно о подобных ошибках я и писал выше (ошибки когда не внимательно прочитал инструкцию). Тоже думал сначала что "решения" это класс (или статический класс). А когда перестал сам себя дурить и внимательно прочитал иструкцию, то сразу понял что это параметр. У меня все это наложилось еще и на то, что я вытался обратиться к нему в доп. функции.
Оставьте свое сообщение