How does the Deep Blue algorithm work?
The Deep Blue chess computer is considered one of the most significant developments in the history of chess and artificial intelligence. In this blog post we take a look at the origins of the Deep Blue, its legendary match against Garry Kasparov and its impact on the world of chess.
Deep Blue was a chess computer developed by IBM. He was particularly famous for defeating world champion Garry Kasparov in a chess match in 1997. Deep Blue was one of the first chess computers to use specialized hardware and sophisticated algorithms to challenge and beat human chess players.
Deep Blue relied on a combination of hardware and software to analyze chess positions, calculate moves and develop counterstrategies. After his success against Kasparov, Deep Blue made headlines and showed the potential of artificial intelligence in the world of chess.
Deep Blue versus Garry Kasparov was a pair of famous six-game human–computer chess matches, in the format of machine and humans. In this format, on the machine side a team of chess experts and programmers manually alter engineering between the games.
| What is the "deep blue" algorithm? |
The deep blue algorithm was developed by IBM. It was a chess-playing computer system designed for a regular chess game or chess match against the reigning world champion under some predefined time controls.
| The history of "deep blue" algorithm |
Deep Blue's early development began in 1985 with the ChipTest project at Carnegie Mellon University. The American Chess Grandmaster Joel Benjamin was a member of the development team that was hired by IBM.
Previously, the project was referred to as "Deep Thought" and subsequently renamed to Deep Blue in 1989. Deep Blue defeated world champion Garry Kasparov in its first game on 10 February 1996. Nonetheless, Kasparov resurrected and emerged victorious in three matches while drawing two, despite not achieving a dominance in the game.
Deep Blue was heavily upgraded and defeated the reigning world champion in May 1997, winning the six-match game. Despite the criticism leveled by Kasparov towards IBM for its alleged cheating.
Joel Benjamin
Joel Benjamin is a renowned chess master and chess coach from the United States. He was born on March 11, 1964 in Brooklyn, New York and showed a great passion for chess from an early age.
At the age of seven, Benjamin learned the rules of chess and soon began participating in tournaments. With ambitious training and tireless commitment, he continuously improved his skills and became a serious opponent for experienced players at a young age.
|
How does the "deep blue" algorithm work? System overview |
Deep Blue is a massively parallel system that can search a chess tree with a graphical representation of all possible moves at the start of the game.
The system was developed using an IBM RS/6000 SP computer with 30 nodes (30 processors) and a single-chip chess search engine with 16 chess chips per SP processor. SP has 28 P2SC MHz processor nodes and 135 MHz P2SC processor nodes.
All nodes communicate with each other via high-speed switches and include 1 GB of RAM and 4 GB of hard disk space. Each dark blue chess chip can take between 2 and 2.5 million chess positions per second. For this purpose, it communicates with the host via a microchannel bus.
|
How does system works? The functioning of the SP processors |
"IBM's Deep Blue Chess grandmaster chips"
The Deep Blue algorithm is divided into three layers: Among the many SP processors, one acts as the master, and the other two act as workers. The main processor's job is to search the upper levels of the chess tree and pass the results (often called "leaf positions") to the workers for further investigation.
Now the worker performs additional searches and distributes the leaf positions among the chess pieces.
Finally, the chess pieces extend the search into the last few levels of the game tree. As you do all these things, the speed of your system also changes. For example, tactical positions: when long and engaging movements are required, the Deep Blue algorithm can study 100 million positions per second.
On the other hand, searching for quiet locations can reach 200 million locations per second.
In his match against Garry Kasparov in 1997, the minimum search speed was said to be 126 million positions per second, and the maximum search speed was 330 million positions per second.
| Components of "deep blue" algorithm |
Move Generation:
"Move generation is a concept in chess engine programming that focuses on generating all possible legal moves by a player in a chess position. This is crucial for strategy and tactical analysis within the game, as well as for AI decision making.
Move Generation uses the rules of chess to calculate all of a player's possible moves based on the current position of the pieces on the chessboard and the possible actions each piece can take. This may also include the consideration of special rules such as castling, check and stalemate."
The generated moves can then be analyzed and evaluated by the chess engine to find the best possible strategy for the next move. Move Generation is therefore an important part of AI programming for chess engines and plays a crucial role in improving the AI's playing strength and performance in the game.
Deep Blue algorithms have a variety of features such as generating checks, avoiding movement, and developing specific types of attacks. Chess pieces also support various search extensions, which are possible with the help of move generators.
This is an 8 x 8 combinatorial logic matrix that acts like a silicon chessboard. However, the move generator only makes one move at a time, but calculates all possible moves and uses an arbitration network to select the most important moves.
Evaluation function:
"An evaluation function is an algorithm used to measure the value of a particular situation in a game or other situation. Typically, an evaluation function in artificial intelligence is used to evaluate a chess position or a similar game position and to give the computer an assessment of how good or bad that position is.
The scoring function is used to help the computer make the best possible moves in a given situation. The function is usually based on certain parameters that have an influence on the evaluation of the situation, such as the number of pieces on the board, the position of the pieces, the control of the center, the structure of the pawns, etc. The evaluation function becomes constantly updated as the position in the game changes and new information becomes available."
The rating function consists of quick rating and slow rating. These standard methods are used to prevent the system from performing expensive searches that require simpler approaches.
Quick Score calculates scores based on the location of certain parts over a one-hour cycle. Instead, slow evaluation scans each column of the checkerboard one by one. For example, calculate the value of chess concepts like square control, king safety, pawn structure, majority of pawns, retention, color complex, captured pieces, development, etc.
Search Control:
"Zero-window alpha-beta search, also known as NegaScout, is a variant of the alpha-beta pruning algorithm used in game-playing programs to search through possible moves and determine the best move to make. In zero-window alpha-beta search, the window between alpha and beta is reduced to zero, meaning that the algorithm assumes that the best move is within this range and any move outside of this range is not considered.
The algorithm works by searching through the game tree, evaluating the possible moves at each level of the tree, and keeping track of the alpha and beta values to determine the best move. When the algorithm encounters a node where the beta value is less than the alpha value, it knows that the best move is outside of the current zero-window range and continues the search with an expanded
This technique helps to reduce the number of nodes that need to be evaluated during the search, as it can quickly identify moves that are not worth considering further. Zero-window alpha-beta search can be more efficient than traditional alpha-beta pruning in certain situations, but it requires careful implementation to ensure that the correct moves are being evaluated."
Deep Blue's chess chips include a zero-window alpha-beta search. The best part about the chip is that it simplifies the board design by eliminating the need for a value stack.
However, there are also disadvantages, such as the need for multiple searches in some cases and the lack of a transposition table, which increases the efficiency of the search. The search algorithm requires a move stack (repetition detector) to track previous moves up to the last 32 positions.
Scalability:
"Three dimensions of distributed system scalability design"
Chess chips support the use of external field-programmable gate arrays (FPGAs) to provide access to external transposition tables, advanced lookup control, and additional conditions for evaluation functions.
The main purpose of this feature is to solve the complexity of the mechanism and make it efficient. Motionless search is also supported in this system, but was not used in Deep Blue due to time constraints.
| Is deep blue an AI? |
For the February 1996 and May 1997 races, IBM, the developer of the Deep Blue algorithm, provided detailed coverage of the races, including up-to-the-minute results, commentary and background information, but did not note that the algorithm used AI.
Some experts say that IBM grasps the question as to equate artificial intelligence with human intelligence. And by that measure, it didn't use AI, because how Deep Blue plays chess as compared to a human being is totally different. For example, a Deep Blue algorithm can explore 200 million chess moves per second that no human can do.
Contrary to this belief, some experts believe that Deep Blue deserves to be called an AI due to its minimal mid-game search capabilities and alpha-beta.
Moreover, chess was one of the problems of AI and predates the term artificial intelligence. Many articles have been written on the subject, including Programming a Computer to Play Chess (Chamon, 1950), "Computers and Thought" (Feigenbaum and Feldman, 1963), and "Chess and Samuel's Checkers" (Samuel, 1963).
These ideas are still the foundation of chess programs today, and Deep Blue is no exception. The most important thing is that it beats the current chess champion, so it should be called AI.
| The film about the duel |
The match attracted so much attention around the world that a documentary was made to capture all the excitement. This well-made documentary includes game footage and interviews with Kasparov, chess fans and the Deep Blue team. You'll see everything this duel has to offer: suspense, drama and Kasparov's perspective.
"Game Over: Kasparov and the machine" is a documentary about the legendary world chess champion Garry Kasparov and his historic duel against the chess computer Deep Blue in 1997.
The film sheds light on the background and drama behind this groundbreaking competition that changed the world of chess forever should change. Kasparov fights against the machine and against his own invincibility as he tries to defend the spirit of human creativity and intuition against the sheer computing power of the computer.
Ultimately, the loss to Deep Blue led to controversy and conspiracy theories that continue to this day. “Game Over” also raises questions about the future of artificial intelligence and the role of humans in a digitalized world.
| Deep Blue against Kasparov |
1996 match
| Name | 1 | 2 | 3 | 4 | 5 | 6 | Points |
| Kasparov | 0 | 1 | 1/2 | 1/2 | 1 | 1 | 4 |
| Deep Blue | 1 | 0 | 1/2 | 1/2 | 0 | 0 | 2 |
Game 1
On February 10, the opening move of the match was made with the Sicilian Defense, Alapin Variation, marking the start of a historic game where a chess-playing computer defeated a reigning world champion for the first time in standard tournament conditions and classical time controls.
On February 11, the second match was characterized by Kasparov utilizing a proactive approach, hindering Deep Blue's progress in the Catalan Opening.
Despite lasting 73 moves, the game ultimately ended with Deep Blue's operator conceding defeat as Kasparov held a superior position with three pawns compared to Deep Blue's one, both players having a bishop.
On February 13, like in their previous match, Kasparov chose the Sicilian Defense while Deep Blue once again used the Alapin Variation in response. The match went on for 39 moves and ended in a draw.
The fourth game on February 14 ended in a tie, as Deep Blue's team initially rejected Kasparov's proposal for a draw. The game began with a move from the Queen's Gambit Declined.
February 16. Game 5 proved to be the pivotal moment in the match as the opening transitioned into a combination of the Scotch Game and the Four Knights Game.
The Deep Blue team viewed Game 5 as a source of disappointment as they refused Kasparov's offer for a draw after the 23rd move. This game was the sole victory for the Black pieces in the match.
February 17. The sixth game, like the fourth, transposed to the same line of the Queen's Gambit Declined. The final game was an illustration of just how badly chess engines could play in some positions at the time.
Employing anti-computer tactics and keeping the focus of the game on long-term planning, Kasparov slowly improved his position throughout the mid-game while Deep Blue wasted time doing very little to improve his position.
By the end of the game, Deep Blue's pieces were crammed into its queenside corner, with no moves to make aside from shuffling its king. Kasparov had all the time in the world to finish the route.
Kasparov's next move would probably have been 44.Qe7 to exchange the queens. That would have allowed his pawn, which was about to promote, to advance.
On May 3, 1997, the rematch started with an opening move from Réti and transitioned into the King's Indian Attack.
Kasparov emerged victorious after 45 moves.
May 4. The second game began with the Ruy Lopez opening, Smyslov Variation. Kasparov eventually resigned, although post-game analysis indicates that he could have held a draw in the final position.
After this game Kasparov accused IBM of cheating, by alleging that a grandmaster (presumably a top rival) had been behind a certain move. The claim was repeated in the documentary Game Over: Kasparov and the Machine.
At the time, it was reported that Kasparov missed the draw due to a standing check after Black (Kasparov) 45...Qe3 46.Qxd6 Re8. His friends told him the story the next morning.
They suggested 47.h4 h5! This is because the Black Queen is able to continuously check White. This is possible because Deep Blue moved 44.Kf1 instead of the alternative king move. Regarding the endgame 2 and 44.Kf1 in particular.
Chess journalist Mig Greengard said in Game Over: “The last position here is actually a draw, and one of Deep Blue's last moves was a terrible mistake. Here. He can move his king here or he can move his king here. He chose the wrong place to step.”
Another character in the film, American champion Yaser Seirawan, said: “Computers have made the king a bit vulnerable. And Harry could have threatened not with victory, but with eternal isolation."
The number that surprised Kasparov was 36.axb5! axb5 37.Be4! Then black loses. A more material machine would have received two pawns with 36.Qb6 Rd8 37.axb5 Rab8 38.Qxa6. But after 38...e4! Black launched a strong counterattack.
Deep Blue can also gain material with the move 37.Qb6. Kasparov and others thought this move was 37.Be4! Computers are too advanced to forcefully ignore material gain and assume human intervention during games.
May 6. In the third game on Kasparov decided to use Mieses, an irregular opening 1.d3.
The game then switched to English opening rules. Kasparov believed that if he played an arcane opening, the computer would pull from the introductory book and play the opening worse than if it had used the book.
This is a common tactic today, but was a relatively new idea at the time. Despite these anti-PC tactics, the game ended in a draw.
May 7. The fourth game began with the initial moves defining the Caro–Kann Defense (1.e4 c6); however, the opening then transposed to the Pirc Defense.
Kasparov got into time trouble late in the game.The sub-optimal moves he played in a hurry may have cost him victory. The game ends with a draw.
May 10. The fifth game of the rematch began identically with the first, with a line of the Réti Opening developing into the King's Indian Attack.
As in the fourth game, Deep Blue played a brilliant endgame that secured a draw, when it was looking as if Kasparov would win. It was later discovered that Kasparov had a win beginning with 44.Rg7+.
May 11. The final, deciding game of the rematch was a miniature, by far the shortest of any played during either match. Before the sixth game, the overall score was even: 2½–2½. As in game 4, Kasparov played the Caro–Kann Defense.
Deep Blue made a knight sacrifice which wrecked Kasparov's defense and forced him to resign in less than twenty moves. As Kasparov later recounts, he chose to play a dubious opening in an effort to put Deep Blue out of his comfort zone.
Although the knight sacrifice is a well-known refutation, Kasparov reasoned that an engine wouldn't play the move without a concrete gain.
| Name | 1 | 2 | 3 | 4 | 5 | 6 | Points |
| Kasparov | 1 | 0 | 1/2 | 1/2 | 1/2 | 0 | 2 1/2 |
| Deep Blue | 0 | 1 | 1/2 | 1/2 | 1/2 | 1 | 3 1/2 |
