Meet Chinook, a humble software program that set out to compete with the world's greatest checkers player. Professor Jonathan Schaeffer wrote Chinook in an attempt to use machine learning to outsmart the unbeatable checkers master Marion Tinsley. But Schaeffer couldn't have imagined how his relationship with Tinsley would affect his program, and how the drama of their matches would change the world of artificial intelligence.
Featured in this episode:
- University of Alberta professor Jonathan Schaeffer, PhD
- Checkers-playing computer program Chinook
- One Jump Ahead: Computer Perfection at Checkers by Jonathan Schaeffer
- On Relate: "Rethinking AI; rethinking our jobless future"
TAMARA STANNERS: You may have heard the old legend, the story of John Henry, the steel drivin' man. It's set in the 1800s, and John Henry and his hammer, they can get through anything. And they're challenged by a man who comes along with a new-fangled steam powered drill to see who could tunnel through the mountain faster. Man or machine? For John Henry, this is more than just a challenge of his strength. This is a challenge of proving that man cannot be replaced by machines.
Today, you'll hear the story of a modern John Henry. A man with a nearly unbeatable mind. Unbeatable, until he finally meets his match in a machine. That's what's happening on Relate. I'm Tamara Stanners, and this is Relate, by Zendesk. Today's relationship pits man against machine, but it also pits science against friendship.
ANDY SHEPPARD: Yeah, it's a story that revolves around these two fascinating men.
TAMARA STANNERS: This is the fascinating man, producer Andy Sheppard.
ANDY SHEPPARD: Well, I don't know about that, but these two men are obsessed with a game that most of us played as kids. So first let me introduce you to Johnathan Schaeffer.
JONATHAN SCHAEFFER: I've been a professor for over 30 years. My research area has been artificial intelligence.
ANDY SHEPPARD: Johnathan has used games like chess, and poker to test ideas about artificial intelligence. But the game of checkers is where he made his mark.
TAMARA STANNERS: I find that so interesting. Why checkers?
ANDY SHEPPARD: Well, back in 1986, Johnathan Schaeffer had one of the best chess software programs in the world. But then, along came the Deep Blue Project, which was sponsored by IBM, and he realized he couldn't compete.
TAMARA STANNERS: Deep Blue, I remember that so clearly. That was the one that eventually beat Garry Kasparov, right?
ANDY SHEPPARD: That's the one. Although it didn't get to that point until 1997, which gives you a sense of how challenging the problem of figuring out chess was. Anyway, with chess off the board, Johnathan turned to checkers, which has all the same research opportunities as chess. Checkers has five-hundred-billion-billion possible scenarios.
TAMARA STANNERS: Okay, checkers. Five-hundred-billion scenarios?
ANDY SHEPPARD: Nope. Five-hundred-billion-billion scenarios.
JONATHAN SCHAEFFER: That's a massive computational problem. And the real challenge in this game is how do you create a smart program that can sift through hundreds of billions, and billions of possibilities, to come up with an intelligent decision?
ANDY SHEPPARD: So I mean we can talk about artificial intelligence for ages, but the real story, here, is about a very rare, very special kind of natural intelligence.
JONATHAN SCHAEFFER: Marion Tinsley was the world checker champion.
ANDY SHEPPARD: Marion Tinsley had an incredible mind for checkers. He was the world champion for many years.
JONATHAN SCHAEFFER: Over the 42 years from 1950 to 1992, he lost a total of three games. This man was more machine than man. He was amazing.
ANDY SHEPPARD: So a checkers match is made up of several games, and he only lost three games in those 42 years, but he never lost a match ever.
TAMARA STANNERS: How? How did he manage that?
JONATHAN SCHAEFFER: I don't know how he did it, but one thing was very clear. He had a phenomenal memory. He would remember things 30, or 40 years ago, and he would tell you the details. So he was a very unusual man, and he had incredible knowledge about the game. I first met him in 1990.
ANDY SHEPPARD: Johnathan Schaeffer had received permission that year, from the US Checker Federation, to have his checkers software play against a human in the US championship in Mississippi.
JONATHAN SCHAEFFER: It was almost a joke, because no computer had ever competed in these tournaments and had done well.
TAMARA STANNERS: So Schaeffer had written this program that actually calculated its own way through checkers matches?
ANDY SHEPPARD: Yeah, and I mean this is the kind of thing we take pretty much for granted nowadays. You play a checkers game on your computer, no big whoop. But in 1990, this was cutting-edge stuff. So he brought this program to a tournament in 1990. He arrives there, and he's greeted by this unassuming mathematician named Marion Tinsley.
JONATHAN SCHAEFFER: And he welcomed me with open arms, and a little bit of amusement, because he was curious to see how the computer would do. And later on in the tournament, much to his surprise, and to everybody's surprise, he was in first place, and we were in second place, and we had to play four games against each other, and we had an epic confrontation. One of the great classics in the history of the game. And at the end of it, it was four draws between us, and it was an amazing result. This was the first time in history that a computer had drawn a game, let alone a four game match, against a human world champion, in a non-exhibition game, for any game.
TAMARA STANNERS: Was Tinsley bothered by this?
ANDY SHEPPARD: Well no, actually, I think he was fascinated by it.
JONATHAN SCHAEFFER: Over time, Tinsley became a great friend, and we all sort of thought of him as our grandfather. He was very friendly, very outgoing. We grew fond of him, and it made the matches against him much more personal.
ANDY SHEPPARD: In fact, after that 1990 US championship, which Tinsley won, by the way, he offered to play some friendly games against Chinook. And he was gonna offer Johnathan Schaeffer some advice and suggestions on how to improve the program.
JONATHAN SCHAEFFER: And so, several months later, we had Tinsley fly up to Edmonton, Alberta, Canada, where we are. And we ended up playing a 14 game match. And of course, nobody imagined that we would possibly win a game against Tinsley.
Well the first nine games were all drawn. And in the tenth game, on the tenth move, and I know this very well, because this game is burned into my memory. So I'm watching the screen, and on the tenth move, the computer, at the last minute, switched to a move that it thought was better. And so I reached out, and I made that move, and as I made that move, Tinsley uncharacteristically broke etiquette and said, "You're going to regret that."
Well, a few moves later, the positions even, and a few moves later, it says Tinsley has the advantage, and a few moves later, it says that we're lost, and a few moves later, I resign.
TAMARA STANNERS: What does he mean, he resigned? Did he quit his job?
ANDY SHEPPARD: I mean I think he was depressed about this, but resigning, in checkers, is like folding in poker. You know you've lost, so you basically throw in the towel.
TAMARA STANNERS: How did Tinsley know, so far out, what was gonna happen?
ANDY SHEPPARD: Well somehow, he could see all the way to the end of the game.
JONATHAN SCHAEFFER: Game 10 haunted me. From that tenth move, when he said, "You're going to regret that." To the final position, when we lose, it takes 64 moves.
TAMARA STANNERS: 64 moves? How could he even do that? It boggles my mind.
ANDY SHEPPARD: Well, the theory is he didn't exactly see 64 moves into the future.
JONATHAN SCHAEFFER: Tinsley, through deep search, or lots of knowledge, knew, right at the beginning of that sequence, that he was going to win. And yet, my computer, in order to prove that it really was a loss, required 64 moves deep worth of analysis. And this was an epiphany for me, because there is no way I was ever going to write a computer program that was gonna search that deep. And so it made a fundamental change in my thinking about how you go about beating Tinsley, when he had this phenomenal ability to visualize so far into the future, with such accuracy.
TAMARA STANNERS: Okay, so Marion Tinsley, checkers master, is still on top, in this battle of man versus machine.
ANDY SHEPPARD: Yeah. But of course, much like the story of John Henry competing against the steam-powered machine, there's something inevitable about this story, and I think Tinsley knows it. And yet, he still wants to be part of it. Now Schaeffer and his Chinook program had earned the right to play in the world checkers championship, but a computer had never made it this far before, and there were some politics, some serious politics, around how this should be handled.
JONATHAN SCHAEFFER: The American Checker Federation, and the English Draughts Association, decided that they didn't want to have a computer playing for the human world championship. And Tinsley said, "I want to play." And the Checker Federation said no, and he said yes, and they said no, so Tinsley said, "I resign. I don't want to be world champion." And the Checker Federations were a gaud, because you have the greatest player ever, and he doesn't want to be world champion anymore. And so they hastily created a new title for him called, World Champion Emeritus, and they allowed us to play Tinsley as the World Man-Machine Championship.
TAMARA STANNERS: The World Man-Machine Championship, it sounds so ominous.
ANDY SHEPPARD: Yeah, I know. But remember, this is years before Garry Kasparov battled IBM's Deep Blue in chess, and decades before Google's Alpha-Go beat the world's best Go player. But it was every bit as important. And every bit as intense.
JONATHAN SCHAEFFER: So the match started off inauspiciously, and after seven games, we were down one to nothing, with seven draws, and quite frankly, even though the match was 40 games, people were pretty sure that the match was over, because Tinsley would get ahead, and then he would just build on the lead, and it would be over. But in the eighth game, I don't know, the program played well, Tinsley eventually made a mistake. And I'm sitting on stage. All of a sudden, the computer stopped. Everything stopped.
ANDY SHEPPARD: Schaeffer thought the computer had crashed.
JONATHAN SCHAEFFER: And so I had to excuse myself from the stage to go backstage, to look at the computer, to see what had happened. And there, I discovered that the computer had actually stopped because it had looked at every single possible scenario from the current position to the end of the game, and in every line it had found a win. And so it had stopped computing, because there was nothing left to compute.
TAMARA STANNERS: So Chinook won the game?
ANDY SHEPPARD: Yeah, but hardly anybody realized it.
JONATHAN SCHAEFFER: People were congratulating Tinsley, and I thought, "Hey! We just beat the world champion. We just beat the unbeatable Tinsley. Why aren't you congratulating us?" People in the room had not realized that Tinsley had resigned. The experts in the room had thought the game was a draw. A day or two later, in game number 14, we won again, and for the first time, now that we were up two games to one, the first time we actually imagined that we might beat Tinsley in this match.
TAMARA STANNERS: Okay. So most of the game have been tied, but Chinook has actually won two games, and Johnathan Schaeffer figures his program might actually win the match? This is pretty momentous.
ANDY SHEPPARD: Yeah, it could have been, except it didn't work out that way.
JONATHAN SCHAEFFER: Well, it turned out, the very next day was probably the darkest day in my life. It was a Saturday, and as per usual, I went down to get everything started, in anticipation of the games that day. When I went down to the room where the computer was held, I opened the door, and was blasted with heat. The computer was in a small room. The lights were supposed to be turned off, and the air conditioning was turned on, but whoever the night person was turned on all the lights in the room, and turned the air conditioning off.
ANDY SHEPPARD: So we know that excessive heat is not good for a computer. And it was so much heat that they had to delay the start of the game, because it actually made the room that they were playing in uncomfortably hot. But they finally got back to the match.
JONATHAN SCHAEFFER: And then game 18 started. On move 17 of game 18, Chinook is near the threshold of announcing a win, and I'm on stage thinking, "Oh my goodness, my computer, it's brilliant. That Tinsley guy, he was great, but he can't really compete with my baby, my computer." But as I sat there on stage, lost in thought, something very unsettling happened. The computer kept computing and computing and computing. It did not make a move, and we lost on move 17, and Tinsley won the game on forfeit. I was stunned, and upset, and of course what do you do? I went back to the computer, and I found that the computer was hung. So something had gone wrong, the computer was in a dead state.
TAMARA STANNERS: So the computer crashed.
ANDY SHEPPARD: Yeah, I mean talk about dumb luck. So Schaeffer figured that the heat caused the problem with the computer, because Chinook had behaved just fine beforehand, and during the rest of the games.
JONATHAN SCHAEFFER: In the 40 game match, we lost four games to two. But I always look back at the horror of game 18, and sitting on stage, and watching the clock tick down, helplessly knowing that we were about to forfeit that game.
TAMARA STANNERS: So Marion Tinsley remained unbeaten against Chinook.
ANDY SHEPPARD: Yeah, but Johnathan Schaeffer, after this experience, he became obsessed with trying to beat Tinsley. Two years later, they finally had a rematch, and Schaeffer came prepared.
JONATHAN SCHAEFFER: We made massive improvements to the program. We built some enormous databases that would aid the computation. We moved to a more powerful supercomputer. Thoroughly tested the program. And we went into that match knowing that we had really an awesome program. ANDY SHEPPARD: The match was played in August 1994, at the Computer History Museum, back when it was in Boston. And Chinook was playing really well. They played six games, and each game was a draw, but Tinsley was a bit unsteady, for some reason. He wasn't his usual unflappable self.
JONATHAN SCHAEFFER: Tinsley almost lost one of the games. After six games he said, "I'm not feeling well, I resign." I refused to accept that. I said, "If you're not well, we won't play, we'll postpone the games." And he agreed. I took him to the hospital, just to get tests done. But the next day he said, "I'm not feeling well, I resign. That's it. No more. We're done." And so, in August 1994, we won the world championship when Tinsley resigned the match.
TAMARA STANNERS: But that doesn't sound like the good way to win.
ANDY SHEPPARD: No, no. You want an honest to goodness win, not a forfeit.
JONATHAN SCHAEFFER: No, it was truly horrible. Later on, we discovered that he had pancreatic cancer, and eight or nine months later, he had passed away. You know, clearly he was sick at the time of the match, and I believe he knew he was sick, and I suspect that the stress of playing this match weighed on his mind, and I think that he probably knew that he was not at the top of his game, and he was in danger of losing, as had almost happened in one of those games, so even if he had continued the match, and if we had won, it wouldn't have been much of a victory. Tinsley was an amazing checker player, and to win a match against him when he was sick, and not at the top of his game, was meaningless. You could argue that winning the World Checkers Championship should have been one of the highlights of my career. It turned out to be one of the darkest events in my life, and for the next year or two, it was like something I just didn't want to talk about. It was too deeply personal, and too deeply upsetting.
TAMARA STANNERS: Oh, it's heartbreaking. All that effort, and not to mention the friendship developed.
ANDY SHEPPARD: Well the experience changed Schaeffer. I mean beating Tinsley when he was not well, it was kind of a pyrrhic victory, and it was hard for
Schaeffer, I mean he's on the receiving end of hate mail from checkers aficionados-
JONATHAN SCHAEFFER: Who said things like, "you never could have beaten Tinsley in his prime," or "Tinsley was so much better than you, it's embarrassing that you claim to be world champion, because Tinsley got sick." I mean we got all sorts of negative hate mail.
ANDY SHEPPARD: But Schaeffer wasn't finished with this project. He knew that even though Tinsley had only lost three games in 42 years-
TAMARA STANNERS: Which is really incredible, what an amazing accomplishment.
ANDY SHEPPARD: It's amazing, but Schaeffer knew that that meant that Tinsley, like any human being, wasn't perfect. So Schaeffer set out to basically build a perfect checkers machine.
TAMARA STANNERS: What do you mean by that?
ANDY SHEPPARD: Well so, if a computer can play perfectly, then no matter who plays against it, the games will always end either in a draw or with the computer winning.
TAMARA STANNERS: So how do you go about making the perfect checkers machine?
ANDY SHEPPARD: With a [inaudible 00:19:09] ton, with a ton of computer horsepower.
JONATHAN SCHAEFFER: And so, literally, for more than a decade, I kept my computers computing, until 2007, when they had finally seen through all the necessary scenarios to prove that checkers with perfect play was a draw. In other words, Tinsley lost three times in 42 years, my program would never lose. And therefore, my program was a better checker player than Tinsley. The program was now perfect.
TAMARA STANNERS: Perfect?
ANDY SHEPPARD: Yeah.
TAMARA STANNERS: But how do you know it's perfect?
ANDY SHEPPARD: Well, take a simpler game, like tic-tac-toe.
TAMARA STANNERS: I always win.
ANDY SHEPPARD: No, I mean if you play someone who knows how the game works-
TAMARA STANNERS: Like my children.
ANDY SHEPPARD: It's probably always gonna be a draw.
TAMARA STANNERS: Yes.
ANDY SHEPPARD: Well it's the same thing for checkers, just multiply it times a trillion more possible moves.
TAMARA STANNERS: But I'm still not sure why it's so important to figure out checkers.
ANDY SHEPPARD: Well, it's like a lot of research, where the applications aren't always obvious, at first. But Schaeffer's program was applied in different ways to the mapping of the human genome, which was again, essentially a massive amount of data that had to be analyzed quickly, the way that Chinook worked on checkers. And the technology was also applicable to the development of certain video games, and GPS, so it turned out to be useful.
JONATHAN SCHAEFFER: How research works, and where it finds a home, in the type of applications that it can be deployed in, is sometimes a delightful surprise.
ANDY SHEPPARD: So Chinook was a major milestone in the quest for artificial intelligence.
TAMARA STANNERS: Hmm. That's pretty amazing. And how does Johnathan Schaeffer imagine life will change, once our new robot overlords take over?
ANDY SHEPPARD: Yeah, well you know for a guy who built the program that could beat the world's best checkers player, he's surprisingly optimistic about it.
JONATHAN SCHAEFFER: And I, for one actually embrace it. I believe that all this technology is being developed for good, and that it has huge potential to improve our quality of life, and I am eager to see where all of this is going to lead.
TAMARA STANNERS: Johnathan Schaeffer is a professor in the department of computing science, and the dean of the faculty of science, at the University of Alberta. His book, One Jump Ahead, is published by Springer. And thanks for this, Andy.
ANDY SHEPPARD: It was really fun.
TAMARA STANNERS: Your intelligence is so far from artificial. Get it? You like what I did there?
So you could look at any story about a machine outsmarting humans, as a cautionary tale. But we've got another perspective for you, over in the Relate Online Magazine. There's an article called Rethinking AI, Rethinking Our Jobless Future. And it challenges you to think about what opportunities will be created, as robots and AI supplant humans in many fields. You can read that at Relate.Zendesk.com.
That's it for Relate this week. Next week, an amazing story about a couple who prepared for a doomsday scenario in their own backyard, but ended up helping people more than 1,500 miles away. In the meantime, subscribe to Relate for free on Apple Podcasts, or wherever you listen, and we'll get that episode to you automatically. For articles on how to connect with your customers in deeper and more meaningful ways, visit Relate.Zendesk.com. And for a free trial of our customer service software, check out Zendesk.com. I'm Tamara Stanners, talk to you next week.