Get best of the week

Kaboom: pencari ranjau yang tidak biasa



Sebagai seorang anak, saya duduk di tempat kerja ayah saya tiga kali seminggu selama satu setengah jam. Saya diizinkan pergi ke komputer, di mana dari hiburan hanya ada ranjau dan Paint. Saya bosan menggambar dengan cepat, tetapi keinginan untuk membuka seluruh bidang dan tidak meledak memotivasi saya untuk mencari cara baru dan baru untuk memainkan permainan ini. Bertahun-tahun kemudian, saya tidak sengaja menemukan artikel menarik tentang klon pencari ranjau, dan tidak bisa lewat. Saya sarankan agar Anda membiasakan diri dengannya. Ini adalah kisah tentang pengembangan Kaboom, tiruan dari game Minesweeper yang legendaris dengan semangatnya sendiri.

Minesweeper muncul cukup lama dengan standar permainan komputer. Tapi menurut saya kebanyakan orang mengingat gim yang merupakan bagian dari versi Windows sebelumnya. Saya tidak pernah bagus di Minesweeper, tetapi saya memainkannya dari waktu ke waktu. Beberapa orang bermain lebih serius . Dan bagi mereka yang ingin menghibur diri sendiri, saya sarankan menonton Minesweeper - The Movie .

Ide


Baru-baru ini, saya punya ide: bagaimana jika Anda harus bermain Minesweeper melawan komputer yang lebih bijaksana?

Biasanya, lokasi ranjau ditentukan pada awal permainan (tetapi ada beberapa trik di sini - misalnya, sehingga Anda tidak dapat kehilangan klik pertama). Tetapi bagaimana jika lokasi tambang tidak ditentukan sebelumnya dan permainan dapat memilih lokasi tambang setelah dimulainya permainan?

Itu akan sangat kejam: jika Anda mengklik kotak yang mungkin berisi tambang, itu akan selalu berisi itu! Jadi, Anda harus membuktikan sebelumnya bahwa alun-alun itu aman.


Pada gambar di atas, dalam sel yang ditandai dengan titik, dijamin tidak ada ranjau, dan sel yang ditandai dengan tanda seru dijamin mengandung satu. Tanda tanya berarti ketidakpastian: mungkin jika Anda membuka lebih banyak sel, Anda dapat menghitung apakah tambang disembunyikan di sana atau tidak.

Di sisi lain, ada situasi ketika Anda harus menebak:



Ada tambang di salah satu sel yang lebih rendah. Tetapi di mana, itu tidak mungkin untuk dipahami. Anda harus memilih salah satunya. Tetapi menurut kondisi yang baru saja saya bicarakan, ini berarti kematian! Saya ingin permainan menjadi brutal, tetapi sekarang jelas kalah.
Karena itu, saya akan sedikit mengubah idenya. Anda bisa menebak, tetapi hanya jika tidak ada sel aman yang tersisa. Dengan demikian, permainannya akan kejam, tapi adil.

Dengan kata lain:

  • , .
  • , , .
  • , :

    1. , , .
    2. , , .


Bagaimana cara mengimplementasikan game seperti itu? Saya bisa mencoba menghitung semua bidang yang mungkin, tetapi ini tidak realistis: bahkan bidang 10x10 kecil berarti 2 ^ 100 kemungkinan. Memilih hanya yang berisi persis N min tidak membantu.

Untungnya, saya tidak perlu khawatir tentang seluruh bidang. Kami tidak tahu apa-apa tentang ranjau darat yang tidak berdekatan dengan tag. Saya hanya tertarik pada mereka yang ada di perbatasan, sisanya dapat ditentukan secara tidak sengaja.



Lalu saya bisa menghitung semua opsi untuk lokasi tambang di perbatasan sesuai dengan label. Backtracking (backtracking) - teknik yang bagus yang memungkinkan Anda untuk memilah-milah semua kombinasi, tetapi juga cepat mundur segera setelah kami menentukan bahwa cabang tidak dapat menghitung.


Dua kemungkinan lokasi tambang di perbatasan ditunjukkan di atas. Menggabungkannya, kita akan memahami sel mana yang dijamin kosong atau ditambang.

Saya juga perlu melacak jumlah total tambang. Dengan demikian, lokasi tersebut benar-benar terlihat seperti "5 menit di perbatasan, 5 menit di luar". Ini penting karena kalau tidak, saya bisa membuat terlalu banyak ranjau di perbatasan (atau terlalu sedikit!)

