Jonathan Schaeffer has a PhD in computing science, an associate professorship at one of Canada's top universities, and research grants from IBM and NSERC. But to most people, he's the guy who plays checkers with a computer.
And he doesn't mind.
"I know the reputation of games," says the University of Alberta professor. "You have to understand that what I'm working on is machine intelligence. I happen to use games as my experimental domain."
Schaeffer used to work with chess, but after 10 years of increasing frustration, he did a stock-taking. "The problems I was trying to solve were just too difficult, to be quite honest," he says. "The more I thought about it I realized you had to be able to walk before you could run."
"A chance conversation" with some colleagues got him thinking about checkers. For the last four years, he's focused much of his effort and energy into developing a checkers-playng program called Chinook, all in the quest to "create the illusion of intelligence" in a computer.
Anyone wondering why there is a need to create such an illusion need look no further than their household chores. "Wouldn't you like to be able to talk to a machine and say, would you please vacuum the rug?" Schaeffer says. "Computers are essentially slaves. They'll only do what you tell them to do [but] the only way you can tell a computer what to do is by programming it."
Like others who work in the area of artificial intelligence, Schaeffer is interested in creating computers that can not only amass data, but figure out what to do with it. In other words, he's trying to develop computers that can think.
"I just drove two days ago to Drumheller," he says by way of explanation. "Coming back on the Calgary Trail is pretty damned boring. I don't know why the car can't drive itself. Why can't there be sensors in the car? Why can't it know where the right and left shoulder are? Why wouldn't it be possible to have a car that is smart enough to drive itself? I could program it to say here I am, here's my destination, here's the route I want to follow and it would do the rest.
"These are things that artificial intelligence can do for us, and I think all they do is improve the quality of our life," he says. "Ultimately isn't that what all technology is supposed to be for?"
It sounds quite benevolent. But think Focus on Computing Science about it long enough and some pretty scary scenarios come to mind: Bladerunners, Terminators, Hal from 2001: A Space Odyssey.
If a computer can master a game with billions of moves, how far are we from computers that can make really important decisions, everything from who will get a heart transplant to who will rule the world?
"None of that is going to happen in my lifetime," Schaeffer says. "There are certain things I'd like to happen in my lifetime, but as with any new technology, people have to think about how it's going to evolve and make sure it's going to evolve for peaceful purposes."
Even as you read this, 100 computers, some at the U of A and the rest at Lawrence Livermore Laboratories in California, are peacefully teaching Chinook 300 to 400 million checkers positions a dav, whenever they have free time. The method they're using is called parallel computing, which Schaeffer calls "the hottest research going on right now."
Parallel computing breaks a problem into small pieces and enables a number of computers to work on those pieces, so that essentially the entire problem is being solved at once. Schaeffer likens it to a system of hierarchical management, where different divisions are all working toward the same goal.
The technology is used mostly in physics, chemistry, and engineering, where it provides an efficient approach to tackling complex problems. For an airplane manufacturer, it can mean the difference between waiting years to test a plane after it's been assembled, or testing the parts throughout the design and construction process.
For Chinook, it means the difference between winning and losing.
The program is currently learning the four to five billion possible positions when there are three checkers and one king on each side of the board. Because that's too much for one computer to handle, the problem is broken down so that each computer is responsible for roughly 10 million positions. Given enough time, Chinook will learn a11 500 billion billion checkers positions.
Plentv of scientists studying artificial intelligence use games as their "drosophila." But only Schaeffer and his colleagues can lay claim to having created the second-best checkers player in the world. And if Schaeffer's predictions are on target, Chinook is on its way to becoming the best checkers player in the world.
"We believe we will have a game that plays perfectly," he says. "We believe in the next few years checkers will be a solved game. We believe it will be a draw, and Chinook will never lose. Never."
It may seem as if Schaeffer is taking the whole thing a bit too seriously: after
all, it's just checkers. But for Schaeffer — indeed, for the international checkers community — Chinook has gone beyond fun and games.
"Basically we've created a monster that's bigger than us," Schaeffer says, and he's only half-joking. "We're trying to train it to be even better, and of course it's very difficult because it's just a much better player than us. There's only one person in the world that's better, and of course he's not going to help us."
That person is Dr Marion Tinsley, a mathematics professor at Florida A&M, and the reason he's not going to help Schaeffer is that he's a better checkers player than Chinook is and he wants to keep it that way.
For more than 40 years, Tinsley has been the world's best checkers player. "The guy is as close to perfection as you can imagine," Schaeffer says.
Until three years ago, Tinsley was the official world champion. But when the World Checkers Federation refused to let him play Chinook for the championship in 1990, the Florida mathematician relinquished his title, freeing him to play Chinook in an unofficial tournament.
Chinook's qualifying for the official championship "put the checkers world in a frenzy," Schaeffer says. "A lot of people were very defensive. They said computers have no business playing for the human world checkers championship."
Tinsley, on the other hand, relished the chance to meet an aggressive opponent rather than one of the timid competitors he has to face just about every time he sits down at the match table.
"Whoever his opponent is does anything for a draw," Schaeffer explains. "As a result, checkers has become boring. But Chinook doesn't care who Tinsley is, doesn't care about his reputation. The computer is willing to go all out for the win. The computer is ~villing to walk along the edge of a cliff if necessary. In other words, the computer has no respect for Tinsley."
Adds Schaeffer, "Tinslev said the first time he played Chinook, it made him feel like a teenager again."
Last year, in a $10,000 non-official world championship match held in London and sponsored by Silicon Graphics (the company that helped create the special effects for Terminator 2), Tinsley and Chinook tied 33 times. Tinsley beat the computer four games to two. Up till then, he had lost seven games in 43 years.
Schaeffer is in the process of arranging a rematch with Tinsley. He doubts Chinook will meet the new official world champion, Derek Oldbury of England. For one thing, it's unlikely that the World Checkers Federation would change its mind and permit Chinook to play. More to the point, Oldbury isn't the checkers player Tinsley is, and finding an independent sponsor for a match featuring him would be difficult.
"Tinsley's record against Oldbury is 15 wins and one loss," Schaeffer says. "That one loss was in the first game they played, in 1958. Tinsley made a blunder. Now I ask you, who is the world champion? Is it Tinsley or Oldbury?
"We would love to play Oldbury just to set the record straight," he says. "We have a problem now: Derek, being the world champion, feels he should get the same treatment as Tinsley, who played in a $10,000 championship. If I could find a sponsor I'd do it, but nobody cares about Derek, I'm afraid."
And so Schaeffer focuses on the rematch with Tinsley, working to secure a sponsor and a venue big enough to host the event and the attendant press corps sure to show up to witness what could be a momentous occasion — should Chinook win.
"For the first time in history," he says, "computers will be demonstrably superior to humans in this problem domain."
A big win won't mean the game is over for Schaeffer, though. "It's a performance milestone, but it's not necessarily a research milestone," he says. "The work continues."
How long the work will continue on Chinook, however, is questionable. Although Schaeffer is committed to seeing a rematch with Tinsley, he doesn't pretend that he will stick with checkers forever.
"Progress is slowing down," he admits. "I might get to the point where I did in chess, where I'm hitting my head against a brick wall. Maybe I'll just call it a day one day and say, 'I'm getting nowhere. The results are just not justifying the effort.' Maybe I'll go on to something different."
He might even go back to the game that drove him to checkers in the first place. "I've learned a lot in checkers that I could use in chess."
Published Summer 1993.