Computers take on crosswords

New Scientist reports: [edited]

A crossword-solving computer program has triumphed in a competition against humans. Two versions of the program, called WebCrow, finished first and second in a competition that gave bilingual entrants 90 minutes to work on five different crosswords in Italian and English.

The competition took place in Riva del Garda, Italy, as part of the European Conference on Artificial Intelligence. WebCrow took on 25 human competitors, mostly conference attendees, while more than 50 crossword enthusiasts and AI researchers competed online.

Among the five crosswords were two American-style ones from that day’s editions of the New York Times and Washington Post. A further two, in Italian, came from national newspaper La Repubblica and a local Italian title, while a puzzle with clues in both languages was made using past clues from the same sources. Full results and the puzzles set can be seen on the WebCrow website.

One version of WebCrow competed from its 'home' in the computing department at the University of Siena, Italy, while a streamlined version installed on a smaller computer competed as well, displaying its progress on a large screen in the conference hall.

The two WebCrow versions came a close first and second overall and on the American and bi-lingual puzzles, with the streamlined version taking the honours. Marco Ernandes, who created WebCrow along with Giovanni Angelini and Marco Gori told New Scientist he was particularly pleased with WebCrow's performance on the American puzzles.

"It exceeded our expectations because there were around 15 Americans in the competition," he said. "Now we'd like to test it against more people with English as their first language.”

However, the streamlined software managed only 21st place and its cousin 25th for the Italian puzzles. "The writer of one of those puzzles is well known for having lots of puns and political clues," Ernandes explains. Such clues, and those used in cryptic crosswords, need very specific human knowledge or reasoning that are beyond WebCrow's ability, he says.

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.

Tony Veale works on software that can deal with human language at University College Dublin, Ireland, and watched WebCrow in action. He told New Scientist he was impressed. "It's part of a trend to use the web as a 'shallow' source of human knowledge for artificial intelligence," he says.

The web is 'shallow' because most content cannot be understood by a computer, Veale explains, but the links between content can be used more easily to provide some information about how things are related.

"There are applications for this kind of technology in educational products," Veale adds, the techniques being developed for WebCrow could be used to automatically generate puzzles for school materials or help children with the answers.
------------