Mahjong sprendžiamumo algoritmas: kaip jis veikia

Mahjong sprendžiamumo algoritmas yra sprendimo procedūra, nustatanti, ar tam tikrą Mahjong solitaire lentą galima visiškai išvalyti nuosekliai poruojant ir šalinant plytelių poras pagal žaidimo taisykles. Suprasti, kas yra Mahjong sprendžiamumo algoritmas, reiškia susidurti su viena įdomiausių kombinatorinių žaidimų teorijos problemų: šis klausimas formaliai yra NP-baigtinis esant pilnai informacijai, o tai reiškia, kad nėra žinomo algoritmo, kuris visiems įmanomiems lentos išdėstymams ją išspręstų efektyviai. Tikroji programinė įranga apeina šią kliūtį naudodama euristikas, kartojimo ciklus ir atsargines strategijas. Būtent tarp teorinio sudėtingumo ir praktinio žaidžiamumo atsiranda naudingiausi inžineriniai sprendimai.

Ką apie Mahjong sprendžiamumą sako skaičiavimo sudėtingumas?

Skaičiavimo sudėtingumas yra formalus tyrimas, kiek sunku kompiuteriui išspręsti tam tikrą problemą. Čia svarbiausios dvi sudėtingumo klasės: NP ir PSPACE.

NP-baigtinis apibūdina problemas, kuriose sprendinį patikrinti greita, tačiau jį rasti gali reikėti eksponentinio laiko. Mahjong solitaire su pilna informacija yra NP-baigtinis sprendimo problemai: turint lentą, kurioje žinomos visų plytelių pozicijos, ar visas plyteles galima pašalinti? Šis rezultatas reiškia, kad nėra algoritmo, kuris garantuotai greitai atsakytų į šį klausimą kiekvienam galimam išdėstymui.

PSPACE-baigtinis yra dar sunkesnė klasė. Pašalinimo tikimybės maksimizavimas yra PSPACE-baigtinis ir PSPACE-sunkus apytiksliai įvertinti iki bet kurio teigiamo laipsnio n koeficiento. Šis rezultatas atmeta net apytikslius sprendimus, veikiančius polinominiu laiku, nebent sugriūtų pamatinės sudėtingumo teorijos prielaidos.

Štai ką šie du rezultatai reiškia praktiškai:

• Sprendimo versija (ar šią lentą galima išvalyti?) yra NP-baigtinė. Tikslūs sprendėjai blogiausiu atveju susiduria su eksponentiniu laiku.
• Optimizavimo versija (kokia seka maksimaliai padidina išvalymo tikimybę?) yra PSPACE-baigtinė. Ji yra dar sunkesnė už sprendimo versiją.
• Tikslus sprendžiamumo tikrinimas reikalauja blogiausiu atveju eksponentinių arba daug atminties reikalaujančių skaičiavimų. Praktiniai sprendėjai vietoj to remiasi euristikomis arba išdėstymo apribojimais.
• Sprendžiamumas priklauso nuo problemos formulavimo ir žaidimo modelio. Nėra universalaus algoritmo, tinkančio visiems Mahjong variantams.

Pagrindinė sudėtingumo teorijos pamoka nėra ta, kad Mahjong neišsprendžiamas. Ji sako, kad jį išspręsti tiksliai bet kuriai lentelei yra skaičiavimo požiūriu taip brangu, kad joks gamybinis žaidimo variklis to nedaro tiesiogiai.

Šis skirtumas lemia kiekvieną Mahjong programinės įrangos dizaino sprendimą. Kūrėjai nelaukia įrodytai teisingo atsakymo. Jie kuria sistemas, kurios su didele tikimybe sugeneruoja išsprendžiamas lentas, o tada patikrina, užuot įrodę.

Kaip modeliuojamas sprendžiamumas ir kodėl svarbus kombinatorinis sprogimas?

Matematinė Mahjong solitaire struktūra sukasi apie plytelių poravimą. Kiekviena plytelė priklauso vienai iš 36 kategorijų, o kiekvienoje kategorijoje yra tiksliai keturios plytelės. Norint išvalyti lentą, kiekviena plytelė turi būti suporuota su viena iš trijų identiškų jos kopijų.

Štai pagrindinis kombinatorinis iššūkis žingsnis po žingsnio:

