Sokoban: оптимальные решения

[B@R5uk]

Думаю, все знают игру-головоломку Сокобан. Выпущенная в 81 году прошлого века она давно стала классической, пусть и не столь популярной, как тетрис. Есть множество реализаций под всевозможные платформы и операционные системы. Её даже в MP3-плееры встраивают наряду со "Змейкой" (во всяком случае, у меня когда-то был такой плеер). Правила просты: кладовщик, находясь внутри склада-лабиринта с ящиками, должен переместить все ящики из начальной позиции в заданные. За раз можно толкать не более одного ящика. Для желающих ознакомиться "по-быстрому", есть всевозможные онлайн сервисы с этой игрой.

(Анимированная иллюстрация из Вики. Кто-нибудь, кстати, знает из какого сета этот левел?)

Большинство реализаций игры ведут некую статистику "успеваемости" игроков: подсчитывают число ходов, число толканий ящиков и время, затраченные на решение каждой конкретной головоломки. Наилучшие результаты сохраняются в качестве соревновательной составляющей. В случае простых/малых уровней время решения обычно ограничивается скоростью нажатия/срабатывания клавиш, а в случае больших уровней — является субъективной характеристикой игрока, поэтому, на мой взгляд, не представляет особого глобального интереса. Совсем другое дело количество движений!

На ряду с просто поиском решения конкретного уровня можно поставить задачу найти решение с минимально возможным числом ходов. Или же решение с минимальным числом толканий ящиков. В обоих этих случаях важны обе величины: при использовании первой метрики решение с 20 ходами и 2 толканиями будет лучше, чем решение с 20 ходами и 4 толканиями; равно как решение с 8 толканиями и 30 ходами лучше решения с 8 толканиями и 36 ходами для случая второй метрики. В связи с этой постановкой задачи естественным образом возникает желание написать программу, которая будет искать эти оптимальные решения.

Надо заметить, игра Сокобан стала своего рода песочницей для тестирования различных алгоритмов поиска пути и вообще приложений теорий искусственного интеллекта (или как это ещё по-умному называется). Бороздя просторы интернетов я периодически натыкался на различные научные статьи по теме. Определённой вехой стала статья Domain-Dependent Single-Agent Search Enhancements 1999 года (авторы Andreas Junghanns и Jonathan Schaeffer) и написанная её авторами программа Rolling Stone, которая ищет решения головоломки. Авторы поставили перед собой задачу написать программу, которая находит решения для максимально возможного числа уровней из 90 уровней сета оригинальной игры 1981 года. Чтобы уложиться в ограниченные ресурсы компьютера им по ходу дела даже пришлось отказаться от оптимальности решений. Не удивительно, что за два десятка лет с тех пор создано не только множество солверов разной степени эффективности, но и написаны программы для автоматического создания новых уровней. Вот здесь даже обсуждался некий конкурс составления головоломок с помощью программ. Удивительно, на форуме до сих пор не было общей темы, посвящённой этой увлекательнейшей задаче!

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

[iifat]

Многабукав.
Одного не пойму: ну чего такого вы от форума ждёте? У вас появились вопросы — ну дык не постесняйтесь задать. Возможно, кто-то ответит. Или благородный дон желает странного?

[kotenok gav]

Насколько я понял, B@R5uk предлагает обсудить алгоритмы для солверов сокобана.

[Sender]

Можно попробовать свести задачу к SAT и использовать известные SAT-солверы.

[wrest]

У меня такое впечатление, что задача давно съедена до косточек и вряд ли чего тут можно улучшить по сравнению с сущетвующими солверами.

[Sender]

Ну она всё-таки PSPACE-полна, так что говорить о том, что она съедена до косточек, несколько преждевременно.

[ozheredov]

B@R5uk в сообщении #1504843 писал(а):

игра Сокобан стала своего рода песочницей для тестирования различных алгоритмов поиска пути и вообще приложений теорий искусственного интеллекта

