Mahjong atrisināmības algoritms: kā tas darbojas

Mahjong atrisināmības algoritms ir lēmumu procedūra, kas nosaka, vai konkrētu Mahjong pasjansa dēli var pilnībā notīrīt, secīgi saskaņojot un noņemot flīžu pārus saskaņā ar spēles noteikumiem. Saprast, ko nozīmē Mahjong atrisināmības algoritms, nozīmē saskarties ar vienu no interesantākajām kombinatorisko spēļu teorijas problēmām: šis jautājums formāli ir NP-pilnīgs pie pilnas informācijas, kas nozīmē, ka nav zināms algoritms, kas to visiem iespējamiem dēļu izkārtojumiem atrisinātu efektīvi. Reālajā programmatūrā šo barjeru apiet ar heiristikām, atkārtotiem mēģinājumiem un rezerves stratēģijām. Tieši plaisā starp teorētisko sarežģītību un praktisko lietojamību notiek visvērtīgākais inženiertehniskais darbs.

Ko mums par Mahjong atrisināmību pasaka skaitļošanas sarežģītība?

Skaitļošanas sarežģītība ir formāla pētījumu joma par to, cik grūti datoram ir atrisināt kādu problēmu. Šeit vissvarīgākās ir divas sarežģītības klases: NP un PSPACE.

NP-pilnīgs raksturo problēmas, kurās risinājuma pārbaude ir ātra, bet tā atrašana var prasīt eksponenciālu laiku. Mahjong pasjanss ar pilnu informāciju lēmuma problēmas ziņā ir NP-pilnīgs: ja dēļa flīžu pozīcijas ir zināmas, vai visas flīzes var noņemt? Šis rezultāts nozīmē, ka nav algoritma, kas garantēti spētu ātri atbildēt uz šo jautājumu katram iespējamajam izkārtojumam.

PSPACE-pilnīgs ir vēl grūtāka klase. Noņemšanas varbūtības maksimizēšana ir PSPACE-pilnīga un PSPACE-grūti aproksimējama ar koeficientu n, kas pacelts jebkurā pozitīvā konstantē. Šis rezultāts izslēdz pat aptuvenus risinājumus, kas darbotos polinoma laikā, ja vien nesabrūk skaitļošanas sarežģītības teorijas pamatpieņēmumi.

Praksē šie divi rezultāti nozīmē sekojošo:

• Lēmuma versija (vai šo dēli var notīrīt?) ir NP-pilnīga. Precīzi risinātāji sliktākajā gadījumā saskaras ar eksponenciālu laiku.
• Optimizācijas versija (kura secība maksimizē notīrīšanas varbūtību?) ir PSPACE-pilnīga. Tā ir stingri grūtāka nekā lēmuma versija.
• Precīzai atrisināmības pārbaudei sliktākajā gadījumā vajadzīga eksponenciāla vai atmiņietilpīga skaitļošana. Praktiskie risinātāji paļaujas uz heiristikām vai izkārtojuma ierobežojumiem.
• Atrisināmība ir atkarīga no problēmas formulējuma un spēles modeļa. Nav viena universāla algoritma, kas derētu visiem Mahjong variantiem.

Galvenā mācība no sarežģītības teorijas nav tā, ka Mahjong nav atrisināms. Tā ir tāda, ka to precīzi atrisināt patvaļīgiem dēļiem ir skaitļošanas ziņā tik dārgi, ka neviens ražošanas spēļu dzinējs to nemēģina darīt tieši.

Šī atšķirība ietekmē katru dizaina lēmumu Mahjong programmatūrā. Izstrādātāji negaida formāli pierādītu atbildi. Viņi veido sistēmas, kas ar lielu varbūtību ģenerē atrisināmus dēļus, un pēc tam pārbauda, nevis pierāda.

Kā tiek modelēta atrisināmība un kāpēc svarīga ir kombinatoriskā eksplozija?

Mahjong pasjansa matemātiskā struktūra balstās uz flīžu pārošanu. Katra flīze pieder vienai no 36 kategorijām, un katrā kategorijā ir tieši četras flīzes. Lai notīrītu dēli, katrai flīzei jāatrod pāris no vienas no trim identiskajām flīzēm.

Šeit ir galvenais kombinatoriskais izaicinājums soli pa solim:

1. Saskaitiet pārošanas iespējas. Jebkurai četru identisku flīžu grupai ir tieši trīs veidi, kā tās sadalīt divos pāros.
2. Reiziniet pāri visām kategorijām. Ar 36 kategorijām un 3 iespējām katrā kopējais pārošanas konfigurāciju skaits ir 3^36, aptuveni 1,5 × 10^17. Tas ir apmēram 150 kvadriljoni kombināciju.
3. Atzīstiet pilnīgas meklēšanas neiespējamību. Pārbaudīt katru konfigurāciju pat ar vienu miljardu darbību sekundē prasītu vairāk nekā četrus gadus nepārtrauktas skaitļošanas. Neviens spēļu dzinējs to nevar atļauties katram dēlim.
4. Nošķiriet pārošanu no gājienu secības. Noņemšanas secība, kad pāri ir fiksēti, neietekmē gala atrisināmības rezultātu. Tas ir būtisks ieskats. Tas nozīmē, ka meklēšanas telpu nosaka pārošanas izvēles, nevis gājienu secība.
5. Koncentrējiet meklēšanu uz pārošanas modeļiem. Stāvokļu telpas samazināšana, pārformulējot spēli kā pārošanas un noņemšanas atkarību problēmu, samazina sarežģītību. Telpa joprojām ir liela, taču tā ir daudz pārvaldāmāka nekā katras iespējamās gājienu secības izsekošana.
6. Pielietojiet iepriekšēju kompresiju. Efektīvi risinātāji koncentrējas uz to, kuras flīzes ir pieejamas, ņemot vērā pašreizējo dēļa izkārtojumu, un apgriež zarus, kuros bloķētas flīzes padara pārošanu fiziski neiespējamu neatkarīgi no abstraktās pārošanas izvēles.

Padoms: Analizējot Mahjong dēli manuāli, domājiet pārošanas saistību, nevis atsevišķu gājienu kategorijās. Nosakiet, kurām flīzēm ir tikai viens pieejams derīgs partneris, un vispirms nostipriniet šos pārus. Tas atspoguļo to, kā algoritmiskie risinātāji apgriež meklēšanas koku.

Kombinatoriskā eksplozija padara pilnīgu meklēšanu nepraktisku. Šī realitāte piespiež jebkuru praktisku ieviešanu virzīties uz heiristikām un nejaušinātām atkārtotu mēģinājumu stratēģijām, nevis pilnīgu uzskaitīšanu. Šī ierobežojuma izpratne ir pamats Mahjong algoritmu skaidrojumam jebkurā nopietnā programmatūras kontekstā.

Kā reālās ieviešanas ģenerē atrisināmus Mahjong dēļus?

Ražošanas Mahjong programmatūra nemēģina pierādīt atrisināmību no pirmajiem principiem. Tā pārbauda atrisināmību, izmantojot divslāņu sistēmu, kas apvieno ātru dēļa izveidi ar risinātāju, kas pārbauda rezultātu.

Standarta arhitektūra darbojas šādi:

• 1. slānis: konstruktīva ģenerēšana. Dzinējs veido dēli, izmantojot metodi, kas paredzēta atrisināmu izkārtojumu radīšanai. Tas ir ātri, taču ne vienmēr izdodas.
• 2. slānis: atrisināmības validācija. Uz ģenerētā dēļa tiek palaists risinātājs. Ja dēlis neiztur pārbaudi, dzinējs mēģina vēlreiz.
• Atkārtotu mēģinājumu cikli. Bieži izmantotas ieviešanas palaiž buildSolvableWithRetries līdz pat 2 000 mēģinājumiem, pirms pāriet uz citām stratēģijām. Šis skaitlis atspoguļo empīrisku pielāgošanu, nevis teorētisku nepieciešamību.
• Alternatīvas stratēģijas. Pēc primārā mēģinājumu budžeta iztērēšanas dzinējs pārslēdzas uz citu izveides algoritmu ar savu atkārtotu mēģinājumu ciklu.
• Nejauša dēļa rezerves variants. Ja nekas cits nepalīdz, dzinējs ģenerē nejaušu dēli un tieši palaiž uz tā atrisināšanas pārbaudi. Tas garantē, ka vienmēr tiek piegādāts spēlējams dēlis.

Padoms: Ja veidojat Mahjong mīklu ģeneratoru, sāciet ar reversās konstrukcijas pieeju: novietojiet flīzes zināmā atrisināmā secībā un pēc tam sajauciet tās noteikto ierobežojumu robežās. Tas būtiski samazina nepieciešamo atkārtoto mēģinājumu skaitu, līdz tiek atrasts derīgs dēlis.

Tālāk esošā tabula apkopo trīs posmu rezerves modeli, ko izmanto ražošanas kodu bāzēs:

Šī divslāņu sistēma ar atkārtotiem mēģinājumiem un rezerves stratēģijām ir ražošanas standarts atrisināmu mīklu dēļu piegādei. Inženiertehniskā pieeja šeit ir apzināta: nepierādīt atrisināmību iepriekš. Veidot ātri, pārbaudīt ātri un vajadzības gadījumā mēģināt vēlreiz. Šī pieeja atbilst tam, ko paredz sarežģītības teorija. Precīzi pierādījumi ir dārgi. Pārbaude ir lēta.

