Algoritma Kebolehselesaian Mahjong: Cara Ia Berfungsi

Algoritma kebolehselesaian mahjong ialah prosedur keputusan yang menentukan sama ada papan Mahjong solitaire yang diberikan boleh dibersihkan sepenuhnya dengan memadankan dan membuang pasangan jubin secara berurutan mengikut peraturan permainan. Memahami apa maksud algoritma kebolehselesaian mahjong bermakna berdepan dengan salah satu masalah yang lebih menarik dalam teori permainan kombinatorial: soalan ini secara formal NP-lengkap di bawah maklumat sempurna, yang bermaksud tiada algoritma yang diketahui dapat menyelesaikannya dengan cekap untuk semua konfigurasi papan yang mungkin. Perisian sebenar mengatasi halangan ini melalui heuristik, gelung cuba semula, dan strategi sandaran. Jurang antara kesukaran teori dan kebolehmainan praktikal ialah tempat kejuruteraan yang paling berguna berlaku.

Apakah yang diberitahu oleh kerumitan pengiraan tentang kebolehselesaian mahjong?

Kerumitan pengiraan ialah kajian formal tentang betapa sukarnya sesuatu masalah untuk diselesaikan oleh komputer. Dua kelas kerumitan paling penting di sini: NP dan PSPACE.

NP-lengkap menerangkan masalah yang pengesahan penyelesaiannya pantas, tetapi pencariannya mungkin memerlukan masa eksponen. Mahjong solitaire dengan maklumat sempurna ialah NP-lengkap bagi masalah keputusan: jika semua kedudukan jubin diketahui, bolehkah semua jubin dibuang? Hasil ini bermakna tiada algoritma yang dijamin dapat menjawab soalan itu dengan cepat untuk setiap susun atur yang mungkin.

PSPACE-lengkap ialah kelas yang lebih sukar lagi. Memaksimumkan kebarangkalian penyingkiran ialah PSPACE-lengkap dan PSPACE-sukar untuk dianggarkan dalam faktor n yang dinaikkan kepada sebarang pemalar positif. Hasil ini menolak kewujudan penyelesaian anggaran yang berjalan dalam masa polinomial kecuali andaian asas teori kerumitan runtuh.

Inilah maksud dua hasil ini dalam amalan:

• Versi keputusan (bolehkah papan ini dibersihkan?) ialah NP-lengkap. Penyelesai tepat berdepan masa eksponen dalam kes terburuk.
• Versi pengoptimuman (urutan mana yang memaksimumkan kebarangkalian pembersihan?) ialah PSPACE-lengkap. Ia jauh lebih sukar daripada versi keputusan.
• Pemeriksaan kebolehselesaian tepat memerlukan pengiraan eksponen atau intensif ruang dalam kes terburuk. Penyelesai praktikal bergantung pada heuristik atau sekatan susun atur.
• Kebolehselesaian bergantung pada formulasi masalah dan model permainan. Tiada algoritma universal sesuai untuk semua varian Mahjong.

Pengajaran utama daripada teori kerumitan bukanlah bahawa Mahjong tidak boleh diselesaikan. Ia ialah bahawa menyelesaikannya secara tepat untuk papan sewenang-wenangnya cukup mahal dari segi pengiraan sehingga tiada enjin permainan pengeluaran cuba melakukannya secara langsung.

Perbezaan ini membentuk setiap keputusan reka bentuk dalam perisian Mahjong. Pembangun tidak menunggu jawapan yang terbukti betul. Mereka membina sistem yang menghasilkan papan yang boleh diselesaikan dengan kebarangkalian tinggi, kemudian mengesahkan bukannya membuktikan.

Bagaimanakah kebolehselesaian dimodelkan, dan mengapa letupan kombinatorial penting?

Struktur matematik Mahjong solitaire berpusat pada pemadanan jubin. Setiap jubin tergolong dalam salah satu daripada 36 kategori, dan setiap kategori mengandungi tepat empat jubin. Untuk membersihkan papan, setiap jubin mesti dipadankan dengan salah satu daripada tiga jubin sejenis yang lain.

Inilah cabaran kombinatorial teras, langkah demi langkah:

