🛸 🧘🏾 🚘 Cara mengatasi "Minesweeper" (dan membuatnya lebih baik) 🈷️ 🔱 🤳

Minesweeper adalah gim sederhana dengan aturan sederhana, namun beberapa konfigurasi membuat kesulitan yang menarik. Dalam artikel ini, kami akan membuat pemecah Minesweeper dengan meningkatnya kompleksitas, dan merefleksikan bagaimana dinamika permainan berubah dengan peningkatan bertahap dalam tingkat bantuan. Pada akhirnya, kami akan mengembangkan versi baru game dengan gameplay yang jauh lebih menarik.

Alasan lokal: nol tambang tetangga

Dalam gim asli , satu mekanisme otomatis digunakan: ketika pemain membuka sel, di sebelahnya tidak ada ranjau, mesin gim membuka semua sel tetangga. Ini tidak mengancam gim, sehingga Anda dapat membiarkan komputer melakukannya dengan aman, dan situasinya sendiri langsung jelas bagi pemain dan tidak mengganggu gameplay.

Alasan ini sepenuhnya lokal: hanya satu informasi sel yang diperhitungkan untuk memutuskan tindakan selanjutnya.

Sulit menemukan situasi di mana permainan akan menjadi lebih buruk tanpa bantuan otomatis ini. Cobalah untuk memainkan permainan seperti itu untuk mendapatkan gambaran tentang bagaimana ia berjalan tanpa secara otomatis membuka sel [dalam artikel asli, semua contoh bersifat interaktif] :

Pertimbangan lokal berdasarkan lingkungan

Akan mudah bagi pemain baru untuk memahami bahwa jika jumlah ranjau tetangga, yaitu, jumlah yang ditunjukkan dalam sel, sama dengan jumlah sel tetangga yang belum ditemukan, maka semua sel ini harus ranjau, jadi Anda perlu memberi tanda pada mereka. Demikian pula, ketika jumlah tambang tetangga sama dengan jumlah bendera tetangga, maka sel tetangga yang belum ditemukan yang tersisa harus kosong.

Dalam aturan ini, satu sel diperhitungkan, serta keadaan sel tetangga (terbuka / dicentang).

Menerapkan aturan-aturan ini secara manual bisa menyenangkan. Jika Anda menambahkan penghitung waktu, pemain mulai belajar cara menerapkannya dengan cepat dan akurat. Ini mengubah Minesweeper menjadi permainan reaksi . Apa yang terjadi jika kita mengotomatiskan aturan ini?

Otomatisasi seperti itu memiliki efek samping yang menarik - menandai kotak dapat memiliki konsekuensi fatal secara instan.

Kalau tidak, kita mungkin mengalami situasi yang dapat dibagi menjadi tiga kategori:

Game sepenuhnya diselesaikan dengan menerapkan aturan otomatis
Situasi rumit yang membutuhkan lebih banyak sel untuk alasan
Keadaan permainan di mana tidak ada cara logis untuk maju - pemain hanya dapat memilih secara kebetulan, mungkin dengan mempertimbangkan probabilitas.

Situasi 1 terlihat indah, tetapi tidak terlalu menarik jika muncul terlalu sering. Akankah game seperti itu lebih baik tanpa solusi otomatis? Mungkin tidak; permainan seperti itu sangat sederhana bahkan ketika diselesaikan secara manual, dan pemain tidak terlalu tertarik bermain game di mana tidak ada kesulitan. Meskipun, tentu saja, selalu ada kesulitan dalam permainan reaksi: Anda harus bertindak secepat mungkin.

Situasi 2 tampaknya sangat menarik bagi saya, kami lebih fokus pada penyelesaian kondisi logis, menghabiskan lebih sedikit waktu untuk membidik dengan tepat dan menekan tombol yang tepat. Ini membuat Sapper lebih seperti puzzle aktif .

Situasi 3 sepenuhnya menghancurkan semua kesenangan. Namun, saya mendengar bahwa beberapa orang suka bermain game dengan keacakan .

Apakah mungkin untuk menyingkirkan situasi 3?

Solusi Lengkap: Penalaran Global

Untuk deteksi algoritmik dari semua kondisi logis yang diperlukan untuk kondisi permainan, kita perlu melakukan pencarian lengkap untuk semua kondisi permainan. Minesweeper terbukti menjadi tugas NP-complete . Di bawah ini adalah contoh kecil tapi menarik dan ilustratif dari keadaan permainan, hanya memiliki satu solusi logis, tetapi untuk menemukannya Anda harus memperhitungkan keadaan permainan secara keseluruhan:

