(Game-)tree searcher search

My efforts to document the 1970 computer chess tournament – the first such event in our 52-year history of game competitions (Schaeffer, 2020) – kindled an interest in connecting with the pioneers of computer chess. We all concentrate on the recent developments in our field and the researchers who are making progress. With the passage of time perhaps we do not fully appreciate the contributions of our predecessors.

On a recent trip to California, I was able to meetup with two of the pioneers of computer chess: Monroe (Monty) Newborn and Ken Thompson. For these game-tree searchers, computer chess was their passion for many years, and remains an important part of their lives today.

Monty Newborn was one of the organizers of the 1970 computer chess championship (see Fig. 1). With his program Ostrich (named because of the program’s seemingly cowardly play at times), he competed in numerous North American Championships (1972–75, 1977–82, 1984–87) and in the first five World Computer Chess Championships (1974, 1977, 1980, 1983, and 1986). From 1970 to 1997, Monty was the driving force behind organizing the North American Championships and played a key role in the Kasparov-Deep Blue matches. He is a co-founder of the ICGA and served as President from 1983–1986. He is a prolific author including popular books Computer Chess (Newborn, 1975) – my introduction to computer chess programming, Deep Blue: Computer Chess Comes of Age (Newborn, 2003), and Beyond Deep Blue: Chess in the Stratosphere (Newborn, 2011).

Fig. 1.

Yesterday – big trees to search. Seated from left to right: Don Beal (computer chess researcher), Ken Thompson, Monty Newborn, and Mikhail Botvinnik (former World Chess Champion). World Computer Chess Championship, New York, November 1983. Photo gifted to the Computer History Museum by Monty Newborn.

After many years as a Professor of Computer Science at McGill University (Montreal, Canada), Monty retired to Woodland, near Sacramento, California.

Ken Thompson (see Fig. 1) started off with a software-only chess program (T. Belle; Thompson’s Belle or Tinkerbelle, named after his employer Bell Telephone Laboratories), but realized that chess strength was correlated with computing horsepower. This principal was simply and elegantly demonstrated in his important paper “Computer Chess Strength” (Thompson, 1982). The consequence was that Ken worked on several iterations of building chess hardware. The final result, Belle (Condon and Thompson, 1982), was recognized in 1983 as the first chess machine to achieve the Master’s title (United States Chess Federation). Ken’s software/hardware programs/machines were frequent competitors in the North American Championships (1973–74, 1978–1982, 1984–87, and 1990, winning in 1978, 1980–1982, and 1986) and the World Computer Chess Championships (1977, 1980, and 1983, winning in 1980). The Belle design was the inspiration for the architecture of Deep Blue.

Ken was the first to realize the potential of building endgame tablebases. In 1977 he demonstrated the strength of tablebases by frustrating Grandmaster Walter Browne with a staunch defence in the KQKR endgame. Ken was first to compute all the five-piece endgames.

While Monty likes to write books, Ken loves to write code. Of course, he is internationally known for creating the UNIX operating system, for which he and colleague Dennis Ritchie received the Turing Award (computing science’s equivalent of the Nobel Prize). He is also well known for his work on regular expressions (which became integral in UNIX), the B programming language (the predecessor of C), the Plan-9 operating system, the UTF-8 encoding system, and the Go (Golang) programming language. With all these other activities, it’s amazing that Ken found time for computer chess.

After many decades working at Bell Telephone Labs (New Jersey), in 2006 Ken moved to Google (California). Today he is retired, living two hours north of San Francisco. He continues to design and implement state-of-the-art systems and, yes, even writes programs related to chess.

Having computers play chess at a superhuman level is one of the early triumphs in the history of artificial intelligence research. Through their words and code, Monty and Ken were critical to achieving this milestone (see Fig. 2).

Note: This short article was fact checked using books written by Monty. The paper was written using an operating system and text-processing tools that are modern re-implementations of software written by Ken.

Fig. 2.

Today – searching for big trees. Left to right: Ken Thompson, Monty Newborn, and Jonathan Schaeffer. Gualala River Redwood Park, June 2022. Photo taken by Jennifer Schaeffer.