Machines That Play Chess — Summary

This is a summary. You can read the longer (yes, even longer) series here.

I recently wrote a 5 part series on Machines that Play (+ 2 parts on checkers and backgammon). The series covers the history of Artificial Intelligence and games (until Deep Blue) and focuses on machines that played chess, checkers, and backgammon. The following topics are covered: how to build chess machines, Shannon’s work on chess, Turing’s work on chess, The Turk, El Ajedrecista, MANIAC, Bernstein chess program, Samuel’s checkers, Mac Hack VI, Cray Blitz, BKG, HiTech, Chinook, Deep Thought, TD-Gammon, and Deep Blue.

I told a friend that Part 5, Machines That Play (Post Deep Blue), is meant to give the reader a break. My exact words, “After going through 4 parts, 3 of which are long, folks will want a break and that’s what Part 5 is — they can take a breather.” He laughed (at me) and said, “Do you realize your breather is 18 minutes long? That’s not a breather.” I thought 18 minutes is short and hence counts as a breather. Clearly one of us is wrong.

In case you find a 5 part chess-machines series too long, here’s the summary, focusing more on the human elements. See the original series for more technical details.

Let’s start.

Part 1: Machines That Play (Overview)

Before we talk about games and machines, let’s first talk about games and humans.

What’s an ideal game?

A game is something with rules and an objective. We “play” a game when we perform actions, constrained by these rules, in order to achieve the established objective.

We (humans) seem to need play almost as much as we need food, water, air, shelter, and tools to survive. What then, for us humans, would make a game ideal? This is a hard question to answer, but I imagine that an ideal game may have at least some of the following characteristics:

  • A game in which all players are highly skilled (or at similar levels): A game in which a player is able to use his skill to overcome the challenge that his opponent(s) offer. Ideal pleasure lies using his skill to outsmart or outmaneuver an opponent who is also very good at the game.
  • A game that is neither too easy, nor too hard so a player would “just win”: A game in which a player beats his opponent(s), who also performs close to his skill level. It’s a game he could have lost, but doesn’t lose. He wins. And he wins because the game allows him to rise just slightly more than his opponent(s); he conquers the elements of chance and exercises control over his environment (and himself).
  • A game that forces a player to develop and reach his highest potential in order to win: A game in which a player develops highest skills to outsmart or outmaneuver his opponent(s). Ideal growth means he is able to realize his potential, to be all that he can be. He develops such great skill that the risk of failure is nearly eliminated.
  • A game that changes a player’s psyche: A game that alters a player’s state of mind and in addition to realizing his highest potential, the game allows him to immerse himself fully in order to succeed. It is a game he would choose to continue playing as long as he can so he can accomplish (what he would later call) meaningful actions. And after the game, he would notice that he has changed from the game-playing experience and that his mind has been enriched with new skills, new experiences and new achievements.
  • A game that forces a player to be a catalyst for global change (remember this is an ideal game): A game in which the player would need to transform (or even transcend) himself, others, or even the entire world to the fullest extent in order to win. An ideal game would involve the player realizing his (and humans’) deepest yearnings, passions, or values. If not this, then the game would at least consume him so deeply as to free him from the chains of his everyday life. And through his journey he would create a path for others to develop and realize their potential.

Is there an ideal game?

I don’t know if there is an ideal game, but, in my opinion, the following example comes pretty close to being one; it not only satisfies many of the characteristics listed earlier, but it challenges and blurs those same characteristics.

[Video] The condition is that you let me live for as long as I can stand against you.

Death: Well, I am a pretty skilled chess player.

Knight: But I bet you’re not as good as me.

Death: Why do you want me to play chess with me?

Knight: That’s my business.

Death: Indeed.

Knight: The condition is that you let me live for as long as I can stand against you.

Knight: If I win, you let me go.

We are never playing against Death (and almost winning). Our actions, in most games, are not nearly as “meaningful” as saving the lives of other humans. Our games neither give us an opportunity to come to terms with our inescapable despair nor to radically transform (or transcend) ourselves or lives of others.

In reality there is probably no ideal game. Why do we still play then? A vague and simplistic answer is “because games are fun and/or useful”, but that doesn’t seem enough. (See Machines That Play (Overview) for a discussion on some of our oldest games).

In summary, we played (and continue to play) games for a wide variety of reasons:

  • We play to experience delight (fun)
  • We play to eliminate boredom / to escape reality
  • We play to practice and improve skills
  • We play to learn how to think critically and strategically
  • We play to conquer uncertainty, chance, luck, and probability
  • We play to play to create things in order to empower ourselves.
  • We play to destroy things in order to lessen our anger and frustration
  • We play to settle differences
  • We play to collaborate
  • We play to sate all of our human desires (prehistoric and current): nurture, hunt, kill, conquer, combat, compete, collaborate, create, survive
  • We play to win — to feel a sense of achievement

Throughout history we have created and played games to challenge our intelligence, strength, strategy, emotions, and more. In games, we come together and agree to a set of arbitrary rules. We compete and collaborate, we strategize to conquer chance and uncertainty, we set and achieve goals, we exercise imagination and experience delight of success.

Why AI and games?

Games are hard. Games are interesting. Games are test-beds for AI.

As technology evolved, so did our games. Recent technology has provided us with new teammates as well as new opponents, in form of machines. Even though the history of games is fascinating, we’ll focus on automation, artificial intelligence (AI), and games in this series. More specifically, we’ll focus on games where AI has either learned to play just as well as us, or better. This journey will turn out to serve as a humble reminder:

No matter what the rate of improvement is for humans, once machines begin to learn, it will become hard for us to keep up with machines, whose learning and progress will end up being measured exponentially. And ours won’t.

Since the earliest days of computing, people wondered if machines could match or surpass human intelligence. Artificial intelligence is about building machines that are able to perform the tasks that (we think) require “intelligence”. Programming machines to play games successfully served as one way for computers to learn tactics and strategies that could later be applied to other real-life domains.

“Games are fun and they’re easy to measure. It’s clear who won and who lost, and you always have the human benchmark…Can you do better than a human?” Murray Campbell

Part 2: Machines That Play (Building Chess Machines)

Part 2 covered 1) why we wanted to build chess machines, 2) some high level strategies to building chess machines and 3) progress in this field from 1940s-1990s.

Why chess?

Why would anyone want to teach a machine how to follow some arbitrary man-made rules to move a bunch of wooden pieces on a checkerboard, with the sole aim of cornering one special wooden piece? It’s so human to attack and capture pawns, knights, bishops and the queen to finally corner the king into an inescapable position. Those are our actions, that is our goal and we balance strategy and tactics to suit those. Then why teach machines to play chess?

Chess is an old game. It is believed to have originated in Eastern India (280–550). It reached Western Europe and Russia in the 9th century and by the year 1000, it had spread throughout Europe. It became popular and writings about chess theory (of how to play chess) began to appear in the 15th century.

Chess has long been regarded as the game of intellect. And many people argued that a machine that could successfully play chess would prove that thinking can be modeled/understood or that machines can be built to think. And that is exactly why people wanted to build a machine that could follow some arbitrary rules of our game and become so good at it that it could one day beat us at it.

Playing the game

Chess is a two-player zero sum game (i.e. if one player wins, then the other player loses) with perfect information (i.e. in which players know, at each time, all moves that have taken place at any given point).

How do we usually play this game? We do the following:

  1. Consider all the legal moves that a player can make
  2. Compute the new position resulting from each move
  3. Evaluate to determine the next best move
  4. Make that (best) move
  5. Wait for opponent to make a move
  6. Respond by repeating above steps

From this perspective, almost all chess computers must deal with these fundamental steps. And in doing that, a chess computer would have to address the following key problems:

  1. Representing the “board”
  2. Generating all legal next states
  3. Evaluating a position

Let’s look at each in detail:

Representing the “board”: A chess computer would need to represent the chessboard and the pieces that occupy squares on the board, i.e., it would need to represent a single position in data structures. There are several ways of doing this — see here.

Before we talk about the next two steps, let’s understand why building a chess computer is hard. A chess computer would receive a given chess position as input and it would need to calculate the next best move. A lot of difficulty is here because of the complexity of chess.

  1. Each player has 16 pieces to play with and 20 possible moves.
  2. Suppose White starts the game — it has 20 possible moves (Black also has the same options — 20 possible moves).
  3. Total Number of Moves For White = 20.
  4. Moves for Pawns = 8 + 8 = 16 (one step) (2 steps).
  5. Moves for Knights = 2 + 2 = 4.
  6. Total = 20.
  7. Therefore, at level 1: 20 possible moves for White.
  8. Then, at level 2: 20 * 20 = 400 possible moves for Black, depending on what White does.
  9. At level 3: 400 * 20 = 8,000 for White.
  10. At level 4 : 8,000 * 20 = 160,000 for Black……and so on.
  11. For all possible positions, the computer would need to evaluate 10¹²⁰ possible moves! (Side note: Go has ~ 10⁷⁰⁰ moves!!). Massive!
HowStuffWorks

In other words,

Complexity of a chess game

Chess has about 10¹²⁰ moves (and about10⁴⁰ nodes)! So the best way to think about a game tree is as a theoretical construct — it cannot be realized in the real world, it’s just too massive.

But a player (human or computer) still needs to find a good move. This means a chess computer still needs to search some tree which is not too massive, but still has enough (relevant) nodes that can be examined to allow it to determine a next “good” move.

What, then, does a chess computer have to do in order to beat the world champion?

Good game programs, therefore, must: 1) prune irrelevant branches of the game tree, 2) use good evaluation functions, and 3) look ahead as many moves as possible (as fast a possible).

In particular, chess computers would need to do the following well:

Generating all legal next states: A chess computer would need to know how to identify possible moves and select the most promising moves for further analysis (i.e. prune out bad moves and keep good moves). Since it is impractical (actually impossible!) to consider every possible move, a computer must make choices by its use of search techniques — these are algorithms to select the best move. This is where a lot of the earlier artificial intelligence innovations took place. For example, a chess computer can evaluate 2 or 5 or 10 or 20 moves ahead in advance. And the depth of the tree it can generate depends on the speed of the computer — the faster the computer generates the moves, the better the performance. Hence the emphasis on computational power.

Evaluating a position: Once a chess computer generates the tree, it needs to evaluate the positions. When the search space is too large, the game tree can be created to a certain depth only, i.e. a computer cannot look ahead to all possible end (win/lose/draw) positions. It must, instead, look ahead a few plies (half moves) and compare the possible positions, i.e. it must correctly evaluate the value of a board position, given no further search will be done at that position. This is done via the evaluation function, which assigns real number scores to these board positions. This evaluation function (and the algorithms) are often vastly different between different chess programs. It is extremely complex to tell how good a position is. For example, Deep Blue examined 200 million positions per second and used very sophisticated evaluation — it had over 8000 features as part of its function.

Many chess computers also added endgame databases. These are databases of pre-calculated position evaluation of hundreds (or thousands or millions) of past games from top players. These endgame databases would mainly be used for openings and endgames.

There were two main philosophical approaches to developing chess computers: emulation vs. engineering — should computers emulate human knowledge and decision-making or should computers improve search via brute force? Those focusing on the first approach would build programs that had a lot of chess knowledge and a relatively smaller focus on search. Those focusing on the engineering approach would focus on computational power, by using special-purpose hardware, and search innovations. We’ll see that the best chess computers used the second approach, but even they ended up using a lot of chess knowledge and sophisticated evaluation heuristics.

Keep this framework in mind while reading through the remaining parts.

Part 3: Machines That Play (Chess-Before Deep Blue)

This part covered a little bit of the history of computer chess, focusing on: Turk, El Ajedrecista, Shannon and Turing’s approaches to build chess programs, MANIAC, Bersnstein’s Chess program, Mac Hack VI, Cray Blitz, HiTech, ChipTest, and Deep Thought — most major attempts until Deep Blue.

Only human (The Turk)

In the spring of 1770, Wolfgang von Kempelen created a sensation; he presented the world’s first ever chess-playing automaton, which he called the Automaton Chess-player, known in modern times as The Turk. The Turk was a man-made machine that could play chess against any human opponent.

The Turk became a hit and Von Kempelen was invited to tour across Europe. The Turk began its European tour in 1783 and it operated for nearly 84 years (when it was destroyed in a fire). During the tour, it interacted with a range of historical figures, including Benjamin Franklin, Catherine the Great, Napoleon Bonaparte, Charles Babbage, and Edgar Allan Poe.

Many people insisted it was a trick, but no one figured out the exact trick.

Edgar Allan Poe claimed that a human mind was at work because a real machine would always win — it would play chess perfectly. It would never lose.

it turned out, the Turk was a hoax. Poe was right, but his reasons were wrong. We would later see machines are flawed and they do not play perfect chess.

The secret of this early automaton is “artificial artificial intelligence”: a human is doing the automaton’s job. Inside the machine hid a man who was small in size and who could play chess well. He hid in a small compartment that could slide left and right. When von Kempelen opened the left cabinet, the man would slide to the right. When he opened the right cabinet, the man would slide left.

The Turk and Knight’s tour

A more honest attempt (El Ajedrecista (The Chessplayer))

In early 1910s, Torres y Quevedo built an automaton called El Ajedrecista(The Chessplayer), which made its debut, at the University of Paris in 1914. It is considered to be one the world’s first computer games.

About Torres: “He would substitute machinery for the human mind” — Scientific American (1915)
Leonardo Torres Quevedo and second chess automata of Leonardo Torres Quevedo at Civil Engineering Faculty museum in Madrid

It was later demonstrated at the Congress on Cybernetics in France of 1951 (see video clip and related original blog).

The machine could not play a full game of chess, but it played an endgamewith three pieces, a king and a rook controlled by the machine against a single king controlled by a human player.

Some theory of games

Multiple games: chess, checkers, go, othello.

John von Neumann founded the field of game theory. In 1928 he proved the minimax theorem. This theorem states that in zero-sum games (i.e. if one player wins, then the other player loses) with perfect information (i.e. in which players know at each time all moves that have taken place so far), there is a pair of strategies for both players that allows each to minimize his maximum losses, hence the name minimax.

John von Neumann (1903–1957), Oskar Morgenstern (1902–1977) (taken from History of University of Vienna website), Ernst Zermelo (1871–1953)

Regarding 1940s-early 1950s: Early pioneers focused on building machines that would play chess much like humans did, so early chess progress relied heavily on chess heuristics (rules of thumb) to choose the best moves. Researchers emphasized emulation of human chess thought process because they believed teaching a machine how to mimic human thought would produce the best chess machines.

How future machines would play chess

Starting in mid 1940s, scientists from different fields (mathematics, psychology, engineering, etc.) had started discussing the possibility of creating a machine that could think, a machine that could compete with or even surpass humans in pattern recognition, computation, problem solving and even language. In 1950, Claude Shannon wrote the very first article ever published on programming a computer to play chess. He published a paper in Philosophical Magazine entitled Programming a computer to play chess.

