Mahjongin ratkeavuusalgoritmi: miten se toimii

Mahjongin ratkeavuusalgoritmi on päätöksentekomenetelmä, joka määrittää, voidaanko tietty Mahjong-pasianssitaulu tyhjentää kokonaan yhdistämällä ja poistamalla laattoja pareittain pelisääntöjen mukaisesti. Sen ymmärtäminen, mitä mahjongin ratkeavuusalgoritmi tarkoittaa, vie yhden yhdistelmällisen peliteorian kiinnostavimmista ongelmista äärelle: kysymys on muodollisesti NP-täydellinen täydellisen informaation tapauksessa, mikä tarkoittaa, ettei mitään tunnettua algoritmia ratkaise sitä tehokkaasti kaikille mahdollisille tauluasetelmille. Käytännön ohjelmistot kiertävät tämän esteen heuristiikoilla, uusintasilmukoilla ja vararatkaisuilla. Juuri teoreettisen vaikeuden ja käytännön pelattavuuden välinen kuilu on se kohta, jossa hyödyllisin suunnittelu syntyy.

Mitä laskennallinen monimutkaisuus kertoo Mahjongin ratkeavuudesta?

Laskennallinen monimutkaisuus on muodollinen tutkimus siitä, kuinka vaikea ongelma on tietokoneelle ratkaista. Tässä kaksi luokkaa ovat tärkeimmät: NP ja PSPACE.

NP-täydellinen kuvaa ongelmia, joissa ratkaisun tarkistaminen on nopeaa, mutta ratkaisun löytäminen voi vaatia eksponentiaalista aikaa. Täydellisen informaation Mahjong-pasianssi on päätösongelmana NP-täydellinen: kun taulun kaikki laattojen sijainnit tunnetaan, voidaanko kaikki laatat poistaa? Tämä tulos tarkoittaa, ettei mikään algoritmi voi taata nopeaa vastausta jokaiseen mahdolliseen asetelmaan.

PSPACE-täydellinen on vielä vaikeampi luokka. Poistumistodennäköisyyden maksimointi on PSPACE-täydellinen, ja sitä on PSPACE-vaikea approksimoida tekijällä, joka on n potenssiin mikä tahansa positiivinen vakio. Tämä tulos sulkee pois jopa likimääräiset ratkaisut polynomisessa ajassa, elleivät monimutkaisuusteorian perustavanlaatuiset oletukset romahda.

Näin nämä kaksi tulosta tarkoittavat käytännössä:

• Päätösversio (voiko tämän taulun tyhjentää?) on NP-täydellinen. Tarkat ratkaisijat kohtaavat pahimmillaan eksponentiaalisen ajan.
• Optimointiversio (mikä siirtojono maksimoi tyhjentymistodennäköisyyden?) on PSPACE-täydellinen. Se on selvästi vaikeampi kuin päätösversio.
• Tarkka ratkeavuuden tarkistus vaatii pahimmillaan eksponentiaalista tai muistia paljon kuluttavaa laskentaa. Käytännön ratkaisijat tukeutuvat heuristiikkoihin tai taulun rakenteen rajoituksiin.
• Ratkeavuus riippuu ongelman muotoilusta ja pelimallista. Yksi yleisalgoritmi ei sovi kaikkiin Mahjong-muunnelmiin.

Monimutkaisuusteorian keskeinen opetus ei ole, että Mahjong olisi mahdoton ratkaista. Opetus on, että sen ratkaiseminen täsmällisesti mielivaltaisille tauluille on laskennallisesti niin kallista, ettei mikään tuotantopelin moottori yritä tehdä sitä suoraan.

Tämä ero ohjaa jokaista Mahjong-ohjelmiston suunnittelupäätöstä. Kehittäjät eivät odota todistettavasti oikeaa vastausta. He rakentavat järjestelmiä, jotka tuottavat ratkeavia tauluja suurella todennäköisyydellä, ja sitten ne tarkistetaan todistamisen sijaan.

