Computers vs Humans: Chess

COMPUTER CHESS

Chess

Chess is a game that does not involve luck. In theory, we could find a winning strategy for white by examining all possible combinations of moves and seeing which sequence leads to a mate. The trouble is that the number of possible move combinations is huge. Before we attempt to give an idea of that number we need to define some terms. The term ply is used to denote a player's turn while the word move is used to denote a pair of turns. So if white opens with "pawn to King's 4" and black reply is "pawn to Queen's 3" the first move is "white: pawn to King's 4/ black:pawn to Queen's 3". For more on these definitions see http://en.wikipedia.org/wiki/Ply_(game_theory).

There are 20 possible values for the first ply and another 20 for the second, so that there are 400 possible values for the first move. The number of values in subsequent moves can be greater or smaller than 400 but for our present purpose will suffice to note that there at least 100 possibilities per move. For 30 moves that is 100³⁰ or 10⁶⁰. If it takes only one second to create a move we will need 10⁶⁰ seconds to create all possible combinations for 30 moves. There are 86,400 seconds in a day and 31,536,000 seconds in a year. We can write the last number as (approximately) 3*10⁷ and use it to divide 10⁶⁰ to find that we will need (1/3)*10⁵³ years, truly an eternity. (Note that a trillion is 10¹².) Suppose now that we could program a computer to calculate all possible combinations of moves and that it could need one nanosecond per move. That would save a factor of the 10⁹. Suppose also that we put a million such machines to work in parallel so that we save a factor of 10⁶. This will reduce the total time to (1/3)*10³⁸ years, still much longer than a trillion years.

Conclusion: While a winning strategy in chess could be found in theory through exhaustive enumeration, the number of possible moves is so large that it is impossible to ever find the winning strategy.

How People Play Chess

Human players do not look in all the possible moves, but only at those that they know (from experience) to be promising. Thus there are about 6 possibilities for the first ply rather than 20. The more experienced a player the more he/she can trim the possibilities and the more moves ahead he/she can look. Casual players may look only 2 or 3 moves ahead while world class players may look 20 moves ahead.

How Modern Computers Play Chess

In the old days computer programs that played chess tried to replicate human play and they did not go far that way. A breakthrough occurred in the 1970's when Ken Thompson [W] (then at Bell Labs) hit upon a different idea. Because computers are much faster than humans it would be feasible to consider all combinations of possibilities for at least a few moves. Such brute force approach could look a few moves ahead and the resulting positions would be given scores according to known chess practice. The play that led to the best position would be chosen. Ken Thompson worked with Joe Condon to build special purpose hardware for generating and evaluating chess moves and they called their machine Belle. It could examine 160,000 positions per second. To look ahead by four moves requires examining roughly 400⁴ positions. That is approximately 25*10⁹ or 25 billion positions. Examining all such positions it will take about 156,000 seconds or about two days. That is too long for the time allotted in chess tournament play. It turns out that one can reduce the number of moves to be examined if a move results in a worse position than another move. (For the mathematically brave: this is called the alpha-beta pruning strategy [W].) By using this strategy the number of moves to be examined was reduced by a factor of more than 1000 allowing Belle to look ahead four moves in a few minutes.

Belle won the American computer chess championship in 1978 and the World chess championship in 1980. It achieved master level rating against human players. The machine is now at the Smithsonian Museum. You can find more about Belle from these two sites: Computer History Museum Page on Belle and Interview with Ken Thompson: Oral History of Belle.

The success of Belle changed the way that people were thinking about computer chess. If one could build hardware that looked 6 or more moves ahead in the allotted time, such a machine was likely to beat any human. That machine, named Deep Blue, was built by IBM research and challenged the reigning world champion Garry Kasparov. The first match took place in February 1996 and Kasparov won by winning three games and losing one. Two games ended in a draw. There was a rematch May 1997 and this time Deep Blue won by winning two games and losing one. Three games ended in a draw. The story of the development of new hardware that resulted in the Deep Blue machine can be found in the following posting on the IBM Research website: Eric Lerner "The Making of a Chess Machine". (The article was written soon after the first match.) Bellow is a quote from that article:

Getting a chess machine to learn from its own mistakes is an appealing idea. It has been tried in the past, but with limited success. "The problem," Campbell explains, "is that when you lose a game, the machine doesn't know what move was the wrong one. It could have been the fourth move or the next-to-last, so it doesn't know what move it has to correct, and determining the reason for the loss and generalizing it to other positions is even more difficult."

In contrast, Deep Blue has no learning ability once its values are chosen by its programmers; it carries out exactly the evaluations hardwired into it. So, in any dictionary definition, as well as in the eyes of its creators, Deep Blue has no intelligence at all. That point seemingly got lost in the media discussion of Deep Blue's IQ.

When the brute force search reaches a position it must evaluated from the viewpoint of chess strategy. In the case of Belle Thompson did that himself. Deep Blue used the services of expert chess players. One of the original members of the team was Murray Campbell who had played chess at near national Master level. Later an international grandmaster, Joel Benjamin, joined the time. Earlier he had played Kasparov to a draw. The page http://www.research.ibm.com/deepblue/meet/html/d.2.html lists 10 differences between Kasparov and Deep and Blue. Here are two of them:

1. Deep Blue can examine and evaluate up to 200,000,000 chess positions per second.
* Garry Kasparov can examine and evaluate up to three chess positions per second.

6. Deep Blue can never forget, be distracted or feel intimidated by external forces (such as Kasparov's infamous "stare").
* Garry Kasparov is an intense competitor, but he is still susceptible to human frailties such as fatigue, boredom and loss of concentration.

Deep Blue was able to beat the best human player by being about 1000 times faster then Belle. It was brute force number crunching plus "intelligent design". For more on Deep Blue and the match with Kasparov see http://www.research.ibm.com/deepblue/. Chess aficionados can find the details about the two matches not only at the IBM site but also at Wikipedia.

Why IBM devoted resources to Deep Blue?

While the publicity made IBM no harm, the main reason for the effort behind Deep Blue was to gain experience in the design of super fast special purpose computers.

Back to the Index Page

First Posted:May 11, 2010 — Latest Update: June 6, 2010