Claude Shannon demonstrates a chess-playing automaton he built for a limited version of chess, to chess champion Edward Laske
“I see no limit to the capabilities of machines. As microchips get smaller and faster, I can see them getting better than we are. I can visualize a time in the future when we will be to robots as dogs are to humans.” — Shannon (Wikiquote (See Omni Magazine interview))

Shannon identified chess as an ideal problem for machines because it could be represented in a machine, it had a very clear goal (deliver checkmate), it involved no randomness, both players had access to all the information, it had relatively simple rules, yet mind-bending complexity — these rules could produce a massively large number of states (~10¹²⁰ possible chess games). This directly influenced and inspired all the chess programs of the following decades.

Complexity of a chess game

In his paper, Shannon discussed many of the basic problems involved with programming a computer to play chess. He specified a framework consisting of three parts: a symbolic board description, a successor function that defines the set of legal moves from any position, and a position evaluation that gives an outcome for the game. This framework is found in nearly all adversarial computer games today (see adversarial search).

To imitate or not to imitate human thought

Shannon said because chess was considered to require “thinking”, solving this problem would force us (humanity) “either to admit the possibility of a mechanized thinking or to further restrict our concept of “thinking”. He then described how a machine that could play a “tolerably good” game of chess would need to have a search function that would identify possible moves at any given point and an evaluation function that would rank those move according to how they could influence the game.

Shannon proposed two very different approaches to do this: A) reduce the total number of moves (i.e. limit the depth of the tree) and do a brute-force search of all possible variations of that tree (known as type A strategy), or B) only search through “important branches” by using human-like heuristics to trim the decision tree (i.e. by prioritizing certain branches over others) until it is clear which branch has the advantage (known as type B strategy).

Type A: Brute force strategy

In this strategy, the machine would do a brute-force search of all possible variations of the game tree, up to a given depth. At the time, it seemed impossible that a machine could be fast enough to look ahead more than a few moves. Shannon said that a machine that implemented this strategy would, at best, be “both slow and a weak player”.

Type A strategy seemed like a computer chess dead end in the early days of AI and chess.

Type B: Intelligence strategy

In this strategy, the machine would use “intelligence” instead of just raw computing power. It would only search through “important branches” and prune the decision tree until it became clear which branch had the advantage. It would prioritize certain branches over others and thus demonstrate something similar to human intuition.

Type B strategy seemed far more feasible and the earliest programs used this strategy

This distinction would turn out to be a deep debate in the field:

Is it necessary for a machine to simulate human intelligence (i.e. think like humans) or is it sufficient if a machine can match our intelligent behavior (i.e. match our functionality)?

A twist in the story

In 1997, a computer would beat one of the greatest players of all time: Garry Kasparov. And the twist is that it would mostly employ Type A strategy. Type B strategy is the strategy that would hit a dead end.

The first program that played chess (Turochamp)

Years: 1948–1953

In 1953, Alan Turing published an article on his chess program (Digital Computers Applied to Games) in the book Faster than Thought by B. Bowden.

Alan Turing (Wikimedia Commons)
“It seems probable that once the machine thinking method had started, it would not take long to outstrip our feeble powers… They would be able to converse with each other to sharpen their wits. At some stage therefore, we should have to expect the machines to take control.” — Alan Turing

Shannon had not spoken about any particular program in his paper. It was Turing who wrote the first chess program. And he wrote it before computers even existed! He knew computers were coming and once they were powerful enough, they would be able to play chess.

In 2012, Garry Kasparov played against Turochamp and defeated it in just 16 moves. Kasparov said (video), “I suppose you might call it primitive, but I would compare it to an early car — you might laugh at them but it is still an incredible achievement…

[Turing] wrote algorithms without having a computer — many young scientists would never believe that was possible. It was an outstanding accomplishment.”
Kasparov vs Turing’s Turochamp

MANIAC: Running the first chess program

While taking a break from producing the first hydrogen bomb…

The MANIAC I chess program was written in 1956. The team that programmed MANIAC was led by Stanislaw Ulam (who invented nuclear pulse propulsion and designed the H-bomb with Edward Teller), Paul Stein, Mark Wells, James Kister, William Walden and John Pasta. Due to MANIAC’s limited memory, the program used a 6 × 6 chessboard and no bishops.

According to Chessprogramming, MANIAC I performed a brute-force Shannon Type A strategy. It performed 11,000 operations per second, and had 2,400 vacuum tubes. It took 12 minutes to search a four moves depth (adding the two bishops would take three hours to search at the same depth). The program was written in 600 words of machine code.

Here is a YouTube video clip on MANIAC (by AtomicHeritage).

Paul Stern (left) and Nick Metropolis play chess with the MANIAC computer (ComputerHistory.org)

Bernstein Chess Program: First complete program

In 1957, Alex Bernstein, an IBM employee, created the first program that could play a full game of chess. He created it with his colleagues Michael Roberts, Thomas Arbucky and Martin Belsky, Bernstein at the Massachusetts Institute of Technology.

See video: IBM programmer and chess player, Alex Bernstein plays one of the first full computer chess game on the IBM 704 (Computer History)

The program ran on an IBM 704 and could perform 42,000 instructions per second. This was one of the last vacuum tube computers. It took about 8 minutes to make a move.

The Bernstein Chess Program used Shannon Type B (selective search) strategy. In order to select a move, it would look at the 30 possible moves available. It would then ask 8 preliminary questions about each of those moves. Next it would select 7 of the 30 possible moves for further analysis. Finally, it searched four plies (moves), considering it’s moves and the possible responses from the opponent for each of the 7 possible moves. It examined 2800 positions in 8 minutes.

Mack Hack VI: First chess program to compete in human tournaments

Game: Chess. Year: 1967

Mac Hack (also known as The Greenblatt Chess Program) is a knowledge-based chess program built by Richard Greenblatt in 1967.

Richard Greenblatt (1944- )

In the same year, Mac Hack VI became the first computer to play against humans under human tournament conditions. By the end of the 1967, it had participated in four tournaments. The MacHack program was the “first widely distributed chess program”, running on many PDP machines. It became the first computer to reach the standard of average tournament players. It was demonstrably superior to all previous chess programs as well as most casual players.

In 1965, Hubert Dreyfus said, “No chess program could play even amateur chess.”
In 1967, Mac Hack VI beats Dreyfus.
Mac Hack (Robert Q)

In 1968, a young Scottish International Master, David Levy, met AI researcher John McCarthy at a party hosted by Donald Michie. McCarthy challenged Levy to a game of chess and Levy beat him. Knowing Mac Hack VI’s quality of play, McCarthy said that a computer would be able to beat him within 10 years. Donald Michie and John McCarthy made a bet of £250 each with David Levy (who wagered £500 — the equivalent of more than £8,000 ($12,000) today).

The following year Seymour Papert joined in, and in 1971 Ed Kozdrowicki joined in. In 1974, Donald Michie raised the total to £1250.

In 1978, he was playing a computer opponent in a match. He played five games: the first was a draw, he won the second and third, he lost the fourth, and he won the fifth. In 1978, Levy collected on his bet. He will go unbeaten until 1989 (by Deep Thought).

David Levy (Computer History)

