Computer Competes in Crossword Tournament
Written by Alex Armstrong   
Monday, 19 March 2012

Can a computer program beat the best human crossword puzzle solvers? Not yet according to the results of last weekend's American Crossword Puzzle Tournament in which the computer was foiled by the ingenuity of the human puzzle setters.

Artificial intelligence can outwit humans at chess and at knowledge quizzes, as demonstrated by IBM's Watson in the Jeopardy TV show last year, but it's not yet honed the subtle skills required to beat us at solving crossword puzzles.

 

ginsberg

 

Dr.Fill, a computer program devised by Matt Ginsberg, an artificial intelligence scientist who also constructs crossword puzzles for the New York Times, was an unofficial entrant in the 35th annual crossword challenge in which players solve seven puzzles created especially for the event.

Dr.Fill's participation in the competition was unofficial, in that only humans can win the challenge, but it was also well publicized. Matt Ginsberg presented a talk on the inner workings of his program, whose name is wordplay on crosswording and talk show host Dr. Phil McGraw. This is a topic on which has already published an academic paper in the Journal of Artificial Intelligence Research.

Prior to the event Ginsberg had expected to do well, predicting a place in the top 30 on the basis of having excelled in most simulations of the 15 past tournaments.

However, as Steve Lohr pointed out, writing in the New York Times in advance of the contest:

Humans and machines play the games very differently. Humans recognize patterns based on accumulated knowledge and experience, while computers make endless calculations to determine the most statistically probable answer.

Lohr also quoted artificial intelligence expert and Google research director, Peter Norvig as saying:

“We’re at the point where the two approaches are about equal. But people have real experience. A computer has a shadow of that experience.”

In the event it was the ability of humans to notice and adapt to changes in established patterns that gave them the advantage.

 

acpt

 

Although Dr Fill completed the seventh and final puzzle, supposedly the most difficult one, perfectly it was stumped by the second and fifth puzzles, ones that were described as "particularly innovative". One of them included words that had to be spelled backwards and the other required answers not just across and down, but diagonally as well.

Before the contest, last year's winner Dan Feyer (who went on to win again last weekend) said he expected that the contest would include "a puzzle or two that involved innovative twists or patterns to trip up Dr. Fill."

So were puzzles chosen deliberately to put the computer program at a disadvantage? Tournament organizer Will Shortz shook his head and smiled when that question was put to him.

So given these novel twists which Dr Fill could not have anticipated, the ranking of 141st out of 600. which places it in the top fourth of human contestants, isn't too shabby a score. Hopefully it won't deter Matt Ginsberg from pursuing his AI crossword-solving hobby. The hobby is one which fits well with his full time occupation. He is chief executive of On Time Systems whose software is used by the United States Air Force, for calculating the most efficient flight paths for aircraft. Both areas share some of the same statistical techniques - weighted CSPs (Constraint Satisfaction Problems).

More Information

American Crossword Puzzle Tournament

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

 

Related Articles

Watson wins on Jeopardy

Watson wins Jeopardy! - trick or triumph

IBM takes on Jeopardy - has AI really got this far?

 

blog comments powered by Disqus

 

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

 

Banner


Node.js Fork - Now You Have A Choice To Make
08/12/2014

One of the big advantages of open source is that if you don't like the current state of things you can simply create a fork and make your own version of the project. However, not all forks are equal a [ ... ]



The New Android Compilers - Meet Jack And Jill
12/12/2014

The new compiler toolchain, Jack and Jill, were included in the recent release of Android SDK 21.1, but only now has Google explained what they are are and what they do.


More News

Last Updated ( Monday, 19 March 2012 )
 
 

   
RSS feed of news items only
I Programmer News
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.