1. Suskaičiuokite poravimo galimybes. Bet kuriai keturių identiškų plytelių grupei yra tiksliai trys būdai jas suporuoti į dvi poras.
2. Padauginkite per visas kategorijas. Esant 36 kategorijoms ir po 3 galimybes kiekvienai, bendras poravimo konfigūracijų skaičius yra 3^36, maždaug 1,5 × 10^17. Tai yra maždaug 150 kvadrilijonų kombinacijų.
3. Supraskite išsamaus paieškos neįmanomumą. Patikrinti kiekvieną konfigūraciją net ir atliekant milijardą operacijų per sekundę užtruktų daugiau nei ketverius nuolatinio skaičiavimo metus. Joks žaidimo variklis negali sau to leisti kiekvienai lentai.
4. Atskirkite poravimą nuo ėjimų sekos. Pašalinimo tvarka, kai poros jau nustatytos, neturi įtakos galutiniam sprendžiamumo rezultatui. Tai labai svarbi įžvalga. Ji reiškia, kad paieškos erdvę apibrėžia poravimo pasirinkimai, o ne ėjimų seka.
5. Sutelkite paiešką į poravimo modelius. Būsenų erdvės sumažinimas performuluojant žaidimą kaip poravimo ir pašalinimo priklausomybių problemą sumažina sudėtingumą. Erdvė vis dar didelė, bet ji daug lengviau valdoma nei sekant kiekvieną įmanomą ėjimų seką.
6. Taikykite išankstinį suspaudimą. Veiksmingi sprendėjai sutelkia dėmesį į tai, kurios plytelės yra pasiekiamos esant dabartiniam lentos išdėstymui, ir atmeta šakas, kur užblokuotos plytelės daro poravimą fiziškai neįmanomą, nepaisant abstraktaus poravimo pasirinkimo.

Patarimas: Analizuodami Mahjong lentą rankiniu būdu, galvokite apie poravimo įsipareigojimus, o ne apie atskirus ėjimus. Nustatykite, kurios plytelės turi tik vieną pasiekiamą tinkamą partnerį, ir pirmiausia užfiksuokite tas poras. Tai atitinka tai, kaip algoritminiai sprendėjai genėja paieškos medį.

Kombinatorinis sprogimas daro išsamią paiešką nepraktišką. Ši realybė verčia kiekvieną praktinį įgyvendinimą remtis euristikomis ir atsitiktinio kartojimo strategijomis, o ne pilnu išvardijimu. Šio apribojimo supratimas yra pagrindas Mahjong algoritmams, paaiškinamiems bet kuriame rimtame programinės įrangos kontekste.

Kaip realūs įgyvendinimai generuoja išsprendžiamas Mahjong lentas?

Gamybinė Mahjong programinė įranga nesistengia įrodyti sprendžiamumo nuo pirmųjų principų. Ji tikrina sprendžiamumą naudodama dviejų sluoksnių sistemą, kuri sujungia greitą lentos konstravimą su sprendėju, patikrinančiu rezultatą.

Standartinė architektūra veikia taip:

• 1 sluoksnis: konstrukcinė generacija. Variklis sukuria lentą naudodamas metodą, skirtą generuoti išsprendžiamus išdėstymus. Tai greita, bet ne visada garantuoja sėkmę.
• 2 sluoksnis: sprendžiamumo patikra. Sugeneruotai lentelei paleidžiamas sprendėjas. Jei lenta neatitinka patikros, variklis bando dar kartą.
• Kartojimo ciklai. Įprasti įgyvendinimai paleidžia buildSolvableWithRetries iki 2 000 bandymų prieš pereidami prie kitų strategijų. Šis skaičius atspindi empirinį derinimą, o ne teorinį būtinumą.
• Alternatyvios strategijos. Išnaudojus pagrindinį bandymų biudžetą, variklis pereina prie kito konstravimo algoritmo su savo kartojimo ciklu.
• Atsarginis atsitiktinės lentos variantas. Jei visa kita nepavyksta, variklis sugeneruoja atsitiktinę lentą ir tiesiogiai ją patikrina sprendėju. Tai užtikrina, kad visada bus pateikta žaidžiama lenta.

Patarimas: Jei kuriate Mahjong galvosūkių generatorių, pradėkite nuo atvirkštinio konstravimo metodo: išdėstykite plyteles žinoma išsprendžiama tvarka, o tada maišykite laikydamiesi apribojimų. Tai smarkiai sumažina kartojimų skaičių, reikalingą norint rasti tinkamą lentą.

Toliau pateikta lentelė apibendrina trijų pakopų atsarginį modelį, naudojamą gamybiniuose kodų pagrinduose:

Ši dviejų sluoksnių sistema su pakartotiniais bandymais ir atsarginėmis strategijomis yra gamybinis standartas, skirtas pateikti išsprendžiamas galvosūkių lentas. Inžinerinis požiūris čia yra sąmoningas: iš anksto neįrodykite sprendžiamumo. Sukurkite greitai, patikrinkite nedelsdami ir, jei reikia, bandykite dar kartą. Toks metodas atitinka tai, ką prognozuoja sudėtingumo teorija. Tikslūs įrodymai yra brangūs. Patikra yra pigi.