Apakah mungkin untuk mencari seluruh ruang keadaan game? Berapa banyak variasi keadaan s yang ada?

Diberikan:

w = lebar bidang

h = tinggi bidang

k = jumlah menit

n = w

Maka jumlah kemungkinan status s adalah

s = b e g i n p m a t r i x n k e n d p m a t r i x

$s = \ begin {pmatrix} n \\ k \ end {pmatrix}$

Untuk level standar "Pemula", "Amatir" dan "Profesional" ini memberi kita:

s_{b} = b e g i n p m a t r i x 8 * 8 10 e n d p m a t r i x = 151473214816

$s_b = \ begin {pmatrix} 8 * 8 \\ 10 \ end {pmatrix} = 151473214816$

s_{i} = b e g i n p m a t r i x 16 * 16 40 e n d p m a t r i x = 1.050 * 10^{47}

$s_i = \ begin {pmatrix} 16 * 16 \\ 40 \ end {pmatrix} = 1.050 * 10 ^ {47}$

s_{e} = b e g i n p m a t r i x 30 * 16 99 e n d p m a t r i x = 5.602 * 10^{104}

$s_e = \ begin {pmatrix} 30 * 16 \\ 99 \ end {pmatrix} = 5.602 * 10 ^ {104}$

Kami memahami bahwa pendekatan naif sepenuhnya tidak pantas di sini. Mari kita lihat bagaimana algoritma naif mungkin terlihat dan mencari tahu apakah itu dapat dioptimalkan menjadi sesuatu yang berfungsi.

Algoritma naif

Tugas algoritma adalah untuk menemukan semua kondisi logis yang diperlukan untuk keadaan lapangan yang diberikan. Akan sulit untuk mengimplementasikan ini dengan mempertimbangkan solusi secara hati-hati; komputer melakukan pekerjaan yang jauh lebih baik dengan cepat melakukan banyak tindakan bodoh.

Apa yang bisa kita lakukan "bodoh": menghasilkan semua kemungkinan permutasi posisi tambang untuk semua tambang yang tersisa. Jika permutasi seperti itu sesuai dengan semua angka terbuka, maka itu akan menjadi solusi yang tepat untuk gim. Kemudian kami mempelajari semua permutasi yang mungkin, menemukan semua solusi yang mungkin, tetapi masih tidak tahu mana yang benar.

Jika dalam semua solusi yang mungkin ada sesuatu yang sama, baik di antara sel terbuka, atau di antara sel yang ditandai sebagai ranjau, maka kami memahami bahwa kesamaan ini harus menjadi bagian dari keputusan yang tepat untuk bidang saat ini. Dan pada kenyataannya: tidak mungkin untuk membuat solusi yang tepat yang tidak memiliki elemen yang cocok, jika tidak kita akan menemukannya.

Dengan demikian, kita dapat menemukan semua kondisi logis yang diperlukan untuk kondisi lapangan saat ini.

Sel dengan dan tanpa batasan

Algoritme di atas memiliki masalah yang jelas: jumlah negara yang perlu diselidiki. Tetapi tidak semua sel itu sama. Sel yang belum dibuka di sebelah angka jelas terbatas pada angka itu. Kami akan menyebut sel-sel ini terbatas. Sel yang tersisa akan kita sebut tidak terbatas.

Jika kami menerapkan algoritme di atas, tetapi kami hanya akan mencari di ruang keadaan sel terbatas, dan kami akan kembali segera setelah kami melanggar batasan, maka di banyak permainan kami dapat menyelesaikan semua kondisi logis dalam jumlah waktu yang wajar:

Dalam kasus sel yang tidak terbatas, kami tidak dapat menemukan di mana tambang berada, dan secara logis kami segera mengetahuinya. Ini berarti Anda dapat mengecualikan mereka dari perhitungan dan hanya mempertimbangkan lokasi tambang di sebelah angka terbuka.

Namun, kita tahu bahwa sejumlah tambang dapat memasuki banyak sel tanpa batas; jika ada 6 menit dan 4 sel terbatas, maka dalam sel terbatas bisa ada maksimum 4 tambang, yaitu, setidaknya 2 menit harus dalam sel tak terbatas. Dengan logika yang sama, kadang-kadang kita dapat menentukan bahwa semua sel tak terbatas harus kosong atau semua mengandung ranjau.

Dalam kasus yang ditunjukkan di bawah ini, kita mengetahui posisi semua tambang, sehingga AI harus dapat memahami bahwa sel-sel yang tersisa tidak ditempati:

