Advance and Be Mechanized

Introduction

The purpose of this article is to present the past and current state of computer chess and we will try to shed some light into its future. We will also give technical explanations of how a chess computer works, based on Deep Blue, the most famous and well-documented chess machine. We will discuss as well the importance that computer chess and in particular Deep Blue has brought to the Artificial Intelligence field.

The motivation to study computer chess lies in the unusual position of computer chess within the artificial intelligence world. Like most AI problems, chess requires a program which will display seemingly intelligent behavior in a limited, artificial world. Unlike most AI problems, the programmers do not get to make up the rules of this world. In addition, there is a very rigorous procedure to test the intelligence of a chess program: playing games against humans. Computer chess is one area where the usually disparate worlds of AI and high-performance computing meet.

It can also be argued that game-playing can be a good problem for AI research because of the following reasons:

* All the information is available.
* It is non-trivial.
* The artificial system needs to display “human-like” intelligence.
* Some games such as chess are very complex.
* It requires decision-making within a time limit.
* It’s more realistic than other search problems.
* Games are played in a controlled environment.
* We can easily replicate situations to do experiments or evaluate research systems .
* We can compare humans and computers directly.
* We can evaluate percentage of wins/losses to quantify performance.

Brief History of Computer Chess

In 1769 Hungarian Baron Wolfgang von Kempelen built a chess playing machine for the amusement of the Austrian Queen. It was a purely mechanical device, shaped like a Turk (and hence the nickname that it acquired “The Turk”). The machine was a fake, as a chess player was hidden inside the machine.

A chess-playing computer had been suggested as early as 1864, and the first machine able to carry out a “program” was invented in Spain in 1914 by the engineer Leonardo Torres-Quevedo and called Ajedrecista for the Spanish word for chess, ajedrez. [1] (Note: although this book was written by a chess historian, the machine was really built in 1912 but not exhibited until 1914 in Paris). The Ajedrecista used electromagnets under the board plays flawless endgame with rook and king against lone king.

Around 1950, mathematician Alan Turing specified the first chess program for chess. There were no computers yet, so he devised a “paper computer” where himself carried out the calculations of the program.

About the same time, Claude Shannon, another mathematician from the Bell Laboratories, described how to program a computer. He differentiated between an "A-Strategy" which looks at all continuations until a fixed depth and a "B-Strategy" which cuts off certain lines. Today most strong programs implement some sort of asymmetrical search, using “extensions” (continuations of the search in promising moves) over a “brute-force” approach (Shannon’s A-strategy).

An important breakthrough to game theory came in 1958 when three scientists of the Carnegie-Mellon University in Pittsburgh (Newell, Shaw and Simon) made an important discovery. The search tree could be greatly pruned without affecting the final results. They called this the alpha-beta algorithm. This is a purely mathematical technique and works for all zero-sum games, not just chess. Alpha-beta produces exactly the same result as a full search, while looking at only about the square root of the number of positions otherwise required. This meant that the early computers were able to look five and six ply ahead. In the seventies the world's fastest computers were able to search seven ply deep and had achieved a respectable playing strength.

In 1968 International Master David Levy made a $3,000 bet that no chess computer would beat him in 10 years. The original bet was with John McCarthy, a distinguished researcher in Artificial Intelligence. Levy collected his 10 year bet by defeating CHESS 4.7 in Toronto with the score of 3 wins and one draw. The drawn game was the first time a computer drew an international master. [2]

Ken Thompson (one of the creators of UNIX) and a colleague at the Bell Laboratories decided to build a special purpose machine. The machine they called "Belle" was able to search at about 180,000 positions per second (the super-computers at the time were doing 5000 positions). Belle could go down eight to nine ply in tournament games, which enabled it to play in the master category. It won the world computer chess championship and all other computer tournaments from 1980 to 1983, until it was superseded by giant Cray X-MPs costing a thousand times more. Belle was the first chess program to attain a Master's rating in 1983.

In the middle of the eighties Prof. Hans Berliner, a computer scientist at the Carnegie-Mellon university, picked up where Ken Thompson had left off. Berliner, who had also been world correspondence chess champion, built a hardware-driven chess machine called HiTech. He and his graduate student Carl Ebeling developed a hardware move generator chip. With 64 chips in parallel HiTech narrowly missed winning the world computer chess championship in 1986 (it was won by a Cray).