1. Kira pilihan pemadanan. Bagi mana-mana kumpulan empat jubin yang sama, terdapat tepat tiga cara untuk memasangkannya menjadi dua pasangan sepadan.
2. Darab merentasi semua kategori. Dengan 36 kategori dan 3 pilihan setiap satu, jumlah konfigurasi pemadanan ialah 3^36, kira-kira 1.5 × 10^17. Itu kira-kira 150 kuadrilion kombinasi.
3. Kenal pasti kemustahilan carian menyeluruh. Memeriksa setiap konfigurasi walaupun pada satu bilion operasi sesaat akan mengambil lebih empat tahun pengiraan berterusan. Tiada enjin permainan mampu menanggung kos itu bagi setiap papan.
4. Pisahkan pemadanan daripada urutan gerakan. Urutan penyingkiran tidak mempengaruhi hasil kebolehselesaian akhir setelah pemadanan ditetapkan. Ini ialah wawasan kritikal. Ia bermakna ruang carian ditentukan oleh pilihan pemadanan, bukan oleh urutan gerakan.
5. Fokuskan carian pada corak pemadanan. Pengurangan ruang keadaan dengan merumus semula permainan sebagai masalah kebergantungan pemadanan dan penyingkiran mengurangkan kerumitan. Ruang itu masih besar, tetapi jauh lebih mudah dikendalikan berbanding menjejak setiap urutan gerakan yang mungkin.
6. Gunakan pramampatan. Penyelesai yang berkesan menumpukan pada jubin yang boleh dicapai berdasarkan susun atur papan semasa, sambil memangkas cabang yang jubinnya terhalang sehingga pemadanan menjadi mustahil secara fizikal tanpa mengira pilihan pemadanan abstrak.

Petua Pro: Apabila menganalisis papan Mahjong secara manual, fikir dalam istilah komitmen pemadanan, bukannya gerakan individu. Kenal pasti jubin yang hanya mempunyai satu pasangan sah yang boleh dicapai, dan kunci pemadanan itu terlebih dahulu. Ini mencerminkan cara penyelesai algoritma memangkas pokok carian.

Letupan kombinatorial menjadikan carian menyeluruh tidak praktikal. Realiti ini memaksa setiap pelaksanaan praktikal ke arah heuristik dan strategi cuba semula secara rawak, bukannya enumerasi lengkap. Memahami kekangan ini ialah asas algoritma mahjong yang dijelaskan dalam mana-mana konteks perisian yang serius.

Bagaimanakah pelaksanaan sebenar menjana papan mahjong yang boleh diselesaikan?

Perisian Mahjong pengeluaran tidak cuba membuktikan kebolehselesaian dari prinsip pertama. Ia mengesahkan kebolehselesaian melalui sistem dua lapisan yang menggabungkan pembinaan papan pantas dengan penyelesai yang menyemak hasilnya.

Seni bina standard berfungsi seperti berikut:

• Lapisan 1: Penjanaan konstruktif. Enjin membina papan menggunakan kaedah yang direka untuk menghasilkan susun atur yang boleh diselesaikan. Ini pantas tetapi tidak dijamin berjaya setiap kali.
• Lapisan 2: Pengesahan kebolehselesaian. Penyelesai dijalankan pada papan yang dijana. Jika papan gagal semakan, enjin akan cuba semula.
• Gelung cuba semula. Pelaksanaan biasa menjalankan buildSolvableWithRetries sehingga 2,000 percubaan sebelum bertukar strategi. Nombor itu mencerminkan penalaan empirikal, bukan keperluan teori.
• Strategi alternatif. Selepas habis bajet cuba semula utama, enjin bertukar kepada algoritma pembinaan lain dengan gelung cuba semula tersendiri.
• Sandaran papan rawak. Jika semuanya gagal, enjin menjana papan rawak dan menjalankan semakan penyelesaian secara terus. Ini menjamin papan yang boleh dimainkan sentiasa dihantar.

Petua Pro: Jika anda membina penjana teka-teki Mahjong, mulakan dengan pendekatan pembinaan songsang: letakkan jubin dalam urutan yang diketahui boleh diselesaikan, kemudian rawakkan dalam batasan tertentu. Ini mengurangkan dengan ketara bilangan cuba semula yang diperlukan sebelum menemui papan yang sah.

Jadual di bawah meringkaskan corak sandaran tiga peringkat yang digunakan dalam pangkalan kod pengeluaran:

Sistem dua lapisan dengan cuba semula berulang dan strategi sandaran ini ialah standard pengeluaran untuk menghantar papan teka-teki yang boleh diselesaikan. Mindset kejuruteraan di sini memang disengajakan: jangan buktikan kebolehselesaian terlebih dahulu. Bina dengan pantas, sahkan dengan cepat, dan cuba semula apabila perlu. Pendekatan itu selaras dengan apa yang diramalkan oleh teori kerumitan. Bukti tepat mahal. Pengesahan murah.

Bagaimanakah pengetahuan kebolehselesaian meningkatkan strategi dan reka bentuk permainan mahjong?

