The Adventure of Chess Programming (Part 2)

by Frederic Friedel
2/12/2019 – Europe's largest (and most influential) news portal, Der Spiegel, recently published a three-part series on the history of chess programming. It was authored by Frederic Friedel, emeritus editor of the ChessBase news page. In the early 1980s Frederic was intrumental to bringing computer chess to the attention of the German public, and in 1987 he co-founded ChessBase. Here is part two of his series. Read part one.

ChessBase 17 - Mega package - Edition 2024 ChessBase 17 - Mega package - Edition 2024

It is the program of choice for anyone who loves the game and wants to know more about it. Start your personal success story with ChessBase and enjoy the game even more.

More...

This article is reproduced with kind permission of Spiegel Online, where it first appeared. The author was told to make the series personal, describe the development of chess programming not as an academic treatise but as a personal story of how he had experienced it. For some ChessBase readers, a number of the passages will be familiar, since the stories have been told before on our pages. For that, we apologize. For others, this can serve as a roadmap through one of the great scientific endeavours of our time.

Part two

By Frederic Friedel

How do computers play chess, how do they "think"? In our answer to this question, we are going to encounter some big numbers — some very, very big numbers. You will be surprised.

But let us start with a module that all chess programs need: the move generator. In order to play the machine needs to know the rules of the game, it must know how the pieces move. Formulating these rules is a painstaking task – if you don't get it right knights will jump over the edge of the board to the other side, or castling rules will be breached. I have told the amusing story of a young chess genius, twelve years old and already of grandmaster strength, who demonstrated the inability of chess players (and chess programmers) to correctly formulate the promotion rules, at least verbally.

In any case, once the machine has understood the rules it is able to generate a list of every legal move in any position. With that, it can start a "look-ahead". This is what all chess programs — and incidentally all humans — do: if I play this and he plays that, I can play this and if he plays that I can capture his knight. Sound familiar? Of course, machines do it at blinding speed, and they usually do it for every possible combination of moves. Which leads to the very large numbers I said we would be dealing with.

Many people know a very large number connected with chess. Legend has it that the game was invented by Sissa ibn Dahir, and his king, Shirham, was so grateful that he said his vizier could have anything he wanted as a reward. "Just some wheat," Sissa said, "one grain on the first square of the board, two on the second, four on the third, and so on." The king was surprised at the inexplicable modesty of this wish – until he had worked out the total number of grains Sissa would receive: 18,446,744,073,709,551,615. That is 18½ quintillion (10^8), and it would today represent the world production of wheat for many centuries. Listen to Stephen Fry describe it.

Sissa apparently understood geometrical progression — how numbers grow exponentially when multiplied by a common ratio (rough definition). This plays a role in the general consideration of chess: Will we ever be able to solve the game? Can we derive a perfect winning strategy by examining every possible sequence of moves? The answer is a resounding no!

Let us take a look: in a normal chess position, a player will have, on average, 40 possible moves to choose from. To each of these, the opponent can play one of 40 different replies. That comes to 1600 different sequences after just one move for either side. And the numbers grow exponentially: after two moves for either side 102 million different sequences are possible. After three moves it is 4.1 billion — more than the age of a human in seconds. Sissa's number is reached after just six moves, and after seven moves we are approaching the number of stars in the universe. Let us assume the average chess game lasts 40 moves. At this point, the number of sequences has reached 10^128. Compared to that the number of particles in the known universe, around 10^86, is completely insignificant. Really.

So the game will never be completely solved in this way — nothing will ever calculate every possible sequence of moves. But that is not actually necessary. If you can work out every continuation to a limited depth you already start playing a reasonable game. Which is exactly what computers do: execute sequences of moves to a given depth, evaluate the resulting position, vary the sequence systematically, and compare the evaluation of all positions at that depth. In the end, they play the first move of the sequence that leads to the most favourable position. That is essentially what humans also do. But they do it at a far slower rate than computers. A chess grandmaster will work out one or two continuations per second in his mind; the computer can manage a few million in the same time. So how can humans compete?

Intelligence vs Brute Force

The difference between humans and computers is that experienced chess players will only consider continuations that are meaningful — they know instinctively that a large number of moves can be safely ignored. These moves lead to nothing. So instead of checking every possible continuation humans only look at plausible ones. The branching factor in the look-ahead is not 40, but just a few moves. Computers, on the other hand, must generally examine everything.

This "brute force" approach appeared doomed to failure. Indeed, in the early days, when computers were still doing shallow searches, they played like rank amateurs. So programmers tried to implement "intelligent pruning", to cut off less meaningful branches so the program could navigate a slimmer search tree, and penetrate deeper into positions.

One such example was MacHack, a chess program developed at MIT by Richard Greenblatt (seated above with tie). He wrote a "plausible move generator" which restricted the computer's branching to 15 on the first two moves, and 9 for the rest of the tree. So a five ply search resulted in 127,575 positions that needed to be evaluated, not the 102 million that pure brute force programs required.