In his 1978 article David Levy said [referring to Alan Turing’s Turing Test as applied to chess], “If a chess master were to play a game against an opponent who was invisible to him, and could not tell from the game whether his opponent was a human or a program, then if the opponent was a computer program that program could be said to be intelligent. I have never faced with this situation but I doubt very much whether I, or any other chess master, could correctly identify an opponent that was a strong computer program. Although there are stylistic differences, these differences become less and less noticeable as the best programs become stronger….The best chess programs must now be considered “intelligent” in the Turing sense, though the brute force way that they play chess is anything but intelligent in human terms.” His last few lines:

If it is possible to produce an artificially intelligent chess player it is surely possible to produce and artificial intellect in other spheres. My only qualm is that perhaps it is wrong to regard the prospect with awe. Maybe fear would be more appropriate.

Cray Blitz: First super(chess) computer

In the early 1970s the first powerful programs were introduced

Harry Nelson and Cray Blitz

Cray Blitz, developed by Robert Hyatt, Harry L. Nelson, and Albert Gower, entered ACM’s North American Computer Chess Championship in 1976. It became a serious competitor in 1980 when it was moved to a Cray-1 supercomputer, becoming the first chess program to use such a powerful machine. This made it possible for Cray Blitz to adapt a mostly algorithmic and computational approach while still retaining most of its (extensive) chess knowledge. Throughout the 1970s and 1980s the computer chess community was focused on beating David Levy (see Mac Hack and David Levy above).

By 1984, Cray Blitz had beaten several strong masters and had achieved a master-level score. So Cray Blitz challenged David Levy — he beat it 4–0! After that he wasn’t so sure about his earlier optimism about computer play. In May 1984, he told Los Angeles Times, “During the last few years I had come to believe more and more that it was possible for programs, within a decade, to play a very strong grandmaster chess. But having played the thing now, my feeling is that a human world chess champion losing to a computer program in a serious match is a lot further away than I thought…”

“…Most people working on computer chess are working on the wrong lines. If more chess programmers studied the way human chess masters think and tried to emulate that to some extent then I think they might get further.”

They weren’t necessarily working on the wrong lines. Machines will begin to improve very quickly.

HiTech: First international master

Computer History
“Hitech is inexorable — like Bobby Fischer.” — Hans Berliner
Hans Berliner: CMU Archives

HiTech was a chess machine with special purpose hardware and software. It was built by Hans Berliner and others at CMU in the 1980s. The move generation and pattern recognition parts of its evaluation function were done in hardware — with 64 chips in parallel. Its custom hardware could analyze ~175,000 moves per second and it could execute a full-width depth-first search. It was one powerful machine.

In 1985 it achieved a rating of 2530, becoming the first (and at the time only) machine to have a rating over 2400. It later tied with Cray Blitz at the 1986 Computer Chess Championship. In 1988 HiTech defeated Grandmaster Arnold Denker in a four-game match (3.5–0.5), winning the last game in 23 moves. It was the first time a chess program had beaten a grandmaster. Arthur Denker said “This is a machine with a sharp game. It plays the openings beautifully. Unfortunately I played badly.” In 1988 HiTech became the first chess computer to rated Grandmaster strength.

According to Time, when asked if a computer would ever threaten the likes of Gary Kasparov, world champions (and others) said “No, I don’t think a computer will ever get that good.” Berliner acknowledged that Hitech was not that good — yet.

He said with conviction, “Ever is far too long a time.”

He was right, a computer would beat Gary Kasparov — soon enough.

ChipTest

Predecessor of Deep Thought, which would evolve into Deep Blue.

ChipTest circuit board

ChipTest was a 1985 chess computer built by Feng-hsiung Hsu, Thomas Anantharaman and Murray Campbell at Carnegie Mellon University (CMU). It is the predecessor of Deep Thought (and hence Deep Blue). ChipTest’s custom technology used “very large-scale integration” (VLSI) to combine thousands of transistors onto a single move generator chip.

Six weeks before the 1986 North American Computer Chess Championship, Hsu and team decided to prepare their machine to compete. According to Hsu, he had already tested and designed a custom chip that could process up to two million moves per second, 10 times faster than Hitech’s 64-chip array (HiTech was also a CMU program). Anantharaman had already written a toy chess program. He substituted Hsu’s chip tester for the software package he used in his program, and it improved the program’s speed by 500 percent, to a total of 50,000 positions per second! Hsu and Anantharaman recruited Campbell and Nowatzyk; Campbell worked on developing a more sophisticated evaluation function and all of them worked on augmenting the chip tester so that it could act as a simple search engine. The machine was buggy in the competition, but it was still a great achievement: on very little budget and in six weeks, they had built ChipTest.

In August 1987 ChipTest was improved and renamed ChipTest-M. It was ten times faster, searching ~500,000 moves per second.

Deep Thought (1989)

Deep Thought was chess- playing machine initially started 1985 as ChipTest by Feng-hsiung Hsu, Thomas Anantharaman, Mike Browne, Murray Campbell and Andreas Nowatzyk. (It would culminate in Deep Blue).

In January of 1988, at a press conference in Paris, world chess champion Gary K. Kasparov was asked whether a computer would be able to defeat a grandmaster before the year 2000. “No way,” he replied, ”and if any grandmaster has difficulties playing computers, I would be happy to provide my advice.”

“No way…and if any grandmaster has difficulties playing computers, I would be happy to provide my advice.”

Ten months later, in November 1988, in the Software Toolworks Open Championship tournament in Long Beach, California, Grandmaster Bent Larsen was defeated by Deep Thought.

Murray Campbell, Feng-hsiung Hsu, Thomas Anantharaman, Mike Browne and Andreas Nowatzyk, after winning the Fredkin Intermediate Prize for Deep Thought’s Grandmaster-level performance

Deep Thought ended up winning the North American Computer Chess Championship in 1988 and the World Computer Chess Championship in the year 1989, and its rating, according to U.S. Chess Federation was 2551, among the top 30 players in the United States. An average tournament player then was rated around 1500. Deep Thought’s rating meant it was playing at the level of the bottom half of the grandmaster range.

Deep Thought was a combination of software and customized hardware. It had a pair of custom built processors, each of which included a VLSI chip to generate moves. Each processor could evaluate 450,000 positions per second and the two processors working together reached 700,000 positions per second. These dual-processors were mounted on a single printed circuit board along with an additional 250 integrated circuit chips that controlled the search and evaluation positions. The evaluation function could weigh around 120 board features. These figures made it the fastest chess machine till then. In the games played after August of 1988, Deep Thought’s performance rating exceeded 2600.

Challenging the world champions

In October 22, 1989, Deep Thought faced Garry Kasparov in an exhibition two-game match. [Side note: Watch Kasparov versus Deep Thought documentary (videos): Part 1, Part 2, Part3, Part 4.]

Kasparov was only twenty-two at the time, the youngest person ever to have become the world champion. Before Deep Thought, there had been no machine that might have challenged a human world champion.

Deep Thought’s rating was approximated to be around 2500 and Kasparov’s rating was around 2800, the highest rating in the history of ratings so far. Kasparaov won the first game, after which he briefly addressed the crowd and said,

“I can’t visualize living with the knowledge that a computer is stronger than the human mind…(to challenge the machine is to) protect the human race.”

Kasparov also won the second game, after which he said the machine still had “a lot to learn”. He was right. The result was not unexpected, but Deep Thought’s play was still considered to be disappointing.

At the end, Kasparov addressed the crowd and expressed a very graceful human sentiment:

“When playing versus a human being there’s energy going between us. Today I was puzzled because I felt no opponent, no energy — kind of like a black hole, into which my energy could disappear. But I discovered a new source of energy, from the audience to me, and I thank you very much for this enormous energy supply.