Memahami cara kebolehselesaian berfungsi mengubah cara pembangun membina permainan dan cara pemain mendekati penyelesaian teka-teki mahjong. Dua perspektif ini saling menguatkan.

Dari sudut strategi pemain, wawasan kebolehselesaian diterjemahkan terus kepada pembuatan keputusan yang lebih baik:

• Utamakan jubin yang terdedah dengan pasangan terhad. Jika sesuatu jubin hanya mempunyai satu padanan yang boleh dicapai, padanan itu mesti dibuat pada satu ketika. Menangguhkannya berisiko menyekat papan.
• Elakkan mengasingkan kumpulan jubin. Membuang jubin yang tidak mendedahkan jubin baharu mengurangkan pilihan masa depan anda tanpa memperbaiki kedudukan anda. Konsep ini diteroka secara mendalam dalam konteks pengasingan jubin dan mengapa ia menjejaskan kebolehselesaian.
• Fikir dalam lapisan, bukan gerakan individu. Kebolehselesaian bergantung pada komitmen pemadanan merentasi keseluruhan papan. Pemain yang merancang dua atau tiga langkah ke hadapan secara konsisten mengatasi mereka yang hanya bertindak balas terhadap peluang satu jubin.
• Gunakan ciri rawak semula secara strategik. Kebanyakan permainan Mahjong digital menawarkan fungsi rawak semula atau petunjuk. Ciri ini bergantung pada algoritma kebolehselesaian yang sama yang berjalan di latar belakang untuk mengesahkan bahawa laluan sah masih wujud.

Dari sudut reka bentuk permainan, algoritma kebolehselesaian menentukan kualiti pengalaman pemain:

• Susun atur yang dijana tanpa semakan kebolehselesaian kerap menghasilkan papan yang tidak boleh dimenangi. Pemain yang menemuinya akan hilang keyakinan terhadap permainan, bukan terhadap kemahiran mereka sendiri.
• Susunan jubin secara langsung mempengaruhi kesukaran. Reka bentuk yang mendedahkan lebih sedikit jubin pada awal memaksa pemain ke dalam pokok keputusan yang lebih sempit, sekali gus meningkatkan kerumitan efektif untuk menyelesaikan teka-teki mahjong.
• Varian maklumat tersembunyi, di mana muka jubin disembunyikan sehingga dibuka, mengalihkan masalah daripada pembuatan keputusan NP-lengkap kepada penaakulan kebarangkalian. Ini mengubah sifat permainan sepenuhnya.
• Pembangun yang memahami algoritma AI mahjong boleh melaras kesukaran dengan menyesuaikan sejauh mana penjana konstruktif mengutamakan susun atur dengan berbilang laluan penyelesaian yang sah.

Hubungan antara teori algoritma dan pengalaman pemain adalah langsung. Papan yang dijana dengan algoritma kebolehselesaian yang mantap memberi anda teka-teki yang adil. Papan yang dijana tanpa algoritma itu mungkin mustahil, dan anda tidak akan tahu mengapa anda gagal.

Pengambilan utama

Algoritma kebolehselesaian mahjong ialah NP-lengkap untuk masalah keputusan dan PSPACE-lengkap untuk pengoptimuman, menjadikan kaedah heuristik dan berasaskan cuba semula satu-satunya laluan praktikal untuk menghasilkan papan yang boleh diselesaikan dalam perisian pengeluaran.

Mengapa teori sahaja tidak akan membantu anda membina permainan mahjong yang lebih baik

Saya telah menghabiskan banyak masa menganalisis bagaimana kebolehselesaian Mahjong dilaksanakan dalam amalan, dan jurang antara hasil kerumitan akademik dan apa yang benar-benar dihantar oleh jurutera amat ketara. Bukti NP-lengkap dan PSPACE-lengkap memang memuaskan dari segi intelektual. Ia memberitahu anda sesuatu yang benar dan penting tentang masalah ini. Tetapi ia tidak memberitahu anda cara membina permainan yang digemari pemain.

Apa yang saya dapati ialah pendekatan berasaskan cuba semula bukanlah kompromi. Ia ialah jawapan yang tepat untuk kelas masalah ini. Apabila ruang carian anda mempunyai 150 kuadrilion konfigurasi, anda tidak perlu meneroka semuanya. Anda memerlukan penjana pantas yang berjaya kebanyakan masa, pengesah murah yang menangkap kegagalan, dan sandaran yang menjamin penghantaran. Seni bina itu lebih boleh dipercayai dalam pengeluaran berbanding mana-mana penyelesai tepat.

