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’s a prize to be won if you are
MATTHEW GINSBERG can’t help feeling a little sorry for his crossword-solving computer program. He points to a recent New York Times clue: “Food or drink dispensers”. The answer? “MachinesV”. “How is a computer meant to figure that out?” Ginsberg asks. “It’s not fair.”
Advertisement
If you’re stuck: it’s “v 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’s all the more surprising, then, that Dr Fill, Ginsberg’s baby, is now better at New York Times crosswords than all but the top human solvers. Remember the hullaballoo when IBM’s 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 “straight” or “quick” 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. “You can’t write a program to get into somebody’s mind,” says William Tunstall-Pedoe. He built , a “knowledge engine” that aims to give answers to naturally posed questions, which was recently bought by Amazon. He has also written a crossword clue solver. “It 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’s crossword solvers, available online at : “Grand 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 “Creole” included the phrases “I am not sure about the ‘grand’ bit”, and “‘horseback’ becomes ‘ole'”, the latter qualified apologetically with “I can’t justify this – if you can you should give a lot more credence to this answer”. At least that’s 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’t your bag: a native of Belgrade is a Serb, which in the clue “goes around” (surrounds) the word up, which can be vaguely associated with being on horseback, forming a word in sum total with the meaning “grand”: superb.)
The ideal is for human and machine to work together, apparently. “In combination with a person, it’s hugely helpful,” Tunstall-Pedoe says. Perhaps that person shouldn’t be me. The more clues I ask the solver to solve, the more confusing things become. The favourite answers don’t 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’s 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’t 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’t until 2011 that Dr Fill debuted in the , a highlight of the US puzzling calendar. “It was very good almost immediately, and has been inching up the scales ever since,” Ginsberg says.
Dr Fill’s 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’t, it starts again and tries a different combination (). It’s 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. “Dr 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. “It 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. “There 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, “This is the room where the President holds his balls and dances”, he says. (Back when he was a college professor, Ginsberg wasn’t allowed to use this example in the AI textbook he was writing; he had to settle for Groucho Marx’s “Time 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’ll 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’s 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, “It’s the first decent puzzle made almost entirely by a computer.”
“It 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: “‘This is our policy’: New Scientist after 3000 issues“
Answers and competition
Full answers to the crossword will appear in our 17 January 2015 issue. A set of New Scientist books will go to the first correct entry drawn out of the hat on 6 January. Details of how to enter and full terms and conditions are at (free registration necessary)
This article appeared in print under the headline “Silicon word whizz was Oprah guru, by the sound of it (2,4)”
