One Jump Ahead: Dallas Morning News

Eleven Steps Forward, Ten Back

reviewed by Chrilly Donninger
This is a quick translation of the original German review. Undoubtably some errors have crept in. Comments from the translator, Andreas Junghanns, are in brackets.

Jonathan Schaeffer belonged during the 80s to the elite of the computer chess world. His program Phoenix tied for first in the 1986 World Computer Chess Championships. Furthermore, he published a number of articles with important new ideas. On the side [in a colloquial tone, like you would say, " on the side he was also the Pres of the US"] he was also the treasurer of the ICCA and organizer of the 1989 World computer Chess Championship in Edmonton/Canada. "Ein Hansdampf in allen Computerschach-Gassen" [This is an adaptation of a German proverb that means somebody hyper-active, part of everything in town that is important or exciting. You should understand that as a compliment.]

Winnetou at Springer

[Winnetou is a main character in one of the, if not THE most important kids and teen literature by a German, Karl May. Practically EVERY German kid reads Karl May, about 25 percent go through a phase of May-ism, reading most of his 120 or so books.] 1989 he [J.S] changed his field. He developed the checkers program "Chinook". From the beginning, Chinook was designed to beat the human world champion. Jonathan now takes account of this project and the wrestling for the championship title with his book "OJA". Springer Verlag is associated with solid and dry science. Usually, you don't read a Springer book for the fun of it. But already after the introduction it was clear to me: this was not a Springer book, but a thrilling novel. When I got my first Karl May [revering to a book from Karl May] at age 8, I skipped two days of school and practically read the book in one sitting. With OJA I felt put back to that time. I laughed and cried, just like back then with Winnetou, with the heros.

Chinook started out innocently. Two colleges asked Jonathan what had happened to Arthur Samuel's checkers program.

An Innocent Question

Samuels program was the first game playing program on a higher level during the 60s. 1962 it beat Robert Nealy, a blind [meaning playing blind] checkers champion. Nealy had just overlooked a tactical combination the program had. This success was totally over-evaluated by Samuel's employer IBM and interestingly by the scientific literature. Schaeffer's funding requests were turned down with the reasoning that Samuel had solved that problem already in the 60s. In reality, Nealy belonged to the second class [With this German sentence, I could not have passed high school, it really does not make a lot of sense.]. On top, the following correspondence match was easily won by him. After Samuel retired, the project died and ever since haunts [yes, like a ghost :)] the scientific literature as a glowing example for the successes of artificial intelligence.

This innocent question was hitting fertile soil. Computer chess was not resulting in sleepless nights anymore for Schaeffer, his inner motivation [fire] had died after 10 years intense work. Furthermore, back then the Deep Thought/Deep Blue was hired by IBM. It was clear to him that as a lonely university assistant professor he could not compete with this kind of resources.

From Heroin to Cocaine

He had promised his girlfriend Steph that after the 1989 World Computer Chess Championship he would finally retire PHOENIX and spend more time with her. He kept the first part of his promise. But as soon as two days after the tournament the "beast", which was later for reasons of political correctness renamed to "Chinook", was born. Chinook is an Edmonton typical stream of warm air [Foen is used, something people know back home] that originates in the home area of the Chinook Indians.

Steph still did not leave him, on the contrary, they married. (Games-) programming is surely a serious addiction. A fit title for OJA could also have been: "Confession of a Computer-Junky". The endless work at a terminal is surely not healthy, but compared to alcohol or heroin it is destroying the body and mind of the addict relatively little. Why would someone marry somebody that heavily addicted? In my opinion, this addiction is does not just carry negative results. The knowledge about ones own addiction and the resulting feeling of guild gives the spouse a certain position of power. During the dry phases we [YES, "WE"!!!] are very caring husbands. On the trip, however, we are empty bodies and rather ugly to live with.

For example in a late phase of the project, Schaeffer was computing a 8-piece endgame database. This database was created during several months during the night hours on all available computers (up to 140) at the University Edmonton [!!]. During this period Schaeffer woke up at about 2am, logged into University from home to check if problems with one of the computers had happened. If everything was in order he could go to bed at 2:30am (where he could only remain till 6am), if not, he would drive to the university to solve the problem. After finishing the computation it took him a while to cancel the inner alarm clock for 2am. I know wives that would in similar situations get a separate bedroom. However, the addiction-literature knows the term of a co-addict. Simply put, these wives are addicted to live with an addict.

Things I don't know about can't worry me [(in-)famous German proverb] When Schaeffer gave birth to his monster, he had no idea about checkers, except the rules of the game. He played it the last time as a small boy. In chess he achieved master class strength as a junior. 10 years of computer chess had taught him: Too much and too complex knowledge is rather bad than useful for the playing strength of a program. The best methods are those that use no chess knowledge at all. For instance, the efficiency of a program depends very much from the probability if the best move is searched first in the search tree. Traditionally, the programmer tries to use domain-dependent knowledge to tackle that problem. Schaeffer's invention, the history heuristic is a primitive and at the same time much more effective than chess based methods. The program memories in a table for each possible move how often it was best. The search then orders all moves according to their history. The move that was best most often is searched first.