Jadi, saya memiliki semua opsi. Apa yang terjadi ketika seorang pemain memutuskan untuk membuka kandang?

  • Pilih opsi acak (yang memenuhi aturan "kejam tapi adil"). Ini akan menentukan lokasi ranjau di perbatasan.
  • Secara acak menyebar yang tersisa di luar perbatasan.
  • Jika ada tambang di sel yang dipilih, permainan sudah berakhir.
  • Jika tidak:

    1. Tetapkan label baru untuk sel yang diidentifikasi
    2. Buka sel tambahan jika 0
    3. , ! .


Untuk bidang kecil ini normal. Biasanya hanya ada beberapa kemungkinan kombinasi ... tunggu, ada apa?



Oh tidak!



Entah bagaimana, saya berhasil membuka 18 juta kemungkinan lokasi tambang. Firefox saya menghabiskan 12 gigabytes memori, dan membuka sel membutuhkan waktu setengah menit. Jelas, saya butuh algoritma yang lebih baik.

Seseorang mungkin memperhatikan bahwa Minesweeper adalah permainan NP-lengkap , dan karenanya waktu yang meningkat secara eksponensial tidak dapat dihindari. Dan dalam kasus umum, ini benar - akan ada posisi yang akan membutuhkan banyak waktu untuk menghitung. Tetapi untuk area kecil ini berfungsi.

Saya tidak perlu mengingat semua kombinasi. Saya bahkan tidak perlu menghitung semua kombinasi. Semua yang diperlukan adalah caranya:

  • periksa apakah sel itu aman, berbahaya atau tidak jelas,
  • (, , ).


Alih-alih mencoba opsi sendiri, saya akan menggunakan pemecah SAT . Ini adalah alat yang mengambil rumus yang terdiri dari variabel logis dan mencari satu set nilai yang akan membuat rumus itu benar. Metode imajiner, tetapi cukup valid untuk tugas kita.

Kelas yang lebih kuat dari perangkat lunak adalah pemecah SMT yang bekerja dengan rentang nilai dan formula yang lebih luas, seperti logika tingkat pertama (pembilang), array, bilangan bulat, dan sebagainya. Ini akan membantu setidaknya mendefinisikan beberapa persamaan untuk bilangan bulat. Tapi saya butuh sesuatu yang berfungsi di browser. Orang-orang berhasil melakukan porting beberapa alat canggih seperti Z3Prover ke browser, tetapi versi WebAssembly berbobot17 MB , dan itu terlalu banyak.

Saya menemukan MiniSat , pemecah SAT kecil yang dikompilasi untuk Javascript oleh Joel Galenson. File yang dikompilasi hanya membutuhkan 200 kilobyte, jadi saya menggunakannya.

Formula CNF


Pemecah SAT bekerja dengan rumus normal konjungtif ( CNF ). Rumus CNF adalah "AND DAN OR", misalnya:

(a | ~ b | ~ c) & (c | d ~ e) & f

Anda dapat mengonversi rumus logika kalimat apa pun (variabel, dan, atau, tidak, implikasi) menjadi CNF, jadi itu semacam format universal.

bagaimana kami menggunakannya? Misalkan kita memiliki papan: Jika saya membuat variabel untuk sel yang tidak diketahui (searah jarum jam: x1, x2, x3), mereka harus memenuhi persamaan berikut: Tapi bagaimana cara mengekspresikan "jumlah variabel adalah 2" di CNF? Saya menemukan metode yang, seperti yang kemudian saya pelajari, disebut "kode binomial" dan merupakan kode yang paling sederhana. Anda harus mempertimbangkan semua subset variabel yang mungkin. Misalnya, untuk Anda memerlukan rumus berikut:

? ? 1
2 ? 1



1 + 2 + 3 = 2
2 + 3 = 1
2 + 3 = 1 ( )



x1 + x2 + x3 = 2

  • Untuk setiap subset dari 2 variabel, setidaknya satu adalah benar. Ini memastikan bahwa jumlahnya lebih besar dari 1.
    (x1 | x2) & (x1 | x3) & (x2 | x3)
  • Setidaknya satu variabel salah. Ini memastikan bahwa jumlahnya kurang dari 3.
    (~ x1 | ~ x2 | ~ x3)


Bagi x2 + x3 = 1saya, saya memerlukan satu set rumus yang serupa:
  • Setidaknya satu variabel benar: (x2 | x3)
  • Paling tidak salah satu variabelnya salah (~ x2 | ~ x3).