In 1985, Hsu and other classmates in Carnegie-Mellon started working on a new chess chip design and some new ideas in the tree search (like the selective extensions) [3]. This team, with some changes in its members later went to IBM to create Deep Blue, the system that beat the chess world champion Garry Kasparov in the 1997 tournament. Contrary to widespread belief, Hsu and his team never worked under Prof. Berliner.

The Machine that Beat the World Champion: Deep Blue

Deep Blue is the chess machine that defeated the World Chess Champion Garry Kasparov in a six-game match in 1997. Many of the facts described here are taken from probably the best source about Deep Blue: the book written by its main contributor Hsu: Behind Deep Blue [3]. This book however doesn’t go deeply into technical particulars, but there are a few detailed papers available, and we have studied an extensive one by the builders of Deep Blue [4] as well as others like [5].

Books that describe Deep Blue in a less technical fashion are [6], [7] and [8].

Motivation and Philosophy

The initial motivation and philosophy for developing Deep Blue is clearly stated by Hsu:

Before us, many pioneers had made their contributions to the “Computer Chess Problem”. In 1949, Claude Shannon made his proposal on how to program a computer to play chess. Since then, thousands of computer scientists, engineers, hobbyists, chess players, and even commercial organizations had worked on the problem. Some wanted to use chess as an experimental tool to find out how human intelligence worked. “If one could devise a successful chess machine, one would seem to have penetrated to the core of the human intellectual endeavor,” said Allen Newell in one of the early computer chess papers. Other people viewed chess as a clear-cut, well-defined example of a complex problem. “Solving” chess could conceivably provide new techniques to solve other complex problems.

We approached the problem from a different direction. We, or at least I, viewed the problem as a purely engineering one. Since the late 1970s, it had been established that chess computers became stronger as their hardware speed increased. By 1985, when I started my small project that eventually become Deep Blue, the extrapolation from the experimental data indicated that a one thousandfold increase in hardware speed would be sufficient to produce a World Champion-class chess machine. Our project began with a simple goal, namely, to find out whether a massive increase in hardware speed would be sufficient to “solve” the Computer Chess Problem.

He goes to great lengths in his book to emphasize that he saw Deep Blue as a technical challenge and as purely an engineer one. He didn’t give too much thought about the philosophical or AI implications, writing strong assertions like this one:

A frequently-asked question about Deep Blue is, “Is it intelligent?” Garry’s accusations of cheating both during and after the 1997 match confirmed that Deep Blue passed the chess version of the Turing test. But Deep Blue is not intelligent, it is only a fine-crafted tool that exhibits intelligent behaviour in a limited domain. Garry lost the match, but he was the player with the real intelligence-Deep blue would never be able to come up with the imaginative accusations.

Hsu is also bothered about how the media and many authors portrayed the match against Kasparov as a “man vs. machine” event. He insists that the games should be viewed as man as a performer (the chess player) against man as engineer (himself or his team). The irony is that the “man vs. machine” catchphrase is the most widespread idea

Deep Blue and its Significance to AI

Hsu narrates [3] that when he came to Carnegie Mellon, two thirds of the school were basically devoted to AI, and the rest to electronic engineering. He started to work on a set of computer chips with other students because of their dislike of AI, and in his book he mentions several times his low esteem for AI, like for instance in this excerpt where he talks about his team mates:

Andreas had a very low opinion of AI research in general. Mike did not share the same opinion at first but, after he split with his first advisor, both he and Andreas referred to AI as bullshit. I did not go to the same extreme, but I had seen some so-called research in AI that really deserved the bullshit label.

Again we find ironical that some of the authors of Deep Blue have a low consideration for AI, while the machine they built is a showcase for AI. For instance in the main Internet newsgroup for AI, there’s a FAQ about what has AI achieved so far, and in the list they provide as answer they give Deep Blue as an example.

As a counterpoint, a paper by Dennis DeCoste [9] argues that the Kasparov vs. Deep Blue match has great significance to AI in several ways, and that the development of Deep blue represents a legitimate and in some ways even a role model, example of the future of AI research.

