Algoritem rešljvosti Mahjonga: kako deluje

Algoritem rešljvosti Mahjonga je odločitveni postopek, ki določi, ali je dano tablo pasjansa Mahjong mogoče v celoti počistiti z zaporednim ujemanjem in odstranjevanjem parov ploščic po pravilih igre. Razumevanje, kaj pomeni algoritem rešljvosti Mahjonga, pomeni soočenje z enim zanimivejših problemov v kombinatorični teoriji iger: vprašanje je formalno NP-polno pri popolnih informacijah, kar pomeni, da ni znanega algoritma, ki bi ga za vse možne postavitve rešil učinkovito. Resnična programska oprema to oviro obide s hevristikami, ponovitvenimi zankami in strategijami za rezervni izhod. Prav v razkoraku med teoretično zahtevnostjo in praktično uporabnostjo nastane najbolj uporabno inženirstvo.

Kaj nam računska zahtevnost pove o rešljvosti Mahjonga?

Računska zahtevnost je formalno preučevanje tega, kako težko je problem rešiti z računalnikom. Tu sta najpomembnejša dva razreda zahtevnosti: NP in PSPACE.

NP-poln opisuje probleme, pri katerih je preverjanje rešitve hitro, iskanje pa lahko zahteva eksponenten čas. Mahjong solitaire s popolnimi informacijami je za odločitveni problem NP-poln: če imamo tablo, pri kateri so znani vsi položaji ploščic, ali je mogoče odstraniti vse ploščice? Ta rezultat pomeni, da ni algoritma, ki bi na to vprašanje za vsako možno postavitev vedno odgovoril hitro.

PSPACE-poln je še zahtevnejši razred. Maksimiziranje verjetnosti odstranitve je PSPACE-polno in PSPACE-težko približati znotraj faktorja n, povzdignjenega na katerokoli pozitivno konstanto. Ta rezultat izključuje celo približne rešitve, ki bi delovale v polinomskem času, razen če se zrušijo temeljne predpostavke teorije zahtevnosti.

V praksi to pomeni naslednje:

• Odločitvena različica (ali je to tablo mogoče počistiti?) je NP-polna. Natančni reševalniki se v najslabšem primeru soočajo z eksponentnim časom.
• Optimizacijska različica (katero zaporedje najbolj poveča verjetnost čiščenja?) je PSPACE-polna. Je strogo težja od odločitvene različice.
• Natančno preverjanje rešljvosti zahteva v najslabšem primeru eksponentno ali prostorsko zelo zahtevno računanje. Praktični reševalniki se zato zanašajo na hevristike ali omejitve postavitve.
• Rešljvost je odvisna od formulacije problema in modela igre. Noben univerzalni algoritem ne ustreza vsem različicam Mahjonga.

Osnovni nauk teorije zahtevnosti ni, da je Mahjong nerešljiv. Pomeni pa, da je njegovo natančno reševanje za poljubne table računsko dovolj drago, da ga noben produkcijski igralni pogon ne poskuša izvajati neposredno.

Ta razlika oblikuje vsako oblikovalsko odločitev v programski opremi za Mahjong. Razvijalci ne čakajo na dokazano pravilen odgovor. Gradijo sisteme, ki z veliko verjetnostjo ustvarijo rešljive table, nato pa rezultat preverijo namesto da bi ga dokazovali.

Kako modeliramo rešljvost in zakaj je pomembna kombinatorična eksplozija?

Matematična struktura pasjansa Mahjong temelji na parjenju ploščic. Vsaka ploščica pripada eni od 36 kategorij, vsaka kategorija pa vsebuje natanko štiri ploščice. Da bi tablo počistili, je treba vsako ploščico ujemati z eno od njenih treh enakih kopij.

Tu je jedro kombinatoričnega izziva, korak za korakom:

1. Preštejte možnosti parjenja. Za vsako skupino štirih enakih ploščic obstajajo natanko trije načini, kako jih razporediti v dva ujemajoča se para.
2. Pomnožite čez vse kategorije. Pri 36 kategorijah in 3 možnostih v vsaki je skupno število konfiguracij parjenja 3^36, približno 1,5 × 10^17. To je približno 150 kvadrilijonov kombinacij.
3. Prepoznajte nemogočnost izčrpnega iskanja. Preverjanje vsake konfiguracije bi pri celo eni milijardi operacij na sekundo trajalo več kot štiri leta neprekinjenega računanja. Noben igralni pogon si tega ne more privoščiti za vsako tablo.
4. Ločite parjenje od vrstnega reda potez. Vrstni red odstranjevanja ne vpliva na končni izid rešljvosti, ko so parjenja enkrat določena. To je ključni vpogled. Pomeni, da je iskalni prostor določen z izbiro parov, ne pa z zaporedjem potez.
5. Osredotočite iskanje na vzorce parjenja. Zmanjšanje prostora stanj s preoblikovanjem igre v problem odvisnosti med parjenjem in odstranjevanjem zmanjša zahtevnost. Prostor ostaja velik, vendar je precej bolj obvladljiv kot sledenje vsaki možni zaporedni potezi.
6. Uporabite predkompresijo. Učinkoviti reševalniki se osredotočajo na to, katere ploščice so glede na trenutno postavitev dostopne, in obrezujejo veje, kjer blokirane ploščice naredijo parjenje fizično nemogoče, ne glede na abstraktno izbiro para.

Nasvet: Ko tablo Mahjong analizirate ročno, razmišljajte v smislu zavez k parjenju, ne posameznih potez. Prepoznajte ploščice, ki imajo dostopnega le enega veljavnega partnerja, in najprej zaklenite ta parjenja. To posnema način, kako algoritmični reševalniki obrezujejo iskalno drevo.

Kombinatorični razmah naredi izčrpno iskanje neizvedljivo. Ta resničnost vsako praktično izvedbo potisne k hevristikam in naključnim strategijam ponovnega poskusa namesto k popolnemu naštevanju. Razumevanje te omejitve je temelj algoritmov za Mahjong, kot jih razlagamo v vsakem resnem programskem kontekstu.

Kako resnične izvedbe ustvarjajo rešljive table Mahjong?

Produkcijska programska oprema za Mahjong ne poskuša dokazati rešljvosti iz prvih načel. Rešljvost preverja s sistemom dveh plasti, ki združuje hitro gradnjo table in reševalnik, ki preveri rezultat.

Standardna arhitektura deluje takole:

• 1. plast: ustvarjalno generiranje. Pogon zgradi tablo z metodo, zasnovano za ustvarjanje rešljvih postavitev. To je hitro, vendar ne uspe vedno.
• 2. plast: preverjanje rešljvosti. Na ustvarjeni tabli se zažene reševalnik. Če tabla preverjanja ne prestane, pogon poskusi znova.
• Zanke ponovnih poskusov. Pogoste izvedbe izvajajo buildSolvableWithRetries do 2.000 poskusov, preden preklopijo na drugo strategijo. Ta številka odraža empirično prilagajanje, ne teoretične nujnosti.
• Alternativne strategije. Ko je primarni proračun ponovnih poskusov izčrpan, pogon preklopi na drug algoritem gradnje z lastno zanko ponovnih poskusov.
• Rezervni naključni izhod. Če vse drugo odpove, pogon ustvari naključno tablo in jo neposredno preveri z reševalnikom. Tako je vedno zagotovljena igrabilna tabla.

Nasvet: Če gradite generator ugank Mahjong, začnite z obratnim pristopom gradnje: ploščice postavite v znan rešljv vrstni red, nato pa jih premešajte znotraj omejitev. To dramatično zmanjša število ponovnih poskusov, potrebnih za najdbo veljavne table.

Spodnja tabela povzema vzorec rezervnega delovanja v treh stopnjah, ki se uporablja v produkcijskih kodnih bazah:

Ta dvoslojni sistem s ponavljajočimi se ponovnimi poskusi in rezervnimi strategijami je produkcijski standard za dostavljanje rešljvih ugankarskih tabel. Inženirska miselnost je tu namerna: rešljvosti ne dokazujte vnaprej. Gradite hitro, preverjajte takoj in po potrebi poskusite znova. Tak pristop se ujema s tem, kar napoveduje teorija zahtevnosti. Natančni dokazi so dragi. Preverjanje je poceni.