This and other techniques can immediately be put in any other game program. The evaluation function and the opening book will need a minimum of domain dependent knowledge. Schaeffer succeeded, after a few problems, to win the good checkers player Norman Treloar for the project. Norman cleaned in a first step the evaluation function of chessish things (e.g. center control is not very productive in checkers).

After only two months of development time participated Chinook in fall of 89 in the Computer Olympiad in London and won the checkers competition hands down. Even though other programs probably had more checker specific knowledge, they got tactically beaten by the methods developed for computer chess. As expected by Schaeffer, Chinook was now the strongest checkers program.

Mount Tinsley

After Schaeffer had stopped the expedition to Mt. Kasparow already on his way to the base camp, his new mount to be wrestle down was Mt. Tinsley. The dominating person in checkers was Dr. M. Tinsley. The mathematician and laymen-pastor [Prediger] had an unbelievable match record. In 40 years, from 1951 to 1991, he lost out of about 1000 tournament games a total of three. Until 95 2 more against Chinook would be added. In comparison, Capablanca had lost in 30 years out of 571 tournament games 43. Even with checkers being much closer to draw then chess, this is an unbelievable performance. On top of that, in the most widespread form, the three move ballot, the first three half moves are are drawn. Each player is then playing white and black in this "random" position. Even with openings analogous to 1.a4 d5 2.h4 - Tinsley could not be bent. In preparation for the first orld championship match in 1992 Schaeffer analyzed with Chinook more than 700 Tinsley-games for tactical mistakes. Chinook found within search depths of 17-20 no even a single tactical error. Out of pure curiosity tried the same with a few Morphy-games. That was rather funny. Some of the most beautiful combinations consist of a simple mate in 3 being converted into a long winning combination. The mistakes of his opponents where terrible. After finishing my new program Hydra I want to do the same with a few randomly selected Karpow - Kasparow games. I am sure that even today's players commit similarly horrible blunders.

Within these 40 years, Tinsley retired several times from the tournament play. Mathematics and the bible were equally important to him. He also suffered from his opponent's fear to loose and which made them play for a draw only. When Chinook appeared on the checkers scene, he reacted rather positive. Finally "somebody" who was playing fresh and without fear. At the beginning, Chinook had only a small opening book. The program was therefore quickly out of the known "worn paths". Even though Chinook was two levels weaker than him at the beginning, he knew that he had found a serious opponent after decades of absolute dominance. At the same time, he was still sure he could even beat that opponent.

The Dream of the Absolute Truth

Norm Treloar opened Jonathan Schaeffer eyes for the beauty and complexity of checkers when he showed him a few endgame positions that, in his opinion, should be part of Chinook's basic endgame knowledge. Those positions are (as far as I understood) full of switching Zugzwang moves. Even small variations change the result. The resulting lines are up to 50 ply deep and therefore not solvable with search. After ten years of computer chess, Schaeffer's reaction was clear: This is impossible to put into a program. Since those positions were taken from an introductory book, one could not argue those away with the standard argument "happens only once every hundred years".

