To date, Deep Blue is the most powerful chess-playing
computer ever developed. But what makes Deep Blue so great at playing chess?
How does it so accurately "choose" its next move from a list of thousands of
possible options? And why is it so much better than other computer chess
'players'? The answer lies in its unique combination of innovate software
engineering and massive parallel processing power.
At the heart of Deep Blue's ability to play chess is its evaluation function.
The evaluation function is an algorithm that measures the "goodness" of a
given chess position. Positions with positive values are good for White, and
conversely, positions with negative values are good for Black. If the overall
score is negative, for example, this means that Black has the advantage.
Deep Blue's evaluation function looks at four basic chess
values: material, position, King safety and tempo. Material is based on
the "worth" of particular chess pieces. For example, if a pawn is valued at
1, then the rook is worth 5 and the Queen is valued at 9. The King, of
course, is beyond value because his loss means the loss of the game.
The simplest way to understand position is by looking at your pieces and
counting the number of safe squares they can attack. King safety is a
defensive aspect of position. It is determined by assigning a value to the
safety of the King's position in order to know how to make a purely defensive
move. Tempo is related to position but focuses on the race to develop control
of the board. A player is said to "lose a tempo" if he dillydallies while the
opponent is making more productive advances.
Deep Blue is not only the finest chess-playing computer in the world, it is
also the fastest. This makes perfect sense, because history has proven that
the fastest computers conduct the most extensive searches into possible
positions. More searches gives the computer a wider array of moves to choose
from and therefore a greater chance of choosing the optimum move.
Deep Blue employs a system called selective extensions to examine chessboard
positions. Selective extensions allow the computer to more efficiently search
deeply into critical board arrangements. Instead of attempting to conduct an
exhaustive "brute force" search into every possible position, Deep Blue
selectively chooses distinct paths to follow, eliminating irrelevant searches
in the process.
Deep Blue uses "live" software that can actually generate up to 200,000,000
positions per second when searching for the optimum move. The software
begins this process by taking a strategic look at the board. It then computes
everything it knows about the current position, integrates the chess
information pre-programmed by the development team, and then generates a
multitude of new possible arrangements. From these, it then chooses its best
possible next move.
Deep Blue's extensive searches make full use of the computer's massively
parallel design. "At the search level, you're saying 'OK, here's the
position. I need to search all the moves," says Joe Hoane, the Deep Blue
development team member in charge of software. "And you go search all the
moves, all at the same time, preferably on a bunch of different computers."
The software inside of Deep Blue is one all-inclusive program written in C,
running under the AIX operating system. Deep Blue utilizes the IBM SP
Parallel System called MPI. "It's a message-passing system," says Hoane. "So
the search is just all control logic. You're passing control messages back
and forth that say, well, what am I doing? Did you finish this? OK, here's
your next job. That kind of thing at the SP level."
The latest iteration of the Deep Blue computer is a 32-node IBM RS/6000 SP high-performance computer,
which utilizes the new Power Two Super Chip processors (P2SC). Each node of
the SP employs a single microchannel card containing 8 dedicated VLSI chess
processors, for a total of 256 processors working in tandem. The net result
is a scalable, highly parallel system capable of calculating 60 billion
moves within three minutes, which is the time allotted to each player's move
in classical chess.