Dengan menggabungkan ini, saya mendapatkan formula CNF dengan 6 poin. Dalam format DIMACS standar: Semua garis posisi diakhiri dengan 0, dan negasi ditandai dengan minus. Jika saya menghubungkannya ke MiniSat (coba sendiri), saya mendapatkan: Ini berarti bahwa MiniSat menemukan solusi di mana x1 dan x2 benar dan x3 salah. Beginilah tampilan dewan: Seluruh program sedikit lebih rumit: ini hanya satu solusi, ada yang lain. Oleh karena itu, untuk mengetahui apakah x1, x2, x3 dapat benar (atau salah), Anda perlu membuat lebih banyak permintaan. Saya perlu bertanya: β€œDengan rumus di atas, dan juga x1, apakah ini layak? Bagaimana dengan rumus di atas, dan juga ~ x1 "?

p cnf 3 6
1 2 0
1 3 0
2 3 0
-1 -2 -3 0
2 3 0
-2 -3 0



SAT 1 2 -3



! ! 1
2 . 1



Pengkodean berarti bahwa saya perlu menemukan semua kombinasi yang mungkin (misalnya, semua himpunan bagian dari 3) dari satu set variabel. Namun, untuk persamaan ini hanya akan ada hingga 8 variabel, jadi rumusnya biasanya cukup kecil sehingga MiniSat dapat dengan cepat menyelesaikannya.

Pelacakan min


Sayangnya, ini bukan solusi lengkap! Saya masih perlu melacak berapa banyak ranjau yang tersisa. Beberapa kombinasi tidak mungkin, karena jika tidak, Anda dapat membuat lebih banyak ranjau dari yang diizinkan, dan tidak mungkin menang.



Bahkan, kasus sebaliknya juga mungkin terjadi: jika ada terlalu sedikit ranjau, permainan akan berakhir, karena tidak akan ada yang terjadi.

Oleh karena itu, saya perlu menunjukkan dalam rumus SAT bahwa "jumlah tambang tidak kurang dari X dan tidak lebih dari Y". Awalnya saya pikir saya bisa menggunakan trik dengan semua kombinasi. Sayangnya, itu tidak bekerja dengan baik dengan jumlah besar. Jika ada, katakanlah, 20 sel dan 10 menit, kemudian setelah menghubungkan angka ke koefisien binomial, kami mengetahui bahwa jumlah kombinasi sudah 6 digit!

Jadi saya menemukan bahwa ada banyak cara lain untuk menyandikan jumlah variabel ke dalam rumus SAT. Anda perlu membuat skema yang akan menggabungkan variabel individu. Lihat, misalnya, jawaban ini di StackExchange atau yang ini .

Sebagai hasilnya, saya menyadari ide dari sebuah artikel berjudul "Pengkodean CNF yang Efektif dengan Kendala Kardinalitas Boolean", yang ditulis oleh Olivier Bayot dan Yasin Bufhad. Kami melihat pohon yang secara rekursif menambahkan angka-angka yang tidak diketahui (atau mengurutkan bit sehingga setiap orang di awal):



Pada akhir diagram ini, Anda akan mendapatkan seperangkat variabel "output" yang diurutkan. Untuk mengonfirmasi bahwa jumlah tidak kurang dari X, periksa bahwa X pertama dari variabel yang dihasilkan adalah 1. Untuk mengklaim bahwa jumlah tidak lebih dari Y, periksa bahwa N - Y terakhir dari variabel yang dihasilkan adalah 0.

Ini jauh lebih baik daripada menggunakan semua kombinasi yang mungkin, Namun, skema ini masih tidak rasional karena menghasilkan kalimat Σ¨ (N ^ 2). Saat jumlah sel terbuka sekitar 100, gim menjadi lamban. Kami dapat mengoptimalkan game lebih lanjut.
Kurangi Permintaan

Saat mempelajari masalah ini, saya perhatikan bahwa saya dapat mengurangi jumlah pertanyaan ke pemecah. Saya ingin menentukan status semua sel (yaitu, untuk memeriksa apakah mereka dijamin berbahaya, aman atau tidak). Saya melakukan ini menggunakan loop sederhana. Katakanlah papan dijelaskan oleh rumus F:

  • Putuskan untuk F & ~ x1memeriksa apakah x1 bisa 0
  • Putuskan untuk F & x1memeriksa apakah x1 bisa 1
  • Putuskan untuk F & ~ x2 memeriksa apakah x2 bisa 0
  • Putuskan untuk F & x2memeriksa apakah x2 bisa 1
  • Dll