The only realistic solution to the problem was an endgame database. In such a database, all possible positions for a certain piece constellation [yea, the German is really ugly here and doesn't do a good job explaining it!] are calculated using retrograde analysis. The program then accesses this database during the game. A checker can be on any of 32 squares. The size of the DB grows with the number of pieces to the power 32. The first realized DB was a 4 piece DB. 4 to the power of 32 is about 1 Million, one for modern computers modest number. In 1995, at the final phase of the project, the 8 piece DB was, under the before mentioned conditions, completed. One Tera (one thousand billion). The biggest data graveyard I know.

In this part of the game the knowledge of Chinook is perfect. The program regularly searches from the opening positions into this DB. In those games it is basically never playing a move it calculates itself.

The Perfect Autist

The giant 8 piece DB had a profound influence on the play. After the program could search directly from the middle game positions into the endgame DB, the percentage of lost games went down drastically. Chinook is still loosing more often then Tinsley. Strangely, the number of won games also went down. Out of a daring boy grew a boring drawer. How can this paradox be explained? All game playing programs use the minimax algorithm. They assume that the opponent will always play the best move. The assumption is that the opponent has the same knowledge as the program. With other words, if the program can search into the endgame DB, then it will assume that the opponent can do the same. With such a perfect opponent it doesn't make a difference if the program gears the game towards an 8 piece or a two piece ending. The program will even exchange pieces as long as the draw remains preserved. I know this problem well from my own experience. A short while ago, a lightly agitated Nimzo user was sending me an endgame with two blocked pawns. For this endgame and for KPK Nimzo has an endgame DB. Even though Nimzo could capture the opposing pawn, it refused the pray and then got its own pawn captured before it reached a draw. From a human perspective, this game was perverse, from the point of view of a perfect program, it was perfectly logical. A draw is a draw, there is no benefit in making a perfect opponent work hard.

The perfect Chinook eases through similar play its non-perfect opponents systematically the survival. Schaeffer tried several tricks to solve this fundamental problem. However, he could not find a real remedy.

Pets

In a mixture of caring and hate, we call a program error a bug. When we are looking for errors, we are "debugging". Each programmer has his own collection of bugs.

Two threads can be found throughout the Schaeffer's book. The guilt towards his wife Steph and his constant struggle with bugs.

Chess player argue that programs are dumb and fantasy-less [-laking], but mechanically perfect monsters. Schaeffer is debunking this myth completely. Programs are complex structures build by humans and therefore every thing else but perfect. Each chess and checkers program contains certainly a few dozen major and a few hundred minor bugs. Even in more important programs, such as controls for thermo-nuclear power plants, it is no different. These bugs are often hidden for years and wait usually for an important moment to appear. Schaeffer used the time control of Phoenix for Chinook. This part of the program was working for almost 10 years for hundreds of games without problems. In a qualification match for the Tinsley challenge, Chinook lost an important game by forfeit on time because of a bug in this part of the program.

This species of phantom bugs is especially nasty and feared. The program is behaving obviously buggy. At home one tries to recreate the problem. The program works just fine. A bug that is not appearing can practically not be found and fixed. Usually, this bug is then reappearing later and is then again irreproducible. Often, the reason for the bug is a combination of many circumstances, e.g. the response time of the opponent that cannot be reproduced exactly.

Schaeffer hunted for over a year one such dangerous phantom bug. The existence of a phantom bug can drive a games programmer shortly before an important tournament close to insanity. During the development of Nimzo 3 an apparent phantom bug was visible. The program was winning a queen in a pawn endgame and lost it shortly afterwards for no apparent reason.

This bug was haunting me for months and was also during the Aegon tournament 96 still not fixed. In the sixth round, the strong GM Yona Kosashvili blew the pawn endgame. Nimzo promoted a queen and Yona did not resign. The first victory against a GM in sight I am sitting on the back of my chair and am asking the "queen-return" bug not to strike. This time fate has mercy. Kosashvili resigned soon thereafter and the bug remains invisible. A few spectators are wondering how one can be so nervous in such a won position. After this nightmare, I hunted the bug for weeks and fixed it.

A truly nasty species of bug is the "Don't-get-upset" bug [This is a famous German past time for kids, a brainless board game that consists of rolling the dies and kicking somebody else's pieces off the board - I was never a fan of it - because I always got upset! :)]. This species of bug stroke in the Chinook project during the calculation of the 8 piece DB. After months of calculation and many sleepless nights, an error was detected in one part of the seven piece DB. A few thousand of some billion positions were wrong. At a piece exchange, the already calculated smaller DBs are used. The error propagated to the 8 piece DB. In such a situation the only thing to do is: back to the start. Jonathan marked in his log [probably meaning your programmer's log]: 11 steps forward, 10 back.

Match 1

In 1992, after a few quarrels with the Checkers federation, the first world championship match Tinsley against Chinook started. First, the federation did not want to accept the match as an official world championship match. When Tinsley resigned from his title and checkers, both parties agreed to a compromise. The match Tinsley-Chinook would be for the new title: man-machine world champion. Distributed over 10 days, 40 games were played. The for chess rather high number of games per day is normal for checkers. At least two games must be played because of the random choice of openings. Otherwise the player playing the strong side as the second would have an advantage in analyzing [over night]. Many games in the drawish and thoroughly analyzed openings end in a human- human match in a quick GM like draw. That then still daring Chinook had no idea about GM draws. The unusually long games tiered Tinsley, born 1927. Nevertheless, he remained on top with a score of 4-2. His human opponents most often where sent home with a 10-0 score.

With this, the apatite of the now to half a dozen members grown Chinook team wasn't satisfied. With the help of even bigger DBs, better search, more checker knowledge and not at last with fixing of a few more bugs, Mt. Tinsley was still to be wrestled down.

Match 2

Tinsley as well like the fight and his role as a defender of the human race. The price-money was with 10 thousand dollar, in comparison with the Kasparow match, a handful of peanuts. And still, this was by far the biggest price money he had ever fought for.

They agreed to rematch in fall 1994. The venue of the match was the famous computer museum in Boston.

One should not tell the end of a thriller. Lets just say, the story ends like Winnetou 3 [If I remember correctly, Winnetou dies a heroic death and all the gold goes down the drain :)]. At that part of the book, my wife asked me, why am I not laughing anymore.

The Moral of the Story

Chinook was a [?] project in which I would have liked to be a part of. Each who would like to know what happens behind the scene of such a project and who would like to have a peek into the souls of the programmers I can only highly recommend this book. Despite the competition, Tinsley and Schaeffer liked each other. This book is as well the story of a friendship between two men. Checker knowledge is an asset, but not necessary for the understanding of the content of the book. The book is written in English but I had to use the dictionary only a few times. It is a pleasure to read.

University of Alberta

Computing Science