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

[B@R5uk]

zykov, великая цель за горизонтом: реализовать "Разделяй и Властвуй". Будничная текучка на данный момент: отработать понимание и навыки работы с графами, потому что для реализации РиВ они должны быть отточены особенно остро.

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

В частности с последним у меня даже на замкнутой карте не всё так гладко. Найти тупиковые состояния, получившиеся обратным проходом, легко: надо пройтись по графу в ширину прямым проходом из вершины, соответствующей начальному состоянию, а затем выкинуть все вершины, оказавшиеся не помеченными в процессе. Однако, в связи с используемым мною походом к построению графа состояний, у меня получаются дополнительные хвосты и ненужные рёбра. С вершинами-хвостами понятно, а вот рёбра для меня были удивлением (впрочем, понимание "почему?" приходит сразу как осознался факт их существования). Хорошо, что я установил себе пару редакторов Gephi и yEd Graph Editor и изучаю их на конкретных примерах, иначе бы я эти косяки не заметил. Кстати, очень интересные программы для работы с графами, которые имеют довольно богатый набор алгоритмов для автоматической укладки со всевозможными настройками. yEd даже онлайн вариант имеет.

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

(Оффтоп)

Картинка выше за одно иллюстрирует самоподобие графов пространств состояний пазлов сокобана, речи про которое я толкал на предыдущих страницах. Обратите внимание, как в трёх параллельных цепочках различие лишь в одном статическом ящике (находящемся, соответственно в ячейках 0, 5 и 6). Да, пример примитивный, в самоподобных участках нет ветвлений и циклов, как будет в графах задач на картах большего размера, но всё же.

-- 12.11.2021, 02:35 --

Mihaylo в сообщении #1538726 писал(а):

А вот из этого что-то реализовано?

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

[Mihaylo]

Перечитайте заново мой текст. Есть общая стратегия (отбор оптимального варианта), частные стратегии (ориентированные на построение деревьев адекватного размера) и тактики. На самом деле, три шага отбора и оптимизации.

-- 12.11.2021, 21:54 --

Есть ли у вас понимание в том, какая глубина перебора осуществляется?

[B@R5uk]

Наладил чистку графа от ненужных/лишних вершин/рёбер. Теперь играюсь с разными графами состояний в редакторе. Нашёл шикарный образчик самоподобия в графе пространства решений. Пазл #8 из набора Microban:



Начало (где-то 2/5 вершин) графа состояний выглядит так (картинка кликабельна для увеличения):


Обратите внимание на циклы с последовательностью ходов L-ulld-R-urrd, по которым ящик гоняется туда-сюда между ячейками d9 и e9. Этот цикл прицеплен ко всем видимым на картинке позициям на пути к решению, кроме первых начальных двух. Всего целых десять таких циклов для положения другого ящика на клетках b4, c2, c3, c4, d3, d4, d5, d6, d7 и d8. И это только подграф разрешимых состояний всего графа! У пазла всего с двумя ящиками. Какой мрак будет творится, когда ящиков и свободного места больше, трудно себе представить. На этом же графе самоподобие ещё видно в появлении у трёх таких циклов одинаковых хвостов с последовательностью ходов ul-D-D-D-D-D-D, которые соответствуют положению статичного ящика в ячейках b4, c3 и c4. Это три различных пути достижения конечного состояния.

-- 12.11.2021, 20:13 --

Mihaylo в сообщении #1538865 писал(а):

Есть ли у вас понимание в том, какая глубина перебора осуществляется?

Не понял, о каком именно переборе идёт речь?

-- 12.11.2021, 20:31 --

Mihaylo в сообщении #1538865 писал(а):

Перечитайте заново мой текст.

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

Вот, например пункт номер два: "Разработать тактику сдвигания ненужных ящиков, чтобы не мешались". Да, бывает много пазлов, где сдвигаешь в начале несколько ящиков и он распадается на отдельные скучные перетаскивания ящиков из точки А в точку Б. Но такое не всегда же работает! Что делать? Или даже если и работает, но решение в результате получается не оптимальным?

[B@R5uk]

Доделал остальные 3/5 графа и самоподобие проявилось на новом масштабе: 6,5 одинаковых 13-элементых блоков с двумя циклами каждый. Просто оставлю картинку:

[Mihaylo]

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

Пазл #8 из набора Microban:

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

если бы вы расписали свои идеи по-развёрнутей, а ещё лучше — подкрепили бы работоспособным примером, то было бы куда интересней!

Вот этот пазл #8. Два ящика, две точки - всего два варианта размещения. С каждым вариантом работаем по отдельности. Ненужных ящиков нет, значит тактика сдвигания ненужных ящиков пуста, тривиальна.
Тактика движения ящиков на точки. Хотелось бы с каждым ящиком работать по отдельности, но так нельзя. Поэтому делаем так: мысленно удаляем все ящики кроме одного. Строим граф траекторий перемещения ящика и граф траекторий перемещения персонажа. Делаем это для каждого ящика по отдельности. Каждый граф выдаст нам "ненужные точки", например, если в графе выбрать какую-либо траекторию, то в какие-то точки не будут использованы для перемещения. В этих точках можно временно размещать другие ящики. Цель - отобрать траектории во всех графах, чтобы не было коллизий.
Кстати, с большими пространствами 4х3 и более, где можно вертеть ящик, как угодно, можно работать просто: если граф траектории включает в себя хотя бы одну точку из этого пространства, то как-то пометить это одним узлом в графе.

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

Вот, например пункт номер два: "Разработать тактику сдвигания ненужных ящиков, чтобы не мешались". Да, бывает много пазлов, где сдвигаешь в начале несколько ящиков и он распадается на отдельные скучные перетаскивания ящиков из точки А в точку Б. Но такое не всегда же работает! Что делать? Или даже если и работает, но решение в результате получается не оптимальным?

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

-- 13.11.2021, 07:30 --

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

[B@R5uk]

Mihaylo в сообщении #1538949 писал(а):

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

Вот это интересная идея!

Mihaylo в сообщении #1538949 писал(а):

граф траекторий

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

Если же (как мне) нужно построить функцию, которая оценивает ещё и число ходов агента, то всё становится очень плохо: задача превращается в задачу о коммивояжере или что-то похожее. Потому что даже если разрешить всем ящикам и агенту двигаться через друг друга, то число ходов агента будет зависеть не только от того, как мы сопоставили ячейки с ящиками первой позиции ячейкам второй позиции (чего уже факториал комбинаций), но и в каком порядке агент будет перемещать эти ящики (результат: факториал в квадрате). Кроме того, если подходить к множеству связывающих траекторий более скрупулёзно, то эти траектории на самом деле связывают не две ячейки лабиринта, а две пары ячеек: в каждой паре одну — для ящика, другую — для агента. Например, для картинки выше выкинем ящик e9, тогда траектория ящика из d9 в d10 будет включать одно толкание, если агент находится в нижней области связности, и 15 толканий (по траектории d9->d8->d7->d6->d5->d4->d3->c3->c4->d4->d5->d6->d7->d8->d9->d10), если — как на картинке в верхней.

После всех этих размышлений я подумал: отсев мёртвых позиций, функции оценки, А-стар, DFS, оптимизация только числа толканий — это всё уже было. Результаты есть, разной степени блистательности. Почему бы не придумать что-нибудь кардинально новое? Какую-нибудь идею, использование которой даже примитивному методу грубой силы позволит щёлкать пазлы как орешки. Препроцессинг допустимых ячеек лабиринта и решение задачи задом наперёд назвать чем-то новым нельзя, да и результаты не шедевр, хоть мне они нравятся. А вот подход Разделяй и Властвуй — это, как мне кажется, весьма перспективная идея. И нереализованная к тому же, во всяком случае, Гугль ничего вразумительного не выдаёт.

[Mihaylo]

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

-- 14.11.2021, 09:50 --

Mihaylo в сообщении #1539118 писал(а):

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

Нужно формализовать "движение вперед по графу траекторий" и "никому не помешал". Слова-то вроде понятные, но как именно это запрограммировать?..
Надо взять пример а-ля "Hello, world!" для сокобана и проанализировать вручную, что есть графы траекторий и как их там скрещивать...

[B@R5uk]

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

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

zykov в сообщении #1532200 писал(а):

