Cadangan cara bermain Sokoban

Notasi

Panduan ini akan menggunakan istilah berikut:

• Langkah: satu langkah pekerja sama ada menolak atau tidak menolak kotak.
• Laluan: urutan pergerakan.
• Lokasi: Keadaan pekerja dan semua kotak berada di tempat tertentu.
• Penyelesaian: lokasi di mana setiap kotak terletak di atas satu titik.
• Laluan penyelesaian: urutan pergerakan dari lokasi asal ke penyelesaian.
• Lokasi buntu: lokasi yang penyelesaiannya tidak dapat dicapai.

Strategi Umum

Penyelesaian terpendek mungkin mengandungi 100, 300 atau 1000 langkah. (Permainan paling mudah 1 kita sudah memerlukan 73 langkah, permainan 8 memerlukan 126 langkah.) Jika secara purata, katakan, 2 kemungkinan untuk setiap langkah dan penyelesaiannya mengambil 100 langkah maka pencarian kekerasan memerlukan mencari 2^100 laluan untuk mencari penyelesaian. Malah untuk komputer ini tidak mungkin. Oleh itu kita perlu:

1. Mengenali terlebih dahulu jika lokasi itu buntu,
2. Pecahkan matlamat keseluruhan kepada sub tugasan. Jika laluan penyelesaian 100 langkah boleh dipecahkan kepada, katakan, 10 sub tugasan maka kerumitan soalan dikurangkan secara drastik. Tambahan pula, adalah mungkin untuk menyimpulkan susunan sub tugasan perlu diselesaikan dan kemudian keseluruhan soalan menjadi mudah untuk diselesaikan,
3. Cari sekatan pada laluan penyelesaian.
4. Fikirkan tentang heuristik lain.

Mengenai 1: Mengenali lokasi buntu terlebih dahulu

1.1: Kadang-kadang mudah untuk memutuskan sama ada sesuatu lokasi adalah buntu, seseorang hanya perlu melihat kejiranan satu kotak. Apa yang diperlukan hanyalah pemeriksaan “tempatan”. Jika kotak tidak berdiri di atas titik dan tidak boleh digerakkan secara mendatar dan tidak menegak, maka lokasinya buntu. Kotak itu mungkin terhalang oleh dinding atau oleh kotak lain yang juga tidak boleh dialihkan.

1.2: Adalah lebih sukar untuk melihat bahawa lokasi buntu jika kotak itu berada di sebelah dinding dan ia boleh ditolak tetapi hanya di sepanjang dinding di sebelah yang sama dan tiada satu pun tempat yang boleh dicapainya adalah titik.

1.3: Dalam generalisasi ini, kotak berada di sebelah dinding dan boleh dialihkan ke tempat di mana ia tidak mempunyai dinding di sisinya (tempat A di bawah), tetapi tempat jiran A yang bebas itu tidak boleh dicapai oleh pekerja selepas menolak kotak di sebelah A.

Ketiga-tiga kes ini boleh diputuskan secara tempatan dan tanpa memindahkan pekerja. Oleh itu, mereka boleh diperiksa dalam lokasi awal dan seseorang boleh menandakan tempat sebagai larang, katakan, dengan! supaya kotak itu tidak boleh ditolak di tempat sedemikian.

1.4: Dalam generalisasi lanjut, tempat A boleh dicapai oleh pekerja tetapi hanya dengan kos meletakkan kotak lain di tempat larangan.

Penjelasan ini adalah rekursif^[1], iaitu mencirikan lokasi buntu dengan menggunakan perkataan lokasi buntu. Lokasi buntu sedemikian lebih sukar untuk dikenali kerana ia tidak dapat dikesan oleh pemeriksaan tempatan dan mungkin memerlukan langkah percubaan.

Mengenai 2: Merumus Sub Tugasan.

Contoh sub tugasan ialah:

1. Pindahkan pekerja dari A ke B,
2. Pindahkan kotak tertentu dari A ke B

Di mana setiap tugasan ini perlu diselesaikan tanpa mewujudkan lokasi buntu.

Contoh untuk (a): Bagaimana pekerja boleh melepasi kotak untuk sampai ke A:

Semua ruang kosong diperlukan kerana pekerja perlu berjalan di sekeliling kotak. Sekiranya terdapat ruang kosong yang kurang maka pekerja tidak boleh melepasi kotak tanpa menghasilkan lokasi buntu.

Jika seseorang mengetahui banyak sub tugasan sedemikian dengan bentuk koridornya dengan teliti, maka seseorang itu menjimatkan banyak masa dengan tidak perlu memikirkannya, di sini laluan 9-langkah ini.Lebih penting lagi, seseorang itu tidak akan berputus asa kerana menganggap sub tugasan ini adalah mustahil.

Soalan yang berkaitan dengan sub tugasan ialah cara mencarinya. Sub tugasan muncul, sebagai contoh, apabila menyelesaikan soalan secara terbalik. Katakan titik tertentu hanya boleh dicapai dari satu sisi dan hanya dengan satu kotak. Oleh itu, kotak ini perlu ditolak ke arah tertentu. Untuk berbuat demikian, pekerja perlu pergi ke sisi lain. Satu tugas boleh membawa kotak dan pekerja dalam lokasi yang betul.

