Algorisme de resolubilitat del Mahjong: com funciona

Un algorisme de resolubilitat del Mahjong és un procediment de decisió que determina si un tauler determinat de Mahjong solitari es pot buidar completament aparellant i eliminant parelles de fitxes de manera seqüencial segons les regles del joc. Entendre què és un algorisme de resolubilitat del Mahjong implica enfrontar-se a un dels problemes més interessants de la teoria de jocs combinatoris: la qüestió és formalment NP-completa sota informació perfecta, cosa que significa que no es coneix cap algorisme que la resolgui eficientment per a totes les configuracions possibles del tauler. El programari real esquiva aquesta barrera amb heurístiques, bucles de reintent i estratègies de reserva. La bretxa entre la dificultat teòrica i la jugabilitat pràctica és בדיוק on passa l’enginyeria més útil.

Què ens diu la complexitat computacional sobre la resolubilitat del Mahjong?

La complexitat computacional és l’estudi formal de com de difícil és per a un ordinador resoldre un problema. Aquí hi ha dues classes de complexitat que importen més: NP i PSPACE.

NP-completa descriu problemes en què verificar una solució és ràpid, però trobar-ne una pot requerir temps exponencial. El Mahjong solitari amb informació perfecta és NP-complet per al problema de decisió: donat un tauler on totes les posicions de les fitxes són conegudes, es poden eliminar totes les fitxes? Aquest resultat vol dir que no hi ha cap algorisme que garanteixi respondre aquesta pregunta ràpidament per a tots els dissenys possibles.

PSPACE-completa és una classe encara més difícil. Maximitzar la probabilitat d’eliminació és PSPACE-complet i PSPACE-difícil d’aproximar dins d’un factor de n elevat a qualsevol constant positiva. Aquest resultat descarta fins i tot solucions aproximades que funcionin en temps polinòmic, tret que s’ensorren els supòsits fonamentals de la teoria de la complexitat.

Això és el que signifiquen aquests dos resultats a la pràctica:

• La versió de decisió (es pot buidar aquest tauler?) és NP-completa. Els resolutors exactes s’enfronten a un temps exponencial en el pitjor cas.
• La versió d’optimització (quina seqüència maximitza la probabilitat de buidar-lo?) és PSPACE-completa. És estrictament més difícil que la versió de decisió.
• La comprovació exacta de resolubilitat requereix, en el pitjor cas, càlcul exponencial o molt costós en memòria. Els resolutors pràctics depenen d’heurístiques o de restriccions de disseny.
• La resolubilitat depèn de la formulació del problema i del model de joc. No hi ha cap algorisme universal que serveixi per a totes les variants del Mahjong.

La lliçó principal de la teoria de la complexitat no és que el Mahjong sigui irresoluble. És que resoldre’l exactament per a taulers arbitraris és computacionalment prou car perquè cap motor de joc de producció ho intenti directament.

Aquesta distinció modela cada decisió de disseny en el programari de Mahjong. Els desenvolupadors no esperen una resposta provadament correcta. Construeixen sistemes que generen taulers resolubles amb alta probabilitat i després ho verifiquen en lloc de provar-ho.

Com es modela la resolubilitat i per què importa l’explosió combinatòria?

L’estructura matemàtica del Mahjong solitari gira al voltant de l’aparellament de fitxes. Cada fitxa pertany a una de 36 categories, i cada categoria conté exactament quatre fitxes. Per buidar el tauler, cada fitxa s’ha d’aparellar amb una de les seves tres còpies idèntiques.

Aquest és el repte combinatori central, pas a pas:

