Nous avons récemment publié Berkeley Crossword Solver (BCS), l’état de l’art en matière de résolution de mots croisés à l’américaine. BCS combine la réponse aux questions neurologiques avec le raisonnement probabiliste pour obtenir des performances presque parfaites sur la plupart des mots croisés de style américain, tels que ceux présentés ci-dessous :
Figure 1 : Un exemple de mots croisés à l’américaine
La version précédente de BCS, en collaboration avec le Dr Fill, a été le premier programme informatique à battre tous les concurrents humains dans le meilleur tournoi de mots croisés au monde. La dernière version est le système le plus performant actuel sur les mots croisés du New York Times, atteignant une précision des lettres de 99,7 % (voir le document technique, la vue Web et la publication du code).
Les mots croisés sont difficiles pour les humains et les ordinateurs. De nombreux indices sont ambigus ou indéfinis et ne peuvent être résolus tant que les restrictions de transit ne sont pas prises en compte. Alors que certains indices ressemblent à des réponses à des questions factuelles, d’autres nécessitent une réflexion relationnelle ou une compréhension des jeux de mots difficiles.
Voici quelques exemples d’indices tirés de notre ensemble de données (les réponses se trouvent au bas de cet article) :
- Offert chez HAAS Berkeley(4)
- horaires d’hiver. À Berkeley (3)
- Ender déclare que l’UC Berkeley a été l’une des premières écoles à accréditer (3)
- Angeleno à Berkeley, par exemple (8)
BCS utilise un processus en deux étapes pour résoudre les mots croisés. Tout d’abord, il génère une distribution de probabilité sur les réponses possibles pour chaque indice à l’aide d’un modèle question-réponse (QA) ; Deuxièmement, il utilise l’inférence probabiliste, ainsi que la recherche locale et un modèle de langage génératif, pour gérer les conflits entre les réponses croisées proposées.
Figure 2 : Schéma d’architecture du solveur de mots croisés de Berkeley
Le paradigme question-réponse dans BCS est basé sur DPR (Karpukhin et al., 2020), un paradigme d’encodeur binaire généralement utilisé pour récupérer des passages pertinents à une question donnée. Au lieu de clips, notre approche rassemble à la fois les questions et les réponses dans un espace d’intégration commun et trouve les réponses directement. Par rapport à la méthode la plus récente précédente pour répondre aux indices de mots croisés, cette approche a eu une amélioration absolue de 13,4% dans la précision des 1000 principales questions et réponses. Nous avons effectué une analyse manuelle des erreurs et constaté que notre modèle d’assurance qualité fonctionne généralement bien sur les questions impliquant des connaissances, un raisonnement et des définitions, mais a souvent des difficultés à comprendre les jeux de mots ou les preuves d’actualité.
Après avoir exécuté le modèle QA sur chaque indice, BCS exécute une propagation de croyance en boucle pour mettre à jour de manière itérative les probabilités de réponse dans le réseau. Cela permet aux informations provenant de prédictions à haut niveau de confiance de se transformer en preuves plus difficiles. Après la convergence de la propagation des croyances, le BCS obtient une solution de puzzle initiale en prenant avidement la réponse la plus élevée possible dans chaque position.
BCS améliore ensuite cette solution en utilisant une recherche locale qui tente de remplacer les caractères à faible confiance dans le réseau. La recherche locale fonctionne en utilisant une distribution de proposition dirigée dans laquelle les lettres qui avaient des probabilités marginales plus faibles pendant la propagation de la croyance sont remplacées de manière itérative jusqu’à ce qu’une solution locale optimale soit trouvée. Nous enregistrons ces substituts à l’aide d’un modèle de langage au niveau de la personnalité (ByT5, Xue et al., 2022), qui gère mieux les nouvelles réponses qu’un modèle d’assurance qualité à livre fermé.
Figure 3 : Exemple de modifications apportées par notre procédure de recherche locale
Nous avons évalué BCS sur des puzzles de cinq grands éditeurs de mots croisés, dont le New York Times. Notre système obtient une précision moyenne des lettres de 99,7 %, qui passe à 99,9 % si vous ignorez les énigmes impliquant des sujets rares. Il résout 81,7 % des énigmes sans une seule erreur, ce qui représente une amélioration de 24,8 % par rapport au système moderne précédent.
Figure 4 Résultats comparés au plus récent Dr. Phil
L’American Crossword Puzzle Tournament (ACPT) est le tournoi de mots croisés le plus important et le plus ancien, et est organisé par Will Shortz, Crossword Editor au New York Times. Deux méthodes précédentes de résolution de mots croisés par ordinateur ont attiré l’attention du grand public et ont concouru dans l’ACPT : Proverbs et Dr. Phil. Proverb est le système de 1998 qui s’est classé 213e sur 252 concurrents dans le tournoi. Le premier concours du Dr Phil a eu lieu à l’ACPT 2012 et il s’est classé 141e sur 650 concurrents. Nous nous sommes associés à Matt Ginsberg, créateur du Dr Phil, et avons combiné une première version de notre système d’assurance qualité avec les recherches du Dr Phil pour battre les 1 033 concurrents humains lors de l’ACPT 2021. Notre soumission conjointe a résolu les sept énigmes en moins d’une minute, et nous n’avons perdu que trois lettres sur deux énigmes.
Figure 5 : Résultats ACPT 2021
Nous sommes vraiment ravis des défis qui restent dans les mots croisés, y compris aborder des sujets difficiles et des jeux de mots plus complexes. Pour encourager les travaux futurs, nous publions un ensemble de données de 6,4 millions de guides de questions-réponses, une démo Berkeley Crossword Solver et notre code sur http://berkeleycrosswordsolver.com.
Réponses aux indices : MBAS, PST, EDU, INSTATER