Сокобан алгоритм решения
Обновлено: 05.07.2024
Можно использовать следующие опции: С помощью оптии -p можно создавать собственные уровни:
BOXSEARCH v.5.0
Author: Ge Yong
Один из лучших в настоящее время солверов. Интерфейс несколько специфический, но, в конце концов, для солверов это не главное. Имеется новая версия BOXSEARCH v.5.1 beta2 от 14 янв. 2007 г. Этот солвер решает и большинство стандартных уровней, но некоторые уровни, которые решает солвер Takaken -а, ему не поддаются. Имеется режим оптимизации решений, которого нет у Takaken-а. Оба солвера, и Takaken-а и Yong-а, очень шустрые.
Сравнение различных солверов я провел на уровне svb485
|
К сожалению мой солвер не предназначен для решения больших уровней, уже на стандартном наборе от Thinking Rabbit Inc. он спотыкается - есть над чем поработать :-)
MYSOL20
Author: Adolfo Ovalle
Как пишет чилийский автор Adolfo Ovalle (Santiago, Chile), этот солвер написан на основе алгоритма Takaken:
This program is only an improvement, as for the number of 'moves', of the published by Paul Voyer, based on the algorithm of the Japanese Takaken.
Программа лежит на сайте Paul Voyer, там же имеется программа MySol312. Тестирование этих программ на уровне svb485 дало следующие результаты:
В этой статье я расскажу как написать свою реализацию известной игрушки Сокобан, а также алгоритм для её решения с нуля. Заодно применю на практике некоторые шаблоны проектирования и принципы SOLID.
Предыстория
Я пользуюсь кнопочным телефоном. Из развлечений на нём только радио и единственная игра Сокобан из 15 уровней. Из них я решил только 10 и застрял на одиннадцатом. Как-то раз я целый день ехал в поезде и решал этот злосчастный 11 уровень, но не преуспел. Тогда я решил прибегнуть к помощи компьютера, благо опыт программирования имею достаточный для такой задачи. Поставил цель: самостоятельно написать реализацию с решением этой игрушки. По результатам появилась эта статья.
Тот самый 11 уровень (решение в конце статьи):
Сама игрушка представляет собой прямоугольное 2D-поле, на котором раскиданы ящики, стены и метки. Ящики можно толкать, но не тянуть, в этом вся сложность. Ваша цель: переместить все ящики на клетки с метками. Пример игры:
Пишем реализацию
Давайте не будем усложнять себе задачу и создавать отдельный GUI со спрайтами и редактором уровней. Вместо этого остановимся на консольном варианте а-ля Rogue-like, где уровни будут отрисовываться построчно и загружаться из текстового файла. Сначала нужно придумать какие символы будут обозначать элементы на уровне. Я сделал такой выбор:
Теперь самый ответственный момент — выбор архитектуры приложения. Если ошибиться, то можно сильно повредить всей дальнейшей разработке. В нашем случае идеально подходит шаблон MVC — Модель, Представление, Контроллер. Модель хранит внутреннее игровое состояние и поле, даёт доступ к данным, не знает ничего о контроллере и представлении. Представление только печатает состояние модели в консоль. Контроллер считывает символы с клавиатуры и изменяет модель. Типичная ошибка новичков — добавлять бизнес-логику в контроллер вместо модели. В результате получаются переполненные чужим кодом контроллеры, нарушающие первую букву SOLID. Согласно ей, каждый класс должен брать на себя только одну ответственность. Представление — печатать уровни в консоль, модель — хранить состояние игрушки и логику работы с ним, контроллер — обрабатывать действия пользователя. То есть контроллер не должен знать как именно двигать ящики и игрока по полю, это ответственность модели. Контроллеру всего лишь нужно вызвать соответствующий метод. Ещё хорошо бы скрыть реализации всех трёх сущностей за интерфейсами. Это даёт следующее:
- Можно спокойно менять реализации, например, написать GUI-представление. На остальной код это никак не повлияет.
- В совокупности с инъекцией зависимостей значительно упрощается модульное тестирование.
Вторая частая ошибка новичков в ООП — компоненты сами управляют своими зависимостями, например создают экземпляры конкретных реализаций интерфейсов в конструкторах:
Здесь первая зависимость model была установлена как надо, через ссылку в параметре конструктора, а вторая view создана напрямую. Это плохо хотя бы потому, что теперь ConsoleController должен знать не только о View, но и ConsoleView, что повышает зацепление. Изменения ConsoleView могут повлечь за собой изменения в ConsoleController, чего можно избежать, написав вот так:
Теперь класс ConsoleController стало проще тестировать. Суть буквы D в SOLID в том, что класс не должен контролировать как именно удовлетворяются его зависимости. Эта ответственность теперь ложится на клиентов класса. Есть множество механизмов разрешения зависимостей, самый популярный из которых — контейнер зависимостей. Это отдельный модуль, обычно реализованный каким-нибудь фреймворком типа Spring или библиотекой, который сам может прокинуть все необходимые экземпляры в конструкторы или сеттеры. От вас нужно только их объявить.
Нужно придумать что из себя вообще представляет модель игрушки. Посмотрим ещё раз на скриншот, что мы видим?
- Квадратное поле из различных плиток
- Набор ящиков и меток
- Игрока
Каждую клетку на поле можно моделировать двумерным вектором (row, col) , где row это номер строки, а col столбца клетки, начиная с нуля. Каждой клетке будет соответствовать плитка — пустое место, куда можно сходить или стена. Ящики не пронумерованы, любой ящик можно поставить на любую метку, поэтому можно смоделировать их как множества клеток, на которых расположены ящики и метки. Позиция игрока также моделируется клеткой.
Было бы логично научить модель саму себя решать, то есть поместить алгоритм поиска решения внутри модели. Однако, если мы захотим иметь несколько таких алгоритмов и сравнивать их между собой, то будет лучше вынести их в отдельный модуль, скрытый за интерфейсом. В этом суть шаблона "Стратегия" — выносить несколько реализаций одной функции в отдельные классы и прятать их под общим интерфейсом, потому что клиенту в большинстве случаев всё равно как именно вычисляется ваша функция, он хочет просто получить результат. У меня получилось вот такая архитектура:
Заметьте, здесь модель представлена не одним классом, а целым пакетом Model. Главный класс Sokoban не скрыт за интерфейсом, потому что представляет единственную реализацию модели игрушки. Метод move() двигает игрока в одну из четырёх сторон. Сам Sokoban можно изменить только вызвав этот метод. Методы getCrates() и getMarks() возвращают неизменяемое представление множеств. Забегая вперёд, скажу что я сразу заложил два алгоритма решения Сокобана: обход графа конфигураций в ширину и поиск оптимального пути от начальной конфигурации до выигрышной с помощью A* (A star algorithm).
Метод run() запускает цикл "отрисовка уровня -> считывание движения -> обновление модели -> снова отрисовка"
Уровни будут загружаться из текстового файла со строками символов клеток, например:
Чтение и парсинг файла лучше тоже вынести в отдельный класс-создатель модели. Здесь идеально подходит шаблон "Абстрактная фабрика". Вкратце: внутри класса CharSokobanFactory пишем код чтения и парсинга файла, создаём игрока, поле, множество меток и ящиков. Важно, чтобы конструктор класса Sokoban оставался чистым, то есть содержал только присвоения зависимостей, это упрощает тестирование:
Созданием этих зависимостей как раз и займётся CharSokobanFactory . Фабрику нужно скрыть за интерфейсом, чтобы не привязываться к созданию модели через символьные строки. В будущем можно использовать другой формат хранения уровней.
Вместо стрелок я решил выбрать vi-like раскладку:
Игра считается завершённой, если множества ящиков и меток равны:
Чтобы не городить кучу свичей и if-ов в контроллере, я создал перечисление Direction, где выписал какой символ отвечает за какое направление. Затем создал класс Move, который инкапсулирует Direction и вызывает метод move(direction) у модели. Также у него есть статичный метод Move.resolve , который создаёт экземпляр по клавише пользователя.
Это хороший пример шаблона "Фабричный Метод". Плюс такого подхода: если я захочу чтобы игрок мог ходить по диагонали, то мне нужно будет добавить только 4 строчки в перечисление.
Таким образом соблюдается буква O в SOLID, Open-Closed Principle: классы должны быть открыты для расширений и закрыты для изменений. То есть, мы должны иметь возможность добавлять новый функционал без изменения старого. Очень часто происходит так, что новые фичи ломают старые, а исправления ошибок только вводят новые. Это как раз из-за того, что программисты не знают как правильно изолировать различные аспекты задачи по классам так, чтобы изменения одних не затрагивали другие.
Получается такая схема:
С такой архитектурой код контроллера становится очень простым:
Красота, как обычно, в мелочах. Как я уже говорил в начале статьи, контроллер не должен содержать никакой бизнес-логики, только читать команды от пользователя, перенаправлять их модели и отрисовывать представление. Такая реализация как раз не содержит ничего лишнего.
Реализация представления тоже проста до невозможности:
Строка 15 обрабатывает клетку с ящиком на метке. Буква G (Good) специально предназначена, чтобы обозначать ящик, задвинутый на метку. Однако такая клетка никак не моделируется, поэтому существует только в представлении.
Остаётся только научить модель передвигать игрока. Нужно учесть следующие моменты:
- Нельзя ходить в стену и в неподвижный ящик
- Ящик двигается в ту же сторону, что и игрок. Поэтому если перед ящиком стена или другой ящик, то двигать его нельзя.
Проверить эти условия несложно, в этом поможет флаг "walkable" в перечислении Tile:
Тогда проверка на то, можно ли сходить на данную ячейку сократится до нескольких строк:
Итак, модель умеет передвигать игрока, контроллер обрабатывать команды пользователя, а представление рисовать уровни в консоль. Самое время собрать всех вместе и запустить:
Для теста возьмём вот этот уровень:
В результате получаем именно то, что хотим:
Как и ожидалось, в стены ходить нельзя, ящики передвигаются как надо, игра заканчивается как только третий ящик оказывается на метке. Вот так просто можно написать простую игрушку Сокобан. Однако, самое сложное ещё впереди — нужно научить компьютер её решать.
Пишем свой искусственный интеллект
Что мы делаем когда передвигаем ящики в Сокобане? Мы меняем конфигурацию уровня. Конфигурация здесь это расположение игрока и ящиков на уровне. У каждой конфигурации есть несколько дочерних, в которые можно перейти, передвинув ящик на соседнюю клетку:
Понятно, что когда игрок просто двигается по уровню не трогая ящики, то конфигурация не изменится. Мы не перейдём в другую вершину графа. Можно было бы предположить, что позиция игрока вообще не имеет значения, и в конфигурацию входит только множество точек ящиков, но это не так. Позиция игрока не важна только пока он передвигается по одной компоненте связности внутри уровня. Кроме графа конфигураций, есть ещё граф инцидентных
клеток для конкретной конфигурации, например:
Игрок может перемещаться только по правой компоненте не трогая ящики, конфигурация от этого не изменится. Однако, если поместить игрока на клетку (1:1), он попадёт в левую и решить такой уровень будет невозможно.
Игра в Сокобан представляет собой прогулку по графу конфигураций в поиске выигрышной вершины. Решение — это путь в таком графе от начальной конфигурации до выигрышной.
Рёбра в графе помечены шагами игрока от его исходной позиции до передвижения ящика. Вес ребра это количество таких шагов. Нам интересно не просто определить имеет ли решение конкретный уровень, но ещё и найти это самое решение. В зависимости от уровня такой граф может иметь любую структуру, поэтому нам нужен алгоритм поиска пути, работающий для любых графов. Если забыть что рёбра взвешенные, то отлично подойдёт алгоритм поиска в ширину — Breadth-First Search (BFS).
Поиск решения с помощью BFS
В отличие от своего "кузена" — поиска в глубину (Depth-First Search) — в невзвешанном графе BFS строит кратчайшие пути от исходной вершины до всех достижимых, постепенно выращивая дерево родителей. Кстати, эти два алгоритма отличаются только порядком извлечения вершин из списка. BFS извлекает вершины в порядке очереди (FIFO), а DFS в порядке стека (LIFO), то есть это по сути один и тот же алгоритм. Псевдокод BFS:
Здесь параметр v.p указывает на предшествующую ей вершину на пути от начальной до v . Поднятый флаг v.marked показывает, что v уже посещали. Чтобы воссоздать кратчайший путь до v надо "промотать" список v -> v.p -> v.p.p -> . -> s до начальной задом-наперёд. Под искомой здесь понимается вершина с решённой конфигурацией.
Нам нужно уметь порождать все соседние конфигурации из данной. Каждая соседняя конфигурация порождается движением ящика в одну из четырёх сторон. Причём по бокам
клетки должны быть пустыми. Например, если двигать ящик вправо, то надо чтобы игрок мог добраться до клетки слева от ящика и чтобы справа была свободная клетка. Аналогично с вертикальным движением. Также при проверке можно отсекать заведомо проигрышные конфигурации, когда ящик прислоняется к стене без дальнейшей возможности движения:
Комбинируя все замечания, получаем вот такой код:
На первой строчке метод shortestPathsFromPlayer создаёт дерево предшественников в кратчайших путях от parent до всех достижимых вершин. Словарь walkablePoints отображает клетки v на v.p . Метод isDeadPosition как раз проверяет чтобы конфигурация не была заведомо проигрышной. Метод derive из класса Sokoban создаёт "копию" конфигурации со сдвинутым ящиком:
Обратите внимание, что "порождённая" таким методом копия не меняет множество меток. Кстати, класс Point я специально сделал неизменяемым (immutable). Нет смысла создавать отдельную структуру данных "Граф", заполнять его вершинами и рёбрами, а потом уже запускать BFS, это только пустая трата циклов процессора. Свойства v.p и v.marked можно симулировать ассоциативным словарём и множеством.
Теперь у нас в арсенале есть всё необходимое для реализации самого алгоритма:
Такой алгоритм находит решение, но далеко не факт что оно будет оптимальным, потому что BFS не учитывает вес ребра, то есть рассматривает граф конфигураций как невзвешенный. Чтобы найти наименьший путь во взвешенном графе можно взять, например, алгоритм Дейкстры, однако тут есть одна загвоздка. Понятно, что даже у простого уровня граф конфигураций может быть гиганским, а оптимальный путь чуть ли не единственным. Алгоритм,
который будет рассматривать вообще "весь" граф, будет работать слишком долго. Причём в графе будет много тупиковых ветвей, куда заходить вообще не надо. Было бы здорово указать на это машине.
На помощь приходит алгоритм А* (A star), который по сути является Дейкстрой с одним отличием. А* вводит т.н. эвристическую функцию h оценки расстояния от текущей вершины до решения. Значение h складывается с текущей оценкой пути. Идея следующая — если алгоритм заходит на одну из таких тупиковых ветвей, то большое значение h превысит текущее оптимальное и алгоритм просто дальше не пойдёт. Нужно только придумать достаточно
"хорошую" эвристику. Я взял сумму расстояний ящиков до ближайших к ним меток. Класс AStarSolver реализует описанную логику. Код преводить не буду чтобы не загружать статью, всё есть по адресу.
Чтобы запустить новый алгоритм ИИ я написал новый контроллер AIController , который не читает команды из консоли, а решает уровень указанным алгоритмом и по таймеру проигрывает решение. нужно изменить всего одну строчку в main . Наши инвестиции в архитектуру окупились:
Выводы
Мы создали свою реализацию игрушки Сокобан, применили на практике шаблоны проектирования "Абстрактная Фабрика", "Фабричный Метод", "Стратегия", рассмотрели принципы S, O и D из SOLID и реализовали алгоритмы BFS и A*.
Решение того самого 11 уровня из начала статьиБуду рад любым комментириям как по коду, так и по самой статье. Увидимся!
В первой версии перебирал движения самого грузчика (робота). Перебирал рекурсивно в глубину, для защиты от зацикливания хранил все пройденные варианты в массиве. Решение он выдавал в виде строки, указывающей в каком порядке нажимать кнопки в игре. Эту последовательность я загружал в программу MacroExpress, а она уже посылала нажатия окну игры. Регулируя паузы между отправкой нажатий можно было смотреть прохождение уровней на удобной скорости.
Бот решил несколько первых уровней и на очередном застрял на пару суток. Этот уровень был раза в 2 больше предыдущего, но время поиска решений росло экспоненциально. Так и не дождавшись ответа, я стал писать вторую версию. Движения робота заменил на движения ящиков, т.о. уже не надо хранить ходы пути робота от одного ящика к другому. На каждом ходу я определял до каких ящиков может сейчас добраться робот и в какую сторону толкнуть.
Тогда бот решил несколько следующих уровней и опять застрял. Потом было еще несколько версий:
— добавил ограничение глубины рекурсии, полагая, что большинство уровней можно решить менее чем за 100 движений ящиков;
— пометил на карте статичные тупиковые места, например угол или первый ряд вдоль ровной стены, т.к. потом будет невозможно вытащить оттуда ящик;
— добавил простейший анализ хода и отбрасывание очевидных динамических тупиков типа сдвигание квадрата из 4 ящиков;
— хранение координат всех предыдущих ходов заменил на хранение их хэшей, чтоб больше влазило в память и было быстрее искать;
Все это позволило продвинуться еще на несколько уровней, но стало понятно, что сложность решений сильно увеличивается с каждым уровнем. Тогда я выбрал самый крупный уровень — 86. Уж если бот решит его, то с остальными справится легко.
Итак, уровень 86.
Он содержит 46 ящиков и 156 клеток поля. При этом 40 клеток это статичные тупиковые места, итого 116 клеток на которые можно двигать ящик. Значит, число разных вариантов не будет превышать 116^46 = 92271483792519010208299118408158326223759549834325815837590809967385695915673894137078445244416. Да, это число из 95 цифр. Оно
= 9,2e+94. Максимальное число ходов в этом случае нет смысла учитывать т.к. такая оценка оказалась еще больше: допустим максимум ходов = 100, и в среднем на каждом ходу можно толкать каждый ящик хотя бы в одном направлении из четырех, тогда количество вариантов не будет превышать (46*1)^100
Дополнение об эвристиках:
— статичные тупики
Понятно, что если задвинуть ящик на любое место помеченное красным маркером, то потом уже будет невозможно оторвать его от стены чтобы толкать к месту назначения. Такие места я заранее маркирую на карте и бот не делает такие ходы в процессе перебора.
— динамические тупики
Понятно, что если сдвинуть 4 ящика квадратом (в различных сочетаниях с ящиками и стенами), то потом уже будет невозможно оторвать их друг от друга. Бот анализирует каждый ход и не делает ходы, приводящие к такому квадрату.
Более сложных пока не придумал.
Конечно, реальных вариантов будет гораздо меньше первой оценки из-за отсечения динамических тупиков, наверное, на несколько порядков. Но даже если взять половину порядков этого числа (92271483792519010208299118408158326223759549834) и хранить состояние каждого хода всего в одном байте, то потребуется 83920425634022658603 терабайт.
Тут-то я понял, что «еще подождать и бот переберет все ходы» как на первых уровнях уже не получится. Надо что-то кардинально менять в алгоритме, на каждом ходу проводить более сложный и долгий анализ, но зато отсекать бОльшие поддеревья вариантов. Но как именно это сделать пока не знаю… может Вы сможете мне посоветовать? Использовать какие-то приемы из области графов, муравьиные алгоритмы, нейронные сети?
Если рассматривать задачу о сокобане узко, то она сводится к задаче написания некоторых частных программ, с помощью которых можно было бы найти по заданному уровню решение. Можно дополнительно предъявлять условия к искомому решению, например, найти решение с минимальным числом ходов или с минимальным числом перемещений ящиков. Можно расширить класс сокобановых задач, включив в этот класс проблему генерации уровней.
К счастью для сокобана, даже эти частные задачи быстро выводят нас на совершенно иной уровень понимания, когда сама побудительная задача уже перестает иметь какое-либо значение, а служит великолепным полигоном для тестирования алгоритмических идей.
Читайте также: