Once again, the capabilities of artificial intelligence have been put to the test, with interesting results.
Researchers at the University of California at Berkeley recently introduced Berkeley Crossword Solver, the first computer program capable of beating all human competitors in the world’s largest crossword puzzle tournament.
An algorithm capable of solving complex crossword puzzles efficiently
The algorithm developed at UC Berkeley is capable of solving crossword puzzles by means of a procedure in which, first, a probability distribution is generated over the possible answers to each clue presented, presenting them to the system as a question. The algorithm has the task of mapping both the questions and the answers in a shared integrated space, which allows managing the conflicts —through a probabilistic inference method— between the possible answers, according to how they intersect in the crossword grid. .
To refine the results obtained, the algorithm executes a search in a local database, with the purpose of reaffirming the choice of certain letters that do not generate enough confidence to be considered adequate. To perform this check, the system uses a generative language model, which replaces conflicting letters iteratively, until a locally optimal solution is found.
This development was called Berkeley Crossword Solver and was designed to solve only American-style crossword puzzles. These crossword puzzles typically involve general knowledge topics, puns, and challenging clues. They usually range in grid size from 15×15 to 21×21.
East model was subjected to crossword review by five of the leading crossword publishers, including the acclaimed New York Times publications. As a result of these tests, it was possible to demonstrate that the system obtains a letter accuracy of 99.7% on average.
An algorithm won the most important crossword competition
The American Crossword Puzzle Tournament (ACPT) is the largest and longest running crossword puzzle tournament and is hosted by Will Shortz, the New York Times crossword editor.
To participate in the 2021 edition of the ACPT, the Berkeley team teamed up with Matt Ginsberg, developer of Dr. Fill, a software that previously participated in the same instance in 2012, achieving 141st place among 650 competitors. In this new opportunity, an earlier version of the Berkeley quality control system was combined with the Dr. Fill search procedure. This combination gave good results, making them winners of the contest, against more than a thousand competitors. The system solved all seven challenged puzzles in less than a minute, with only three letters missing in two puzzles.
This system will continue subject to further refinements. To encourage its development, a dataset of 6.4 million question-answer clues and the code for this tool, along with an interactive demo, were published on the Web site. Berkeley Crossword Solver.
