В этой статье мы, наконец, перейдем от учебного этапа из серии Automating is Fun и решим задачу, с которой многие из вас, вероятно, знакомы: поиск пути из заранее заданного лабиринта. Сложность этой задачи может сильно различаться в зависимости от размера и сложности упомянутого лабиринта: даже дети могут решить более простые задачи, в то время как некоторые из них намного сложнее и требуют много времени и усилий для решения. Не говоря уже о разочаровании, которое вы испытываете, когда тратите минуты на заданный путь только для того, чтобы обнаружить, что он ведет в тупик.

Поэтому, чтобы преодолеть это беспокойство, на этот раз мы разработаем агента ИИ, который сможет найти выход из любого лабиринта, каким бы сложным он ни был. Все, что нам нужно сделать, это посмотреть, как он справляется с данным уровнем. Звучит довольно волшебно, правда? Что ж, извините, что разочаровал вас, но это простая теория графов и классический ИИ. Но давайте не будем забегать вперед и сначала поговорим об окружении, которое мы будем использовать для генерации лабиринтов для нас.

Окружающая среда

В серии статей Автоматизация — это весело мы обычно пытаемся решать проблемы, когда сама среда уже задана, вместо того, чтобы создавать собственные среды (например, простые игры), чтобы задача немного сложнее и реалистичнее. Сегодня ничего не изменится, так как мы будем использовать онлайн-игру MaZe, чтобы генерировать для нас случайные лабиринты. Есть и другие хорошие онлайн-игры с лабиринтами, но я считаю, что эта лучше всего подходит для нас, так как она напомнила мне старые игры, а управление персонажем простое: он движется только при нажатии клавиши. (вместо того, чтобы идти до тех пор, пока персонаж не упрется в стену или использовать другую более сложную механику).

Каждый раз, когда мы нажимаем кнопку воспроизведения, игра генерирует случайный уровень, относящийся к одной из трех предустановленных сложностей: легкой, средней и высокой. Разница между ними заключается в размере и сложности генерируемых уровней. Это особенно полезно для нас, так как мы сможем протестировать наш агент на разных уровнях сложности и уровне, чтобы убедиться, что он работает хорошо. Цель одинакова для всех уровней: нам нужно достичь конечной позиции (нижний правый угол лабиринта), начиная с начальной позиции (верхний левый угол).

Однако есть одна вещь, которая объединяет всеуровни (независимо от их сложности): все они состоят из ячеек, образующих сетку. . Более подробно об этом будет рассказано в следующем разделе, поэтому все, что нам нужно знать сейчас, это то, что каждый уровень состоит из предопределенного количества строительных блоков (также называемых ячейками), которые имеют одинаковые размеры (ширина и высота). С любой стороны этих блоков может быть стена, которая будет ограничивать движение в этом направлении (белые пиксели на изображении ниже). Количество этих блоков варьируется в зависимости от сложности уровня: для легкого всего 10х10 ячеек, для среднего 12х12 и для сложного 15х15. В следующем разделе будет подробно описано извлечение этих блоков и то, как мы можем использовать их для построения стратегии для нашего агента.

Извлечение информации

Теперь, когда у нас есть среда и мы знаем, как она работает, нам нужно иметь возможность извлекать информацию, представленную на экране, чтобы агент мог понять, как выглядит лабиринт. Это будет сделано с помощью простого компьютерного зрения. Как обычно, мы будем использовать популярную библиотеку OpenCV.

Как упоминалось в предыдущем разделе, если вы играете в эту игру в своем браузере и обращаете внимание на структуру лабиринта, вы сразу заметите ключевую особенность лабиринтов, созданных в этой игре: они состоят из простых ячеек. Поскольку строительным блоком любого уровня является ячейка, мы хотим, чтобы агент мог различать их. А именно, мы хотим, чтобы он «видел», какая сторона данной ячейки загорожена белой стеной, чтобы агент мог не биться в них головой. Итак, в основном мы хотим наложить сетку на окно игры, как на изображении ниже, а затем обработать отдельные ячейки, чтобы узнать, какие пути заблокированы стенами, а какие нет.

Хорошо. Так как же нам этого добиться? Что ж, учитывая, что у нас есть входное изображение, на первом этапе мы порог изображения, чтобы потерять всю дополнительную информацию, которая может плохо повлиять на нашего агента, например узор и цвет фона и т. д. Далее , мы удаляем символ и его след из входного изображения, чтобы избежать путаницы между стенами, фигурой и его следом. Это можно сделать, просто установив эти пиксели в черный цвет. Затем мы точно укажем, сколько ячеек находится в одной строке и столбце в заданном входном изображении, и разделим изображение на разные части в соответствии с этим. Проще говоря, мы разобьем изображение на несколько меньших изображений, каждое из которых будет содержать одну ячейку. Например, если в строке 10 ячеек, в столбце 10 ячеек, а ширина, а также высота входного изображения 100 пикселей, то мы разделим изображение на 100 частей (10х10), где каждая кусок будет иметь размер 10x10 пикселей. После этого мы перебираем пиксели и определяем, какая сторона данной ячейки является стеной, просто проверяя граничные пиксели (или, точнее, пиксели в их окрестностях, чтобы гарантировать, что алгоритм будет работать) даже для не идеально разложенной сетки): если они белые, то с данной стороны у клетки есть стена, иначе с этой стороны стены нет. Просто, верно? Во время этого цикла мы будем хранить доступные направления для каждой ячейки в списке (например, если у ячейки есть стены с правой и левой сторон, то доступные направления в этой ячейки находятся вверху и внизу). Сделав это, мы получим информацию о каждой ячейке и доступных направлениях в этой ячейке, которую алгоритм ИИ может использовать для определения пути, по которому он должен идти.