And also Joe Hoane, a member of the Deep Blue team expresses his opinions in the conference where the previous paper was presented, about the significance for AI of the famous match [10]:

In Hoane’s opinion, the significance of Deep Blue for AI was that it begins to address some of the “easier problems” in the field, related to the need for an effective representation of knowledge about a single problem. In particular, Deep Blue shows how the representation of domain knowledge is “vastly modified” as the result of the kind of computational resources allowed.

Hoane’s concluding remarks were optimistic for the field of AI: in his words, “AI has a green light. Many of the things which have seem impossible may not be”.

In the official IBM’s web site dedicated to Deep Blue [11], the question “Does Deep Blue use artificial intelligence?” is answered:

The short answer is "no." Earlier computer designs that tried to mimic human thinking weren't very good at it. No formula exists for intuition. So Deep Blue's designers have gone "back to the future." Deep Blue relies more on computational power and a simpler search and evaluation function.

The long answer is "no." "Artificial Intelligence" is more successful in science fiction than it is here on earth, and you don't have to be Isaac Asimov to know why it's hard to design a machine to mimic a process we don't understand very well to begin with. How we think is a question without an answer. Deep Blue could never be a HAL-2000 if it tried. Nor would it occur to Deep Blue to "try."

But afterwards in the same answer they acknowledge that it operates much like a turbocharged "expert system".
So as a conclusion we can see that there are many different opinions and we believe that at least Deep Blue has brought a healthy debate over its role in the AI field.

Description and History

Deep Blue is a computer chess system that combines hardware and software. It is a series of machines rather than a single system, but the most distinct versions are two: one which lost to Kasparov in 1996 and the one who defeated him in 1997.

The predecessors of Deep Blue are ChipTest and Deep Thought, developed at Carnegie Mellon University in the 1980s. In 1988 Deep Thought was the first machine to beat a Grandmaster in tournament play. These systems used a single-chip chess move generator that would search around 500,000 positions per second (ChipTest) to 700,000 positions per second (Deep Thought).

In 1989-90, part of the Deep Thought team (Anantharaman, Campbell, Hsu) was hired by IBM and they moved to the T.J. Watson Research Center. In late 1990, Joe Hoane replaced Thomas Anantharaman in the group. Deep Thought 2, also known as Deep Blue prototype, was the first result of this effort. Although the primary purpose of the system was as an intermediate step towards Deep Blue, Deep Thought 2 played in a number of public events from 1991 through 1995, including victories in the 1991 and 1994 ACM Computer Chess Championships, and a 3-1 win against the Danish national team in 1993.

The group at IBM decided to change the name of the system from Deep Thought to Deep Blue. According to Hsu, apparently when people heard of “Deep Thought” they were thinking of “Deep Throat”, a character in Nixon’s Watergate scandal to some, and a porno movie to others. So they looked for a more suitable name.

Deep Blue I was based on a single-chip chess search engine, designed over a period of three years. It ran on a 36-node IBM RS/6000 SP computer, and used 216 chess chips. Each chip searched about 1.6 - 2 million chess positions per second for a total search speed of 50 - 100 million chess positions per second. Deep Blue I played only six games under tournament conditions, all in the 1996 match with Kasparov that he won with a 4 - 2 score.

Deep Blue II was a significant improvement of Deep Blue I. First, a new chess chip was designed with a completely redesigned evaluation function, going from around 6,400 features to over 8,000. Many new features were added in response to specific problems detected in the 1996 Kasparov games, as well as in test games again Benjamin. The new chip also added hardware repetition detection, a number of specialized move generation modes (e.g., generate all the moves that attack the opponent’s pieces), and some improvements that increased the per chip search speed to 2-2.5 million positions per second. The second major change was to more than double the number of chess chips in the system, and use the new generation of SP computer.

Deep Blue defeated Garry Kasparov in the 1997 match by 3.5 – 2.5. For this victory the Deep Blue team was awarded the Fredkin prize for beating the human world champion in a regulation match.

The success of Deep Blue in the 1997 match was not the result of any one single factor. The large search capability, non-uniform search, and complex evaluation functions were all critical. However other factors also played a role, like the extended book and the evaluation tuning.

Deep Blue Characteristics

What sets apart Deep Blue from other chess systems is the massive use of parallel search and the off-loading of part of the search onto specialized chess chips. In this section we explore more these differences between traditional ideas in chess programs and Deep Blue.

