Hello and welcome to the NVIDIA AI Podcast.
I'm your host, Noah Kravitz. Crossword puzzles have long been a staple of newspapers and websites, but in Until recently, they hadn't attracted the kind of attention from the AI community that other games and puzzles like Go and Chess have garnered.
Then came Dr. Phil. No, not the daytime TV host, but a crossword puzzle playing AI that scored higher than any humans did at the American Crossword Puzzle Tournament earlier this year.
Dr. Phil is the creation of today's guest, Matt Ginsburg, a serial entrepreneur, pioneering AI researcher, and former research professor who's been doing crosswords for nearly half a century. and more recently partnered with UC Berkeley's Natural Language Processing team to give Dr. Phil the edge it needed.
Matt's here to tell us all about Dr. Phil and what it's like to build a machine that solves crossword puzzles.
So Matt, thank you so much for taking the time to join the NVIDIA AI podcast.
My pleasure. Thank you for allowing me to be here.
So let's start with this. You hold a PhD in mathematics from the University of Oxford.
You have 100 technical papers, 14 patents, and multiple books to your name.
But as I understand it, about a decade or so you entered a crossword tournament, didn't win, and then became a bit obsessed.
Can you tell us a little bit about that experience, what happened and how it started the road that's led to Dr. Phil?
So I didn't enter. I knew better than to enter.
I started constructing puzzles for the New York Times.
I actually had I had a tough period at work and I took a month off and during the month, I didn't know what to do.
So I started making crosswords. I love making them.
And I, I enjoyed it, the solvers seemed to like it, but I can't do them at all.
I'm just terrible. The information is not stored in my head that way.
One of the things that I tell people, when you send a puzzle to the Times, It takes about a year for it to actually come out by the time they review it and they have a queue and so forth and so on.
When my puzzles come out in the times, I can't do it.
So that's how... terrible I am at solving crossroads.
So I went to the tournament just to meet all the other constructors and all the solvers and just to be part of this community.
And I was surrounded by all these people who were just so much better at solving crosswords than I would ever be.
And I just, you know, I thought I know what to do about this.
I'll write a program and I will... I will still be terrible at solving crosswords, but I will show all these guys that perhaps indirectly, can be as good at it as they are or close.
And that started the work that eventually turned into Dr. Phil.
So what was it like in the early stages?
Or I say early, and we're going to get to this, but it sounds like in the past year, it was kind of this partnership that led to this big advance.
I mean, the work with Berkeley absolutely put Dr. Phil over the top.
Dr. Phil was reasonably good, reasonably quickly.
So the very first year, it was like in the top 15%, 20% of entries.
And these are the people who are willing to travel across the country to go to a CrossFit tournament, so they're pretty good at it.
And the basic techniques that I used haven't actually changed that much.
So, you know, it's a matter of saying, okay, here's a clue.
I mean, my level clue, things like scoopy blank, three letters.
And it says, oh, well, the answer could be do or it could be this or it could be that.
And then you look at the crossing words and you try and make it all work so that The words you're putting in don't mess up all the crossing words.
And then there are a variety of things you can try.
But the first time it entered, most of the basic technology was there.
And I thought it was going to do better than it did because I had screwed up the testing and I was disappointed coming in wherever I was, 120th or something.
And then I started looking at exactly what happened and how themes work.
I started doing the hard work. So when you write a game planning program, and this is not the first one I've written, Getting it sort of up and running is Fun and fast.
And then you have the grind of figuring out when it makes a mistake, why did it do that wrong?
And how do I fix it? And I started working on the grinding part.
And over the last 10 years, Dr. Phil has slowly gotten better.
And I've made a little bit of progress in its ability to figure out what's the right answer to any particular clue, but not a whole lot.
And then the Berkeley guys showed up. And I always was thinking, if only I had a natural language group to help me because this is, this is right up their alley.
And the Berkeley guys called me about a month before the tournament this year.
And it evidenced, you know, and said they were interested in working together.
And I was like, whoa, well, we better get on it because the tournament's a month from now.
It turned out that we were very well positioned to fit our code bases together relatively easily. worked pretty hard for a couple of weeks and then we had something that worked.
I had crawled my way up to 10, 12, 15, something in that range.
And this year, instead of something like that, we were first.
So before getting into what NLP and the Berkeley groups, what their work was able to do for you or for Dr. Phil, go back a second.
What are some of the differences between other game playing programs that you had worked on previously or just in general? and the specifics of creating a crossword playing program.
I think the hardest thing about crosswords is there are sort of no rules.
I mean, there are rules, right? You've got squares and letters and-
But crossword constructors are always trying to do innovative things.
So one of the things I did in a crossword I made, it was called a takeaway crossword.
And the clue might be German steel city, except the T's would be replaced by asterisks.
And that's a hint. that you're going to take the Ts out of the answer.
So a German steel city is Stuttgart. When you take the Ts out, you get sugar, which is still a word.
Right. So in this crossword, every single word had this property.
There's no way Dr. Phil can do this because it's just too strange.
But even this sort of normal Sunday New York Times puzzles You might have a crossword that's all about rabbits.
So an answer might be not Bonnie and Clyde, but Bunny and Clyde.
Right, right. You might have hair today gone tomorrow instead of here today gone tomorrow.
And, Those kinds of things where there at some level aren't any rules are what make crosswords so hard.
If you're playing chess, the rules are the rules.
If you're playing poker, the rules are the rules.
And people have started, so initially, the game playing programs worked on what are called perfect information games, where you have the same information available to every player.
So chess, everybody knows where the pieces are.
There's no mistaking that. And then people gradually moved to imperfect information games where different players have different knowledge of the situation.
So I worked on bridge. People have worked on poker.
But again, the rules are very clear. Nobody can argue at the end of a bridge hand Whether you took six tricks or seven, you just look at it and whoever want, you know, you took what you took in a poker hand.
You've got three aces or you don't, and nobody's going to say, well, maybe no, it's not like that.
And then crosswords are this next sort of level of uncertainty. where you don't know whether, Dr. Phil, you can give it the right answer.
And sometimes it'll say, nah, I like my answer better.
Because it really, it's not clear. There are no rules so specific that you can say, oh yeah, that's right.
You know, I think I generally tapped out Tuesday, maybe on a good week, the Wednesday edition of the Times crossword puzzle that.
I haven't done them in a while, but they still get progressively harder as the week goes on.
And are they always thematic? So the way the times works is Monday through Thursday are themed.
Sunday is Thursday difficulty but larger, and it's almost always themed.
And Friday and Saturday are unthemed. Okay.
And Dr. Phil does way better on unthemed puzzles than themed puzzles because the themes are what makes it nasty.
Right, right. So I was going to ask, how do you, when you're designing a piece of software to tackle this, The theme isn't stated.
The theme has to sort of be deduced by the solver.
Correct. And so does Dr. Phil specifically try to deduce the theme or...
It does. And it's not, I mean, it doesn't do anything overwhelmingly clever.
So what it'll do is it'll just fill in the puzzle and has no idea.
And then it looks at it. and says, wow, there's a long answer that's not in my dictionary, but if you add an A, to a word that is in my dictionary, that gets that long answer.
And here's another long answer that if I take the A out, it's back in the dictionary.
It says, I think that's the theme. The theme is add an A. That's a fairly common crossword theme.
So it'll say, okay, And it's so fast. It's I'm just going to solve the puzzle again, but this time I'm going to take every word in my dictionary.
I'm going to add an a and every possible location.
I'm going to add all those new words to my dictionary and I'm going to do it over.
And it goes through and it'll find lots more places it can add words with As.
And that's how it does the theme. There are lots of themes that are relatively straightforward, and that's how it does them.
Then there are lots of themes that are impossible, like this takeaway theme.
There was a guy, a while ago who made a puzzle and one of the clues was I think Apollo 11 and 13.
180 degrees. And the answer is like something unpronounceable.
It turns out if you write down moon missions and rotate it 180 degrees, they're all still left.
M's turn into W, S's stay the same, N stay the same, I stay the same.
And this puzzle had all of you, it had, you know, sums were 90 degrees.
So onion rings, the ends turn into Zs. And how do you get a computer to do this?
It doesn't know that letters have shapes.
Letters are just bits. to it. There's some things that are just so innovative, you can't do it.
You have to hope that you get it from the crossing words.
The theme stuff is what makes it so hard.
And I don't, you know, I'm looking forward to the Crossroad tournament next year because I know we're going to be working hard to make the program better.
I think the constructors got a little sloppy this year.
And the themes were things that Dr. Phil was able to deal with.
And I have a feeling they're going to be a little bit more careful, let's say, next year.
We'll see whether they've made progress or we have.
But it'll be fun because... as they do these funky things, the puzzles are more fun for the human solvers.
So it's all good. Things like the ability to interpret clues and, and you know, fourth highest mountain in the world, whatever that is.
But if that were in a puzzle, That, at some level, is what the Berkeley guys brought this time.
So I already have this huge database that I maintained for constructing purposes, of every crossword clue that's ever been used and what the answer was.
So if you use a clue that has appeared before...
Every clue that's ever been used in the New York Times?
It's like, you know, it's some number of millions of clues.
I mean, of course that exists, but it's just kind of amazing to hear somebody say it.
So you have to get all the puzzles, and there are people who collect all the puzzles.
And then you just turn through them. So if Dr. Phil sees a clue that it's seen before or sees a clue that is like a clue it's seen before, it'll get it.
And it's not really using natural language understanding per se.
So if it has never seen fourth highest peak in the world and that shows up, it doesn't know what to do.
But the Berkeley guys are actually bringing real knowledge, real natural language stuff And I've been saying for a long time, I wish I had a natural language group helping me because it makes so much sense.
Right. So I'd wanted to come back to that.
So let's dig into those examples. roughly 10 years, I think, eight years, something like that, where you said you were kind of chipping away and And Dr. Phil was getting a little bit better each competition, each year, whatever the marker was.
What were – if you can kind of categorize kind of what types of progress you're able to make and maybe what types of – problems you couldn't solve, and then kind of bring us to this year when, as I understand it, you got an email out of nowhere from Dan Klein and his team.
I did. I got an email from one of his graduate students.
I think over the past decade, I've just been soldiering away.
I would explain more theme types. So if you have a theme type, you have to say, consider taking away letters from the fill you have and see if it's in your dictionary.
And I would add, well, sometimes they don't add the letter A, they add the sound A.
So I would get a pronunciation database and then I would convert it all to pronunciation and say, okay, if I take away the sound A, do I get the sound that appears already in my database.
So it was just grinding through theme types.
It was finding more sources of words, looking at mistakes it had made, and fixing them.
So one of the things I noticed was there was some name that it had never heard of.
And the name appears in Wikipedia, but the Wikipedia title is the whole name.
So it's got this weird last name, but on Wikipedia, you find first name, last name.
And I said, okay. If there's a Wikipedia title where the article appears to be reasonably popular and the title has a space in it, then each part of the title is probably a legit word.
Just stuff like that. It really was grinding it out. and slight improvements to the search algorithms where I noticed that So when it gets something wrong, it doesn't really know, but it has an inkling because the words are scoring badly.
And I said, okay. I wrote some code so that if it's a piece of the puzzle where the words is going badly, try harder there, give it some more computational resources.
So again, just small changes that were just very gradually improving it.
And I knew I had this gap. Like I said, I knew I had this gap on natural language, And I had spoken, I think I had spoken only to one of the big tech companies at this point saying, hey, why don't we just finish this together? you guys have a natural language group.
Let's just put this together and, and, win the crossword tournament and get the associated publicity.
Except it'll be you, because I don't have any need for publicity.
And they didn't do it, and they passed. And then, like...
Like you said, then I heard from Dan Klein's group, a guy named Eric Wallace, and we started working together and it all went.
It turns out that what I was doing with all of my simple look at old clues, statistics, and so forth, is I was...
If you give me a clue, I was saying, okay, it could be any of these 10,000 possible answers, and here's a rating. where for each of these possible, every word of length five, every five-letter word, here is how likely I think it is to be the answer for this particular clue.
If you build a machine learning system, you produce the same information.
So they would take a clue, and they would produce this giant list of five-letter words and how likely they thought each one was.
At a high level, all I really did was I took my ranking out and I put their ranking in and the program got better.
It was a little bit more subtle than that because it turns out that The right thing to do is to take 90 percent of their ranking and 10 percent of mine if theirs was better.
And if Dr. Phil got really excited about a particular word, you should use it because it had some It had good reason.
So basically, I used whoever thought the world was more exciting, I used that value.
And you said that you had a matter of weeks, less than a month, from when you started working with the Cal Group to when the— the ACPT was this past year.
But it sounds like it was a pretty, you know, almost plug and play kind of thing as it turned out.
Well... I'm overstating, but it was pretty smooth.
Yeah, it wasn't quite that easy. So they reached out to me a month before the tournament, and I said...
Hey, let's go. And then two weeks went by.
And the hardest part was, you know, they have one piece of code and I have another piece of code. and the two pieces of code weren't designed to talk to each other.
So I had to at some point, the way we ended up building it is Dr. Phil would say, okay, and it would just write to disk.
And their program would be sitting there waiting for this disk file to show up.
And as soon as the file showed up with all the clues, it would analyze them and then put the answers in a different file.
So you have this incredibly primitive way for, this is not our program. to communicate using disk file.
But if you only have two weeks to get it working, it's not a bad way.
What's next? I mean, you mentioned wanting to work on it to get it better and kind of anticipating... some curve balls, some more devilish, you know, puzzle constructs.
Are you still working with the Cal team?
Yeah. You know, we want to make Dr. Phil better.
I am not a fan of we do this, and then we say, OK, next up, cancer.
No. Dr. Phil is a crossword solving program.
It's not going to be more than a crossword solving program.
We're learning. As scientists, we're learning about techniques that work and techniques that don't work for search and for natural language processing.
And because of the success of the program, we've had the opportunity to talk about it.
And that matters. So we can tell people, you know, computers, yet another game has fallen to computer technology.
Don't feel threatened. It's just another game.
One of the things that I think is incredibly important that we talk about is If you remember when I described what Dr. Phil did, it sees a clue. and it makes a list of every five letter word and how likely it is.
Not just the best ones, all of them. And then it combines those lists to solve the puzzle That's not how we solve puzzles at all.
We see the clue and we say, well, it's probably this or this, and that's about it.
I can't think of another answer. That reflects... a fundamental difference in how machines and people solve problems.
We look at very small spaces of possibilities.
Two words. If we're playing chess, a chess grandmaster will look at tens of positions.
Machines are look at tens of thousands of words.
A chess player will look at billions of positions.
It is not an accident that you have this pervasive difference in how we solve problems.
And I think not only is it an accident, but it's incredibly important because Games are games.
When it comes time to figure out the most efficient flight plan, to ferry relief supplies from New York to Haiti, I want a computer to do that.
It'll look at more options. When it comes time to decide, Do I want to bail the people in Haiti out or not?
That's a human decision. We should make it.
So what's going to happen is we're going to be able to solve problems together that we couldn't solve separately.
It's all good news. I don't think we're not looking at like the Terminator here where machines decide they want to solve our problems and we are just sad.
We're looking at a world where our abilities as people get extended because problems that we find difficult, we're no good at these giant search problems.
Problems that we find hard, all of a sudden we can solve.
And armed with the ability to solve them, we can then do things that we couldn't do before.
So I think it's all very optimistic and that's what's next.
So when you're doing puzzles yourself, or even when you're doing other things in your life, do you ever find yourself thinking like, well, what would Dr. Phil do here?
No. Your decade-plus relationship with Dr. Phil, it's a crossword solver.
It's not more than that. Yes. So I've learned a lot.
I've learned about search. I've learned all sorts of stuff that I can use elsewhere, but I've learned about computation.
When I'm sitting down with a crossword, which never happens because I'm so awful at them, but when I look over someone's shoulder, I'm not thinking about computation.
I'm not thinking, oh, I wish I could solve this.
It's like, you know, and it's, and then the same thing happens in all these other areas.
So when you watch a computer play chess, or when you play chess, you don't think, I wish I could solve this like a computer.
You're trying to say, what's the What's the right move?
You're using human techniques and you always will be.
I think that you're running a foot race.
You're running a quarter mile. Nobody running that race thinks, I wish I had a horse.
They just don't, right? They're running.
They're trying to get the most they can out of their abilities.
And if there's another entity, whether it's a horse or a sports car that could run faster than them, That's not what you're thinking about.
You're thinking, how can I be the best runner I can be in the moment?
And that's what Dr. Phil is for me. So kind of looking ahead and without asking you to spoil anything or give away something that the puzzle constructors might use against you next year.
Are there particular challenges or particular buckets of challenges that you're focused on with Dr. Phil?
We really did just shoehorn these two things together.
One of the things that we should do is we should make the integration better and more seamless.
As we do that, Dr. Phil's going to improve across the board.
Now there's other stuff we could do. We could try and do a new type of theme and we could try and do this and try and do that.
I don't know that we're going to spend a lot of time doing that because the basic integration is so much more effective.
I mean, it's the reason that Dr. Phil all of a sudden went from where it was hanging out sort of the teens to, to winning.
And it's also, it's, it's more interesting from a scientific perspective.
Adding, I've spent hundreds of hours adding individual theme types to Dr. Phil.
It's a huge amount of work. Did I learn anything about science?
I didn't. I learned that coding is hard and you make mistakes.
You make progress. It's more fun to learn things you can take to other places.
Now, it's not the case when I sit down and do a crossword. that I think about Dr. Phil.
But it is the case when I look at other problems that I can take some of the stuff I learned from Dr. Phil.
So Dr. Phil's fundamental search algorithm is take the next word you should fill in, which is an important choice, should be the word where the difference between the first and second choices in terms of sort of damage to the rest of the puzzle is as big as possible.
Because the size of that difference is how confident you are that this is the right word.
So even if this word isn't that good, If the second word is way worse, put this word in.
Before I did the work on Dr. Phil, people used to say, just fill in the word that looks the best first.
But then you end up putting all this junk in.
Eon, nice word. Maybe unrelated to the clue, but an E and O and an N are good letters.
They're not going to mess up the crossing word.
So you put in all these random three-letter words.
It doesn't work. I had this idea of measuring the order by this notion of confidence.
I have used that elsewhere. That's been good.
That's been valuable. I love having insights like that.
That's what moves science forward. And that will have greater utility than just in crosswords.
There will be other computer problems where something like that turns out to be valuable.
So this has been so much fun. The Berkeley guys have been great.
The Crossword world has been awesome. Everybody's been...
They act like I'm the bad guy, but they've been ridiculously welcoming.
And it's a complicated decision. Will Shorts, who runs the tournament-
Do you let a computer participate or not?
And he has handled it incredibly well. I have felt welcome.
I think it's added value to all the human competitors.
And it's just been, you know, it's been a tremendous success from that perspective.
And it's the people who get the credit, you know, like the solvers and will and the berkeley guys everybody's been such a joy to work with that's great it's been a blast excellent yeah Every year I give a little talk about how Dr. Phil did each of the puzzles at the tournament.
I couldn't do it this year, obviously. I always complain that everybody hates me.
It is the case. Will, as the tournament goes on, he'll say, Dr. Phil solved that puzzle in two minutes.
In 37 seconds with no mistakes, and the whole crowd groans.
And if it makes mistakes, everybody applauds.
So I complain that nobody's on my side, but Everybody, it's all tongue in cheek.
Everybody knows that everybody's Friends.
Excellent. Good. Fun. I look forward to it every year.
Excellent. Well, again, for folks who want to find out more, It's a great article on the NVIDIA blog, a little plug there, that our producer Brian wrote with an interview with you, Matt.
And then also another article Brian sent me to read before this on slate.com, which is also great.
You should go check it out. You can just search for Dr. Phil, F-I-L-L, should be Claire.com.
And Matt, what can I say except that we're all going to have our eyes peeled for the 2022 version of the tournament.
And I, for one, will be applauding, you know, faster times and fewer mistakes on your end.
The humans can go take care of themselves.
Thanks for coming on and best of luck with your continued work.
My pleasure. Thank you. Thank you.