On December 12 and 13, 1989, Deep Thought faced David Levy in a four-game match. Deep Thought defeated the master chess player David Levy. Until then, Levy had beaten all other previous computers since 1968. Deep Thought was represented and operated by Peter Jansen, who later told David 30 new evaluation terms had been added to Deep Thought’s program prior to its match with Levy. And Levy hadn’t competed seriously in chess for more than a decade so he played like a “rusty” man. Recall, in 1968, David Levy had met John McCarthy and Donald Michie. Based on the success of Mac Hack VI (and similar programs), McCarthy said challenged Levy that a computer would be able to beat him within 10 years.

Levy became the first master chess player to be defeated by a computer, but it didn’t happen until twenty-one years after the bet. And when it did finally happen, some called it the end of an era.

Part 4: Machines That Play (Deep Blue) + Part 5: Machines That Play (Post Deep Blue)

These parts covered the summary of innovations in chess programs, leading up to and including Deep Blue. Part 4 focused on technical details (from papers of the Deep Blue team) and Part 5 (the “breather”) was mostly about people’s reactions — the fun part.

Review

1930s: Creation of electronic computers began in the 1930s. ENIAC, which is considered to be the first general-purpose electronic computer, became operational in 1946. By the late 1940s computers were used as research and military tools in US, England, Germany, and the former USSR. Computer chess presented a fascinating and challenging engineering problem.

1940s — 1950s: Early pioneers focused on building machines that would play chess much like humans did, so early chess progress relied heavily on chess heuristics (rules of thumb) to choose the best moves. Researchers emphasized emulation of human chess thought process because they believed teaching a machine how to mimic human thought would produce the best chess machines.Computing power was limited in the 1950s, so machines could only play at a very basic level. This is the period when researchers developed the fundamental techniques for evaluating chess positions and for searching possible moves (and opponent’s counter-moves). These ideas are still in use today.

1960s: AI pioneers Herbert Simon and John McCarthy referred to chess as “the Drosophila of AI”, which meant that chess, like the common fruit fly, represented a relatively simple system that could also be used to explore larger, more complex real-world phenomena. Computer chess was the perfect test-bed for AI research. By the end of the 1960s, computer chess programs were good enough to occasionally beat against club-level or amateur players.

1970s–1980s: Emphasis was on hardware speed. In the 1950s and 1960s, early pioneers focused on chess heuristics (rules of thumb) to choose the best next moves. Even though programs in 1970s and 1980s also used heuristics, there was a much stronger focus was on software improvements as well as use of faster and more specialized hardware. Customized hardware and software allowed programs to conduct much deeper searches of game trees (involving millions of chess positions), something humans did not (because they could not) do. The 1980s also brought an era of low cost chess computers. First microprocessor-based chess programs started becoming available. Because of the availability of home computers and these programs, anyone could now play chess (and improve their game) against a machine. By the mid-1980s, the sophistication of microprocessor-based chess software had improved so much they began winning tournaments — both against supercomputer based chess programs and some top-ranked human players.

1990s: Chess programs began challenging International Chess masters and later Grandmasters. These programs relied much more on memory and brute force than on strategic insight, and they started to consistently beat the best humans. Some dramatic moments in computer chess occurred in 1989 — two widely-respected Grandmasters were defeated by CMU’s Hitech and Deep Thought. Researchers felt machines could finally beat a World Chess Champion. This got IBM interested so they began working on this challenge in 1989 and built a specialized chess machine, named Deep Blue.

Six-game chess matches had been organized between world champion Garry Kasparov and IBM Deep Blue. First match took place in Philadelphia in February 1996. A rematch took place in New York City in May 1997.

A brief history of chess machines (repeated from earlier)

Deep Blue (1996)

At the time of the first match, Kasparov had a rating of 2800, which was the highest point total ever achieved. Deep Blue’s creators placed the machine at a similar level.

IBM’s Deep Blue Team (from left to right): Joe Hoane, Joel Benjamin, Jerry Brody, F.H. Hsu, C.J. Tan and Murray Campbell

Popular Science asked David Levy about Garry Kasparov match against Deep Blue and Levy stated that

“…Kasparov can take the match 6 to 0 if he wants to. ‘I’m positive, I’d stake my life on it.’”

On the other hand Monte Newborn, a computer science professor at McGill University said, “I’ll give the computer 4 1/2 to Kasparov 1 1/2 [A draw gives each player a half point.] Once a computer gets better than you, it gets clearly better than you very quickly. At worst, it will get a 4 1/2 score.

“Once a computer gets better than you, it gets clearly better than you very quickly.”

The outcome was unclear. Deep Thought, predecessor of Deep Blue, was a tournament grandmaster, not a match grandmaster. And this was not a regular tournament, this was a match. This was a different challenge. Why did a match-play present a different challenge than a tournament-play? Because in a match, the players play multiple games against each other. This gave human grandmasters a opportunity to gauge the machine’s weaknesses and exploit those weaknesses to their advantage. According to Hsu,

Human Grandmasters, in serious matches, learn from computers’ mistakes, exploit the weaknesses, and drive a truck thru the gaping holes.

IBM needed to build a machine that would have very few weaknesses and those weaknesses needed to be very difficult for human grandmasters to exploit.

Deep Blue was only a two-week old baby when it faced Garry Kasparov in 1996. Hsu, one of its creators said,

“Would it be the baby Hercules that strangled the two serpents send by the Goddess Hera? Or were we sending a helpless baby up as a tribute to placate the sea monster Cetus, but without the aid of Perseus? We were afraid it would be the latter.”

The very first game Deep Blue played against Kasparov, in February 1996, Deep Blue won, — prompting Kasparov to question himself and asking Frederic Friedel, his computer consultant,

“Frederic, what if this thing is invincible?”

In this first game of the match, Kasparov wrote, “the computer nudged a pawn forward to a square where it could easily be captured. It was a wonderful and extremely human move. If I had been playing White, I might have offered this pawn sacrifice…Humans do this sort of thing all the time. But computers generally calculate each line of play so far as possible within the time allotted…computers’ primary way of evaluating chess positions is by measuring material superiority, they are notoriously materialistic. If they “understood” the game, they might act differently, but they don’t understand. So I was stunned by this pawn sacrifice. What could it mean? I had played a lot of computers but had never experienced anything like this. I could feel — I could smell — a new kind of intelligence across the table. While I played through the rest of the game as best I could, I was lost; it played beautiful, flawless chess the rest of the way and won easily.”

“I could feel — I could smell — a new kind of intelligence across the table.”

It turned out that the pawn was not a sacrifice at all. Deep Blue (1996) did calculate every possible move “all the way to the actual recovery of the pawn six moves later”. Kasparov then asked, “So the question is…

…if the computer makes the same move that I would make for completely different reasons, has it made an “intelligent” move? Is the intelligence of an action dependent on who (or what) takes it?

Later in his TED talk, Kasparov said, “When I first met Deep Blue in 1996 in February, I had been the world champion for more than 10 years, and I had played 182 world championship games and hundreds of games against other top players in other competitions. I knew what to expect from my opponents and what to expect from myself. I was used to measure their moves and to gauge their emotional state by watching their body language and looking into their eyes. And then I sat across the chessboard from Deep Blue. I immediately sensed something new, something unsettling. You might experience a similar feeling the first time you ride in a driverless car or the first time your new computer manager issues an order at work. But when I sat at that first game, I couldn’t be sure what is this thing capable of. Technology can advance in leaps, and IBM had invested heavily. I lost that game. And I couldn’t help wondering, might it be invincible? Was my beloved game of chess over? These were human doubts, human fears, and the only thing I knew for sure was that my opponent Deep Blue had no such worries at all.”