Вот как все это выглядит в коде.

Алгоритм ИИ

Здорово! Теперь у агента есть доступ ко всей информации, необходимой для вычисления оптимального пути от начала до конца лабиринта. Но как именно агент будет это делать?

Как всегда, у нас есть множествоалгоритмов на выбор. Например, мы могли бы использовать нейронные сети или даже глубокое обучение с подкреплением, чтобы агент узнал, какие функции присутствуют в изображениях, на которых он должен основывать свои решения. Однако, как я всегда говорю в своих сообщениях, вы всегда должны думать о самом простом возможном решении. Не делайте себе лишней работы, потому что это никому не нравится. Итак, в сегодняшней статье мы будем искать самое простое решение, которым обычно является недооцененный классический ИИ.

Классический ИИ часто упускают из виду и недооценивают. Многие люди часто говорят что-то вроде: «Но у нас же есть нейронные сети. Зачем беспокоиться об этом?» или «Зачем изучать что-то настолько сложное, вместо того, чтобы позволить нейронным сетям делать свое дело?». Однако правда в том, что они действительно хорошо справляются с различными задачами (например, с поиском оптимального пути из точки А в точку Б). Термин «классический ИИ» может относиться к множеству алгоритмов и тем, но сегодня мы сосредоточимся на алгоритмах поиска по графу, поскольку мы хотим сгенерировать оптимальный (также известный как кратчайший) путь от начальной точки до конечной. . Алгоритмов такого типа существует множество, например поиск в ширину, поиск в глубину, поиск наилучших результатов и т. д., поэтому сначала нам нужно выбрать между ними или искать другие решения, если нас не устраивает этот список.

Вопрос, который вы должны задать себе сейчас: какую проблему мы здесь пытаемся решить? Что важнее всего? Самое главное, конечно, найти путь между начальной точкой и выходом. Что, само по себе, не звучит так пугающе. Однако мы хотели бы найти самый короткий , так как у нас есть таймер для каждого уровня, и мы не хотим упустить время. Таким образом, у нас остается оптимальный поиск и поиск в ширину, поскольку оба они выводят оптимальный путь, только для разных ситуаций. Оптимальный поиск следует использовать, когда у нас есть функция затрат (например, использование автомобиля и сжигание топлива, или разные маршруты, занимающие разное время, и т. д.), что сейчас не так. Теперь каждое действие, которое мы совершаем, стоит одинаково, поскольку нет никакой разницы между нажатием любой из четырех клавиш (влево, вправо, вверх, вниз). И снова, поскольку этот алгоритм оценивает каждыйузел на k-м уровне, передлюбым узлом на (k+1)-го уровня, это гарантирует, что мы найдем кратчайший путь от начальной точки до выхода. Здорово! Теперь мы знаем, что нужно использовать поиск в ширину!

В нашем случае каждый узел, представляющий состояние на графе, представляет собой ячейку в сетке. Это означает, что корневойузел (который является начальным узлом) — это первая ячейка, находящаяся в позиции [0,0], а узел, которого мы хотим достичь, — это узел, представляющий ячейку в правом нижнем углу сетки. На нашем графе будет ребро, соединяющее два узла A и B со стрелкой, указывающей на B, если мы можем использовать любое действие (также известное как operator), чтобы перейти от A к B (например, перейдя на одну ячейку влево).

Я решил не включать непосредственно соответствующий код (алгоритм ИИ) в статью, так как это заняло бы слишком много места. Однако, если вам интересен код, вы можете проверить его в файле utils.py в репозитории.

Решение

Хорошо. Так что теперь мы можем преобразовать захваченный экран в значимую информацию для агента, и у нас даже есть алгоритм, чтобы действовать как агент. У нас есть все необходимое, так что давайте посмотрим, как работает наш агент!

Начнем с легкой сложности! Как мы видим из GIF ниже, агент находит оптимальный путь очень быстро, без особых усилий.

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

Вы можете поиграть со всеми трудностями, изменив следующую строку в файле main.py.

DIFFICULTY = config.Difficulty.hard # Change hard to any difficulty.

Вывод

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

Если вам так хочется, скачайте код с моего GitHub и попробуйте! Не стесняйтесь изменять код, если у вас есть другая идея для извлечения признаков или даже для алгоритма ИИ, и получайте удовольствие! До скорого!