3.4. THE GAME OF CHESS

Belle

The number of possible move combinations in chess is truly astronomical. 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 chess 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¹².) So the exhaustive strategy not only is not feasible for human chess players. It is not even feasible for computers.

Indeed, suppose that we program a machine to calculate all possible combinations of moves and that it could need one nanosecond per move. That would speed up the process by a factor of the 10⁹. Suppose also that we put a million such machines to work in parallel so that we speed up the process by an additioanl factor of 10⁶ for a total speed up of 10¹⁵. This will reduce the total time from (1/3)*10⁵³ years to (1/3)*10³⁸ years. That is still much longer than a trillion years.

Ken Thompson's idea was to limit the number of moves for the exhaustive search and then select the initial move that looked most promising from the results of the exhaustive search after, say, four moves. He 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.) 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. Additional information about Belle (and other chess playing computer programs) can be found at the web site of the Computer History Museum [A]. Typing Belle in the search box of the pages returns all the relevant pages, including a link to an interview with Ken Thompson that provides the oral history of Belle.

Deep Blue

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 a little before the first match. 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.

Notes

[A] Computer History Museum page on chess: http://www.computerhistory.org/chess/

Back to Contents --- Previous Section --- Next Section