L'algoritmo evolutivo supera le macchine di deep learning nei videogiochi

Con tutta l'eccitazione per le reti neurali e le tecniche di deep learning, è facile immaginare che il mondo dell'informatica sia composto da poco altro. Le reti neurali, dopotutto, hanno iniziato a superare le prestazioni degli umani in compiti come il riconoscimento di oggetti e volti e in giochi come scacchi, Go e vari videogiochi arcade.

Queste reti si basano sul modo in cui funziona il cervello umano. Niente potrebbe avere più potenziale di quello, giusto?

Non proprio. Un tipo di elaborazione completamente diverso ha il potenziale per essere significativamente più potente delle reti neurali e del deep learning. Questa tecnica si basa sul processo che ha creato il cervello umano: l'evoluzione. In altre parole, una sequenza di cambiamento e selezione iterativa che ha prodotto le macchine più complesse e capaci conosciute dall'umanità: l'occhio, l'ala, il cervello e così via. Il potere dell'evoluzione è una meraviglia da vedere.

Ecco perché gli informatici hanno tentato a lungo di sfruttarne le capacità. La cosiddetta informatica evolutiva ha raggiunto risultati notevoli negli ultimi 30 anni da quando è stata utilizzata per la prima volta per l'ottimizzazione delle linee di produzione in fabbrica per i trattori.

Ma negli ultimi anni, quest'area dell'informatica ha dovuto giocare in secondo piano rispetto alle macchine di deep learning e al loro enorme successo.

Oggi la situazione sembra destinata a cambiare grazie al lavoro di Dennis Wilson e di alcuni colleghi dell'Università di Tolosa in Francia. Questi ragazzi hanno mostrato come l'informatica evolutiva possa eguagliare le prestazioni delle macchine di deep learning al compito emblematico che li ha portati alla fama per la prima volta nel 2013: la capacità di superare gli umani nei videogiochi arcade come Pong, Breakout e Space Invaders. Il lavoro suggerisce che l'informatica evolutiva dovrebbe essere celebrata tanto quanto le sue relazioni basate sull'apprendimento profondo.

Il calcolo evolutivo funziona in un modo completamente diverso rispetto alle reti neurali. L'obiettivo è creare codice per computer che risolva un problema specifico utilizzando un approccio in qualche modo controintuitivo.

Il modo convenzionale per creare codice è scriverlo partendo dai primi principi con un obiettivo specifico in mente.

L'informatica evolutiva utilizza un approccio diverso. Inizia con codice generato interamente a caso. E non solo una versione, ma molte versioni, a volte centinaia di migliaia di pezzi di codice assemblati casualmente.

Ciascuno di questi codici viene testato per vedere se raggiunge l'obiettivo richiesto. E, naturalmente, tutto il codice è orribile perché è generato casualmente.

Ma solo per caso, alcuni pezzi di codice sono un po' meglio di altri. Questi pezzi vengono quindi riprodotti in una nuova generazione di codice, che include più copie dei codici migliori.

Tuttavia, la generazione successiva non può essere una copia identica della prima. Invece, deve cambiare in qualche modo. Queste modifiche possono comportare il cambio di due termini nel codice, una sorta di mutazione puntiforme. Oppure possono coinvolgere due codici che vengono tagliati a metà e le metà scambiate, come la ricombinazione sessuale.

Ciascuna della nuova generazione viene quindi testata per vedere come funziona. I migliori pezzi di codice sono riprodotti preferenzialmente in un'altra generazione e così via.

In questo modo il codice si evolve. Nel tempo, diventa migliore e dopo molte generazioni, se le condizioni sono giuste, può diventare migliore di quanto qualsiasi programmatore umano possa progettare.

Gli informatici hanno applicato con successo approcci evolutivi a problemi che vanno dalla progettazione di robot alla costruzione di parti di aeromobili.

Ma è caduto in disgrazia a causa dell'enorme interesse per il deep learning. Quindi una domanda importante è se può eguagliare le prestazioni delle macchine di deep learning. Per scoprirlo, Wilson e colleghi hanno utilizzato l'approccio per sviluppare codice in grado di controllare i giochi per computer arcade risalenti agli anni '80 e '90.

