Puzzle Solver

Introduzione

Il gioco in questione ebbe una prima grande diffusione alla fine dell'Ottocento, quando Sam Loyd, grande esperto americano in giochi e rompicapi, ne propose una versione diabolica che battezzò il "14 - 15 puzzle": "I vecchi abitanti del Regno dei Giochi - scrive lo stesso Loyd, presentando il gioco, con lo stile dei tempi passati, nel suo libro Passatempi matematici - ricorderanno che ho fatto impazzire tutto il mondo con una scatoletta di tessere scorrevoli che divenne famosa col nome di "gioco del 15". Le quindici tessere sono disposte nella scatola in serie numerica regolare, ma con i numeri 14 e 15 scambiati; il gioco consiste nello spostare le tessere, muovendole una alla volta, fino a riportarle in una posizione identica alla precedente ma con il 14 e il 15 al posto giusto. Questo gioco è diventato per molti una vera e propria mani: si narra di piloti che hanno fatto naufragare la loro nave e di macchinisti che hanno oltrepassato la stazione a tutta velocità. Un famoso editore di Baltimora, racconta, che, uscito una volta per il pranzo di mezzogiorno, fu ritrovato dai suoi impiegati, dopo frenetiche ricerche, a notte inoltrata mentre spingeva dei quadratini di focaccia su e giù per il piatto!”.

Loyd offrì un premio di 1000 dollari a chi fosse riuscito a trovare la soluzione del gioco, ben sapendo che questa non esisteva: data infatti una configurazione qualsiasi è sufficiente contare il numero di scambi necessari per arrivare alla soluzione finale, cioè gli spostamenti di blocchetti che si devono effettuare per rimetterli in ordine, sollevandoli dalla scacchiera, al di fuori dei vincoli del gioco; soltanto se il numero degli scambi è pari, il gioco è risolvibile. Dobbiamo contare il numero degli scambi effettuati ovvero, se definiamo come inversione di una configurazione ogni situazione in cui un numero è preceduto da un numero più grande, quante sono le inversioni, tenendo presente che metà delle configurazioni possibili sono pari e Il gioco in questione ebbe una prima grande diffusione alla fine dell'Ottocento, quando Sam Loyd, grande esperto americano in giochi e rompicapi, ne propose una versione diabolica che battezzò il "14 - 15 puzzle": "I vecchi abitanti del Regno dei Giochi - scrive lo stesso Loyd, presentando il gioco, con lo stile dei tempi passati, nel suo libro Passatempi matematici - ricorderanno che ho fatto impazzire tutto il mondo con una scatoletta di tessere scorrevoli che divenne famosa col nome di "gioco del 15". Le quindici tessere sono disposte nella scatola in serie numerica regolare, ma con i numeri 14 e 15 scambiati; il gioco consiste nello spostare le tessere, muovendole una alla volta, fino a riportarle in una posizione identica alla precedente ma con il 14 e il 15 al posto giusto. Questo gioco è diventato per molti una vera e propria mani: si narra di piloti che hanno fatto naufragare la loro nave e di macchinisti che hanno oltrepassato la stazione a tutta velocità. Un famoso editore di Baltimora, racconta, che, uscito una volta per il pranzo di mezzogiorno, fu ritrovato dai suoi impiegati, dopo frenetiche ricerche, a notte inoltrata mentre spingeva dei quadratini di focaccia su e giù per il piatto!”.

Loyd offrì un premio di 1000 dollari a chi fosse riuscito a trovare la soluzione del gioco, ben sapendo che questa non esisteva: data infatti una configurazione qualsiasi è sufficiente contare il numero di scambi necessari per arrivare alla soluzione finale, cioè gli spostamenti di blocchetti che si devono effettuare per rimetterli in ordine, sollevandoli dalla scacchiera, al di fuori dei vincoli del gioco; soltanto se il numero degli scambi è pari, il gioco è risolvibile. Dobbiamo contare il numero degli scambi effettuati ovvero, se definiamo come inversione di una configurazione ogni situazione in cui un numero è preceduto da un numero più grande, quante sono le inversioni, tenendo presente che metà delle configurazioni possibili sono pari e metà sono dispari e che non è possibile passare da una configurazione pari a una dispari; nel caso della configurazione del gioco proposta da Loyd, essa ha 1 sola inversione, mentre la configurazione finale del gioco ne ha 0 e quindi non sarà mai possibile passare dalla prima alla seconda.

Questa introduzione è necessaria per consentire al lettore di capire i dati che ora esporremo: nel caso del Puzzle 4x4 vi sono 16! / 2 configurazioni valide da cui si può effettivamente arrivare alla soluzione del Puzzle (se consideriamo le configurazioni di inversione pari, non consideriamo le configurazioni di inversione dispari, e viceversa); questo significa 10.461.394.944.000 configurazioni possibili (10.500 miliardi)... Un dato che si commenta da solo.

Descrizione Attività svolta

Il progetto riguarda la creazione di un programma che affronti la risoluzione del problema del Puzzle (visto a lezione) mediante una serie di algoritmi ed euristiche (viste a lezione); l'attività si è incentrata prevalentemente sui seguenti punti:

- quali algoritmi implementare

Best First Greedy, Astar, IDAStar – concordati con il Docente.

