The brute force method and chess computers! -The reason why computer fail at chess
"In 50 years, a calculating machine will defeat the world chess champion,"
prophesied German computer pioneer Konrad Zuse in 1938. The engineer was correct; his error was barely ten years. Garry Kasparov, the world champion at the time, was defeated in a match in 1997 in New York by the 1.4-ton IBM computing giant "Deep Blue."
"Deep Blue" ultimately defeated the expert thanks to its incredible processing power—the supercomputer could check 200 million chess moves per second.
| The story behind chess computers |
The history of chess computers dates back to the 1940s, when the first attempts were made to develop computers capable of playing chess. One of the first chess computers was the "Turing's Chess Program", developed by Alan Turing himself.
In the following decades, new chess computers were repeatedly developed, which became increasingly more powerful thanks to improved hardware and special chess software.
A milestone in the development of chess computers was the victory of the computer Deep Blue over the world chess champion Garry Kasparov in 1997.
Kasparov and the chess computers
Garry Kasparov, one of the world's most prominent chess players, has helped chess computers in a variety of ways. He was one of the top chess players of his day and had played numerous memorable games against chess machines, including IBM's Deep Blue. These games have served to push the boundaries of human intellect in chess and increase the performance of chess machines.
Kasparov has also contributed to the advancement of chess software and artificial intelligence algorithms by working with computer scientists and engineers to investigate new techniques to constructing computer-based chess systems.
His experiences and ideas from these partnerships have contributed to breakthroughs in chess technology, allowing chess machines to compete at a high level today.
GM Garry Kasparov vs Deep Blue
| Exciting area for computer experts |
“Chess programs are the oldest computer games in existence. As early as the 1940s, researchers tried to teach the first computers to play chess. The chess programs served as an experimental field to let the computers solve complex problems and further develop their software.”
reports Andreas Lange, head of the Computer Games Museum in Berlin.
The clear rules of chess require a high degree of abstraction and can be easily represented mathematically on the computer. And chess has a clearly defined goal: checkmate the king.
1. Chess software makes it possible to test the performance of computers:
Chess is a game that is well suited to the use of computers. Chess software makes it possible to test the performance of computers in terms of strategic decisions, calculation skills and game understanding.
2. Chess software offers opportunities for research and development:
Chess software is also interesting for computer experts because it offers opportunities for research and development. New algorithms, strategies and technologies can be developed and tested to improve the performance of chess programs.
3. Chess software can also be used in other areas:
The technologies and algorithms used in chess software can also be used in other application areas such as artificial intelligence, data analysis or machine learning.
Computer Games Museum in Berlin
Computer Games Museum in Berlin
Entering of Computer Games Museum in Berlin
Inside of Computer Games Museum in Berlin
Inside of Computer Games Museum in Berlin
Inside of Computer Games Museum in Berlin
| First game of computer chess in 1952 |
In 1945 Konrad Zuse developed the first ideas for a chess program. Four years earlier, the Berlin inventor had built the world's first freely programmable, program-controlled calculating machine, Z3. In 1945 he completed his programming language “Pankalkül”.
In 1949, Claude E. Shannon, father of communication theory and computer pioneer, gave a groundbreaking lecture on the possibilities and difficulties of computer chess. A year later he also published a chess program. The mathematician Alan Turing also worked on chess: in 1952 he played the first game of computer chess against Alick Glennie in Manchester.
| Konrad Zuse |
Konrad Zuse (born on June 22, 1910 in Berlin) was a German engineer and inventor who is considered a pioneer of computer development.
Zuse showed interest in technology and mechanics since he was a child and began developing mechanical calculating machines while studying at the Technical University of Berlin.
In year 1941, he presented the Z3, the world's first functional programmable computer. This computer was capable of performing complex calculations and thus laid the foundation for modern computer technology. During World War II the Z3 was used for military purposes.
After the war, Zuse continued his work on computer development and founded Zuse Apparate GmbH, which later became one of the leading computer manufacturers in Europe. Among other things, Zuse invented the Z4, the first commercially successful computer.
Logo of "Zuse Apparate GmbH"
Konrad Zuse died on December 18, 1995 in Hünfeld. He is considered one of the world's greatest computer pioneers and his contribution to the development of computer technology is still highly valued today.
| Claude Shannon |
Claude Shannon, born April 30, 1916 in Petoskey, Michigan, was an American mathematician, electrical engineer and cryptanalyst known as the father of information theory. He is known for his pioneering work on the digitization of communication systems, coding theory and cryptography.
Shannon studied electrical engineering at the Massachusetts Institute of Technology (MIT), graduating in 1936. He later received his doctorate in mathematics from the University of Michigan. During his time as a student, he developed innovative ideas that significantly influenced the field of information theory.
In 1948 he published his groundbreaking work "A Mathematical Theory of Communication", in which he introduced the concept of entropy in information theory and developed fundamental concepts such as Shannon entropy and Shannon-Fano coding.
This work laid the foundation for modern communications technology and laid the theoretical foundations for the development of computers and digital networks.
Shannon also worked as a cryptanalyst for the U.S. Army during World War II, where he was involved in deciphering codes of enemy powers. His work contributed significantly to the Allies' success and made him a pioneer in the field of cryptography.
After the war, Shannon returned to MIT and taught there as a professor of electrical engineering. He continued to publish seminal works in information theory, cryptography and signal processing.
He also invented the concept of the bit as the smallest unit of information and thus had a significant influence on computer science.
Claude Shannon died on February 24, 2001 in Cambridge, Massachusetts.
He is considered one of the most important scientists of the 20th century and one of the leading figures of the digital revolution.
| Alan Turing |
Alan Turing was a British mathematician, logician and computer scientist, considered one of the most influential thinkers of the 20th century. He was born in London on June 23, 1912 and grew up in a wealthy family. From an early age he showed exceptional intelligence and a strong interest in mathematics and technology.
Turing studied at the renowned University of Cambridge, where he primarily focused on mathematical logic. During his studies he developed important concepts such as the Turing machine, which can be considered an early precursor to the modern computer.
During World War II, Turing worked for the British government, where he was instrumental in deciphering the German Enigma codes. His work in deciphering the codes was instrumental to the Allies' success and is often seen as a significant contribution to victory in the war.
After the war, Turing continued his work in computer science, developing groundbreaking concepts such as the Turing Test to measure the intelligence of machines. Turing was also one of the first to create the theoretical basis for artificial intelligence.
Despite his outstanding achievements and contribution to modern computer science, Turing was persecuted and condemned for his homosexuality. He was forced to undergo 'chemical castration', which led to severe mental health problems. Turing died in 1954 at the age of just 41.
It was only many years after his death that Turing was posthumously rehabilitated for his achievements and recognized for his groundbreaking contributions to science.
Today he is revered around the world as a pioneer of computer science and artificial intelligence, and his legacy lives on in the form of the Turing Award, considered the highest honor in computer science.
Alan Turing is celebrated as one of the greatest thinkers of the 20th century and a hero of science.
The Turing Award
[all winners by years: https://amturing.acm.org/byyear.cfm]
| “Paper Computer” lost the game |
But because there was still a lack of a powerful computer, Turing took on the role of the computer himself and calculated the moves according to his previously written program on paper.
The paper chess computer was a device Turing developed in the late 1940s to simulate chess games on an analog, mechanical system. The device was based on a complex network of circuits that allowed Turing to analyze chess positions and calculate possible moves.
Although the paper chess computer did not have the same level of intelligence or functionality as modern computer chess programs, it was still an important milestone in the history of artificial intelligence.
However, the “paper computer” lost – certainly also the result of a somewhat chaotic improvisation.
Turing's paper machine – Alick Glennie, Manchester 1952
As early as 1956, a machine defeated a human in chess for the first time in Los Alamos: the tube computer “Maniac I” beat a young secretary who had only learned the board game a week before. However, the chessboard, programmed by John von Neumann, was reduced to six by six fields for the sake of simplicity. The computing time was twelve minutes per move.
The “Belle” machine, developed in New Jersey in 1979, even became “National Champion” in the USA. Belle could calculate up to 180,000 positions per second and was the first chess computer to receive such a title. However, strong players were far superior in the battle between humans and computers until the 1980s. Although chess master David Levy from Scotland had to settle for a draw after 89 moves against “Chess 4.8” in Hamburg in February 1979, Garry Kasparov won in 1985 in a simultaneous game against 15 computers and four years later defeated the “Deep Blue” predecessor “Deep Thought”.
“Chess computers were the first opportunity to directly compare human and artificial intelligence,” explains historian Stefan Stein from the Heinz Nixdorf MuseumsForum Paderborn. “When it comes to chess, computers ‘think’ completely differently than people. Because the attempt to transfer human intelligence directly into the computer has failed. While humans work intuitively, computers calculate endless amounts of data in a short time and make decisions based on the data,” says the museum curator.
But because an incredible number of theoretically possible game variants open up in a chess game of 40 moves, the software works with tricks: “In order not to waste computing power on nonsensical moves, the program selects the possible game variants from among the possible game variants when searching for the next move most sensible options.”
| Calculating machine: Z1 |
The invention ultimately came about out of laziness. As an engineering student, Konrad Zuse developed a deep dislike for the complicated static calculations that he of course had to carry out by hand at the time. Zuse wanted to leave this task to a machine.
Although there were already the first mechanical calculating machines with which he could carry out individual steps of the calculations, "but they couldn't work according to a program. The joke of the computer is that I first have to do a whole sequence of operations, a whole formula, a whole complex formula complex," explained Zuse.
From 1934 onwards, Zuse devoted himself entirely to the development of a programmable calculating machine. In contrast to the existing calculating machines, the Z1 already worked with binary numbers - just like computers still do today. This meant that Zuse was able to do without gears, as the calculating machines of the time still used them.
Switches that had two positions: on were sufficient for the arithmetic operations. Zero, one – binary.
However, the mechanical switches regularly got stuck, which meant that reliable operation of the machine was not possible.
"Then it turns out that such a complicated device, like a program-controlled calculating machine, cannot be built purely mechanically and I then took the step of building it with relays." - Zuse
| Calculating machine: Z2 |
In his second prototype, the Z2, he tested the use of such electromechanical relays. He was also able to convince the German Aviation Research Institute DVL that he could use this technology to develop a reliable calculating machine.
The DVL then supported the development of the third prototype with 25,000 Reichsmarks (=12.782,30 Euro=13.807,76 Dollar)
On May 2, 1941, Konrad Zuse presented his third prototype: the Zuse Z3, the world's first functional, programmable computer.
| Calculating machine: Z3 |
On May 12, 1941, Konrad Zuse presented this prototype: Zuse Z3, the world's first functional, programmable computer.
It could perform five operations per second, had 200 bytes of memory and weighed about one ton. Today humans put billions of times more powerful computers in our pockets. The Z3 was primarily used for calculations in technical and scientific applications.
Z3 was based on the binary floating point format developed by Zuse and could handle floating point numbers with an accuracy of up to 7 decimal places. The computer had a clock speed of 5 to 10 Hertz and could run simple programs written in a type of assembly language.
The Z3 was very primitive compared to our today's computers, it is considered groundbreaking in the development of modern computers. The development of Z3 was the beginning of the age of electronic calculating machines and revolutionized the way calculations were carried out.
The only prototype of the Z3 was destroyed in a bombing raid on Berlin in 1944. But there are Replicas; for example, in the German Museum in Munich and in the Konrad Zuse Museum in Hünfeld.
Horst Zuse, son of Konrad Zuse, presents the replica of the world's first computer, the Zuse Z3.
The Z3 computer was relatively small and consisted of a number of mechanical and electromechanical components. It had a rectangular metal frame and was equipped with various switches, buttons and indicators to facilitate data input and output. The computer also had a series of mechanical relays used to process data.
| Programming language “Pankalkül” |
Pankalkül is a programming language originally developed by Konrad Zuse which was introduced in the 1940s and was one of the first programming languages to ever exist.
The programming language itself has many unique features that is different from other programming languages. One of the most important features of Pankalkül is its block structure, that means; that programs are organized into blocks of instructions. These blocks can be recursively nested and allow the programmer to create complex structures.
Pankalkül also uses a method called "treasure hunt" or search method, which allows the programmer to find specific data or patterns in a large database. Treasure hunt is based on a type of tree structure that allows the programmer to search through different branches of the database to find the item he or she is looking for.
Another interesting feature of Pankalkül is the ability to perform symbolic calculations. This means that the programmer can define mathematical expressions with variables without inserting concrete values. This gives the programmer the ability to create universal mathematical rules that can be used with different inputs.
Pankalkül is a programming language that offers many unique features and possibilities. Although it is no longer used, it has made an important contribution to the development of computer science.
"Pankalkül, a formalized programming language developed by Konrad Zuse, is no longer actively used today. But it is sometimes used (e.g in University) as a historical example or for research purposes in computer science and computer history."
| The brute force method |
The brute force method is a trial-and-error approach technique and is used to find a solution to a problem by systematically trying all solutions which are possible.
How it works:
1. A list of all possible solutions is created. Depending on the nature of the problem, these solutions can be numbers, letters, strings, or other elements.
2. Each possible solution is then tried one by one to check whether it meets the requirements of the problem, this means that the solution is checked for validity.
3. If a valid solution is found the process stops and the solution which was found is presented as a result.
4. If no valid solution is found, the process continues until all possible solutions have been tried until there is a possible solution.
The brute force method is relatively easy to implement, but in genral it requires a lot of computing power and is not always that efficient for complex problems. But in some cases it is the only way to find a solution, especially when the number of possible solutions is limited, like in chess.
A mathematician would describe the brute force method as an approach to solving a problem in which every possible combination or solution is systematically tried to find the best or most optimal solution.
The mathematician would probably explain that the brute force method is typically used for smaller problems or those with a limited number of variables, as the high computational complexity can make it inefficient for larger problems.
Nevertheless, in certain cases, the brute force method could be the simplest and most direct method to find a solution, especially when there are no specialized algorithms or techniques that can solve the problem more efficiently.
The brute force method in connection with chess
The brute force method, in the context of chess, refers to going through all possible moves and variations in a game of chess to find the best move order or move. This is often used by chess computers and chess programs to calculate the best possible moves.
With the brute force method, all possible moves and variants are played through without taking special strategies or tactical considerations into account. This can be very time consuming as the number of possible moves and variations in chess is extremely high.
The computer analyze which moves are possible for him, which reactions of the opponent are possible for each of these moves, which own moves are then possible again and so on.
This means that there is a complete scope which shows for every conceivable course of the game whether it ends in a victory or a loss. So the computer can only make a perfect decision. It would never decide on an action whether the opponent could force a victory through a certain decision.
At the same time, it would recognize that the opponent would be able to force a win through a certain sequence of decisions or independent actions and would therefore never choose this option.
A human could never set a trap, the computer would immediately exploit every "error" with a foresight over hundreds of moves that a human could never calculate. Because of this the computer delivers a flawless and perfect game of chess.
How many possible game progressions are there?
The first player, can open the game with 20 possible moves, then black also has 20 options for his first move, which means after both players have made their first move there are 20 x 20; 400 possible games.
After White has moved the third time, there are 8902 possible game variations. After 10 moves, when every player moved 5 times, there are 69,352,859,712,417 possible games that can theoretically be played.
With every move the number grows so much that the final number of possibilities cannot be calculated.
| Move | Possiblities |
| 1 | 20 |
| 2 | 20 x 20 = 400 |
| 3 | 8902 |
| 10 | 69,352,859,712,417 |
Mathematician Claude Shannon gave a rough estimate, which is known as the Shannon number. He estimates that the players can make an average of 30 possible moves and a game consists of an average of 80 moves, which results in about 10120 chess games that are possible.
This is an estimate of the lower bound, meaning that the true number is probably well above it. The fundamental problem lies in the enormous size of this number - it is difficult to imagine the real size of a number with 120 zeros.
1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
A modern supercomputer would need 1090 years to calculate a complete game.
That means our universe's time since the Big Bang wouldn't be enough for the computer to make the first move. A billion times that time wouldn't be enough.
The time of the universe from Big Bang to present
| "Deep Blue" |
"Deep Blue" computer, developed by IBM
Nevertheless, in 1997 the computer "Deep blue" became the first computer to beat a world champion in a chess competition. Computers can find other ways to make the decision advantageous, for example by selecting sensitive small areas of the game tree or by targeting a certain position or by analyzing all of the opponent's past games. (One Blog post ago I explained how "Deep blue" is working)
This works because chess grandmasters incorporated their ways of thinking into the programming and the code could be adapted between games. Whether this was still a victory based on pure computer power is a matter of opinion.
But that also means that the Blue didn't play perfect chess. Computers will play better than humans but with fallible human programming and would definitely be beaten by a computer with the brute-force method.
Nevertheless, we are used to an immense increase in the computing power of computers, but is it possible that a computer with incredible computing power will play chess perfectly one day?
In order to carry out such a calculation, the results of the individual games have to be saved temporarily and in order to save the information, you need a storage medium like a piece of paper, a brain cell or tiny components in computer chips, so you need a piece of matter made up of particles.
However, in our observable universe there are about 1080 atoms, which is significantly less than the 10120 possible courses of play in chess.
For every atom in existence there are billions of possible chess games, so our entire observable universe simply does not offer enough storage space for a perfect chess computer.
No matter how technology develops, we will probably never know what the flawless moves of a perfect, overpowering chess intelligence will look like.
The structure of an atom
First ever taken X-ray-photo of an atom
| Conclusion |
Computers can never play chess perfectly because chess is a game with an infinite number of possible moves. Even the most powerful computers cannot calculate all variants and therefore have to rely on heuristics and algorithms to make decisions.
