L’algoritmo che risolve i superpuzzle

Poco meno di un giorno: tanto è bastato all’intelligenza artificiale di un computer per risolvere un puzzle di diecimila pezzi. Si tratta del nuovo record mondiale: il primato precedente si era fermato a “soli” tremila pezzi. Il sorprendente risultato si deve a un nuovo algoritmo sviluppato da Andrew Gallagher della Cornell University (Ithaca, NY), presentato alla conferenza Computer Vision and Pattern Recognition a Providence (RI, Usa).

Il ricercatore racconta di aver avuto l’idea mentre lavorava su delle fotografie, ispirandosi all’approccio umano nella risoluzione dei puzzle. Infatti, a differenza degli altri software, che si limitano ad analizzare i bordi e le forme dei pezzi per cercare le corrispondenze, l’algoritmo di Gallagher studia la distribuzione dei colori: ad esempio, se un frammento diventa progressivamente più chiaro da sinistra verso destra, è molto verosimile che vada affiancato a un pezzo chiaro a destra e uno scuro a sinistra.

In base a questo approccio, il software associa un punteggio a ogni coppia di pezzi affiancati, stilando una classifica di corrispondenze che viene progressivamente ricalcolata quando si trova un abbinamento migliore. Per ricostruire il puzzle, l’algoritmo inizia con i due pezzi che si accoppiano meglio tra loro, poi passa ai successivi e così via: ma – e qui sta uno dei punti di forza del programma – gli abbinamenti non devono necessariamente essere a loro volta adiacenti. Questa peculiarità, infatti, consente all’algoritmo di lavorare contemporaneamente su porzioni diverse del puzzle, abbreviando il tempo necessario per la soluzione.

È lo stesso Ohad Ben-Shahar, scienziato della Ben-Gurion University di Beer-Sheva (Israele) e detentore del record precedente, a tributare il giusto onore all’algoritmo di Gallagher: “Oltre a essere così veloce questo algoritmo è capace di ricomporre puzzle in cui l’orientamento dei pezzi è del tutto casuale, un problema molto difficile dal punto di vista computazionale”. Comunque, sottolinea ancora Ben-Shahar, c’è ancora spazio per ulteriori miglioramenti: “Con un piccolo sforzo, il tempo complessivo per la soluzione potrebbe scendere significativamente al di sotto delle ventiquattro ore“.

In ogni caso, tendono a sottolineare i ricercatori, la scoperta promette di andare ben al di là della “semplice” risoluzione di giochi e rompicapi: l’algoritmo superveloce potrebbe avere svariate applicazioni, dalla ricomposizione di documenti triturati al riordino di frammenti provenienti da siti archeologici.

Riferimenti: Computer Vision and Pattern Recognition

Video: L’algoritmo di Gallagher risolve un puzzle di 600 pezzi. Credit a Andrew Gallagher, Cornell University
Credit immagine a OhOlek / Flickr