Tada! The 20-year crusade to solve checkers

When Marion Tinsley, the world number one, played checkers against Professor Jonathan Schaeffer's checkers-playing program Chinook for a series of exhibition matches in 1990, he declared: "I feel like a teenager again."

In fact, Tinsley was 63 at the time, and he was widely regarded as the greatest checkers player who had ever lived. This happy state of affairs was not without drawbacks, though. For one thing, it meant that it was surprisingly hard for Tinsley to get a good game of checkers. (I'm sticking with 'checkers' instead of 'draughts' in this article out of deference to my interviewee, incidentally. Also, it's a wonderfully percussive clickety-clack kind of word.)

"The first thing you have to know about Tinsley is that Tinsley was more machine than human," Schaeffer explains to me when we chat over Skype. "He was almost perfect. You think of perfection with computers - you don't think of it with humans. There was a period from 1950 to when we played him another time in 1992 - 42 years in which he lost a total of three games. Three games in 42 years he lost. Two of those games were trivial blunders in obviously drawn positions. In 42 years there's only one documented case where he was actually out-played.

"So he was virtually perfect. And very quickly as he began to rack up, you know, never losing a game, he got a nickname: the Terrible Tinsley." Schaeffer frowns. "He didn't like the name, but the point was that it was a terrible experience to play against him. You never won. People were afraid of him, and whenever people sat down to play him, they wouldn't play to win. They would only play to draw. Then, when Tinsley played Chinook in 1990, he came here and we played a 14-game match. He beat us one-to-nothing with 13 draws. He said, 'When I was young, Checkers was exciting. We'd try interesting things. We'd try dangerous lines and risky things. We'd do anything to try and win a game and it was fun. But as I became older, it became boring because nobody tried to beat me.' Chinook had no respect for Tinsley. None, right? The program would make loud, audacious moves. It would walk upon the edge of a precipice, daring Tinsley to charge at him. Tinsley said checkers was fun again because it was playing the game like it was played when he was a teenager. He really, really loved playing against the computer."

Making Marion Tinsley feel like a teenager again was a decent achievement, but it isn't Schaeffer's greatest. 17 years later, he would lead a small team that would go on to actually solve checkers. That is, he would be able to confirm exactly what the outcome would be in any checkers game played between two 'perfect' players if neither made any errors. What if Tinsley played Tinsley, and they both had a really good day? How does the optimal game of checkers end? It's a fascinating prospect. People had played variations of checkers for hundreds of years. All this time was it inherently, you know, rigged once you got to a certain - albeit extreme - level of proficiency? Rigged not by a designer, but by mathematics - by the universe?

Today, Schaeffer's Dean of Science at the University of Alberta, and he cuts an energetic figure when we chat over Skype. Through accident or design, the professor has angled the camera of his laptop slightly skyward, so above his head I see the clean metal sweep of an Alberta campus window frame set against bright white clouds. Schaeffer himself is staring down, like a pugnacious vicar delivering a rigorous sermon. He's part Noam Chomsky, part Norman Mailer and part James Caan, and he starts by admitting that, when he was a young boy, he didn't care about checkers at all. Instead, he cared about chess.

"That's what got me interested," he explains. "I was a young guy playing chess. I was reasonably good and I dreamt of becoming a world champion. Eventually you get to the point where you realise: hey, I ain't gonna make it. Because I had an interest in computing, I started hearing a lot about computer chess events. This was the 1970s. I knew how to program, I was interested in chess, so I thought, 'This shouldn't be too hard? I could write a program to make me world champion, right?' So that was my motivation. Sort of egotistical."

Schaeffer started writing chess programs in 1979 and was competitive for a decade. In 1986, his program tied for first place in the World Chess Championships - the World Computer Chess Championships. In 1989, he helped organise the next event in Edmonton, but bugs in his code led to defeat. Even worse, for a student of endgames, it was looking like the trajectory of his childhood chess hopes was about to repeat itself. "The writing was on the wall because some friends of mine had formed a team called Deep Blue," he laughs. "I realised that one person, me, working part-time on a chess program would never compete with what IBM was about to do with Deep Blue."

"'The program would make loud, audacious moves. It would walk upon the edge of a precipice, daring Tinsley to charge at him.'"

As a researcher, though, Schaeffer's job was to produce papers, so rather than stepping away from the field entirely, he switched games. "I realised I could be more productive solving the same problems with checkers than with chess," he says.

It was the kind of canny tactical move you'd expect from a chess player. "The whole point is that checkers had all the same research challenges, but it's simpler," explains Schaeffer. "Because instead of six different piece types, you only have two. Instead of playing on 64 different squares, you only have 32. Instead of a whole bunch of special rules like castling and en passant, there are none in checkers. It allowed me to just get rid of a lot of complications and special cases and just focus on solving the interesting problems."

