Beloved crossword editor will update#
Beloved crossword editor will code#

To encourage future work, we are releasing a dataset of 6.4M question answer clues, a demo of the Berkeley Crossword Solver, and our code at. We are really excited about the challenges that remain in crosswords, including handling difficult themes and more complex wordplay. Our joint submission solved all seven puzzles in under a minute, missing just three letters across two puzzles.įigure 5: Results from the 2021 American Crossword Puzzle Tournament (ACPT) We teamed up with Dr.Fill’s creator Matt Ginsberg and combined an early version of our QA system with Dr.Fill’s search procedure to outscore all 1033 human competitors in the 2021 ACPT. Dr.Fill’s first competition was in ACPT 2012, and it ranked 141st out of 650 competitors. Proverb is a 1998 system that ranked 213th out of 252 competitors in the tournament. Two prior approaches to computer crossword solving gained mainstream attention and competed in the ACPT: Proverb and Dr.Fill.

The American Crossword Puzzle Tournament (ACPT) is the largest and longest-running crossword tournament and is organized by Will Shortz, the New York Times crossword editor. Winning The American Crossword Puzzle Tournament It solves 81.7% of puzzles without a single mistake, which is a 24.8% improvement over the previous state-of-the-art system.įigure 4: Results compared to previous state-of-the-art Dr.Fill Our system obtains 99.7% letter accuracy on average, which jumps to 99.9% if you ignore puzzles that involve rare themes. We evaluated the BCS on puzzles from five major crossword publishers, including The New York Times. We score these alternate characters using a character-level language model (ByT5, Xue et al., 2022), that handles novel answers better than our closed-book QA model.įigure 3: Example changes made by our local search procedure Local search works by using a guided proposal distribution in which characters that had lower marginal probabilities during belief propagation are iteratively replaced until a locally optimal solution is found. The BCS then refines this solution using a local search that tries to replace low confidence characters in the grid. After belief propagation converges, the BCS obtains an initial puzzle solution by greedily taking the highest likelihood answer at each position. This allows information from high confidence predictions to propagate to more challenging clues.

Beloved crossword editor will update#

We conducted a manual error analysis and found that our QA model typically performed well on questions involving knowledge, commonsense reasoning, and definitions, but it often struggled to understand wordplay or theme-related clues.Īfter running the QA model on each clue, the BCS runs loopy belief propagation to iteratively update the answer probabilities in the grid. Compared to the previous state-of-the-art method for answering crossword clues, this approach obtained a 13.4% absolute improvement in top-1000 QA accuracy. Rather than passages, however, our approach maps both questions and answers into a shared embedding space and finds answers directly. The BCS’s question answering model is based on DPR (Karpukhin et al., 2020), which is a bi-encoder model typically used to retrieve passages that are relevant to a given question. First, it generates a probability distribution over possible answers to each clue using a question answering (QA) model second, it uses probabilistic inference, combined with local search and a generative language model, to handle conflicts between proposed intersecting answers.įigure 2: Architecture diagram of the Berkeley Crossword Solver The BCS uses a two-step process to solve crossword puzzles.

Domain ender that UC Berkeley was one of the first schools to adopt (3).

They’re given out at Berkeley’s HAAS School (4).

Here are a handful of example clues from our dataset (answers at the bottom of this post):

While some clues are similar to factoid question answering, others require relational reasoning or understanding difficult wordplay. Many clues are vague or underspecified and can’t be answered until crossing constraints are taken into account. The most recent version is the current top-performing system on crossword puzzles from The New York Times, achieving 99.7% letter accuracy (see the technical paper, web demo, and code release).Ĭrosswords are challenging for humans and computers alike. The BCS combines neural question answering and probabilistic inference to achieve near-perfect performance on most American-style crossword puzzles, like the one shown below:įigure 1: Example American-style crossword puzzleĪn earlier version of the BCS, in conjunction with Dr.Fill, was the first computer program to outscore all human competitors in the world’s top crossword tournament. We recently published the Berkeley Crossword Solver (BCS), the current state of the art for solving American-style crossword puzzles. Eric Wallace, Nicholas Tomlin, Albert Xu, Kevin Yang, Eshaan Pathak