Una macchina ha capito da sola il Cubo di Rubik

Ancora un altro bastione dell'abilità e dell'intelligenza umana è caduto sotto l'assalto delle macchine. Un nuovo tipo di macchina per il deep learning ha imparato da sola a risolvere un cubo di Rubik senza alcun aiuto umano.

La pietra miliare è significativa perché il nuovo approccio affronta un problema importante nell'informatica: come risolvere problemi complessi quando l'aiuto è minimo.

Prima un po' di background. Il Cubo di Rubik è un puzzle tridimensionale sviluppato nel 1974 dall'inventore ungherese Erno Rubik, con l'obiettivo di allineare tutti i quadrati dello stesso colore sulla stessa faccia del cubo. È diventato un giocattolo più venduto a livello internazionale e ha venduto oltre 350 milioni di unità.

Il puzzle ha anche attirato un notevole interesse da parte di informatici e matematici. Una domanda che li ha incuriositi è il minor numero di mosse necessarie per risolverlo da qualsiasi posizione . La risposta, provata nel 2014, risulta essere 26.

Un'altra sfida comune è progettare algoritmi in grado di risolvere il cubo da qualsiasi posizione. Lo stesso Rubik, entro un mese dall'invenzione del giocattolo, ha escogitato un algoritmo in grado di farlo.

Ma i tentativi di automatizzare il processo si sono basati tutti su algoritmi creati a mano dagli esseri umani.

Più recentemente, gli informatici hanno cercato di trovare il modo in cui le macchine risolvessero il problema da sole. Un'idea è quella di utilizzare lo stesso tipo di approccio che ha avuto tanto successo con giochi come scacchi e Go.

In questi scenari, una macchina di deep learning riceve le regole del gioco e poi gioca contro se stessa. Fondamentalmente, viene premiato ad ogni passaggio in base a come si comporta. Questo processo di ricompensa è estremamente importante perché aiuta la macchina a distinguere il gioco buono da quello cattivo. In altre parole, aiuta la macchina ad apprendere.

Ma questo non funziona in molte situazioni del mondo reale, perché le ricompense sono spesso rare o difficili da determinare.

Ad esempio, i giri casuali di un cubo di Rubik non possono essere facilmente ricompensati, poiché è difficile giudicare se la nuova configurazione sia più vicina a una soluzione. E una sequenza di turni casuali può andare avanti per molto tempo senza raggiungere una soluzione, quindi la ricompensa dello stato finale può essere offerta solo raramente.

Negli scacchi, al contrario, c'è uno spazio di ricerca relativamente ampio ma ogni mossa può essere valutata e premiata di conseguenza. Questo non è il caso del Cubo di Rubik.

Entrano Stephen McAleer e colleghi dell'Università della California, Irvine. Questi ragazzi hanno sperimentato un nuovo tipo di tecnica di apprendimento profondo, chiamata iterazione autodidattica, che può imparare a risolvere un cubo di Rubik senza l'assistenza umana. Il trucco che McAleer e compagni hanno imparato è trovare un modo per la macchina di creare il proprio sistema di ricompense.

Ecco come funziona. Dato un cubo non risolto, la macchina deve decidere se una mossa specifica è un miglioramento rispetto alla configurazione esistente. Per fare ciò, deve essere in grado di valutare la mossa.

L'iterazione autodidattica lo fa partendo dal cubo finito e lavorando all'indietro per trovare una configurazione simile alla mossa proposta. Questo processo non è perfetto, ma il deep learning aiuta il sistema a capire quali mosse sono generalmente migliori di altre.

Dopo essere stata addestrata, la rete utilizza quindi un albero di ricerca standard per cercare le mosse suggerite per ciascuna configurazione.

Il risultato è un algoritmo che funziona molto bene. Il nostro algoritmo è in grado di risolvere il 100% dei cubi rimescolati casualmente raggiungendo una lunghezza mediana di risoluzione di 30 mosse, inferiore o uguale ai solutori che utilizzano la conoscenza del dominio umano, affermano McAleer e altri.

È interessante perché ha implicazioni per una varietà di altre attività con cui il deep learning ha lottato, inclusi enigmi come Sokoban, giochi come Montezuma's Revenge e problemi come la fattorizzazione dei numeri primi.

In effetti, McAleer e co hanno altri obiettivi nel mirino: stiamo lavorando per estendere questo metodo per trovare soluzioni approssimative ad altri problemi di ottimizzazione combinatoria come la previsione della struttura terziaria delle proteine.

Non è chiaro se questi problemi saranno suscettibili di questo approccio. In genere non beneficiano di una prova che possono essere risolti in un piccolo numero di mosse, come fa il problema del Cubo di Rubik. Questo senza dubbio ha funzionato a favore della squadra qui.

McAleer e colleghi sostengono che il loro approccio è una forma di ragionamento sui problemi. Sottolineano che una definizione di ragionamento è: manipolare algebricamente le conoscenze acquisite in precedenza per rispondere a una nuova domanda.

Dicono che questo è esattamente ciò che fa il loro algoritmo, chiamato DeepCube. Al contrario, le macchine di deep learning convenzionali riconoscono semplicemente determinati modelli. DeepCube è in grado di imparare a ragionare per risolvere un ambiente complesso con un solo stato di ricompensa usando il puro apprendimento per rinforzo, dicono.

Forse. Il vero test, ovviamente, sarà come questo approccio affronti problemi più complessi come il ripiegamento delle proteine. Staremo a guardare per vedere come funziona.

Rif: arxiv.org/abs/1805.07470 : Risolvere il Cubo di Rubik senza la conoscenza umana

nascondere