Crossword-solving system strikes a blow for AI

 

Gallery

By Simon Aughton

Posted on 1 Sep 2006 at 11:09

A crossword-solving computer program has struck another blow for artificial intelligence by beating all 25 humans in completing two English-language puzzles and one Italian and English bilingual puzzle in a competition in Italy.

Two different versions of the WebCrow software competed - one running from its 'home' machine at the University of Siena and a streamlined version installed on a lesser computer at the competition venue - and they took first and second place in the competition to finish the three non-cryptic puzzles in the quickest time.

'It exceeded our expectations because there were around 15 Americans in the competition,' Marco Ernandes, who created WebCrow along with Giovanni Angelini and Marco Gori told New Scientist said. 'Now we'd like to test it against more people with English as their first language.'

The program did less well when solving two Italian puzzles, coming 21st and 15th, which Ernandes attributed to the number of puns and political clues. Like cryptic clues, these require specific human knowledge and reasoning beyond WebCrow's ability he explained.

WebCrow draws upon a database that it searches using keywords in the clue. Once it has found possible answers it employs trial-and-error to find the combination of answers to all the clues that fit the grid.

Crosswords are just one test of the ability of computers to match human reasoning. In 1997 an IBM chess program, Deep Blue, caused a considerable stir by beating the then world champion Garry Kasparov, considered by some to be the greatest chess player ever. But since then Deep Blue's successors have routinely held their own against the top human players. Scrabble is another game where artificial intelligence (AI) programmers have attempted to prove that humans are not out on their own. Brian Sheppard, developer of best-known Scrabble unscrambler, Maven, believes that the program is now unbeatable, although it has yet to be tested in competition. Similarly computers' ability to calculate all possible moves in advance makes them impossible to beat at Othello.

However the Chinese game Go remains the realm of the human mind, despite the offer of a $1 million prize by one Taiwanese businessman for the developer of the first program to beat the country's junior champion.

The sophisticated game play, where no one move can be determined to be the best in a given circumstance, means that current AI techniques are incapable of evaluating the options that even the best human players find hard to judge.

One Computer Go study estimates that at the earliest it could take 50 years to produce a program capable of playing a professional level. Producing a world champion, however, is a different matter entirely.