History of Deep Blue Algorithm

The early development of Deep Blue began in 1985 with the ChipTest project at Carnegie Mellon University. The American Chess Grandmaster Joel Benjamin was a part of the development team that was hired by IBM. Earlier the project was named Deep Thought and was renamed to Deep Blue in 1989. Deep Blue won its first game against world champion Garry Kasparov on 10 February 1996. However, Kasparov made a comeback and won three and drew two matches that didn’t lead deep blue to dominate the game.

Later on, in May 1997, Deep Blue was heavily upgraded and defeated the reigning world champion and won the six-match game. Although Kasparov criticized IBM for cheating.

How Does Deep Blue Algorithm Work?

System Overview

Deep blue is the gigantic parallel system to carry out chess game tree searches - a graphical representation of all the possible moves from the initial stages of the game. The system was developed with 30-node ( 30-processor) IBM RS/6000 SP computer and single-chip chess search engines having 16 chess chips per SP processor. The SP system had 28 nodes with MHz P2SC processors, and 2 nodes with 135 MHz P2SC processors. All nodes communicate with each other using a high-speed switch and contain 1 GB RAM and 4 GB hard disk space. Each chess chip of deep blue is capable of searching 2 to 2.5 million chess positions per second. In order to do that, they communicate with their host via a microchannel bus.

How Does System Works?

The functioning of the SP processors

The Deep Blue algorithm is separated into three layers: out of many SP processors, one acts as a master, and the other two as workers. The master processor's job is to search the top levels of the chess game tree and hand over the results - often called "leaf positions"- to the workers for further examination. Now, workers carry out additional searches and distribute leaf positions to the chess chips. Finally, chess chips extend the search to the last few levels of the game tree.

While performing all these activities, the speed of the system also varies. For example, tactical positions - when long and forcing moves are required, the deep blue algorithm can explore up to 100 million positions per second. On the other hand, for quieter positions, the search could go up to 200 million positions per second. It is said that in 1997 match with Garry Kasparov, the minimum search speed was 126 million positions per second, and the maximum number of the search speed was 330 million positions per second.

Components of Deep Blue Algorithm

• Move Generation: The Deep Blue algorithm has numbers of other functions like generation of checking, check evasion moves, and developing certain kinds of attacking moves. Besides, chess chips also support several search extensions, which is made possible by the move generator. It's an 8 X 8 array of combinatorial logic acting as a silicon chessboard. However, the move generator generates a single move at a time but it calculates all the possible moves and selects the most significant one with the help of an arbitration network.
• Evaluation Function: The evaluation function is composed of fast evaluation and slow evaluation. These standard techniques are used to save the system from running an expensive search where a simple approximation is required. The fast evaluation computes the score on the basis of the position of a particular piece in a single clock cycle. Contrary, the slow evaluation scans the chess board’s each column at a time. For example, it computes the values of chess concepts such as square control, king safety, pawn structure, pawn majority, restraint, color complex, trapped pieces, development, etc.
• Search Control: The Deep Blue chess chip contains the null-window alpha-beta search. The best part of the chip is it averts the need for a value stack, thus simplifying the board design. However, there are some disadvantages too like in some cases it requires multiple searches and the lack of transposition table that increases the search efficiency. The search algorithm needs a move stack-a repetition detector to keep track of the previous moves up to the last 32 positions.
• Extendability: The chess chip also supports the use of external Field Programmable Gate Array (FPGA) to give access to the external transpositional table, complex search control, and additional terms for the evaluation function. The main aim of this function is to address the complexity of the mechanism and make it efficient. Null move search is also supported by this system but due to time constraints, this was never used in Deep Blue.

Is Deep Blue an AI?

During both the matches in February 1996 and May 1997, IBM, the creator of the Deep Blue algorithm provided detailed coverage of the match like showcasing updated results every minute, commentary, and background information, but denied 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 idea, some experts believe that the Deep Blue deserves to be called AI because of its mid-game play and alpha-beta minimax search. Besides this, chess was one of the orthodox AI problems and predates the term artificial intelligence". Lots of papers were written on this subject like Programming a Computer To Play Chess (Shamon, 1950), Computers and Thought (Feigenbaum and Feldman, 1963), Chess and Samuel's checkers program (Samuel, 1963). Even today, these ideas form the basis of chess programs, and Deep Blue is no exception. And above all, it beats the reigning chess champion, thus it should be called an AI.

Conclusion:

The modern AI that we see today is a glimpse of evolution that happened in the past fifty years or so. Be it Deep Blue or Turing Test they all laid the foundation of AI. However, they weren't as successful as people thought them to be in the first place yet constant working on the basic principles of human intelligence simulation worked, and today AI has opened millions of opportunities to the world.