Miten ratkeavuus mallinnetaan, ja miksi yhdistelmällinen räjähdys on tärkeä?

Mahjong-pasianssin matemaattinen rakenne keskittyy laattojen parittamiseen. Jokainen laatta kuuluu yhteen 36 kategoriasta, ja jokaiseen kategoriaan kuuluu täsmälleen neljä laattaa. Jotta taulu voidaan tyhjentää, jokainen laatta on paritettava yhden kolmesta identtisestä vastineestaan kanssa.

Tässä on keskeinen yhdistelmällinen haaste vaihe vaiheelta:

1. Laske paritusvaihtoehdot. Jokaiselle neljän identtisen laatan ryhmälle on täsmälleen kolme tapaa jakaa ne kahdeksi pariksi.
2. Kerro kategoriat keskenään. Kun kategorioita on 36 ja jokaisessa 3 vaihtoehtoa, parituskonfiguraatioiden kokonaismäärä on 3^36, noin 1,5 × 10^17. Se on noin 150 biljardia yhdistelmää.
3. Tunnista täydellisen haun mahdottomuus. Jokaisen konfiguraation tarkistaminen jopa miljardilla operaatiolla sekunnissa veisi yli neljä vuotta yhtäjaksoista laskentaa. Yksikään pelimoottori ei voi käyttää siihen aikaa jokaista taulua kohden.
4. Erota paritus siirtojärjestyksestä. Poistojen järjestys ei vaikuta lopulliseen ratkeavuuteen, kun parit on kerran määrätty. Tämä on ratkaiseva oivallus. Se tarkoittaa, että hakutila määräytyy paritusvalinnoista, ei siirtojen järjestyksestä.
5. Keskity hakemaan parituskuvioita. Tilatilan pienentäminen muotoilemalla peli paritus- ja poistoriippuvuusongelmaksi vähentää monimutkaisuutta. Tila on yhä suuri, mutta paljon hallittavampi kuin kaikkien mahdollisten siirtosekvenssien seuraaminen.
6. Käytä esipuristusta. Tehokkaat ratkaisijat keskittyvät siihen, mitkä laatat ovat käytettävissä nykyisen taulun perusteella, ja karsivat haarat, joissa estyneet laatat tekevät parituksesta fyysisesti mahdottoman riippumatta abstraktista paritusvalinnasta.

Vinkki: Kun analysoit Mahjong-taulua käsin, ajattele yksittäisten siirtojen sijaan parituspäätöksiä. Tunnista, millä laatoilla on vain yksi käytettävissä oleva kelvollinen pari, ja lukitse nuo parit ensin. Tämä jäljittelee sitä, miten algoritmiset ratkaisijat karsivat hakupuuta.

Yhdistelmällinen räjähdys tekee täydellisestä hausta käytännössä mahdotonta. Tämä todellisuus pakottaa kaikki käytännön toteutukset heuristiikkoihin ja satunnaistettuihin uusintayrityksiin täydellisen läpikäynnin sijaan. Tämän rajoitteen ymmärtäminen on perusta Mahjong-algoritmeille, kun niitä selitetään vakavassa ohjelmistokontekstissa.

Miten todelliset toteutukset luovat ratkeavia Mahjong-tauluja?

Tuotantokäytön Mahjong-ohjelmisto ei yritä todistaa ratkeavuutta ensimmäisistä periaatteista lähtien. Se varmistaa ratkeavuuden kaksikerroksisella järjestelmällä, joka yhdistää nopean taulun rakentamisen ja ratkaisijan, joka tarkistaa tuloksen.

Vakiomalli toimii näin:

• Taso 1: Rakentava generointi. Moottori rakentaa taulun menetelmällä, joka on suunniteltu tuottamaan ratkeavia asetelmia. Tämä on nopeaa, mutta ei takaa onnistumista joka kerta.
• Taso 2: Ratkeavuuden validointi. Ratkaisija ajetaan luodulle taululle. Jos taulu ei läpäise tarkistusta, moottori yrittää uudelleen.
• Uusintasilmukat. Yleiset toteutukset ajavat buildSolvableWithRetries-toimintoa jopa 2 000 yritykseen asti ennen strategian vaihtamista. Tämä määrä perustuu empiiriseen säätöön, ei teoreettiseen välttämättömyyteen.
• Vaihtoehtoiset strategiat. Kun ensisijainen uusintabudjetti on käytetty loppuun, moottori vaihtaa toiseen rakennusalgoritmiin, jolla on oma uusintasilmukkansa.
• Satunnaisen taulun vararatkaisu. Jos mikään muu ei auta, moottori luo satunnaisen taulun ja ajaa sille suoran ratkaisun tarkistuksen. Tämä takaa, että aina toimitetaan pelattava taulu.

Vinkki: Jos rakennat Mahjong-pulmageneraattoria, aloita käänteisellä rakentamistavalla: aseta laatat tunnetussa ratkeavassa järjestyksessä ja sekoita sitten rajoitusten puitteissa. Tämä vähentää dramaattisesti tarvittavien uusintayritysten määrää ennen kelvollisen taulun löytymistä.

Alla oleva taulukko tiivistää tuotantokoodissa käytetyn kolmivaiheisen vararatkaisumallin:

Tämä kaksikerroksinen järjestelmä, jossa on toistuvia uusintayrityksiä ja varastrategioita, on tuotantotason standardi ratkeavien pulmataulujen toimittamiseen. Tässä suunnittelutapa on harkittu: älä todista ratkeavuutta etukäteen. Rakenna nopeasti, varmista nopeasti ja yritä uudelleen tarvittaessa. Tämä lähestymistapa vastaa sitä, mitä monimutkaisuusteoria ennustaa. Tarkat todistukset ovat kalliita. Varmistus on halpaa.

Miten ratkeavuuden tuntemus parantaa Mahjong-pelistrategioita ja suunnittelua?

Ratkeavuuden ymmärtäminen muuttaa sekä sitä, miten kehittäjät rakentavat pelejä, että sitä, miten pelaajat lähestyvät Mahjong-pulmien ratkaisemista. Nämä kaksi näkökulmaa vahvistavat toisiaan.

Pelaajastrategian näkökulmasta ratkeavuusnäkemykset muuttuvat suoraan paremmaksi päätöksenteoksi:

• Priorisoi näkyvissä olevat laatat, joilla on vähän pareja. Jos laatalla on vain yksi saavutettava pari, tuo paritus on tehtävä jossain vaiheessa. Viivyttely voi lukita taulun.
• Vältä laataryhmien eristämistä. Laattojen poistaminen niin, ettei se paljasta uusia laattoja, vähentää tulevia vaihtoehtojasi parantamatta asemaasi. Tätä käsitellään perusteellisesti laattojen eristämisen yhteydessä ja siinä, miksi se heikentää ratkeavuutta.
• Ajattele kerroksittain, älä yksittäisinä siirtoina. Ratkeavuus riippuu koko taulun kattavista parituspäätöksistä. Pelaajat, jotka suunnittelevat kaksi tai kolme siirtoa eteenpäin, suoriutuvat johdonmukaisesti paremmin kuin ne, jotka reagoivat yksittäisiin tilaisuuksiin.
• Käytä sekoitustoimintoja strategisesti. Useimmissa digitaalisissa Mahjong-peleissä on sekoitus- tai vihjetoiminto. Nämä ominaisuudet tukeutuvat samoihin ratkeavuusalgoritmeihin taustalla varmistaakseen, että kelvollinen polku on yhä olemassa.

Pelisuunnittelun näkökulmasta ratkeavuusalgoritmit määrittävät pelaajakokemuksen laadun:

• Asetelmat, jotka luodaan ilman ratkeavuustarkistuksia, tuottavat usein voittamattomia tauluja. Pelaajat, jotka kohtaavat tällaisia, menettävät luottamuksensa peliin, eivät omaan taitoonsa.
• Laattojen sijoittelu vaikuttaa suoraan vaikeustasoon. Suunnitelmat, jotka paljastavat vähemmän laattoja alussa, pakottavat pelaajat kapeampiin päätöspuihin ja lisäävät Mahjong-pulmien ratkaisemisen käytännön monimutkaisuutta.
• Piilotetun tiedon versiot, joissa laattojen kuviot ovat piilossa kunnes ne paljastuvat, siirtävät ongelman NP-täydellisestä päätöksenteosta todennäköisyyspohjaiseen päättelyyn. Tämä muuttaa pelin luonteen täysin.
• Kehittäjät, jotka ymmärtävät Mahjongin tekoälyalgoritmeja, voivat säätää vaikeustasoa muuttamalla sitä, kuinka aggressiivisesti rakentava generaattori suosii asetelmia, joilla on useita kelvollisia ratkaisupolkuja.

Yhteys algoritmisen teorian ja pelaajakokemuksen välillä on suora. Taulu, joka on luotu vankalla ratkeavuusalgoritmilla, antaa sinulle reilun pulman. Taulu, joka on luotu ilman sellaista, voi olla mahdoton, etkä koskaan tiedä miksi epäonnistuit.

Keskeiset huomiot

Mahjongin ratkeavuusalgoritmi on päätösongelmissa NP-täydellinen ja optimointiongelmissa PSPACE-täydellinen, mikä tekee heuristiset ja uusintayrityksiin perustuvat menetelmät ainoaksi käytännölliseksi tavaksi tuottaa ratkeavia tauluja tuotanto-ohjelmistoissa.

Miksi teoria yksin ei auta sinua rakentamaan parempaa Mahjong-peliä

Olen käyttänyt huomattavasti aikaa siihen, miten Mahjongin ratkeavuus toteutetaan käytännössä, ja kuilu akateemisten monimutkaisuustulosten ja sen välillä, mitä insinöörit todella julkaisevat, on silmiinpistävä. NP-täydellisyyden ja PSPACE-täydellisyyden todistukset ovat älyllisesti tyydyttäviä. Ne kertovat sinulle jotain totta ja tärkeää ongelmasta. Mutta ne eivät kerro, miten rakennetaan peli, josta pelaajat nauttivat.

Olen havainnut, että uusintayrityksiin perustuva lähestymistapa ei ole kompromissi. Se on oikea vastaus tämän luokan ongelmaan. Kun hakutilassasi on 150 biljardia konfiguraatiota, sinun ei tarvitse tutkia niitä kaikkia. Tarvitset nopean generaattorin, joka onnistuu suurimman osan ajasta, halvan varmistajan, joka havaitsee epäonnistumiset, ja vararatkaisun, joka takaa toimituksen. Tuo arkkitehtuuri on tuotannossa luotettavampi kuin mikään tarkka ratkaisija olisi.

Oivallus siitä, että siirtojärjestys ei vaikuta ratkeavuuteen, kun parit on kerran määrätty, on tämän alueen aliarvostetuin tulos. Se tarkoittaa, että näennäisesti peräkkäisen ongelman voi pelkistää yhdistelmälliseksi ongelmaksi, ja yhdistelmälliset ongelmat reagoivat hyvin rajoitepropagointiin ja karsintaan. Jos rakennat Mahjong-ratkaisijaa tai tutkit pulmapelien monimutkaisuutta, aloita siitä.

Neuvoni kaikille, jotka haluavat toteuttaa ratkeavuuden tarkistuksen: älä aloita monimutkaisuuskirjallisuudesta. Aloita toimivalla uusintasilmukalla, mittaa, kuinka usein kukin varavaihe laukeaa, ja säädä sen perusteella. Teoria kertoo katon. Mittaus kertoo, missä todella olet.

