Поради щодо того, як грати в Сокобан

Зауваження

У цьому посібнику використовуватимуться такі терміни:

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

Загальна стратегія

Найкоротше рішення може містити 100, 300 або навіть 1000 ходів. (Нашій найпростішій грі 1 вже потрібно 73 ходи, 8 грі – 126 ходів). Якщо є в середньому, скажімо, 2 можливості для кожного ходу, і рішення займає 100 ходів, то для пошуку методом перебору знадобиться шукати 2^100 шляхів, щоб знайти рішення. Навіть для комп’ютерів це неможливо. Тому нам необхідно:

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

Про 1: Раннє розпізнавання мертвих позицій

1.1: Іноді легко вирішити, чи позиція мертва, потрібно лише подивитися в околі однієї коробки. Все, що потрібно, це «локальна» перевірка. Якщо коробка не стоїть на точці і її не можна переміщати по горизонталі, і по вертикалі, значить, позиція мертва. Ящик може бути заблокований стіною або іншими ящиками, які також не можна пересунути.

1.2: Трохи важче побачити, що позиція мертва, якщо коробка стоїть біля стіни і її можна штовхнути, але тільки вздовж стіни з тієї ж сторони, і жодне з місць, до яких вона може досягти, не є крапкою.

1.3: У цьому узагальненні коробка знаходиться поруч зі стіною і може бути переміщена в місце, де немає стіни що заважає (місце A нижче), але це вільне сусіднє місце A не може бути досягнуто працівником після пересування коробки в А.

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

1.4: У подальшому узагальненні працівник може досягти місця А, але лише за ціну постановки іншої коробки в забороненому місці.

Це пояснення є рекурсивним^[1], тобто характеризує мертву позицію за допомогою слів мертва позиція. Такі мертві позиції важче розпізнати, оскільки вони не можуть бути виявлені місцевою інспекцією і, можливо, знадобляться тестові переміщення.

Про 2: Формулювання підзадач

Приклади підзадач:

1. перемістіть працівника з точки А в точку Б,
2. Перемістіть певну коробку з А в Б

Де кожне з цих завдань має бути виконане без створення мертвої позиції.

Приклад для (a): Як працівник може обминути коробку, щоб дістатися до A:

Потрібне все порожнє місце, оскільки працівник повинен обходити коробку. Якщо порожнього місця не достатньо, то працівник не може пройти коробку без створення мертвої позиції.

Якщо вивчити багато таких підзадач з їхніми формами коридору, то можна заощадити багато часу, не думаючи про це, ось цей шлях із 9 рухів. Що ще важливіше, людина не здасться через те, що вважає це підзавдання неможливим.

Питання, пов’язане з підзадачами, полягає в тому, як їх знайти. Підзадачі виникають, наприклад, при розв’язуванні задачі в зворотному порядку. Припустимо, що до певної точки можна дістатися лише з одного боку і лише за допомогою однієї коробки. Отже, цю коробку потрібно штовхати в певному напрямку. Для цього робітнику необхідно перейти на інший бік. Завдання може полягати в тому, щоб привести коробку і робітника в потрібне положення.

Іншим типовим прикладом створення підзавдання є наступний. Можна з упевненістю припустити, що для рішення необхідний весь внутрішній простір у певному положенні. Це означає, що якщо вихідна позиція має об’ємні внутрішні простори, як-от порожня область 2 на 3 у наведеному вище прикладі, тоді можна задуматись, яка мета цього простору. Можливо, він потрібен працівникові для пересування коробки або він використовується для тимчасового зберігання коробки, щоб тимчасово звільнити простір в іншому місці. Отже, якщо громіздкий простір здатний тимчасово зберігати коробку, то яка коробка це може бути? Як можна доставити цю коробку до цього проміжного паркувального місця?

Про 3: Формулювання обмежень на шлях вирішення

Існує багато обмежень на шляху вирішення, можливих просто подивившись на позицію, не випробовуючи ходи. Приклади:

3.1: Є коридор, в який можна потрапити за допомогою коробки, але коробка ніколи не може переміщатися по всьому коридору, і тому до місця в кінці коридору ніколи не можна дістатися з боку, де закінчується коридор.

3.2: До певної точки можна дістатися лише з одного боку, навіть якщо з різних сторін є вільний простір.

3.3: Певна коробка ніколи не може бути переміщена у певному напрямку, і тому вона може досягати лише однієї певної точки.

3.4: Оскільки до точок можна потрапити за допомогою квадратів лише з певної сторони, це визначає порядок, у якому точки мають бути зайняті.

3.5: Може бути зрозумілим, яку точку потрібно досягнути останньою, тому що працівнику потрібен простір, щоб штовхнути коробку в певному напрямку.

Про 4: Інші евристики

4.1: Будь-яку послідовність поштовхів, яку можна змінити, можна і потрібно спробувати, навіть якщо це означає, що працівник повинен пройти довгий шлях, щоб штовхнути з іншого боку, щоб змінити ці поштовхи. Навіть якщо така вправа здається безглуздою, нова позиція може відкрити нові можливості як діяти далі.

4.2: Якщо є пряма лінія, яка відокремлює всі точки принаймні від однієї коробки, то ця коробка повинна перетнути цю лінію. Якщо це неможливо, позиція мертва. Якщо існує лише один спосіб перетину прямокутника цієї лінії, то це є сильним обмеженням для шляху вирішення.

Приклад повного рішення, гра 8

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

Спочатку робітник має лише 2 варіанти: A, пройти крізь отвір G3, або B, пройти крізь отвір E3. Перехід через G3 дозволяє працівнику лише перемістити коробку від B3 до B1, що призводить до мертвої позиції. Отже, робітник проходить через отвір E3 до B2:

Єдине, що ми можемо зробити, це A, коробку B3 до B4 (а не B5, що означає мертву позицію), або коробку C2 праворуч.

Ми усвідомлюємо, що коробки не можна переміщати в точки на маршруті через G3, тому що вони ніколи не можуть бути переміщені ліворуч, як показано в 1.2.

Але для того, щоб перемістити їх через отвір B3,C3, нам потрібен простір у цій області, тому нам потрібно припаркувати однe або дві коробки праворуч, а потім повернути їх.

Ми також усвідомлюємо, що блок B3 можна переміщати лише на лінії B, і тому, він повинен закінчитися на точці B4.

Щоб перемістити пізніші ящики на C4, а потім штовхнути їх праворуч, працівник повинен мати можливість перейти до A4, але щоб потрапити туди знизу, коробка B3 має бути на B2, а місця B3, C3, C2 мають бути вільними, тож дві коробки мають відійти з дороги та припаркуватися в нижньому правому куті.

�

але перемістити коробку A3 або B3 не виходить. Єдиний інший варіант, який у нас був у позиції 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.

ГОТОВО.