“…I lost that game. And I couldn’t help wondering, might it be invincible? Was my beloved game of chess over? These were human doubts, human fears, and the only thing I knew for sure was that my opponent Deep Blue had no such worries at all.”

The 1996 match was finally won by Kasparov (4–2 score). The match was tied at 2–2 after the first four games and even though it looked like it was a decisive win, it was a fairly close match, closer than generally believed.

Kasparov ended his essay in Time by talking about why he won the first match. He said “I could figure out its priorities and adjust my play. It couldn’t do the same to me. So although I think I did see some signs of intelligence, it’s a weird kind, an inefficient, inflexible kind that makes me think I have a few years left.”

He did not have a few years left. In May 1997, he would lose the rematch to Deep Blue.

Kasparov won the 1996 match. A rematch took place in New York City in 1997. This time, Kasparov lost — Kasparov’s loss to Deep Blue was his first ever chess match loss in his entire life.

Garry Kasparov (Time Magazine)

Deep Blue (1997)

According to Campbell, Hoane, Hsu, “In fact there are two distinct versions of Deep Blue, one which lost to Garry Kasparov in 1996 and the one which defeated him in 1997.

Improvements on Deep Blue (1996)

Some high level factors that contributed to Deep Blue’s success in 1997:

  1. A single-chip chess search engine
  2. A massively parallel system with multiple levels of parallelism
  3. A strong emphasis on search extensions
  4. A complex evaluation function, and
  5. An effective use of a Grandmaster game database.

The Deep Blue team knew that there were a number of deficiencies in Deep Blue (1996) that they needed to overcome, such as, gaps in chess knowledge and computation speed. So Campbell, Hoane, Hsu designed a new and significantly enhanced chess chip: 1) the new chess chip had a completely redesigned evaluation function, going from “around 6,400 features to over 8,000”, 2) the new chip added “hardware repetition detection”, which included a number of specialized move generation modes (e.g., to generate all moves that attack the opponent’s pieces:), 3) the new chip had increased its search speed to 2–2.5 million positions per second.

Deep Blue Architecture and System overview

Deep Blue (1997) was a massively parallel system designed for carrying out chess game tree searches. The distributed architecture was composed of 30-nodes (30 processor (one per node)) IBM RS/6000 SP computer, which did high level decision making, and 480 chess chips (each a single-chip chess search engine), with 16 chess chips per SP processor.

The 480 chips were running in parallel to do a) deep searches, b) move generation and ordering, c) position evaluation (over 8000 evaluation features) effectively. Then they designed, tested, and tuned the new evaluation function.

Before the match

Kasparov was asked to explain his earlier statement regarding Deep Blue: that he was in presence of some kind of intelligence.

He answered, “Yes. I think we can hardly call it intelligence because we always believe that intelligence is something similar to our mind. But playing with Deep Blue, and other computers but mainly with Deep Blue, I can smell that the decisions that it’s making are intelligent because I would come to the same conclusion by using my intuition…

…But if I use 90% of my intuition and positional judgement and 10% of calculation, and Deep Blue uses 95% of computation and 5% of built in chess knowledge, and the result matches four times out of five, maybe we should talk about some sort of artificial intelligence.”
Garry Kasparov (Wikimedia Commons)

Let the games begin

Kasparov won the first game of the rematch.

Predictions were in Kasparov’s favor, many experts predicted the champion to score at least four points out of six. Kasparov was coming off a superb performance at the Linares tournament and his rating was at an all-time high of 2820. In a 2003 movie, he recalled his early confidence:

“I will beat the machine, whatever happens. Look at Game One. It’s just a machine. Machines are stupid.”

Postmortem analysis showed that Deep Blue could have drawn that game, if only it could have searched a few more plies deeper…

Then came game 2 — a game so different that a machine playing such a game had never been seen before.

Computers’ strength was in tactical chess; they didn’t play strategically, in other words, until then, computers chose materialistic gains over positional advantages. Until then.

Kasparov had set a trap in which Deep Blue would gain a pawn (a materialistic gain) but lose position. Instead of capturing the exposed pawn (as expected by everyone), Deep Blue (1997), chose another route; it chose a positional advantage. At the time, no machine was playing with, what grandmasters called, strategic foresight. Deep Blue had just shown a glimpse of that.

Deep Blue (1997) played game 2 like a human and that is not how machines were supposed to play. Grandmasters who were observing the game later said that had they not known who was playing, they would have thought that Kasparov was playing one of the greatest human players, maybe even himself.

Grandmaster Joel Benjamin said, “This is the game that any human grandmaster would be proud to have played for White. This was not computer-type game. This was real chess.”

This play shook Kasparov. Kasparov resigned this game. Later, the chess-playing community would begin analyzing game 2 and discover something shocking: Kasparov had resigned in a drawn position — after just 45 moves. Before this he had never resigned a drawn position!

Malcolm Pein, chess correspondent for The Daily Telegraph of London said, “There were only three explanations:

Either we were seeing some kind of vast quantum leap in chess programming that none of us knew about, or we were seeing the machine calculate far more deeply than anyone heard it could, or a human had intervened during the game.”

Kasparov accused IBM o f cheating; he alleged 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. He claimed that move in game 2 was too human and there was no way a computer could have chosen such a move.

Later when asked about whether he thought there was human intervention, he said,

“It reminds me of the famous goal which Maradona scored against England in 1986. He said it was the hand of God.”

IBM hadn’t cheated. But Kasparov was upset.

Imagine this: It’s game 3 and Kasparov knows he could have drawn game 2, but didn’t. Even worse, he has never resigned a drawn position. How does this effect how he plays game 3? Well, in game 3 he has White, but doesn’t play his usual game. He alters his style and goes on the defensive.

Referring to Kasparov’s Game 3 play, a New York Times article titled Wary Kasparov and Deep Blue Draw Game 3, said, “His play yesterday with the white pieces, cautious rather than aggressive, was uncharacteristic, at least compared with games against living, breathing opponents.” They quote Miguel Illescas, a Spanish Grandmaster who was with the Deep Blue team,

“I don’t want to say he’s afraid, but when the world champion with the white pieces doesn’t want to attack, what do you do?”

In Man versus Machine, Goodman and Keene quote Grandmaster Yasser Seirawan, “The computer has an advantage. It doesn’t have this body of emotions. We human players get depressed. We simply get depressed. The computer doesn’t get depressed, it doesn’t have any prejudice, it doesn’t carry along any emotional turmoil or upset… Garry was feeling rotten the whole game because Garry was getting outplayed the whole game.”

“…Garry was in a mental framework which said to himself “Man, I hate this game. I’m disgusted with myself. I played like a jerk. I’m going to lose in front of millions of fans. What am I doing here? Why did I wake up today? Again, there is that intimidating factor. When you sit there and you’re told that your opponent analyses chess at 2OO million moves a second, and all you’re looking at is a three or four move perpetual check, you’ve got to figure that your opponent’s seen everything.”

According to the New York Times article, other grandmasters didn’t think Kasparov was collapsing, “Mr. Kasparov didn’t see the drawing strategy, said David Levy, an international master, because he felt the computer would have insured that a perpetual check was impossible. That was seconded by Mr. Friedel, who said Mr. Kasparov told him, “The computer had played so well I didn’t even consider it.”

