Copyright ©2007 NPR. For personal, noncommercial use only. See Terms of Use. For other uses, prior permission required.

JOE PALCA, host:

And now, switching gears. A computer scientist has solved the game of checkers. He wrote a program that will never be beat. After analyzing not the five billion or the 50 billion or the five million billion, but the 500 billion billion checkers positions, he determined that if you play a game of checkers with no mistakes, neither player will win the game. Wow, that's some outcome. It ends in a draw. The calculations took nearly two decades.

Here to talk about the king of all checker programs is Jonathan Schaeffer, a computer scientist at the University of Alberta. Schaeffer wrote most of the programs that solved the centuries-old game and is responsible for the world's best poker program. Well, maybe we'll find out about that, too. Welcome, Dr. Schaeffer.

Dr. JONATHAN SCHAEFFER (Computer Scientist, University of Alberta): Thank you.

PALCA: So what does it mean to solve checkers?

Dr. SCHAEFFER: What it means is to answer the age-old question, is, if you never make a mistake, what happens? We all know, for example, at Tic-Tac-Toe that if you play perfectly, the game is a draw. Well, we've done the same thing with checkers. Not only do we know now that perfect play leads to a draw, but if you go to our website, you can see the proof. And if you have the patience, you can go through the proof and use it to learn how to play perfect checkers yourself.

PALCA: I'd like to invite our listeners, if they have a burning checkers question to call us not about the speech that President Nixon gave, but the game that you play on a checkerboard square. Our number is 800-989-8255.

So what drew you to this particular problem?

Dr. SCHAEFFER: Well, I'm a researcher that works on problems of artificial intelligence. We're trying to create computer programs that exhibit intelligent behavior. And because of my love for games, I've always used games as my experimental test bed.

In the 1980s, I worked on chess programs. And I had one of the best chess programs in the world at that time. Some of my friends got together, formed a team called Deep Blue, and well, the rest, as they say, is history.

PALCA: Mm-hmm. Wait a minute. For those of us who don't know about Deep Blue, what did Deep Blue succeed at that made it historic?

Dr. SCHAEFFER: Deep Blue, in 1997, played a match against the then-world champion, chess champion Garry Kasparov and won the match. And that, of course, was a historic event. We all have a high regard for the game of chess and we were, I think, collectively surprised to see the computers were as good as, or perhaps better than mankind at the game of chess.

PALCA: So you've essentially, you know, taken the approach of computational muscle to solve checkers. It's not as if - I mean, you did it by brute force or is that not a fair assessment?

Dr. SCHAEFFER: It's not a fair assessment. There's 500 billion billion checkers positions as you mentioned earlier. That's a five followed by 20 zeroes, so you can - astronomically big number, but we didn't use brute force. If we used brute force, we would've had to look at all of those positions. We used smarts in the programming, intelligence. So that we solved in one five-millionth of the amount of work that you would think. A one followed by 14 zeroes is the amount of work that was done.

PALCA: Mm-hmm.

Dr. SCHAEFFER: Five million times faster than the conventional brute-force approach.

PALCA: Get it. We're talking with Jonathan Schaeffer about his new paper, actually, in Science this week that solves checkers. We're taking your calls at 800-989-8255.

I'm Joe Palca. And this is TALK OF THE NATION from NPR News.

Okay. So, say again, if you could do it with a tenth of the time, did you have to do it on one computer? Was it distributed computing? How much of it was algorithm and how much of it was a computer muscle?

Dr. SCHAEFFER: It was both. We needed a lot of computer muscle because the computation is huge. But without the intelligence, this never would've got solved in my lifetime. I'm a little bit impatient. I wanted to see the result. And all of our research efforts were spent on designing new algorithms that could effectively use the computing resources we had at hand to get the result quicker.

PALCA: Okay. Let's take a call now and go to Michael(ph) in Brentwood. Michael, you're on the air. Did I do that right? No. No. It's not working. Okay. Never mind. All right. Maybe now - whoops, not yet. Michael, are you there? Mm, yes. Michael? No. No Michael. Okay.