B@R5uk в сообщении #1504843 писал(а):

Определённой вехой стала статья Domain-Dependent Single-Agent Search Enhancements 1999 года (авторы Andreas Junghanns и Jonathan Schaeffer) и написанная её авторами программа Rolling Stone, которая ищет решения головоломки.

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

[B@R5uk]

ozheredov в сообщении #1504869 писал(а):

игра Сокобан стала песочнице для тестирования различных солверов для игры Сокобан, а не вообще приложений искусственного интеллекта.

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

wrest в сообщении #1504861 писал(а):

задача давно съедена до косточек и вряд ли чего тут можно улучшить по сравнению с сущетвующими солверами.

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

iifat в сообщении #1504848 писал(а):

У вас появились вопросы — ну дык не постесняйтесь задать.

Ну, вот, например, конкретный вопрос, который я сейчас обсасываю в своём уме день и ночь: как лучше решать задачу, вперёд или назад? Другими словами, двигаясь от начальной позиции к конечной или же от конечных (поскольку их много — отличаются положением грузчика) к начальной?

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

-- 12.02.2021, 20:50 --

Картинка для иллюстрации сказанного выше:



Крестиком помечены ячейки, куда нельзя ставить ящик при прямом поиске, поскольку с этих ячеек ящик нельзя передвинуть на конечную ячейку. Теоретическая верхняя граница размера пространства решений падает с $(27-4)\times C_{27}^4=403\,560$ до $(27-4)\times C_{12}^4=11\,385$.

[wrest]

B@R5uk в сообщении #1504881 писал(а):

Если я хочу решить конкретную задачу, то какой лучше скачать?

Я использую вот этот https://github.com/joriswit/YASS

-- 12.02.2021, 21:12 --

B@R5uk в сообщении #1504881 писал(а):

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

Не, я не вникал, только пользовался.

[arseniiv]

B@R5uk в сообщении #1504881 писал(а):

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

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

-- Сб фев 13, 2021 05:49:13 --

Так например легко увидеть, что на поле $5 \times 5$ нельзя получить расстановку четырёх ящиков по углам, четырёх по серединам стен и одного в центре, потому что куда в ней ни подойди, ничего не утянешь — мешает другой ящик.

[B@R5uk]

arseniiv в сообщении #1504908 писал(а):

при прямом ходе плохие ситуации — это когда ящик больше нельзя утолкать (вообще или в нужную сторону), а при обратном — когда нельзя утянуть.

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



Если грузчик утянет ящик вправо, то позиция станет тупиковой, если конечные позиции, на которых должны оказаться ящики, находятся слева. При этом, если грузчик чудесным образом окажется слева от сдвинутого ящика (в другой области связности), то такая позиция уже не будет мёртвой. (Область связности — это множество ячеек, по которым может перемещаться грузчик, не передвигая ящики).

wrest в сообщении #1504882 писал(а):

Я использую вот этот https://github.com/joriswit/YASS

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

[B@R5uk]

Интересно, как много существует статических блоков, присутствие которых на карте означает, что позиция мёртвая вне зависимости от того, где находится грузчик (для прямого хода, разумеется)? Если не считать случаев, когда ящик находится у мёртвой стенки (картинка с красными крестиками выше), то мне на вскидку вспоминаются только такие пять случаев:



Кто-нибудь подскажет другие варианты?

[wrest]

B@R5uk в сообщении #1504926 писал(а):

Спасибо. А его под винду можно скомпилировать?

Да. Та ссылка что я дал - порт на андроид вот этого https://sourceforge.net/projects/sokobanyasc/

[B@R5uk]

Для экспериментального исследования пространства поиска задачи написал следующую программку:

Цитата:

CellVector.java
MapHandler.java
MapLoader.java
State.java
State_Space_Explorer_1.java

