This is the second part of the chess series by ChessBase founder Frederic Friedel. The first part can be found here.
Actually, it's quite simple: To play chess, a machine has to know the rules - it has to know how to draw the pieces. Defining the rules correctly requires a lot of attention. For example, if you make a mistake, jumpers may jump over the edge of the board and appear on the other side.
Now, if the computer has understood the chess rules correctly, it can generate a list of all legal traits for any position. With this, like any human player, he can start the "Foresight": If I play this and my opponent counters, I can play that, and when he does, I can beat his knight. Does this sound familiar to you? Of course, machines perform this pre-search at breathtaking speed, and that leads to an enormous number of possibilities.
Javascript is required for the display.
There is a very large number that became famous in connection with the game of chess. Legend has it that the Indian vizier Sissa ibn Dahir invented the game. His king, Shirham, was so pleased that he told the inventor that he could wish for anything he wanted. "Just some wheat," said Sissa, "one grain in the first box of the chessboard, two on the second, four on the third, and so on." The king was very surprised at the modesty of the vizier - until he realized how many wheat grains he owed him: 18,446,744,073,709,551,615. That is about 18.5 trillion, which would be equal to today's world production for many centuries.
Sissa has obviously known the geometric progression - he understood how numbers grow exponentially when successively multiplied by a constant factor, say two. This plays an important role in the general theory of chess: Will we ever "solve" the game? Can we find a perfect winning strategy by examining all possible moves? The answer is an express no!
More trains than stars in the universe
In an average chess position, a player has 40 moves to choose from. For each of these moves, the opponent can play 40 different response moves. That makes 1600 possible moves after only one move. And the numbers are growing exponentially: After two moves for each side, 102 million different sequels are possible, after three moves it is 4.1 billion. That already surpasses the number of seconds in a human life. Sissa's wheat grain number is reached after six moves, and after seven moves, we're at the number of stars in the universe. If we assume that a game of chess lasts 40 moves, we end up with a number of 10128 possible variants. By comparison, the number of elementary particles in the known universe is around 1086 - a ridiculously small number. Really.
So definitely the game will never be solved this way, because never all possible moves can be calculated. But that is not necessary. If you calculate all possible sequels to a limited depth, you can already reach an acceptable level of play. Doing the computer exactly: You execute the trains up to a defined draft depth and evaluate the resulting position. Then they vary the train sequences systematically and evaluate all emerging positions. At the end they play the first move of the series, which led to the most advantageous position.
That's basically what human players do, but much slower than computers. A chess grandmaster can create and check one or two positions per second in the head; the calculator creates several millions in the same time. So how can people compete with them?
Intelligence vs. Brute Force
The difference in the approach of humans and machines is that experienced chess players only consider sequels that make sense . They instinctively know that certain moves can be safely ignored because they lead to nothing. Instead of checking all possible moves, human players are only considering plausible sequels. For them, the branching factor in the look-ahead is a much lower number than 40. Computers generally have to investigate everything.
The project of chess programming seemed to fail due to this "brute force method". In fact, computers performed very shallow searches in the early days and played like bloody novices. So programmers tried to introduce "intelligent cutting" in the tree search. They wanted to cut off certain, less meaningful sequels at the root, so that the computer could penetrate deeper.
One such example was MacHack, a chess program developed at the Massachusetts Institute of Technology (MIT) by Richard Greenblatt. He used over 50 elaborate evaluation functions to determine "plausible" moves and to consider only those in the pre-search. In the first two moves it was 15, then only nine. Thus, a search of five half-strokes yielded only 127,575 positions that needed to be rated, not 102 million, as in a brute-force program.
Soviet dream of artificial intelligence
MacHack achieved the strength of an advanced amateur. It played hundreds of games against people - also rumored three against Bobby Fischer. The program, however, only really came into the limelight when it struck the philosopher and Artificial Intelligence skeptic Hubert Dreyfus. He had predicted that computers would never succeed in defeating even a ten-year-old in chess. MacHack refuted that.
Javascript is required for the display.
Another (more famous) attempt at intelligent chess programming was undertaken by Mikhail Botvinnik, the former World Chess Champion (from 1948 to 1963, with two breaks). Botwinnik was an electrical engineer by profession and dreamed of controlling the Soviet economy with artificial intelligence. With a team of computer scientists he developed a very selective chess program called Pioneer, which used general principles of the game to radically shorten the tree search. The project suffered from a lack of computational power in the Soviet Union, but attracted much attention in the West.
Deeper, deeper and deeper
The reason for the success of the violence programs was that scientists discovered a series of "tricks" to radically shorten the foresight without changing the outcome. An important example is the alpha-beta algorithm. It became clear that once the program has found a clear rating for a tree branch in the search, it can completely cut off the next branch as soon as a worse rating is discovered in a single move.
After that, it was discovered that the order in which the moves are processed plays a crucial role in alpha-beta tricks. So first you did a flatter search to get the trimming done. The procedure is called iterative deepening .
By using these and a dozen other equally clever algorithms, one could make chess programs ever lower and more powerful. The attempt to define "meaningful" moves and push the "intelligent" method had failed and been abandoned. Add to that the truly breathtaking speed acceleration of computer hardware that led to the final victory of the brute force method.
Is this the end of the story? Not at all. Especially this year we experienced a fundamentally new direction in chess programming - a development that is of utmost importance not only for chess but for humanity in general. That's the topic for the last post of this series.