Mahjongi lahendatavuse algoritm: kuidas see töötab

Mahjongi lahendatavuse algoritm on otsustusprotseduur, mis määrab, kas antud Mahjongi pasjansilaua saab mängureeglite järgi järjestikuste plaatide paaritamise ja eemaldamisega täielikult tühjendada. Mõistmine, mis on mahjongi lahendatavuse algoritm, tähendab silmitsi seismist ühega kombinatoorse mänguteooria huvitavamatest probleemidest: küsimus on täieliku info korral formaalselt NP-täielik, mis tähendab, et ühtki teadaolevat algoritmi ei ole, mis lahendaks selle kõigi võimalike lauaasetuste jaoks tõhusalt. Tegelik tarkvara möödub sellest takistusest heuristikate, korduskatsete ja varustrateegiate abil. Just teoreetilise raskuse ja praktilise mängitavuse vaheline lõhe on koht, kus sünnib kõige kasulikum inseneritöö.

Mida ütleb arvutuslik keerukus mahjongi lahendatavuse kohta?

Arvutuslik keerukus on formaalne uurimus selle kohta, kui raske on arvutil mingit probleemi lahendada. Siin on kõige olulisemad kaks keerukusklassi: NP ja PSPACE.

NP-täielik kirjeldab probleeme, mille puhul lahenduse kontrollimine on kiire, kuid selle leidmine võib nõuda eksponentsiaalset aega. Täieliku infoga Mahjongi pasjanss on otsustusprobleemina NP-täielik: kui kõik plaatide asukohad on teada, kas kõik plaadid saab eemaldada? See tulemus tähendab, et ühtki algoritmi ei saa garanteeritult kasutada selle küsimuse kiireks vastamiseks iga võimaliku paigutuse korral.

PSPACE-täielik on veelgi raskem klass. Eemaldamise tõenäosuse maksimeerimine on PSPACE-täielik ja PSPACE-raskesti lähendatav tegurini n tõstetud suvalise positiivse konstandini. See tulemus välistab isegi polünoomajaga töötavad ligikaudsed lahendused, kui keerukusteooria aluspõhimõtted kokku ei kuku.

Praktikas tähendab see järgmist:

• Otsustusvariant (kas seda lauda saab tühjendada?) on NP-täielik. Täpsed lahendajad seisavad silmitsi halvimal juhul eksponentsiaalse ajaga.
• Optimeerimisvariant (milline järjestus maksimeerib tühjendamise tõenäosust?) on PSPACE-täielik. See on otsustusvariandist rangelt raskem.
• Täpne lahendatavuse kontroll nõuab halvimal juhul eksponentsiaalset või mälumahukat arvutust. Praktilised lahendajad toetuvad selle asemel heuristikatele või paigutuse piirangutele.
• Lahendatavus sõltub probleemi sõnastusest ja mängumudelist. Ükski universaalne algoritm ei sobi kõigile Mahjongi variantidele.

Keerukusteooria põhijäreldus ei ole see, et Mahjong on lahendamatu. Pigem on asi selles, et selle täpne lahendamine suvaliste laudade puhul on arvutuslikult nii kulukas, et ükski tootmises kasutatav mängumootor ei püüa seda otse teha.

See eristus kujundab iga Mahjongi tarkvara disainiotsust. Arendajad ei oota tõestatult õiget vastust. Nad ehitavad süsteeme, mis loovad suure tõenäosusega lahendatavaid laudu, ja seejärel kontrollivad, mitte ei tõesta.

Kuidas lahendatavust modelleeritakse ja miks kombinatoorne plahvatus on oluline?

Mahjongi pasjanssi matemaatiline struktuur keskendub plaatide paaritamisele. Iga plaat kuulub ühte 36 kategooriast ja igas kategoorias on täpselt neli plaati. Laua tühjendamiseks tuleb iga plaat sobitada ühega oma kolmest samasugusest paarilisest.

Siin on põhikombinatoorne väljakutse samm-sammult:

