Matt Ginsberg has built Dr. Fill, a computer program that will be participating in the 35th annual American Crossword Puzzle Tournament (of Wordplay fame), held in Brooklyn March 16-18. Ginsberg runs two software companies, On Time Systems and Green Driver, but is a longtime puzzle fan and a cruciverbalist, or crossword-constructor, himself. Ginsberg says that trial runs of the program place it among the world’s best crossword solvers, and he hopes the program will perform as well as the top few contestants this year. “Because of the complexity of the English language, the breadth of subjects covered in puzzles, and the playfulness of crossword themes,” Will Shortz, the Times’s puzzle guru, has said, “I’ve always thought that a human brain would be better than a computer at solving crosswords. Maybe I’ll be proved wrong. I’m excited to see what Dr. Fill can do.”
FAST COMPANY: So you’ve gone and activated Skynet.
MATT GINSBERG: Not quite. First of all, it’s an incredibly vertical thing. Yes, it’s good at crossword puzzles, but it’s hopeless at everything else. Also it solves them in a massively inhuman way. It basically has no idea what it’s doing.
So what’s Dr. Fill’s technique? Brute force?
It’s applying brute force techniques and crunching huge numbers of possibilities. It looks at clues, and for each clue it tries to figure out an answer. But the goal is not to get the answer to the top of the list. If Dr. Fill can get the right answer anywhere in the top 100, I’m happy. The top 100 is good enough that the constraints provided by crossing words turn out to be enough.
Watson, IBM’s “Jeopardy!” whiz, had memorable gaffes, calling Toronto an American city. What are some funny things Dr. Fill gets wrong?
Its first choice is always something stupid and unrelated. It thinks it’s related, because it’s got some clue that involves “bad day for Caesar.” The answer is “ides.” But it sees “Caesar,” and it sees four letters, so it puts in “vidi,” from “Vini, vidi, vici.” When it tries to work out the rest of the puzzle, “vini,” “vidi,” and “vici” work out terribly, and eventually it comes along and puts “ides” in. It’s the crossing words that saves it.
So Dr. Fill doesn’t know the first thing about puns.
It knows the first thing. That’s exactly what it knows. What I do, it fills in the whole puzzle, and then I go back and say, does it look like there’s a pun in there? Some kinds of puns appear often in puzzles, for example, normal phrases where you add an “r” somewhere, and it’s funny. Dr. Fill will get some of these right just from crossing words. It’ll fill in the whole puzzle, then notice, “Oh, in three places in this puzzle, there’s a normal phrase that someone adds an ‘r’ to.” It rips out the whole puzzle and starts over. It thinks, before it starts over, “I’ll take all the phrases in my dictionary, add an ‘r’, and refill the puzzle.” And that’s exactly how it does puns. It knows exactly one thing about puns: this is how they are created. It has no idea why they’re funny.
You’re a cruciverbalist, or puzzle-maker, yourself, having published some 30 puzzles in the Times.
But I am the world’s worst crossword solver. When you submit a puzzle to the Times, Will gets it, takes three months, and says yes or no. A year later, the puzzle comes out, and I can’t do them, that’s how bad I am. But the reason I love puzzles is because when I send it to Will, I’m done. Nothing else in my life has that spirit of closure. I have kids, and the companies I run…
Is Dr. Fill in any way a business proposition?
Yes, sort of, in two separate ways. What the businesses I run do, is we solve optimization problems. Dr. Fill is solving an optimization problem. I had to develop new algorithms, and those get added to the toolkits available to On Time Systems. The second way is, I run a couple of high-tech companies, and it’s important I keep coding or my brain will turn to mush. So in part it’s because the algorithms become part of our toolkit, and in part it’s so my brain stays oiled. And in part it’s because it makes me cheerful.
Is this final week running up to the competition going to be like a training montage from a “Rocky” movie? Do you have a lot of work left to do?
The answer, sadly, is yes. I found out the other night that some of the testing I’d done wasn’t right, and I’ve got a bunch of stuff inside the program at the moment that slows it down to no appreciable advantage. So I’ll be spending the next week frantically trying to cull the stuff I did that worked, from the stuff I did that didn’t work. I’ll be trying to strip a lot of code without breaking everything else. So no sleep for me.