Pitting Computers Against Each Other . . . in Chess

September 18, 2020 https://bit.ly/35Nc1SS

For those of us involved in programming computers to play chess, it has been a great adventure. ACM annual tournaments began in 1970 (50 years ago!) and were hosted year after year for a quarter-century by the organization. They were terrific catalysts for progress in the field, and deserve major credit for the eventual 1997 defeat of then-World Champion Garry Kasparov.

I feel human intelligence has been vastly overrated. We humans haven't learned how not to fight wars over various explanations of how the universe or man came into being. The telescope that allows us to peer into the universe at 1,000,000,000,000,000,000,000 stars is only 400 years old. Women were burned alive as witches only 300 years ago. With the universe in existence for 14.7 billion years, the Earth in existence for 4.6 billion years, and humans in existence for several million years, there is an excellent chance at least one of those stars may now and/or in the past have supported some sort of intelligent life. I suspect there might be creatures far more advanced than Earthlings. One of the great disappointments of my life is that we have not made greater efforts to explore the universe, especially our Moon and Mars.

Historically, there have been arguments supporting the belief the animals of this planet do not possess the mental capabilities of humans. They were not thought to be able to use tools to solve problems, and they were not thought to be able to recognize themselves in a mirror. More and more, we find animals are more intelligent than they have been given credit for.

Researchers in the field decided in the 1940s that chess was the task over which human intelligence might be studied. The definition of intelligence, of course, is problematic. How do we say someone is more intelligent than someone else? Chess provides an environment to study this. Ratings are assigned to chess players based on their performance against opposition. If one person consistently defeats another person, the former will be higher-rated and can be considered more intelligent than the latter at playing chess. That, in part, was the motivation for using chess as a barometer of intelligence. There is also no luck involved, as with many other games.

This brings us back to the game of chess and, in particular, ACM's role in it. In 1970, ACM's Annual Conference took place at the New York Hilton. Ken King, head of Columbia University's computer center, served as co-chairman with me of the conference's Special Events program. About the same time, Tony Marsland, a Bell Telephone Laboratories researcher, approached me suggesting a demonstration of his chess-playing computer at the conference as a special event. We met, discussed this, and concluded we could put together something more exciting: the first chess tournament exclusively for computers. It was named the U.S. Computer Chess Championship. In addition, we included a computer music festival and a computer art festival in the program. These constituted our special events. I have forgotten how the music and art festivals turned out. I do recall Charles Dodge's music involved transforming the intensity of energy from the sun into musical notes, and the resulting music's randomness was surprisingly delightful.

Marsland and I rounded up six contestants for the chess tournament.

Hans Berliner, who had been the world correspondence chess champion, was a doctoral student at Carnegie Mellon University at that time; he entered his program J. Biit. Ken King arranged for it to run on Columbia University's powerful IBM 360/91 during the competition. Berliner's program entered the tournament as the favorite.

Northwestern University students David Slate, Larry Atkin, and Keith Gorlen entered their program CHESS 3.0. It ran on their university's CDC 6400, a powerful machine, but not in the same class as Columbia's IBM 360/91.

Marsland entered his program, The Marsland CP; it ran on a Burrough's B5500 located in Burrough's New York City sales office.

Running on IBM 360/65s were two other entries: COKO III, developed by Dennis Cooper and Ed Kozdrowicki at Bell Telephone Laboratories' Whippany facilities, and SCHACH, developed at Texas A&M by Franklin Ceruti and Rolf Smith, U.S. Air Force captains at the time.

