Indice Rubik   Home: Http://digilander.iol.it/tamanti

Risoluzione del cubo di Rubik in linguaggio prolog,
ideato e realizzato da Marco Tamanti.

Rubik in prolog (zippato)

Il cubo è composto da 8 "vertici" (ognuno con tre faccette) e da 12 "spigoli" (con due faccette). Il numero totale di possibili figure diverse è dato da dalle combinazioni di tutti i vertici con tutti gli spigoli, contando anche le orientazioni dei cubetti, cioè: 8! * 38 * 12! * 212 = 5,19 * 1020.   È pertanto impensabile attaccare il problema direttamente con la forza bruta senza utilizzare della conoscenza. D'altra parte é anche molto difficile costruire delle euristiche basate sulla distanza dei cubetti dal goal, visto che sono sufficienti quattro mosse per portare fuori posto tutti i cubetti; inoltre con tre mosse è possibile portare un cubetto alla massima distanza dalla posizione originale.
L'unica possibilità è contare il numero di cubetti fuori posto per avere una idea più o meno indicativa dello stato del cubo; non è comunque detto che uno stato che abbia un numero maggiore di cubetti al posto giusto sia più vicino al goal: spesso per riuscire a mettere a posto un ulteriore cubetto bisogna prima passare per uno stato in cui regna la confusione.
Ripeto che con sole tre mosse tutti i cubetti possono essere portati fuori posto!

Per un uomo la parte più difficoltosa nella risoluzione del cubo è quella finale: il problema è riuscire a sistemare gli ultimi cubetti senza spostare quelli già a posto. Per far ciò si utilizzano delle sequenze di mosse che permettono, alla fine della sequenza, di spostare solo un numero limitato di pezzi. Ad esempio è possibile, con dodici mosse elementari, spostare reciprocamente quattro vertici lasciando tutti gli altri pezzi al loro posto (naturalmente durante la sequenza anche gli altri pezzi vengono mossi, ma la sequenza è tale che alla fine si aggiusta tutto).
Ho pensato che sarebbe stato utile riuscire a trovare il maggior numero di queste sequenze "magiche".

Per trovare la soluzione finale è utile riuscire a scomporre il problema in sottoproblemi:
sistemare prima tutti i vertici, poi tutti gli spigoli o viceversa; questo è possibile se riesco a trovare due sequenze magiche diverse che mi permettano di spostare solo un certo numero di vertici senza toccare gli spigoli, oppure spostare alcuni spigoli senza muovere i vertici dal loro posto.

Con il programma "Cerca veloce.pl" (zip) sono riuscito a trovare una combinazione che permette di spostare solo 3 spigoli in 10 mosse elementari (tempo di ricerca 37 secondi), oppure solo 4 vertici in 12 mosse (tempo di ricerca 300 secondi). Era possibile muovere solo la faccia bianca e quella verde.
Se elimino le mosse da due ottengo delle prestazioni migliori e pressocché gli stessi risultati pratici.
Ho provato anche a muovere 3 facce ("cerca3.x.pl": vedi in fondo a "cerca veloce.pl"), ma nessun nuovo risultato utile.

Mi sono ora concentrato solo sui vertici, sfruttando una delle sequenza di 12 mosse che mi permette di spostare solo 4 vertici: con "Cerca12.pl" (zip) ho avuto degli ulteriori risultati.

Finalmente, sfruttando le sequenze trovate, posso mirare ad una soluzione del cubo. Dopo alcune prove (vedi "Risolvi0.pl" (zip) : 50 minuti) sono approdato ad una soluzione discreta per i vertici.
Proprio analizzando le sequenze mi è venuto in mente di scomporre il problema ulteriormente: in "Vertici.pl" (zip) ho fatto un programma che, partendo da una configurazione in cui nessun pezzo è a posto, arriva a posizionare correttamente tutti i vertici lasciando inalterati gli spigoli. La ricerca è stata scomposta in due parti: posizionamento dei vertici e orientamento degli stessi, sfruttando due diversi set di sequenze. La soluzione arriva in meno di 2 secondi.
Benchè il programma esegua delle ricerche depth first, in realtà la filosofia generale è breadth first; ho fatto questa scelta per due validi motivi:

Un'altra cosa da notare è la ricerca per gradi: prima si posizionano alcuni vertici, poi si riparte la ricerca di nuovi aggiustamento a partire da tale stato. Questo assomiglia all'algoritmo A*, che però non sarebbe adeguato nella prossimità del goal, infatti per mettere a posto gli ultimi 2 vertici bisogna ritornare a configurazioni peggiori (forse si otterrebbe una qualche soluzione con il Simulated Annealing). Uno dei miei intenti era anche quello di trovare il numero minore di mosse, però alla fine nella ricerca considero con lo stesso peso una mossa singola o una sequenza da 12 mosse.

Sono poi passato agli spigoli: prima ho tentato con sequenze di mosse da 10 che non modificavano i vertici, ma per una soluzione ci voleva più di un'ora (quando ci arrivava in tempo utile). Così, visto che già riuscivo a sistemare i vertici senza più toccare gli spigoli, ho pensato che fosse utile disinteressarmi dei vertici mentre sistemavo gli spigoli. Primi risultati con "Spigoli.pl" (zip): 37 secondi per posizionarli.
In "Spigoli1.pl" (zip), con sequenze che spostano 2 soli spigoli anziché 3, il tempo è passato a meno di 1 secondo.
Con "Spigoli3.pl" (zip) ho cercato di diminuire il numero di mosse totali necessarie: posizionare i primi spigoli è molto più che posizionare quelli successivi, quindi è possibile utilizzare solo mosse singole.
Con "Spigoli4.pl" (zip) ho perseverato su questa strada e pur ottenendo delle prestazioni peggiori, ho migliorato di molto il numero di mosse necessarie. Ho anche seguito una metodologia fin qui non provata: anziché pura ricerca di stati positivi dopo l'applicazione casuale di mosse diverse, analizzo lo stato del cubo per applicare la sequenza di mosse adeguata.

Rubik.pl (zip) è il programma in versione definitiva in cui ho privilegiato la velocità rispetto al numero di mosse. Ho inoltre aggiunto vari predicati per modificare manualmente o casualmente lo stato del cubo.
Modifiche per migliorare l'algoritmo (in velocità e/o in numero di mosse) ce ne sarebbero a volontà:

Tutti i test sono stati realizzati con Sicstus prolog 3.6 su un processore Pentium a 166 MHz, RAM di 32 MB (comunque ininfluente) e sistema operativo windows NT, di cui ho utilizzato il "task manager" per calcolare l'utilizzo della CPU da parte di ogni simulazione. Le notizie finali le ho ricavete da una pagina internet pubblicata da Jake Olefsky che a sua volta si riferisce a : Discover, March 1986 v7 p81(8), Full Text COPYRIGHT Family Media Inc. 1986.
Per esplorare sul web: http://www.snipercade.com/cubeman/


(Relazione che portai alla professoressa di intelligenza artificiale)

Home