Apa yang saya perhatikan? Jika saya mendapatkan solusi untuk F & ~ x1, itu juga akan berisi nilai-nilai semua variabel lain. Ini sudah menjawab banyak pertanyaan lain: jika solusinya berisi x2 = 0, saya tidak perlu bertanya apakah x2 bisa 0, karena saya sudah tahu ini. Ini memungkinkan saya untuk mengurangi jumlah permintaan sekitar 2-5 kali.

Caching


Ini tidak memecahkan masalah rumus besar yang dihasilkan oleh sirkuit "penghitungan". Seperti yang saya katakan, jumlah kalimat berada di urutan N ^ 2. Pada papan besar, rumus bisa hingga 10.000 asumsi.

Untungnya, sebagian besar waktu kita tahu arti sebenarnya dari banyak sel. Jika sel dijamin kosong atau dijamin diisi, nilainya tidak akan pernah berubah! Ini berarti bahwa kami dapat menyimpannya dan tidak memasukkannya ke dalam rumus SAT. Setelah kami menentukan keadaan sel, kami tidak perlu lagi memasukkannya ke dalam perhitungan lagi. Sel akan digunakan selama tidak terdefinisi.

Optimalisasi ini sedikit berbahaya: kami tidak lagi memiliki formula yang mengkonfirmasi kebenaran seluruh papan. Jika semuanya berjalan sesuai rencana, ini bukan masalah, tetapi bisa mempersulit pelacakan kesalahan.

Kasus lain: bermain di luar negeri


Apakah Anda diizinkan mengeklik di mana saja pada peta di luar perbatasan antara bidang yang terbuka dan yang belum dibuka?

Awalnya, saya pikir itu sama dengan menebak: jika tidak ada sel aman, Anda cukup mengklik di mana saja di lapangan. Tetapi beberapa orang merasa aneh bahwa ini menjamin pembukaan kandang kosong.

Karena itu, saya mengubah permainan sehingga klik di luar perbatasan selalu dihukum. Dengan pengecualian pada permulaan permainan, tentu saja, karena dengan demikian seluruh papan adalah "di luar".

Tapi ternyata ada skenario lain: bagaimana jika semua bidang perbatasan mematikan? Anda tidak punya pilihan selain mengungkapkan sesuatu yang lain. Situasi ini dapat membuat game tidak bisa dilewati sejak awal. Jadi sekarang ada satu pengecualian lagi. Anda diizinkan bermain di luar perbatasan jika:

3 . .
. . .
. . .



  • Bidang tidak terbuka
  • Sel yang ditambang mungkin terletak di perbatasan (mengklik di luar harus aman), atau
  • Harus ada bom di semua sel di perbatasan (Anda harus mengklik di luar).

Pembaruan : Perubahan itu ternyata kontroversial, karena batasannya agak buatan. Saya menambahkan saklar yang akan memungkinkan / melarang bermain dengan kondisi ini.

Itu semua


Anda dapat memainkan Kaboom di sini . Coba aktifkan mode debugging: itu membuat game sepele, tetapi itu menunjukkan dengan baik cara kerjanya.

Kode sumber Github . Dia tidak terlalu tampan.

Anda mungkin juga tertarik dengan game serupa dari Simon Tatham, pencipta PuTTY. Versi ini memiliki twist yang berbeda: selalu dapat dipecahkan tanpa spekulasi.

Mainkan dengan bijak!

Apa lagi yang bisa berguna untuk dibaca di blog Cloud4Y

β†’ Bagaimana bank β€œrusak”
β†’ Privasi pribadi? Tidak, mereka tidak mendengar
β†’ Teori Besar Kepingan Salju
β†’ Diagnostik koneksi jaringan pada router EDGE virtual
β†’Virus yang resistan terhadap CRISPR membangun tempat perlindungan untuk melindungi genom dari enzim penembus DNA.

Berlangganan ke saluran Telegram kami agar Anda tidak ketinggalan artikel lain! Kami menulis tidak lebih dari dua kali seminggu dan hanya untuk bisnis. Kami mengingatkan Anda bahwa startup bisa mendapatkan 1 juta rubel. dari Cloud4Y. Syarat dan ketentuan untuk mereka yang ingin - di situs web kami: bit.ly/2sj6dPK

Source: https://habr.com/ru/post/undefined/

More articles:


All Articles