I'm Puzzled

Hi, my name is Jon and I'm a puzzle-holic. Crossword, Sudoku, Jumble word. You name it, I play it. On airplanes, in front of the fireplace, at coffee shops. Give me a sharp pencil, a good eraser, and 15-minutes of quiet time and I'm ready to roll.

I like to tell myself that I'm pretty good at times, but I admit I'm no where as good as WebCrow, a computer program that took on--and soundly whipped--dozens of human competitors at last month's European Conference on Artificial Intelligence.

Both on-site and an on-line competitions took place, with eight different winners in the general catagories of Overall, Bilingual, Italian, and American. Participants were asked to solve five different crosswords--two Italian, two American, and one mixed). A time limit of 15 minutes was imposed for each crossword, 90 minutes total. The American-style puzzles were from the New York Times and Washington Post, and the Italian ones from La Repubblica and a local Italian paper. WebCrow competed from its " the computing department at the University of Siena. WebCrow was written by Giovanni Angelini, Marco Ernandes, and Marco Gori.

According to the authors, problems like solving crosswords from clues have been defined as AI-complete and are extremely challenging for machines since there is no closed-world assumption and they require human-level knowledge. Interestingly, for the first time since AI's kick-off, there is a first nucleus of technology, such as search engines, information retrieval and machine learning techniques, that enable computers to enfold with semantics real-life concepts. The goal of WebCrow's authors is to design a software system whose major assumption is to attack crosswords making use of the Web as its primary source of knowledge.

As described by Tom Simonite in an article in New Scientist, WebCrow uses four techniques in parallel to find possible answers to a clue. Two involve looking for the clue or a near match in a database of solved crosswords or using a dictionary. Another uses rules known to work on a kind of Italian clue with two letter answers and the fourth technique is to search the Internet. WebCrow performs a search using key words extracted from the clue. It can usually find the answer by looking at the small previews that appear with the search engine results, but it can scan whole pages if necessary. Words of the right length that crop up most often in the results are taken to be possible answers. A list of possible solutions to the clue is produced by combining the suggestions generated by each technique. When possible answers have been found for each clue the software uses trial and error to find the combination of interlocking answers that best fills the grid.

All in all, WebCrow did okay, finishing first and second. Detailed results are posted at the WebCrow web site.

And no, you won't find my name listed among the winners.

Posted by Jon Erickson at 08:55 AM  Permalink