Kaip žinios apie sprendžiamumą pagerina Mahjong žaidimo strategijas ir dizainą?

Supratimas, kaip veikia sprendžiamumas, keičia ir tai, kaip kūrėjai kuria žaidimus, ir tai, kaip žaidėjai sprendžia Mahjong galvosūkius. Šios dvi perspektyvos viena kitą sustiprina.

Iš žaidėjo strategijos perspektyvos sprendžiamumo įžvalgos tiesiogiai virsta geresniais sprendimais:

• Pirmenybę teikite atviroms plytelėms su ribotu partnerių skaičiumi. Jei plytelė turi tik vieną pasiekiamą porą, tą poravimą teks atlikti tam tikru momentu. Atidėliojimas gali užblokuoti lentą.
• Venkite izoliuoti plytelių grupes. Pašalinus plyteles, kurios neatskleidžia naujų plytelių, sumažėja būsimos galimybės, nepagerinant padėties. Ši sąvoka išsamiai nagrinėjama plytelių izoliacijos kontekste ir kodėl ji kenkia sprendžiamumui.
• Galvokite sluoksniais, o ne apie atskirus ėjimus. Sprendžiamumas priklauso nuo poravimo įsipareigojimų visoje lentoje. Žaidėjai, planuojantys du ar tris ėjimus į priekį, nuosekliai lenkia tuos, kurie reaguoja tik į vienos plytelės galimybes.
• Strategiškai naudokite maišymo funkcijas. Dauguma skaitmeninių Mahjong žaidimų siūlo maišymo arba užuominos funkciją. Šios funkcijos fone remiasi tais pačiais sprendžiamumo algoritmais, kad patvirtintų, jog vis dar egzistuoja galiojantis kelias.

Iš žaidimo dizaino perspektyvos sprendžiamumo algoritmai lemia žaidėjo patirties kokybę:

• Išdėstymai, sugeneruoti be sprendžiamumo patikros, dažnai sukuria neįveikiamas lentas. Žaidėjai, susidūrę su tokiomis lentomis, praranda pasitikėjimą žaidimu, o ne savo įgūdžiais.
• Plytelių išdėstymas tiesiogiai veikia sunkumą. Dizainai, kurie anksti atveria mažiau plytelių, verčia žaidėjus rinktis siauresnius sprendimų medžius, taip didindami faktinį Mahjong galvosūkių sprendimo sudėtingumą.
• Paslėptos informacijos variantai, kai plytelių veidai yra paslėpti, kol jie neatskleidžiami, perkelia problemą iš NP-baigtinio sprendimo į tikimybinį samprotavimą. Tai visiškai pakeičia žaidimo pobūdį.
• Kūrėjai, suprantantys Mahjong DI algoritmus, gali derinti sunkumą reguliuodami, kiek agresyviai konstrukcinis generatorius teikia pirmenybę išdėstymams su keliais galimais sprendimo keliais.

Ryšys tarp algoritminės teorijos ir žaidėjo patirties yra tiesioginis. Lenta, sugeneruota naudojant patikimą sprendžiamumo algoritmą, suteikia jums sąžiningą galvosūkį. Lenta, sugeneruota be jo, gali būti neįmanoma, ir jūs niekada nesužinosite, kodėl nepavyko.

Pagrindinės išvados

Mahjong sprendžiamumo algoritmas sprendimo problemoms yra NP-baigtinis, o optimizavimo problemoms – PSPACE-baigtinis, todėl euristiniai ir kartojimu paremti metodai yra vienintelis praktiškas kelias į išsprendžiamas lentas gamybinėje programinėje įrangoje.

Kodėl vien teorijos nepakaks, kad sukurtumėte geresnį Mahjong žaidimą

Praleidau nemažai laiko analizuodamas, kaip praktiškai įgyvendinamas Mahjong sprendžiamumas, ir skirtumas tarp akademinių sudėtingumo rezultatų ir to, ką iš tikrųjų išleidžia inžinieriai, yra stulbinantis. NP-baigtumo ir PSPACE-baigtumo įrodymai yra intelektualiai patenkinami. Jie pasako ką nors teisingo ir svarbaus apie problemą. Tačiau jie nepasako, kaip sukurti žaidimą, kuris patiktų žaidėjams.

Ką pastebėjau, tai kad kartojimais paremta strategija nėra kompromisas. Tai yra teisingas atsakymas šiai problemų klasei. Kai jūsų paieškos erdvėje yra 150 kvadrilijonų konfigūracijų, jums nereikia jų visų išnagrinėti. Jums reikia greito generatoriaus, kuris dažniausiai sėkmingas, pigaus tikrintojo, kuris pagauna nesėkmes, ir atsarginio sprendimo, kuris užtikrina pateikimą. Tokia architektūra gamyboje yra patikimesnė nei bet kuris tikslus sprendėjas.

