Chesspedia, The Free Chess Encyclopedia

Computer chess

From Chesspedia, the Free Chess Encyclopedia.

The idea of creating a chess-playing machine dates back to the eighteenth century. Around 1769, the chess playing automaton called The Turk became famous before being exposed as a hoax. After that, the field of mechanical chess research languished until the advent of the digital computer in the 1950s. Since then, chess enthusiasts and computer engineers have built, with increasing degrees of seriousness and success, chess-playing machines and computer programs.

Chess-playing computers are available for negligible cost, and there are many programs (such as the free GNU Chess, Amy and Crafty) that play a game that, with the aid of virtually any modern personal computer can defeat most master players under tournament conditions, while top commercial programs like Shredder or Fritz have surpassed even world champion caliber players at blitz and short time controls.

Hydra beat Shredder by 5.5 to 2.5 in 2004 running on 16 nodes; and would seem to be the strongest chess system. One should note however that Hydra was running on technically superior, specially designed hardware architecture, whereas Shredder was running on a conventional computer. Some chess commentators think that it will prove stronger than the very best human players under tournament conditions, but it has not yet played enough matches against the world's best players to say definitively.

Contents

Motivation

The prime motivations for computerized chess playing have been solo entertainment (allowing players to practice and to amuse themselves when no human players are available), their use in chess analysis, and as research to provide insights into human cognition. For the first two purposes computer science has been a phenomenal success, from the earliest real attempts to programs which challenge the best human players in less than fifty years. The latter objective has largely been unrealized. We can say that chess play is not an intractable problem to modern computing.

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, (as with other games, like Scrabble) is no longer of great academic interest to researchers in artificial intelligence, and has largely been replaced by more intuitive games such as Go as a testing paradigm. 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, whereas Computer Go challenges programmers to consider conceptual approaches to play.

The brute-force methods are useless for most other problems artificial intelligence researchers have tackled, and are 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. In chess, the combined skills of knowledgeable humans and computer chess engines can produce a result stronger than either alone.

Brute force vs. strategy

The first paper on the subject by Claude Shannon, published in 1950 before anyone had programmed a computer to play chess, successfully predicted the two main possible search strategies which would be used, which he labeled 'Type A' and 'Type B'.

Type A programs would use a "brute force search" approach, examining every possible position for a fixed number of moves using the minimax algorithm. Shannon believed this would be impractical for two reasons.

Firstly, with approximately 30 moves possible in a typical real-life position, he expected that searching the 30 × 30 × 30 × 30 × 30 × 30 positions involved in looking three moves ahead for both side (six plies) would take about 16 minutes, even in the "very optimistic" case that the program evaluated a million positions every second. (In the event, it took about forty years to achieve this speed.)

Secondly, it ignored the problem of quiesence, trying to only evaluate a position that is at the end of an exchange of pieces or other important sequence of moves ('lines'). He expected that adapting type A to cope with this would greatly increase the number of positions needing to be looked at and slow the program down still further.

Instead of wasting processing power examining bad or trivial moves, Shannon suggested that type B programs would use a "strategic AI" approach to solve this problem by only looking at a few good moves for each position. This would enable them to look further ahead ('deeper') at the most significant lines in a reasonable time.

Research by Adriaan de Groot had already shown that this is what good human players do: both masters and beginners look at around forty to fifty positions before deciding which move to play. What makes the former much better players is that they use pattern recognition skills built from experience. This enables them to examine some lines in much greater depth than others by simply not considering moves they can assume to be poor.

More evidence for this being the case is the way that good human players find it much easier to recall positions from genuine chess games, breaking them down into a small number of recognisable sub-positions, than completely random arrangements of the same pieces. In contrast, poor players have the same level of recall for both.

The problem with type B is that it relies on the program being able to decide which moves are good enough to be worthy of consideration ('plausible') in any given position and this proved to be a much harder problem to solve than speeding up type A searches where use of alpha-beta pruning combined with a number of other search heuristics dramatically improved performance.

One milestone was the abandonment of type B in 1973 by the team from Northwestern University responsible for the 'Chess' series of programs, who had won the first three ACM Computer Chess Championships (1970-1972). The resulting type A program, Chess 4.0, won that year's championship and its successors went on to come second in both the 1974 ACM Championship and that year's inaugral World Computer Chess Championship, before winning the ACM Championship again in 1975, 1976 and 1977.

One reason they gave for the switch was that they found it less stressful during competition, because it was difficult to anticipate which moves their type B programs would play and why! They also reported that type A was much easier to debug in the four months they had available and turned out to be just as fast: in the time it used to take to decide which moves were worthy of being searched, it was possible to just search the lot.

Ultimately, the brute force camp won out for these reasons and in the sense that their programs simply played better chess. The game of chess is not conducive to inerrantly discriminating between obviously bad, trivial, and good moves using a rigid set of rules. Traps are set and sprung by expert players who understand and master the many levels of depth and irony inherent to the game.