1. Loenda paaritamisvõimalused. Iga nelja identse plaadi rühma puhul on täpselt kolm viisi, kuidas need kaheks sobitatud paariks jaotada.
2. Korruta üle kõigi kategooriate. 36 kategooria ja igaühe 3 võimaluse korral on paarituskonfiguratsioonide koguarv 3^36, ligikaudu 1,5 × 10^17. See on umbes 150 kvadriljonit kombinatsiooni.
3. Mõista ammendava otsingu võimatust. Isegi ühe miljardi operatsiooni sekundis kontrollimine võtaks üle nelja aasta järjestikust arvutamist. Ükski mängumootor ei saa seda iga laua kohta endale lubada.
4. Erista paaritamine liikumisjärjestusest. Eemaldamise järjekord ei mõjuta lõplikku lahendatavuse tulemust, kui paarid on juba fikseeritud. See on kriitiline arusaam. See tähendab, et otsinguruumi määravad paarivalikud, mitte käikude järjestus.
5. Keskendu otsingus paarimismustritele. Seisuruumi vähendamine, sõnastades mängu paaritamise ja eemaldamise sõltuvusprobleemina, vähendab keerukust. Ruum jääb suureks, kuid see on palju paremini hallatav kui iga võimaliku käigujada jälgimine.
6. Rakenda eelkärpimist. Tõhusad lahendajad keskenduvad sellele, millised plaadid on praeguse lauaasetuse põhjal ligipääsetavad, kärpides harusid, kus blokeeritud plaadid muudavad paaritamise füüsiliselt võimatuks, sõltumata abstraktsest paarivalikust.

Pro nõuanne: Kui analüüsid Mahjongi lauda käsitsi, mõtle paarituskohustuste, mitte üksikute käikude kaudu. Tuvasta, millistel plaatidel on ainult üks ligipääsetav kehtiv paariline, ja lukusta need paarid esimesena. See peegeldab seda, kuidas algoritmilised lahendajad otsingupuud kärbivad.

Kombinatoorne paisumine muudab ammendava otsingu teostamatuks. See reaalsus sunnib iga praktilist rakendust liikuma heuristikate ja juhuslike korduskatsete strateegiate poole, mitte täieliku loendamise poole. Selle piirangu mõistmine on mahjongi algoritmide selgituste alus igas tõsises tarkvarakontekstis.

Kuidas päris rakendused loovad lahendatavaid mahjongi laudu?

Tootmises kasutatav Mahjongi tarkvara ei püüa lahendatavust esimestest põhimõtetest tõestada. See kontrollib lahendatavust kahekihilise süsteemi abil, mis ühendab kiire laua loomise lahendajaga, mis kontrollib tulemust.

Tavaline arhitektuur töötab nii:

• Kiht 1: konstruktiivne genereerimine. Mootor ehitab laua meetodil, mis on loodud lahendatavate paigutuste tekitamiseks. See on kiire, kuid ei ole iga kord garanteeritud.
• Kiht 2: lahendatavuse valideerimine. Genereeritud laual käivitatakse lahendaja. Kui laud kontrolli ei läbi, proovib mootor uuesti.
• Korduslingid. Levinud rakendused käivitavad buildSolvableWithRetries kuni 2 000 korda enne strateegia vahetamist. See arv peegeldab empiirilist häälestust, mitte teoreetilist vajadust.
• Alternatiivsed strateegiad. Pärast esmase korduskatsete eelarve ammendumist lülitub mootor teisele konstruktsioonialgoritmile koos omaenda korduslingiga.
• Juhusliku laua varulahendus. Kui kõik muu ebaõnnestub, genereerib mootor juhusliku laua ja käivitab sellel otse lahenduskontrolli. See tagab, et alati antakse mängitav laud.

Pro nõuanne: Kui ehitad Mahjongi mõistatuste generaatorit, alusta tagurpidi konstrueerimise lähenemisest: paiguta plaadid teadaolevalt lahendatavas järjekorras ja seejärel sega neid piirangute sees. See vähendab märkimisväärselt korduskatsete arvu, mida on vaja kehtiva laua leidmiseks.

Allolev tabel võtab kokku tootmiskoodis kasutatava kolmeastmelise varulahenduse mustri:

See kahekihiline süsteem koos korduvate katsete ja varustrateegiatega on tootmises standardne viis lahendatavate mõistatuslaudade pakkumiseks. Siinne insenerimõtteviis on teadlik: ära tõesta lahendatavust ette. Ehita kiiresti, kontrolli kiiresti ja proovi vajadusel uuesti. See lähenemine on kooskõlas sellega, mida keerukusteooria ennustab. Täpsed tõestused on kallid. Kontrollimine on odav.

