Hail Dr Fill, il nuovo re dei cruciverba basato sull’intelligenza artificiale che batte gli umani
Il Dr Phil è stato addestrato su oltre 47.000 puzzle che sono apparsi su vari giornali e riviste.
Cinque milioni di persone in tutto il mondo risolvono ogni giorno cruciverba. Di questo, a livello globale, Dr Fill è uno dei 50 migliori giocatori di cruciverba. Ma ciò che sorprende è che il dottor Fill non è un americano di mezza età. Non è che un programma per computer, un algoritmo artificiale basato sull’intelligenza. Un anno fa, Dr Fill era considerato un programma primitivo che non poteva risolvere enigmi complessi. Oggi, dopo aver vinto il torneo di cruciverba americano del 2021, è paragonato ai migliori risolutori di puzzle umani.
Dr Fill è stato sviluppato da Mathew Ginsberg, in collaborazione con il gruppo Berkley NLP composto da studenti universitari e laureati, e supervisionato dal professor Dan Klein dell’UC Berkeley. Il team ha completato il modello finale di Dr Fill appena due settimane prima dell’inizio del torneo.
Mathew aveva sviluppato il modello primitivo quasi dieci anni fa nel tentativo di creare un programma che, a differenza di lui, potesse superare i cruciverba umani. Un decennio dopo, Mathew ha collaborato con l’UC Berkeley per renderlo una tecnologia di nuova generazione. Lo ha fatto incorporando i metodi della rete neurale di Berkeley per interpretare gli indizi che si sarebbero allineati con la struttura Ginsberg del programma per compilare in modo efficiente il cruciverba.
La sfida
Lo sviluppo di un cruciverba è uno dei compiti più impegnativi nell’apprendimento automatico . Uno sviluppatore deve creare un algoritmo che navighi tra i dati come fa la mente umana, ovvero con l’inferenza multi-hop. Oltre a questo, la sfida più grande è stata sviluppare un programma che non potesse essere basato solo sulla conoscenza. I cruciverba americani implicano un certo grado di pensiero laterale. Pertanto, il programma doveva capire che un punto interrogativo avrebbe segnalato qualche imbroglio semantico. Doveva anche comprendere le sfide linguistiche, che potevano significare mille cose diverse. La conclusione, quindi, era che l’algoritmo non poteva cercare risposte semplici, che sarebbero state evidenti.
Inoltre, anche la conclusione del programma è stata impegnativa. Tuttavia, gli sviluppatori hanno deciso di contrastarlo codificando l’algoritmo per terminare se fosse trascorso un minuto intero.
Dr Fill garantisce il puzzle come completo e lo termina dopo che soddisfa uno dei seguenti criteri:
– Quando dopo la scansione, l’algoritmo non può apportare alcun miglioramento al puzzle
– Se un’iterazione LDS (ciclo dell’algoritmo) viene completata senza alcun cambiamento nel puzzle
– Quando viene raggiunto il limite di tempo del torneo
In che modo il dottor Fill ha superato in astuzia gli umani?
Dr Fill ha un approccio profondamente metodico ai cruciverba. Durante l’allenamento, l’ algoritmo ha lavorato sui cruciverba sette giorni su sette.
Risolvendo il cruciverba del New York Times (il livello di difficoltà dei puzzle del New York Times aumenta durante la settimana), Dr Fill ha risolto i puzzle dei primi tre giorni “abbastanza facilmente”. Ha fatto bene anche il venerdì e il sabato, ma ha faticato il giovedì e la domenica.
Dr Fill è stato addestrato su oltre 47.000 puzzle che sono apparsi su vari giornali e riviste. Simile agli umani, il programma dipende dalla sua formazione in passato per cercare connessioni tra il vecchio e il nuovo. Genera centinaia di possibili soluzioni che corrispondono meglio agli indizi e le classifica in base alla probabilità della loro corrispondenza nel puzzle.
Il torneo è un sistema chiuso, il che significa che il programma non può “Google” le lacune nella sua conoscenza. Pertanto, è stato addestrato a imitare le capacità e l’archiviazione imperfette dell’essere umano e a lavorare con questo.
Il programma funziona convertendo i cruciverba in problemi di soddisfazione dei vincoli ponderati (CSP) e quindi utilizza la tecnica per trovare una soluzione. Ginsberg concluse che la tecnica più efficace era una modifica della Limited Discrepancy Search (LDS). Ha anche capito che il Branch & Bound comunemente usato sembra non essere una soluzione efficace per un problema di questo tipo.
Il Dr Fill è stato formato sulle lingue per comprendere le inferenze linguistiche che ora vengono riconosciute come un passo avanti nell’elaborazione del linguaggio naturale (NLP) e una pietra miliare nell’apprendimento automatico.
La performance in ACPT
La performance del Dr Fill è stata paragonabile a quella dei migliori risolutori umani di cruciverba. Sebbene il programma sia rimasto indietro in alcune aree con un vantaggio umano, è stato superato in altre. Ha risolto enigmi in un solo minuto, due minuti più velocemente degli umani. Sebbene i cruciverba risolti dall’uomo fossero privi di errori, Dr Fill non era perfetto su tutti i puzzle. È stato teso su due e finito con errori. Tuttavia, nonostante la sua mancanza, ha vinto perché altri risolutori non erano nemmeno vicini alla sua velocità.
L’editore del New York Times Will Shortz pensa che gli enigmi di quest’anno riguardassero i punti di forza del dottor Fill. Sebbene in soggezione per l’ingegnosità e la meraviglia per il programma, pensa ancora che gli umani abbiano il vantaggio sulle macchine per risolvere “problemi disordinati, non logici e del mondo reale”, come i cruciverba.
Il successo di Dr Fill è una pietra miliare in quanto aiuterà nell’applicazione dell’intelligenza artificiale nello sviluppo di programmi che possono aiutare a risolvere i problemi del mondo reale.