And to Schaeffer there had always been one really interesting problem: "What does it take to build a superhuman game-playing program?" he sighs. "It's easy to build a game-playing program, just as it's easy to teach a human how to play a game like chess or checkers. With a little bit of training you can play any game, right? We're general purpose problem-solvers. But how do you get it to be superhuman? It's almost like the laws of diminishing returns. If you're a weak chess player, it doesn't take a lot of work to become a good chess player. It takes a lot more work to become very good, and then it takes an awful lot more to work to become a grandmaster. I was intrigued: what would it take for computer programs? What was the effort involved to get from good to very good to great, to perfect? "

After a little work, Schaeffer was back on the competition circuit with Chinook. This was the program that made Tinsley so happy in 1990 - and those exhibition matches were quickly followed by tournament games.

"We went through the normal channels and we earned the right to play in the human World Championship," he says. "You know, Deep Blue played Kasparov in 1997 but it did not earn the right to play Kasparov. IBM put up a very large amount of money, and Kasparov agreed to play for that amount of money. We went through human tournaments, we earned the right to play Marion Tinsley, the world champion, for the World Championship." Playing Tinsley in London in 1992, Chinook was narrowly defeated. Boston in 1994, however, saw Tinsley resigning after six games, all draws, stating that he was not well enough to play. Chinook won on forfeit. Nine months later, Tinsley was dead.

Sad times for the checkers community, but Chinook was not about to retire. If anything, Schaeffer was now more ambitious. Why play checkers to win when you could beat the game itself? "I always wanted to solve checkers," admits Schaeffer. "When I started out looking at the game in the early years it was with the idea of eventually solving it." He laughs. "I was pretty naive."

Remember, solving a game means being able to identify the ultimate outcome from any position in any match between two perfect players. In this context, 'perfect' means that neither player makes any mistakes along the way - each move is provably optimal. Schaeffer was aiming for what's known as a 'weak' solution. In other words, he was seeking to produce at least a single complete ideal sequence of moves from start to finish. Creating an algorithm that could do this sort of thing meant playing a lot of checkers - or at least getting a computer to do the playing instead as it hunted for those perfect moves.

This is where the process started to get tricky. "First off, how big a game is checkers?" asks Schaeffer. "Because, obviously, with a game like tic-tac-toe, you can play that perfectly and you can solve the game quickly. It's not hard. Why is checkers so much harder?"

It turns out that it's so much harder because of a very large number: 5 x 10 to the 20th. That's 500 billion billion - a five followed by 20 zeroes.

"That's how many positions there are in checkers, and people have trouble understanding how big a number this is," laughs Schaeffer. "So suppose you empty the Pacific Ocean. No water. It's bone dry. Now, I'm going to give you a spoon, a teaspoon, and you're allowed to fill the teaspoon with water, walk over to the empty Pacific Ocean, and dump that teaspoon of water in. If you do that 500 billion billion times, you will fill up the Pacific Ocean. So that's how big it is."

It was in 1989 that Schaeffer declared he was going to solve checkers, and that meant finding a way of navigating those 500 billion billion positions on a hunt for perfect moves. "When I started working on it seriously it was a million times bigger than any problem that had been computationally solved to perfection before," he admits. "This was really silly of me, but when you're young and innocent everything looks doable - so you do it."

Even so, 500 billion billion was just too big to handle. Schaeffer and his team had to invent ways of looking at the problem to try and bring that number down. Key to the success of the project was using something that had proven to be mildly effective in chess, but could be employed very powerfully in checkers. To start with, Schaeffer would turn the game on its head.

"To solve the game, I actually started at the end of the game," he explains. "So when checkers starts out there are 24 pieces on the board. We each capture some pieces and eventually you get down to maybe one piece on the board. I started there. Pretend there's only one piece on the board: my piece, a white piece. There are only 32 squares that piece can be in on the board. Actually, I could have a king or a checker, so there's actually 64 possibilities. I could build a database with all 64 possibilities, and all those possibilities are wins for me, because I'm the only one with a piece. And if I change the colour, those 64 possibilities are all wins for you. So now, I have a database that says: whenever I get down to one piece on the board, I don't have to do any computation. I can just look it up in my database and it tells me whether that's a win for me or a win for you. Right?

"Now back it up to two pieces on the board. One piece for me, one for you. I can figure out all the ways to put those pieces on the board. If ever I capture a piece, I have one piece left and I can then go to my database. Now I can move to three pieces, because when I lose a piece I've got two left and I've already got my answer for that - a win for you or a win for me waiting in the database. Eventually, I build this database until I've got ten pieces on the board. That's trillions of positions and it's beyond anything any human can understand. It's perfect information. If you give me any checkers position with ten pieces on the board, I just instantly go to the database and it tells me: win, loss or draw. No thinking, you're done."

Armed with his endgame database, Schaeffer then went back to the beginning of checkers. "With 24 pieces on the board, we would do searches, and then we'd stop whenever we got down to just ten pieces because we could look up the final result on our database. That allowed us to take a problem that was 500 billion billion and make it a million times smaller for me to solve. It became something I actually could solve."

