Man vs Machine: the legacy of Marion Tinsley

Who was Marion Tinsley? Nothing more and nothing less than the greatest player of checkers - a 5,000-year-old game that almost everyone knows how to play but only a few thousand people compete in seriously- in history. Tinsley was born in Ironton, a small town in Ohio, on February 3, 1927, and, like many residents of the American Midwest, learned to play checkers at an early age. It is said that as a child he did not show anything extraordinary on the board, and his first great rival was Mrs. Kershaw, an old woman who defeated him repeatedly accompanying each victory with laughter and mockery. Young Marion, now 14, was upset by his lack of progress in the game, and it was by chance that, while looking for a math book in the local library, he came across two books on the game of checkers. From then on, Marion alternated studying the game with her other two passions; the study of the Bible and the study of mathematics.

At age 27, Tinsley began his final ascent to the world champion title by triumphing in the American Checkers Federation (ACF) tournament and defeating Asa Long and Walter Hellman in two matches. In 1958 he was recognized as a world champion by defeating the English champion, Derek Oldbury with a resounding result of nine wins, one loss and twenty-four draws. After these successes, Tinsley renounced the world title and dedicated himself to his work as a mathematics professor at the University of Florida, since he considered that there were no longer challenges that motivated him to continue competing.

In 1970, Tinsley made his comeback at the ACF national tournament held in Houston, winning it easily, a success he repeated in the 1974 championship. This allowed him to challenge Elbert Lane Lowder for the world title in 1975, defeating him without appeal. Following these events, Tinsley began his second retirement, although he made occasional appearances at major tournaments while giving instructions to a select group of disciples. One of them, Don Lafferty, challenged his teacher in 1989, winning Tinsley by two wins without losses and thirty-six draws.

While Tinsley hammered at every human rival dared to oppose him, an artificial intelligence research program was advancing how to solve the game of checkers. In 1989, a group at the University of Alberta, Canada, launched a draft resolution focused on a program called Chinook. The main challenge for solving a game lies in its “complexity”. The complexity, in turn, comes from two sources, the first is the decision complexity, which includes the difficulties for a program to generate good plays, and the second is the state-space complexity, which is the number of legal game positions reachable from the initial position of the game and refers to the size of the search space. In the case of checkers, the state-space complexity is of the order of 10²⁰, which makes it more complex than Backgammon (10¹⁹), but less complex than Xiangqi (10⁴⁰), Chess (10⁵⁰), Shogi (10⁷¹) and Go (10¹⁷⁰). A key element in the possibilities of solving the game of checkers is working from the simplest positions since usually the exchange of pieces tends to make most of the possible games end in relatively simple positions. Once resolved, these simple positions are archived in databases and can be used by Chinook to "know" how to settle a game without the need to recalculate.

By 1989, Chinook had a database with all the possible combinations of 4 pieces or less, which translated into seven million solved positions; that year the program was crowned champion of the Computer Olympiad. The following year, with a database of positions solved for six pieces or less (which involved the number of 2.7 billion positions), Chinook won the Mississippi state championship, then placed second in the U.S. championship, despite being undefeated and drawing the four games it played with who in the end became champion: Marion Tinsley.

According to the rules, Chinook had earned the right to challenge Tinsley for the title of world champion, but the ACF and the EDA (English Draughts Association) refused to validate a program as a challenger. Marion Tinsley, who had found a motivation to play at her best, gave up her title in 1992 and agreed to play a match with Chinook. The maneuver forced the ACF and the EDA to create a new title, the men's and machine championship, to participate in the match.

Tinsley, who was also the pastor of the Baptist church, declared before the match that he was going to win because “I'm sure I have a better programmer than Chinook. God has given me a rational mind”. The match began on August 17, 1992, in London with Tinsley driving the white men. Before this encounter, Tinsley had been defeated only 3 times since 1948.

According to the programmers, having a new database for seven pieces or less (with thirty-seven billion positions), helped Chinook to successfully resist the pressure exerted by Tinsley. Three quick draws followed, until in the fifth game the world champion won his first victory, masterfully exploiting the weakness of the two black tiles (at 7 and 11) that were mercilessly besieged by Tinsley's two crowned tiles until one of they fell; and then in the seventh, he also had a decisive advantage, but allowed Chinook to escape. When everything indicated that the world champion would win the match, Chinook won games 8 and 14, and for the first time since 1958, Marion Tinsley had to come from behind to win.

To understand what happened next, we must remember the phrase Tinsley said before the match. Chinook programmers are human, and as such they are wrong. In Game 18, the computer crashed, and, in a difficult position, Chinook ended up running out of time! Then, in game twenty-five, Tinsley, through a reversal of moves, removed Chinook from his "opening book," which meant that he made a couple of mistakes that were decisive. With a point advantage, Tinsley only had to draw the rest of the games and thus win the match. The moment of truth came with game 39, the last of the match. Chinook's chief programmer, Jonathan Schaeffer, says that before the opening draw, he was mentally asking: "Let the White Doctor come out," which happened. This opening was analyzed extensively by Marion Tinsley in one of her books, where she proposes the sacrifice of a man as the only way for Black to survive. After the sacrifice, the program evaluated that he had a great advantage, but after several plays, the evaluation was adjusted until it showed a parity, which later evolved into a decisive advantage for Tinsley.

Tinsley was proclaimed the winner of the match with four wins, two losses and thirty-three draws. How was it possible that the man won against the machine? The explanation that Tinsley offered, now speaking as a mathematician, is that between the twenty moves ahead that the machine could calculate and the database of simple positions there was a "dark area" where the limitations of the program could not guarantee reaching winning positions. Hence, he tried to generate positions where the complexity of the decision was so great that made the dark zone a dangerous place for Chinook. Why was this area not so dangerous for Tinsley? The only thing I can say is that he, I don't know how or why was able "to see the best moves".

The team of Chinook programmers negotiated a new match for two years while improving the weaponry of the contender for the title: the calculation capacity was increased from 20 to 29 moves forward, the opening book was expanded and refined, and the simple positions database now had all the possibilities of 8 pieces or less (440 billion positions). In 1994 Tinsley and Chinook met again in Boston, but the match was interrupted after four draws because Tinsley got sick. As Tinsley cannot continue playing, Chinook was declared the winner of the match. Immediately, Tinsley's strongest disciple, Don Lafferty, challenged Chinook to a match that ended in a draw, allowing Chinook to retain the title. Lafferty once again challenged the man-vs-machine champion in 1995, but this time he was defeated by the machine.

Marion Tinsley died on April 3, 1995, in Houston. His body lost the final battle against formidable enemies: sickness, old age, and death; but Tinsley left this world without being defeated on the board. The Chinook team of programmers has continued to work on the resolution of the game of Checkers, and their first major announcement (2005) was the demonstration that the White Doctor opening, the same one played in the decisive game of the 1992 match, ends in a tie if both sides play the best strategies.