Задача №2 "Лабиринт" (ТЮИИ-2016)

1. Короткая формулировка:

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

2. Развернутая формулировка:

На поле NxN, в каждой клетке которого есть яблоко, забрасывают k роботов (как правило, от разных команд). Цель роботов: собрать как можно больше яблок за минимальное время (игра заканчивается, когда на поле кончились яблоки или после совершения M ходов). 

В начальный момент времени робот может знать, а может и не знать свое местоположение. В каждый следующий момент времени робот может совершить одно из пяти действий: попытаться сдвинуться в одном из четырёх направлений или остаться на прежнем месте. После каждого хода робот узнаёт результат своего хода ("прошёл + собрал яблоко", "прошёл на пустое поле", "не прошёл, потому что упёрся в стенку", "не прошёл, потому что столкнулся с другим роботом"). Соответственно, если несколько роботов хотят одновременно зайти на одно поле, то все они получают последний статус. 

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

3. Как устроен робот:

  • Робот перед каждым ходом получает следующие данные: размер поля (NхN), номер нынешнего хода, результат своего предыдущего хода и сам этот ход,  массив из 16N^2 символов с кодами от 33 до 126 (это его память - там робот может хранить своё представление о том, как устроена карта и любую другую информацию);
  • в результате хода робот возвращает одно из пяти состояний (свой ход) и массив из 16N^2 элементов; 
  • весь обмен данными ведётся через файлы.

4. Уровни решения:

А.  Квадратный лабиринт размером NxN клеток, робот ровно один, он знает свои координаты. Цель - как можно быстрее обойти все клетки. 

В.  В квадратном лабиринте NxN одна клетка является запрещенной (колонна), робот один, он не знает свои начальные координаты. Цель прежняя - как     можно быстрее обойти все клетки.

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

5. Поясняющая картинка:

6. Форматы входных и выходных файлов:

Программа-робот запускается средой-симулятором с двумя параметрами: именем файла со входными данными и именем файла для записи ответа. Из первого файла можно прочитать следующие данные (в скобках пример):

  • первая строка - сторона квадратного поля (5),
  • вторая строка - номер текущего хода (0),
  • третья строка - координаты робота (3 4) - два числа от 1 до N, где N - это сторона поля, или флаг "-1 -1", означающий, что робот не знает свои координаты,
  • четвёртая строка - свой предыдущий ход (может быть "00", "-0", "0-", "+0",  "0+", что означает остаться на месте, уменьшить первую/вторую координату, увеличить первую/вторую координату, соответственно),
  • пятая строчка - результат своего предыдущего хода (возможные значения:  "e" (прошёл на пустое поле), "a" (прошёл и взял яблоко), "w" (не прошёл из-за стены),  "r" (не прошёл из-за другого робота).
  • шестая строчка - объём своей памяти (может быть "0", если робот ранее ничего  не запоминал) или число не более 16N^2, где N - сторона поля,
  • остальные строки - символы с кодами от 33 до 126 (т.е. цифры от 0 до 9, английские   буквы от 'A' до 'Z' и от 'a' до 'z', а также знаки препинания, операций и скобки:  '!', '"', '#', '$', '%', '&', ''', '(', ')', '*', '+', ',', '-', '.', '/', ':',  ';', '<', '=', '>', '?', '@', '[', '\', ']', '^', '_', '`', '{', '|', '}', '~')   в количестве, указанном в предыдущей строке (как раз память).

Во второй файл робот должен записать следующие данные:

  • первая строка - свой ход ("00", "-0", "0-", "+0" или "0+"),
  • вторая строка - объём памяти ("0", если ничего не надо запоминать или число, не превышающее 16N^2, где N - сторона поля),
  • остальные строки - символы с кодами от 33 до 126 в количестве, указанном в предыдущей  строке (память).

7. Из чего состоит среда (скачать отсюда):

  • движок находится в каталоге "engine",
  • роботы - одинаковые "r1c", "r1pp", "r1cs", "r1pa", "r1py", пользующиеся памятью, и один случайно бегающий в каталоге "r2py",
  • входные данные для движка - в "tests".

Примеры файлов из "tests":
1) b0c.txt

5
A 3 4
r1c

Это означает, что среда должна запустить задачу A (про квадратное поле без колонн, где робот знает свои координаты), с полем 5х5, роботом с именем r1c, находящемся изначально на поле с координатам [3,4].

b) b1py.txt

5
B 2 1 2 2
r1py

Это означает, что среда должна запустить задачу B (про квадратное поле с одной колонной, где робот не знает свои координаты), с полем 5х5, роботом с именем r1py, находящемся изначально на поле с координатам [2,1], а колонной на поле с координатами [2,2].

Для запуска симуляции необходимо установить Python (https://www.python.org/).

В каталоге с роботами есть несколько .bat файлов для запуска тестовых роботов ("e0c.bat", "e0cs.bat" и т.д.). Если запустить любой из них, будет выполнен один из тестов. Например, запустить "e0c.bat", то будет выполнено следующее:
  @del /q output\*
  @python engine\engine.py tests\b0c.txt output\b0c.txt
Первая строчка очищает каталог "output", а вторая запускает симулятор, передав ему в качестве параметров имя теста ("b0c.txt") и имя файла для записи
протокола ("output\b0c.txt").

Соответственно, после запуска "e0c.bat" будет сформирован файл "b0c.txt" в каталоге "output" с подробным отчётом о том, куда и почему данный робот двигался. В этом же каталоге сохранятся входные и выходные файлы робота ("riNNN.txt" и "roNNN.txt", где "NNN" - это номер шага). Также возможна запись файлов с изображениями состояния поля (файлы "aNNN.bmp"), если используется Python2.

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

Робот - это каталог, в котором есть файл "run", в единственной строке которого написано, как запускать этого робота. Вариантов два: 
1) имя исполняемого файла (например, под Windows "robot.exe") и
2) имя интерпретатора и скрипта (например "python robot.py").

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

8. Рекомендуемый порядок работы:

1) Сформулировать алгоритм для робота, пользуясь тетрадкой в клеточку и карандашами, шахматной доской и шашками или любым другим набором для удобной симуляции поведения вашего будущего робота.

2) Изучить устройство робота r1, реализованного на выбранном вами языке. Все эти роботы одинаковы и выполняют три этапа: прочитывают входной файл,
определяются со своим следующим ходом, записывают выходной файл. Соответственно, задача команд - заменить код второго этапа на свой.

3) Создать тесты для своего робота (примеры входных файлов вы можете увидеть в каталоге "output" после запуска любого из тестовых роботов, формат файлов описан выше). Проверить, что ваша реализация своего робота правильно работает на созданных вами тестах. На этом этапе уже необходимо пользоваться SVN, чтобы всегда иметь возможность посмотреть историю изменений своего проекта.

4) Создать новый файл в каталоге "tests" для запуска вашего робота на тестовой арене (формат описан выше). Можно скопировать любой из имеющихся файлов под новым именем, а потом указать в его третьей строчке имя вашего робота (т.е. имя каталога, где находится ваш робот и файл "run").

5) Проверить, как ваш робот ведёт себя на арене. Если обнаружено неправильное поведение, то взять из каталога "output" те входные данные для вашего робота, на которых он сделал неправильный ход, чтобы доработать робота. Далее вновь проверить робота на аренах разных размеров и с разными начальными положениями робота.

6) Как только робот начал справляться со всеми задачами уровня A, переходите на более сложный уровень B (арена с одной колонной, робот не знает своих координат).

7) Если ваша команда создаст нескольких роботов, то в дальнейшем сможет сравнить их, чтобы выбрать наиболее эффективные и надёжные подходы для финала. Кроме того, имея несколько разных роботов, их можно будет запускать на одну арену (уровень C).
Но даже с одним роботом это можно будет делать - в таком случае на арене будет несколько разных роботов, управляемых одним и тем же алгоритмом (см. тест "b2py.txt" и запись боя "e2py.gif").

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

< >