Satu lagi contoh tipikal untuk menghasilkan sub tugasan ialah yang berikut. Adalah selamat untuk mengandaikan bahawa semua ruang dalaman dalam lokasi diperlukan untuk penyelesaian. Ini bermakna, jika lokasi asal mempunyai ruang dalaman yang besar seperti 2 kali 3 kawasan kosong dalam contoh di atas, maka seseorang boleh bertanya apakah tujuan ruang itu. Boleh jadi ia diperlukan oleh pekerja untuk melepasi kotak atau ia digunakan untuk meletak kotak sementara untuk mengosongkan ruang di tempat lain secara pertengahan. Jadi jika ruang yang besar mampu menyimpan sebuah kotak buat sementara waktu maka kotak yang manakah itu? Bagaimanakah seseorang boleh membawa kotak ini ke tempat sementara?

Mengenai 3: Merumuskan Sekatan pada Laluan Penyelesaian.

Terdapat banyak sekatan pada laluan penyelesaian yang mungkin hanya dengan melihat lokasi tanpa mencuba langkah. Contohnya ialah

3.1: Terdapat koridor yang boleh dimasuki oleh kotak tetapi kotak itu tidak boleh bergerak melalui keseluruhan koridor dan oleh itu ruang di hujung koridor tidak boleh dicapai dari sisi di mana koridor itu berakhir.

3.2: Titik tertentu boleh dicapai hanya dari satu sisi walaupun terdapat ruang kosong pada sisi yang berbeza.

3.3: Kotak tertentu tidak boleh dialihkan ke arah tertentu dan oleh itu hanya boleh mencapai satu titik tertentu.

3.4: Oleh kerana titik boleh dicapai dengan kotak hanya dari beberapa bahagian, ia menentukan susunan titik mesti diduduki.

3.5: Mungkin jelas titik mana yang perlu ditutup terakhir kerana ruang diperlukan untuk pekerja menolak kotak ke arah tertentu.

Mengenai 4: Other Heuristics

4.1: Sebarang urutan tolakan yang boleh diterbalikkan dan harus dicuba, walaupun ia bermakna pekerja perlu pergi jauh untuk menolak dari sisi lain untuk membalikkan tolakan ini. Walaupun latihan sebegitu kelihatan sia-sia, lokasi baharu mungkin membuka kemungkinan baharu bagaimana untuk meneruskan.

4.2: Jika terdapat garis lurus yang memisahkan semua titik daripada sekurang-kurangnya satu kotak, maka kotak ini mesti melintasi garisan tersebut. Jika ini tidak mungkin maka lokasi itu buntu. Jika terdapat hanya satu cara untuk kotak itu melepasi garisan itu maka ini adalah sekatan yang kuat untuk laluan penyelesaian.

Contoh Penyelesaian Lengkap, Permainan 8

Kita memperkenalkan koordinat kepada titik label. Contohnya, pekerja pada mulanya berada di titik G1.

Pada mulanya, pekerja hanya mempunyai 2 pilihan: A, untuk melalui lubang G3, atau B, untuk melalui lubang E3. Melalui G3 hanya membenarkan pekerja menolak kotak di B3 ke B1, mengakibatkan buntu. Jadi pekerja melalui lubang E3 ke B2:

Satu-satunya tolakan yang boleh kita lakukan ialah A, kotak B3 sehingga B4 (bukan ke B5 yang bermaksud buntu), atau kotak C2 ke kanan.

Kita menyedari bahawa kotak tidak boleh dialihkan ke titik pada laluan melalui G3 kerana ia tidak boleh dialihkan ke kiri selepas itu, seperti yang dilihat dalam 1.2.

Tetapi untuk memindahkannya melalui lubang B3, C3, kita memerlukan ruang di kawasan ini, jadi kita perlu meletakkan satu atau dua kotak di sebelah kanan dan perlu mendapatkannya semula selepas itu.

Kita juga menyedari bahawa kotak B3 hanya boleh dialihkan pada garisan B dan oleh itu akhirnya perlu berakhir pada titik B4.

Untuk mengalihkan kotak pada C4 kemudian dan kemudian untuk menolaknya ke kanan, pekerja mesti boleh bergerak ke A4 tetapi untuk ke sana dari bawah, kotak B3 mesti berada di ruang B2 dan ruang B3, C3, C2 mesti kosong, jadi dua kotak mesti keluar dari laluan dan diletakkan di bahagian bawah sebelah kanan.

i

tetapi menolak kotak A3 atau B3 ke bawah tidak berfungsi. Satu-satunya pilihan lain yang kita ada di lokasi 2 adalah untuk menolak kotak B3 sehingga B4 terlebih dahulu dan kemudian melakukan langkah menuju ke lokasi 3. Kita mendapat

Kini kita boleh membuat kemajuan dengan menolak kotak C3 ke C2 dan bergerak bersama pekerja untuk menolak kotak F2 ke G2 dan G3:

Seperti yang dibincangkan di atas, kita memerlukan ruang B3, C3, C2 bebas dan menolak kotak B4 ke B2, jadi kita perlu meletakkan kotak C2 buat sementara pada G2. Kita mendapat

Sekarang kita boleh mengikut rancangan awal kita dan menolak kotak G2 ke C4 untuk menolaknya lebih jauh ke kanan:

Persoalannya adalah sejauh mana kita perlu menolak kotak C4 itu. Kerana kita masih perlu menolak kotak G3 melalui laluan yang sama, kita perlu membawa pekerja ke G4 dan untuk melakukan itu, kita perlu menolak kotak C4 sejauh F4 dan memindahkan pekerja ke G4 untuk menolak G4 ke G3:

Untuk mengalihkan kotak G2 ke kiri, pekerja perlu bergerak jauh ke belakang arah lawan jam ke H2.

Selebihnya mudah: kotak G2 ditolak ke C2, C4, D4

kemudian kotak B2 ditolak ke B4 dan kemudian pekerja bergerak ke G4 untuk akhirnya menolak kotak F4 pada titik E4.

SELESAI.