How did the checkers decide

The story of a duel between two people, one of whom is dying, and the search for a way to create artificial intelligence

Marion Tinsley - a professor of mathematics, a priest, the best drafts player in the world - was sitting at a table opposite the computer and was dying.

For 40 years, Tinsley held the championship in checkers, and during this time he lost several games to people, but never lost the match. It is possible that in no competitive discipline was there such a champion as Tinsley was in checkers. But this competition was different - the world championship between man and machine.

His opponent was Chinook , a checker program created by Jonathan Schaeffer , a curly-haired man with puffy professorship at the University of Alberta. That day he drove a car. Thanks to the manic work on Chinook, she became a very good player. She has not lost a single game in her last 125 games - and since they came close to defeating Tinsley in 1992, Schaeffer and the team spent thousands of hours improving the program.

On the eve of the match, Tinsley dreamed that God spoke to him and told him: “I like Jonathan too,” which led him to think that he had lost exclusive support from above.

And so they sat in the Boston Computer Museum, now no longer functioning. The room was large, but there were only a few dozen people. Two people planned to play 30 matches over the next two weeks. It was 1994, when there were no games of Garry Kasparov and Deep Blue, or Lee Sedol and AlphaGo.

Contemporaries described this event as the battle of man and machine, the cunning human mind and the brute computing power of a supercomputer. But Tinsley and Schaeffer agreed that it was a battle between two men who prepared and set up a unique tool for defeating an opponent. So long prevailing over human rivals, Tinsley was looking forward to a match with an entity that could be played properly. He volunteered to participate in friendly matches, to warm up before two matches for the world championship. Schaeffer, although he was stubborn, became the most effective promoter of Tinsley’s art and heritage.

But in that room, Tinsley was pestering the features of human development. His stomach hurt. The pain kept him awake all night. After six games - all draws - he had to see a doctor. Schaeffer drove him to the hospital. He escaped with the Maalox. But the next day, on an X-ray, they saw a tumor in the pancreas. Tinsley realized his fate.

He recused himself. "Chinook" was the first computer program in history to win the world championship in humans. But Schaeffer was depressed. He devoted years of his life to creating a program that could beat the best drafts player, and as soon as he was ready to realize his dream, Tinsley left the game. A few months later, Tinsley died without losing the Shinuku match.

As a result, Schaeffer embarked on a 13-year-old odyssey to expel a human ghost. Without Tinsley, the only way to prove that Chinook could defeat him was to find a way to defeat the game itself. He will publish the results on July 19, 2007, in the journal Science, with the title: " Checkers resolved ."

“After the end of the Tinsley saga in 94-95, until 2007, as an obsessed person, I worked on creating the perfect program for drafts,” Schaeffer told me. “The reason was simple: I wanted to get rid of the ghost of Marion Tinsley.” They said to me: "You could not beat Tinsley, because he was perfect." Well, yes, we would defeat Tinsley because he was almost perfect. But my computer program is perfect. ”

* * *

Jonathan Schaeffer did not begin his career with the intention of solving checkers. At first he played chess. Good, but not brilliant. He also loved computers, and received his doctorate in computer science, so he decided to write a program that plays chess. He called it “Phoenix,” and she was one of the best among many chess programs written in the 80s. However, in 1989 at the world championship for computers playing chess, it failed miserably. At the same time, a team began to assemble that would create DeepBlue, a chess software that could defeat Kasparov. Schaeffer realized that he would never succeed in creating a world computer champion.

A colleague suggested he try drafts instead - and after only a few months of work, his software was already good enough to go to the computer Olympiad in London and compete with other drafts bots. It was there that he began to learn the story of Marion Tinsley, the greatest.

At the highest levels, checkers is a game of intellectual exhaustion. Most games come down to a draw. In serious matches, players do not start from standard positions. For them, a debut is randomly selected after three moves from the set of approved ones, which gives a slight advantage to one or another player. They play it, then change colors. The main way to lose is to make a mistake that the opponent grasps at.

