Con un paio di giorni di ritardo rispetto a quando il calendario diceva che stava cadendo il boxing day 2011, anche per il sottoscritto e’ stata l’ora di un po’ di sano shopping. Shopping che, giusto per rimanere in tema con i post degli ultimi giorni, ha avuto carattere ludico. Entrato per una perlustrazione all’interno di un negozio di giocattoli, mi sono soffermato sul reparto giochi da tavolo, dove non ho potuto fare a meno di mettere nel carrello la Plymouth Edition di Monopoly. Nonche’ lui, Eternity II, il puzzle a cui avevo pensato sin dal momento della sua uscita ma che poi, per un motivo o per l’altro, non avevo mai avuto modo di acquistare.
Per chi non lo conoscesse, basti sapere che si tratta di un puzzle dal funzionamento molto semplice. 256 tessere, ciascuna di esse con un particolare disegno sui quattro lati, da disporre all’interno di un tabellone 16×16 in maniera tale che tutte le tessere abbiano i disegni che “matchino” con quelli delle tessere adiacenti. Per quanto il meccanismo sia semplice e lineare, il problema e’ uno di quelli NP-complete e la dimensione dello spazio delle soluzioni e’ qualcosa nell’ordine di dieci alla seicentosessantuno (senza tuttavia tener presente alcuni vincoli, per esempio il fatto che alcune tessere devono essere necessariamente poste lungo i bordi esterni del tabellone) (vedi Codebrain.co.uk per una spiegazione un po’ più approfondita). Cio’ esclude la possibilità’ di risolvere il puzzle via brute-force e richiede che strategie alternative vengano individuate. Originariamente i produttori del gioco avevano messo in palio un premio di $2,000,000 per chiunque fosse riuscito a trovare la soluzione al puzzle. Il concorso, scaduto il 31 dicembre 2010, si e’ concluso senza alcun vincitore.
Avendo in questi giorni un po’ di tempo a disposizione, mi sono subito messo al lavoro per provare a scrivere un software in grado, tramite algoritmi evolutivi, di tentare perlomeno di approssimare una soluzione corretta. Per farlo non sto utilizzando la versione completa di Eternity II, ma una più ridotta (il Clue Puzzle 1) composta da 36 pezzi da disporre su di una griglia 6×6.
Il primo problema che ci si pone nel momento in cui si voglia approcciare il problema per via informatica e’ naturalmente quello dell’encoding. Ho quindi provveduto a mappare le varie tessere ed il risultato potete vederlo nell’estratto di codice qui sotto. I parametri passati al costruttore degli oggetti “piece” sono rispettivamente: numero della tessera, orientamento, disegno sul lato nord, disegno sul lato est, disegno sul lato sud, disegno sul lato ovest, presenza di almeno un bordo (si’/no), tessera già utilizzata (si’/no) per la generazione della soluzione corrente.
Ora si tratta “soltanto” di scrivere qualche funzione in grado di generare soluzioni valide per il puzzle nei tempi piu’ rapidi possibili (magari tenendo fissi i bordi ed isolando quelle tessere dal resto dell’euristica?) e poi scrivere un algoritmo evolutivo che provi ad evolvere popolazioni di potenziali soluzioni verso il punteggio più alto possibile (data una soluzione, ogni disegno che combacia vale un punto).
Insomma, avrò di che divertirmi nei prossimi giorni…
Comments(18)