From the point of AI, the most interesting problem would be the huge search space that is generated in a chess game. The average search tree is about 35100 nodes, since there are around 35 possible moves for a given position (average branching factor) and each player makes around 50 moves in an average game. The last advances in computer chess search algorithms are described in detail in [12], where topics like selective forward pruning are explained.

Deep Blue is organized in three layers. One of the SP processors is designated as the master, and the remainders as workers. The master searches the top levels of the chess game tree, and then distributes “leaf” positions to the workers for further examination. The workers carry out a few levels of additional search, and then distribute their leaf positions to the chess chips, which search the last few levels of the tree.

The most important characteristics that Deep Blue introduced are:

1. Large searching capability. Previous research in game tree search typically dealt with systems that searched orders of magnitude fewer positions that Deep Blue. It’s not clear what’s the best way to take advantage of this greater search power, but the Deep Blue search was guided by two principles:
1. The search should be highly non-uniform. It is well known that strong human players are able to calculate well beyond the depth reachable by a uniform searcher of any conceivable speed.
2. The search should provide “insurance” against simple errors, so all move sequences are explored to a reasonable minimum depth.
2. Hardware evaluation. The Deep Blue evaluation function is implemented in hardware and the time to execute is a fixed constant, unlike evaluation functions implemented in software that perform slower as it gets more complex.
3. Hybrid software/hardware search. The Deep Blue search combines a software search, implemented in compiled C code on a general purpose CPU, with a hardware search, encoded in silicon on the chess chips. The software search is extremely flexible, and can be changed as needed. The hardware search is parameterized, but the general form of the search is fixed.
4. Massively parallel search. Deep Blue is a massively parallel system, with over 500 processors available to participate in the game tree search.

The Chess Chip

The chess chip tasks are divided in three: the move generator, the evaluation function and the search control.

The move generator is implemented in an 8 x 8 array of combinatorial logic, which is effectively a silicon chessboard. A hardwired finite state machine controls move generation. The move generator computes all the possible moves and selects one via an arbitration network.

A good move ordering, preferably as close to best-first as possible, is an important consideration for efficient search in game trees.

The ordering of moves is made with a heuristic, considering special moves first, for example:

* Captures.
* Moving least valuable piece for capture.
* Moves to safer squares.
* Moves of pieces left unguarded.
* Moves to a central square.

An evaluation function is essentially a sum of features values that represent chess concepts, returning the score of the current position. Usually a signed integer is used to keep the score, being positive (adding) for the white side and being negative (subtracting) for the black side. A baseline is used, typically assigning a value like 100 or 200 to represent the material value of a pawn.

The features or functions that make up the evaluation function are weighted in a linear combination fashion to represent the relative importance of each feature. Chess programs are tuned-up by Grandmasters (like Benjamin and Illescas did for Deep Blue) that can study special positions and determine which side is better and why, thus adjusting the weights of the evaluation function members.

In simpler chess programs the evaluation function is static (the weights don’t change during a game), but more sophisticated systems (like Deep Blue) use static values set at the beginning of the game and also dynamic values that are scale during the search, based on the value and type of pieces on the board at evaluation time. For example, the weight for the king safety feature becomes less important in a node that is several moves away if we see that in that branch the queens are going to be exchanged.

The evaluation function implemented in the Deep Blue chip is composed of a
”fast evaluation” and a “slow evaluation” [13]. This is a standard technique to skip computing an expensive full evaluation when an approximation is good enough. The fast evaluation, which computes a score for a chess position in a single clock cycle, contains all the easily computed major evaluation terms with high values. The most significant part of the fast evaluation is the “piece placement” value (the sum of the basic piece values with square-based location adjustments). Positional features that can be computed quickly are also part of the fast evaluation. The slow evaluation scans the chess board one column at a time, computing values for the rest of chess concepts like square control, pins, king safety, pawn structure, development, trapped pieces etc. The features recognized in both evaluation functions have programmable weights, allowing their relative importance to be adjusted.

The search control part of the chip uses a number of state machines to implement null-window alpha-beta search. The advantage of null-window search is that it eliminates the need for a value stack, simplifying the hardware design. The disadvantage is that in some cases it is necessary to do multiple searches, for example when an exact score is needed.

