Programmazione competitiva con AlphaCode

'Competitive programming with AlphaCode'

Nota: Questo blog è stato pubblicato per la prima volta il 2 febbraio 2022. Dopo la pubblicazione del paper su Science l’8 dicembre 2022, abbiamo apportato piccoli aggiornamenti al testo per riflettere questo.

Risolvere problemi nuovi e raggiungere un nuovo traguardo nella programmazione competitiva

Trovare soluzioni a problemi imprevisti è una seconda natura nell’intelligenza umana – un risultato del pensiero critico basato sull’esperienza. La comunità del machine learning ha fatto enormi progressi nella generazione e comprensione dei dati testuali, ma gli avanzamenti nella risoluzione di problemi rimangono limitati a problemi matematici e di programmazione relativamente semplici, o al recupero e copia di soluzioni esistenti.

Come parte della missione di DeepMind di risolvere l’intelligenza, abbiamo creato un sistema chiamato AlphaCode che scrive programmi informatici a un livello competitivo. AlphaCode ha raggiunto un ranking stimato tra il 54% dei partecipanti nelle competizioni di programmazione, risolvendo problemi nuovi che richiedono una combinazione di pensiero critico, logica, algoritmi, codifica e comprensione del linguaggio naturale.

Pubblicato sulla copertina di Science, il nostro paper dettaglia AlphaCode, che utilizza modelli linguistici basati su transformer per generare codice su una scala senza precedenti e filtrare in modo intelligente un piccolo insieme di programmi promettenti.

• Annuncio di Google DeepMind
• Come possiamo integrare i valori umani nell’IA?
• La più recente ricerca di DeepMind al ICLR 2023

Abbiamo convalidato le nostre prestazioni utilizzando competizioni ospitate su Codeforces, una piattaforma popolare che ospita regolari competizioni che attirano decine di migliaia di partecipanti da tutto il mondo che vengono a testare le proprie abilità di programmazione. Abbiamo selezionato per la valutazione 10 competizioni recenti, più recenti dei nostri dati di allenamento. AlphaCode si è posizionato a circa il livello del concorrente mediano, segnando la prima volta che un sistema di generazione automatica di codice AI ha raggiunto un livello competitivo di prestazioni nelle competizioni di programmazione.

Per aiutare gli altri a basarsi sui nostri risultati, abbiamo reso disponibili il nostro dataset di problemi di programmazione competitiva e soluzioni su GitHub, inclusi test estesi per garantire che i programmi che superano questi test siano corretti – una caratteristica critica che i dataset attuali non hanno. Speriamo che questo benchmark porti a ulteriori innovazioni nella risoluzione di problemi e generazione di codice.

La programmazione competitiva è un’attività popolare e sfidante; centinaia di migliaia di programmatori partecipano a competizioni di codifica per acquisire esperienza e mostrare le proprie abilità in modi divertenti e collaborativi. Durante le competizioni, i partecipanti ricevono una serie di lunghe descrizioni di problemi e qualche ora per scrivere programmi per risolverli.

I problemi tipici comprendono la ricerca di modi per posizionare strade e edifici entro determinati vincoli, o la creazione di strategie per vincere giochi da tavolo personalizzati. I partecipanti vengono poi classificati principalmente in base al numero di problemi risolti. Le aziende utilizzano queste competizioni come strumenti di reclutamento e tipi simili di problemi sono comuni nei processi di assunzione di ingegneri software.

“Posso dire con sicurezza che i risultati di AlphaCode hanno superato le mie aspettative. Ero scettico perché anche nei semplici problemi di competizione spesso è necessario non solo implementare l’algoritmo, ma anche (e questa è la parte più difficile) inventarlo. AlphaCode è riuscito a ottenere prestazioni al livello di un nuovo concorrente promettente. Non vedo l’ora di vedere cosa ci riserva il futuro!” ‍ – Mike Mirzayanov, Fondatore di Codeforces

Le abilità di risoluzione dei problemi necessarie per eccellere in queste competizioni vanno oltre le capacità dei sistemi AI esistenti. Tuttavia, combinando i progressi nei modelli di trasformatori su larga scala (che hanno recentemente dimostrato abilità promettenti nella generazione di codice) con campionamento e filtraggio su larga scala, abbiamo compiuto progressi significativi nel numero di problemi che possiamo risolvere. Pre-alleniamo il nostro modello su codice pubblico selezionato da GitHub e lo perfezioniamo sul nostro dataset relativamente piccolo di programmazione competitiva.

Al momento della valutazione, creiamo un’enorme quantità di programmi in C++ e Python per ogni problema, di ordini di grandezza superiori rispetto ai lavori precedenti. Quindi filtriamo, raggruppiamo e riordiniamo tali soluzioni in un piccolo insieme di 10 programmi candidati che inviamo per una valutazione esterna. Questo sistema automatizzato sostituisce il processo di prova ed errore dei concorrenti di debug, compilazione, superamento dei test e infine l’invio.

Con il permesso di Codeforces, abbiamo valutato AlphaCode simulando la partecipazione a 10 competizioni recenti. Il lavoro impressionante della comunità di programmazione competitiva ha creato un ambito in cui non è possibile risolvere i problemi attraverso scorciatoie come duplicare soluzioni già viste o provare ogni algoritmo potenzialmente correlato. Invece, il nostro modello deve creare soluzioni nuove e interessanti.

Nel complesso, AlphaCode si è posizionato approssimativamente al livello del concorrente mediano. Sebbene lontano dal vincere competizioni, questo risultato rappresenta un notevole salto nelle capacità di risoluzione di problemi di intelligenza artificiale e speriamo che i nostri risultati ispirino la comunità di programmatori competitivi.

“Risolvere problemi di programmazione competitiva è davvero difficile, richiedendo sia buone capacità di codifica che creatività nella risoluzione dei problemi negli esseri umani. Sono rimasto molto impressionato dal fatto che AlphaCode potesse fare progressi in questo ambito e sono entusiasta di vedere come il modello utilizzi la comprensione delle dichiarazioni per produrre codice e guidare la sua esplorazione casuale per creare soluzioni.” ‍ – Petr Mitrichev, Ingegnere del Software, Google & Programmatore Competitivo di Classe Mondiale

Perché l’intelligenza artificiale possa aiutare l’umanità, i nostri sistemi devono essere in grado di sviluppare capacità di risoluzione dei problemi. AlphaCode si è classificato tra i primi il 54% nelle competizioni di programmazione del mondo reale, un progresso che dimostra il potenziale dei modelli di deep learning per compiti che richiedono pensiero critico. Questi modelli sfruttano in modo elegante il moderno apprendimento automatico per esprimere soluzioni a problemi come codice, tornando così alle radici del ragionamento simbolico dell’intelligenza artificiale di decenni fa. E questo è solo l’inizio.

La nostra esplorazione della generazione di codice lascia ampio spazio per miglioramenti e suggerisce idee ancora più eccitanti che potrebbero aiutare i programmatori a migliorare la loro produttività e aprire il campo a persone che attualmente non scrivono codice. Continueremo questa esplorazione e speriamo che ulteriori ricerche porteranno a strumenti per migliorare la programmazione e avvicinarci a un’intelligenza artificiale di risoluzione dei problemi.

‍

Visualizza le soluzioni di AlphaCode ed esplora il modello su alphacode.deepmind.com