Furthermore, technological advances by orders of magnitude in processing power have made the brute force approach far more incisive in recent years than was the case in the early years. The result is that a very solid, tactical AI player has been built which is errorless to the limits of its search depth and time. This has left the strategic AI approach universally recognized as obsolete. It turned out to produce better results, at least in the field of chess, to let computers do what they do best (calculate) rather than coax them into imitating human thought processes and knowledge.

In modern times, the general consensus is that chess is theoretically a nearly-understood paradigm as an AI design goal and the Chinese game of Go is now at the forefront of challenges to AI designers. Again, Go is an example where human pattern recognition skills are currently far ahead of computer programs' and the number of possible moves in any position is so large that a successful program cannot use a brute force approach.

Computers 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.

Deep Thought, however, was still considerably below World Championship Level, as the then reigning world champion Garry 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 in Deep Blue - Kasparov, 1996, Game 1. This game was, in fact, the first time a reigning world champion had lost to a computer using regular 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. 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.

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 middlegame, tried a 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.

Hydra, a dedicated chess computer with custom hardware and 64 processors, has defeated other top computer programs in recent matches, and is probably the strongest computer player yet created. It completely crushed seventh-ranked Michael Adams 5.5-0.5 in a recent six-game match (though Adams' preparation was far less thorough than Kramnik's 2002 series). Some commentators [1] believe that Hydra will ultimately prove clearly superior to the very best human players, or if not its direct successor will.

Several other matches with computers against top human players were played recently:

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, starting with positions where the final result is known (e.g. where one side has been mated) and seeing which other positions are one move away from them, then which are one move from those etc. Ken Thompson, perhaps better known as the key designer of the UNIX operating system, was a pioneer in this area.

Endgame play had long been one of the great weaknesses of chess programs because of the depth of search needed, with some otherwise master-level programs being unable to win in positions that even intermediate human players would be able to force a win.

The results of the computer analysis sometimes surprised people. Thompson's Belle chess machine proved itself able to draw the theoretically lost ending of King and Rook against King and Queen despite not following the usual strategy to delay defeat of keeping the two pieces close together. Asked to explain the reasons behind some of the program's moves, Thompson was unable to do so beyond saying the program's database simply said the moves were the best.

Other positions, long believed to be 'won', turned out to take more moves against perfect play to actually win than were allowed by chess's fifty move rule. As a consequence, for some years the official laws of chess were changed to extend the number of moves allowed in these endings. After a while, the law reverted back to fifty moves in all positions - more such positions were discovered, complicating the rule still further, and it made no difference in human play, as they could not play the positions perfectly.

Over the years, other endgame database formats have been 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 Shredder or Fritz. All five-piece endings have now been analysed completely, and some of the six-piece endings are available. Only a few endings involving more pieces are likely to be analysed due to the large number of such possible positions and the resources needed to generate and store the resulting databases.

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, plus the fastest way of getting to that result. 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 prominently 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 two Queens which was used heavily to aid analysis by both sides.

Chronology of computer chess

Computer chess implementation issues

Developers of chess-playing computer system must decide on a number of fundamental implementation issues. These include

  • board representation (how a single position is represented in data structures),
  • search techniques (how to identify the possible moves and select the most promising ones for further examination),
  • leaf evaluation (how to evaluate the value of a board position, if no further search will be done from that position).

Implementors also need to decide if they will use endgame databases or other optimizations, and often implement common de facto chess standards.

Board representations

One of the simplest ways to represent a board is to create an 8x8 two-dimensional array (or, equivalently, a 64 element one-dimensional array). Each array element would identify what piece or pawn occupied the given square, or alternatively, if the square is empty. A common encoding is to consider 0 as empty, positive as white, and negative as black, e.g., white knight +1, black knight -1, white bishop +2, and so on.

One problem with this approach is that knight moves must be carefully examined to make sure they do not go "off the board". One solution is to use a 12x12 array instead, with the outer edges filled with nonsense blocking pieces; this means that knight moves do not have to implement special edge-checking code.

Better memory usage can be achieved with a 10x12 array, which provides the same functionalities as a 12x12 one by overlapping the leftmost and rightmost edge files (which are marked as off-the board). Some chess engines use 16x16 arrays to improve the speed of the rank and file number conversion and allow some special coding tricks for attacks etc.

However, another technique has gained favor in many programs: the bitboard. The bitboard approach was first used by Arthur Samuel in a checkers program, as documented by his 1959 paper "Some Studies in Machine Learning Using the Game of Checkers" in the IBM Journal of Research and Development. It was later rediscovered and adapted for chess programs by the Kaissa team in the Soviet Union in the late 1960s. A bitboard is a 64-bit sequence of bits (0 or 1), which indicates the absence or presence (false or true) of some state about each place on the board. A board position can then be represented using a series of bitboards. For example, a series of bitboards for each piece type or pawn, for each side, can represent the board position. See Bitboard.

Additional information must be stored as well as piece and pawn location, such as move number, which side is to move, whether or not castling is possible (and on which side), en passant information, draw-related information, and so on.

Search techniques

