Encyclopedia > Computer chess

Article Content

Computer chess

Chess enthusiasts and computer engineers have attempted to build, with increasing degrees of seriousness and success, chess-playing machines since 1769. Their motivations can essentially be consolidated into two: firstly, to build a machine to play chess with for solo entertainment, and secondly, to investigate chess as a problem which might provide some insight into human cognition. In this view, the history of computer chess is both a spectactular success and a virtually complete failure. Chess-playing computers are available for negligible cost, and there are many programs (even the free GNU Chess, Amy, Pepito,Crafty (ftp://ftp.cis.uab.edu/pub/hyatt/) and more (http://wbec-ridderkerk.nl/)) that play a game that, with the aid of virtually any modern personal computer can defeat most master players under tournament conditions, while top commerical programs like Fritz have surpassed even world champion caliber players at blitz and short time controls.

However, to the surprise and disappointment of many, chess has taught us little about building machines that offer human-like intelligence, or indeed do anything except play excellent chess. For this reason, computer chess is no longer of great academic interest to researchers in artificial intelligence. Chess-playing programs essentially explore huge numbers of potential future moves by both players and apply a relatively simple evaluation function to the positions that result. Such brute-force methods are useless for most other problems artificial intelligence researchers have tackled, and are believed to be very different from how human chess players select their moves. In some strategy games, computers easily win every game, while in others they are regularly beaten even by amateurs. Therefore, the fact that the best efforts of chess masters and computer engineers are as of 2003 so finely balanced should probably be viewed as an amusing quirk of fate rather than the profound comment on thought that many in the past, including some of the early theorists on machine intelligence, thought it to be.

Table of contents

1 Brute force vs. strategy

2 Brute force vs. humans

3 Endgame Databases

4 More on Endgame Databases

5 The future of computer chess?

6 Other chess software

7 Technical details of computer chess

8 Computer Chess theorists

9 External links

Brute force vs. strategy

In the early days of computer chess, there were two general schools of thought. One camp assumed that examining all possible sequences of moves to any reasonable depth would be impractical due to the astronomical number of possibilities. Instead of wasting power examining garbage moves, they tried to make their programs recognize patterns and formulate plans, much as humans do.

The second camp took a "brute force search" approach, examining as many positions as possible using the minimax algorithm with only the most superficial evaluation function. A program might, for example, pay attention only to checkmate, which side has more pieces, and which side has more possible moves, without any attempt at more complicated positional judgement. In compensation, the program would be fast enough to look exhaustively at all positions to a certain depth.

Use of alpha-beta pruning combined with a number of search heuristics[?] dramatically improved the performance of brute-force search algorithms.

To make a long story short, the brute force camp won out, in the sense that their programs simply played better chess. It turned out to produce better results, at least in the field of chess, to let computers do what they do well rather than coax them into imitating human thought.

Brute force vs. humans

On the other hand, it remained an open question whether any amount of brute force computation would ever be adequate to defeat the expertise of top humans. In 1968, IM David Levy made a famous bet that no chess computer would be able to beat him within ten years. He won his bet in 1978 by beating Chess 4.7[?] (the strongest computer at the time), but acknowledged then that it would not be long before he would be surpassed. It is well that Levy didn't renew his bet for another ten years, because in 1989 he was crushed by the computer Deep Thought in an exhibition match, and would probably have lost even to earlier, lesser computers.

Deep Thought, however, was still considerably below World Championship Level, as the then reigning world champion Gary Kasparov demonstrated in two sterling wins in 1989. It wasn't until a 1996 match with IBM's Deep Blue that Kasparov lost his first game to a computer at tournament time controls. However, Kasparov regrouped to win three and draw two of the remaining five games of the match, for a convincing victory.

In May 1997, an updated version of Deep Blue defeated Kasparov 3.5-2.5 in a return match. IBM keeps a web site of the event at http://www.chess.ibm.com. While not an official world championship, the outcome of the match is often taken to mean that the strongest player in the world is a computer. Such a claim is open to strong debate, as a truly fair human-machine match is difficult to arrange.

Firstly, in one of the games, Kasparov was not defeated over the board. He resigned in a technically drawn position, perhaps distraught that Deep Blue was playing such human-like moves. He angrily accused the Deep Blue team of feeding human input to the computer as the game was in progress. Thus this defeat should be reckoned more as a psychological loss than an indication of inferior chess ability.

Secondly, there are other players whose playing style is recognised as more effective against computer opponents. Kasparov's strength lies in overwhelming opponents tactically and psychologically, both of which play to the strength of computers, whereas Vladimir Kraminik, who recently defeated Kasparov in a World Championship match, is more content to defend a tenable position, probe for weaknesses, and accumulate small advantages.

Thirdly, it was impossible for Kasparov to prepare to play the machine as he would against a human opponent, as the computer's programming was adjusted between prior matches and the Kasparov match. That incarnation of Deep Blue had no tournament record before the match, whereas the Deep Blue team was able to study and prepare against hundreds of Kasparov's public games.

Finally, a six-game match was too short for Kasparov to adjust to any potential weaknesses of Deep Blue. One great advantage of humans over computers is adaptability. In all his previous encounters with computers Kasparov had finished more strongly than he began, and it is reasonable to suppose that he would have fared better in a twenty-four game match, the traditional length of World Championship matches.

IBM retired Deep Blue after the match and it has not played since. However, other "Man vs. Machine" matches continue to be played. In October 2002, Vladimir Kramnik and Deep Fritz competed in the eight-game Brains in Bahrain match, which ended in a draw. Kramnik won games 2 and 3 by "conventional" anti-computer tactics - play conservatively for a long-term advantage the computer is not able to see in its game tree search. Fritz, however, won game 5 after a severe blunder by Kramnik. Game 6 was described by the tournament commentators as "spectacular". Kramnik, in a better position in the early midgame, tried a spectacular piece sacrifice to achieve a strong tactical attack, a strategy known to be highly risky against computers who are at their strongest defending such attacks. True to form, Fritz found a watertight defence and Kramnik's attack petered out leaving him in a bad position. Kramnik resigned the game, believing the position lost. However, post-game human and computer analysis has shown that the Fritz program was unlikely to have been able to force a win and Kramnik effectively sacrificed a drawn position. The final two games were draws. Given the circumstances, most commentators still rate Kramnik the stronger player in the match.

In January 2003, Kasparov played Deep Junior, another chess computer program, in New York. The match ended 3-3.

Endgame Databases

Computers have been used to analyse some chess endgame positions completely. Such endgame databases are generated in advance using a form of retrograde analysis. Ken Thompson, perhaps better known as the key designer of the UNIX operating system, was a pioneer in this area. Over the years, other endgame database formats have being released including the Edward Tablebases, the De Koning Endgame Database (released in 2002) and the Nalimov Endgame Tablebases which is the current standard supported by most chess programs such as Fritz . All five-piece endings have now been analysed completely, and some of the six-piece endings are available. A computer using these databases will, upon reaching a position in them , be able to play perfectly, and immediately determine whether the position is a win, loss or draw. Knowledge of whether a position is a win,loss or draw is also helpful in advance since this can help the computer avoid or head towards such positions depending on the situation.

Endgame databases featured prominantly in 1999, when Kasparov played an exhibition match on the Internet against the Rest of the World. A seven piece Queen and pawn endgame was reached with the World Team fighting to salvage a draw. Eugene Nalimov helped by generating the six piece ending tablebase where both sides had 2 Queens which was used heavily to aid analysis by both sides.

More on Endgame Databases

It is still unclear how much chess programs benefit from using the current set of endgame databases. This is because most modern chess programs can play a majority of such positions well enough using their normal search algorithms and heuristics without using endgame databases as a crutch. It is suspected that as more endgame databases are added, this situation will change.

Nalimov Endgame Tablebases, which use state of the art compression techniques, require 7.05 GB of hard disk space for all five-piece endings. It is estimated that to cover all the six-piece endings will require at least 1 Terabyte. Seven-piece tablebases are currently a long way off.

While Nalimov Endgame Tablebases handle En passant positions, they assume that castling is not possible. This is a minor flaw that is probably of interest only to endgame specialists.

More importantly, they do not take into account the fifty move rule. Nalimov Endgame Tablebases only store the shortest possible mate (in ply) for each position. However in certain rare positions, the stronger side cannot force win before running into the fifty move rule. A chess program that searches the database and obtains a value of mate in 85 will not be able to know in advance if such a position is actually a draw according to the fifty move rule, or if it is a win, because there will be a piece exchange or pawn move along the way.

Various solutions including the addition of a "distance to zero" (DTZ) counter have been proposed to handle this problem, but none have been implemented yet.

The future of computer chess?

Many observers extrapolate that computers will consistently beat the best human players by perhaps 2010, and then go on to exceed their abilities to the point where a human vs. computer chess match would be as unfair as a human vs. automobile race. Others are unconvinced, saying that there are still deep strategic elements to chess that will resist brute-force computer searching.

Other chess software

There are several other forms of chess-related computer software:

Chess game viewers allow players to view a pre-recorded game on a computer. Most chess-playing programs can be also used for this purpose, but some special-purpose software exists.
Chess instruction software is designed to teach chess.
Chess databases are systems which allow the searching of a large library of historical games.

Technical details of computer chess

Computer Chess theorists