Kuidas lahendatavuse teadmine parandab mahjongi mängustrateegiaid ja disaini?

Mõistmine, kuidas lahendatavus töötab, muudab nii seda, kuidas arendajad mänge ehitavad, kui ka seda, kuidas mängijad mahjongi mõistatusi lahendavad. Need kaks vaatenurka tugevdavad teineteist.

Mängijastrateegia vaatenurgast tõlgituvad lahendatavuse teadmised otse paremateks otsusteks:

• Eelista avatud plaate, millel on vähe võimalikke paarilisi. Kui plaadil on ainult üks ligipääsetav vaste, tuleb see paaritus mingil hetkel teha. Edasilükkamine võib laua blokeerida.
• Väldi plaatide rühmade isoleerimist. Selliste plaatide eemaldamine, mis ei ava uusi plaate, vähendab tulevasi võimalusi, parandamata sinu seisu. Seda mõistet käsitletakse põhjalikult plaatide isoleerimise kontekstis ja selles, miks see lahendatavust õõnestab.
• Mõtle kihtidena, mitte üksikute käikudena. Lahendatavus sõltub paarituskohustustest kogu laua ulatuses. Mängijad, kes planeerivad kaks või kolm käiku ette, edestavad järjekindlalt neid, kes reageerivad üksikutele plaatide võimalustele.
• Kasuta segamisfunktsioone strateegiliselt. Enamik digitaalseid Mahjongi mänge pakub segamise või vihje funktsiooni. Need funktsioonid tuginevad taustal samadele lahendatavuse algoritmidele, et kinnitada, et kehtiv tee on endiselt olemas.

Mängudisaini vaatenurgast määravad lahendatavuse algoritmid mängija kogemuse kvaliteedi:

• Lahendatavuse kontrollita loodud paigutused toodavad sageli võitmatuid laudu. Mängijad, kes sellistega kokku puutuvad, kaotavad usalduse mängu, mitte oma oskuste vastu.
• Plaatide paigutus mõjutab otseselt raskusastet. Disainid, mis avavad alguses vähem plaate, sunnivad mängijaid kitsamatesse otsustuspuudesse, suurendades mahjongi mõistatuste lahendamise tegelikku keerukust.
• Varjatud teabega variandid, kus plaatide näod on peidetud kuni nende avamiseni, nihutavad probleemi NP-täielikust otsustamisest tõenäosuslikule arutlusele. See muudab mängu iseloomu täielikult.
• Arendajad, kes mõistavad mahjongi tehisintellekti algoritme, saavad raskusastet häälestada, muutes seda, kui agressiivselt konstruktiivne generaator eelistab mitme kehtiva lahendustee paigutusi.

Seos algoritmilise teooria ja mängijakogemuse vahel on otsene. Tugeva lahendatavuse algoritmiga loodud laud annab sulle ausa mõistatuse. Ilma selleta loodud laud võib olla võimatu ja sa ei saa kunagi teada, miks sa läbi kukkusid.

Põhipunktid

Mahjongi lahendatavuse algoritm on otsustusprobleemide puhul NP-täielik ja optimeerimisprobleemide puhul PSPACE-täielik, mistõttu on heuristilised ja korduskatsetel põhinevad meetodid ainsad praktilised viisid lahendatavate laudade loomiseks tootmistarkvaras.

Miks teooriast üksi ei piisa parema mahjongimängu ehitamiseks

Olen kulutanud märkimisväärselt aega sellele, kuidas Mahjongi lahendatavust praktikas rakendatakse, ja lõhe akadeemiliste keerukustulemuste ning selle vahel, mida insenerid tegelikult tarnivad, on silmatorkav. NP-täielikkuse ja PSPACE-täielikkuse tõestused on intellektuaalselt rahuldust pakkuvad. Need ütlevad sulle midagi tõest ja olulist probleemi kohta. Kuid need ei ütle, kuidas ehitada mängu, mida mängijad naudivad.

Minu kogemus näitab, et korduskatsetel põhinev lähenemine ei ole kompromiss. See on selle probleemi klassi jaoks õige vastus. Kui sinu otsinguruumis on 150 kvadriljonit konfiguratsiooni, ei pea sa neid kõiki läbi uurima. Sul on vaja kiiret generaatorit, mis õnnestub enamasti, odavat kontrollijat, mis tabab ebaõnnestumised, ja varulahendust, mis tagab kohaletoimetamise. Selline arhitektuur on tootmises usaldusväärsem kui ükski täpne lahendaja oleks.