MacHack achieved a strong amateur level of skill, and it played hundreds of games against humans, including three, it is rumoured, against Bobby Fischer. It was most famous for winning a game against Hubert Dreyfus, a philosopher and Artificial Intelligence critic who had predicted that computers would never be able to beat a ten-year-old at chess. MacHack proved him wrong.

I visited the MIT team around 1980, when MacHack had reached a playing strength of more than 1500 Elo points and had, in fact, become an honorary member of the US Chess Federation. Greenblatt was having a bit of a crisis because his program was still too error-prone. To correct this he had designed what he described to me as an "blunder blocker and brilliancy finder." It was a hardware chess rack that ran a brute force search parallel to MacHack. Cheops, as he had named it, was meant to alert MacHack to tactics that the heuristic program would otherwise miss. I do not know how far he got, or how useful this combination of intelligence and brute force proved to be.

Another (more famous) effort at using the intelligent method in chess was undertaken by former World Champion (from 1948 to 1963, with two short breaks) Mikhail Botvinnik. He was by profession an electrical engineer and dreamed of managing the Soviet economy using artificial intelligence. With a team of computer scientists, he designed a highly selective chess program, PIONEER, that used general principles of chess to drastically restrict the search. The project suffered from a lack of proper computer power in the Soviet Union, but was well publicised in the West and at least produced a seminal book on artificial intelligence.

I visited Botvinnik and his team in Moscow and met with him a number of times, in Germany, Holland and the US. It was clearly painful for him that a rival Soviet program, KAISSA, was far stronger than Pioneer, and had, in fact, become the first world computer chess champion in 1974. Kaissa was a pure brute force program.

The head of the Pioneer programming team Boris Stilman (left), Mikhail Botvinnik. We spent an interesting day together at Botvinnik's dacha outside Moscow in the early 1980s | Photo: Frederic Friedel

The reason the non-selective programs won the day is that scientists came up with a number of "tricks" that allowed them to reduce the number of sequences that needed to be considered in the tree search without affecting the result. A prime example is Alpha–Beta pruning. Programmers realized that if you have a final score for one move, and start calculating another, as soon as you have found a line that is inferior to the first you can abandon that branch of the search tree. It is not necessary to waste time determining exactly how much worse the second move is. Then they discovered that if you ordered the sequence of moves the program searched based on a previous, shallower search, you got substantially more cut-offs. That is called iterative deepening.

Using this and a dozen other very clever algorithms, chess programs were able to search deeper and deeper, and become stronger and stronger. All attempts to generally define "meaningful" moves in chess programs were abandoned, the "intelligent" (also known as the "Shannon type B") method of chess programming had failed. And the truly dramatic speed-up of computer hardware over the years contributed to the triumph of the brute force method. It allowed computer programs to soon rival and then completely outpace human chess abilities. This was described in my previous article (see link below).

End of the story? Not at all. The past year has brought a radically new development in chess programming — one that is relevant not just for the game but for humanity in general. That is the subject of the final article.


All articles in this series

The Adventure of Chess Programming (Part 1)
Did you know that the first chess program was written by Alan Turing a few years before the first computers were built. The first chess program to actually run on a machine was MANIAC, written in 1951 by the atomic bomb scientists in Los Alamos. Fifty years later computers were challenging world champions, and today it is pointless for any human to play against a digital opponent.

The adventure of chess programming (Part 2)
How do computers play chess, how do they "think"? The author discusses the very, very big numbers involved in looking ahead at all possible continuations. Unfortunately the effort to prune the search tree and only look at plausible lines failed, while advances in hardware and software development led to the triumph of the "brute force" method.

The adventure of chess programming (Part 3)     
In the first two sections of this series, originally published in Der Spiegel, Europe's largest (and most influential) news portal, Frederic Friedel described his decades-long involvement in computer chess. He was commissioned to make the story personal, and in part three he describes his encounter with the latest twist in this area of research: artificial intelligence and self-learning machines that are playing at the very highest levels of the game. Where are we headed and what will the future bring?

About the author: Frederic Friedel, 73, studied Philosophy, Science and Linguistics in Hamburg and Oxford. As a science journalist he was employed by the national TV channels ZDF and ARD, and in this capacity already in the 1970s he reported on computer chess. In 1987 Friedel founded, together with Matthias Wüllenweber, the ChessBase, a company that today is one of the world's largest producers of chess software. It is also a cooperation partner of the SPIEGEL. Friedel lives in Hamburg, Germany.

Originally published in Spiegel Online (in German): Wie aus niedlichen Gegnern unschlagbare Maschinen wurden. ChessBase is a cooperation partner of DER SPIEGEL.


Editor-in-Chief emeritus of the ChessBase News page. Studied Philosophy and Linguistics at the University of Hamburg and Oxford, graduating with a thesis on speech act theory and moral language. He started a university career but switched to science journalism, producing documentaries for German TV. In 1986 he co-founded ChessBase.

Discuss

Rules for reader comments

 
 

Not registered yet? Register