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

Я не буду вдаваться в подробности процесса, потому что это не является целью этой статьи, но за этим стоит очень интересная задача.

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

Я объясню весь процесс создания идей и то, как я взялся за проблему и сумел найти решение. Таким образом, вы можете увидеть полный процесс обработки проекта такого типа. Там не будет ни строчки кода, вы можете обратиться по ссылке GitHub, где вы найдете все, что хотите: https://github.com/AmT42/Maze_generator_with_ReinforcementLearning

Давайте начнем,

Напомним, цель проекта — создать алгоритм, способный генерировать бесконечное количество лабиринтов 4х4. Мы будем использовать обучение с подкреплением, точнее алгоритм Q-обучения, для создания карт разных уровней. Вот в чем сложность этого проекта. В литературе по игровому дизайну обычно используется алгоритм BFS или DFS для создания лабиринта и/или использования обучения с подкреплением для его решения, но я нашел только одну статью, в которой говорится об обучении с подкреплением для создания лабиринта (Ахмед Халифа, Филип Бонтрагер и др. PCGRL: Генерация процедурного контента с помощью обучения с подкреплением, 2021 г.). По словам авторов: Насколько нам известно, обучение с подкреплением используется впервые. взяться за эту проблему. Вероятно, это связано с тем, что не сразу очевидно, как представить проблему генерации уровней как проблему обучения с подкреплением.

Именно в этом заключается вызов. Обычная практика для программиста, когда у него есть проект кодирования, с которым он никогда раньше не сталкивался, заключается в том, чтобы после прочтения и понимания проекта провести некоторое исследование в Google, StackOverflow и т. д. Мы не изобретаем велосипед, это важно чтобы не тратить время на ошибки, уже допущенные программистами, работавшими над такого рода проектами до нас. Это также дает нам больше информации и больше понимания возможных проблем в будущем. Лично я никогда раньше не работал над реальным проектом RL. У меня были только некоторые теоретические представления из моей степени магистра. Поэтому, естественно, как программист, знающий свои лучшие практики, я погуглил «RL для создания карты» :). После некоторых исследований я нашел статью, о которой я упоминал выше, это очень интересная статья, она дала мне некоторые идеи о процессе обучения, функции вознаграждения и т. д., но это была единственная статья, в которой говорилось о RL для создания карты и их проект сильно отличался в некоторых важных аспектах.

Я знал, что мне придется изобретать велосипед. Я начал с чтения статей и теоретических статей об RL, чтобы глубже понять, как это работает. Более того, я купил два очень хороших курса по Udemy у известных преподавателей. Первый — это знаменитый курс Ленивый программист, а второй — от Фила Табора. Это очень хорошая отправная точка для тех, кто интересуется обучением с подкреплением.

Пройдя эти теоретические и практические курсы по обучению с подкреплением, я почувствовал, что готов начать свой проект. Вскоре я столкнулся с некоторыми проблемами: каково оптимальное пространство действий, пространство состояний и так далее? Так начались головные боли. В инструкциях было использовать Q-обучение, но я понял, что у меня будет почти 1e10 элементов в моей Q-таблице, и с этим просто невозможно справиться. Пришлось думать о другом. Моей первой идеей было использовать DeepQ-обучение, но в инструкциях было использовать Q-обучение, и, поскольку я никогда не использовал DeepQN, я не хотел усложнять задачу. Затем я подумал об уменьшении размерности за счет использования симметрии и группировки похожих состояний. И в этот момент мне в голову пришла новая идея, хэш-таблица! Во время моего опыта запуска блокчейна хеширование было повсеместным, поэтому я много работал с хеш-функциями и словарями. Я уверен, что идея пришла оттуда.

Обобщить :

есть 24 бинарных редактируемых стены Либо есть, либо нет =› 2²⁴ возможных комбинаций стен.

Есть 16 ящиков, либо пустых, либо заполненных одной из трех ключевых точек = › 16P3 = 3360 возможных комбинаций ящиков.

Я решил использовать пространство действий с 11 действиями: addStart, AddEnd, addTreasure, EditTopwall, EditBotwall, EditEastWall, EditWestWall, goUp, goBot, goLeft, goRight (они говорят сами за себя).

Агент имеет случайную начальную позицию в матрице с 16 ячейками.

В итоге мы получаем почти 2²⁴ * 3360 * 11 * 16 возможных состояний.

Решение? Вместо использования Q_table используйте Q_hash (с Q dict), где мы храним только посещенные состояния. Мы также используем хэш для хранения нашего состояния с помощью хеш-функции, заданной Python: мы сохраняем его в self.state: hash(self.maze_map, self.start, self.end, self.treasure, self.ix, self.iy) где maze_map — это состояние нашего лабиринта, начало, конец, сокровище — расположение ваших ключевых точек, self.ix и self.iy — расположение нашего агента в матрице. Когда у нас есть состояние, если это новое состояние, мы инициализируем Q[self.state] = [0] * len пространства действий (= 11 в нашем случае). После настройки нашего Q_hash нам просто нужно использовать уравнение Беллмана и временную разницу обучения Q, чтобы обновить наш Q_hash.

На самом деле, наш алгоритм на самом деле не генерирует бесконечное количество лабиринтов, так как мы всегда даем один и тот же лабиринт в начале со всеми закрытыми стенами, только позиция агента в начале отличается от одной игры к другой, и есть только 16 возможных другое начальное местоположение для агента. Таким образом, представленный ниже, наш ИИ может генерировать лишь небольшое количество различных лабиринтов. Но это не проблема, нам просто нужно сделать несколько небольших модификаций, чтобы он мог делать «бесконечное» количество лабиринтов. Одним из решений может быть случайный выбор начального состояния в Q_hash.keys() (мы можем начать только с уже посещенного состояния).

Этот ИА в большинстве случаев дает достаточно хорошие лабиринты, но иногда они довольно «плохие». Чтобы улучшить это, мы можем «поиграть» с параметрами агента или среды, такими как гамма-фактор, коэффициент дисконтирования, количество сыгранных игр, количество шагов за игрой и т. Д. Но я думаю, чтобы сделать алгоритм намного лучше мы должны уменьшить len пространственных состояний до 10 000 или 20 000 состояний, используя обнаружение симметрии или сходства. Возможно, DeepQN тоже мог бы дать лучшие результаты, поскольку он справляется с проклятием размерности.

Уравнение Беллмана

Обновление Q с временной разницей

Вот и все, надеюсь, вам понравился пост. Если вам нужен пост, в котором я объясняю код, просто дайте мне знать. Спасибо за ваше время :)