Программа осуществляет поиск в ширину раскрывая позиции вперёд и назад. Поиск вперёд начинается от стартовой позиции, поиск назад — от всевозможных конечных позиций. Затем программа находит общие состояния и состояния, уникальные для каждого направления. Общие позиции — это те, через которые проходит хотя бы одно решение (не обязательно оптимальное). Уникальные позиции — это тупиковые направления поиска.

Идея заключается в том, чтобы иметь полную информацию о дереве/графе состояний, на котором ищется решение. Эту информацию в дальнейшем можно использовать для проверки эффективности функций отсева мёртвых позиций и функций оценки ожидаемого количества ходов/толканий, которая нужна для работы алгоритма A-Star. Разумеется, полную информацию можно получить только для карт небольшого размера и/или с малым числом ящиков. Например, для первого уровня оригинальной игры на моём компьютере памяти уже не хватает, а там всего то 6 ящиков. Программа делает далеко не всё, что я от неё хотел, а то, что делает, не очень эффективно. Однако, уже можно наблюдать некоторые интересные результаты:

Используется синтаксис Text

Yoshio 52 L09
#####
#. .###
#.#$$ #
#   @ #
# $#  #
##   ##
 #####
Cells:    19
Boxes:     3
                   Placements   States
Theoretical:              969   15 504
Forward total:            190    2 762
Forward dead:             153    2 268
Matched:                   37      494
Backward dead:            130    1 584
Backward total:           157    2 078

Yoshio Hand-Made L06
  #####
  #   ##
###$   ##
#  .$.$ #
# #.#.# #
#  *$*  #
###   ###
  # @ #
  #####
Cells:    31
Boxes:     6
                   Placements       States
Theoretical:          736 281   18 407 025
Forward total:        272 429    6 082 562
Forward dead:         270 208    6 035 122
Matched:                2 357       47 440
Backward dead:         10 559      104 378
Backward total:        11 748      151 818


NABOKOSMOS L40
   #####
 ###   #
##     #
# *** ##
#  *@ #
# .*$##
##   #
 ##  #
  ####
Cells:    27
Boxes:     6
                   Placements      States
Theoretical:          296 010   6 216 210
Forward total:        295 729   5 807 533
Forward dead:         294 967   5 793 018
Matched:                  865      14 515
Backward dead:          2 583      12 442
Backward total:         2 976      26 957

SokWhole L24
 ######  
##  . ## 
#@$ *$ ##
## $.$  #
 ###.*  #
   #.  ##
   ##### 
Cells:    23
Boxes:     6
                   Placements      States
Theoretical:          100 947   1 716 099
Forward total:         43 258     672 200
Forward dead:          43 237     671 943
Matched:                   21         257
Backward dead:            721       3 221
Backward total:           734       3 478
 

Надо заметить, что цифры прямого поиска являются сильно завышенными. Никто в здравом уме не будет в процессе поиска двигать ящики в мёртвые ячейки, с которых их нельзя будет переместить ни в одну целевую ячейку. Мне просто было интересно, как полный размер дерева прямого поиска соотносится с теоретическим максимумом для различных карт Сокобана. Чтобы иметь более осмысленные и практически важные значения нужно отсеять позиции с ящиками на мёртвых ячейках и уже затем подсчитывать число тупиковых состояний. Затем из них отсеять те, что содержат статические мёртвые блоки с картинки выше, и снова посчитать число тупиковых позиций. Тогда цифры будут значительно более представительными и можно будет судить об эффективности прямого и обратного методов.

Кстати, на счёт статических блоков. В исходнике YASS нашёл такие вот строки в комментариях:

Используется синтаксис Text

Deadlock Sets

--------
Legend:
--------
# :     A wall
- :     A 'simple-illegal-box-square'.
        They are marked directly in the board squares because
        this is faster than using deadlock-sets.
% :     A square in the set, it may or may not be a goal square.
? :     A square in the set unless the square is a wall.
X :     A non-empty square
--------