— Dmytro Romaniuk

Pelaa Mahjong-pulmia, jotka perustuvat ratkeavien taulujen generointiin

Jokainen Mahjong Online Clubin pulma luodaan tässä artikkelissa kuvatulla ratkeavuus ensin -lähestymistavalla. Yhtäkään taulua ei tarjota sinulle ilman, että se läpäisee ratkaisijan validointivaiheen. Tämä tarkoittaa, että jokainen aloittamasi peli on voitettavissa, ja jokainen epäonnistuminen on strategiaongelma, ei rikkinäinen asetelma.

Voit pelata ilmaista Mahjongia suoraan selaimessasi ilman rekisteröitymistä. Alusta on rakennettu häiriöttömän kokemuksen ympärille, jotta keskittyminen ja kuvioiden tunnistaminen onnistuvat. Jos haluat soveltaa tässä kuvattuja algoritmisia käsitteitä käytäntöön, tämä on oikea paikka siihen.

Usein kysytyt kysymykset

Mikä on Mahjongin ratkeavuusalgoritmi?

Mahjongin ratkeavuusalgoritmi on laskennallinen menetelmä, joka määrittää, voidaanko Mahjong-pasianssitaulu tyhjentää kokonaan yhdistämällä ja poistamalla kaikki laatat pareittain. Tämän ongelman päätösversio on muodollisesti NP-täydellinen täydellisen informaation tapauksessa.

Miten Mahjongin ratkeavuus toimii matemaattisesti?

Ratkeavuus riippuu paritusvalinnoista 36 laatkategorian yli, joista jokainen tarjoaa 3 mahdollista paritusta, mikä tuottaa noin 150 biljardia kokonaiskonfiguraatiota. Koska siirtojärjestys ei muuta lopputulosta, kun parit on kerran määrätty, ratkaisijat keskittyvät paritusrajoitteisiin eivätkä siirtosekvensseihin.

Miksi ohjelmisto ei voi ratkaista Mahjong-tauluja täsmällisesti joka kerta?

Tarkan ratkeavuuden tarkistaminen vaatii pahimmillaan eksponentiaalista laskentaa, mikä on epäkäytännöllistä reaaliaikaisille pelimoottoreille. Tuotantojärjestelmät käyttävät rakentavia generaattoreita, joissa on jopa 2 000 yrityksen uusintasilmukat ja varavaiheita, jotta pelattava taulu voidaan taata ilman tarkkaa todistusta.

Mikä on ero NP-täydellisen ja PSPACE-täydellisen välillä Mahjongissa?

Päätösongelma (voiko tämän taulun tyhjentää?) on NP-täydellinen. Optimointiongelma (mikä siirtojono maksimoi tyhjentymistodennäköisyyden?) on PSPACE-täydellinen, mikä on selvästi vaikeampi luokka ja sulkee pois myös tehokkaat approksimaatioalgoritmit.

Miten Mahjong-pelistrategiat liittyvät ratkeavuusalgoritmeihin?

Pelaajat, jotka priorisoivat laattoja, joilla on vain vähän saavutettavia pareja, ja välttävät laataryhmien eristämistä, soveltavat samaa rajoitteiden karsintalogiikkaa, jota algoritmiset ratkaisijat käyttävät. Ratkeavuuden rakenteen ymmärtäminen tekee strategisista päätöksistä harkitumpia ja vähemmän arvailuun perustuvia.

Suositellut

• Miten pelata Mahjong-pasianssia — säännöt, laatat ja strategia
• Miksi laattojen eristäminen pilaa Mahjong-pelit kaikilta pelaajilta
• Mahjong Titans -huijaukset: ratkaisijat, vihjeet ja lailliset oikotiet
• Mikä on Mahjongin tavoite? Säännöt ja strategia