UC Berkeley’s Automated Crossword Solver Achieves 99.9% Letter Accuracy, Wins Top Tournament

For more than a century, the crossword puzzle has been one of the world’s most popular games for testing vocabulary, trivia, common sense and wordplay — all while requiring players to reason out multiple intersecting answers. The crossword puzzle has also attracted the interest of AI researchers, whose automated solvers outperform most human hobbyists. These AI agents however struggle with some of the complex linguistic phenomena present in crosswords, and even leading systems still trailed expert human players by significant margins until a UC Berkeley team got involved.

In the new paper Automated Crossword Solving, researchers from UC Berkeley and Matthew Ginsberg LLC present the Berkeley Crossword Solver (BCS), an end-to-end state-of-the-art system for automatically solving challenging crossword puzzles that captured first place in the American Crossword Puzzle Tournament.

The BCS is built on the premise that some clues are hard to answer without any letter constraints, but other (easier) clues are more standalone. The team thus treats the solving process using a multi-stage approach, where each question is first dealt with independently, and the answers are entered into the puzzle. Uncertain answers are then revisited while conditioning on the predicted letter constraints.

The BCS pipeline comprises three steps: question answering (QA), loopy belief propagation, and local search. The team builds their QA model using a bi-encoder architecture that generates a list of answer candidates with corresponding probabilities for each clue. They then refine the probabilities with loopy belief propagation to maximize the total number of correct words and letters in the solution and generate an n-best list of puzzle candidates. Finally, they fill the grid with greedy search and then iteratively improve uncertain areas of the puzzle via local search.

In their empirical study, the team compared the proposed system to the state-of-the-art Dr. Fill system on themed and themeless puzzles.

The BCS handily outperformed Dr. Fill, boosting exact puzzle accuracy from 57 to 82 percent on New York Times crosswords and achieving 99.9 percent letter accuracy on themeless puzzles.

In a wake-up call to cruciverbalists last spring, an early BCS Version won the live American Crossword Puzzle Tournament (ACPT), marking the first time an AI agent had surpassed top human players at the prestigious event.

The BCS code is available on the project’s GitHub. The paper Automated Crossword Solving is on arXiv.

---

Author: Hecate He | Editor: Michael Sarazen

---

We know you don’t want to miss any news or research breakthroughs. Subscribe to our popular newsletter Synced Global AI Weekly to get weekly AI updates.