Arusaam, et liikumisjärjestus ei mõjuta lahendatavust, kui paarid on fikseeritud, on selle valdkonna kõige alahinnatum tulemus. See tähendab, et näiliselt järjestikuse probleemi saab taandada kombinatoorseks probleemiks ning kombinatoorsed probleemid alluvad hästi piirangute levitamisele ja kärpimisele. Kui ehitad Mahjongi lahendajat või uurid mõistatusmängude keerukust, alusta sealt.

Minu soovitus kõigile, kes tahavad lahendatavuse kontrolli rakendada: ära alusta keerukuskirjandusest. Alusta töötava korduslingiga, mõõda, kui sageli iga varuetapp käivitub, ja häälesta sealt edasi. Teooria ütleb sulle lagi. Mõõtmine ütleb sulle, kus sa tegelikult oled.

— Dmytro Romaniuk

Mängi mahjongi mõistatusi, mis põhinevad lahendatavate laudade genereerimisel

Iga mõistatus Mahjong Online Clubis on loodud kasutades selles artiklis kirjeldatud lahendatavust esikohale seadvat lähenemist. Ühtki lauda ei pakuta sulle ilma lahendaja valideerimisetappi läbimata. See tähendab, et iga mäng, mida alustad, on võidetav ja iga ebaõnnestumine on strateegia, mitte vigase paigutuse probleem.

Saad mängida tasuta Mahjongi otse oma brauseris ilma registreerimiseta. Platvorm on üles ehitatud segamatule kogemusele, mis toetab keskendumist ja mustrite äratundmist. Kui tahad siin kirjeldatud algoritmilisi mõisteid praktikas proovida, siis see on selleks õige koht.

KKK

Mis on mahjongi lahendatavuse algoritm?

Mahjongi lahendatavuse algoritm on arvutuslik protseduur, mis määrab, kas Mahjongi pasjansilauda saab täielikult tühjendada, sobitades ja eemaldades kõik plaatide paarid. Selle probleemi otsustusvariant on täieliku info korral formaalselt NP-täielik.

Kuidas mahjongi lahendatavus matemaatiliselt töötab?

Lahendatavus sõltub 36 plaadikategooria paarivalikutest, millest igaüks pakub 3 võimalikku paaritust, tekitades kokku ligikaudu 150 kvadriljonit konfiguratsiooni. Kuna liikumisjärjestus ei muuda tulemust, kui paarid on fikseeritud, keskenduvad lahendajad paaritamispiirangutele, mitte käikude jadadele.

Miks ei saa tarkvara mahjongi laudu iga kord täpselt lahendada?

Täpsete lahendatavuse kontrollide puhul on halvimal juhul vaja eksponentsiaalset arvutust, mis on reaalajas mängumootorite jaoks ebapraktiline. Tootmissüsteemid kasutavad konstruktiivseid generaatoreid koos kuni 2 000 katsega korduslingi ja varuetappidega, et tagada mängitav laud ilma täpse tõestuseta.

Mis vahe on mahjongis NP-täielikul ja PSPACE-täielikul?

Otsustusprobleem (kas seda lauda saab tühjendada?) on NP-täielik. Optimeerimisprobleem (milline järjestus maksimeerib tühjendamise tõenäosust?) on PSPACE-täielik, mis on rangelt raskem klass ja välistab ka tõhusad lähendusalgoritmid.

Kuidas seostuvad mahjongi mängustrateegiad lahendatavuse algoritmidega?

Mängijad, kes eelistavad piiratud ligipääsetavate paarilistega plaate ja väldivad plaatide rühmade isoleerimist, rakendavad sama piirangute kärpimise loogikat, mida kasutavad algoritmilised lahendajad. Lahendatavuse struktuuri mõistmine muudab strateegilised otsused teadlikumaks ja vähem juhuslikuks.

Soovitatud

• Kuidas mängida Mahjongi pasjanssi — reeglid, plaadid ja strateegia
• Miks plaatide isoleerimine rikub Mahjongi mängud kõigi mängijate jaoks
• Mahjong Titansi pettused: lahendajad, vihjed ja ausad otseteed
• Mis on Mahjongi eesmärk? Reeglid ja strateegia