杏吧原创

Down. 1: Silicon word whizz was Oprah guru, by the sound of it

Silicon-chip logic is remorseless, but it can think laterally enough to flummox human minds. Up for the challenge? There鈥檚 a prize to be won if you are

MATTHEW GINSBERG can鈥檛 help feeling a little sorry for his crossword-solving computer program. He points to a recent New York Times clue: 鈥淔ood or drink dispensers鈥�. The answer? 鈥淢achinesV鈥�. 鈥淗ow is a computer meant to figure that out?鈥� Ginsberg asks. 鈥淚t鈥檚 not fair.鈥�

If you鈥檙e stuck: it鈥檚 鈥渧 ending machines鈥�, or vending machines. Plenty of people struggle with this more whimsical sort of crossword clue, which can combine general knowledge, word play and cultural references with a generous dose of lateral thinking. A silicon processor, armed only with remorseless logic, seems even less well equipped. It鈥檚 all the more surprising, then, that Dr Fill, Ginsberg鈥檚 baby, is now better at New York Times crosswords than all but the top human solvers. Remember the hullaballoo when IBM鈥檚 beat the reigning chess world champion, Garry Kasparov, in 1997? Looks like the crossword could be the new chessboard.

Computers began to hook themselves up to the crossword grid a while back. Fitting words into such a grid is a classic example of a constraint satisfaction problem, something that computers excel at. The constraints are that the words must exist (generally, which is why that New York Times clue is a bit of a cheat if you ask me) and no two letters in the grid should clash. Give a computer access to a large enough dictionary, and it can crunch through the possibilities far faster than a human to find an optimal solution; indeed, many crossword compilers now use silicon brains to generate an answer grid to which they can write the clues. Give the computer a thesaurus too and it will stand a good chance of solving 鈥渟traight鈥� or 鈥渜uick鈥� crosswords that consist purely of redefinitions of the words in the grid.

Solving crosswords of the more cryptic type is a different story, however. The clues here have both a surface reading and another, more devious reading, making cracking them a battle of wits with whoever created it. That is a problem for any artificial intelligence. 鈥淵ou can鈥檛 write a program to get into somebody鈥檚 mind,鈥� says William Tunstall-Pedoe. He built , a 鈥渒nowledge engine鈥� that aims to give answers to naturally posed questions, which was recently bought by Amazon. He has also written a crossword clue solver. 鈥淚t makes hypotheses about what bits of the clues can mean, and then it tries to get those hypotheses to produce an answer that fits.鈥�

British-style crossword clues are often particularly fiendish, with the cryptic element set at maximum, so I fed an example from the London Times to one of Tunstall-Pedoe鈥檚 crossword solvers, available online at : 鈥淕rand native of Belgrade going about on horseback (6)鈥�. I got back five words assessed as having a more than 1 per cent chance of fitting the clue: Creole (32%), hoggin (26%), direct (15%), honest (15%) and superb (11%).

It gave me its working out. The explanation for favouring 鈥淐reole鈥� included the phrases 鈥淚 am not sure about the 鈥榞rand鈥� bit鈥�, and 鈥溾�榟orseback鈥� becomes 鈥榦le'鈥�, the latter qualified apologetically with 鈥淚 can鈥檛 justify this 鈥� if you can you should give a lot more credence to this answer鈥�. At least that鈥檚 honest, and gave me some candidate words, one of which was right: more than the organic intelligence inside my skull supplied without prompting. (If this really isn鈥檛 your bag: a native of Belgrade is a Serb, which in the clue 鈥済oes around鈥� (surrounds) the word up, which can be vaguely associated with being on horseback, forming a word in sum total with the meaning 鈥済rand鈥�: superb.)

The ideal is for human and machine to work together, apparently. 鈥淚n combination with a person, it鈥檚 hugely helpful,鈥� Tunstall-Pedoe says. Perhaps that person shouldn鈥檛 be me. The more clues I ask the solver to solve, the more confusing things become. The favourite answers don鈥檛 mesh together. Soon the back page of my copy of The Times is a mess.

Compared with this piecemeal approach, Dr Fill represents artificial intelligence鈥檚 all-out assault on the crossword grid. Back in 1976, Ginsberg, whose speciality is optimisation mathematics, wrote what he thinks was the first software to construct crosswords. He didn鈥檛 start thinking seriously about it until a decade or so later, when a friend had a couple of puzzles accepted for publication in The New York Times.

These things take time: it wasn鈥檛 until 2011 that Dr Fill debuted in the , a highlight of the US puzzling calendar. 鈥淚t was very good almost immediately, and has been inching up the scales ever since,鈥� Ginsberg says.

Dr Fill鈥檚 secret is knowledge: it has a huge database of 6 million crossword clues and answers. It searches these entries for correlations with the clues in a given puzzle, then tries them all out in the grid to see if they fit together. If they don鈥檛, it starts again and tries a different combination (). It鈥檚 a bit like Netflix trying to predict what movies you are going to like, Ginsberg says: you just elicit patterns from information without really trying to understand it. 鈥淒r Fill is just one more application of big data,鈥� he says.

It seems rather prosaic, and the brute force approach has its limitations.Although it is among the top 100 solvers based on speed and accuracy, Dr Fill has probably got as good as it can, says Ginsberg. Anything more would need a more subtle approach to AI.

Time, then, to set Dr Fill a new challenge: writing a cryptic crossword from scratch. This is a really tough nut to crack. Creating a phrase that reads well on the surface, but also encodes an answer that is almost unrelated to that surface meaning, is incredibly difficult. 鈥淚t requires a deep understanding of language and the real world to do that well,鈥� says Tunstall-Pedoe. Indeed, he reckons the problem provides a good measure of our AI capabilities. 鈥淭here could be a Turing test for cryptic clues set by a computer: can you distinguish between a human-set one and a computer-set one?鈥�

Ginsberg agrees. Writing such clues requires the kind of contextual understanding that lets us know what people mean when they say, 鈥淭his is the room where the President holds his balls and dances鈥�, he says. (Back when he was a college professor, Ginsberg wasn鈥檛 allowed to use this example in the AI textbook he was writing; he had to settle for Groucho Marx鈥檚 鈥淭ime flies like an arrow, fruit flies like a banana鈥�.)

No wonder both Tunstall-Pedoe and Ginsberg declined our invitation to unleash their AIs on creating a British-style cryptic crossword 鈥� that might be something for our centenary issue in 40 or so years鈥� time. But Ginsberg did agree to program Dr Fill to generate a New York Times-style crossword. You鈥檒l find it below (click on the crossword for a bigger version if you want to print it out). The clues are not the twisted type, but they do sometimes require a bit of lateral thinking.

If you find it easy to solve, that鈥檚 instructive: it took several iterations to set and Dr Fill had to be given new instructions once when two very similar words popped up in the grid. Still, says Ginsberg, 鈥淚t鈥檚 the first decent puzzle made almost entirely by a computer.鈥�

鈥淚t is the first decent puzzle made almost entirely by computer鈥�

So sit back and pit your intelligence against the artificial version. May the best player win!

Leader: 鈥�鈥楾his is our policy鈥�: New 杏吧原创 after 3000 issues鈥�

This article appeared in print under the headline 鈥淪ilicon word whizz was Oprah guru, by the sound of it (2,4)鈥