Computer chess
Encyclopedia
Computer chess is computer architecture
encompassing hardware
and software
capable of playing chess
autonomously without human guidance. Computer chess acts as solo entertainment (allowing players to practice and to better themselves when no human opponents are available), as aids to chess analysis, for computer chess competitions, and as research to provide insights into human cognition
.
, Fruit and GNU Chess
that can be downloaded from the Internet
for free. These engines are able to play a game that, when run on an up-to-date personal computer
, can defeat most master players under tournament conditions. Top programs such as the Proprietary software programs Shredder
or Fritz
or the open source
program Stockfish
have surpassed even world champion caliber players at blitz
and short time control
s. , Rybka
is top-rated in CCRL, CEGT, CSS, SSDF
, and WBEC rating lists and has won many recent official computer chess tournaments such as CCT 8 and 9, 2006 Dutch Open Computer Championship, the 16th IPCCC, and the 15th World Computer Chess Championship
. As of December 17, 2010, Houdini
is now top-rated chess program on IPON rating list edging out Rybka.
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. In 1989, Levy was defeated 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 was not 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½-2½ in a return match. A documentary mainly about the confrontation was made in 2003, titled Game Over: Kasparov and the Machine
. IBM keeps a web site of the event.
With increasing processing power, chess programs running on commercially available workstations began to rival top flight players. In 1998, Rebel 10
defeated Viswanathan Anand
, who at the time was ranked second in the world, by a score of 5-3. However most of those games were not played at normal time controls. Out of the eight games, four were blitz
games (five minutes plus five seconds Fischer delay (see time control
) for each move); these Rebel won 3-1. Two were semi-blitz games (fifteen minutes for each side) that Rebel won as well (1½-½). Finally, two games were played as regular tournament games (forty moves in two hours, one hour sudden death); here it was Anand who won ½-1½. In fast games, computers played better than humans, but at classical time controls - at which a player's rating is determined - the advantage was not so clear.
In the early 2000s, commercially available programs such as Junior
and Fritz
were able to draw matches against former world champion Garry Kasparov
and classical world champion Vladimir Kramnik
.
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 against such attacks. True to form, Fritz found a watertight defense 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, Garry Kasparov
played Junior
, another chess computer program, in New York
. The match ended 3-3.
In November 2003, Garry Kasparov
played X3D Fritz
. The match ended 2-2.
In 2005, Hydra
, a dedicated chess computer with custom hardware and sixty-four processors and also winner of the 14th IPCCC in 2005, defeated seventh-ranked Michael Adams 5½-½ in a six-game match (though Adams' preparation was far less thorough than Kramnik's for the 2002 series).
In November–December 2006, World Champion Vladimir Kramnik
played Deep Fritz. This time the computer won; the match ended 2-4. Kramnik was able to view the computer's opening book. In the first five games Kramnik steered the game into a typical "anti-computer" positional contest. He lost one game (overlooking a mate in one), and drew the next four. In the final game, in an attempt to draw the match, Kramnik played the more aggressive Sicilian Defence
and was crushed.
There was speculation that interest in human-computer chess competition would plummet as a result of the 2006 Kramnik-Deep Fritz match. According to McGill University computer science professor Monty Newborn, for example, "the science is done".
Human-computer chess matches showed the best computer systems overtaking human chess champions in the late 1990s. For the 40 years prior to that, the trend had been that the best machines gained about 40 points per year in the Elo rating while the best humans only gained roughly 2 points per year. The highest rating obtained by a computer in human competition was Deep Thought
's USCF rating of 2551 in 1988 and FIDE no longer accepts human-computer results in their rating lists. Specialized machine-only Elo pools have been created for rating machines, but such numbers, while similar in appearance, should not be directly compared. A recent top chess engine, Rybka
, has an estimated Elo rating of about 3200 (when running on an up-to-date PC, as computed by SSDF
).
Chess engines continue to improve. In 2009 chess engines running on slower hardware have reached the grandmaster level. A mobile phone
won a category 6 tournament with a performance rating 2898: chess engine Hiarcs
13 running inside Pocket Fritz
4 on the mobile phone HTC Touch HD
won the Copa Mercosur tournament in Buenos Aires, Argentina with 9 wins and 1 draw on August 4–14, 2009. Pocket Fritz 4 searches fewer than 20,000 positions per second. This is in contrast to supercomputers such as Deep Blue that searched 200 million positions per second.
Advanced Chess
is a form of chess developed in 1998 by Kasparov where a human plays against another human, and both have access to computers to enhance their strength. The resulting "advanced" player was argued by Kasparov to be stronger than a human or computer alone, although this has not been proven.
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 Chess Engine Communication Protocol
(CECP). Another open alternate chess communication protocol is the Universal Chess Interface
(UCI). 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.)
Implementers also need to decide if they will use endgame databases or other optimizations, and often implement common de facto chess standards.
used to represent each chess position is key to the performance of move generation and position evaluation. Methods include pieces stored in an array ("mailbox" and "0x88"), piece positions stored in a list ("piece list"), collections of bit-sets for piece locations ("bitboard
s"), and huffman coded
positions for compact long-term storage.
Type A programs would use a "brute force
" approach, examining every possible position for a fixed number of moves using the minimax algorithm
. Shannon believed this would be impractical for two reasons.
First, with approximately thirty moves possible in a typical real-life position, he expected that searching the approximately 109 positions involved in looking three moves ahead for both sides (six plies
) would take about sixteen minutes, even in the "very optimistic" case that the chess computer evaluated a million positions every second. (It took about forty years to achieve this speed.)
Second, it ignored the problem of quiescence, 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 two improvements:
This would enable them to look further ahead ('deeper') at the most significant lines in a reasonable time. The test of time has borne out the first approach; all modern programs employ a terminal quiescence search before evaluating positions. The second approach (now called forward pruning) has been dropped in favor of search extensions.
Adriaan de Groot
interviewed a number of chess players of varying strengths, and concluded that 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 recognizable sub-positions, rather 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 with superior hardware and search extension techniques.
One of the few chess grandmasters to devote himself seriously to computer chess was former World Chess Champion Mikhail Botvinnik
, who wrote several works on the subject. He also held a doctorate in electrical engineering. Working with relatively primitive hardware available in the Soviet Union
in the early 1960s, Botvinnik had no choice but to investigate software move selection techniques; at the time only the most powerful computers could achieve much beyond a three-ply full-width search, and Botvinnik had no such machines. In 1965 Botvinnik was a consultant to the ITEP team in a US-Soviet computer chess match (see Kotok-McCarthy
).
One developmental milestone occurred when the team from Northwestern University
, which was responsible for the Chess
series of programs and won the first three ACM
Computer Chess Championships (1970–72), abandoned type B searching in 1973. The resulting program, Chess 4.0, won that year's championship and its successors went on to come in second in both the 1974 ACM Championship and that year's inaugural 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 just to search all of them.
In fact, Chess 4.0 set the paradigm that was and still is followed essentially by all modern Chess programs today. Chess 4.0 type programs won out for the simple reason that their programs played better chess. Such programs did not try to mimic human thought processes, but relied on full width alpha-beta
and negascout
searches. Most such programs (including all modern programs today) also included a fairly limited selective part of the search based on quiescence searches, and usually extensions and pruning (particularly null move pruning from the 1990s onwards) which were triggered based on certain conditions in an attempt to weed out or reduce obviously bad moves (history moves) or to investigate interesting nodes (e.g. check extensions, passed pawn
s on seventh rank, etc.). Extension and pruning triggers have to be used very carefully however. Over extend and the program wastes too much time looking at uninteresting positions. If too much is pruned, there is a risk cutting out interesting nodes. Chess programs differ in terms of how and what types of pruning and extension rules are included as well as in the evaluation function. Some programs are believed to be more selective than others (for example Deep Blue was known to be less selective than most commercial programs because they could afford to do more complete full width searches), but all have a base full width search as a foundation and all have some selective components (Q-search, pruning/extensions).
Though such additions meant that the program did not truly examine every node within its search depth (so it would not be truly brute force in that sense), the rare mistakes due to these selective searches was found to be worth the extra time it saved because it could search deeper. In that way Chess programs can get the best of both worlds.
Furthermore, technological advances by orders of magnitude in processing power have made the brute force approach far more incisive than was the case in the early years. The result is that a very solid, tactical AI player aided by some limited positional knowledge built in by the evaluation function and pruning/extension rules began to match the best players in the world. It turned out to produce excellent 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 1997 Deep Blue defeated World Champion Garry Kasparov
, marking the first time a computer has defeated a reigning world chess champion in standard time control.
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 a certain maximum search depth or the program determines that a final "leaf" position has been reached (e.g. checkmate).
A naive implementation of this approach can only search to a small depth in a practical amount of time, so various methods have been devised to greatly speed the search for good moves.
For more information, see:
", and these algorithms are often vastly different between different chess programs.
Evaluation functions typically evaluate positions in hundredths of a pawn, and consider material value along with other factors affecting the strength of each side. When counting up the material for each side, typical values for pieces are 1 point for a pawn
, 3 points for a knight
or bishop
, 5 points for a rook
, and 9 points for a queen
. (See Chess piece relative value.) By convention, a positive evaluation favors White, and a negative evaluation favors Black.
The king
is sometimes given an arbitrary high value such as 200 points (Shannon's paper) or 1,000,000,000 points (1961 USSR program) to ensure that a checkmate outweighs all other factors . Evaluation function
s take many factors into account, such as pawn structure, the fact that a pair of 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).
s have the potential to weaken performance strength in chess computers if incorrectly used. Because some positions are analyzed as forced wins for one side, the program will avoid the losing side of positions at all costs. However, many endgames are forced wins only with flawless play, where even a 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). This observation is only relevant when a computer program is in a situation where it has a choice between two losing moves, one of which is actually more difficult for the opponent, but leads to a tablebase position with a known value, and is hence of very minor importance.
The Nalimov tablebases do not consider the fifty-move rule, under which a game where fifty moves pass without a capture or pawn move can be claimed to be a draw by either player. This results in the tablebase returning results such as "Forced mate in sixty-six moves" in some positions which would actually be drawn because of the fifty-move rule. However, a correctly programmed engine does know about the fifty-move rule, and in any case if using an endgame tablebase will choose the move that leads to the quickest win (even if it would fall foul of the fifty-move rule with perfect play). If playing an opponent not using a tablebase, such a choice will give good chances of winning within fifty moves.
One 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. To cover all the six-piece endings requires approximately 1.2 terabyte
. It is estimated that seven-piece tablebases will require more storage capacity than will be available in the foreseeable future.
It is surprising, but easily verified, that without an endgame tablebase even otherwise very strong chess engines may fail to find a winning plan even in endings with six or fewer pieces, when they need more moves than the calculation horizon to achieve a checkmate, a win of material or the advance of a pawn. Many endings require more moves than their calculation horizon.
Computers have been used to analyze 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. In 1977 Thompson's Belle chess machine used the endgame tablebase for a king
and rook
against king and queen
and was able to draw that theoretically lost ending against several masters (see Philidor position#Queen versus rook). This was despite not following the usual strategy to delay defeat by keeping the defending king and rook close together for as long as possible. 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 evaluated its moves as best it could.
Most grandmasters
declined to play against the computer in the queen versus rook endgame, but Walter Browne accepted the challenge. A queen versus rook position was set up in which the queen can win in thirty moves, with perfect play. Browne was allowed 2½ hours to play fifty moves, otherwise a draw would be claimed under the fifty-move rule. After forty-five moves, Browne agreed to a draw, being unable to force checkmate or win the rook within the next five moves. In the final position, Browne was still seventeen moves away from checkmate, but not quite that far away from winning the rook. Browne studied the endgame, and played the computer again a week later in a different position in which the queen can win in thirty moves. This time, he captured the rook on the fiftieth move, giving him a winning position , .
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 FIDE rules of chess were changed to extend the number of moves allowed in these endings. After a while, the rule reverted 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 Rybka
, Shredder
or Fritz
. All endgames with five or fewer pieces have been analyzed completely. Of endgames with six pieces all positions have been analyzed except for trivial positions with five pieces against a lone king. Some seven-piece endgames, have been analyzed by Marc Bourzutschky and Yakov Konoval. In all of these endgame databases it is assumed that castling is no longer possible.
Endgame databases are generated by storing in memory the values of positions which have been encountered so far, and using these results to lop off the ends of the search trees if they arise again. Although the number of possible games after a number of moves rises exponentially with the number of moves, the number of possible positions with a few pieces is exponential only in the number of pieces — and effectively limited however many end game moves are searched. The simple expediency of remembering the value of all previously reached positions means that the limiting factor in solving end games is simply the amount of memory available in the computer. While computer memory sizes are increasing exponentially, there is no reason why end games of increasing complexity should not continue to be solved.
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 or longest 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.
s 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). Many chess engines use pondering to increase their strength.
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 only software. Another way to examine more chess positions is distribute the analysis of positions to many computers. The ChessBrain project was a chess program that distributed the search tree computation through the Internet. In 2004 the ChessBrain played chess using 2,070 computers.
points in playing strength .
, including the following:
chess are generally considered to be rather remote. It is widely conjectured that there is no computationally inexpensive method to solve chess even in the very weak sense of determining with certainty the value of the initial position, and hence the idea of solving chess in the stronger sense of obtaining a practically usable description of a strategy for perfect play for either side seems unrealistic today. However, it has not been proven that no computationally cheap way of determining the best move in a chess position exists, nor even that a traditional alpha-beta-searcher running on present-day computing hardware could not solve the initial position in an acceptable amount of time. The difficulty in proving the latter lies in the fact that, while the number of board positions that could happen in the course of a chess game is huge (on the order of 1040), it is hard to rule out with mathematical certainty the possibility that the initial position allows either side to force a mate or a threefold repetition
after relatively few moves, in which case the search tree might encompass only a very small subset of the set of possible positions. It has been mathematically proven that generalized chess (chess played with an arbitrarily large number of pieces on an arbitrarily large chessboard) is EXPTIME-complete, meaning that determining the winning side in an arbitrary position of generalized chess provably takes exponential time in the worst case; however, this theoretical result gives no lower bound on the amount of work required to solve ordinary 8x8 chess.
called The Turk
became famous before being exposed as a hoax. Before the development of digital computing, serious trials based on automata such as El Ajedrecista
of 1912, were too complex and limited to be useful for playing full games of chess. 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.
Computer architecture
In computer science and engineering, computer architecture is the practical art of selecting and interconnecting hardware components to create computers that meet functional, performance and cost goals and the formal modelling of those systems....
encompassing hardware
Computer hardware
Personal computer hardware are component devices which are typically installed into or peripheral to a computer case to create a personal computer upon which system software is installed including a firmware interface such as a BIOS and an operating system which supports application software that...
and software
Computer software
Computer software, or just software, is a collection of computer programs and related data that provide the instructions for telling a computer what to do and how to do it....
capable of playing chess
Chess
Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...
autonomously without human guidance. Computer chess acts as solo entertainment (allowing players to practice and to better themselves when no human opponents are available), as aids to chess analysis, for computer chess competitions, and as research to provide insights into human cognition
Cognition
In science, cognition refers to mental processes. These processes include attention, remembering, producing and understanding language, solving problems, and making decisions. Cognition is studied in various disciplines such as psychology, philosophy, linguistics, and computer science...
.
Availability
Chess-playing computers are now accessible to the average consumer. From the mid-70's to the present day, dedicated chess computers have been available for purchase. There are many chess engines such as CraftyCrafty
Crafty is a chess program written by UAB professor Dr. Robert Hyatt. It is directly derived from Cray Blitz, winner of the 1983 and 1986 World Computer Chess Championships....
, Fruit and GNU Chess
GNU Chess
GNU Chess is a computer program which plays a full game of chess against a human or other computer program.GNU Chess is one of the oldest computer chess programs for Unix-based computers and one of the earliest available with full source code....
that can be downloaded from the Internet
Internet
The Internet is a global system of interconnected computer networks that use the standard Internet protocol suite to serve billions of users worldwide...
for free. These engines are able to play a game that, when run on an up-to-date personal computer
Personal computer
A personal computer is any general-purpose computer whose size, capabilities, and original sales price make it useful for individuals, and which is intended to be operated directly by an end-user with no intervening computer operator...
, can defeat most master players under tournament conditions. Top programs such as the Proprietary software programs Shredder
Shredder (chess)
Shredder is a commercial chess program developed in Germany by Stefan Meyer-Kahlen in 1993. Shredder won the World Microcomputer Chess Championship in 1996 and 2000, the World Computer Chess Championship in 1999 and 2003, the World Computer Speed Chess Championship in 2002, 2003, 2004, 2005, and...
or Fritz
Fritz (chess)
Fritz is a German chess program developed by Frans Morsch and Mathias Feist and published by ChessBase. There is also a version called Deep Fritz that is designed for multiprocessing....
or the open source
Open source
The term open source describes practices in production and development that promote access to the end product's source materials. Some consider open source a philosophy, others consider it a pragmatic methodology...
program Stockfish
Stockfish (chess)
Stockfish is an open source chess engine, developed by Tord Romstad, Joona Kiiski and Marco Costalba and licensed under the GNU General Public License version 3. The current version 2.1.1 is available as C++ source code, and also has precompiled versions for Microsoft Windows, Mac OS X Snow...
have surpassed even world champion caliber players at blitz
Blitz chess
Fast chess, also known as blitz chess, lightning chess, sudden death, speed chess, bullet chess and rapid chess, is a type of chess game in which each side is given less time to make their moves than under the normal tournament time controls of 60 to 180 minutes per player.-Overview:The different...
and short time control
Time control
A time control is a mechanism in the tournament play of almost all two-player board games so that each round of the match can finish in a timely way and the tournament can proceed. Time controls are typically enforced by means of a game clock...
s. , Rybka
Rybka
Rybka is a computer chess engine designed by International Master Vasik Rajlich. , Rybka is one of the top-rated engines on chess engine rating lists and has won many computer chess tournaments...
is top-rated in CCRL, CEGT, CSS, SSDF
Swedish Chess Computer Association
The Swedish Chess Computer Association is an organization that tests computer chess software by playing chess programs against one another and producing a rating list. On September 26, 2008, the list was released with Deep Rybka 3 leading with an estimated Elo rating of 3238. Rybka's listing in...
, and WBEC rating lists and has won many recent official computer chess tournaments such as CCT 8 and 9, 2006 Dutch Open Computer Championship, the 16th IPCCC, and the 15th World Computer Chess Championship
World Computer Chess Championship
World Computer Chess Championship is an annual event where computer chess engines compete against each other. The event is organized by the International Computer Games Association...
. As of December 17, 2010, Houdini
Houdini (chess)
Houdini is a chess engine for Windows, by Belgian programmer Robert Houdart. Free for non-commercial use , later versions are not free. Since the release of version 1.5 on 15 December 2010, it has taken the top spot in every rating list that includes it...
is now top-rated chess program on IPON rating list edging out Rybka.
Computers versus humans
For a time in the 1970s and 1980s it was unclear whether any chess program would ever be able to defeat the expertise of top humans. In 1968, International Master David LevyDavid Levy (chess player)
David Neil Laurence Levy , is a Scottish International Master of chess, a businessman noted for his involvement with computer chess and artificial intelligence, and the founder of the Computer Olympiads and the Mind Sports Olympiads. He has written more than 40 books on chess and computers.- Life...
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
Chess (Northwestern University)
Chess was a pioneering chess program from the 1970s, authored by Larry Atkin and David Slate at Northwestern University. Chess ran on Control Data Corporation's line of supercomputers. It dominated the first computer chess tournaments, such as the World Computer Chess Championship and ACM's North...
(the strongest computer at the time), but acknowledged then that it would not be long before he would be surpassed. In 1989, Levy was defeated by the computer Deep Thought
Deep Thought (chess computer)
Deep Thought was a computer designed to play chess. Deep Thought was initially developed at Carnegie Mellon University and later at IBM. It was second in the line of chess computers developed by Feng-hsiung Hsu, starting with ChipTest and culminating in Deep Blue...
in an exhibition match.
Deep Thought, however, was still considerably below World Championship Level, as the then reigning world champion Garry Kasparov
Garry Kasparov
Garry Kimovich Kasparov is a Russian chess grandmaster, a former World Chess Champion, writer, political activist, and one of the greatest chess players of all time....
demonstrated in two sterling wins in 1989. It was not 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
Deep Blue - Kasparov, 1996, Game 1
Deep Blue–Kasparov, 1996, Game 1 is a famous chess game in which a computer played against a human being. It was the first game played in the 1996 Deep Blue versus Garry Kasparov match, and the first time that a chess-playing computer defeated a reigning world champion under normal chess tournament...
. 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
Draw (chess)
In chess, a draw is when a game ends in a tie. It is one of the possible outcomes of a game, along with a win for White and a win for Black . Usually, in tournaments a draw is worth a half point to each player, while a win is worth one point to the victor and none to the loser.For the most part,...
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½-2½ in a return match. A documentary mainly about the confrontation was made in 2003, titled Game Over: Kasparov and the Machine
Game Over: Kasparov and the Machine
Game Over: Kasparov and the Machine is a 2003 documentary film by Vikram Jayanti about the match between Garry Kasparov, the highest rated chess player in history and the World Champion for 15 years , and Deep Blue, a chess-playing computer created by IBM...
. IBM keeps a web site of the event.
With increasing processing power, chess programs running on commercially available workstations began to rival top flight players. In 1998, Rebel 10
REBEL (chess)
REBEL was a world champion chess program developed by Ed Schröder. Development of REBEL started in 1980 on a TRS-80, and it was ported many times to dedicated hardware and the fastest microprocessors of the day:...
defeated Viswanathan Anand
Viswanathan Anand
V. Anand or Anand Viswanathan, usually referred as Viswanathan Anand, is an Indian chess Grandmaster, the current World Chess Champion, and currently second highest rated player in the world....
, who at the time was ranked second in the world, by a score of 5-3. However most of those games were not played at normal time controls. Out of the eight games, four were blitz
Blitz chess
Fast chess, also known as blitz chess, lightning chess, sudden death, speed chess, bullet chess and rapid chess, is a type of chess game in which each side is given less time to make their moves than under the normal tournament time controls of 60 to 180 minutes per player.-Overview:The different...
games (five minutes plus five seconds Fischer delay (see time control
Time control
A time control is a mechanism in the tournament play of almost all two-player board games so that each round of the match can finish in a timely way and the tournament can proceed. Time controls are typically enforced by means of a game clock...
) for each move); these Rebel won 3-1. Two were semi-blitz games (fifteen minutes for each side) that Rebel won as well (1½-½). Finally, two games were played as regular tournament games (forty moves in two hours, one hour sudden death); here it was Anand who won ½-1½. In fast games, computers played better than humans, but at classical time controls - at which a player's rating is determined - the advantage was not so clear.
In the early 2000s, commercially available programs such as Junior
Junior (chess)
Junior is a computer chess program authored by the Israeli programmers Amir Ban and Shay Bushinsky. Grandmaster Boris Alterman assisted, in particular with the opening book...
and Fritz
Fritz (chess)
Fritz is a German chess program developed by Frans Morsch and Mathias Feist and published by ChessBase. There is also a version called Deep Fritz that is designed for multiprocessing....
were able to draw matches against former world champion Garry Kasparov
Garry Kasparov
Garry Kimovich Kasparov is a Russian chess grandmaster, a former World Chess Champion, writer, political activist, and one of the greatest chess players of all time....
and classical world champion Vladimir Kramnik
Vladimir Kramnik
Vladimir Borisovich Kramnik is a Russian chess grandmaster. He was the Classical World Chess Champion from 2000 to 2006, and the undisputed World Chess Champion from 2006 to 2007...
.
In October 2002, Vladimir Kramnik
Vladimir Kramnik
Vladimir Borisovich Kramnik is a Russian chess grandmaster. He was the Classical World Chess Champion from 2000 to 2006, and the undisputed World Chess Champion from 2006 to 2007...
and Deep Fritz competed in the eight-game Brains in Bahrain
Brains in Bahrain
Brains in Bahrain was an eight-game chess match between World Chess Champion Vladimir Kramnik and the computer program Deep Fritz 7, held in October 2002. The match ended in a tie 4-4, with two wins for each participant and four draws.-Outcome of games:...
match, which ended in a draw. Kramnik won games 2 and 3 by "conventional" anti-computer tactics
Anti-computer tactics
Anti-computer tactics are a style of play used by humans to beat strong computer opponents at various games, especially in board games such as chess and Arimaa. It involves playing conservatively for a long-term advantage the computer is not able to see in its game tree search...
- 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 against such attacks. True to form, Fritz found a watertight defense 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, Garry Kasparov
Garry Kasparov
Garry Kimovich Kasparov is a Russian chess grandmaster, a former World Chess Champion, writer, political activist, and one of the greatest chess players of all time....
played Junior
Junior (chess)
Junior is a computer chess program authored by the Israeli programmers Amir Ban and Shay Bushinsky. Grandmaster Boris Alterman assisted, in particular with the opening book...
, another chess computer program, in New York
New York
New York is a state in the Northeastern region of the United States. It is the nation's third most populous state. New York is bordered by New Jersey and Pennsylvania to the south, and by Connecticut, Massachusetts and Vermont to the east...
. The match ended 3-3.
In November 2003, Garry Kasparov
Garry Kasparov
Garry Kimovich Kasparov is a Russian chess grandmaster, a former World Chess Champion, writer, political activist, and one of the greatest chess players of all time....
played X3D Fritz
X3D Fritz
X3D Fritz was a version of the Fritz chess program, which in November 2003 played a four-game Human-computer chess match against world number one Grandmaster Garry Kasparov...
. The match ended 2-2.
In 2005, Hydra
Hydra (chess)
Hydra was a chess machine, designed by a team with Dr. Christian "Chrilly" Donninger, Dr. Ulf Lorenz, GM Christopher Lutz and Muhammad Nasir Ali. Since 2006 the development team consised only of Donninger and Lutz. Hydra was under the patronage of the PAL Group and Sheikh Tahnoon Bin Zayed Al...
, a dedicated chess computer with custom hardware and sixty-four processors and also winner of the 14th IPCCC in 2005, defeated seventh-ranked Michael Adams 5½-½ in a six-game match (though Adams' preparation was far less thorough than Kramnik's for the 2002 series).
In November–December 2006, World Champion Vladimir Kramnik
Vladimir Kramnik
Vladimir Borisovich Kramnik is a Russian chess grandmaster. He was the Classical World Chess Champion from 2000 to 2006, and the undisputed World Chess Champion from 2006 to 2007...
played Deep Fritz. This time the computer won; the match ended 2-4. Kramnik was able to view the computer's opening book. In the first five games Kramnik steered the game into a typical "anti-computer" positional contest. He lost one game (overlooking a mate in one), and drew the next four. In the final game, in an attempt to draw the match, Kramnik played the more aggressive Sicilian Defence
Sicilian Defence
The Sicilian Defence is a chess opening that begins with the moves:The Sicilian is the most popular and best-scoring response to White's first move 1.e4...
and was crushed.
There was speculation that interest in human-computer chess competition would plummet as a result of the 2006 Kramnik-Deep Fritz match. According to McGill University computer science professor Monty Newborn, for example, "the science is done".
Human-computer chess matches showed the best computer systems overtaking human chess champions in the late 1990s. For the 40 years prior to that, the trend had been that the best machines gained about 40 points per year in the Elo rating while the best humans only gained roughly 2 points per year. The highest rating obtained by a computer in human competition was Deep Thought
Deep Thought (chess computer)
Deep Thought was a computer designed to play chess. Deep Thought was initially developed at Carnegie Mellon University and later at IBM. It was second in the line of chess computers developed by Feng-hsiung Hsu, starting with ChipTest and culminating in Deep Blue...
's USCF rating of 2551 in 1988 and FIDE no longer accepts human-computer results in their rating lists. Specialized machine-only Elo pools have been created for rating machines, but such numbers, while similar in appearance, should not be directly compared. A recent top chess engine, Rybka
Rybka
Rybka is a computer chess engine designed by International Master Vasik Rajlich. , Rybka is one of the top-rated engines on chess engine rating lists and has won many computer chess tournaments...
, has an estimated Elo rating of about 3200 (when running on an up-to-date PC, as computed by SSDF
Swedish Chess Computer Association
The Swedish Chess Computer Association is an organization that tests computer chess software by playing chess programs against one another and producing a rating list. On September 26, 2008, the list was released with Deep Rybka 3 leading with an estimated Elo rating of 3238. Rybka's listing in...
).
Chess engines continue to improve. In 2009 chess engines running on slower hardware have reached the grandmaster level. A mobile phone
Mobile phone
A mobile phone is a device which can make and receive telephone calls over a radio link whilst moving around a wide geographic area. It does so by connecting to a cellular network provided by a mobile network operator...
won a category 6 tournament with a performance rating 2898: chess engine Hiarcs
HIARCS
HIARCS is a commercial computer chess program developed by Mark Uniacke. Its name is an acronym stands for higher intelligence auto response chess system.-Overview:...
13 running inside Pocket Fritz
Pocket Fritz
Pocket Fritz, which is currently at version 4, is a chess playing program for Pocket PC personal digital assistants . Pocket Fritz 4 uses HIARCS as the chess engine. Pocket Fritz 2 used a port of the Shredder chess engine....
4 on the mobile phone HTC Touch HD
HTC Touch HD
The HTC Touch HD, also known as the HTC T828X or its codename the HTC Blackstone, is a Windows Mobile 6.1 -powered luxury Pocket PC designed and manufactured by HTC...
won the Copa Mercosur tournament in Buenos Aires, Argentina with 9 wins and 1 draw on August 4–14, 2009. Pocket Fritz 4 searches fewer than 20,000 positions per second. This is in contrast to supercomputers such as Deep Blue that searched 200 million positions per second.
Advanced Chess
Advanced Chess
Advanced Chess is a relatively new form of chess, wherein each human player uses a computer chess program to help him explore the possible results of candidate moves...
is a form of chess developed in 1998 by Kasparov where a human plays against another human, and both have access to computers to enhance their strength. The resulting "advanced" player was argued by Kasparov to be stronger than a human or computer alone, although this has not been proven.
Implementation issues
The developers of a 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.
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
Portable Game Notation
Portable Game Notation is a computer-processible format for recording chess games ; many chess programs recognize this extremely popular format due to its being stored in plain text.-History:...
(PGN), and can read and write individual positions as Forsyth-Edwards Notation
Forsyth-Edwards Notation
Forsyth–Edwards Notation is a standard notation for describing a particular board position of a chess game. The purpose of FEN is to provide all the necessary information to restart a game from a particular position....
(FEN). Older chess programs often only understood long algebraic notation
Algebraic chess notation
Algebraic notation is a method for recording and describing the moves in a game of chess. It is now standard among all chess organizations and most books, magazines, and newspapers...
, but today users expect chess programs to understand standard algebraic chess notation
Algebraic chess notation
Algebraic notation is a method for recording and describing the moves in a game of chess. It is now standard among all chess organizations and most books, magazines, and newspapers...
.
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 Chess Engine Communication Protocol
Chess Engine Communication Protocol
The Chess Engine Communication Protocol is an open communication protocol that enables a chess engine to communicate with its user interface....
(CECP). Another open alternate chess communication protocol is the Universal Chess Interface
Universal Chess Interface
The Universal Chess Interface is an open communication protocol that enables a chess program's engine to communicate with its user interface....
(UCI). 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.)
Implementers also need to decide if they will use endgame databases or other optimizations, and often implement common de facto chess standards.
Board representations
The data structureData structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
used to represent each chess position is key to the performance of move generation and position evaluation. Methods include pieces stored in an array ("mailbox" and "0x88"), piece positions stored in a list ("piece list"), collections of bit-sets for piece locations ("bitboard
Bitboard
A bitboard is a data structure commonly used in computer systems that play board games.A bitboard, often used for boardgames such as chess, checkers and othello, is a specialization of the bitset data structure, where each bit represents a game position or state, designed for optimization of speed...
s"), and huffman coded
Huffman coding
In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable-length code table for encoding a source symbol where the variable-length code table has been derived in a particular way based on...
positions for compact long-term storage.
Search techniques
The first paper on the subject was by Claude Shannon — published in 1950 before anyone had programmed a computer to play chess. He 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
Brute-force search
In computer science, brute-force search or exhaustive search, also known as generate and test, is a trivial but very general problem-solving technique that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's...
" approach, examining every possible position for a fixed number of moves using the minimax algorithm
Minimax
Minimax is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a worst case scenario. Alternatively, it can be thought of as maximizing the minimum gain...
. Shannon believed this would be impractical for two reasons.
First, with approximately thirty moves possible in a typical real-life position, he expected that searching the approximately 109 positions involved in looking three moves ahead for both sides (six plies
Ply (game theory)
In two-player sequential games, a ply refers to one turn taken by one of the players. The word is used to clarify what is meant when one might otherwise say "turn"....
) would take about sixteen minutes, even in the "very optimistic" case that the chess computer evaluated a million positions every second. (It took about forty years to achieve this speed.)
Second, it ignored the problem of quiescence, trying to only evaluate a position that is at the end of an exchange
Exchange (chess)
In the tactics and strategy in the board game of chess, an exchange or trade of chess pieces is series of closely related moves, typically sequential, in which the two players capture each others pieces. Any types of pieces except the kings may possibly be exchanged, i. e. captured in an...
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 two improvements:
- Employ a quiescence searchQuiescence searchQuiescence search is an algorithm typically used to evaluate minimax game trees in game-playing computer programs. It is a remedy for the horizon problem faced by AI engines for various games like chess and Go.-The horizon effect:...
. - Only look 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. The test of time has borne out the first approach; all modern programs employ a terminal quiescence search before evaluating positions. The second approach (now called forward pruning) has been dropped in favor of search extensions.
Adriaan de Groot
Adriaan de Groot
Adrianus Dingeman de Groot was a Dutch chess master and psychologist, who conducted some of the most famous chess experiments of all time in the 1940s-60...
interviewed a number of chess players of varying strengths, and concluded that both masters
Chess master
A chess master is a chess player of such skill that he/she can usually beat chess experts, who themselves typically prevail against most amateurs. Among chess players, the term is often abbreviated to master, the meaning being clear from context....
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
Pattern recognition
In machine learning, pattern recognition is the assignment of some sort of output value to a given input value , according to some specific algorithm. An example of pattern recognition is classification, which attempts to assign each input value to one of a given set of classes...
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 recognizable sub-positions, rather 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 with superior hardware and search extension techniques.
One of the few chess grandmasters to devote himself seriously to computer chess was former World Chess Champion Mikhail Botvinnik
Mikhail Botvinnik
Mikhail Moiseyevich Botvinnik, Ph.D. was a Soviet and Russian International Grandmaster and three-time World Chess Champion. Working as an electrical engineer and computer scientist at the same time, he was one of the very few famous chess players who achieved distinction in another career while...
, who wrote several works on the subject. He also held a doctorate in electrical engineering. Working with relatively primitive hardware available in the Soviet Union
Soviet Union
The Soviet Union , officially the Union of Soviet Socialist Republics , was a constitutionally socialist state that existed in Eurasia between 1922 and 1991....
in the early 1960s, Botvinnik had no choice but to investigate software move selection techniques; at the time only the most powerful computers could achieve much beyond a three-ply full-width search, and Botvinnik had no such machines. In 1965 Botvinnik was a consultant to the ITEP team in a US-Soviet computer chess match (see Kotok-McCarthy
Kotok-McCarthy
Kotok-McCarthy also known as was the first computer program to play chess convincingly. It is also remembered because it played in and lost the first chess match between two computer programs.-Development:...
).
One developmental milestone occurred when the team from Northwestern University
Northwestern University
Northwestern University is a private research university in Evanston and Chicago, Illinois, USA. Northwestern has eleven undergraduate, graduate, and professional schools offering 124 undergraduate degrees and 145 graduate and professional degrees....
, which was responsible for the Chess
Chess (Northwestern University)
Chess was a pioneering chess program from the 1970s, authored by Larry Atkin and David Slate at Northwestern University. Chess ran on Control Data Corporation's line of supercomputers. It dominated the first computer chess tournaments, such as the World Computer Chess Championship and ACM's North...
series of programs and won the first three ACM
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
Computer Chess Championships (1970–72), abandoned type B searching in 1973. The resulting program, Chess 4.0, won that year's championship and its successors went on to come in second in both the 1974 ACM Championship and that year's inaugural World Computer Chess Championship
World Computer Chess Championship
World Computer Chess Championship is an annual event where computer chess engines compete against each other. The event is organized by the International Computer Games Association...
, 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 just to search all of them.
In fact, Chess 4.0 set the paradigm that was and still is followed essentially by all modern Chess programs today. Chess 4.0 type programs won out for the simple reason that their programs played better chess. Such programs did not try to mimic human thought processes, but relied on full width alpha-beta
Alpha-beta pruning
Alpha-beta pruning is a search algorithm which seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games...
and negascout
Negascout
NegaScout or Principal Variation Search is a negamax algorithm that can be faster than alpha-beta pruning. Like alpha-beta pruning, NegaScout is a directional search algorithm for computing the minimax value of a node in a tree...
searches. Most such programs (including all modern programs today) also included a fairly limited selective part of the search based on quiescence searches, and usually extensions and pruning (particularly null move pruning from the 1990s onwards) which were triggered based on certain conditions in an attempt to weed out or reduce obviously bad moves (history moves) or to investigate interesting nodes (e.g. check extensions, passed pawn
Passed pawn
In chess, a passed pawn is a pawn with no opposing pawns to prevent it from advancing to the eighth rank, i.e. there are no opposing pawns in front of it on the same file nor on an adjacent file. A passed pawn is sometimes colloquially called a passer...
s on seventh rank, etc.). Extension and pruning triggers have to be used very carefully however. Over extend and the program wastes too much time looking at uninteresting positions. If too much is pruned, there is a risk cutting out interesting nodes. Chess programs differ in terms of how and what types of pruning and extension rules are included as well as in the evaluation function. Some programs are believed to be more selective than others (for example Deep Blue was known to be less selective than most commercial programs because they could afford to do more complete full width searches), but all have a base full width search as a foundation and all have some selective components (Q-search, pruning/extensions).
Though such additions meant that the program did not truly examine every node within its search depth (so it would not be truly brute force in that sense), the rare mistakes due to these selective searches was found to be worth the extra time it saved because it could search deeper. In that way Chess programs can get the best of both worlds.
Furthermore, technological advances by orders of magnitude in processing power have made the brute force approach far more incisive than was the case in the early years. The result is that a very solid, tactical AI player aided by some limited positional knowledge built in by the evaluation function and pruning/extension rules began to match the best players in the world. It turned out to produce excellent 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 1997 Deep Blue defeated World Champion Garry Kasparov
Garry Kasparov
Garry Kimovich Kasparov is a Russian chess grandmaster, a former World Chess Champion, writer, political activist, and one of the greatest chess players of all time....
, marking the first time a computer has defeated a reigning world chess champion in standard time control.
Computer chess programs consider chess moves as a game tree
Game tree
In game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position; the complete tree is the same tree as that...
. 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
Ply (game theory)
In two-player sequential games, a ply refers to one turn taken by one of the players. The word is used to clarify what is meant when one might otherwise say "turn"....
". This evaluation continues until a certain maximum search depth or the program determines that a final "leaf" position has been reached (e.g. checkmate).
A naive implementation of this approach can only search to a small depth in a practical amount of time, so various methods have been devised to greatly speed the search for good moves.
For more information, see:
- MinimaxMinimaxMinimax is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a worst case scenario. Alternatively, it can be thought of as maximizing the minimum gain...
algorithm - Alpha-beta pruningAlpha-beta pruningAlpha-beta pruning is a search algorithm which seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games...
- Killer heuristicKiller heuristicIn competitive two-player games, the killer heuristic is a technique for improving the efficiency of alpha-beta pruning, which in turn improves the efficiency of the minimax algorithm. This algorithm has an exponential search time to find the optimal next move, so general methods for speeding it...
- Iterative deepening depth-first searchIterative deepening depth-first searchIterative deepening depth-first search is a state space search strategy in which a depth-limited search is run repeatedly, increasing the depth limit with each iteration until it reaches d, the depth of the shallowest goal state...
- Null-move heuristicNull-move heuristicIn computer chess programs, the null-move heuristic is a heuristic technique used to enhance the speed of the alpha-beta pruning algorithm.- Rationale :...
- Late Move ReductionsLate Move ReductionsLate Move Reductions is a non-game specific enhancement to the alpha-beta algorithm and its variants which attempts to examine a game search tree more efficiently. It uses the assumption that good game-specific move ordering causes a program to search the most likely moves early...
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 functionEvaluation function
An evaluation function, also known as a heuristic evaluation function or static evaluation function, is a function used by game-playing programs to estimate the value or goodness of a position in the minimax and related algorithms...
", and these algorithms are often vastly different between different chess programs.
Evaluation functions typically evaluate positions in hundredths of a pawn, and consider material value along with other factors affecting the strength of each side. When counting up the material for each side, typical values for pieces are 1 point for a pawn
Pawn (chess)
The pawn is the most numerous and weakest piece in the game of chess, historically representing infantry, or more particularly armed peasants or pikemen. Each player begins the game with eight pawns, one on each square of the rank immediately in front of the other pieces...
, 3 points for a knight
Knight (chess)
The knight is a piece in the game of chess, representing a knight . It is normally represented by a horse's head and neck. Each player starts with two knights, which begin on the row closest to the player, one square from the corner...
or bishop
Bishop (chess)
A bishop is a piece in the board game of chess. Each player begins the game with two bishops. One starts between the king's knight and the king, the other between the queen's knight and the queen...
, 5 points for a rook
Rook (chess)
A rook is a piece in the strategy board game of chess. Formerly the piece was called the castle, tower, marquess, rector, and comes...
, and 9 points for a queen
Queen (chess)
The queen is the most powerful piece in the game of chess, able to move any number of squares vertically, horizontally, or diagonally. Each player starts the game with one queen, placed in the middle of the first rank next to the king. With the chessboard oriented correctly, the white queen starts...
. (See Chess piece relative value.) By convention, a positive evaluation favors White, and a negative evaluation favors Black.
The king
King (chess)
In chess, the king is the most important piece. The object of the game is to trap the opponent's king so that its escape is not possible . If a player's king is threatened with capture, it is said to be in check, and the player must remove the threat of capture on the next move. If this cannot be...
is sometimes given an arbitrary high value such as 200 points (Shannon's paper) or 1,000,000,000 points (1961 USSR program) to ensure that a checkmate outweighs all other factors . Evaluation function
Evaluation function
An evaluation function, also known as a heuristic evaluation function or static evaluation function, is a function used by game-playing programs to estimate the value or goodness of a position in the minimax and related algorithms...
s take many factors into account, such as pawn structure, the fact that a pair of 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).
Using endgame databases
Some computer chess operators have pointed out that endgame tablebaseEndgame tablebase
An endgame tablebase is a computerized database that contains precalculated exhaustive analysis of a chess endgame position. It is typically used by a computer chess engine during play, or by a human or computer that is retrospectively analysing a game that has already been played.The tablebase...
s have the potential to weaken performance strength in chess computers if incorrectly used. Because some positions are analyzed as forced wins for one side, the program will avoid the losing side of positions at all costs. However, many endgames are forced wins only with flawless play, where even a 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). This observation is only relevant when a computer program is in a situation where it has a choice between two losing moves, one of which is actually more difficult for the opponent, but leads to a tablebase position with a known value, and is hence of very minor importance.
The Nalimov tablebases do not consider the fifty-move rule, under which a game where fifty moves pass without a capture or pawn move can be claimed to be a draw by either player. This results in the tablebase returning results such as "Forced mate in sixty-six moves" in some positions which would actually be drawn because of the fifty-move rule. However, a correctly programmed engine does know about the fifty-move rule, and in any case if using an endgame tablebase will choose the move that leads to the quickest win (even if it would fall foul of the fifty-move rule with perfect play). If playing an opponent not using a tablebase, such a choice will give good chances of winning within fifty moves.
One 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
Gigabyte
The gigabyte is a multiple of the unit byte for digital information storage. The prefix giga means 109 in the International System of Units , therefore 1 gigabyte is...
of hard disk space for all five-piece endings. To cover all the six-piece endings requires approximately 1.2 terabyte
Terabyte
The terabyte is a multiple of the unit byte for digital information. The prefix tera means 1012 in the International System of Units , and therefore 1 terabyte is , or 1 trillion bytes, or 1000 gigabytes. 1 terabyte in binary prefixes is 0.9095 tebibytes, or 931.32 gibibytes...
. It is estimated that seven-piece tablebases will require more storage capacity than will be available in the foreseeable future.
It is surprising, but easily verified, that without an endgame tablebase even otherwise very strong chess engines may fail to find a winning plan even in endings with six or fewer pieces, when they need more moves than the calculation horizon to achieve a checkmate, a win of material or the advance of a pawn. Many endings require more moves than their calculation horizon.
Computers have been used to analyze some chess endgame positions completely. Such endgame databases are generated in advance using a form of retrograde analysis
Retrograde analysis
In chess, retrograde analysis is a computational method used to solve game positions for optimal play by working backward from known outcomes , such as the construction of endgame tablebases. In game theory at large, this method is called backward induction...
, 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
Unix
Unix is a multitasking, multi-user computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs, including Ken Thompson, Dennis Ritchie, Brian Kernighan, Douglas McIlroy, and Joe Ossanna...
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. In 1977 Thompson's Belle chess machine used the endgame tablebase for a king
King (chess)
In chess, the king is the most important piece. The object of the game is to trap the opponent's king so that its escape is not possible . If a player's king is threatened with capture, it is said to be in check, and the player must remove the threat of capture on the next move. If this cannot be...
and rook
Rook (chess)
A rook is a piece in the strategy board game of chess. Formerly the piece was called the castle, tower, marquess, rector, and comes...
against king and queen
Queen (chess)
The queen is the most powerful piece in the game of chess, able to move any number of squares vertically, horizontally, or diagonally. Each player starts the game with one queen, placed in the middle of the first rank next to the king. With the chessboard oriented correctly, the white queen starts...
and was able to draw that theoretically lost ending against several masters (see Philidor position#Queen versus rook). This was despite not following the usual strategy to delay defeat by keeping the defending king and rook close together for as long as possible. 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 evaluated its moves as best it could.
Most grandmasters
International Grandmaster
The title Grandmaster is awarded to strong chess players by the world chess organization FIDE. Apart from World Champion, Grandmaster is the highest title a chess player can attain....
declined to play against the computer in the queen versus rook endgame, but Walter Browne accepted the challenge. A queen versus rook position was set up in which the queen can win in thirty moves, with perfect play. Browne was allowed 2½ hours to play fifty moves, otherwise a draw would be claimed under the fifty-move rule. After forty-five moves, Browne agreed to a draw, being unable to force checkmate or win the rook within the next five moves. In the final position, Browne was still seventeen moves away from checkmate, but not quite that far away from winning the rook. Browne studied the endgame, and played the computer again a week later in a different position in which the queen can win in thirty moves. This time, he captured the rook on the fiftieth move, giving him a winning position , .
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 FIDE rules of chess were changed to extend the number of moves allowed in these endings. After a while, the rule reverted 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
Eugene Nalimov
Eugene Nalimov is a chess programmer and former Microsoft employee.Starting in 1998, he wrote a tablebase generator which included many different endgames. He received a ChessBase award at the ChessBase meeting in Maastricht in 2002 for his work.Nalimov has an M.Sc. from Novosibirsk State...
Endgame Tablebases which is the current standard supported by most chess programs such as Rybka
Rybka
Rybka is a computer chess engine designed by International Master Vasik Rajlich. , Rybka is one of the top-rated engines on chess engine rating lists and has won many computer chess tournaments...
, Shredder
Shredder (chess)
Shredder is a commercial chess program developed in Germany by Stefan Meyer-Kahlen in 1993. Shredder won the World Microcomputer Chess Championship in 1996 and 2000, the World Computer Chess Championship in 1999 and 2003, the World Computer Speed Chess Championship in 2002, 2003, 2004, 2005, and...
or Fritz
Fritz (chess)
Fritz is a German chess program developed by Frans Morsch and Mathias Feist and published by ChessBase. There is also a version called Deep Fritz that is designed for multiprocessing....
. All endgames with five or fewer pieces have been analyzed completely. Of endgames with six pieces all positions have been analyzed except for trivial positions with five pieces against a lone king. Some seven-piece endgames, have been analyzed by Marc Bourzutschky and Yakov Konoval. In all of these endgame databases it is assumed that castling is no longer possible.
Endgame databases are generated by storing in memory the values of positions which have been encountered so far, and using these results to lop off the ends of the search trees if they arise again. Although the number of possible games after a number of moves rises exponentially with the number of moves, the number of possible positions with a few pieces is exponential only in the number of pieces — and effectively limited however many end game moves are searched. The simple expediency of remembering the value of all previously reached positions means that the limiting factor in solving end games is simply the amount of memory available in the computer. While computer memory sizes are increasing exponentially, there is no reason why end games of increasing complexity should not continue to be solved.
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 or longest 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
Kasparov versus The World
Kasparov versus the World was a game of chess played in 1999 over the Internet. Conducting the white pieces, Garry Kasparov faced the rest of the world in consultation, with the World Team moves to be decided by plurality vote. Over 50,000 individuals from more than 75 countries participated in the...
. A seven piece Queen
Queen (chess)
The queen is the most powerful piece in the game of chess, able to move any number of squares vertically, horizontally, or diagonally. Each player starts the game with one queen, placed in the middle of the first rank next to the king. With the chessboard oriented correctly, the white queen starts...
and pawn
Pawn (chess)
The pawn is the most numerous and weakest piece in the game of chess, historically representing infantry, or more particularly armed peasants or pikemen. Each player begins the game with eight pawns, one on each square of the rank immediately in front of the other pieces...
endgame was reached with the World Team fighting to salvage a draw. Eugene Nalimov
Eugene Nalimov
Eugene Nalimov is a chess programmer and former Microsoft employee.Starting in 1998, he wrote a tablebase generator which included many different endgames. He received a ChessBase award at the ChessBase meeting in Maastricht in 2002 for his work.Nalimov has an M.Sc. from Novosibirsk State...
helped by generating the six piece ending tablebase where both sides had two Queens which was used heavily to aid analysis by both sides.
Other optimizations
Many other optimizations can be used to make chess-playing programs stronger. For example, transposition tableTransposition table
In computer chess and other computer games, transposition tables are used to speed up the search of the game tree. Transposition tables are primarily useful in perfect information games, meaning the entire state of the game is known to all players at all times....
s 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). Many chess engines use pondering to increase their strength.
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 only software. Another way to examine more chess positions is distribute the analysis of positions to many computers. The ChessBrain project was a chess program that distributed the search tree computation through the Internet. In 2004 the ChessBrain played chess using 2,070 computers.
Playing strength versus computer speed
It has been estimated that doubling the computer speed gains approximately fifty to seventy EloElo rating system
The Elo rating system is a method for calculating the relative skill levels of players in two-player games such as chess. It is named after its creator Arpad Elo, a Hungarian-born American physics professor....
points in playing strength .
Other chess software
There are several other forms of chess-related computer softwareComputer software
Computer software, or just software, is a collection of computer programs and related data that provide the instructions for telling a computer what to do and how to do it....
, 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. Shane's Chess Information DatabaseShane's Chess Information DatabaseShane's Chess Information Database is a popular free UNIX, Windows, Linux, and Mac database application for viewing and maintaining databases of chess games. Scid development has been resumed after it ceased in 2004....
(Scid) is a good example of a chess database. Scid http://scid.sourceforge.net/ may be used under Microsoft WindowsMicrosoft WindowsMicrosoft Windows is a series of operating systems produced by Microsoft.Microsoft introduced an operating environment named Windows on November 20, 1985 as an add-on to MS-DOS in response to the growing interest in graphical user interfaces . Microsoft Windows came to dominate the world's personal...
, UNIXUnixUnix is a multitasking, multi-user computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs, including Ken Thompson, Dennis Ritchie, Brian Kernighan, Douglas McIlroy, and Joe Ossanna...
, LinuxLinuxLinux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...
and Mac OS XMac OS XMac OS X is a series of Unix-based operating systems and graphical user interfaces developed, marketed, and sold by Apple Inc. Since 2002, has been included with all new Macintosh computer systems...
. There are also commercial databases, such as ChessbaseChessBaseChessBase GmbH is a German company that markets chess software, maintains a chess news site, and operates a server for online chess. Set up in 1998, it maintains and sells massive databases, containing most historic games, that permit analysis that had not been possible prior to computing...
and Chess Assistant for Windows and ExaChess http://www.exachess.com/ for Mac OS X. - Software for handling chess problemsSoftware for handling chess problemsSoftware for chess problems is a category of software intended for handling chess problems, usually distinct from chess playing and analyzing programs. Chess problems are based on the rules of chess, but problemists may have little use for ordinary chess playing programs. Many chess playing...
- Internet chess serverInternet chess serverAn Internet chess server is an external server that provides the facility to play, discuss, and view the board game of chess over the Internet...
and clients
Notable theorists
Well-known computer chess theorists include:- Alexander KronrodAlexander KronrodAleksandr Semenovich Kronrod was a Soviet mathematician and computer scientist, best known for the Gauss-Kronrod quadrature formula which he published in 1964. Earlier his computations informed theoretical physics...
- Georgy Adelson-VelskyGeorgy Adelson-VelskyGeorgy Maximovich Adelson-Velsky , is a Soviet mathematician and computer scientist. Along with E.M. Landis, he invented the AVL tree in 1962....
- Mikhail BotvinnikMikhail BotvinnikMikhail Moiseyevich Botvinnik, Ph.D. was a Soviet and Russian International Grandmaster and three-time World Chess Champion. Working as an electrical engineer and computer scientist at the same time, he was one of the very few famous chess players who achieved distinction in another career while...
(also three-time World Chess Champion) - D. F. Beal (Donald Francis Beal)
- David Levy
- Robert HyattRobert HyattDr. Robert Hyatt is an Associate Professor of Computer science at the University of Alabama at Birmingham, in the Department of Computer and Information Sciences . He is the author of the computer chess program Crafty and the co-author of Cray Blitz, a two-time winner of the World Computer Chess...
(author of open source chess program CraftyCraftyCrafty is a chess program written by UAB professor Dr. Robert Hyatt. It is directly derived from Cray Blitz, winner of the 1983 and 1986 World Computer Chess Championships....
) - Hans BerlinerHans BerlinerHans Jack Berliner , a Professor of , is a former World Correspondence Chess Champion, from 1965–68. He is a Grandmaster of Correspondence Chess, and an International Master for over-the-board chess. He directed the construction of the chess computer HiTech. Berliner is also a chess writer.-Life...
- Claude Elwood ShannonClaude Elwood ShannonClaude Elwood Shannon was an American mathematician, electronic engineer, and cryptographer known as "the father of information theory"....
Solving chess
The prospects of completely solvingSolved game
A solved game is a game whose outcome can be correctly predicted from any position when each side plays optimally. Games which have not been solved are said to be "unsolved"...
chess are generally considered to be rather remote. It is widely conjectured that there is no computationally inexpensive method to solve chess even in the very weak sense of determining with certainty the value of the initial position, and hence the idea of solving chess in the stronger sense of obtaining a practically usable description of a strategy for perfect play for either side seems unrealistic today. However, it has not been proven that no computationally cheap way of determining the best move in a chess position exists, nor even that a traditional alpha-beta-searcher running on present-day computing hardware could not solve the initial position in an acceptable amount of time. The difficulty in proving the latter lies in the fact that, while the number of board positions that could happen in the course of a chess game is huge (on the order of 1040), it is hard to rule out with mathematical certainty the possibility that the initial position allows either side to force a mate or a threefold repetition
Threefold repetition
In chess and some other abstract strategy games, the threefold repetition rule states that a player can claim a draw if the same position occurs three times, or will occur after their next move, with the same player to move. The repeated positions need not occur in succession...
after relatively few moves, in which case the search tree might encompass only a very small subset of the set of possible positions. It has been mathematically proven that generalized chess (chess played with an arbitrarily large number of pieces on an arbitrarily large chessboard) is EXPTIME-complete, meaning that determining the winning side in an arbitrary position of generalized chess provably takes exponential time in the worst case; however, this theoretical result gives no lower bound on the amount of work required to solve ordinary 8x8 chess.
Chronology of computer chess
The idea of creating a chess-playing machine dates back to the eighteenth century. Around 1769, the chess playing automatonAutomaton
An automaton is a self-operating machine. The word is sometimes used to describe a robot, more specifically an autonomous robot. An alternative spelling, now obsolete, is automation.-Etymology:...
called The Turk
The Turk
The Turk, also known as the Mechanical Turk or Automaton Chess Player , was a fake chess-playing machine constructed in the late 18th century. From 1770 until its destruction by fire in 1854, it was exhibited by various owners as an automaton, though it was exposed in the early 1820s as an...
became famous before being exposed as a hoax. Before the development of digital computing, serious trials based on automata such as El Ajedrecista
El Ajedrecista
El Ajedrecista was an automaton built in 1912 by Leonardo Torres y Quevedo. El Ajedrecista made a public debut during the Paris World Fair of 1914, creating great excitement at the time. It was first widely mentioned in Scientific American as "Torres and His Remarkable Automatic Devices" on...
of 1912, were too complex and limited to be useful for playing full games of chess. 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.
- 1769, Wolfgang von KempelenWolfgang von KempelenJohann Wolfgang Ritter von Kempelen de Pázmánd was a Hungarian author and inventor with Irish ancestors.-Life:...
builds the Automaton Chess-PlayerThe TurkThe Turk, also known as the Mechanical Turk or Automaton Chess Player , was a fake chess-playing machine constructed in the late 18th century. From 1770 until its destruction by fire in 1854, it was exhibited by various owners as an automaton, though it was exposed in the early 1820s as an...
, in what becomes one of the greatest hoaxes of its period. - 1868, Charles Hooper presented the AjeebAjeebAjeeb was a chess-playing "automaton", created by Charles Hooper , first presented at the Royal Polytechnical Institute in 1868...
automaton — which also had a human chess player hidden inside. - 1912, Leonardo Torres y QuevedoLeonardo Torres y QuevedoLeonardo Torres y Quevedo was a Spanish civil engineer and mathematician of the late nineteenth and early twentieth centuries.- Biography :Torres was born on 28 December 1852, on the Feast of the Holy Innocents, in Santa Cruz de Iguña, Molledo , Spain...
builds a machine that could play King and Rook versus King endgames. - 1948, Norbert WienerNorbert WienerNorbert Wiener was an American mathematician.A famous child prodigy, Wiener later became an early researcher in stochastic and noise processes, contributing work relevant to electronic engineering, electronic communication, and control systems.Wiener is regarded as the originator of cybernetics, a...
's book Cybernetics describes how a chess program could be developed using a depth-limited minimax search with an evaluation functionEvaluation functionAn evaluation function, also known as a heuristic evaluation function or static evaluation function, is a function used by game-playing programs to estimate the value or goodness of a position in the minimax and related algorithms...
. - 1950, Claude Shannon publishes "Programming a Computer for Playing Chess", one of the first papers on the problem of computer chess.
- 1951, Alan TuringAlan TuringAlan Mathison Turing, OBE, FRS , was an English mathematician, logician, cryptanalyst, and computer scientist. He was highly influential in the development of computer science, providing a formalisation of the concepts of "algorithm" and "computation" with the Turing machine, which played a...
develops on paper the first program capable of playing a full game of chess. - 1952, Dietrich Prinz develops a program that solves chess problems.
- 1956, Los Alamos chessLos Alamos chessLos Alamos chess is a chess variant played on a 6×6 board without bishops. This was the first chess-like game played by a computer program. This program was written in Los Alamos laboratory by Paul Stein and Mark Wells for the MANIAC I computer in 1956...
is the first program to play a chess-like game, developed by Paul Stein and Mark Wells for the MANIAC IMANIAC IThe MANIAC was an early computer built under the direction of Nicholas Metropolis at the Los Alamos Scientific Laboratory...
computer. - 1956, John McCarthyJohn McCarthy (computer scientist)John McCarthy was an American computer scientist and cognitive scientist. He coined the term "artificial intelligence" , invented the Lisp programming language and was highly influential in the early development of AI.McCarthy also influenced other areas of computing such as time sharing systems...
invents the alpha-beta search algorithm. - 1957, The first programs that can play a full game of chess are developed, one by Alex Bernstein and one by RussiaRussiaRussia or , officially known as both Russia and the Russian Federation , is a country in northern Eurasia. It is a federal semi-presidential republic, comprising 83 federal subjects...
n programmers using a BESMBESMBESM is the name of a series of Soviet mainframe computers built in 1950-1960s. The name is an acronym for "Bolshaya Elektronno-Schetnaya Mashina" , literally "Large Electronically Computing Machine". The series began as a successor to MESM...
. - 1958, NSS becomes the first chess program to use the alpha-beta search algorithm.
- 1962, The first program to play credibly, Kotok-McCarthyKotok-McCarthyKotok-McCarthy also known as was the first computer program to play chess convincingly. It is also remembered because it played in and lost the first chess match between two computer programs.-Development:...
, is published at MITMassachusetts Institute of TechnologyThe Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in... - 1963, Grandmaster David BronsteinDavid BronsteinDavid Ionovich Bronstein was a Soviet chess grandmaster, who narrowly missed becoming World Chess Champion in 1951. Bronstein was described by his peers as a creative genius and master of tactics...
defeats an M-20Minsk family of computersMinsk family of mainframe computers was developed and produced in the Byelorussian SSR from 1959 to 1975. Its further progress was stopped by a political decision of switching to IBM System/360 clone family known as ES EVM during the brief period of détente....
running an early chess program. - 1966-1967, The first chess match between computer programs is played. MoscowMoscowMoscow is the capital, the most populous city, and the most populous federal subject of Russia. The city is a major political, economic, cultural, scientific, religious, financial, educational, and transportation centre of Russia and the continent...
Institute for Theoretical and Experimental PhysicsInstitute for Theoretical and Experimental PhysicsThe Institute for Theoretical and Experimental Physics is located in Moscow, Russia as a MinAtom physical institute....
(ITEP) defeats Kotok-McCarthy at Stanford UniversityStanford UniversityThe Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is a private research university on an campus located near Palo Alto, California. It is situated in the northwestern Santa Clara Valley on the San Francisco Peninsula, approximately northwest of San...
by telegraph over nine months. - 1967, Mac Hack SixMacHack (chess)Mac Hack is a computer chess program written by Richard D. Greenblatt. Also known as Mac Hac and ', it was developed at the Massachusetts Institute of Technology...
, by Richard GreenblattRichard Greenblatt (programmer)Richard D. Greenblatt is an American computer programmer. Along with Bill Gosper, he may be considered to have founded the hacker community, and holds a place of distinction in the Lisp and the MIT AI Lab communities.-Childhood:...
et al. introduces transposition tableTransposition tableIn computer chess and other computer games, transposition tables are used to speed up the search of the game tree. Transposition tables are primarily useful in perfect information games, meaning the entire state of the game is known to all players at all times....
s and becomes the first program to defeat a person in tournament play chessville - 1968, David LevyDavid Levy (chess player)David Neil Laurence Levy , is a Scottish International Master of chess, a businessman noted for his involvement with computer chess and artificial intelligence, and the founder of the Computer Olympiads and the Mind Sports Olympiads. He has written more than 40 books on chess and computers.- Life...
makes a bet with AI researchers that no computer program would win a chess match against him within 10 years. - 1970, The first year of the ACM North American Computer Chess ChampionshipsNorth American Computer Chess ChampionshipThe North American Computer Chess Championship was a computer chess championship held from 1970 to 1994. It was organised by the Association for Computing Machinery and by Dr. Monty Newborn, Professor of Computer Science at McGill University. It was one of the first computer chess tournaments. The...
- 1974, KaissaKaissaKaissa was a chess program developed in the Soviet Union in the 1960s. It was named so after the chess goddess Caissa. Kaissa became the first world computer chess champion in 1974 in Stockholm.- History :...
wins first World Computer Chess ChampionshipWorld Computer Chess ChampionshipWorld Computer Chess Championship is an annual event where computer chess engines compete against each other. The event is organized by the International Computer Games Association... - 1977, The first microcomputer chess playing machine, CHESS CHALLENGER, was created
- 1977, The International Computer Chess Association is established.
- 1977, Chess 4.6Chess (Northwestern University)Chess was a pioneering chess program from the 1970s, authored by Larry Atkin and David Slate at Northwestern University. Chess ran on Control Data Corporation's line of supercomputers. It dominated the first computer chess tournaments, such as the World Computer Chess Championship and ACM's North...
becomes the first chess computer to be successful at a major chess tournament. - 1978, David LevyDavid Levy (chess player)David Neil Laurence Levy , is a Scottish International Master of chess, a businessman noted for his involvement with computer chess and artificial intelligence, and the founder of the Computer Olympiads and the Mind Sports Olympiads. He has written more than 40 books on chess and computers.- Life...
wins the bet made 10 years earlier, defeating the Chess 4.7 in a six-game match by a score of 4.5-1.5. - 1980, The first year of the World Microcomputer Chess Championship
- 1980, The Fredkin Prize is established.
- 1981 Cray BlitzCray BlitzCray Blitz was a computer chess program written by Robert Hyatt, Harry Nelson, and Albert Gower to run on the Cray supercomputer. It was derived from "Blitz" a program that Hyatt started to work on as an undergraduate. "Blitz" played its first move in the fall of 1968, and was developed...
wins the Mississippi State Championship with a perfect 5-0 score and a performance rating of 2258. In round 4 it defeats Joe Sentef (2262) to become the first computer to beat a master in tournament play and the first computer to gain a master rating. - 1982, Ken Thompson's hardware chess player BelleBelle (chess machine)Belle was the name of a chess computer and its associated software, developed by Joe Condon and Ken Thompson at Bell Labs in the 1970s and 1980s. Belle was the first computer built for the sole purpose of chess playing. The strongest computer chess system of its time, Belle achieved a USCF rating...
earns a US master title. - 1988, HiTechHiTechHiTech was a chess machine built at Carnegie Mellon University under the direction of World Correspondence Chess Champion Dr. Hans J. Berliner, by Berliner, Carl Ebeling, Murray Campbell, and Gordon Goetsch....
is developed by Hans BerlinerHans BerlinerHans Jack Berliner , a Professor of , is a former World Correspondence Chess Champion, from 1965–68. He is a Grandmaster of Correspondence Chess, and an International Master for over-the-board chess. He directed the construction of the chess computer HiTech. Berliner is also a chess writer.-Life...
and Carl EbelingCarl EbelingCarl Ebeling is an United States computer scientist, professor. His recent interests include coarse-grained reconfigurable architectures of integrated circuits.-Education and career:...
wins a match against grandmasterInternational GrandmasterThe title Grandmaster is awarded to strong chess players by the world chess organization FIDE. Apart from World Champion, Grandmaster is the highest title a chess player can attain....
Arnold DenkerArnold DenkerArnold Sheldon Denker was an American chess player, Grandmaster, and chess author. He was U.S. Chess Champion in 1945 and 1946....
3.5 - 0.5. - 1988, Deep ThoughtDeep Thought (chess computer)Deep Thought was a computer designed to play chess. Deep Thought was initially developed at Carnegie Mellon University and later at IBM. It was second in the line of chess computers developed by Feng-hsiung Hsu, starting with ChipTest and culminating in Deep Blue...
shares first place with Tony MilesTony MilesAnthony John Miles was an English chess Grandmaster.- Early achievements in chess :Miles was born in Edgbaston, a suburb of Birmingham...
in the Software Toolworks Championship, ahead of a former world champion Mikhail TalMikhail TalMikhail Tal was a Soviet–Latvian chess player, a Grandmaster, and the eighth World Chess Champion.Widely regarded as a creative genius, and the best attacking player of all time, he played a daring, combinatorial style. His play was known above all for improvisation and unpredictability....
and several grandmasters including Samuel ReshevskySamuel ReshevskySamuel "Sammy" Herman Reshevsky was a famous chess prodigy and later a leading American chess Grandmaster...
, Walter Browne and Mikhail GurevichMikhail Gurevich (chess player)Mikhail Naumovich Gurevich is a Soviet chess player. He lived in Belgium from 1991 to 2005 and since then resides in Turkey....
. It also defeats grandmaster Bent LarsenBent LarsenJørgen Bent Larsen was a Danish chess Grandmaster and author. Larsen was known for his imaginative and unorthodox style of play and he was the first western player to pose a serious challenge to the Soviet Union's dominance of chess...
, making it the first computer to beat a GM in a tournament. Its ratingElo rating systemThe Elo rating system is a method for calculating the relative skill levels of players in two-player games such as chess. It is named after its creator Arpad Elo, a Hungarian-born American physics professor....
for performance in this tournament of 2745 (USCF scale) was the highest obtained by a computer player. - 1989, Deep Thought loses two exhibition games to Garry KasparovGarry KasparovGarry Kimovich Kasparov is a Russian chess grandmaster, a former World Chess Champion, writer, political activist, and one of the greatest chess players of all time....
, the reigning world champion. - 1992, first time a microcomputerMicrocomputerA microcomputer is a computer with a microprocessor as its central processing unit. They are physically small compared to mainframe and minicomputers...
, the ChessMachineChessmachineThe ChessMachine was a chess computer sold between 1991 and 1995 by TASC . It was unique at the time for incorporating both an ARM2 coprocessor for the chess engine on an ISA card which plugged into a IBM PC and a software interface running on the PC to display a chess board and control the engine...
Gideon 3.1REBEL (chess)REBEL was a world champion chess program developed by Ed Schröder. Development of REBEL started in 1980 on a TRS-80, and it was ported many times to dedicated hardware and the fastest microprocessors of the day:...
by Ed Schröder from The Netherlands, wins the 7th World Computer Chess ChampionshipWorld Computer Chess ChampionshipWorld Computer Chess Championship is an annual event where computer chess engines compete against each other. The event is organized by the International Computer Games Association...
in front of mainframesMainframe computerMainframes are powerful computers used primarily by corporate and governmental organizations for critical applications, bulk data processing such as census, industry and consumer statistics, enterprise resource planning, and financial transaction processing.The term originally referred to the...
, supercomputerSupercomputerA supercomputer is a computer at the frontline of current processing capacity, particularly speed of calculation.Supercomputers are used for highly calculation-intensive tasks such as problems including quantum physics, weather forecasting, climate research, molecular modeling A supercomputer is a...
s and special hardware. - 1996, Deep Blue loses a six-game match against Garry KasparovGarry KasparovGarry Kimovich Kasparov is a Russian chess grandmaster, a former World Chess Champion, writer, political activist, and one of the greatest chess players of all time....
. - 1997, Deep Blue wins a six-game match against Garry KasparovGarry KasparovGarry Kimovich Kasparov is a Russian chess grandmaster, a former World Chess Champion, writer, political activist, and one of the greatest chess players of all time....
. - 2002, Vladimir KramnikVladimir KramnikVladimir Borisovich Kramnik is a Russian chess grandmaster. He was the Classical World Chess Champion from 2000 to 2006, and the undisputed World Chess Champion from 2006 to 2007...
draws an eight-game match against Deep Fritz. - 2003, Kasparov draws a six-game match against Deep JuniorDeep JuniorJunior is a computer chess program authored by the Israeli programmers Amir Ban and Shay Bushinsky. Grandmaster Boris Alterman assisted, in particular with the opening book...
. - 2003, Kasparov draws a four-game match against X3D FritzX3D FritzX3D Fritz was a version of the Fritz chess program, which in November 2003 played a four-game Human-computer chess match against world number one Grandmaster Garry Kasparov...
. - 2004, a team of computers (HydraHydra (chess)Hydra was a chess machine, designed by a team with Dr. Christian "Chrilly" Donninger, Dr. Ulf Lorenz, GM Christopher Lutz and Muhammad Nasir Ali. Since 2006 the development team consised only of Donninger and Lutz. Hydra was under the patronage of the PAL Group and Sheikh Tahnoon Bin Zayed Al...
, Deep JuniorDeep JuniorJunior is a computer chess program authored by the Israeli programmers Amir Ban and Shay Bushinsky. Grandmaster Boris Alterman assisted, in particular with the opening book...
and FritzFritz (chess)Fritz is a German chess program developed by Frans Morsch and Mathias Feist and published by ChessBase. There is also a version called Deep Fritz that is designed for multiprocessing....
), wins 8.5-3.5 against a rather strong human team formed by Veselin TopalovVeselin TopalovVeselin Aleksandrov Topalov is a Bulgarian chess grandmaster. He currently has the sixth highest rating in the world, and was the challenger facing world champion Viswanathan Anand in the World Chess Championship 2010, losing the match 6½–5½....
, Ruslan PonomariovRuslan PonomariovRuslan Olegovich Ponomariov is a Ukrainian chess player and former FIDE World Champion.-Early career:Ponomariov was born in Horlivka in Ukraine. In 1994 he placed third in the World Under-12 Championship at the age of ten. In 1996 he won the European Under-18 Championship at the age of just...
and Sergey KarjakinSergey KarjakinSergey Alexandrovich Karjakin is a Russian chess grandmaster. He was a chess prodigy and holds the record for both the youngest International Master, eleven years and eleven months, and grandmaster in history, at the age of twelve years and seven months...
, who had an average ELOElo rating systemThe Elo rating system is a method for calculating the relative skill levels of players in two-player games such as chess. It is named after its creator Arpad Elo, a Hungarian-born American physics professor....
rating of 2681. - 2005, HydraHydra (chess)Hydra was a chess machine, designed by a team with Dr. Christian "Chrilly" Donninger, Dr. Ulf Lorenz, GM Christopher Lutz and Muhammad Nasir Ali. Since 2006 the development team consised only of Donninger and Lutz. Hydra was under the patronage of the PAL Group and Sheikh Tahnoon Bin Zayed Al...
defeats Michael Adams 5.5-0.5. - 2005, Rybka wins the IPCCC tournament and very quickly afterwards becomes the strongest engine
- 2006, the undisputed world champion, Vladimir KramnikVladimir KramnikVladimir Borisovich Kramnik is a Russian chess grandmaster. He was the Classical World Chess Champion from 2000 to 2006, and the undisputed World Chess Champion from 2006 to 2007...
, is defeated 4-2 by Deep Fritz. - 2009, Pocket FritzPocket FritzPocket Fritz, which is currently at version 4, is a chess playing program for Pocket PC personal digital assistants . Pocket Fritz 4 uses HIARCS as the chess engine. Pocket Fritz 2 used a port of the Shredder chess engine....
4 wins Copa Mercosur 9.5/10. - 2010, Before the World chess championship, Topalov prepares by sparring against the supercomputer Blue Gene with 8,192 processors capable of 500 trillion floating point operations per second.
- 2011, Rybka is stripped of its WCCC titles when evidence of plagiarism comes to light.
See also
- Advanced ChessAdvanced ChessAdvanced Chess is a relatively new form of chess, wherein each human player uses a computer chess program to help him explore the possible results of candidate moves...
- Chess Engines Grand Tournament
- Chess engine
- Computer GoComputer GoComputer Go is the field of artificial intelligence dedicated to creating a computer program that plays Go, a traditional board game.-Performance:...
- Computer shogiComputer shogiComputer shogi is a field of artificial intelligence concerned with the creation of computer programs which can play shogi. The research and development of shogi software has been carried out mainly by freelance programmers, university research groups and private companies.-Game complexity:Shogi...
- Computer OthelloComputer Othellois a reversi-based video arcade game developed and published by Nintendo. It is one of their earliest video arcade games along with Block Fever and after they did release a dedicated console called Color TV Game 6 and a variety of electromechanical arcade games earlier in the 1970s. It was...
- Computer OlympiadComputer OlympiadThe Computer Olympiads are a multi-games event taking place every year in which computer programs compete against each other. The majority of the games are board games but other games such as Bridge take place as well...
- Internet chess serverInternet chess serverAn Internet chess server is an external server that provides the facility to play, discuss, and view the board game of chess over the Internet...
- List of chess software
- Shannon numberShannon numberThe Shannon number, named after Claude Shannon, is an estimated lower bound on the game-tree complexity of chess. Shannon calculated it as an aside in his 1950 paper "Programming a Computer for Playing Chess"...
- Swedish Chess Computer AssociationSwedish Chess Computer AssociationThe Swedish Chess Computer Association is an organization that tests computer chess software by playing chess programs against one another and producing a rating list. On September 26, 2008, the list was released with Deep Rybka 3 leading with an estimated Elo rating of 3238. Rybka's listing in...
- World Computer Chess ChampionshipWorld Computer Chess ChampionshipWorld Computer Chess Championship is an annual event where computer chess engines compete against each other. The event is organized by the International Computer Games Association...
Further reading
- New Architectures in Computer Chess - Thesis on How to Build A Chess Engine
- Lasar, Matthew (2011). Brute force or intelligence? The slow rise of computer chess". Ars TechnicaArs TechnicaArs Technica is a technology news and information website created by Ken Fisher and Jon Stokes in 1998. It publishes news, reviews and guides on issues such as computer hardware and software, science, technology policy, and video games. Ars Technica is known for its features, long articles that go...
. - Newborn, Monty (1996). Outsearching Kasparov, American Mathematical Society's Proceeding of Symposia in Applied Mathematics: Mathematical Aspects of Artificial Intelligence, v. 55, pp 175–205, 1998. Based on paper presented at the 1996 Winter Meeting of the AMS, Orlando, Florida, Jan 9–11, 1996.
- Newborn, Monty (2000). Deep Blue’s contribution to AI, Annals of Mathematics and Artificial Intelligence, v. 28, pp. 27–30, 2000.
- Newborn, Monty (2006). Theo and Octopus at the 2006 World Championship for Automated Reasoning Programs, Seattle, Washington, August 18, 2006
External links
- Mastering the Game: A History of Computer Chess at the Computer History MuseumComputer History MuseumThe Computer History Museum is a museum established in 1996 in Mountain View, California, USA. The Museum is dedicated to preserving and presenting the stories and artifacts of the information age, and exploring the computing revolution and its impact on our lives.-History:The museum's origins...
- ACM Computer Chess by Bill Wall
- Computer Chess Information and Resources - Blog following the creation of a computer chess engine
- Defending Humanity's Honor, an article by Tim KrabbéTim KrabbéTim Krabbé is a Dutch journalist and novelist.Krabbé was born in Amsterdam. His writing has appeared in most major periodicals in the Netherlands. He is known to Dutch readers for his novel De Renner , first published in 1978...
about "anti-computer style" chess - A guide to Endgame Tablebases
- GameDev.net -- Chess Programming by François-Dominic Laramée Part 1 2 3 4 5 6
- Colin Frayn's Computer Chess Theory Page
- "Play chess with God" - Play chess against Ken Thompson's endgame database
- Media
- The History of Computer Chess: An AI Perspective - a full lecture featuring Murray Campbell (IBM Deep Blue Project), Edward Feigenbaum, David Levy, John McCarthy, and Monty Newborn. at Computer History Museum