Chi ha seguito un corso di informatica conosce sicuramente gli algoritmi di ordinamento. Esistono numerosi modi per ottenere il risultato finale, sfruttando le librerie standard dei linguaggi di programmazione. Finora l’obiettivo era ottimizzare gli algoritmi esistenti per velocizzare l’ordinamento. Google DeepMind ha invece sviluppato AlphaDev, un sistema IA in grado di scoprire algoritmi più veloci da zero, quindi senza partire da quelli esistenti.
IA scopre nuovi algoritmi di ordinamento
Invece di un linguaggio di alto livello, come C++, gli scienziati di DeepMind hanno utilizzato il linguaggio Assembly, intermedio tra linguaggio di alto livello e linguaggio macchina. AlphaDev deriva da AlphaZero, il modello di machine learning che ha sconfitto i campioni del mondo di scacchi e Go, quindi è stato utilizzato lo stesso approccio.
Per scoprire i nuovi algoritmi di ordinamento è stato creato un “assembly game” a singolo giocatore. Ad ogni turno, AlphaDev osserva l’algoritmo generato e le informazioni contenute nella CPU. Successivamente sceglie un’istruzione da aggiungere all’algoritmo. L’operazione è piuttosto complessa, in quanto esiste un numero enorme di possibili combinazioni.
L’algoritmo viene costruito un’istruzione alla volta. AlphaDev verifica la correttezza confrontando i risultati con quelli attesi e vince il gioco se scopre gli algoritmi più veloci. Il modello IA ha ottenuto un incremento delle prestazioni fino al 70% per sequenze brevi (da 3 a 5 elementi) e all’1,7% per sequenze con oltre 250.000 elementi (numeri, lettere o altro). Le sequenze brevi sono quelle più usate.
Gli algoritmi sono scritti in linguaggio Assembly, quindi sono stati tradotti in linguaggio C++ e aggiunti alla libreria di ordinamento LLVM libc++. AlphaDev è stato utilizzato anche per migliorare un algoritmo di hashing molto utilizzato, ottenendo un incremento di velocità del 30%.
Ti potrebbe interessare
8 giu 2023