Computer chess programs consider chess moves as a game tree. In theory, they examine all moves, then all counter-moves to those moves, then all moves countering them, and so on, where each individual move by one player is called a "ply". This evaluation continues until it reaches a final "leaf" position which is evaluated.

A naïve implementation of this approach, however, would never finish in a practical amount of time, so various methods have been devised to greatly speed the search for good moves.

For more information, see:

Leaf evaluation

For most chess positions, computers cannot look ahead to all final possible positions. Instead, they must look ahead a few plies and then evaluate the final board position. The algorithm that evaluates final board positions is termed the "evaluation function", and these algorithms are often vastly different between different chess programs.

Nearly all evaluation functions evaluate positions in units and at the least consider material value. Thus, they will count up the amount of material on the board for each side (where a pawn is worth exactly 1 point, a knight is worth 3 points, a bishop is worth 3 points, a rook is worth 5 points and a queen is worth 9 points). The king is sometimes given an arbitrary high value such as 200 points to artificially include checkmate situation to position evaluation.

Evaluation functions take many other factors into account, however, such as pawn structure, the fact that doubled bishops are usually worth more, centralized pieces are worth more, and so on. The protection of kings is usually considered, as well as the phase of the game (opening, middle or endgame).

See Claude Elwood Shannon for a description of his early paper about a chess-playing program.

Using endgame databases

Some computer chess operators have suggested that endgame tablebases will actually weaken performance strength in chess computers. Because some positions are analyzed as forced wins for one side, the program will avoid these positions at all costs. However, many endgames are forced wins only with flawless play, where an even slight error would produce a different result. Consequently, most modern engines will play many endgames well enough on their own. A symptom of this problem is that computers may resign too early because they see that they are being forced into a position that is theoretically dead lost (although they may be thirty or more moves away from the end of the game, and most human opponents would find it hard to win in that time).

The Nalimov tablebases do not consider the fifty move rule, under which a game where fifty moves pass without a capture or pawn move is automatically drawn. This results in the tablebase returning results such as "Forced mate in 66 moves" in some positions which are actually a dead draw because of the fifty move rule.

Once reason for this is that if the rules of chess were to be changed once more, giving more time to win such positions, it will not be necessary to regenerate all the tablebases. It is also very easy for the program using the tablebases to notice and take account of this 'feature'.

The Nalimov 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. It is estimated that seven-piece tablebases will require more storage capacity than will be available in the forseeable future.

Since endgame positions are typically very simple, and with the power of desktop computers growing exponentially, most engines can calculate in endgames very effectively, making the usefulness of endgame databases questionable in light of these serious shortcomings.

Other optimizations

Many other optimizations can be used to make chess-playing programs stronger. For example, transposition tables are used to record positions that have been previously evaluated, to save recalculation of them. Refutation tables record key moves that "refute" what appears to be a good move; these are typically tried first in variant positions (since a move that refutes one position is likely to refute another). Opening books aid computer programs by giving common openings that are considered good play (and good ways to counter poor openings).

Of course, faster hardware and additional processors can improve chess-playing program abilities, and some systems (such as Deep Blue) use specialized chess hardware instead of solely software implementations.

Standards

Computer chess programs usually support a number of common de facto standards. Nearly all of today's programs can read and write game moves as Portable Game Notation (PGN), and can read and write individual positions as Forsyth-Edwards Notation (FEN). Older chess programs often only understood long algebraic notation, but today users expect chess programs to understand standard algebraic chess notation.

Most computer chess programs are divided into an engine (which computes the best move given a current position) and a user interface. Most engines are separate programs from the user interface, and the two parts communicate to each other using a public communication protocol. The most popular protocol is the Xboard/Winboard Communication protocol. Another open alternate chess communication protocol is the Universal Chess Interface. By dividing chess programs into these two pieces, developers can write only the user interface, or only the engine, without needing to write both parts of the program. (See also List of chess engines.)

Playing strength vs. the computer speed

It has been estimated that doubling the computer speed gains approximately 50-70 ELO points in playing strength. However, this applies mainly to computer-vs-computer matches, and not to computer-vs-human matches.

Other chess software

There are several other forms of chess-related computer software, including the following:

  • 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.

Computer chess theorists

Well-known computer chess theorists include:

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.

One potentially fruitful field of research is in distributed computation, where many computers are joined together through the internet and are each tasked with a small section of the overall search tree to analyse. The leading project is the ChessBrain project, which gained a world record in 2004 for the largest number of computers ever playing a game of chess simultaneously (2,070)

Solving chess

The number of board positions that a chess board may be placed in is astronomical- more than the number of atoms in the universe. However, the number of legal positions is rather smaller, under 1050. This is somewhat too large to be solved by conventional technology in less than a few centuries, even with a thousand fast chess computers each searching a billion positions per second, and using alpha-beta pruning.

It might, however, theoretically be tackled by quantum computing in combination with alpha-beta pruning. These techniques each reduce the average number of branches of the game tree by 2- and jointly the combination appears to reduce the tree size to one that might be completed in a practical time; about 10(50/4) ~ 1013 positions, which could be completed on a single computer in a year at only ~100,000 positions per second.

See also

External links