...Ещё 10 карт покрупнее, которые было сложно считать. Вот последняя карта:

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

  #####
 ## . ##
###$ $###
#  $ $  #
# . . . #
### * ###
 ## * ##
 ##$.$##
 ## . ##
 ##$.$##
 ## + ##
  #####
 

На рабочем компьютере не считалась. Вышло решить на сервере с 2Гб памяти.
В процессе работы память до 1.6Гб поднималась. Считало 25 минут. Количество состояний в памяти 36 408 246.

Результат:

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

..\_Test.txt  #3
  #####
  # . #
###$ $###
#  $ $  #
# . . . #
### * ###
  # * #
  #$.$#
  # . #
  #$.$#
  # + #
  #####

Cells total:   38
Active cells:  30
Boxes:         10

Map of active cells:
  #####  
  #.,.#  
###,,,###
#.,,,,,.#
#.,,,,,.#
###,,,###
  #,,,#  
  #,,,#  
  #,,,#  
  #,,,#  
  #.,.#  
  #####  

States found: 5934382
Move sequences: 21080
Processing time: 73710

Solution (501 move(s), 153 push(es)):

uulUU URuuL Drrru LdldD rUluR lddld drUUr uullD
Duurr urrdL Lddld drUUl ddddr UUluu luuuR uulDD
DlluR drUrR drruL LdLLu lldRR RDDlU drDDl Udrrd
dllUd rruul uurDu luuLr Rurrd LLDld drUUl dddDr
UUluu luuRD Duull ldRRu ruulD rdLdd rDDlU drrdd
llUdr ruulu urDul UURDr ruLLd lddrU lddDr UUluu
luuur rDLDD llluR RdrDD lUdrr ddllU UruuL DurRU
rrdLL DldDr UUllu uRDDu ullld RRuru ulDrd Lddrr
ddllU drruu lUURD rruLL dldDr Ululu uurrD LDDll
luRRd rRddl lUdrr uulDu Lulld RRdrr uULLr uulDD
rrddl UUrrr dLLul luurr Dulld drRdd llUUr Dlllu
RRdrr uuull DDldR uuurr ddLUd Ldllu RRurr ddrru
LdlLL uurrD ulldd rRuul D 

States found: 5929994
Move sequences: 21080
Processing time: 69194

Solution (503 move(s), 151 push(es)):

uurUU ULuuR Dlllu RdrdD lUruL ddrrd dlUUl uurrD
Duull ulldR Rddrd dlUUd drddl UUruu ruuuL uurDD
DrruL dlUlL dlluR RdRRu rrdLL LDDrU ldDDr Uldld
drrUd lluur uulDu ruuRl Lulld RRDrd dlUUd drdDl
UUruu ruuLD Duurr rdLLu luurD ldRdd lDDrU ldldd
rrUdl luuru ulDur UULDl luRRd rddlU drdDl UUruu
ruuul lDRDD rrruL LdlDD rUldl ddrrU dlluu ruuRl
LUlld RRDrd DlUUr ruuLD Duurr rdLLu luurD ldRdd
llddr rUdll uurUU LDllu RRdrd DlUru ruuul lDRDD
rrruL LdlLd drrUd lluur DuRur rdLLd lluUR Rluur
DDlld drUUl lldRR urruu llDur rddlL ddrrU UlDrr
ruLLd lluuu rrDDr dLuuu llddR UdRdr ruLLu llddl
luRdr RRuul lDurr ddlLu urD 
 

Корректность не проверял, надо бы закодить соответствующую процедурку. Считалось порядка минуты с четвертью каждое решение (частота ядра 3 ГГц). И это на Джава самым простым брутфорсом без всякого отсева и без А-стар! С А-стар эти уровни должны щёлкаться как орешки, наверное. Судя по графику в диспетчере задач, памяти потребовалось максимум 1,2 Гб, виртуальной машине я 2 Гб разрешил выделать для работы (ключ -Xmx2048m).

