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


MariaDB 10 Available
10/04/2014

The stable version of MariaDB 10 has been released with better performance and new features. One major change is support for data in non-relational databases courtesy of the new Connect engine.



Mozilla Wants To Recommend The Best Tools
17/04/2014

Mozilla is putting together a core set of tools and recommendations that it considers the most useful for making Web apps and is asking for input from the developer community.


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.