Kako znanje o rešljvosti izboljša strategije in zasnovo igre Mahjong?

Razumevanje delovanja rešljvosti spremeni tako način, kako razvijalci gradijo igre, kot tudi način, kako igralci pristopajo k reševanju ugank Mahjong. Obe perspektivi se medsebojno krepita.

Z vidika strategije igralca se vpogledi v rešljvost neposredno prevedejo v boljše odločanje:

• Prednost dajte izpostavljenim ploščicam z omejenim številom partnerjev. Če ima ploščica le en dostopen par, bo treba to parjenje nekoč izvesti. Odlašanje lahko blokira tablo.
• Izogibajte se osamitvi skupin ploščic. Odstranjevanje ploščic, ki ne razkrijejo nobenih novih ploščic, zmanjša vaše prihodnje možnosti, ne da bi izboljšalo položaj. Ta koncept je podrobno obravnavan v okviru osamitve ploščic in tega, zakaj spodkopava rešljvost.
• Razmišljajte v plasteh, ne v posameznih potezah. Rešljvost je odvisna od zavez k parjenju po vsej tabli. Igralci, ki načrtujejo dve ali tri poteze vnaprej, dosledno prekašajo tiste, ki se odzivajo na priložnosti posameznih ploščic.
• Uporabljajte funkcije premešanja strateško. Večina digitalnih iger Mahjong ponuja funkcijo premešanja ali namigov. Te funkcije v ozadju uporabljajo iste algoritme rešljvosti, da potrdijo, da še vedno obstaja veljavna pot.

Z vidika zasnove igre algoritmi rešljvosti določajo kakovost igralne izkušnje:

• Postavitve, ustvarjene brez preverjanja rešljvosti, pogosto ustvarijo neprehodne table. Igralci, ki naletijo na takšne primere, izgubijo zaupanje v igro, ne pa v lastno spretnost.
• Razporeditev ploščic neposredno vpliva na težavnost. Zasnove, ki zgodaj razkrijejo manj ploščic, prisilijo igralce v ožje odločitvena drevesa, kar poveča dejansko zahtevnost reševanja ugank Mahjong.
• Različice s skritimi informacijami, kjer so obrazi ploščic prikriti, dokler niso odkriti, problem iz NP-polnega odločanja premaknejo v verjetnostno sklepanje. To povsem spremeni značaj igre.
• Razvijalci, ki razumejo algoritme umetne inteligence za Mahjong, lahko težavnost prilagodijo tako, da nastavijo, kako agresivno ustvarjalni generator daje prednost postavitvam z več veljavnimi potmi rešitve.

Povezava med algoritmično teorijo in igralno izkušnjo je neposredna. Tabla, ustvarjena z robustnim algoritmom rešljvosti, vam ponudi pošteno uganko. Tabla, ustvarjena brez njega, je morda nemogoča, vi pa nikoli ne boste vedeli, zakaj vam ni uspelo.

Ključne ugotovitve

Algoritem rešljvosti Mahjonga je za odločitvene probleme NP-poln, za optimizacijske pa PSPACE-poln, zato so hevristične metode in metode, ki temeljijo na ponovnih poskusih, edina praktična pot do rešljvih tabel v produkcijski programski opremi.

Zakaj vam teorija sama ne bo pomagala zgraditi boljše igre Mahjong

Precej časa sem posvetil analizi tega, kako se rešljvost Mahjonga dejansko implementira, in razkorak med akademskimi rezultati o zahtevnosti ter tem, kar inženirji dejansko izdajo, je osupljiv. Dokazi o NP-polnosti in PSPACE-polnosti so intelektualno zadovoljivi. Povejo vam nekaj resničnega in pomembnega o problemu. Ne povedo pa vam, kako zgraditi igro, v kateri igralci uživajo.

Ugotovil sem, da pristop, ki temelji na ponovnih poskusih, ni kompromis. Je pravi odgovor za ta razred problema. Ko ima vaš iskalni prostor 150 kvadrilijonov konfiguracij, vam ni treba raziskati vseh. Potrebujete hiter generator, ki večinoma uspe, poceni preverjevalnik, ki ujame napake, in rezervni izhod, ki zagotovi dostavo. Takšna arhitektura je v produkciji zanesljivejša od katerega koli natančnega reševalnika.