Opening and Extended Book

The opening book in Deep Blue was created by hand, primarily by Grandmaster Joel Benjamin, with assistance from Grandmasters Nick de Firmian, John Fedorowicz and Miguel Illescas. The book consisted of only about 4,000 positions, because the team was very confident in the extended book. All the positions had been checked by Deep Blue in overnight runs, and the openings were chosen to emphasize positions that Deep Blue played well, like tactically complex openings. Prior to a game, a particular repertoire was chosen for Deep Blue, based on the match situation and the previous experience playing with that color. Curiously, none of the Kasparov-specific preparations arose in the 1997 match.

The extended book in Deep Blue is a mechanism that allows a large Grandmaster game database to influence and direct Deep Blue’s play when the game has stepped out of the opening book. The basic idea is to summarize the information available at each position of the 700,000 game database, and use the summary information to drive Deep Blue in the consensus direction of chess opening theory.

M. Campbell developed an ad hoc function that combines heuristic factors (like number of times a move has been played, strength of the player that play that move, outcome of the game, recentness of the move) in a nonlinear way to produce a scalar value as output.

The value of this output or bonus can be as high as half a pawn in some situations.

Endgame Databases

The endgame databases in Deep Blue includes all chess positions with five or fewer pieces (including pawns) on the board, as well as selected positions with six pieces that included a pair of blocked pawns. Each of the 30 general purpose processors in the Deep Blue system replicated the 4-piece and important 5-piece databases on their local disk. The remaining databases were duplicated on two 20-GB RAID disk arrays, and were available to all the general purpose processors through the SP switch.

The endgame databases did not play a role in the matches against Kasparov. In the 1997 match, only game 4 approached an endgame that required access to the databases, but the chess chips had recognized that the endgame that would have arisen was a draw.

Time Control

The Deep Blue – Kasparov games were played at a speed of 40 moves every two hours (per player), which is a tournament standard. The time control mechanism in Deep Blue is simple. Before each search two time targets are set. The first is the normal time target, set to approximately the time remaining to the next time control divided by the moves remaining, and allowing also for a time buffer to handle technical problems. The second time target is the panic target, roughly one third of the remaining time. Under a few conditions (like if the current evaluation has dropped sharply) Deep Blue goes into “panic mode” and expends more time trying to find a good move. In the 1997 match against Kasparov, Deep Blue went into panic mode only once.

Present and Future of Computer Chess

After the 1997 loss of Kasparov to Deep Blue there were some sense of restless; at the beginning it seemed like everybody thought that the “man vs. machine” contest was over, with machine being the clear winner. But then some voices started to contest this impression. For example, as Hallman relates [1]:

The chess world was out to correct the popular notion that Kasparov’s loss to Deep Blue meant that computers had conquered the game. IBM had canceled the Deep Blue program, but Kasparov arranged to play a program called Deep Junior, and Kramnik played a program called Deep Fritz in a match billed as “The Brains in Bahrain”. “I think that in the public eye the computer is already stronger that any chess player”, Kramnik said. “I am very eager to win and to prove that this is not the case.” He took a 1-3 lead against Deep Fritz, then lost two in a row, committing in the first game what was arguably the worst blunder ever made by a sitting world champion, and trying a doomed sacrifice in the second. “I was seduced by beauty,” Kramnik said. The match was drawn, and a month later, Kasparov played a similar match against Deep junior. Another draw.

To summarize the current state of computer chess, and to grasp their power, we can come down from the world of parallel supercomputers to the world of domestic PCs. Today's top PC programs like Fritz and Junior run at 500,000 and more positions per second. They are a match for all but the top 100 players in the world. In rapid chess only the top dozen or so can compete, in blitz chess (5 minutes per player per game) probably only two or three players could survive.

Chess and the Internet

Chess and computers have also been deeply affected by the advent of the Internet, and the network of networks is changing already the chess landscape. Most chess games are now played over the Internet, where every chess player, from aficionado to Grandmaster comes to play. The fast-paced nature of Internet has tilted the pace of the game from the standard 2*2 hours per game to blitz games (2*5 minutes) or even the craziest “bullet” games (2*1 minute games).