The IBM team didn’t face these types of difficulties. Man versus Machine quotes Murray Campbell, “It’s certainly nice not to have the problem of how do you handle the news that it was a draw. And you know, Garry will have to display great nerves in order not to let such a thing bother him.”

Kasparov did not win the next three games, but neither did Deep Blue — three draws.

Leading up to the final game, the match was tied 2.5–2.5.

The last game was brisk and brutal, in just 19 moves Deep Blue stunned the world. Deep Blue had unseated Kasparov. [See rare footage of the last game.]

The final score was 3.5–2.5. Kasparov was such a great player that he had never lost a match until then — in his entire life. And he had played some of the greatest matches in chess history, including several against Anatoly Karpov.

But this time was different. Devastated, Kasparov said, “I lost my fighting spirit.” After game 6 he said,

I lost my fighting spirit...I was not in the mood of playing at all..I’m a human being. When I see something that is well beyond my understanding, I’m afraid.’’

Usually in any significant chess match, players study their opponent’s previous games. According to Kasparov and his team, when they asked IBM for Deep Blue’s previous matches, IBM said there is nothing to share because there were no public games. It turned out that Deep Blue had not played any matches after the one against Kasparov in 1996. Deep Blue’s training and preparation had been done entirely in private. Hence Garry went into the 1997 match blind — something he had never done. And Deep Blue had every game Kasparov had ever played in its memory.

In the Wired article, Ray Keen said,

“IBM bent the rules. They didn’t actually cheat, but they exploited every resource of the rule book to disadvantage Garry. He would have won if they’d played fair with him.”

The author of the Wired Article then says, “Most grandmasters, even those who regularly get kicked all over the chessboard by Kasparov, agree.” Not everyone agreed, but almost everyone had a strong reaction, one way or another.

Garry Kasparov asked for a rematch, but it never occurred.

After losing to Deep Blue, later in his 1997 Time essay, “IBM Owes me a Rematch”, Garry Kasparov said, “I also think IBM owes me, and all mankind, a re-match. I hereby challenge IBM to a match of 10 games, 20 days long, to play every second day. I would like to have access in advance to the log of 10 Deep Blue games played with a neutral player or another computer in the presence of my representative. I would like to play it this fall, when I can be in my best form after a summer of vacation and preparation. And I’m ready to play for all or nothing, winner take all, just to show that it’s not about money. Moreover, I think it would be advisable if IBM would step down as an organizer of the match. It should be organized independently.

At the press conference following game 6, Kasparov said, “I think it is time for Deep Blue to prove this was not a single event. I personally assure you that, if it starts to play competitive chess, put it in a fair contest and I personally guarantee you I will tear it to pieces.” [See rare footage of the last game.]

He later appeared on Larry King Live and said he was willing to play Deep Blue “all or nothing, winner take all”. But that did not happen.

IBM had retired Deep Blue. A rematch would have required months of resources and preparation, which IBM did not want to spend on this. In the Scientific American article titled “20 Years after Deep Blue”, Campbell said, “We felt we had achieved our goal, to demonstrate that a computer could defeat the world chess champion in a match and that it was time to move on to other important research areas.

Deep Blue had stunned the world. And everyone had an opinion about the match or Deep Blue or Kasparov or IBM or intelligence or creativity or brute-force or the mind….

Let’s start with Louis Gerstner, CEO of IBM’s view, who said“What we have is the world’s best chess player vs. Garry Kasparov.”

So, who was the better player?

Was Deep Blue really the best chess player? Or was Kasparov still the better player?

The problem is that the rematch was only six games and Kasparov was only one point behind. Championship matches usually have a lot more games and most end in draws. So, it was hard to say if the rematch of six games said anything about who the better player was.

Most would argue that Kasparov was still the better player. But may be that wasn’t the real point. We saw some very special humans put tremendous efforts to create a machine that forced even the best of us to doubt. It beat us at one of our most treasured games and it left us in awe (or some in fear).

Jonathan Schaeffer said, “In looking at the match retrospectively, can we conclude that one chess computer (Deep Blue) is now better than the best that mankind has to offer? No, at least not yet. Two points come to mind. First, we believe that Kasparov played the better chess and failed to convert his opportunities. Second, IBM bought the right to play Kasparov; they did not earn it. By offering Kasparov a lot of money to play, Deep Blue could bypass the normal route for getting to play Kasparov, including the Candidate’s Matches. Deep Blue has demonstrated that it can successfully compete with Kasparov; it has not yet demonstrated that it can beat the other top grandmasters in the world. The positional playing style, for example, of Anatoly Karpov might give Deep Blue trouble.”

Charles Krauthammer, in Be Afraid in the Weekly Standard wrote, “To the amazement of all, not least Kasparov, in this game drained of tactics, Deep Blue won. Brilliantly. Creatively. Humanly. It played with — forgive me — nuance and subtlety.”

“…Deep Blue won. Brilliantly. Creatively. Humanly. It played with — forgive me — nuance and subtlety.”

Even though Deep Blue played a game that appeared to have some elements of “humanness” and even though its victory seems mind-blowing, Rodney Brooks (and others) said that training a machine to play a difficult game of strategy isn’t intelligence, at least not as we use intelligence for other humans; this view was shared by many researchers in AI.

On the other side was Drew McDermott, who said that the usual argument people used to say Deep Blue is not intelligent was faulty. He said, “Saying Deep Blue doesn’t really think about chess is like saying an airplane doesn’t really fly because it doesn’t flap its wings.”

So was Deep Blue intelligent?

May be, a little. Deep Blue was certainly not stupid, but it also wasn’t intelligent, in the same way we say another human being is intelligent. What Deep Blue showcased was a narrow kind of intelligence; the kind that shows brilliance in one domain and it does so because humans create better hardware, better software, better algorithms, and better representations. But if you ask these specialized machines to do anything else, they will fail. Deep Blue would have failed at all those other non-chess related tasks we do; it did not exhibit general intelligence.

No machine till date has exhibited general intelligence and it appears that they still have a long way to go before they can.

How did Deep Blue do what it did?

Murray Campbell said, “If we had simply used brute processing force, it wouldn’t have had a chance. It needed to be a focused computational effort.”

When Murray Campbell was asked about a particular move the computer made, he replied, “The system searches through many billions of possibilities before it makes its move decision, and to actually figure out exactly why it made its move is impossible. It takes forever. You can look at various lines and get some ideas, but…

“…you can never know for sure exactly why it did what it did.”

Deep Blue could only play chess, it could do nothing else. This is called narrow intelligence. This narrow intelligence, however, was already so complex that its makers could not trace its individual decisions. Deep Blue did not make the same move in a given position and it was simply too complicated, too complex, or too hard to understand its decisions.

Explainability was already too hard then, and it has since become more and more challenging to solve.

Until Deep Blue, humans were winning at chess. Machines really couldn’t beat the best humans — not even close. But then Deep Blue won. And soon so did the other machines and they have been beating humans ever since. This massive growth in performance is their identity.

No matter what our rate of improvement, once machines begin to improve, their progress ends up being measured exponentially. And ours doesn’t.

But it’s not really us vs. them, even though it was Garry Kasparov vs. Deep Blue. That was a game, a way to test how machines could learn, improve, and play. But the biggest win was for the humans because their intelligence had created Deep Blue.

Our emotions matter