Dalam kasus berikut, kami tidak tahu posisi semua tambang, tetapi kami dapat memahami bahwa sisa tambang harus ditempatkan di salah satu dari dua sel di kiri atas. Ini berarti bahwa sel yang tersisa di sudut kanan bawah gratis:

Versi acak

Jika kami menjalankan pemecah global secara otomatis, kami akan mendapatkan versi Minesweeper yang dioptimalkan secara acak:

Anda dapat membagi game dalam versi ini menjadi tiga kategori:

Game di mana pemain membuat pilihan dan menang secara sewenang-wenang.
Game di mana pemain membuat pilihan sewenang-wenang dan kalah.
Game di mana AI membutuhkan banyak waktu, dan pemain benar-benar dapat menggunakan penalaran.

Jelas, ini adalah permainan kebetulan. Apa daya tarik dari game semacam itu? Dalam hal logika, permainan yang ditunjukkan di atas mirip dengan ini:

Tapi game acak mana yang lebih baik? Tampaknya makna permainan lain dengan keacakan terletak pada keberadaan hubungan yang kompleks antara tindakan pemain dan menang / kalah. Untuk menggambar nomor lotre, mesin kompleks digunakan yang tidak terburu-buru untuk memilih nomor dan membuat seluruh menunjukkan nomor ini.

Mungkin bidang besar yang diputuskan secara otomatis adalah permainan yang cukup bagus
dengan keacakan, mengingat bahwa pemain menonton pembukaan semua sel secara bertahap.

Bisakah kita menghasilkan jenis permainan yang berbeda?

Versi deterministik

Sekarang kami memiliki AI yang mampu menentukan semua langkah logis dari kondisi permainan tertentu. Terkadang dia tidak akan bisa menemukan langkah logis. Dalam situasi seperti itu, pemain harus menebak dan dia bisa kalah jika dia tidak beruntung.

Bagaimana jika kita menambahkan aturan lain? Ketika permainan tidak memiliki jalan logis ke depan, maka kita dapat meminta bantuan. Jika AI setuju bahwa pemain tidak dapat melakukan apa-apa, maka ia datang membantu. Jika tidak, pemain akan langsung kalah. Ini mungkin menarik. Bantuan macam apa ini? Mungkin Anda perlu membuka satu sel, terlepas dari keberadaan ranjau di dalamnya:

Jadi, kami benar-benar menyingkirkan situasi di mana seseorang bisa kehilangan secara kebetulan.

Namun, ada satu pengecualian: masih ada kemungkinan situasi yang memburuk di mana pemecah global tidak dapat menyelesaikan perhitungan dalam jumlah waktu yang wajar. Sayangnya, ini adalah hasil yang tak terelakkan bahwa tugas Minesweeper NP-complete.

Bagaimana tombol "Minta Bantuan" memengaruhi gameplay? Ini mengarah pada fakta bahwa game lebih berfokus pada logika; Ini adalah versi "Minesweeper" yang paling "membingungkan". Seseorang mungkin berpikir bahwa permainan akan menjadi lebih mudah, tetapi pada kenyataannya itu menjadi lebih rumit. Sekarang tidak ada alasan untuk kesalahan pemain, dan tombol akan menghukumnya jika dia melewatkan sesuatu. Tanpa tombol, mudah untuk menyimpulkan bahwa Anda telah kehabisan semua kemungkinan logis dan satu-satunya pilihan untuk pengembangan acara adalah mencoba menebak secara acak. Tetapi karena keberadaan tombol, pemain harus benar dalam penilaian ini.

Kesimpulannya

Setelah menerapkan solver penuh "Minesweeper", kami dapat membuat variasi permainan, bebas dari kutukannya: sekarang tidak mungkin untuk kalah karena kenyataan bahwa Anda harus memilih secara kebetulan ketika Anda hampir memutuskan seluruh bidang. Versi ini berbeda dari game asli hanya pada saat-saat ketika Anda perlu menebak secara acak, jadi saya bisa berasumsi bahwa itu jauh lebih menyenangkan daripada game aslinya.

Selain itu, kami mengembangkan versi game yang secara otomatis memecahkan aturan lokal yang sederhana. Apakah menggunakan bantuan itu terserah Anda. Ini menggeser fokus permainan dari mengklik mekanis ke gameplay yang lebih membingungkan. Pada saat yang sama, tidak perlu menggunakan peningkatan gameplay yang disediakan oleh tombol "Minta Bantuan".

Cara mengatasi "Minesweeper" (dan membuatnya lebih baik)