Lastly, Chris Daly, working with Ken King (not Columbia's Ken King), brought their computer, an IDIOM system based on a Varian 620/i processor, to the site.

Three entrants used terminals connected to their remote computers, two others spoke by telephone to a human operator at their computers' sites, and one was at the site.

Jacques Dutka, a mathematician known for calculating the square root of 2 to a million decimal digits, served as tournament director.

Missing from the competition was Mac Hack, developed at MIT by Richard Greenblatt, established leading up to the tournament as the strongest chess-playing program. It had competed in a number of human tournaments and was rated around 1600, the level of a good high school player.

So began a very significant, long-lasting experiment. Could a computer be designed to exhibit the intelligence of a chess expert, master, grandmaster, or world champion? Could one be designed to match the chess intelligence of the top human mind? What would it take? How long would it take? In 1970 there were no cellphones, no email, no drones, no self-driving cars, no Siri. Yet, the computer revolution was heating up!

Grandmasters were generally in denial in 1970. Some contended good chess players used intuition when playing chess, and intuition could not be programmed. The programs were the laughingstocks of the top chess players. That was the situation when the first ACM U.S. Computer Chess Championship was held.

The format of the competition was a three-round Swiss-style tournament beginning Aug. 31, 1970, and ending Sept. 2, 1970. Entries had two hours to make their first 40 moves, then 30 minutes to make each successive 10 moves. Bugs cropped up as the competition went on, with the most dramatic seen in the early moves of the round 1 game between The Marsland CP (White) and J. Biit (Black). Marsland's program made the worst possible 8th and 9th moves, leading to a quick victory for J. Biit and laughter from the audience of computer and chess experts. Attendees Grandmaster Pal Benko and International Master Al Horowitz may have been among those laughing.

In the next round, J. Biit was defeated by the Slate/Atkin/Gorlen program, with the audience cheering CHESS 3.0's 47^th move, a short-term sacrifice leading to an easier, shorter path to victory. Quite unlike a human tournament, the audience was very vocal as the games progressed, cheering and laughing. Also unlike human tournaments, programmers would get together for coffee after the games ended, to discuss the day. A close community of programmers developed over the years.

CHESS 3.0 went on to win the tournament, winning all three games. It dominated the field for a decade, until Ken Thompson's BELLE arrived in the late 1970s with special chess hardware. BELLE stayed on top until Bob Hyatt's CRAY BLITZ and Hans Berliner's HITECH caught up in the middle 1980s. In the late 1980s and early 1990s, IBM's Deep Blue, developed by Feng-Hsiung Hsu with major help from Murray Campbell, Joe Hoane, and Jerry Brody, with Chung-Jen Tan serving as boss, rose to the top of the pack. Deep Blue, playing grandmaster-level chess, went on to defeat Garry Kasparov in their classic 1997 match, a landmark in the world of artificial intelligence.

(Tan and I go back to the late 1960s, when he was a doctoral student at Columbia University and I was a young professor there. We lived in the same apartment building. We published several papers together in the field of automata theory; most prominently, one in the January 1970 issue of IEEE Transactions on Computers entitled Iteratively Realized Sequential Circuits.¹)

A half-century later, chess programs are so much better than top humans that there is no contest. The top players use computers to help them learn to play better! The laughing has ended.

Computers are, in round numbers, 1,000 times faster than in 1970, and their memories are clearly more than 1,000 times larger. Imagine driving a car that goes 1,000 times faster than the one you currently drive; a 10-mile drive to work at 60 mph would take 10 minutes, while at 60,000 mph it would take less than a second. Chess programs require, for each additional level of search, approximately four times the amount of time; a speedup of 1,000 allows computers to search about five levels deeper (4x4x4x4x4 = 1024). On top of faster computers and much larger memories, there have been many software improvements and even different approaches all together, such as the use of Monte Carlo search.

Over the years, ACM headquarters supported the yearly tournaments. I would like to single out two individuals in particular: Jim Adams and Joe DiBlasi. In addition, Temple University professor Frank Friedman provided support, as did Ben Mittman, head of Northwestern University's Vogelback Computer Center. Lastly, British International Chess Master David Levy helped, especially in setting up the 1996 Kasparov versus DEEP BLUE match.

My books, one with David Levy, chronicle the great progress computers have made at chess and ACM's involvement in it:

Computer Chess, Academic Press, New York, 1975.

How Computers Play Chess, with David Levy, W. H. Freeman, 1991.

Kasparov versus DEEP BLUE: Computer Chess Comes of Age, Springer-Verlag, 1997.

Deep Blue: An Artificial Intelligence Milestone, Springer, 2002.

Beyond Deep Blue: Chess in the Stratosphere, Springer, 2011.