Literature Review
What Is 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.
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.
https://www.professional-ai.com/deep-blue-algorithm.html
AI Techniques
Tree Search
The basic model of chess is that of a Tree Search problem, where each state is a particular arrangement of the pieces on the board and the available actions correspond to the legal chess moves for the current player in that arrangement. An example “slice” of such a tree is given in the following figure:
Once we have modeled the game in this way, we can begin applying our algorithms from this course to the problem!
The Evaluation Function
As put forth in Shannon’s paper, the primary ingredient in a chess-playing program is the evaluation function. Since we can’t look forward all the way to the end of the game and see if a particular move will win (especially since we don’t know what the other player will do during their turns!), we must create a function which takes in a state of the game (in our case, a board arrangement) and boils it down to a real-number evaluation of the state. For example, the function could give higher scores to board states in which the player of interest has more of their pieces on the board than the opponent. In particular, we would probably want the function to assign an extremely high score (perhaps even infinity) to the board arrangement in which the opponent’s king is in checkmate, meaning that the player of interest is guaranteed to win the game.
The Minimax Algorithm
Given an evaluation, all that’s left is a way of actually choosing which move to take. Although looking ahead one step and simply choosing the move which leads to the board arrangement with the highest evaluation score would be a good baseline, we can be even smarter and take into account the actions our opponent could take once we’ve moved. This intuition leads to the “Minimax algorithm”, so-called because we choose the action which minimizes our maximum possible “loss” from making a particular move. Specifically, for each move we could make we look ahead as many steps as our computing power will allow and examine all the possible moves our opponent could make in each of their future turns, given that we’ve made our original move. We then take the maximum “loss” (equivalently, the minimum of our evaluation function) that our opponent could induce for us via their moves, and we choose the move we could make which minimizes this maximum.
Heuristics/Optimizations
Equipped with an evaluation function and an implementation of the minimax algorithm, one can already design an incredibly effective chess-playing program. However, the “big time” programs build even further upon these by implementing “heuristics”, simple rules which can cut down on computation time, along with optimizations of the minimax algorithm, given the specific structure of chess. An example heuristic could be that if a move leads to the player’s king being in checkmate, then the algorithm should not look any farther down that path of the game tree, since we know the player will never want to make that move. A popular optimization of minimax is known as Alpha-beta pruning, wherein any move for which another move has already been discovered that is guaranteed to do better than it is eliminated. For example, in the following tree we do not need to explore any of the paths whose edges are crossed-out, since we’ve already found moves we know will perform better:
Decision Trees
start with a root node, which symbolizes the current state of the game. Every possible move we can make at that point will be the children of that node. Then for each child, there is a new set of possible moves for the opponent. The tree branches out until it covers every possible state in the game and the game ends when it reaches a leaf node.
The very first artificial intelligence algorithms were based on making a brute-force search on the decision trees. The search algorithm tries to reach any leaf node that makes the machine win and makes decisions so that it can reach one of these winning nodes. We shall now see one of these algorithms in action.
Minimax Algorithm
Abstract yourself from the game now and assume we have assigned a score to every possible outcome of the game. The scores are assigned to the leaf nodes of the tree. A positive score indicates that the machine wins and a negative score indicates that you win. So, the goal of AI is to maximize the score and yours is to minimize. Green arrows indicate the turn of the AI (maximizer) and red arrows indicate yours (minimizer) in the tree.
The minimax algorithm is very simple and it is a modified version of depth-first search. The AI (green) will always choose the move with the maximum possible outcome, assuming that its opponent (red) will play optimally and choose the minimum possible outcome all the time. It is intelligent to assume that your opponent plays optimally so that you will be prepared for the worst. Now take a while and follow the tree from the bottom to the top to see the moves each opponent made.
You can see that this algorithm pretty much searches all possible scenarios by brute force. If we assume that b is the branching factor and d is the depth of the decision tree, the algorithm works in O(bᵈ) which exponential.
If you are implementing a Tic-Tac-Toe game, this may not be that bad. After all, there are 9 possible moves on the first turn, 8 in the next, 7, and so on, which will make up to 9! scenarios in total. However, if you were making a chess game, the number of possibilities will grow up by an insane amount! It would take millions of years for any computer to calculate all possibilities.
Do I need to say there must be a better way?
Alpha-Beta Pruning
Alpha-beta pruning is the strategy of eliminating the branches that will not be contributing to the solution. I will explain this with an example. The red lines in the tree below mark the current state of our search. The maximizer (AI) has chosen 9 and 5, which are the maximum reachable values on the corresponding subtrees. At this point, the minimizer currently holds the value 5, which is the smaller one among 9 and 5.
There is still one branch left to search and the first value the depth-first search sees is the value 6. Now we know that whatever maximizer chooses will be at least 6. But we also know that minimizer has chosen 5, which is already smaller than 6. At this point, we no longer need to check the remaining children (1 and 7) because we know for sure that the minimizer will select 5.
The reverse could also be true: If the maximizer has already chosen a value bigger than the value minimizer chose, we wouldn’t need to search the rest of the subtrees. In the tree below, the maximizer has already chosen 5 at the root node. Since -2 is smaller than 5 and anything minimizer chooses will be at most -2, we no longer need to search the rest of the subtrees.
So go ahead, apply this strategy to your entire search and prune the c**p out of the decision tree. There is one last subtree you can prune out on the very right side, which I’m leaving you to check why we can skip it. The final result of the alpha-beta pruning algorithm shall be this:
We pruned the tree quite a bit. Alpha-beta pruning can provide performance optimization up to the square root of the performance of the original minimax algorithm. It may also provide no performance improvement at all, depending on how unlucky you are.
Depth-Limited Search
Even though alpha-beta pruning provides a great amount of performance improvement, searching the entire set of possible scenarios still can be overkill. We can employ intelligent strategies to avoid searching the entire tree and still get very good results.
One such strategy is depth-limited search and it is exactly what it sounds like. Instead of searching the entire tree, you search it to a limited depth that you predefined. For example, you can search the next 5 moves in chess. But in order to do that, you need a deterministic way to score the current state of the game, since you no longer know who wins the game when you reach the end of your search. In order to do that, we will use an evaluation function.
Note: There are other alternatives to the depth-limited search, like iterative deepening but I preferred not to include them in order to keep the story short.
How deep is your search? Get it? That was a joke…
Evaluation Functions
So, you decided to limit your search to the next 5 moves you and your opponent will make in the game. Then you realized that most of the time the game still continues after 5 moves and you are now stuck in this intermediary step. How do you feed the numbers into the minimax algorithm? What you need is an evaluation function.
An evaluation function is a way to deterministically score the current state of the game. If you are playing chess, for example, an evaluation function can be the numeric difference between the number of chess pieces you and your opponent have. The bigger the difference is, the better chance you have.
A better evaluation function can use a weighted calculation in which each piece has a weight depending on how important it is. This will probably produce better results than simply counting them. And an even better one may use the locations on the chessboard in addition to their weights.
How you define your evaluation function is entirely depends on you. Beware this will be the most critical part of your algorithm, though. How good your evaluation function determines the state of the game will greatly affect the success of your algorithm. There are two other things you should be careful when you are writing an evaluation function:
- The function should be deterministic: Given the same state, it should always produce the same result.
- The function should work fast: You will be making a lot of calls to your evaluation function. If it works slow, then your AI will respond slow.
https://medium.com/data-science/algorithms-revisited-part-7-decision-trees-alpha-beta-pruning-9b711b6bf109
https://stanford.edu/~cpiech/cs221/apps/deepBlue.html
Bottom of Form
Classical GOFAI (“Good Old Fashioned AI”) builds on the assumption that intelligence and cognition consist of rule-based manipulations of symbols. In this regard, DeepBlue is a classic AI system par excellence. To calculate the evaluation function of millions of possible positions based on a given starting position (on average more than 100 million positions per second) DeepBlue relied on the expert knowledge of numerous chess grandmasters implemented in the calculation algorithms. As a nonlearning system it was only able to operate within the framework of the given implementation. Such a limitation is typical for a classical GOFAI architecture: DeepBlue was designed for one special purpose, and was therefore unable to perform any other task than playing chess. It is a specialized or „narrow“AI (ANI: artificial narrow intelligence). The more recent AI development almost reverses the original GOFAI doctrine. The ability to self-learn is precisely what opens up the field of flexible general intelligence. In retrospect, it seems hard to understand how the importance of learning could have been downplayed in the early stages of AI. Paradigmatic for this latter view is the position of Noam Chomsky (1980), according to which the human language ability is not otherwise understandable than under the assumption of a presupposed, allegedly innate deep grammar, i.e. a deeply anchored rule competence that is universal to humans. Chomsky considered it out of the question that such an ability could have arisen through imitation or reinforcement learning. Terrence Sejnowski comments on this very clearly:
Thus, for each version of the Alpha series, from AlphaGo to AlphaZero, the respective rules of the games to be learned were unambiguously implemented (Silver et al. 2017). The machine then develops a functional role semantics about the elements and overall setup of the game limited by these pre-determined rules. The systems of the Alpha series have no further grounding. Google Translate or DeepL, on the other hand, already have a rudimentary form of a socially anchored semantics, because these systems acquire an indirect social grounding in the course of their translation learning. After all, the text corpora on the basis of which the systems learn were generated by socially situated speakers, and are therefore parasitic with regard to their social practices. A future AI that combines, for example, the external performance of Google Duplex with the indirect grounding of world knowledge on the basis of Internet data could ultimately become a real part of our social practice of language and, hence, a real part of the language community. There is no convincing reason to assume that such systems would still lack a proper semantic grounding. To conclude: social grounding is as important as causal grounding. To acquire meaning, intelligent systems must not only be coupled to the world, they must also share social practices. The debate about the ultimate theory of meaning and representation is still open in philosophy of mind and language, but for the time being it seems reasonable to assume both types of grounding as independent dimensions of the AI state space.
The State Space of AI 5.1 A Simplified Model Space As a first shot and according to the foregoing sections, the AI state space is to be conceived as a three-dimensional space spanned by the dimensions: • Self-learning (from rule-based to learning-based), • Generalization (from narrow to general AI), • Grounding (the degree of semantic world anchoring). 340 H. Lyre 1 3 We already saw in Sect. 4 that the grounding dimension in fact decomposes into three sub-dimensions: functional role grounding, causal grounding and social grounding. Therefore, the full AI space has more than three dimensions. It is nevertheless instructive to look at the simplified three-dimensional model for a first orientation and to locate the systems discussed in this paper in this space: A classic GOFAI system like DeepBlue is close to the origin (see Fig. 1). Such systems are rule-based rather than learn-based, and almost all of them are narrow AI systems (e.g. DeepBlue is confined to chess). At best, a typical GOFAI system has an internal FRS (as DeepBlue captures the functional roles of chess pieces). AlphaGo sits at a much higher position in the self-learning dimension. From there we reach AlphaGoZero and AlphaZero by successive shifts parallel to the generalization axis. But none of the mentioned systems has a semantic grounding beyond FRS. At best, AI assistance systems such as Google Duplex move into this dimension, albeit still weakly at present. It would be desirable to proceed from the state space topology (dimensionality and neighborhood) to a metric space (to determine distances). Human-level AI is a point of orientation (see Sect. 3.1). HAI has values in all dimensions and can therefore be used to calibrate the coordinate axes. In addition, systems that lie on the extended radial connecting line between origin and HAI (or within a suitably chosen spatial angle range) mark the area of superintelligence or superhuman AI (SAI), as roughly outlined in Fig. 2. A detailed determination of the metric goes beyond the scope of this paper and is a task of further investigations. Let us, instead, focus once again on t
dimensionality. As we already saw, the three-dimensional model offers a first orientation only, but is strictly speaking an approximation. It amounts to a simplified dimensionality reduction. While the generalization dimension is already correctly identified, we saw that the grounding dimension in fact decomposes into three further sub-dimensions. It could be dubbed a “main dimension” and actually represents a subspace of the AI state space. Let us first, however, consider self-learning.
Searching State Spaces
1 A General Search Algorithm How do we search for paths in our implicitly-specified graph (state space)? We have some notion of the current state — the one we’re currently looking at. At the start of the search, the current state is the one associated with the start state. We check whether the current state is a goal state (whether it satisfies the goal condition). If it does then, assuming we’re looking for only one solution path, we can stop. If the current state is not a goal state, we expand the current state. What this means is that we apply operators to this state to generate its successor states. While there might be no successor states (a dead-end) or just one successor state, in general there will be multiple successors. The essence of search is to choose one state for further exploration (it becomes the new current state) and to put the others somewhere in case we want to come back to them, e.g. if the chosen one does not lead to a solution. The data structure in which we keep states that have not yet been explored is called an agenda. Given that there are multiple states waiting on the agenda, yet to be explored, the policy which determines which state to explore next is called the search strategy (or control strategy).
Here’s the algorithm in pseudocode: insert start state onto agenda; while agenda is not empty { currentState := remove from front of agenda i
f currentState satisfies goal test { return the path of actions that led to currentState; } else { successors := states that result from expanding currenState; insert successors onto agenda; } } return fail;
Different search strategies result from different implementations of the line that I have underlined. 2 Search Trees One way to think about the search algorithm is that it is making explicit parts of the implicitly-specified state space: the nodes it actually visits and the edges it actually traverses. The parts of the state space that the search algorithms visits can be shown in the form of a tree, called the search tree. It’s important to distinguish the state space from the search tree. The state space is all the states reachable by sequences of actions from the start state. The search tree is different because: 1
• Some search strategies may leave parts of the state space unexplored. In other words, there may be nodes and edges in the state space that never get visited and so do not appear in the search tree. This, of course, is a ‘good thing’: it improves efficiency, although, if we skimp too much, we may end up missing the solution paths, which, in general, is a ‘bad thing’.
• Some search strategies may re-explore parts of the state space. This can happen when two or more paths in the state space lead to the same node.
Unless steps are taken to deal with this, then some nodes in the state space may get visited and expanded more than once, and so they appear in the search tree more than once. This is, in general, a ‘bad thing’, although the cost of eliminating it can be high. (A common special case of this is when the state space is cyclic. Unless steps are taken to deal with cycles, the search tree may then be infinite.) Let’s explore the second bullet point in more detail. 3 Avoiding Re-exploration Strictly, we cannot draw search trees unless we know what the search strategy is. But, to illustrate the second bullet point above, without getting too bogged down in wondering what the exact search strategy is (i.e. how to decide what to visit next), in the lecture we will draw possible search trees for the following two state spaces: start node start node A B C D E F A B C
To avoid re-exploration of parts of the state space, we must be more selective about which states we add to the agenda. Some of the successors of the current state should be discarded. There are various ways of deciding which to discard, and they vary in how effective they are in avoiding re-exploration and in how much time & space they cost us. (Sometimes it might be better to allow some re-exploration, rather than pay the price of eliminating it). Three options for avoiding (some or all) re-exploration are common:
• Discard any successor that is the same as the current node’s parent.
• Discard any successor that is the same as another node on that path.
• Discard any successor if it is the same as any previously generated node. Class Exercise. How effective at avoiding re-exploration are these three options? What do they cost in time & space? [Advanced point. In fact, I’m oversimplifying this third option. (Ignore this if it makes no sense.) From the above, you might assume that if the newly-generated node is the same as a previously-generated node, we always throw away the new node. But, this is not correct. If the cost of the path to the new node is less than the cost of the path to the previously-visited node, then we should not throw away the new node (because the path to it is cheaper.) To handle all of this properly makes the algorithm so complicated and its costs (both space and time) so much higher that this option is hardly ever implemented. If you want to read a proper description of such an algorithm, consult a textbook such
1.2 State Spaces and Search Problems
In order to create a rational planning agent, we need a way to mathematically express the given environment in which the agent will exist. To do this, we must formally express a search problem – given our agent’s current state (its configuration within its environment), how can we arrive at a new state that satisfies its goals in the best possible way? A search problem consists of the following elements:
- A state space – The set of all possible states that are possible in your given world
- A set of actions available in each state
- A transition model – Outputs the next state when a specific action is taken at current state
- An action cost – Incurred when moving from one state to another after applying an action
- A start state – The state in which an agent exists initially
- A goal test – A function that takes a state as input, and determines whether it is a goal state
Fundamentally, a search problem is solved by first considering the start state, then exploring the state space using the action and transition and cost methods, iteratively computing children of various states until we arrive at a goal state, at which point we will have determined a path from the start state to the goal state (typically called a plan). The order in which states are considered is determined using a predetermined strategy. We’ll cover types of strategies and their usefulness shortly.
Before we continue with how to solve search problems, it’s important to note the difference between a world state, and a search state. A world state contains all information about a given state, whereas a search state contains only the information about the world that’s necessary for planning (primarily for space efficiency reasons). To illustrate these concepts, we’ll introduce the hallmark motivating example of this course – Pacman. The game of Pacman is simple: Pacman must navigate a maze and eat all the (small) food pellets in the maze without being eaten by the malicious patrolling ghosts. If Pacman eats one of the (large) power pellets, he becomes ghost-immune for a set period of time and gains the ability to eat ghosts for points.
Let’s consider a variation of the game in which the maze contains only Pacman and food pellets. We can pose two distinct search problems in this scenario: pathing and eat-all-dots. Pathing attempts to solve the problem of getting from position (x1,y1) to position (x2,y2) in the maze optimally, while eat all dots attempts to solve the problem of consuming all food pellets in the maze in the shortest time possible. Below, the states, actions, transition model, and goal test for both problems are listed:
Pathing
- States: (x,y) locations
- Actions: North, South, East, West
- Transition model (getting the next state): Update location only
- Goal test: Is (x,y)=END?
Eat-all-dots
- States: {(x,y) location, dot booleans}
- Actions: North, South, East, West
- Transition model (getting the next state): Update location and booleans
- Goal test: Are all dot booleans false?
Note that for pathing, states contain less information than states for eat-all-dots, because for eat-all-dots we must maintain an array of booleans corresponding to each food pellet and whether or not it’s been eaten in the given state. A world state may contain more information still, potentially encoding information about things like total distance traveled by Pacman or all positions visited by Pacman on top of its current (x,y) location and dot booleans.
1.2.1 State Space Size
An important question that often comes up while estimating the computational runtime of solving a search problem is the size of the state space. This is done almost exclusively with the fundamental counting principle, which states that if there are n variable objects in a given world which can take on x1, x2, …, xn different values respectively, then the total number of states is x1 · x2 · … · xn. Let’s use Pacman to show this concept by example:
Let’s say that the variable objects and their corresponding number of possibilities are as follows:
- Pacman positions – Pacman can be in 120 distinct (x,y) positions, and there is only one Pacman
- Pacman Direction – this can be North, South, East, or West, for a total of 4 possibilities
- Ghost positions – There are two ghosts, each of which can be in 12 distinct (x,y) positions
- Food pellet configurations – There are 30 food pellets, each of which can be eaten or not eaten
Using the fundamental counting principle, we have 120 positions for Pacman, 4 directions Pacman can be facing, 12⋅12 ghost configurations (12 for each ghost), and 2⋅2⋅…⋅2=230 food pellet configurations (each of 30 food pellets has two possible values – eaten or not eaten). This gives us a total state space size of 120⋅4⋅122⋅230.
1.2.2 State Space Graphs and Search Trees
Now that we’ve established the idea of a state space and the four components necessary to completely define one, we’re almost ready to begin solving search problems. The final piece of the puzzle is that of state space graphs and search trees.
Recall that a graph is defined by a set of nodes and a set of edges connecting various pairs of nodes. These edges may also have weights associated with them. A state space graph is constructed with states representing nodes, with directed edges existing from a state to its children. These edges represent actions, and any associated weights represent the cost of performing the corresponding action. Typically, state space graphs are much too large to store in memory (even our simple Pacman example from above has ≈1013 possible states, yikes!), but they’re good to keep in mind conceptually while solving problems. It’s also important to note that in a state space graph, each state is represented exactly once – there’s simply no need to represent a state multiple times, and knowing this helps quite a bit when trying to reason about search problems.
Unlike state space graphs, our next structure of interest, search trees, have no such restriction on the number of times a state can appear. This is because though search trees are also a class of graph with states as nodes and actions as edges between states, each state/node encodes not just the state itself, but the entire path (or plan) from the start state to the given state in the state space graph. Observe the state space graph and corresponding search tree below:
The highlighted path (S → d → e → r → f → G) in the given state space graph is represented in the corresponding search tree by following the path in the tree from the start state S to the highlighted goal state G. Similarly, each and every path from the start node to any other node is represented in the search tree by a path from the root S to some descendant of the root corresponding to the other node. Since there often exist multiple ways to get from one state to another, states tend to show up multiple times in search trees. As a result, search trees are greater than or equal to their corresponding state space graph in size.
We’ve already determined that state space graphs themselves can be enormous in size even for simple problems, and so the question arises – how can we perform useful computation on these structures if they’re too big to represent in memory? The answer lies in how we compute the children of a current state – we only store states we’re immediately working with, and compute new ones on-demand using the corresponding getNextState, getAction, and getActionCost methods. Typically, search problems are solved using search trees, where we very carefully store a select few nodes to observe at a time, iteratively replacing nodes with their children until we arrive at a goal state. There exist various methods by which to decide the order in which to conduct this iterative replacement of search tree nodes, and we’ll present these methods now.