Apparently, checkers should easily obey the computer. This idea hovered back in the mid-1950s, when an IBM researcher, Arthur Samuel , began experimenting with programs playing checkers on the IBM 704. He worked on this problem for the next 15 years, published several important scientific papers on the discipline he called "Machine learning."

MO is the basic concept of the modern wave of AI. The descendants of that early work today promise to revolutionize entire industries and labor markets. But Samuel’s programs weren’t successful in matches with human opponents. In May 1958, several members of the Endicot Johnson Corporation Drafts and Chess Club defeated a computer, to the delight of the Binghamton Press and Sun-Bulletin newspapers.

“The human brain, sometimes lost in the era of satellites, frozen food, and electronic data processing machines, has now returned to its former splendor,” the newspaper said. - 704th, according to Dr. Samuel, does not think. He searches the “memory”, stored on the film, of the checkerboard positions he met earlier. Then he rejects the elections, which ended badly for him in the past, and makes moves that in the past led to success. ”

It still describes the concept of reinforcement learning well.", one of the MO technologies that has revived the field of AI in recent years. One of the authors of the book on this topic," Reinforcement Learning ", Rich Sutton, called Samuel's study" the earliest "of the works" today regarded as directly related "to modern development AI: Sutton is also among Schaeffer's colleagues at the University of Alberta, where, according to a recent announcement, Google’s DeepMind AI Lab will open its first international research center .

Although his technology was revolutionary, Samuel, in his own words, made “limited progress” over 10 years, although he continued to work on it at IBM, peering at the Massachusetts Institute of Technology, and then receiving a grant from the Department of Defense at Stanford University. As is the case with many of today's unusual AI technologies, he simply did not have enough computing power or data sets to make his great ideas work.

So when Schaeffer began creating his own software, he returned to Samuel’s work and found that he couldn’t take this path. He needed to do everything from scratch. At first they called the project "The Beast", but as a result they came to the name "Chinook", which is called the warm winds blowing in the Canadian province of Alberta.

Work captured Scheffer. As he described it in a 1997 book: "Sometimes, when it was hard for me to fall asleep, I imagined the excitement that would seize me when Chinook finally defeated the Terrible Tinsley." His wife interrupted his thoughtfulness with the words: "Do you think about him there again?"

Over the years, the program has grown, retaining two key components. The first is easy to understand - this is a “book” of complete calculations of all possible positions in checkers with a certain, small number of checkers on the board. So, if there are only six checkers left on the board - and over time they got to seven, and then to eight - all the possible combinations became known by Schaeffer's software. In the early 90s, for these calculations, huge computing power was needed at that time.

But the more calculations Schaeffer did with the team, the better Chinook became. He had the opportunity to beat people. But they knew that they were not able to calculate all possible positions.

The rules of checkers are simple [American - approx. transl.], but the number of potential moves is huge - 5 x 10 ²⁰ . Schaeffer has a good analogy that helps to imagine the absurdity of the situation: imagine that we drained the Pacific Ocean, and now we need to fill it with a small cup. Then it just turns out that the whole ocean is the number of possible positions.

The second component of the system is more difficult to understand. “Chinook” needed to be able to look for possible moves, starting from the beginning of the match. Like many similar programs, “Chinook” looks ahead to many moves and tries to calculate the desirability of each option. At first, “Chinook” could look only 14-15 moves forward, but with the improvement of computers and software, he looked further and further. “As with chess, deeper always means better,” says Schaeffer.

In the late 1990s, the American Drafts Federation allowed Chinook to play in the American Championship. PO did not know defeats and tied with Tinsley six times. This earned the right for the software to compete against Tinsley in the world championship.

After the Chinook performance, Tinsley called Jonathan Schaeffer and asked if he could play some friendly matches.

* * *

From 1950 to 1990, Tinsley was the world champion in drafts every time he was interested. Sometimes he retired to work on mathematics or study religious issues, but as a result he returned, beat everyone and became the champion again. Over 40 years, in total, he lost five games and never dropped out of the match.