Из неприятного: по пазлам, которые не считаются из-за превышения лимита памяти, высчитал, что на одно состояние в среднем приходится 130-140 байт, что как-то с моими прикидками совсем не сходится (память замерена по разности rt .totalMemory () - rt .freeMemory (), где Runtime rt = Runtime .getRuntime ();). Надо разбираться в чём дело. Размер указателя вроде 4 байта, class State должен 16 байт занимать и class StateRecord — 28, по 2 указателя на эти классы из TreeMap <State, StateRecord>, в итоге порядка 52 байт. Размером коллекции массивов с последовательностями ходов между состояниями можно пренебречь, поскольку количество элементов в ней на 2,5 порядка меньше. Неужто коллекция TreeMap столько много внутри себя занимает?

[zykov]

B@R5uk
25 минут - это была какая-то старая версия программы.

zykov в сообщении #1532252 писал(а):

zykov в сообщении #1532200

писал(а):
В процессе работы память до 1.6Гб поднималась. Считало 25 минут. Количество состояний в памяти 36 408 246.

Нашел в архивах последнюю версию солвера.
Она эту карту номер 10 за 373 секунды решила. Так же 151 толкание ящиков.
Памяти меньше старой использует.
Количество состояний 11 188 099, память 234.7Мб. Максимальная длина очереди 729 804.

[Mihaylo]

Человек решает задачу быстрее и лишь с несколькими переменными в памяти (умозрительно рассуждаю).

[zykov]

Сомнительно, что средний человек решит за 5 минут такую карту (где надо минимум 151 толкание).

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

  #####
 ## . ##
###$ $###
#  $ $  #
# . . . #
### * ###
 ## * ##
 ##$.$##
 ## . ##
 ##$.$##
 ## + ##
  #####

[B@R5uk]

Наткнулся тут в Вики на такую интересную структуру данных: Bucket queue (ведёрочная очередь?) с константным (!!!) временем O(C) операций над её элементами (величина С — максимально возможный приоритет). Мало этого, для алгоритма Дейкстры поиска кратчайшего пути в графе, длины рёбер которого ограничены константой A, эта очередь хорошо оптимизируется до времени O(A) (надо рассматривать приоритеты по модулю A).

Применительно к задаче о поиске решения пазла Сокобан эта очередь потенциально может имеет просто шикарнейшее быстродействие! При поиске в ширину разница между максимальным и минимальным приоритетом в очереди не может превышать количество ячеек в лабиринте (что на много порядков меньше размера очереди Q), а при использовании A-star — длину решения (которая тоже на порядки меньше Q). Более того, приоритеты элементов очереди заполняют допустимых диапазон равномерно без пропусков. Поэтому одна из самых трудоёмких операций — удаление минимального элемента и поиск следующего минимального — делается на самом деле за время O(1).

Единственная проблема применительно к Сокобану, пожалуй, в том, что размер списков элементов в каждом ведре этой структуры данных может быть очень большой (обратная сторона малости величины A). По этой причине обычный список (простой массив, ArrayList или LinkedList) не прокатит и придётся городить для каждого ведра структуру данных с логарифмическим временем поиска элемента типа TreeSet. Это увеличит время операций добавления/удаления элемента и обновления приоритета c O(1) до $O(\log(Q/A))$ Тут надо думать, экспериментировать и сравнивать. В любом случае, структура данных Bucket queue однозначно достойна пристального внимания!

[zykov]

В моём случае быстродействие очереди было второстепенным.
Самое главное - это хранилище встреченных состояний. Оно огромно и в нём надо по значению искать (когда генерируем новое состояние, нужно проверить, не встерчали ли мы его уже).
Вобщем, обычная ассоциативная стуктура данных, вроде 'map' в 'stl'. Какое-нибудь red-black tree или hash table.

[B@R5uk]

Да, это верно. Более того, поскольку размер хранилища на столько велик, что оно не влезает ни в какие кэши процессора, а доступ к нему произвольный и совершенно случайный, то получается, что скорость работы определяется временем доступа к оперативной памяти, которое может составлять несколько сотен тактов процессора. Пока подгружается очередной лист/ветвь дерева, чтобы проверить является ли новое стояние в действительности старым и в каком направлении искать дальше, процессор ничего не делает.

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

[zykov]

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

что скорость работы определяется временем доступа к оперативной памяти,

Да, скорее всего там не в процессоре bottle neck, а в памяти. Поэтому видимо на сервере и работало быстрее, т.к. там была быстрая серверная память.