Kā atrisināmības zināšanas uzlabo Mahjong spēles stratēģijas un dizainu?

Izpratne par to, kā darbojas atrisināmība, maina gan to, kā izstrādātāji veido spēles, gan to, kā spēlētāji pieiet Mahjong mīklu risināšanai. Šīs divas perspektīvas viena otru pastiprina.

No spēlētāja stratēģijas viedokļa atrisināmības ieskati tieši pārtop labākā lēmumu pieņemšanā:

• Dodiet priekšroku atklātām flīzēm ar ierobežotu partneru skaitu. Ja flīzei ir tikai viens pieejams pāris, šis pāris kādā brīdī būs jāizveido. Vilcināšanās var bloķēt dēli.
• Izvairieties no flīžu grupu izolēšanas. Noņemot flīzes, kas neatklāj jaunas flīzes, jūs samazināt nākotnes iespējas, neuzlabojot savu pozīciju. Šis jēdziens detalizēti aplūkots flīžu izolācijas kontekstā un tajā, kāpēc tā grauj atrisināmību.
• Domājiet slāņos, nevis atsevišķos gājienos. Atrisināmība ir atkarīga no pārošanas saistībām visā dēlī. Spēlētāji, kas plāno divus vai trīs gājienus uz priekšu, konsekventi pārspēj tos, kas reaģē tikai uz vienas flīzes iespējām.
• Stratēģiski izmantojiet sajaukšanas funkcijas. Lielākajā daļā digitālo Mahjong spēļu ir sajaukšanas vai padoma funkcija. Šīs funkcijas fonā izmanto tos pašus atrisināmības algoritmus, lai apstiprinātu, ka joprojām pastāv derīgs ceļš.

No spēles dizaina viedokļa atrisināmības algoritmi nosaka spēlētāja pieredzes kvalitāti:

• Izkārtojumi, kas ģenerēti bez atrisināmības pārbaudēm, bieži rada neuzvaramus dēļus. Spēlētāji, kas ar tiem sastopas, zaudē uzticību spēlei, nevis savām prasmēm.
• Flīžu izvietojums tieši ietekmē grūtības pakāpi. Dizaini, kas agrīni atklāj mazāk flīžu, piespiež spēlētājus šaurākos lēmumu kokos, palielinot Mahjong mīklu risināšanas efektīvo sarežģītību.
• Varianti ar slēptu informāciju, kuros flīžu sejas ir paslēptas līdz atklāšanai, pārceļ problēmu no NP-pilnīgas lēmumu pieņemšanas uz varbūtisku spriešanu. Tas pilnībā maina spēles raksturu.
• Izstrādātāji, kas saprot Mahjong mākslīgā intelekta algoritmus, var pielāgot grūtības pakāpi, mainot to, cik agresīvi konstruktīvais ģenerators dod priekšroku izkārtojumiem ar vairākiem derīgiem risinājuma ceļiem.

Saikne starp algoritmisko teoriju un spēlētāja pieredzi ir tieša. Dēlis, kas ģenerēts ar robustu atrisināmības algoritmu, sniedz godīgu mīklu. Dēlis, kas ģenerēts bez tā, var būt neiespējams, un jūs nekad neuzzināsiet, kāpēc izgāzāties.

Galvenie secinājumi

Mahjong atrisināmības algoritms lēmuma problēmām ir NP-pilnīgs, bet optimizācijas problēmām — PSPACE-pilnīgs, tāpēc heiristiskas un uz atkārtotiem mēģinājumiem balstītas metodes ir vienīgais praktiskais ceļš uz atrisināmiem dēļiem ražošanas programmatūrā.

Kāpēc ar teoriju vien nepietiks, lai izveidotu labāku Mahjong spēli

Es esmu pavadījis ievērojamu laiku, analizējot, kā Mahjong atrisināmība tiek ieviesta praksē, un plaisa starp akadēmiskajiem sarežģītības rezultātiem un to, ko inženieri patiešām piegādā, ir pārsteidzoša. NP-pilnības un PSPACE-pilnības pierādījumi ir intelektuāli apmierinoši. Tie pasaka kaut ko patiesu un svarīgu par problēmu. Taču tie nepasaka, kā izveidot spēli, kas spēlētājiem patīk.

Tas, ko esmu secinājis, ir tas, ka pieeja ar atkārtotiem mēģinājumiem nav kompromiss. Tā ir pareizā atbilde šai problēmu klasei. Ja jūsu meklēšanas telpā ir 150 kvadriljoni konfigurāciju, jums nav jāizpēta tās visas. Jums vajag ātru ģeneratoru, kas lielākoties izdodas, lētu pārbaudītāju, kas noķer neveiksmes, un rezerves mehānismu, kas garantē piegādi. Šāda arhitektūra ražošanā ir uzticamāka nekā jebkurš precīzs risinātājs.