Derek Oldbury, arguably the second best player of all time, wrote a drafts encyclopedia. In it, he unrestrainedly glorified the master: "Marion Tinsley in checkers - like Leonardo da Vinci in science, like Michelangelo in art, like Beethoven in music."


Marion Tinsley, 1974

It is difficult to evaluate Tinsley from the perspective of the 21st century. He seems an alien from another world, or from another time. His life consisted of checkers, mathematics and faith. He was kind, but his style of play was ruthless and aggressive.

It is often said that someone “lived with the mind”, but in the case of Tinsley, both life and mind were unusual. For years, first as a student, and then a graduate student at Ohio State University, he spent eight hours a day playing drafts. He has never been married. “I never saw a marriage and checkers get along, ” he told a reporter . “A rare woman can marry a true follower of drafts.” His mother lived with him until the 1980s. In 1993, The Philadelphia Inquirer described Tinsley's clothing as a large blue sweater worn over a shirt and tie. Lunch was served with a "jug of milk, half an apple and a peanut butter sandwich."

His attitude to the racial issues of the South was also surprising. “I was thinking of going to Africa and becoming a missionary,” he told Sports Illustrated.in 1992, - and then a black woman with a long tongue told me that most people who wanted to help blacks in Africa do not even speak with blacks in America. ”

As a result, he became a priest in a predominantly Negro church and quit his job at the math department of Florida State University to teach at the historically Negro Florida University of Agriculture and Engineering. There he spent 26 years. The photo album, dated one of the last years of his work there, shows the busy life of the student campus, in which Tinsley was probably the only white man over 40. There were no students' opinions about his professor, the drafts champion, but his colleague described the role of Tinsley in local obituary: "At the dinner in honor of the resignation, literally everything: old, young, black, white, students, employees of the institute ... told how he influenced their lives." For a man of his time, who grew up in pieces. Kentucky, his life path looks very amazing.

One thing is clear: Tinsley was a genius. His genius was honed and framed in something strange and wonderful. He was the best in this single area, and average in everything else. One part of it has become similar to AI - highly specialized, but extremely skillful - and everyone else lived a simple human life.

When a reporter visited him in 1993 in Tallahassee, he saw in his section a path leading to a two-story brick house framed by lavender azaleas. In the room on the second floor there was a board for drafts and read books on drafts. Tinsley liked to sit in a velor armchair brand La-Z-Boy. He could not explain what checkers meant to him - why he had studied the sequence of moves all his life, why he kept a magnetic board near the bed to practice new combinations. It was something close to divine.

“Checkers is a deep, simple, elegant game,” he once said. And another time he noted that playing with another good player is like “two artists working together on a work of art”.

There is his most popular quote: "Chess is like observing a vast, endless ocean, and checkers are like looking into a bottomless well."

As if the moves in checkers for him were quotes from the Holy Scriptures, over which he could meditate endlessly and understand in a new way. “Suddenly, out of nowhere, an improvement in a published game might come to mind, as if the subconscious was working on it, ” he told the Chicago Tribune in 1985. “Many of my discoveries appear in this way, out of nowhere.” Some of my insights regarding Scripture appear in the same way. ”

* * *

When Tinsley arrived in Edmonton in 1991 to have friendly matches with Chinook, Schaeffer was amazed that the world champion agreed to play with his computer just for fun.

Two men settled in his office and the matches began. Schaeffer went for "Chinook", and entered the moves in the system. The first nine games ended in a draw. In the tenth game, “Chinook” worked, as usual, tracking moves 16-17 steps forward. He made a move in which he should have had a slight advantage. “Tinsley immediately said, 'You will regret it,'” Schaeffer says. “At that time, I thought, how the hell did he know what could go wrong?” But in fact, from that moment, Tinsley began to win. “In his notes on this game, he later wrote that he foresaw all the moves until the very end of the game and knew that he would win,” Schaeffer wrote.

