Artificial intelligence: A match for angry words

Artificial intelligence: A match for angry words

CHESSPLAYING computers are old hat. A superthinker that can best the champions of rapid-response trivia on "Jeopardy"? Last year's news — February of last year, to be precise. Matt Ginsberg, an entrepreneur by day, has set his sights on unconquered territory: crossword puzzles.

The Oxford-trained Dr Ginsberg, a former artificial-intelligence researcher, has created Dr Fill, a system that analyses both clues and answers to solve puzzles with what he says is now a fair degree of accomplishment. Dr Ginsberg previously created the first bridge-playing program that competed at a master level. He is a crossword puzzle constructor, regularly selling his work to Will Shortz, the New York Times editor, who also directs the American Crossword Puzzle Tournament, at which Dr Fill will debut on March 16th.

Dr Ginsberg gave himself an additional constraint in building his solver: that it fit on a laptop. That requires his software to be cleverer than Watson, which had many terabytes of data to sift through, but also makes it portable for shows. Dr Ginsberg says this is possible because crossword puzzle clues have correct answers that can be tested against the grid.

His software contains all clues and answers for crossword puzzles created since 1990, and can break down unknown clues into long lists of potential answers that fit the required word or phrase length. Dr Fill fills in squares with its most confident pick, and then works through potential crosses. The trick in making this large problem smaller is the crossed words, he says, as it reduces the universe of possibilities in comparison to open-ended questions. Many short and unusually spelled words are rarely used in speech and writing, but commonplace in crossword puzzles. "Jai ____" always has the answer "alai", Dr Ginsberg notes. (For those less adept at solving crosswords, jai alai is a variety of Basque pelota, a sport where a ball is slung against a wall, in this case using a basket-like contraption attached to a player's hand.)

Dr Ginsberg says Dr Fill is another example of the modern trend in artificial intelligence, which is not to simulate people's pattern-matching ability, but to make use of exceedingly rapid serial tasks. He says that his program makes no attempt to understand words and clues. Rather, it uses the power in its particular domain to search vastly deeper and juggle more possibilities than any human being can. (While Dr Fill is all for fun, Dr Ginsberg's firm, On Time Systems, finds approximate but optimised answers to so-called "NP Hard" mathematical routing problems to reduce fuel consumption for US Air Force non-combat flights, among other things.)

At the upcoming tournament in New York, Dr Fill will be a non-ranked participant. Dr Ginsberg says he will receive timed puzzles along with true competitors, and punch them into his system. When Dr Fill is done, it will print out the answer, which judges will score. Dr Ginsberg says the crossword puzzle community has welcomed his efforts with open arms, and that Mr Shortz has been particularly supportive.

Dr Ginsberg, with the permission of the event handlers, will hand out "you beat Dr Fill" buttons to the competitors who rank higher than the algorithm's would have had it competed in earnest. Based on testing against previous year's puzzle Dr Fill might place 20th.

The competition's organisers need not worry that Dr Ginsberg, as a professional constructor, can give his software an unfair edge. He confesses that he is a terrible solver, and, by the time his own puzzles are published, often incapable of completing them.