Even so, it took a fair old while. Starting from 1989, Schaeffer's program ran continually on around 200 computers until 1996, when Schaeffer had to stop briefly because the next computations he needed to perform required machines more powerful than the current 32-bit standard. Three years later, with 64-bit processors commonplace, he set the computation running again and it then kept going until 2007. That's 18 years from start to finish, with three years of downtime.

In the spring of 2007, the team suspected that the computation was drawing to a close. "I know the end is near," Schaeffer remembers, "but I can't predict when the computers are going to stop. The way the program worked, it divided all the work that it had to do into pieces. Some pieces were small, some were very big. You never knew if something would take a minute or a day. You could never tell."

"'If you give me any checkers position with ten pieces on the board, I just instantly go to the database and it tells me: win, loss or draw. No thinking, you're done.'"

One afternoon in April, however, Schaeffer got a funny feeling. He was on a business trip in California, driving up the coast with his daughter. "It's about five o'clock on the weekend and I suddenly had an urge. I said, 'We need to find a hotel. I need to check the computers.' We got to a hotel. I immediately went to the room and logged in. As ever, the first thing I did was check the Chinook directory to see what was going on, and I saw immediately that all the computers had stopped.

"I was so angry," he laughs. "We were running between 50 to 100 computers at the time, and when all the computers stopped, something had gone wrong - maybe a power outage - and it takes a while to get them all restarted. When you're talking about a computation where you have to have perfection, you can't risk introducing an error. So if it died in the middle of a computation, you had to get rid of that and start from scratch.

"So I thought, 'Oh god, it's going to take an hour for me to fix this all up.' I decided to look at the damage. I opened the log file and I looked at the end of it. The end of it just had one word."

That word was Tada!

Tada! Schaeffer had programmed this into the system a long time ago, but admits he'd never really expected to see it. It meant that the computation had stopped because there was no more work to be done. It meant checkers was solved.

"What really freaked me out was, the date stamp on the Tada! was 5.17 PM," he laughs. "It was 5.18 right then when you adjust for the time difference. So I had logged in within seconds of the computation finishing. Somehow I just knew the computation was ending. Even stranger, my research associate who had done a lot of the work on the project, he logged in at the same time. Literally within one minute of the computation ending, both of us had logged in and we were talking to each other. I concluded that the internet has some kind of psychic abilities. Very strange."

And the outcome? A draw. "Perfect play by both sides in checkers results in a draw," says Schaeffer. "Two perfect players will always draw. If you have an imperfect player who makes a mistake, then that person will lose."

The key, of course, is that word 'perfect'. It means that while Schaeffer has solved checkers, he hasn't ruined it for most of us. If you and I played checkers tomorrow, a draw would hardly be the only possible outcome. I would certainly make mistakes. You might make a few mistakes too. The game would still be pleasantly unpredictable and we'd have a great time. (You could bring brioche.)

To me, it feels like Schaeffer's ultimate achievement is akin to discovering something buried in the genetic code of checkers - something buried deep. Humans have been playing the game for so many hundreds of years, and now Schaeffer's revealed that, all this time, at a certain level, it's been waiting to break down into unavoidable stalemate. The only way to find this out for certain, of course, is to play the game in a manner that no human ever would. Tinsley may have been more machine than human, and he may even have suspected checkers was fundamentally a game about drawing once you attained his degree of skill, but he would never have been able to prove it the way Chinook could. He played the game differently. His brilliance was a different kind of brilliance.

"It's the same analogy as birds flying," argues Schaeffer. "We all know how birds fly. They've evolved that way and they do a very good job of flying. When you get technology and you introduce it to the mix, you could mimic the way birds fly, but technology has certain advantages. If you're building wings you can build them out of metal, you can build jet engines.

"It's the same thing with computers and intelligence. Since the hardware is different, the things that you can do well and that are easy are very different. Humans are very good at learning and reasoning and things like that. Computers are generally weak at learning and reasoning. On the other hand they're very good at doing partial differential equations or solving repetitive problems billions of times or memorising gigabytes of data. Humans are very weak at doing that. You're not going to memorise the encyclopaedia. If I give you a task and ask you to do it a billion times you're not going to do it."

Checkers isn't the only game to have had its genetics explored in this manner. Not by a long shot. "There are a lot of games that are solved," says Schaeffer. "Most of them are uninteresting - they're not the sort of games that you or I will ever play. Then there are games we would love to be solved. Chess. Chess is huge. Chess will not be solved unless there's new technology. Go is impossible to solve with current technology. But chess, checkers, go: they're all solvable. There are games with elements of luck, where you can't build a program that's always going to win because there's luck involved, like the roll of a dice, but elsewhere..."

And finally, what about Schaeffer and checkers? His program seemed to bring the game back to life for Tinsley. Has Chinook's eventual solution affected Schaeffer's own enjoyment of huffing and king-making at all? Does he still play, or has knowing about that draw buried deep within the genes ruined his fun?

"Oh, I've never played checkers," Schaeffer laughs. "I'm not a checkers player, I'm a chess player, remember?"

If you're interested, you can play against Chinook online.