This moment has sunk into the memory of the programmer. After the match, he ran simulations to figure out what went wrong. He found that from that move to the end of the game, if both sides played perfectly, the computer would still lose. And his next discovery stunned him: in order to understand this, a computer or a person would have to calculate 64 moves ahead.

“I was just shocked,” Schaeffer told me. “How can one compete with someone whose understanding of the game is so deep that he will immediately win, thanks to experience or knowledge, or some kind of amazing search?”

Schaeffer is still trying to figure out Tinsley's incredible skill. When he wrote his book about this story, “One Jump Ahead,” he received a letter from a professor who oversaw Tinsley during his studies. According to Schaeffer, it was written there that “he was an exceptionally talented person and capable of one brilliant thing. And these were not checkers; he would probably be a brilliant mathematician. ”

When a person’s motivation is not fame or money, we apparently need some explanation of his actions at a higher level, the search for some kind of emotional engine that everyone else does not have. Tinsley best described his motivation in an article in the 1993 Philadelphia Inquirer. He was an introvert who “didn’t feel the love” of his parents, who he believed focused on his sister. To win their approval, he participated in competitions in mathematics and spelling. “And, like a curved, but growing branch, I grew up and continued to feel exactly the same.”

* * * The

need to be exceptional encouraged Tinsley to go to college at age 15, where he met with a passion that would dominate his life. He won his first international title in 1955.

And in 1992, he agreed to stake his champion title in the first international championship of people and cars against Shinuk. The match, held in London, was sponsored by Silicon Graphics. “I can win,” Tinsley told The Independent. “My programmer was better than Shinuk. He had Jonathan, and I have the Lord. ”

Two weeks before the event, another world-class player, Don Lafferty, trained with him in Tallahassee, discussing matches and redefining positions until late at night.

The games of 1992 were held at the Park Lane Hotel, which hosted international chess championships, as well as the computer olympiad, which became Shinuk's debut two years ago. The room was large and two-story, with a balcony from which the players could be seen, and with a computer the size of a refrigerator on which Shinuk worked.

Schaeffer and Tinsley sat opposite each other, and the movements of the figures were depicted on the big screen. Tinsley got his first blood, beating Chinook in the fifth game. But in the eighth game, “Chinook” pulled out a terrific victory - this was Tinsley’s sixth defeat in 40 years.

Despite years of hard work and dreams of success, Schaeffer at that moment felt sad. “We are still members of the human race,” he wrote in his book, “and the fact that Chinook defeated Tinsley in one game means that the advantage of computers in checkers and then in other games is only a matter of time.” Schaeffer may have won, but humanity has lost.

After a series of draws, Chinook won again in the 16th game. Not a single live player beat Tinsley twice. Surprisingly, and almost unbelievably - but the software was ahead of man. They were on the verge of creating a computer story.

Then an event occurred that Schaeffer was still pained to describe. “Shinuk” had some kind of mistake, because of which it was necessary to leave the game. “Tinsley decided that God was helping him,” Schaeffer said. “It was a religious experience for Tinsley, and one of the most devastating moments of my life.”

Schaeffer and Chinook were unable to defeat the man again. Tinsley won the match and retained his title.

“If my health doesn’t fail me, I don’t think there will be a computer that can beat me,” Tinsley told CNN after the match.

* * *

And all this led to the 1994 meeting in Boston.

First, “Chinook” was played by Derek Oldbury and beat him. Soon after, Oldbury died. Chinook is playing with Oldbury. "Chinook" beat Oldbury. Oldbury is dying, ”Tinsley joked in an interview with Schaeffer. “He probably died of shinukita!”

But Schaeffer was not funny. He was a young man who programmed computers, playing the game of the elderly. The best players were dying out. And, from the point of view of some representatives of the world of drafts, it was not fitting for this youth with his fashionable to beat weak masters with machines and code.

Growing up, Schaeffer thought that he would like to know Tinsley better while they talked. “I recall the time spent with Marion Tinsley. Then I did not realize how fast it would fly and how I would like it. I did not take advantage of this, did not reap the benefits of our warm and deep friendship with him, ”he told me. - I remember, and with a back mind I can say that I am disappointed with myself. I would like to do things differently, but at a time when you are obsessed, you can only see in one direction. ”