Wawasan bahawa urutan gerakan tidak mempengaruhi kebolehselesaian setelah pemadanan ditetapkan ialah hasil yang paling kurang dihargai dalam ruang ini. Ia bermakna anda boleh mengurangkan masalah yang kelihatan berurutan kepada masalah kombinatorial, dan masalah kombinatorial bertindak balas dengan baik terhadap penyebaran kekangan dan pemangkasan. Jika anda membina penyelesai Mahjong atau mengkaji kerumitan permainan teka-teki, mulakan di situ.

Nasihat saya kepada sesiapa yang mahu melaksanakan semakan kebolehselesaian: jangan mulakan dengan literatur kerumitan. Mulakan dengan gelung cuba semula yang berfungsi, instrumentasikannya untuk mengukur kekerapan setiap peringkat sandaran dicetuskan, dan laraskan dari situ. Teori memberitahu anda siling. Pengukuran memberitahu anda kedudukan sebenar anda.

— Dmytro Romaniuk

Main teka-teki mahjong yang dibina atas penjanaan papan yang boleh diselesaikan

Setiap teka-teki di Mahjong Online Club dijana menggunakan pendekatan mengutamakan kebolehselesaian seperti yang diterangkan dalam artikel ini. Tiada papan disajikan kepada anda tanpa melalui langkah pengesahan penyelesai. Ini bermakna setiap permainan yang anda mulakan boleh dimenangi, dan setiap kegagalan ialah masalah strategi, bukan susun atur yang rosak.

Anda boleh bermain Mahjong percuma terus dalam pelayar anda tanpa perlu pendaftaran. Platform ini dibina sekitar pengalaman bebas gangguan yang direka untuk menyokong fokus dan pengecaman corak. Jika anda mahu mempraktikkan konsep algoritma di sini, inilah tempatnya.

Soalan Lazim

Apakah itu algoritma kebolehselesaian mahjong?

Algoritma kebolehselesaian mahjong ialah prosedur pengiraan yang menentukan sama ada papan Mahjong solitaire boleh dibersihkan sepenuhnya dengan memadankan dan membuang semua pasangan jubin. Versi keputusan bagi masalah ini secara formal ialah NP-lengkap di bawah maklumat sempurna.

Bagaimanakah kebolehselesaian mahjong berfungsi secara matematik?

Kebolehselesaian bergantung pada pilihan pemadanan merentasi 36 kategori jubin, setiap satu menawarkan 3 pemadanan yang mungkin, menghasilkan kira-kira 150 kuadrilion konfigurasi keseluruhan. Oleh sebab urutan gerakan tidak mengubah hasil setelah pemadanan ditetapkan, penyelesai menumpukan pada kekangan pemadanan dan bukannya urutan gerakan.

Mengapa perisian tidak boleh menyelesaikan papan mahjong dengan tepat setiap kali?

Pemeriksaan kebolehselesaian tepat memerlukan pengiraan eksponen dalam kes terburuk, yang tidak praktikal untuk enjin permainan masa nyata. Sistem pengeluaran menggunakan penjana konstruktif dengan gelung cuba semula sehingga 2,000 percubaan dan peringkat sandaran untuk menjamin papan yang boleh dimainkan tanpa bukti tepat.

Apakah perbezaan antara np-lengkap dan pspace-lengkap dalam mahjong?

Masalah keputusan (bolehkah papan ini dibersihkan?) ialah NP-lengkap. Masalah pengoptimuman (urutan mana yang memaksimumkan kebarangkalian pembersihan?) ialah PSPACE-lengkap, iaitu kelas yang jauh lebih sukar dan turut menolak kewujudan algoritma anggaran yang cekap.

Bagaimanakah strategi permainan mahjong berkait dengan algoritma kebolehselesaian?

Pemain yang mengutamakan jubin dengan pasangan yang boleh dicapai terhad dan mengelakkan pengasingan kumpulan jubin sedang menggunakan logik pemangkasan kekangan yang sama seperti yang digunakan oleh penyelesai algoritma. Memahami bagaimana kebolehselesaian distrukturkan menjadikan keputusan strategik lebih disengajakan dan kurang bergantung pada tekaan.

Disyorkan

• Cara Bermain Mahjong Solitaire — Peraturan, Jubin & Strategi
• Mengapa Pengasingan Jubin Merosakkan Permainan Mahjong untuk Semua Pemain
• Tipu Mahjong Titans: Penyelesai, Petunjuk, dan Pintasan Sah
• Apakah Matlamat Mahjong? Peraturan dan Strategi