1. Compta les opcions d’aparellament. Per a qualsevol grup de quatre fitxes idèntiques, hi ha exactament tres maneres d’aparellar-les en dues parelles coincidents.
2. Multiplica-ho per totes les categories. Amb 36 categories i 3 opcions cadascuna, el nombre total de configuracions d’aparellament és 3^36, aproximadament 1,5 × 10^17. Això són aproximadament 150 bilions de bilions de combinacions.
3. Reconeix la impossibilitat de la cerca exhaustiva. Comprovar cada configuració fins i tot a mil milions d’operacions per segon trigaria més de quatre anys de càlcul continu. Cap motor de joc s’ho pot permetre per tauler.
4. Separa l’aparellament de l’ordre dels moviments. L’ordre d’eliminació no afecta el resultat final de la resolubilitat un cop els aparellaments estan fixats. Aquesta és una idea clau. Vol dir que l’espai de cerca el defineixen les opcions d’aparellament, no la seqüència de moviments.
5. Centra la cerca en patrons d’aparellament. La reducció de l’espai d’estats reformulant el joc com un problema de dependència entre aparellament i eliminació redueix la complexitat. L’espai continua sent gran, però és molt més manejable que seguir cada seqüència possible de moviments.
6. Aplica precompressió. Els resolutors eficaços se centren en quines fitxes són accessibles segons el disseny actual del tauler, i poden podar branques on les fitxes bloquejades fan que un aparellament sigui físicament impossible, independentment de l’elecció abstracta d’aparellament.

Consell professional: Quan analitzis manualment un tauler de Mahjong, pensa en termes de compromisos d’aparellament més que no pas de moviments individuals. Identifica quines fitxes tenen només una parella vàlida accessible i fixa primer aquests aparellaments. Això reflecteix com els resolutors algorítmics poden podar l’arbre de cerca.

L’explosió combinatòria fa que la cerca exhaustiva sigui inviable. Aquesta realitat empeny qualsevol implementació pràctica cap a heurístiques i estratègies de reintent aleatori en lloc d’una enumeració completa. Entendre aquesta restricció és la base dels algorismes de Mahjong explicats en qualsevol context seriós de programari.

Com generen els implementacions reals taulers de Mahjong resolubles?

El programari de Mahjong de producció no intenta provar la resolubilitat des de primers principis. La verifica mitjançant un sistema de dues capes que combina una construcció ràpida del tauler amb un resolutor que comprova el resultat.

L’arquitectura estàndard funciona així:

• Capa 1: generació constructiva. El motor construeix un tauler amb un mètode dissenyat per produir dissenys resolubles. És ràpid, però no garanteix l’èxit cada vegada.
• Capa 2: validació de resolubilitat. S’executa un resolutor sobre el tauler generat. Si el tauler no supera la comprovació, el motor ho torna a intentar.
• Bucles de reintent. Les implementacions habituals executen buildSolvableWithRetries fins a 2.000 intents abans de canviar d’estratègia. Aquesta xifra reflecteix una ajustada empírica, no una necessitat teòrica.
• Estratègies alternatives. Després d’esgotar el pressupost principal de reintents, el motor canvia a un altre algorisme de construcció amb el seu propi bucle de reintent.
• Alternativa de tauler aleatori. Si tot falla, el motor genera un tauler aleatori i hi executa directament una comprovació de resolució. Això garanteix que sempre es lliuri un tauler jugable.

Consell professional: Si estàs construint un generador de puzles de Mahjong, comença amb un enfocament de construcció inversa: col·loca les fitxes en un ordre conegut com a resoluble i després barreja-les dins de les restriccions. Això redueix dràsticament el nombre de reintents necessaris abans de trobar un tauler vàlid.

La taula següent resumeix el patró de reserva en tres etapes que s’utilitza en les bases de codi de producció:

Aquest sistema de dues capes amb reintents repetits i estratègies de reserva és l’estàndard de producció per lliurar taulers de puzle resolubles. La mentalitat d’enginyeria aquí és deliberada: no provar la resolubilitat per endavant. Construir ràpid, verificar de pressa i tornar-ho a intentar quan calgui. Aquest enfocament s’alinea amb el que prediu la teoria de la complexitat. Les proves exactes són cares. La verificació és barata.