Even talking about how he drove Tinsley to the hospital, Schaeffer cannot get rid of the idea that the old man’s illness could prevent him from winning. Tinsley says, “I'm ready to leave,” and Schaeffer remains confused. The old man knew that he was dying, but the young man did not understand this.

After Tinsley’s withdrawal, Don Lafferty took his place and fought with the computer, but Schaeffer was focused on a larger prize, on solving drafts. Schaeffer claims that checkers began to despise him. They sent him letters scolding him and his software. He released the book “One Leap Ahead” in 1997, and still the drafts players continued to attack him.

From 1997 to 2001, he suspended work on a project involving the creation of a computer program that always knew which step would be right. Such a program should become invincible. Perfect.

When he returned to him, his team expanded the database of game endings - the perfect knowledge of Shinuk - to any situation in which there were no more than ten pieces on the board. This is 39 trillion positions.

They continued to improve the “Chinook” search strategy, allowing them to perform a small fraction of the calculations necessary to calculate all the possible positions in the game. Sheffer had to use computers from around the world, learn parallel computing. He assembled cars from everywhere, from Switzerland to the Lawrence Livermore National Laboratory, a core set of equipment owned by the Department of Energy that often counts simulations of nuclear weapons.

“There someone else had a program called BOMB, and I ran drafts programs,” Schaeffer told me. - It was very strange. The security service should have been interested in this. ” They are also interested. They came to him with questions, finding that gigabytes of data were coming from a national laboratory to the city of Edmonton, Alberta.

For years, computers worked like Samuel's machines did before them. How will DeepMind machines work. These intellectual skills were highly specialized, but they were part of a long history of the development of AI, which should revolutionize the life of the current generation.

Schaeffer believed that his work was the completion of Samuel's original dream. After a success at the US Championship in 1990, he contacted an old IBM sheep to share news with him. But got the bad news: Samuel recently died. He was one of the oldest programmers still working. He was born in Emporia, Kansas, in 1901, and last logged onto the Stanford computer network in February 1990. He witnessed the spread of electricity, the release of Model T, two world wars, the flight of man into space and the first signs of machine intelligence.

Finally, in 2007, Schaeffer was able to proclaim in the journal Science that after working on checkers for 19 years, he decided this game. A direct search met a database of game endings somewhere in the middle, like the AI ​​transcontinental railway, the publication of which became the golden crutch. His team processed sequences for 19 of the 300 tournament openings, but it turned out that these 19 were enough to prove that the game, played perfectly, ends in a draw.

* * *

Checkers continue to live. The sport was officially conquered by computers, but the wave of AI has since shifted to more complex tasks, and left people fighting each other in places like the Hanisacle Inn or the Conferences Center in Branson, Missouri. Tournaments and championships are held, cash prizes are given out. A group of young Italians strives for world domination.

Schaeffer believes that he put the checkers aside. He is working on a computer chess history book that will be released later this year. He is dean at the University of Alberta. “I tried to move on, to expel some ghosts from history, but they keep coming back,” he tells me. “They'll probably be part of me until I die.”

But until that moment he has one more unfinished task from the field of drafts. “I would like to make a pilgrimage to Ohio and see his grave,” says Schaeffer.

The grave is marked with a simple tombstone: Marion F. Tinsley. In the upper right corner is a chessboard. In the upper left - a passage from the Scripture, "Hebrews 13:11: Brotherly love between you abides." And further: “Don’t forget the strange love, because through it some, not knowing, provided hospitality to the Angels” [love for strangers - approx. transl.].

Imagine Schaeffer, who was once one of those strangers, completing his pilgrimage and looking down at this grave, as if in a well. For Tinsley, a spiritualist, the metaphor of checkers as a well without a bottom was poetic and truthful. But Schaeffer, an engineer, knows that there are no bottomless wells. And people will always proclaim their depth.