Un Algoritmo ha vinto il più importante Concorso di Cruciverba

Ancora una volta le capacità dell’intelligenza artificiale sono state messe alla prova, con risultati interessanti. I ricercatori dell’Università della California a Berkeley hanno recentemente introdotto Berkeley Crossword Solver, il primo programma per computer in grado di battere tutti i concorrenti umani nel più grande torneo di cruciverba del mondo.

Un algoritmo in grado di risolvere in modo efficiente cruciverba complessi

L’algoritmo sviluppato alla UC Berkeley è in grado di risolvere i cruciverba attraverso una procedura in cui, in primo luogo, viene generata una distribuzione di probabilità sulle possibili risposte a ciascun indizio presentato, presentandole al sistema come una domanda. L’algoritmo ha il compito di mappare sia le domande che le risposte in uno spazio integrato condiviso, che permette di gestire i conflitti (attraverso un metodo di inferenza probabilistica) tra le possibili risposte, a seconda di come si intersecano nella griglia del cruciverba.

Per affinare i risultati ottenuti, l’algoritmo esegue una ricerca in un database locale, con lo scopo di riaffermare la scelta di alcune lettere che non generano sufficiente confidenza per essere considerate adeguate. Per eseguire questo controllo, il sistema utilizza un modello di linguaggio generativo, che sostituisce le lettere in conflitto in modo iterativo, fino a trovare una soluzione ottimale a livello locale.

Questo sviluppo è stato chiamato Berkeley Crossword Solver ed è stato progettato per risolvere solo cruciverba in stile americano. Questi cruciverba di solito coinvolgono argomenti di cultura generale, giochi di parole e indizi impegnativi. Di solito hanno una dimensione della griglia da 15×15 a 21×21.

Questo modello è stato sottoposto alla valutazione dei cruciverba da cinque dei principali editori di cruciverba, comprese le acclamate pubblicazioni del New York Times. Come risultato di questi test, è stato possibile dimostrare che il sistema ottiene in media un’accuratezza delle lettere del 99,7%.

Un algoritmo ha vinto il più importante concorso di cruciverba

L’American Crossword Puzzle Tournament (ACPT) è il torneo di cruciverba più grande e più lungo ed è ospitato da Will Shortz, l’editor di cruciverba del New York Times.

Per partecipare all’edizione 2021 dell’ACPT, il team di Berkeley ha collaborato con Matt Ginsberg, sviluppatore di Dr Fill, un software che aveva già partecipato nella stessa istanza nel 2012, ottenendo il 141° posto su 650 concorrenti. In questa nuova opportunità, una versione precedente del sistema di controllo qualità Berkeley è stata combinata con la procedura di ricerca Dr Fill. Questa combinazione ha dato buoni risultati, rendendoli vincitori del concorso, contro più di mille concorrenti. Il sistema ha risolto tutti e sette gli enigmi sfidati in meno di un minuto, con solo tre lettere mancanti in due enigmi.

Questo sistema continuerà ad essere soggetto a ulteriori perfezionamenti. Per incoraggiarne lo sviluppo, sul sito Web di Berkeley Crossword Solver sono stati pubblicati un set di dati di 6,4 milioni di indizi di risposta alle domande e il codice per questo strumento, insieme a una demo interattiva.