People believed Kasparov was a better player, but his emotions got in the way. Either way, one of the biggest takeaways from this match was that we had collectively underestimated both the physiological and psychological aspects of the match. Our emotions, fears, desires, and doubts had a way of getting the best of us and sometimes we cannot do much more than just stand by and let it pass. And this is a uniquely human problem, one our machine opponents do not worry about.

Our emotions, fears, desires, and doubts had a way of getting the best of us…And this is a uniquely human problem, one our machine opponents do not worry about.

It’s a theme Kasparov hinted at throughout the match and continues to discuss even now [Kasparov’s TED talk]. [Side note: A video summary of Kasparov vs Deep Blue]

Computer Chess Post Deep Blue

The end of human-computer matches

In 2005, Hydra, a dedicated chess supercomputer with custom hardware and 64 processors crushed seventh-ranked Michael Adams (5.5–0.5) in a six-game match. Some people criticized Michael Adams for not preparing as well as Kasparov had, but that was irrelevant — this event was the beginning of the end of human-computer matches.

Hydra’s estimated rating was over 3000!

The rise of the Centaurs

Garry Kasparov introduced Advanced Chess (also known as cyborg chess, centaur chess or Ivanov chess), where a human player and a computer chess program would play as a team against other such pairs. This is a perfect example of the way Kasparov saw (and continues to see) the ideal interplay between humans and machines. The idea is that advanced chess would amplify human performance.

In 2017, however, chess engine Zor won the freestyle Ultimate Challenge tournament (freestyle is a variation or Advanced Chess, where consultation teams are also allowed). The best human plus computer came in 3rd place.

Chess machines became superior to human plus computers.

Computer Chess Status

Chess machines perform at a super-human level, i.e. they perform better than all humans. Here’s when different chess machines beat humans:

  • Supercomputer (1997): Deep Blue vs. Garry Kasparov (3.5–2.5)
  • Personal computer (2006): Deep Fritz vs. Vladimir Kramnik (4–2)
  • Mobile phone (2009): Pocket Fritz 4 won the Copa Mercosur Grandmaster tournament by winning 9 games and drawing 1 game (scoring 9.5 out of 10)
  • Computer defeats human+computer (2017): Zor

The biggest paradigm shift in computer chess since Deep Blue

In 2017, DeepMind’s AlphaZero beat Stockfish 28–0, with 72 draws, in a 100-game match. It used the a similar approach to master not just chess, but also Go and shogi.

Here’s the mind-boggling part: Imagine showing a computer how the chess pieces move, i.e. showing it legal moves, and nothing more. Then you tell the computer to learn to play the game — by itself. And in just 9 hours — yes ONLY 9 hours — it figures out not just how to play chess, but how to play at such a high level that it beats the strongest programs in the world — by far!

After just four hours of training, AlphaZero was playing at a higher Elo rating than Stockfish 8 and after 9 hours of training, it had decisively defeated Stockfish 8 in 100-game tournament.

Jonathan Schaeffer, an AI researcher at the University of Alberta, said, “It surprised the hell out of me. The games were beautiful and creative. AlphaZero made apparently crazy sacrifices that humans would not even consider in order to get more freedom of movement. But it also played differently to all other chess programmes which rely on human input.”

Other chess grandmasters were equally impressed. Russian champion Peter Svidler said that AlphaZero’s play was “absolutely fantastic, phenomenal” and he felt in “awe” of its play.

Magnus Carlsen’s coach Peter Nielsen said,

“…the aliens came and showed us how to play chess.”

Chess.com asked experts for their first reactions:

  • Maxime Vachier-Lagrave: “Of course the result is extremely impressive; I wouldn’t even dream of winning one game against Stockfish. The score especially with White is extremely impressive.”
  • Fabiano Caruana: “I was amazed. I don’t think any other engine has shown dominance like that. I think it was four hours of learning so who knows what it can do with even more.”
  • Sergey Karjakin: “I am very much surprised because we normally work with Stockfish and it looks like it’s a good program but if we have a program which beats Stockfish so easily it might be a new generation for computers and maybe it’s a historical day for chess. We’ll see how it will get stronger!”
  • Wesley So: “I was shocked. This is the new big thing. It totally changes chess. It might be rated, what, 3700? Close to 4000? That’s really crazy.”
  • Michael Adams: “I was pretty amazed. It will be interested in seeing more of the games.
  • Levon Aronian: “I am very excited but I am not sure about the conditions.”
  • Ian Nepomniachtchi: “If there is a chess program that easily beats the strongest chess engine at the moment it’s pretty good news for us also. We’ll probably play some other game but chess very soon!”
  • Hikaru Nakamura: “I think the research is certainly very interesting; the concept of trying to learn from the start without any prior knowledge so certainly it’s a new approach and it worked quite well obviously with go. It’s definitely interesting. That being said, having looked at the games and understand[ing] what the playing strength was I don’t necessarily put a lot of credibility in the results simply because my understanding is that AlphaZero is basically using the Google supercomputer and Stockfish doesn’t run on that hardware; Stockfish was basically running on what would be my laptop. If you wanna have a match that’s comparable you have to have Stockfish running on a super computer as well.”

Where are we?

What does machine performance, compared to human performance, look like?

Broad classes of outcome for AI and games are:

Optimal: it is not possible to perform better (some of these entries were solved by humans)

Super-human: performs better than all humans

High-human: performs better than most humans

Where do we go from here?

It seems right to end with Garry Kasparov’s TED talk and his view on the experience.

What I learned from my own experience is that we must face our fears if we want to get the most out of our technology, and we must conquer those fears if we want to get the best out of our humanity. While licking my wounds, I got a lot of inspiration from my battles against Deep Blue. As the old Russian saying goes, if you can’t beat them, join them. Then I thought, what if I could play with a computer — together with a computer at my side, combining our strengths, human intuition plus machine’s calculation, human strategy, machine tactics, human experience, machine’s memory. Could it be the perfect game ever played? But unlike in the past, when machines replaced farm animals, manual labor, now they are coming after people with college degrees and political influence. And as someone who fought machines and lost, I am here to tell you this is excellent, excellent news. Eventually, every profession will have to feel these pressures or else it will mean humanity has ceased to make progress. We don’t get to choose when and where technological progress stops.

We cannot slow down. In fact, we have to speed up. Our technology excels at removing difficulties and uncertainties from our lives, and so we must seek out ever more difficult, ever more uncertain challenges. Machines have calculations. We have understanding. Machines have instructions. We have purpose. Machines have objectivity. We have passion. We should not worry about what our machines can do today. Instead, we should worry about what they still cannot do today, because we will need the help of the new, intelligent machines to turn our grandest dreams into reality. And if we fail, if we fail, it’s not because our machines are too intelligent, or not intelligent enough. If we fail, it’s because we grew complacent and limited our ambitions. Our humanity is not defined by any skill, like swinging a hammer or even playing chess.There’s one thing only a human can do. That’s dream. So let us dream big.”

In this 2018 WSJ article titled “Intelligent Machines Will Teach Us — Not Replace Us”, Garry Kasparov reflected on the progress of AI and said, “My chess loss in 1997 to IBM supercomputer Deep Blue was a victory for its human creators and mankind, not triumph of machine over man. In the same way, machine-generated insight adds to ours, extending our intelligence the way a telescope extends our vision. We aren’t close to creating machines that think for themselves, with the awareness and self-determination that implies. Our machines are still entirely dependent on us to define every aspect of their capabilities and purpose, even as they master increasingly sophisticated tasks.”

Here’s how the 1997 result stands: The machine won, humanity also won (even though we sometimes forget the latter).

So let us dream big.