Please note that the program only uses deadlock sets where the player's
position doesn't matter. This way, it completely avoids all timeconsuming and
complicated pattern matching during the solving process, and bookkeeping and
checking for deadlocks is merely a question of simple reference-counting.

Finding deadlock sets is a part of the level pre-processing, i.e., it's not
time-critical since it doesn't affect the solver. This means the program can
spend a reasonable amount of time finding quite complicated deadlock situations.


--------
01              Non-goal corner
                ===============
 #              A non-goal corner square is an illegal square.
#-

--------
02              3-block
                =======
  #
 %%             At least one of the squares is not a goal-square.
#%

--------
03              4-Block/A
                =========
XX              Each 'X' is a non-empty square, and at least one
XX              of them is a box on a non-goal square. The non-wall
                squares in the block form a set.

--------
04              4-Block/B
                =========
 #              At least one of the squares is not a goal-square.
%%
#               The 'capacity of a set is the number of boxes
                that can be added before the set overflows,
                hence, the capacity is calculated as:

                squares - 1 - number of boxes on the squares.

                This applies to all deadlock sets except for
                type 07 and 08.

                4-block/B's are actually slightly more general
                than depicted: The '#''s aren't required, it
                suffices that the boxes can't move to any of
                the neighbour squares.


--------
05              Double-L
                ========
??              The central floor square must be a non-goal square,
? ?             or each "L" (upper-left, down-right) must
 ??             contain at least one non-goal floor square.

----------
06              Closed edge without goals
                =========================
 # ##~~# #      A closed edge is a line from which a box cannot
#----~~---#     escape. If there aren't any goals then all
  #     #       squares on the line are illegal.

---------
07              Closed edge with goals
                ======================
 # ##~~# #      The capacity of the set is the number of boxes
#%%%%~~%%%#     that can be added before the line overflows,
  #     #         hence, capacity = goals - boxes.

---------
08              Closed edges sharing a goal corner
                ==================================
 # ##~~~##      2 closed edges sharing a goal corner form
#%%%%~~%%%#     a union of the squares along the edges.
  #      %#     Capacity = goals - boxes.
         %#
         #

----------
09              Closed edge fence
                =================
 #%##~~#%#      The capacity and topology of the fence and the
#         #     closed-in floor-squares must make it impossible
 %#%#~~%#%      to break the fence.

----------
10              Fenced-in area
                ==============
                A fenced-in area is rooted in a corner square or
                the center of a 'double-L'. Using these sets as
                base, a generator builds new fenced-in areas by
                moving and adding boxes one at a time, taking
                the level topology into account.

---------
 

Всё довольно запутанно, но по крайней мере один новый блок точно есть. Причём, его можно наращивать до бесконечности:

[Mihaylo]

Предлагаю так:
1. Сначала разработать стратегию накрытия точек ящиками. Разработка стратегии сводится к поиску всех возможных размещений ящиков по точкам $A=\frac{n!}{(n-r)!}$, где $n$ - число ящиков, $r$ - число точек. Здесь гораздо меньше вариантов для перебора, чем вариантов траекторий.
В рамках каждой из стратегий:
2. Разработать тактику сдвигания ненужных ящиков, чтобы не мешались.
3. Разработать тактику движения ящиков на точки.
4. Выстраивать тактику движения персонажа (траектории) для реализации тактик п.2 и п.3.
5. Если тактики п.2-4 полностью собрались, значит стратегия реализуема.
В рамках общей стратегии:
6. Отобрать оптимальную стратегию.

Из этого множества соответствий "ящики-точки" можно легко отбросить недопустимые соответствия путем доказательства, а также, наоборот, доказать, что накрыть точку может только один из ящиков. Те же мертвые ящики легко отбрасываются из рассмотрения. Нужно стараться сокращать стратегические решения из п.1 в первую очередь.