Questi giochi sono disponibili in un database chiamato Arcade Learning Environment, che viene sempre più utilizzato per testare il comportamento di apprendimento di algoritmi di vario tipo. Il database è composto da 61 giochi Atari, come Pong, Space Invaders, Breakout e Kung Fu Master.

Il compito è creare un algoritmo in grado di riprodurre un gioco come Pong guardando solo l'output dello schermo, allo stesso modo in cui giocano gli umani. Quindi l'algoritmo deve analizzare ogni posizione di gioco e poi decidere come muoversi per massimizzare il suo punteggio.

I controlli per tutti i giochi sono gli stessi. Questi corrispondono alle otto direzioni in cui il controller può essere spostato (su, giù, sinistra e destra più quattro direzioni diagonali), la pressione di un pulsante, gli stessi otto movimenti combinati con la pressione di un pulsante e senza fare nulla. Non tutti i giochi utilizzano tutte le 18 combinazioni possibili e alcuni ne usano solo quattro.

Il codice deve prima essere creato. L'approccio evolutivo richiede un vocabolario di termini che possono essere concatenati per formare codice informatico. I termini vanno da azioni semplici come ADD (x+y)/2 a azioni più complesse, come restituire il vettore x a 1 elemento se x è uno scalare.

La scelta dei termini che compongono questo vocabolario è importante, e Wilson e compagni utilizzano un insieme già definito per la programmazione genetica cartesiana (come viene chiamata la loro tecnica).

Il processo inizia creando casualmente un codice contenente 40 termini. Questo è il genoma del programma. Questo genoma viene quindi testato per vedere come gioca bene il gioco, come giudicato dal punteggio. A seconda delle prestazioni, il genoma viene quindi riprodotto con mutazioni e testato di nuovo, e così via. In totale, il team ha testato 10.000 genomi in questo modo.

I risultati costituiscono una lettura interessante. All'inizio, i genomi sono terribili nel gioco. Ma col tempo migliorano. E dopo molte generazioni, suonano bene, a volte meglio degli umani.

Molti genomi hanno finito per giocare strategie di gioco completamente nuove, spesso complesse. Ma a volte ne trovavano di semplici che gli umani avevano trascurato.

Ad esempio, giocando a Kung Fu Master, l'algoritmo evolutivo ha scoperto che l'attacco più prezioso era un pugno accovacciato. Accovacciarsi è più sicuro perché schiva metà dei proiettili diretti al giocatore e attacca anche qualsiasi cosa nelle vicinanze. La strategia dell'algoritmo consisteva nell'utilizzare ripetutamente questa manovra senza altre azioni. Con il senno di poi, l'uso esclusivo del pugno accovacciato ha senso.

Ciò ha sorpreso gli attori umani coinvolti nello studio. Impiegando questa strategia a mano ha ottenuto un punteggio migliore rispetto al normale gioco, e l'autore ora usa pugni accovacciati esclusivamente quando attacca in questo gioco, affermano Wilson e co.

Nel complesso, il codice evoluto ha giocato bene a molti dei giochi, superando persino gli umani in giochi come Kung Fu Master. Altrettanto significativamente, il codice evoluto è buono quanto molti approcci di deep learning e li supera in giochi come Asteroids, Defender e Kung Fu Master.

Produce anche un risultato più rapidamente. Sebbene i programmi siano relativamente piccoli, molti controller sono competitivi con metodi all'avanguardia per il set di benchmark Atari e richiedono meno tempo di addestramento, affermano Wilson e co.

Il codice evoluto ha un altro vantaggio. Poiché è piccolo, è facile vedere come funziona. Al contrario, un problema ben noto con le tecniche di deep learning è che a volte è impossibile sapere perché hanno preso decisioni particolari, e questo può avere ramificazioni pratiche e legali.

Nel complesso, questo è un lavoro interessante che dovrebbe suggerire agli informatici che si stanno concentrando esclusivamente sull'apprendimento profondo che potrebbe mancare un trucco. L'approccio evolutivo è una potente alternativa che può essere applicata in un'ampia serie di situazioni.

In effetti, alcuni ricercatori hanno iniziato a usarlo per sviluppare migliori macchine di deep learning. Che cosa potrebbe andare storto?

Rif: https://arxiv.org/abs/1806.05695 : Programmi semplici in evoluzione per giocare ai giochi Atari

nascondere