How Checkers Was Solved
The story of a duel between two men, one who dies, and the nature of the quest to build artificial intelligence
Marion Tinsley—math professor, minister, and the best checkers player in the world—sat across a game board from a computer, dying.
Tinsley had been the world’s best for 40 years, a time during which he'd lost a handful of games to humans, but never a match. It's possible no single person had ever dominated a competitive pursuit the way Tinsley dominated checkers. But this was a different sort of competition, the Man-Machine World Championship.
His opponent was Chinook, a checkers-playing program programmed by Jonathan Schaeffer, a round, frizzy-haired professor from the University of Alberta, who operated the machine. Through obsessive work, Chinook had become very good. It hadn't lost a game in its last 125—and since they’d come close to defeating Tinsley in 1992, Schaeffer’s team had spent thousands of hours perfecting his machine.
The night before the match, Tinsley dreamt that God spoke to him and said, “I like Jonathan, too,” which had led him to believe that he might have lost exclusive divine backing.
So, they sat in the now-defunct Computer Museum in Boston. The room was large, but the crowd numbered in the teens. The two men were slated to play 30 matches over the next two weeks. The year was 1994, before Garry Kasparov and Deep Blue or Lee Sedol and AlphaGo.
Contemporary accounts played the story as a Man vs. Machine battle, the quick wits of a human versus the brute computing power of a supercomputer. But Tinsley and Schaeffer both agreed: This was a battle between two men, each having prepared and tuned a unique instrument to defeat the other. Having been so dominant against humans for so long, Tinsley seemed to thrill at finally having some entity that could give him a real game. He had volunteered to play friendly matches against the computer in the run-up to their two world championship matches. And Schaeffer, though he was a bull-headed young man, had become the most effective promoter of Tinsley’s prowess and legacy.
But there, in that hall, a quirk of human development was troubling Tinsley. His stomach hurt. The pain was keeping him up all night. After six games—all draws—he needed to see a doctor. Schaeffer took him to the hospital. He left with Maalox. But the next day, an X-ray revealed there was a lump on his pancreas. Tinsley understood his fate.
He withdrew. Chinook became the first computer program in history to win a human world championship. But Schaeffer was crushed. He’d devoted years of his life to creating a program that could beat the best checkers player ever, and just as he was about to realize this dream, Tinsley quit. Seven months later, Tinsley died, never having truly lost a match to Chinook.
And that would lead Schaeffer to undertake a 13-year computational odyssey to exorcise the man’s ghost. With Tinsley gone, the only way to prove that Chinook could have beaten the man was to beat the game itself. The results would be published July 19, 2007, in Science with the headline: Checkers Is Solved.
“From the end of the Tinsley saga in ’94–’95 until 2007, I worked obsessively on building a perfect checkers program,” Schaeffer told me. “The reason was simple: I wanted to get rid of the ghost of Marion Tinsley. People said to me, ‘You could never have beaten Tinsley because he was perfect.’ Well, yes, we would have beaten Tinsley because he was only almost perfect. But my computer program is perfect.”
Jonathan Schaeffer did not begin his career intending to solve checkers. He was a chess player, first. Good, not great. But he also loved computers—and had done a Ph.D. in computer science, so he decided to build a chess-playing program. He called it Phoenix and it was one of the better chess programs of many that were created in the 1980s. In 1989, he “crashed and burned” at the World Computer Chess Championships, however. At the same time, the team that would form DeepBlue, the chess software that would eventually defeat Kasparov, was coming together. Schaefer realized he would never build the world computer champion.
A colleague suggested that perhaps he should try checkers, and thrillingly, with just a few months of work, his software was good enough to bring to the Computer Olympiad in London to compete against other checkers-playing bots. And it was there that he began to hear about Marion Tinsley, the great.
At the highest levels, checkers is a game of mental attrition. Most games are draws. In serious matches, players don’t begin with the standard initial starting position. Instead, a three-move opening is drawn from a stack of approved beginnings, which give some tiny advantage to one or the other player. They play that out, then switch colors. The primary way to lose is to make a mistake that your opponent can jump on.
This would seem to make checkers a game amenable to computer play. That was certainly the idea back in the mid-1950s, when an IBM research scientist named Arthur Samuel began to experiment with getting a checkers-playing program to run on an IBM 704. He worked on the problem for the next 15 years or so, publishing several important papers on what he called—and what we all would now call—“machine learning.”
Machine learning is the underlying concept for the current wave of artificial intelligence. The descendants of that early work now promise to revolutionize whole industries and labor markets. But Samuel’s programs never had much success against actual humans. In May 1958, several members of the Endicott Johnson Corporation Chess and Checkers Club trounced the computer, much to the delight of the Binghamton Press and Sun-Bulletin.
“The human brain, sometimes lost sight of in an age of satellites, frozen foods, and electronic data processing machines, returned to former glories early today,” the paper said. “The 704, Dr. Samuel explained, does not think. What it does, he said, is to search its ‘memory,’ stored on tape, of checkerboard situations it has encountered previously. Then it rejects choices which have turned out badly in the past and makes moves which turned out well.”
This still would work pretty well as a description of what’s known as “reinforcement learning,” one of the basket of machine-learning techniques that has revitalized the field of artificial intelligence in recent years. One of the men who wrote the book Reinforcement Learning, Rich Sutton, called Samuel’s research the “earliest” work that’s “now viewed as directly relevant” to the current AI enterprise. And Sutton also happens to be one of Schaeffer’s colleagues at the University of Alberta, where Google’s DeepMind AI shop recently announced it will set up its first international research office.
While his techniques were groundbreaking, 10 years later Samuel had made, in his own words, “limited progress” on the problem, though he’d kept working at it at IBM, while visiting at the Massachusetts Institute of Technology, and then with a Department of Defense grant at Stanford University. As with so many of the currently hot AI techniques, he just did not have the computational horsepower or datasets that he needed to make the beautiful ideas work.
So when Schaeffer began building his own software, he went straight back to Samuel, and found that he could not exactly follow Samuel’s path. He’d have to build a new system. At first they called it The Beast, but eventually they named it Chinook after the warm winds that sometimes blow through Alberta.*
The work consumed Schaeffer. As he described it in his 1997 book, “Sometimes, when I had difficulty getting to sleep, I would fantasize about the exhilaration that I would experience when Chinook finally defeated the Terrible Tinsley.” His wife would interrupt his reveries asking, “You’re thinking about him again, aren’t you?”
As the software developed through the years, it retained two core components. The first is easy to understand: It’s a “book” of complete computations of every possible checkers position with a certain small number of pieces on the board. So, if there were six pieces left—and as time went on, seven, then eight—Schaeffer’s software knew every possible combination. Back in the early ’90s, it took vast amounts of computer time to be able to run all those calculations.
But as Schaeffer and his team did more and more computation, Chinook got better and better. It started to be able to beat people. But they knew that they couldn’t calculate every possible position.
The rules of checkers are simple, but the number of potential moves is massive—there are 5 x 1020 possibilities. Schaeffer has an analogy to help people understand how ridiculous that is: Imagine draining the Pacific Ocean and then having to fill it back up with a tiny cup, one at a time. The sea is the number of checkers possibilities. The cup is each calculation.
The second component of the system is a little trickier to grasp. Chinook needed to search through possible moves beginning with the start of a match. Like many similar systems, Chinook would look ahead many possible moves and then try to score each permutation’s desirability. At first, Chinook could only look ahead 14 to 15 moves out, but as computers and the software improved, it could look further and further. “As with chess, deeper was always better,” Schaeffer told me.
In late 1990, the American Checker Federation allowed Chinook to play in the U.S. Championships. The software went undefeated and played Tinsley to a draw six times. That earned the software the right to challenge Tinsley for the world championship.
And after Chinook’s 1990 performance, Tinsley called up Jonathan Schaeffer and asked if he might like to play a few friendly matches.
From 1950 to 1990, Tinsley had been the world champion of checkers whenever he wanted to be. He’d occasionally retire to work on mathematics or devote himself to religious study, but he’d eventually return, beat everyone and become champion again. In that 40-year span, he lost five total games and never once dropped a match.
Derek Oldbury, probably the second best player of all time, wrote an encyclopedia of checkers. It was effusive in its praise for the master: “Marion Tinsley is to checkers what Leonardo da Vinci was to science, what Michelangelo was to art and what Beethoven was to music.”
/media/img/posts/2017/07/kL4sALtPKCzGuCmXAn6UqD6NvEaJmeh_2MkYyenfFefy9Svxs35tUphmmTVRPUGDOpbe8LB16FYccKtRCV5UueVB0UlormV2zKrNxvfWwZXnWAx0dh45zL2PgaMPINV8IJZpxQaD-1/original.png)
It’s hard to know what to make of Marion Tinsley from the perspective of the 21st century. He seems otherworldly or, at the very least, othertimely. His life was composed of checkers, mathematics, and his abiding faith. He was kind, by literally every account, and yet his style of play was relentless and aggressive.
It is not uncommon to say that someone lived a “life of the mind,” but in Tinsley’s case both the life and the mind were unusual. For years, as an undergraduate and then graduate student at the Ohio State University, he spent eight hours a day on checkers. He never married. “I haven’t seen a checker marriage that worked out,” he told a reporter. “It is a very rare woman who can be married to a real student of checkers.” His mother lived with him well into the 1980s. A 1993 profile in The Philadelphia Inquirer found Tinsley in a big, blue sweater over a shirt and tie. His lunch was “a jar of milk, half an apple, and a peanut butter sandwich.”
His relationship with the racial dynamics of the South is also fascinating. “I had thought of going to Africa as a self-supporting missionary," he told Sports Illustrated in 1992, "until a sharp-tongued sister pointed out to me that most people who wanted to help blacks in Africa wouldn't even talk to blacks in America.”
Instead, he became a lay minister at a predominantly black church and left Florida State University’s math department to teach at the historically black Florida Agricultural and Mechanical University. He spent 26 years there. A yearbook from towards the end of his time there showed a deep and lively campus life in which Tinsley might have been the only white person over the age of 40. No contemporary accounts ask any of the black students what they made of their checkers-champion professor, but a colleague was able to describe Tinsley’s role in a local obituary: “At his retirement dinner, literally everybody; young, old, black, white, students, faculty members ... gave testimonies about the impact he had had on their lives.” For a man of his time and upbringing in Kentucky, his path seems almost miraculous.
One thing is for sure: Tinsley was a genius. His genius had been refined and whittled into a strange and wonderful shape. He was the very best at this one thing and pretty ordinary in all else. One part of him had become almost like an artificial intelligence—narrow but extraordinarily capable—while the rest of him lived this simple human life.
When a reporter visited him in Tallahassee, Florida, in 1993, lavender azaleas lined the driveway leading up to his two-story brick house. His home had bare white walls. A room upstairs contained his checkerboard and heavily used checkers books. Tinsley liked to sit in a velour La-Z-Boy. He could never quite explain what checkers meant to him—why he’d pored over sequences of moves for almost his entire life, why he’d kept a magnetic checkerboard by his bedside to work out new combinations. It was something close to godly, though.
“Checkers is a deep, simple, elegant game,” he once said. Playing another human great was “like two artists collaborating on a work of art,” Tinsley said another time.
And then there is his most quotable line: “Chess is like looking out over a vast open ocean; checkers is like looking into a bottomless well.”
It was as if the checker moves were Scriptures that he could endlessly meditate on and understand in new ways. “Out of the clear blue sky an improvement of a published play will just come to mind, as if the subconscious has been working to come to light,” he told the Chicago Tribune in 1985. “A lot of my discoveries come that way, out of the clear blue sky. Some of my insights into the Scriptures come the same way.”
When Tinsley came to Edmonton in 1991 to play the friendly matches against Chinook, Schaeffer was also blown away that the world champion would agree to play this computer for fun.
The two men sat in his office and began the matches, Schaeffer moving for Chinook and entering changes in the game into the system. The first nine games were all draws. In the tenth game, Chinook was cruising along, searching 16 to 17 moves deep into the future. And it made a move where it thought it had a small advantage. “Tinsley immediately said, ‘You’re gonna regret that.’” Schaeffer said. “And at the time, I was thinking, what the heck does he know, what could possibly go wrong?” But, in fact, from that point forward, Tinsley began to pull ahead.
“In his notes to the game, he later wrote that he had seen all the way to the end of the game and he knew he was going to win,” Schaeffer said.
The computer scientist became fixated on that moment. After the match, he ran simulations to examine what had gone wrong. And he discovered that, in fact, from that move to the end of the game, if both sides played perfectly, he would lose every time. But what he discovered next blew his mind. To see that, a computer or a human would have to look 64 moves ahead.
“I was absolutely stunned,” Schaeffer told me. “How do you compete with somebody whose understanding of the game is so deep that he immediately knows through experience or knowledge or doing some amazing search that he was gonna win that position?”
Schaeffer still struggles to make sense of Tinsley’s incredible skill. When he wrote his book about the saga, One Jump Ahead, Schaeffer received a letter from Tinsley’s academic supervisor. It read, Schaeffer told me, “that he was an exceptionally talented person and he was capable of doing one thing brilliantly. If it wasn’t checkers, he probably would have been a brilliant mathematician.”
When someone’s motivations are not fame or money, we seem to require a higher level of explanation, some emotional engine the rest of us do not possess. The closest Tinsley ever came to describing his motivations came in the 1993 Philadelphia Inquirer feature. He was an introvert who “felt unloved” by his parents, who he thought doted on his sister. To gain their approval, he competed at math and spelling bees. “And as a twig is bent, it grows: As I grew up, I still kept feeling that way.”
The hunger to excel propelled Tinsley to college at 15, where he really discovered the passion that would dominate his life. He won his first world title in 1955.
And in 1992, he agreed to put his title on the line in the first Man-Machine World Championship against Chinook. The match was sponsored by the computer manufacturer Silicon Graphics and held in London. “I can win,” Tinsley told The Independent. “I have a better programmer than Chinook. His was Jonathan, mine was the Lord.”
For the two weeks leading up to the event, another world-class player, Don Lafferty, trained with him down in Tallahassee, going over their matches and reviewing positions deep into the night.
The 1992 games were held at the Park Lane Hotel, which had hosted world chess championships as well as the Computer Olympiad that had been Chinook’s public debut two years earlier. The room was large and two-storied, with a balcony that overlooked the players and the refrigerator-sized computer that was running Chinook.
Schaeffer and Tinsley sat across from each other, and a large screen rendered the movement of the pieces. Tinsley drew first blood, besting Chinook in game five. But then in game eight, Chinook delivered a stunning win; it was Tinsley’s sixth loss in 40 years.
Despite the years of toil and dreams of success, Schaeffer felt sadness in that moment. “We’re still members of the human race,” he wrote in his book, “and Chinook defeating Tinsley in a single game means that it will only be a matter of time before computers will be supreme in checkers, and eventually in other games like chess.” Schaeffer might have won, but the humans have lost.
After a series of draws, Chinook won again in game 16. No living player had ever defeated Tinsley more than once. Incredibly, almost unbelievably, the software was on top. They were on the verge of making computing history.
Then, in an episode that Schaeffer still finds too painful to describe, Chinook had some sort of error, which forced them to resign the game, tying the match up. “Tinsley viewed it as God helping him out,” Schaeffer said. “It was a religious experience for Tinsley and one of the most devastating experiences of my life.”
Schaeffer and Chinook were never able to get back on top.Tinsley came from behind to win the match, retaining his title.
“I think, if I can keep my health, I don’t believe there will ever be a computer that can beat me,” Tinsley told CNN after the match.
All of which set the table for the 1994 matchup in Boston.
In the run-up, Chinook had played Derek Oldbury and trounced him. Shortly thereafter, Oldbury died. “Chinook plays Oldbury. Chinook beats Oldbury. Oldbury dies,” Tinsley joked with Schaeffer. “He must have died of Chinookitis!”
Schaeffer was not amused. He was a young man programming computers to play an old man’s game. The best players were dying off. And it was, in the eyes of some in the checkers world, a bit untoward for this guy with his fancy machines and code to come around beating up on the frail masters.
As he’s gotten older, Schaeffer has come to wish that he’d appreciated Tinsley more during their entanglement. “I also look back at my time with Marion Tinsley, not realizing how fleeting it would be and how much I appreciated it. I didn’t take advantage of that and reap the benefits of a warm and deep friendship that I had with him,” he told me. “I look back at it and with hindsight; I can say that I am disappointed in myself. I wish I would have done things differently, but at the time, when you’re obsessed, you can only see in one direction.”
Even in his narration of taking Tinsley to the hospital, Schaeffer cannot get over the idea that the older man’s illness might prevent him from having the chance to beat him. Tinsley says, “I’m ready to go,” and Schaeffer acts befuddled. The old man knew he was dying, and the younger didn’t get it.
After Tinsley resigned, Don Lafferty took his spot and dueled with the computer, but Schaeffer’s sights became set on the larger prize of solving checkers. Human checkers players came to despise Schaeffer, by his own telling. They sent him letters trash talking him and his software. He released One Jump Ahead in 1997, and still checkers players kept coming for him.
From 1997 to 2001, he suspended his project to solve the game, which meant creating a computer program that always knew the right move. It would be unbeatable. It would be perfect.
When he returned, his team expanded the endgame database—Chinook’s perfect knowledge—to any situation where there were 10 pieces or less on the board. That’s 39 trillion positions.
They continued improving Chinook’s “best-first” search strategy, which allowed them to do a fraction of the calculations necessary to compute every single possible play in the game. It took Schaeffer harnessing computers all over the world, drawing on and expanding his expertise in parallel computing. He conscripted machines everywhere from Switzerland to Lawrence Livermore National Laboratory, a major Department of Energy facility that often deals with nuclear weapons.
“There was somebody else there [running a program] called BOMB and I was running checkers programs,” Schaeffer told me. “It was a very strange situation. Security should have been concerned.” And they were. They paid him a visit after discovering gigabytes of data flowing out of a national lab to Edmonton, Alberta.
Through the years, the computers cranked away. As Samuel’s machines had before him. As future DeepMind machines would. This was a narrow kind of intelligence to develop, but it was part of the long arc of the development of artificial intelligence, which is expected to revolutionize the world within this generation.
Schaeffer saw what he was doing as the completion of Samuel’s initial dream. After his team’s success at the 1990 U.S. championships, he reached out to the old IBM man to share the news. The unhappy word came back: Samuel had just died, one of the oldest computer programmers still working. Born in Emporia, Kansas, in 1901, his last login to Stanford’s computer network was recorded in February of 1990. He’d seen the diffusion of electricity, the release of the Model T, two world wars, humans on the moon, and the very first glimmers of machine intelligence.
Finally, in 2007, Schaeffer was able to announce in Science that after working on checkers for 19 years, he had solved the game. The forward search had met the endgame database somewhere in the middle, like an AI transcontinental railroad, with the high-profile publication as Schaeffer’s golden spike. His team had figured out the sequences for 19 of the 300 tournament openings, but as it turned out, those 19 were all that were needed to prove that the game, played perfectly, amounts to a draw.
The game of checkers grinds on. The sport has been officially conquered by computers, but the wave of artificial intelligence has long moved on to more difficult challenges, leaving the humans to beat up on each other in places like the Honeysuckle Inn and Conference Center in Branson, Missouri. There are still tournaments and champions and even some prize money. There’s a group of young Italians who are challenging for global dominance.
Schaeffer thinks he’s laid checkers to rest himself. He’s working on a book about the history of computer chess that’s coming out later this year. He’s a dean at University of Alberta. “I’ve tried to move on and exorcise some of the ghosts of the story, but it keeps coming back,” he tells me. “I guess it will be part of me until the day I die.”
Before he does, though, he has one more checkers item on his to-do list. “I’d like to make a pilgrimage to Ohio and visit his grave,” Schaeffer said.
The grave is marked by a simple headstone: Marion F. Tinsley. In the upper right corner, there’s a checkerboard. In the upper left, a Scriptural reference, Hebrews 13:1: “Let brotherly love continue.”
Followed by: “Be not forgetful to entertain strangers: for thereby some have entertained angels unawares.” Imagine Schaeffer, once one of those strangers, completing his pilgrimage and looking down at this grave, as if down a well. For Tinsley, the spiritualist, the metaphor of checkers as a well without end was both poetic and true. But Schaeffer, the engineer, knew that no well is bottomless. And humans will always sound the depth.
* This article originally stated that the Chinook winds blow through Edmonton. We regret the error.