Computer Comes First In Crossword Competition
Written by Sue Gee   
Sunday, 02 May 2021

After more than a decade of competing in the annual American Crossword Puzzle Tournament, Dr. Fill, a computer program devised by Matt Ginsberg came at the top of the rankings. It convincingly beating over 1300 human opponents in another triumph for AI. Its success this time around can be attributed to the contribution of a neural network.

amcrosswordbanner

Directed by New York Times Crossword Puzzle Editor Will Shortz, the ACPT is the nation's oldest and largest crossword competition. Solvers tackle original crosswords devised specially for this event with scoring is based on accuracy and speed. 

We previously reported on it in 2012, the year when Matt Ginsberg's Dr. Fill, whose name is wordplay on crosswording and talk show host Dr. Phil McGraw, first participated. On that occasion, despite having predicted that he would be placed in the top 30, Dr. Fill was ranked 141st out of 600 entrants. Over subsequent years its best achievement was 11th place in 2017.

The reason for its poor showing back in 2012 was that the AI was completely stumped by puzzles that were "particularly innovative" one of which required words to be spelled backwards and the other answers that read only only across and down, but diagonally as well. Changing the game in this way put the algorithmic approach at a disadvantage compared to the human brain.

As well as having benefited from the experience of all the twists and turns the contest had devised in the intervening years, there were two new factors in Dr Fill's favor in 2021. Firstly, the contest was held online which meant that rather than running on a laptop computer Dr.Fill was able to take advantage of a custom-built desktop with a 64-core processor and two GPUs.

Secondly, and possibly the real game-changer, was that the software combined Dr.Fill's original weighted CSPs (Constraint Satisfaction Problems) approach with the neural network of the Berkeley Crossword Solver. Originated in 2020 by a team at UC Berkeley including the head of the Natural Language Processing Group, Dan Klein, this is an automated crossword solver that uses neural network models for a question-answering system using Dr. Fill as its constraint solver.

Shortly before this year's APC Tournament Klein emailed Ginsberg suggesting a collaboration in which the Crossword Solver was plugged into Dr. Fill. This resulted in an AI in which Ginsberg’s system handled searching and placing answers into the grid -  the mathematical side of things-, while the Berkeley team’s system "unriddled" cryptic clues and focused on understanding the human language aspects.  

The combination was a game changer. While Dr. Fill wasn’t perfect - it made three errors over the course of the tournament - it made up for its mistakes due to its speed, solving most puzzles in well under a minute so that at the end of the main block of puzzles 1-7 it had a score of 12,825 beating the top human, Erik Agard, by 15 points. 

Dr. Fill went on to solve the Playoff puzzle perfectly in 49 seconds, over two minutes faster than Tyler Hinman who, as the winner, was awarded the trophy and the $3,000 first prize.

We have now seen neural networks beat the human competition at Go, Poker, computer games and many more.

 

acpt

 

More Information

American Crossword Puzzle Tournament

Dr.Fill: Crosswords and an Implemented Solver for Singly Weighted CSPs

Berkeley Crossword Solver

Related Articles

Computer Competes in Crossword Tournament

Neural Networks Applied To Machine Translation

AI Beats Top Poker Players

AlphaFold Solves Fundamental Biology Problem

AI Helps Make Chess Better

 

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

 

Banner


Deno Developers Form Company
15/04/2021

The developers of Deno, the JavaScript and TypeScript runtime from the creator of Node.js, have announced they've formed a company and had an injection of funds.



Feeling Your Feet In VR
28/04/2021

When you walk feedback from your feet adds to the experience. A research study from Japan investigates how best to incorporate the sensation of walking into virtual reality.


More News

square

 



 

Comments




or email your comment to: comments@i-programmer.info

Last Updated ( Sunday, 02 May 2021 )