The Winnability of Klondike Solitaire and Many Other Patience Games

Questo studio presenta "Solvitaire", un programma di intelligenza artificiale in grado di calcolare con elevata precisione la percentuale di giocabilità per 73 varianti di 35 giochi di carte solitari, fornendo risultati nuovi o significativamente migliorati, inclusa una stima definitiva per il Klondike.

L'essenziale

🃏 Il Grande Esperimento del Solitario: Chi Vince e Chi No?

Immagina di avere un mazzo di carte e di sederti a giocare a Solitario (quello classico di Windows, chiamato Klondike). Ti chiedi mai: "Quante probabilità ho di vincere questa partita?".
Per decenni, questa domanda è rimasta un mistero imbarazzante per i matematici. Sapevamo che il gioco era popolare, ma non sapevamo se fosse un gioco di fortuna o di abilità, e quanto fosse "ingiusto" il mazzo.

In questo studio, due ricercatori (Charlie Blake e Ian Gent) hanno deciso di risolvere il mistero non giocando a mano, ma creando un super-intelligenza artificiale chiamata "Solvitaire".

🤖 Solvitaire: Il "Super-Giocatore" Infinito

Pensa a Solvitaire non come a un robot che gioca per divertirsi, ma come a un esploratore di labirinti.

• Il problema: Il Solitario è un labirinto enorme. Ogni mossa apre nuove strade, ma molte portano a vicoli ciechi.
• La soluzione: Solvitaire è un esploratore che non si stanca mai. Può provare milioni di percorsi in un secondo. Se un percorso porta alla vittoria, lo segna. Se un percorso è un vicolo cieco, lo cancella e ne prova un altro.
• La magia: Non si limita a un gioco. Solvitaire è come un cannocchiale universale. I ricercatori hanno scritto un linguaggio speciale (un po' come un manuale di istruzioni in codice) che permette a Solvitaire di capire le regole di 73 varianti diverse di solitario, dal classico Klondike al FreeCell, fino a giochi molto strani che nessuno aveva mai studiato così approfonditamente.

🔍 Cosa hanno scoperto? (I Risultati Sorprendenti)

Ecco le scoperte principali, spiegate con metafore:

1. Il Klondike (il classico) è più facile di quanto pensassimo:
   Prima pensavamo che il Klondike "pensoso" (dove sai dove sono tutte le carte, anche quelle coperte) fosse vinto circa l'82% delle volte. Solvitaire ha confermato questo numero, ma con una precisione chirurgica: 81,945%.

   • L'analogia: Immagina di dover misurare la lunghezza di un campo da calcio. I vecchi metodi ti dicevano "circa 100 metri". Solvitaire ti dice "100,45 metri, con un errore di un millimetro". Hanno ridotto l'incertezza di 30 volte!

2. Il "pensiero" cambia tutto:
   Hanno studiato la versione "pensosa" (dove vedi le carte coperte). Nella vita reale, se giochi con le carte vere e non puoi guardare sotto, le probabilità crollano. Ma sapere che il 82% delle partite è teoricamente risolvibile ci dice che il gioco non è "rotto", è solo molto complesso.

3. Alcuni giochi sono quasi impossibili:
   Hanno scoperto che alcuni giochi, come il British Canister, sono quasi un suicidio: si vince solo una volta su un milione. È come cercare un ago in un pagliaio, ma il pagliaio è fatto di miliardi di pagliuzze.

4. Le regole contano più di quanto pensi:
   Hanno fatto esperimenti cambiando le regole del Klondike.

   • Esempio: Se ti permettono di pescare 3 carte alla volta dal mazzo (come nel gioco classico), vinci l'82%. Se ti permettono di pescarne 1 alla volta, vinci il 90%. Se ne peschi 7, vinci solo il 23%.
   • La metafora: È come se il gioco ti desse una scala. Più la scala è corta (pochi pesci), più è facile arrampicarsi. Più è lunga (molte carte da pescare), più è difficile vedere la cima.

🛠️ Come funziona la loro "Scatola Magica"?

Per rendere Solvitaire veloce, hanno usato tre trucchi da mago dell'informatica:

1. La Mappa dei Vicoli Ciechi (Transposition Tables):
   Immagina di camminare in un labirinto. Se giri a destra, poi a sinistra, poi a destra e ti ritrovi nello stesso punto in cui eri prima, non ha senso ripercorrere la strada. Solvitaire tiene una mappa mentale di tutti i posti in cui è già stato. Se vede un posto già visitato, dice: "No, qui sono già stato, non serve perdere tempo".

2. Le Regole di Sicurezza (Dominances):
   A volte, in un gioco, c'è una mossa che è sempre la scelta giusta.

   • Esempio: Se hai un Asso e puoi metterlo nella pila di fondazione (la vittoria), fallo subito! Non c'è nessun motivo per tenerlo in mano. Solvitaire ha imparato queste "regole d'oro" e le applica istantaneamente, saltando milioni di mosse inutili. Hanno anche dimostrato matematicamente che queste regole sono sicure e non ingannano il gioco.

3. Il Simulatore di "Cosa Succederebbe Se" (Streamliners):
   A volte, per risparmiare tempo, Solvitaire fa un'ipotesi: "Proviamo a giocare come se le carte avessero più simmetria di quanto abbiano realmente". Se trova una soluzione con questa ipotesi semplificata, vince! Se non la trova, torna indietro e gioca con le regole vere. È come se un detective provasse prima la teoria più semplice prima di approfondire casi complicati.

🏆 Perché è importante?

Prima di questo studio, la maggior parte delle risposte sulle probabilità di vittoria veniva da appassionati che giocavano per anni o da programmi fatti "su misura" per un solo gioco.
Questo studio è rivoluzionario perché:

• È uno solo che risolve tutti i giochi.
• È preciso al punto di dare una percentuale con due decimali dopo la virgola.
• Ha scoperto bug (errori) nei programmi precedenti usati da altri ricercatori, correggendo la storia del solitario.

🎯 In Conclusione

Hanno preso un gioco che abbiamo tutti giocato a scuola o a casa, e lo hanno trasformato in un laboratorio scientifico. Hanno dimostrato che con l'intelligenza artificiale giusta, possiamo capire la "natura" di un gioco: quanto è difficile, quanto è fortunato e quali regole lo rendono un incubo o un piacere.

In pratica, hanno risposto alla domanda che Stanislaw Ulam si pose negli anni '40 mentre giocava a solitario in ospedale (e che lo portò a inventare il metodo Monte Carlo): "Quante probabilità ho di vincere?".
La risposta? Dipende dal gioco, ma ora lo sappiamo con una precisione che prima sembrava magia.

Sommario tecnico

1. Il Problema

Il documento affronta un problema fondamentale nell'ambito dei giochi di carte a giocatore singolo (noti come "patience" o "solitaire"): la determinazione della percentuale di winnability (probabilità che una data configurazione casuale di carte sia risolvibile).

• Il "Klondike": La variante più famosa, inclusa nel software Microsoft Windows Solitaire, è stata descritta come "uno degli imbarazzi della matematica applicata" a causa della mancanza di una stima precisa della sua probabilità di vittoria. Le stime precedenti erano spesso basate su simulazioni Monte Carlo con ampi intervalli di confidenza o su solver specifici per singoli giochi.
• La sfida: Esistono centinaia di varianti di questi giochi con regole diverse. Determinare la winnability richiede di esplorare lo spazio degli stati del gioco, che è esponenzialmente grande. Inoltre, per giochi con carte coperte (come il Klondike), la comunità accademica si concentra sulla variante "thoughtful" (dove il giocatore conosce la posizione e il valore di tutte le carte nascoste), che fornisce un limite superiore alla probabilità di vittoria reale.

2. Metodologia: Solvitaire

Gli autori hanno sviluppato Solvitaire, un risolutore (solver) di scopo generale basato su Ricerca in Profondità (Depth-First Search - DFS) con backtracking. A differenza dei solver precedenti, spesso ottimizzati per un singolo gioco, Solvitaire utilizza un linguaggio di descrizione delle regole flessibile (in formato JSON) per gestire 35 giochi diversi e 73 varianti senza modifiche al codice sorgente.

Le tecniche di Intelligenza Artificiale impiegate per ottimizzare la ricerca includono:

• Transposition Tables: Tabelle di cache per evitare di esplorare stati già visitati, riducendo drasticamente la ridondanza della ricerca.
• Symmetry Breaking: Riconoscimento e eliminazione di stati simmetrici (es. pile del tavolo indistinguibili o simmetrie tra i semi) per ridurre lo spazio di ricerca.
• Dominance (Dominanza): Tecniche per eliminare rami di ricerca che non possono portare a una soluzione migliore o necessaria. Gli autori forniscono le prime dimostrazioni di correttezza formale per due dominanze chiave:
  1. Safe Moves to Foundations: Spostare una carta alla fondazione se è "sicuro" farlo (senza bloccare future mosse vincenti).
  2. Tableau Moves of Incomplete Piles: Limitare lo spostamento di gruppi parziali di carte sul tavolo a meno che la carta immediatamente superiore non possa essere immediatamente spostata alla fondazione.
• Streamliners: Euristiche che impongono vincoli aggiuntivi per accelerare la ricerca (es. forzare lo spostamento alla fondazione quando possibile). Se falliscono, il sistema esegue una ricerca completa senza vincoli per garantire la correttezza.
• Rappresentazione K+: Una rappresentazione ottimizzata per lo stock (mazzo di pesca) in giochi con riciclaggio infinito, che calcola quali carte sono ottenibili senza simulare ogni singola pesca.

3. Contributi Chiave

1. Solvatore Universale: La creazione di un unico motore di ricerca capace di gestire una vasta gamma di giochi di patience con regole eterogenee, superando la necessità di scrivere solver specifici per ogni gioco.
2. Dimostrazioni di Correttezza: Fornire le prime prove matematiche di correttezza per due dominanze critiche utilizzate nei solver di patience, risolvendo dubbi sulla loro validità in contesti generali.
3. Scoperta di Bug: Attraverso il confronto con solver esistenti (come quelli di Matt Birrell per Klondike e Jan Wolter per Canfield), gli autori hanno identificato e corretto bug sottili nelle implementazioni precedenti, inclusi errori nelle dominanze e nei generatori di numeri casuali.
4. Analisi delle Varianti: Studio sistematico di come le variazioni delle regole (es. dimensione della pesca, possibilità di "riportare indietro" le carte dalla fondazione al tavolo) influenzino la winnability.

4. Risultati Principali

Gli autori hanno calcolato le percentuali di winnability per 73 varianti di 35 giochi diversi, con un intervallo di confidenza al 95% di ±0,1% o migliore.

• Klondike (Thoughtful): La winnability è stata determinata con precisione come 81,945% ± 0,084%. Questo rappresenta una riduzione di 30 volte dell'intervallo di confidenza rispetto ai migliori risultati precedenti.
• Canfield (Thoughtful): Stima di 71,245% ± 0,031%, con un miglioramento significativo rispetto alla letteratura precedente.
• FreeCell: Conferma che la winnability è estremamente alta (99,998881%), confermando che quasi tutti i casi sono risolvibili, con solo 110 casi su 10 milioni risultati irrisolvibili.
• Nuovi Risultati: Sono stati ottenuti risultati completamente nuovi per 20 giochi (es. Beleaguered Castle, Fortune's Favor, Mrs Mop) e miglioramenti sostanziali per molti altri.
• Analisi delle Varianti di Klondike:
  • All'aumentare della dimensione della pesca (draw size), la winnabilità diminuisce drasticamente (da ~90% con pesca di 1 carta a ~0,6% con pesca di 13 carte).
  • L'uso della funzione "worrying back" (riportare carte dalla fondazione al tavolo) è necessario in una percentuale crescente di casi risolvibili man mano che la pesca aumenta (fino al 9,26% per la pesca di 13 carte).

5. Significato e Impatto

• Risoluzione di un problema storico: Il paper risponde finalmente alla domanda che ha ispirato Stanislaw Ulam a inventare i metodi Monte Carlo negli anni '40 (la winnability del solitaire), fornendo una stima precisa e statisticamente robusta.
• Validazione Accademica: Dimostra che i metodi di ricerca AI generali, se combinati con tecniche avanzate di ottimizzazione e dimostrazioni formali, possono competere o superare i solver specializzati creati manualmente per decenni.
• Risorsa per la Comunità: Il codice sorgente di Solvitaire è open-source (GPL v2) e tutti i dati sperimentali sono disponibili pubblicamente, permettendo alla comunità di verificare, replicare e migliorare i risultati.
• Limiti e Futuro: Il paper ammette che per alcuni giochi con regole molto permissive ma vincoli locali severi (es. spazi non riutilizzabili), il solver fatica a dimostrare l'irrisolvibilità a causa dell'enorme spazio di ricerca. Tuttavia, l'approccio proposto apre la strada a futuri lavori che combinano ricerca esaustiva con ragionamento basato su vincoli (constraint reasoning) per colmare queste lacune.

In sintesi, questo lavoro rappresenta un punto di riferimento nella risoluzione algoritmica dei giochi di carte, trasformando un'area di studio spesso basata su euristiche empiriche in una disciplina rigorosa supportata da prove formali e dati su larga scala.