Cruciverba e intelligenza artificiale: una sfida all’ultima parola

Il sistema di intelligenza artificiale Dr.Fill – basato su GPU Nvidia – vince per la prima volta l’American Crossword Puzzle Tournament, il torneo tra i migliori giocatori di cruciverba.

Se uno più uno fa sempre due, ovunque nel mondo, al contrario dei numeri le parole possono assumere significati differenti: il campo, ad esempio, è il luogo dove cresce il grano, ma anche dove si gioca a pallone e, se manca, il nostro cellulare non funziona.

Tutto ciò diventa ancora più complesso se cerchiamo di dare un significato alle parole pronunciate durante un discorso: la stessa parola può assumere significati e sfumature differenti a seconda del contesto, dell’intonazione della voce e delle pause tra una parola e l’altra.

Avere a che fare con le parole, dunque, è sicuramente molto più complesso che gestire i numeri, come dimostra il fatto che le prime calcolatrici elettroniche sono state realizzate oltre sessant’anni fa mentre i primi programmi di traduzione (appena decenti) sono molto più recenti.

Per i computer anche l’approccio ai giochi che hanno regole precise, come gli scacchi, i giochi di carte, ecc. risulta più semplice rispetto alla gestione delle parole: i computer hanno battuto gli umani nel gioco degli scacchi nel lontano 1997, nel 2016 è stata la volta di go e nel 2019 i computer sono diventati più bravi anche nel Texas hold’em, una delle più note versioni di poker.

Con i cruciverba, o parole crociate che dir si voglia, ci sono voluti dieci anni, e solo questo mese Dr. Fill – il programma creato da Matthew Ginsberg, un ricercatore e imprenditore seriale – ha battuto i quasi 1300 partecipanti che hanno partecipato all’American Crossword Puzzle Tournament, il torneo tra i migliori giocatori di cruciverba organizzato dal New York Times.

Lo ha comunicato Will Shortz, fondatore e direttore dell’ACPT, precisando che si tratta di una vittoria non ufficiale in quanto il torneo è riservato a concorrenti umani; Dr. Fill ha risolto il puzzle finale in 49 secondi, ben due minuti in meno rispetto al primo concorrente umano.

“I cruciverba sono generalmente considerati un’attività tipicamente umana, perché coinvolgono elementi difficili da programmare come il linguaggio e una profonda conoscenza del mondo reale” ha detto Shortz, “è semplicemente incredibile che abbiano programmato un computer per risolvere i cruciverba, specialmente quelli più difficili“.

L’organizzatore del concorso ha sottolineato che il più grande vantaggio di Dr.Fill è la velocità: può riempire le caselle molto più in fretta di un umano; tuttavia, a giudicare unicamente dall’accuratezza, Dr.Fill non è ancora il migliore, in quanto durante la gara ha commesso tre errori, più di molti concorrenti umani.

Matthew Ginsberg, da sempre appassionato di cruciverba, non riuscendo a vincere i tornei ai quali partecipava, tempo fa ha pensato di realizzare un programma ad “hoc”, Dr. Fill, appunto, che ha debuttato nell’ACPT nel 2012 piazzandosi solo 141°. Negli anni successivi, il software di Ginsberg non è mai riuscito a piazzarsi tra i primi 10, a causa anche delle scarse risorse che Ginsberg ha potuto dedicare allo sviluppo del programma, in una sfida che non aveva l’impatto mediatico (e gli sponsor) che ebbe a suo tempo il primo computer che sfidò gli umani nel gioco degli scacchi.

La sfida, poi, è decisamente più complessa: i cruciverba spesso si basano su indizi criptici che richiedono una vasta e profonda cultura e un ampio vocabolario, nonché la capacità di trovare risposte che si adattino meglio alle righe e alle colonne sovrapposte di ciascun puzzle.

La svolta è arrivata dalla collaborazione tra Matthew Ginsberg e un team di ricercatori dell’UC Berkeley, del Berkeley Natural Language Processing (NPL).

Nicholas Tomlin, uno degli ingegneri del team, un anno fa aveva proposto all’NPL l’idea del suo risolutore di cruciverba; in seguito il gruppo ha iniziato a lavorare al Berkeley Crossword Solver, o BCS, un sistema di intelligenza artificiale focalizzato sulla lettura di indizi di parole crociate e sulla generazione di possibili risposte.

“Ci sono due fasi per risolvere un cruciverba“, ha dichiarato Dan Klein, professore universitario di ingegneria elettrica e informatica a capo del team. “Per prima cosa, devi fare un brainstorming delle possibili risposte per ogni indizio. La seconda fase è prendere tutte quelle possibili risposte e capire quali sono compatibili con la griglia”.

Secondo Klein, il BCS si concentra sulla prima fase della risoluzione dei cruciverba tramite un modello di apprendimento automatico. Il BCS è stato addestrato su circa 6,5 ​​milioni di coppie di indizi e risposte: risolvendo diversi esempi di cruciverba, il BCS apprende e aggiorna il suo algoritmo man mano che commette errori.

La seconda fase della risoluzione dei cruciverba è gestita dal programma Dr.Fill, che identifica le migliori ipotesi da inserire nella griglia dei cruciverba.

Il software di Ginsberg, perfezionato nel corso di molti anni, classifica tutte le risposte che si adattano ai confini della griglia di ciascun puzzle e le adatta con lettere sovrapposte da altre risposte: un classico problema di soddisfazione dei vincoli.

Sebbene i due sistemi si basino su tecniche molto diverse, entrambi parlano il linguaggio comune delle probabilità.

Klein ha sottolineato come le performance di Dr.Fill nell’ACPT rappresentino una “pietra miliare” nel campo dell’elaborazione del linguaggio naturale.

“I riempimenti dei cruciverba richiedono la creazione di connessioni laterali multi-hop con il linguaggio“, afferma ancora il professor Klein, “Quando abbiamo dato vita al progetto ho pensato che sarebbe stato un buon test per vedere come la tecnologia che abbiamo creato in questo campo avrebbe gestito quel tipo di utilizzo del linguaggio creativo“.

Le parole crociate, come tutti gli altri giochi competitivi, mettono alla prova il modo di “pensare” dei computer e aiutano i ricercatori a capire meglio i meccanismi del nostro cervello.

Data questa natura non strutturata, è sorprendente che un computer possa competere in questo campo, ed ancora più sorprendente è stato il fatto che quest’anno il sistema messo a punto da Ginsberg e dai ricercatori dell’NPL abbia vinto il concorso del New York Times.

Merito anche dell’hardware utilizzato: la sofisticata rete neurale sviluppata dal team dell’UC Berkeley è stata addestrata in pochi giorni su un sistema NVIDIA DGX-1 e distribuita su un PC dotato di una coppia di GPU NVIDIA GeForce RTX 2080 Ti che si è inserita direttamente nel sistema di Ginsberg.