Ieskats, ka gājienu secība neietekmē atrisināmību, kad pāri ir fiksēti, ir visvairāk nenovērtētais rezultāts šajā jomā. Tas nozīmē, ka šķietami secīgu problēmu var reducēt uz kombinatorisku, un kombinatoriskas problēmas labi reaģē uz ierobežojumu izplatīšanu un apgriešanu. Ja veidojat Mahjong risinātāju vai pētāt mīklu spēļu sarežģītību, sāciet tur.

Mans padoms ikvienam, kas vēlas ieviest atrisināmības pārbaudi: nesāciet ar sarežģītības literatūru. Sāciet ar strādājošu atkārtotu mēģinājumu ciklu, aprīkojiet to ar mērījumiem, lai redzētu, cik bieži aktivizējas katrs rezerves posms, un pēc tam pielāgojiet. Teorija pasaka griestus. Mērījumi pasaka, kur jūs patiesībā atrodaties.

— Dmytro Romaniuk

Spēlējiet Mahjong mīklas, kas balstītas uz atrisināmu dēļu ģenerēšanu

Katra mīkla Mahjong Online Club tiek ģenerēta, izmantojot tieši tādu atrisināmību vispirms pieeju, kā aprakstīts šajā rakstā. Neviens dēlis jums netiek piedāvāts, pirms tas nav izgājis risinātāja validācijas soli. Tas nozīmē, ka katra spēle, ko sākat, ir uzvarama, un katra neveiksme ir stratēģijas problēma, nevis bojāts izkārtojums.

Jūs varat spēlēt bezmaksas Mahjong tieši pārlūkprogrammā bez reģistrācijas. Platforma ir veidota ap pieredzi bez traucēkļiem, lai atbalstītu koncentrēšanos un modeļu atpazīšanu. Ja vēlaties šeit aprakstītās algoritmiskās koncepcijas pielietot praksē, šī ir īstā vieta.

BUJ

Kas ir Mahjong atrisināmības algoritms?

Mahjong atrisināmības algoritms ir skaitļošanas procedūra, kas nosaka, vai Mahjong pasjansa dēli var pilnībā notīrīt, saskaņojot un noņemot visus flīžu pārus. Šīs problēmas lēmuma versija formāli ir NP-pilnīga pie pilnas informācijas.

Kā matemātiski darbojas Mahjong atrisināmība?

Atrisināmība ir atkarīga no pārošanas izvēlēm 36 flīžu kategorijās, katrā no kurām ir 3 iespējamie pāri, kopā veidojot aptuveni 150 kvadriljonus konfigurāciju. Tā kā gājienu secība nemaina rezultātu, kad pāri ir fiksēti, risinātāji koncentrējas uz pārošanas ierobežojumiem, nevis gājienu secībām.

Kāpēc programmatūra nevar katru reizi precīzi atrisināt Mahjong dēļus?

Precīzai atrisināmības pārbaudei sliktākajā gadījumā vajadzīga eksponenciāla skaitļošana, kas reāllaika spēļu dzinējiem ir nepraktiska. Ražošanas sistēmas izmanto konstruktīvus ģeneratorus ar atkārtotu mēģinājumu cikliem līdz 2 000 mēģinājumiem un rezerves posmiem, lai garantētu spēlējamu dēli bez precīza pierādījuma.

Kāda ir atšķirība starp NP-pilnīgu un PSPACE-pilnīgu Mahjong kontekstā?

Lēmuma problēma (vai šo dēli var notīrīt?) ir NP-pilnīga. Optimizācijas problēma (kura secība maksimizē notīrīšanas varbūtību?) ir PSPACE-pilnīga, kas ir stingri grūtāka klase un arī izslēdz efektīvus aproksimācijas algoritmus.

Kā Mahjong spēles stratēģijas saistās ar atrisināmības algoritmiem?

Spēlētāji, kas prioritizē flīzes ar ierobežotu pieejamo partneru skaitu un izvairās no flīžu grupu izolēšanas, izmanto to pašu ierobežojumu apgriešanas loģiku, ko izmanto algoritmiskie risinātāji. Izpratne par to, kā ir strukturēta atrisināmība, padara stratēģiskos lēmumus apzinātākus un mazāk atkarīgus no minējumiem.

Ieteicamie

• Kā spēlēt Mahjong pasjansu — noteikumi, flīzes un stratēģija
• Kāpēc flīžu izolācija sabojā Mahjong spēles visiem spēlētājiem
• Mahjong Titans čīti: risinātāji, padomi un godīgi īsceļi
• Kāds ir Mahjong mērķis? Noteikumi un stratēģija