Com millora el coneixement de la resolubilitat les estratègies i el disseny del joc de Mahjong?

Entendre com funciona la resolubilitat canvia tant la manera com els desenvolupadors creen jocs com la manera com els jugadors s’enfronten als puzles de Mahjong. Les dues perspectives es reforcen mútuament.

Des del punt de vista de l’estratègia del jugador, les idees sobre resolubilitat es tradueixen directament en una millor presa de decisions:

• Prioritza les fitxes exposades amb pocs companys possibles. Si una fitxa només té una coincidència accessible, aquest aparellament s’haurà de fer en algun moment. Posposar-lo pot acabar bloquejant el tauler.
• Evita aïllar grups de fitxes. Eliminar fitxes que no n’exposen de noves redueix les opcions futures sense millorar la posició. Aquest concepte s’explora en profunditat en el context de l’aïllament de fitxes i de com perjudica la resolubilitat.
• Pensa en capes, no en moviments individuals. La resolubilitat depèn de compromisos d’aparellament a tot el tauler. Els jugadors que planifiquen dos o tres moviments per endavant superen de manera constant els que reaccionen a oportunitats d’una sola fitxa.
• Utilitza les funcions de barreja de manera estratègica. La majoria de jocs digitals de Mahjong ofereixen una funció de barreja o d’ajuda. Aquestes funcions depenen dels mateixos algorismes de resolubilitat que s’executen en segon pla per confirmar que encara existeix un camí vàlid.

Des del punt de vista del disseny del joc, els algorismes de resolubilitat determinen la qualitat de l’experiència del jugador:

• Els dissenys generats sense comprovacions de resolubilitat sovint produeixen taulers impossibles de guanyar. Els jugadors que s’hi troben perden la confiança en el joc, no en la seva habilitat.
• La disposició de les fitxes afecta directament la dificultat. Els dissenys que exposen menys fitxes al principi obliguen els jugadors a arbres de decisió més estrets, augmentant la complexitat efectiva de resoldre els puzles de Mahjong.
• Les variants amb informació oculta, en què les cares de les fitxes romanen amagades fins que es descobreixen, desplacen el problema de la presa de decisions NP-completa cap al raonament probabilístic. Això canvia completament el caràcter del joc.
• Els desenvolupadors que entenen els algorismes d’IA per a Mahjong poden ajustar la dificultat modificant fins a quin punt el generador constructiu afavoreix dissenys amb múltiples camins de solució vàlids.

La connexió entre la teoria algorítmica i l’experiència del jugador és directa. Un tauler generat amb un algorisme de resolubilitat robust et dona un puzle just. Un tauler generat sense aquest algorisme pot ser impossible, i mai no sabràs per què has fallat.

Conclusions clau

L’algorisme de resolubilitat del Mahjong és NP-complet per als problemes de decisió i PSPACE-complet per a l’optimització, cosa que fa que els mètodes heurístics i basats en reintents siguin l’únic camí pràctic per obtenir taulers resolubles en programari de producció.

Per què la teoria sola no t’ajudarà a construir un millor joc de Mahjong

He passat força temps analitzant com s’implementa la resolubilitat del Mahjong a la pràctica, i la bretxa entre els resultats acadèmics de complexitat i el que realment publiquen els enginyers és sorprenent. Les proves de NP-completesa i PSPACE-completesa són intel·lectualment satisfactòries. T’expliquen alguna cosa certa i important sobre el problema. Però no t’expliquen com construir un joc que agradi als jugadors.

El que he descobert és que l’enfocament basat en reintents no és un compromís. És la resposta correcta per a aquesta classe de problema. Quan el teu espai de cerca té 150 bilions de bilions de configuracions, no cal explorar-les totes. Necessites un generador ràpid que tingui èxit la major part del temps, un verificador barat que detecti els errors i una reserva que garanteixi el lliurament. Aquesta arquitectura és més fiable en producció que qualsevol resolutor exacte.