Well, I have another question. When you talk about not making a mistake, what is a mistake in checkers?

Dr. SCHAEFFER: Well, the program only treats every position as having exactly one of three values. We either prove that it's a win. We prove that it's a loss. Or we prove that it's a draw. And for the game of checkers, to play perfectly, it means that in the starting position, it's a draw. You will only play a move that leads to a draw. If the opponent, who might be human who makes mistakes, does make a mistake, then they will make a move into a position that is a loss for them. In which case, the program will prefer to take positions that lead to wins now, instead of a draw. So if you make a mistake, you're going to lose.

PALCA: Hmm. And is there - I mean - this program has a name, right?

Dr. SCHAEFFER: Not really. We developed a program in the early 1990s called Chinook, which won the human World Checkers Championship. And everything we do, I'd, sort of, call it Chinook, because that's the name that people know us. But this is actually a different program, and it really, probably should have a different name. But I'm - and I confess that I'm not particularly creative at coming up with clever names. And so, I've, sort of, avoided the question.

PALCA: Well, maybe we can invite our listeners to submit suggestions for clever names. And we'll forward you the best one. How is that?

Dr. SCHAEFFER: Great.

PALCA: Okay.

Dr. SCHAEFFER: I'd love it.

PALCA: Well, you know, try and be helpful. Is there - I mean, has knowing that you cannot win a game of checkers dulled your interest in playing the game, or did you never have that much interest in playing games?

Dr. SCHAEFFER: I'm sorry. I didn't quite catch the question.

PALCA: Has knowing that there's no possibility that you're going to beat this computer program, dulled your interest in playing the game or did you never have that much interest or will it...

Dr. SCHAEFFER: Yeah. I'm not a checker player. I do play games and I've known enough about the game to appreciate its beauty. But I'm a competitive person, and when I play games, I like to win. And there's not enough time in life to hold down a full time job, a family life, hobbies, interests, and be competitive at a game like checkers. So I just play recreationally and for fun.

PALCA: Okay. Let's see if we can get one quick call in. And we'll go to Tim(ph) in Cleveland for one quick call. Tim?

TIM (Caller): Hi.

PALCA: Hi.

TIM: Hi. Yeah. I was wondering, he seemed to have mastered the software for the game of checkers and chess, I was wondering if you can also do the same for Go.

PALCA: Okay.

TIM: The game of Go.

PALCA: Let's ask.

TIM: And I'll take my answer off the air.

PALCA: Okay. Thanks, Tim.

Dr. SCHAEFFER: It's a very good question. Checkers, when you write the number down, there's 20 zeroes on the end. When you write it for Go, there's roughly 100 zeroes on the end. So the answer is, no. It's not going to happen for a very, very long time that we're going to have solved the game of Go. And in fact, it's not even clear that we're going to have very strong Go programs for quite a few years yet.

PALCA: All right. Well, I guess - I would keep talking. But the opportunity to say that there is no go for Go is too intense for me not to take advantage and say that. So I'll just say that, and thank you very much for joining us today and talking about your checkers program.

Dr. SCHAEFFER: Thank you very much.

PALCA: That was Jonathan Schaeffer. He's a computer scientist at the University of Alberta. And if you go to this week's Science magazine, you can see how he solved the game of checkers.

Copyright © 2007 NPR. All rights reserved. No quotes from the materials contained herein may be used in any media without attribution to NPR. This transcript is provided for personal, noncommercial use only, pursuant to our Terms of Use. Any other use requires NPR's prior permission. Visit our permissions page for further information.

NPR transcripts are created on a rush deadline by a contractor for NPR, and accuracy and availability may vary. This text may not be in its final form and may be updated or revised in the future. Please be aware that the authoritative record of NPR's programming is the audio.

Comments

 

Please keep your community civil. All comments must follow the NPR.org Community rules and terms of use, and will be moderated prior to posting. NPR reserves the right to use the comments we receive, in whole or in part, and to use the commenter's name and location, in any medium. See also the Terms of Use, Privacy Policy and Community FAQ.