Perché non si può giocare due volte la stessa partita? (...) E chi mi assicura che tutte le partite siano realmente risolvibili?In effetti queste domande se le sono poste diversi ricercatori nel campo della matematica, in particolare dei giochi combinatori, e dell'informatica e, in un certo senso, hanno adottato un approccio non molto diverso da quello del personaggio ideato da Vismara, ma solo un po' più raffinato. Infatti il personaggio letterario si è stampato tutti gli screenshot di tutti isolitari che ha giocato nel corso degli anni, mentre i ricercatori hanno fatto compiere qualcosa di simile al computer, che ha esaminato, dopo opportuna matematizzazione del problema, tutte le possibili configurazioni. Andiamo, però, con ordine raccontando qualcosa sul gioco stesso.
Dalle carte al computer
Il mahjong è un gioco di origine cinese probabilmente ideato a metà del XIX secolo come variazione di alcuni giochi di carte, in particolare il Mádìao. Come ricorda in maniera molto sintetica, ma efficace, la Wiki in italiano, eistono tre ipotesi principali sulle sue origini: creato da alcuni ufficiali dell'esercito cinese nel corso della Ribellione di Tai Ping (1851-1864); o forse fu un nobile di Shanghai fra il 1870 e il 1875; o ancora due fratelli di Ningbo attorno al 1850. In effetti molti aspetti del gioco farebbero pensare soprattutto all'origine militare, ma nulla è certo.
I primi riferimenti occidentali al gioco risalgono alla fine del XIX secolo, ma la sua espansione inizia con gli anni Venti del XX secolo a partire dagli Stati Uniti. Con la sua diffusione nel mondo, nascono diverse varianti, quasi una per ciascuna nazione in cui attecchisce, inclusa una variante italiana, o romagnola. Dal gioco di carte originario prende anche l'abitudine di fare puntate, cosa che lo ha fatto classificare come gioco d'azzardo dal primo governo della Repubblica popolare cinese, nel 1949, che tra l'altro considerandolo di origine occidentale decise di bandirlo. La riscoperta della sua storia nel corso della rivoluzione culturale della seconda metà degli anni Sessanta riabilitò il gioco, che tornò a essere ampiamente diffuso tra i cinesi.
Il gioco prevede la presenza di 4 giocatori, ma esistono anche variazioni a 3 e 2 giocatori. E persino una versione "solitario", che è quella da cui siamo partiti, diventata molto diffusa proprio grazie alla diffusione dei computer, dove si trovava all'interno sovente installata.
Formazione a tartaruga
Questa variante elettronica del mahjong, che utilizza 144 tessere sistemate su quattro strati, venne ideato da Brodie Lockard nel 1981. Oltre al mahjong, il gioco era basato, almeno stando a quanto asserì il creatore, da un altro gioco tradizionale cinese, la tartaruga. E infatti la configurazione con cui per diversi anni tutti i mahjong elettronici iniziavano è nota proprio come formazione a tartaruga.
Scopo del solitario è quello di togliere tutte le tessere della configurazione, eliminandole a due a due a patto che siano uguali e poste sui bordi di uno qualsiasi degli strati.
Dal punto di vista della combinatoria, il mahjong solitario è piuttosto complesso: nell'ipoitesi in cui il giocatore conosca comunque la posizione di ciascuna tessera, trovare una soluzione al solitario, ovvero far scomparire tutte le tessere, è un problema NP-completo, ovvero i problemi più difficili appartenenti alla classe NP. Questi ultimi sono problemi risolvibili in tempo polinomiale da un algoritmo, dove per tempo polinomiale si intende una durata di tempo calcolabile con un polinomio.
A dimostrazione prattica di questo fatto, come mostrato da Michiel de Bondt sia su Solving Mahjong Solitaire boards with peeking, sia sulla pagina Solitaire Mahjongg solver, si sa che il 3% delle "tartarughe" non è risolvibile anche conoscendo la disposizione di tutte le tessere, incluse quelle nascoste. E' interessante, osservando l'elenco, come ci sono alcune disposizioni impossibili da risolvere, ovvero quelle denominate come hourglass e papillon.
Abbiamo, quindi, ottenuto la risposta alla seconda domanda, ovvero non tutte le configurazioni sono risolvibili, ma questo dipende soprattutto dalla formazione di partenza.
Per rispondere alla prima domanda, invece, rielaboriamola in un modo leggermente differente, ovvero chiediamoci quante configurazioni possibili si possono realizzare. In questo caso ci viene in soccorso Jan van Rijn che in Mahjong Solitaire Computing the number of unique and solvable arrangements (pdf) ha effettivamente calcolato il numero di configurazioni possibili al variare della dimensione dell'insieme delle tessere del mahjong, trovando che per un insieme costituito da 100 tessere 635111413 configurazioni, che si possono ridurre a 317880216 configurazioni per riflessione.
Più complesso degli scacchi?
E' inevitabile, dopo quanto scritto fino a ora, porsi una nuova domanda, ovvero se il mahjong sia più complessi degli scacchi e del go. Per approcciare il problema partiamo da Mathematical aspect of the combinatorial game "Mahjong" che affronta non già il solitario, ma proprio il gioco a due o più giocatori.
Spulciando l'articolo, gli autori sembrano suggerire, anche se non lo scrivono esplicitamente, che dal punto di vista computazionale affrontare il mahjong è una sfida che si potrebbe rivelare più complessa, anche se indubbiamente molto interessante. Questa maggiore complessità, che però non vuol dire che non sia fattibile, soprattutto partendo dai risultati ottenuti con gli scacchi e il go, è sostanzialmente dovuta alle peculiarità del mahjong.
Innanzitutto i giocatori non hanno tutte le informazioni sulle tessere in mano ai loro avversari. Dunque devono compiere un esercizio di previsione molto più complesso e in qualche modo più creativo nella costruzione del loro piano di gioco. Inoltre c'è la possibilità di realizzare delle alleanze di due o tre giocatori.
Quindi, giocare bene a Mahjong richiede un buon uso della teoria combinatoria, della teoria della probabilità, della teoria dei giochi, della psicologia, ecc. Per sviluppare una buona macchina per giocare a Mahjong sarà necessario un altro livello di intelligenza.Un ottimo risultato nella realizzazione di un software in grado di giocare con efficacia il mahjong viene descritto in Imperfect-Information Game AI Agent Based on Reinforcement Learning Using Tree Search and a Deep Neural Network, che però ha il problema di un tempo di calcolo e di un uso delle risorse ancora eccessivamente alto. Ovviamente l'idea dei ricercatori è anche quella di estendere l'approccio di addestramento anche ad altri giochi, immagino scacchi e go.
C'è poi la questione delle molte varianti, come per esempio il bloody mahjong, una variante ancora più complicata del mahjong particolarmente diffura in Cina. In questo caso i ricercatori sono riusciti ad addestrare una rete neurale in grado di giocare come un essere umano, utilizzando contemporaneamente più di un modello di addestramento.
I risultati con il mahjong e le sue varianti suggeriscono che gli sviluppi delle ricerche sulle reti neurali nei giochi, in particolare quelli combinatori, non hanno ancora raggiunto il loro livello massimo.
Nessun commento:
Posta un commento