La idea que l’ordre dels moviments no afecta la resolubilitat un cop els aparellaments estan fixats és el resultat més infravalorat d’aquest àmbit. Vol dir que pots reduir un problema aparentment seqüencial a un de combinatori, i els problemes combinatoris responen bé a la propagació de restriccions i a la poda. Si estàs construint un resolutor de Mahjong o estudiant la complexitat dels jocs de puzles, comença per aquí.

El meu consell per a qualsevol persona que vulgui implementar la comprovació de resolubilitat: no comencis amb la literatura de complexitat. Comença amb un bucle de reintent que funcioni, instrumenta’l per mesurar amb quina freqüència s’activa cada etapa de reserva i ajusta a partir d’aquí. La teoria et diu el sostre. La mesura et diu on ets realment.

— Dmytro Romaniuk

Juga a puzles de Mahjong basats en la generació de taulers resolubles

Cada puzle de Mahjong Online Club es genera amb el tipus d’enfocament centrat primer en la resolubilitat descrit en aquest article. No se’t serveix cap tauler sense passar per una etapa de validació del resolutor. Això vol dir que cada partida que comences es pot guanyar, i que cada fracàs és un problema d’estratègia, no pas un disseny trencat.

Pots jugar al Mahjong gratuïtament directament al navegador, sense necessitat de registrar-te. La plataforma està pensada per oferir una experiència sense distraccions, dissenyada per afavorir la concentració i el reconeixement de patrons. Si vols posar en pràctica aquí els conceptes algorítmics, aquest és el lloc per fer-ho.

Preguntes freqüents

Què és un algorisme de resolubilitat del Mahjong?

Un algorisme de resolubilitat del Mahjong és un procediment computacional que determina si un tauler de Mahjong solitari es pot buidar completament aparellant i eliminant totes les parelles de fitxes. La versió de decisió d’aquest problema és formalment NP-completa sota informació perfecta.

Com funciona matemàticament la resolubilitat del Mahjong?

La resolubilitat depèn de les opcions d’aparellament entre 36 categories de fitxes, cadascuna amb 3 aparellaments possibles, cosa que produeix aproximadament 150 bilions de bilions de configuracions totals. Com que l’ordre dels moviments no canvia el resultat un cop els aparellaments estan fixats, els resolutors se centren en les restriccions d’aparellament i no en les seqüències de moviments.

Per què el programari no pot resoldre exactament els taulers de Mahjong cada vegada?

La comprovació exacta de resolubilitat requereix un càlcul exponencial en el pitjor cas, cosa que és impracticable per a motors de joc en temps real. Els sistemes de producció utilitzen generadors constructius amb bucles de reintent de fins a 2.000 intents i etapes de reserva per garantir un tauler jugable sense una prova exacta.

Quina diferència hi ha entre NP-complet i PSPACE-complet en el Mahjong?

El problema de decisió (es pot buidar aquest tauler?) és NP-complet. El problema d’optimització (quina seqüència maximitza la probabilitat de buidar-lo?) és PSPACE-complet, una classe estrictament més difícil que també descarta algorismes d’aproximació eficients.

Com es connecten les estratègies de joc de Mahjong amb els algorismes de resolubilitat?

Els jugadors que prioritzen les fitxes amb pocs companys accessibles i eviten aïllar grups de fitxes apliquen la mateixa lògica de poda de restriccions que fan servir els resolutors algorítmics. Entendre com s’estructura la resolubilitat fa que les decisions estratègiques siguin més deliberades i menys dependents de l’atzar.

Recomanat

• Com jugar al Mahjong solitari — regles, fitxes i estratègia
• Per què l’aïllament de fitxes arruïna els jocs de Mahjong per a tots els jugadors
• Trucs de Mahjong Titans: resolutors, pistes i dreceres legítimes
• Quin és l’objectiu del Mahjong? Regles i estratègia