Предложения о том, как играть в Сокобан

Нотация

В этом руководстве будут использоваться следующие термины:

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

Общая стратегия

Самое короткое решение может содержать 100, 300 или даже 1000 ходов (наша самая простая партия 1 уже требует 73 хода, партия 8 требует 126 ходов). Если в среднем, скажем, 2 варианта для каждого хода, а решение занимает 100 ходов, то для поиска решения методом перебора потребуется перебрать 2¹⁰⁰ путей. Даже для компьютеров это невозможно. Поэтому нам необходимо:

1. раннее распознавание, если позиция мертва,
2. Разбейте общую цель на подзадачи. Если путь решения из 100 ходов можно разбить, скажем, на 10 подзадач, то сложность задачи резко снижается. Кроме того, можно было бы вывести порядок, в котором подзадачи должны быть выполнены, и тогда вся проблема становится легко решаемой.
3. найти ограничения на пути решения,
4. Подумайте о других эвристиках.

О 1) Раннее распознавание мертвых позиций

1.1) Иногда легко решить, является ли позиция мертвой, достаточно посмотреть на окрестности одного единственного ящика. Все, что для этого нужно, — это «местная» проверка. Если коробка не стоит на точке и ее нельзя перемещать по горизонтали и не по вертикали, то позиция мертва. Коробка может быть заблокирована стеной или другими коробками, которые также нельзя перемещать.

1.2) Немного сложнее увидеть, что позиция мертва, если коробка находится рядом со стеной и ее можно толкать, но только вдоль стены с той же стороны, и ни одно из мест, до которых она может дотянуться, не является точкой.

1.3) В этом обобщении коробка находится рядом со стеной и может быть перемещена в место, где стена не находится на ее стороне (место А ниже), но это свободное соседнее место А не может быть достигнуто рабочим после того, как он толкнет коробку рядом с А.

Эти три случая могут быть решены на месте и без перемещения работника. Таким образом, их можно проверить в исходном положении и отметить места как запрещенные, скажем, с помощью ! чтобы ящик никогда не был задвинут на такое место.

1.4) В дальнейшем обобщении рабочее может добраться до места А, но только ценой установки другого ящика в запрещенном месте.

Это объяснение является рекурсивным^[1], т.е. оно характеризует мертвую позицию с помощью слов «мертвая позиция». Такие мертвые позиции труднее распознать, потому что они не могут быть обнаружены при локальном осмотре и могут потребовать тестовых ходов.

О 2) Формулировка подзадач

Примеры подзадач:

1. Переместите работника из пункта А в пункт Б,
2. Перемещение определенного ящика из пункта А в пункт Б

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

Пример для (а): Как работник может пройти через коробку, чтобы попасть в А:

Все пустое пространство необходимо, так как работник должен ходить вокруг коробки. Если пустого места меньше, то работник не может пройти мимо коробки, не создав мертвую позицию.

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

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

Еще один типичный пример придумывания подзадачи выглядит следующим образом. Можно с уверенностью предположить, что для решения необходимо все внутреннее пространство в нужном месте. Это означает, что если исходное положение имеет объемные внутренние пространства, как пустая область 2 умножить на 3 в приведенном выше примере, то можно спросить, какова цель этого пространства. Может случиться так, что он нужен работнику, чтобы пройти мимо коробки, или он используется для временной парковки коробки, чтобы освободить место где-то в другом промежуточном месте. Итак, если громоздкое пространство способно временно вместить коробку, то какая это может быть коробка? Как можно доставить эту коробку на эту промежуточную стоянку?

О 3) Формулирование ограничений на пути решения

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

3.1) Существует коридор, в который можно войти с помощью ящика, но ящик никогда не может пройти через весь коридор, и поэтому пространство в конце коридора никогда не может быть достигнуто с той стороны, где коридор заканчивается.

3.2) До определенной точки можно добраться только с одной стороны, хотя с разных сторон есть свободное пространство.

3.3) Определенный ящик никогда не может быть перемещен в определенном направлении и поэтому может достичь только одной конкретной точки.

3.4) Поскольку точки могут быть достигнуты коробками только с некоторой стороны, это определяет порядок, в котором точки должны быть заняты.

3.5) Может быть ясно, какую точку нужно охватить в последнюю очередь, потому что пространство необходимо для того, чтобы работник мог толкать коробку в определенном направлении.

О 4) Другие эвристики

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

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

Пример готового решения (игра 8)

Мы вводим координаты для обозначения точек. Например, рабочий изначально находится в точке G1.

Изначально у рабочего есть только 2 варианта: а) пройти через отверстие G3, или б) пройти через отверстие E3. Прохождение через G3 позволяет рабочему только толкать коробку в B3 в B1 → смерти. Итак, рабочий проходит через отверстие E3 в B2:

Единственные толчки, которые мы можем сделать, это: а) ящик B3 до B4 (не до B5, что означает смерть) или ящик C2 вправо.

Мы понимаем, что коробки не могут быть перемещены в точки на маршруте через G3, потому что впоследствии они никогда не могут быть перемещены влево (см. 1.2).

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

Мы также понимаем, что коробка B3 может быть перемещена только по линии B и поэтому в конечном итоге должна заканчиваться на точке B4.

Чтобы переместить более поздние коробки на С4, а затем сдвинуть их вправо, рабочий должен иметь возможность переместиться на А4, но чтобы попасть туда снизу, ящик В3 должен быть в В2, а места В3, С3, С2 должны быть свободны, поэтому два ящика должны уйти в сторону и быть припаркованы в правом нижнем углу.

�

но продавливание коробок А3 или В3 не работает. Единственный другой вариант, который у нас был в позиции (2), состоит в том, чтобы сначала подтолкнуть коробку B3 к позиции B4, а затем сделать ходы, ведущие к позиции (3). Мы получаем

Теперь мы можем продвинуться вперед, сдвинув коробку C3 вниз до C2 и перемещаясь вместе с рабочим к коробке F2 к G2 и G3:

Как обсуждалось выше, нам нужны свободные места B3, C3, C2 и получить бокс B4 до B2, поэтому нам нужно временно припарковать бокс C2 на G2. Получаем:

Теперь мы можем следовать нашему предыдущему плану и сдвинуть блок G2 на C4, чтобы сдвинуть его дальше вправо:

Вопрос в том, насколько правым мы должны задвинуть эту коробку C4. Поскольку нам все еще нужно протолкнуть блок G3 по тому же пути, нам нужно доставить воркера к G4, а для этого нам нужно протолкнуть бокс C4 до F4 и переместить воркера в G4, чтобы отправить G4 в G3:

Чтобы переместить коробку G2 влево, работнику нужно пройти весь путь назад против часовой стрелки до H2.

В остальном все просто: коробка G2 выталкивается в C2, C4, D4

затем блок B2 перемещается в B4, а затем рабочий перемещается в G4, чтобы наконец вытолкнуть блок F4 на точку E4.

ДОГОВОРИЛИСЬ.