Internet is the ideal place to play chess; all the organization of the games (clock settings, enforcing the rules, setting of new ratings etc) is automatically taken care of.

Some new forms of chess (with different rules) have become popular. For example a form of “wild chess” is Fisher’s “randomchess”, in which from time to time the computer shuffles the positions of the pieces in the first row of the board. This is clearly only possible because a computer is present. Some other types of time control are also easily implemented, like for example the time arrangement that besides the fixed time gives the player extra time (like 5 seconds) per move.

Some other rules are also changed. We were surprised when we were playing a blitz game on ICC (Internet Chess Club, the most important Internet chess site) and having only a King, the opponent ran out of time. In all our “real-world” games, that means that we would win, but the computer server declared the game a draw since we didn’t have material to mate.

There are unofficial tournaments played over the Internet but the only hurdle to have real tournaments is the possibility of cheating. We think that if a reliable identification system (a biometric card for example) is implemented, then official chess tournaments over the Internet could become a reality. Although there are other problems with cheating besides authentication of identity, like for example, a player could consult a book or a computer in the middle of the game. Perhaps playing fast chess (like blitz) could inhibit this, because is hard to consult another source while you have to move so fast. Having a video-conference type of camera (webcam) doesn’t resolve the issue either, because players wouldn’t be allowed to leave their seats, or they could still run a program in the computer they are playing on.

The Kasparov-Fritz Match

As recent as this month (November 2003) we could witness the last “man vs. machine” episode, sponsored by X3D, a tech company that created the event to promote its 3D vision product. The match paired one of the strongest chess programs (the German Fritz) with the still strongest chess player in the world, Garry Kasparov.

Unfortunately some years ago there was a schism in the chess world and at least two organizations claim to have the World Champion, but still everybody knows that Kasparov is the strongest player on the world.

The good thing about this short match (only four games, too short to reach conclusions when two Grandmasters are playing) is that it shows some of the stereotypical strengths and weaknesses of human and computer when they play chess.

The match was a draw 2 – 2, with two draws and two wins for each player.

In the game that Fritz won, Kasparov basically blundered badly when he was running out of time and Fritz saw easily the winning continuation. So we see here the human weakness of overseeing something that is just one move away, something that no computer program would do.

In the game that Kasparov won, Fritz couldn’t see the long-term plans that Kasparov was making, so the machine played very passively in the closed position. Any intermediate chess player could tell the guidelines of what the computer side should do in that kind of situation, but Fritz just couldn’t see it in its search, nor could it understand the type of position it was playing. Basically Kasparov overran one side of the board for an easy win.

References

[1] J. C. Hallman, The chess artist, St. Martin Press, 2003.

[2] David Lavy, Chess and Computers, Batsford, 1976.

[3] Feng-Hsiung Hsu, Behind Deep Blue, Princeton university Press, 2002.

[4] Murray Campbell, A. Joseph Hoane Jr., Deep Blue. Feng-Hsiung Hsu. Artificial Intelligence 134, 2002.

[5] Murray Campbell, Knowledge Discovery in Deep Blue., Communications of the ACM. November 1999 / Vol. 42, No. 11.

[6] Bruce Pandolfini, Kasparov and Deep Blue: The Historic Chess Match Between Chess and Machine, Fireside, 1997.

[7] M. Newborn, Kasparov Cersus Deep Blue: Computer Chess Comes of Age, Springer Verlag, 1996.

[8] M. Newborn, Deep Blue, Springer Verlag, 2000.

[9] Dennis DeCoste, Deep Blue Versus Kasparov: The Significance for Artificial Intelligence. Papers from the 1997 AAAI Workshop.

[10] Robert Morris, Workshop Summary. Kasparov vs. Big Blue: The Significance for Artificial Intelligence. CS Program, Florida Institute of Technology. AAAI 1997.

[11] IBM Research. Deep Blue FAQ: http://www.research.ibm.com/deepblue/meet/html/d.3.3.html

[12] E. A. Heinz, Scalable Search in Computer Search: Algorithmic Enhancements and Experiments at High Search Depths, Friedrich Vieweg & Sohn, 1999.

[13] J. H. Condon, K. Thompson, Belle chess hardware, Advances in Computer Chess 3, Pergamon Press, Oxford 1982.