Vpogled, da vrstni red potez ne vpliva na rešljvost, ko so parjenja enkrat določena, je najbolj podcenjen rezultat na tem področju. Pomeni, da lahko navidez zaporedni problem zmanjšate na kombinatoričnega, kombinatorični problemi pa se dobro odzivajo na širjenje omejitev in obrezovanje. Če gradite reševalnik Mahjong ali preučujete zahtevnost ugankarskih iger, začnite tam.

Moj nasvet vsem, ki želijo implementirati preverjanje rešljvosti: ne začnite z literaturo o zahtevnosti. Začnite z delujočo zanko ponovnih poskusov, instrumentirajte jo, da meri, kako pogosto se sproži posamezna rezervna stopnja, in nato prilagajajte naprej. Teorija vam pove zgornjo mejo. Meritve vam povedo, kje dejansko ste.

— Dmytro Romaniuk

Igrajte uganke Mahjong, zgrajene na ustvarjanju rešljvih tabel

Vsaka uganka na Mahjong Online Club je ustvarjena z uporabo pristopa, ki najprej upošteva rešljvost, kot je opisan v tem članku. Nobena tabla vam ni ponujena, ne da bi prestala korak preverjanja z reševalnikom. To pomeni, da je vsaka igra, ki jo začnete, zmagljiva, vsak neuspeh pa je problem strategije, ne pokvarjena postavitev.

Mahjong lahko igrate brezplačno neposredno v brskalniku, brez registracije. Platforma je zasnovana za izkušnjo brez motenj, ki podpira osredotočenost in prepoznavanje vzorcev. Če želite tukaj predstavljene algoritmične koncepte preizkusiti v praksi, je to pravo mesto za to.

Pogosta vprašanja

Kaj je algoritem rešljvosti Mahjonga?

Algoritem rešljvosti Mahjonga je računski postopek, ki določi, ali je tablo pasjansa Mahjong mogoče v celoti počistiti z ujemanjem in odstranjevanjem vseh parov ploščic. Odločitvena različica tega problema je formalno NP-polna pri popolnih informacijah.

Kako rešljvost Mahjonga deluje matematično?

Rešljvost je odvisna od izbire parov med 36 kategorijami ploščic, pri čemer vsaka ponuja 3 možna parjenja, kar skupaj ustvari približno 150 kvadrilijonov konfiguracij. Ker vrstni red potez ne spremeni izida, ko so parjenja enkrat določena, se reševalniki osredotočajo na omejitve parjenja, ne pa na zaporedja potez.

Zakaj programska oprema ne more vsakič natančno rešiti tabel Mahjong?

Natančno preverjanje rešljvosti zahteva v najslabšem primeru eksponentno računanje, kar je za igralne pogone v realnem času nepraktično. Produkcijski sistemi uporabljajo ustvarjalne generatorje z zankami ponovnih poskusov do 2.000 poskusov in rezervnimi stopnjami, da zagotovijo igrabilno tablo brez natančnega dokaza.

Kakšna je razlika med NP-polnim in PSPACE-polnim pri Mahjongu?

Odločitveni problem (ali je to tablo mogoče počistiti?) je NP-poln. Optimizacijski problem (katero zaporedje najbolj poveča verjetnost čiščenja?) je PSPACE-poln, kar je strogo zahtevnejši razred, ki prav tako izključuje učinkovite približevalne algoritme.

Kako se strategije igre Mahjong povezujejo z algoritmi rešljvosti?

Igralci, ki dajejo prednost ploščicam z omejenim številom dostopnih partnerjev in se izogibajo osamitvi skupin ploščic, uporabljajo isto logiko obrezovanja omejitev, kot jo uporabljajo algoritmični reševalniki. Razumevanje strukture rešljvosti naredi strateške odločitve bolj premišljene in manj odvisne od ugibanja.

Priporočeno

• Kako igrati pasjans Mahjong — pravila, ploščice in strategija
• Zakaj osamitev ploščic pokvari igre Mahjong za vse igralce
• Goljufije za Mahjong Titans: reševalniki, namigi in legitimni bližnjice
• Kaj je cilj Mahjonga? Pravila in strategija