- quali euristiche implementare

Mismatch, distanza di Pitagora, distanza di Manhattan – concordate con il Docente, ad eccezione dell'euristica della distanza di Pitagora; tale euristica è un derivato, leggermente più scarso in termini di prestazioni, della distanza di Manhattan: si sfrutta la distanza in linea retta calcolata in base al Teorema di Pitagora, usando come lati la distanza verticale e la distanza orizzontale di una cella rispetto alla sua posizione corretta (come per la distanza di Manhattan); tale euristica è fornita come “bonus”, non è stata considerata nei test.

- quali politiche di gestione degli stati ripetuti implementare

Controllo del Nodo “Nonno”, Controllo dei Nodi Predecessori, Controllo di tutti i Nodi – concordate con il docente. Sono necessarie alcune precisazioni: non è corretto effettuare il controllo degli stati ripetuti sul nodo “Padre”, poiché in un Puzzle nel caso migliore sono necessarie almeno 2 mosse per poter tornare a uno stato precedente; quando si effettua il Controllo di tutti i Nodi, si scarta un nodo solo se esiste un altro nodo nell'albero le cui configurazioni di pezzi del Puzzle sono le medesime, e solo se la sua profondità è maggiore di quello del nodo dell'albero.

- quali dati registrare (utilizzati in seguito per i test)

Profondità della Soluzione (equivale al numero di scambi di caselle necessarie per vincere), Nodi espansi, Nodi scartati, Tempo impiegato – concordati con il docente.

- se e come definire un'interfaccia grafica

Suddivisione in Puzzle e Risolutore – a scelta dello studente; l'interfaccia grafica separa la definizione dei dati del Puzzle (dimensione, disordine dei pezzi) e del Risolutore (algoritmo, euristica, politica di gestione degli stati ripetuti), dimodochè si possano confrontare i risultati di diversi Risolutori sullo stesso Puzzle e viceversa.

- quale linguaggio di programmazione utilizzare

Java – a scelta dello studente, per la portabilità e la semplicità di programmazione.

Risultati dei Test

Di seguito sono esposti i risultati emersi dai test, suddivisi per dimensione e randomizzazione del Puzzle, catalogati prima in tabella e poi esposti con grafici; nel caso in cui l'esecuzione di un test superi i 60 secondi di calcolo, tutti i valori della corrispondente riga vengono impostati a -1.

Puzzle 3 * 3 (randomizzazione = 25)

Analizzando il caso più semplice, ossia una tabella 3 * 3 parzialmente disordinata (in cui il numero di mosse richieste per trovare una soluzione ottimale è esiguo), si può notare fin da subito la notevole inadeguatezza di prestazioni degli algoritmi Greedy abbinati a euristiche non ottimali (numeri 2 e 3) o a controlli degli stati ripetuti laschi (numeri 1 e 4); non ci sono altri dati rilevanti da cogliere, poiché, data la relativa semplicità con cui si giunge alla soluzione ottima, tutte le altre combinazioni algoritmo – euristica – gestione stati ripetuti sono egualmente più efficaci.

Puzzle 3 * 3 (randomizzazione = 100)

Analizzando un caso di complessità media, ossia una tabella 3 * 3 completamente disordinata (in cui il numero ottimale di mosse richieste per trovare una soluzione è elevato), si può notare fin da subito la notevole inadeguatezza di prestazioni degli algoritmi Greedy abbinati a euristiche non ottimali (numeri 2 e 3) o a controlli degli stati ripetuti laschi (numeri 1 e 4): viene rintracciata subito (o quasi) una soluzione non ottima in poco tempo; si può notare inoltre che gli algoritmi A* e I.D.A* trovano sempre la medesima soluzione ottima, le differenze riguardano i nodi espansi/scartati e il tempo impiegato: l'euristica “Manhattan” risulta molto più efficace dell'euristica “Mismatch” sotto tutti i fronti (come ci si aspetterebbe). Rimane una particolarità da osservare: il controllo degli stati ripetuti su tutto l'albero risulta molto efficace per l'algoritmo Greedy, consentendo di trovare una soluzione migliore, rispetto a quella ottenuta da altri tipi di controllo sul medesimo algoritmo, a un costo temporale aggiuntivo molto contenuto; d'altro canto, lo stesso controllo applicato a A* o I.D.A* peggiora drasticamente le prestazioni temporali usuali, giungendo infine comunque ad una soluzione ottima.

Puzzle 4 * 4 (randomizzazione = 100)

Analizzando un caso di complessità alta, ossia una tabella 4 * 4 parzialmente disordinata (in cui il numero ottimale di mosse richieste per trovare una soluzione è molto elevato), si può notare fin da subito come la complessità del Puzzle NP – Hard sia in grado di ridurre in ginocchio un calcolatore: solo gli algoritmi A* e I.D.A*, guidati dall'euristica Manhattan (la più efficiente) e dotati di un controllo degli stati ripetuti “leggero” riescono in meno di 60 secondi a trovare una soluzione (ottima per le proprietà di A* e I.D.A*); per scrupolo l'autore ha lasciato che quasi tutti gli algoritmi eseguissero per ben più di 60 secondi, ma nessuno di essi a parte i sopracitati è riuscito a risolvere il problema.