Įžvalga, kad ėjimų seka neturi įtakos sprendžiamumui, kai poros jau nustatytos, yra labiausiai neįvertintas rezultatas šioje srityje. Tai reiškia, kad iš pažiūros sekų problemą galite sumažinti iki kombinatorinės, o kombinatorinės problemos gerai reaguoja į apribojimų sklaidą ir genėjimą. Jei kuriate Mahjong sprendėją arba studijuojate galvosūkių žaidimų sudėtingumą, pradėkite nuo to.

Mano patarimas visiems, norintiems įgyvendinti sprendžiamumo tikrinimą: nepradėkite nuo sudėtingumo literatūros. Pradėkite nuo veikiančio kartojimo ciklo, įdiekite matavimus, kad stebėtumėte, kaip dažnai suveikia kiekvienas atsarginis etapas, ir tada derinkite. Teorija parodo viršutinę ribą. Matavimai parodo, kur iš tikrųjų esate.

— Dmytro Romaniuk

Žaiskite Mahjong galvosūkius, sukurtus remiantis išsprendžiamų lentų generavimu

Kiekvienas galvosūkis Mahjong Online Club yra sugeneruotas naudojant tokį sprendžiamumą pirmiausia taikantį metodą, kaip aprašyta šiame straipsnyje. Jokia lenta jums nepateikiama nepraėjusi sprendėjo patikros etapo. Tai reiškia, kad kiekvienas jūsų pradėtas žaidimas yra įveikiamas, o kiekviena nesėkmė yra strategijos problema, o ne sugadintas išdėstymas.

Galite žaisti nemokamą Mahjong tiesiog naršyklėje, nereikia registracijos. Platforma sukurta taip, kad patirtis būtų be trukdžių ir padėtų susikaupti bei atpažinti raštus. Jei norite praktiškai pritaikyti čia aptartas algoritmines sąvokas, tai yra tinkama vieta tai padaryti.

DUK

Kas yra Mahjong sprendžiamumo algoritmas?

Mahjong sprendžiamumo algoritmas yra skaičiavimo procedūra, nustatanti, ar Mahjong solitaire lenta gali būti visiškai išvalyta suderinant ir pašalinant visas plytelių poras. Šios problemos sprendimo versija formaliai yra NP-baigtinė esant pilnai informacijai.

Kaip matematiškai veikia Mahjong sprendžiamumas?

Sprendžiamumas priklauso nuo poravimo pasirinkimų per 36 plytelių kategorijas, kiekviena iš jų siūlo 3 galimus poravimus, todėl iš viso susidaro maždaug 150 kvadrilijonų konfigūracijų. Kadangi ėjimų seka nekeičia rezultato, kai poros jau nustatytos, sprendėjai sutelkia dėmesį į poravimo apribojimus, o ne į ėjimų sekas.

Kodėl programinė įranga negali kiekvieną kartą tiksliai išspręsti Mahjong lentų?

Tikslus sprendžiamumo tikrinimas reikalauja blogiausiu atveju eksponentinių skaičiavimų, kurie realaus laiko žaidimo varikliams yra nepraktiški. Gamybinės sistemos naudoja konstrukcinius generatorius su kartojimo ciklais iki 2 000 bandymų ir atsarginiais etapais, kad užtikrintų žaidžiamą lentą be tikslaus įrodymo.

Kuo skiriasi np-baigtinis ir pspace-baigtinis Mahjong kontekste?

Sprendimo problema (ar šią lentą galima išvalyti?) yra NP-baigtinė. Optimizavimo problema (kokia seka maksimaliai padidina išvalymo tikimybę?) yra PSPACE-baigtinė, o tai yra griežtai sunkesnė klasė, kuri taip pat atmeta efektyvius apytikslius algoritmus.

Kaip Mahjong žaidimo strategijos siejasi su sprendžiamumo algoritmais?

Žaidėjai, kurie pirmenybę teikia plytelėms su ribotais pasiekiamais partneriais ir vengia izoliuoti plytelių grupes, taiko tą pačią apribojimų genėjimo logiką, kurią naudoja algoritminiai sprendėjai. Supratimas, kaip struktūruotas sprendžiamumas, daro strateginius sprendimus sąmoningesnius ir mažiau priklausomus nuo spėjimo.

Rekomenduojama

• Kaip žaisti Mahjong Solitaire — taisyklės, plytelės ir strategija
• Kodėl plytelių izoliacija sugadina Mahjong žaidimus visiems žaidėjams
• Mahjong Titans gudrybės: sprendėjai, užuominos ir teisėti spartieji keliai
• Koks yra Mahjong tikslas? Taisyklės ir strategija