Old page wikitext, before the edit (old_wikitext) | '{{Short description|Computer hardware and software capable of playing chess}}
{{about||the 2013 film|Computer Chess (film)|chess played over the Internet|Online chess}}
[[Image:RS Chess Computer.JPG|thumb|1990s pressure-sensory chess computer with LCD screen]]
{{Chess programming series}}
'''Computer chess''' includes both hardware (dedicated computers) and [[software]] capable of playing [[chess]]. Computer chess provides opportunities for players to practice even in the absence of human opponents, and also provides opportunities for analysis, entertainment and training. Computer chess applications that play at the level of a [[Chess title|chess grandmaster]] or higher are available on hardware from [[supercomputer]]s to [[Smartphone|smart phones]]. Standalone chess-playing machines are also available. [[Stockfish (chess)|Stockfish]], [[Leela Chess Zero]], [[GNU Chess]], [[Fruit (software)|Fruit]], and other free open source applications are available for various platforms.
Computer chess applications, whether implemented in hardware or software, utilize different strategies than humans to choose their moves: they use [[Heuristic (computer science)|heuristic methods]] to build, search and evaluate [[Tree (data structure)|trees]] representing sequences of moves from the current position and attempt to execute the best such sequence during play. Such trees are typically quite large, thousands to millions of nodes. The computational speed of modern computers, capable of processing tens of thousands to hundreds of thousands of nodes or more per second, along with extension and reduction heuristics that narrow the tree to mostly relevant nodes, make such an approach effective.
The first chess machines capable of playing chess or reduced chess-like games were software programs running on digital computers early in the [[vacuum-tube computer]] age (1950s). The early programs played so poorly that even a beginner could defeat them. Within 40 years, in 1997, [[chess engine]]s running on super-computers or specialized hardware were capable of [[Deep Blue versus Garry Kasparov|defeating even the best human players]]. By 2006, [[Human–computer chess matches|programs running on desktop PCs]] had attained the same capability. In 2006, [[Monty Newborn]], Professor of Computer Science at [[McGill University]], declared: "the science has been done". Nevertheless, [[solving chess]] is not currently possible for modern computers due to the [[Game complexity|game's extremely large number of possible variations]].<ref>{{cite web |last1=Sreedhar |first1=Suhas |title=Checkers, Solved! |url=https://spectrum.ieee.org/computing/software/checkers-solved |website=IEEE Spectrum |date=2 July 2007 |publisher=Institute of Electrical and Electronics Engineers}}</ref>
Computer chess was once considered the "[[Drosophila]] of AI", the edge of [[knowledge engineering]]. The field is now considered a scientifically completed paradigm, and playing chess is a mundane computing activity.<ref>{{Cite journal|url=https://pubmed.ncbi.nlm.nih.gov/22530382/|pmid = 22530382|year = 2012|last1 = Ensmenger|first1 = N.|title = Is chess the drosophila of artificial intelligence? A social history of an algorithm|journal = Social Studies of Science|volume = 42|issue = 1|pages = 5–30|doi = 10.1177/0306312711424596|s2cid = 968033}}</ref>
== Availability and playing strength ==
[[File:Frans Morsch name on the ICs.jpg|thumb|Computer chess IC bearing the name of developer Frans Morsch (see [[Mephisto (chess computer)|Mephisto]])]]
Chess machines/programs are available in several different forms: stand-alone chess machines (usually a microprocessor running a software chess program, but sometimes as a specialized hardware machine), software programs running on standard PCs, web sites, and apps for mobile devices. Programs run on everything from super-computers to smartphones. Hardware requirements for programs are minimal; the apps are no larger than a few megabytes on disk, use a few megabytes of memory (but can use much more, if it is available), and any processor 300Mhz or faster is sufficient. Performance will vary modestly with processor speed, but sufficient memory to hold a large [[transposition table]] (up to several gigabytes or more) is more important to playing strength than processor speed.
Most available commercial chess programs and machines can play at super-grandmaster strength (Elo 2700 or more), and take advantage of multi-core and hyperthreaded computer CPU architectures. Top programs such as [[Stockfish (chess)|Stockfish]] have surpassed even world champion caliber players. Most chess programs comprise a chess engine connected to a GUI, such as [[Winboard]] or [[Chessbase]]. Playing strength, time controls, and other performance-related settings are adjustable from the GUI. Most GUIs also allow the player to set up and to edit positions, to reverse moves, to offer and to accept draws (and resign), to request and to receive move recommendations, and to show the engine's analysis as the game progresses.
There are thousands of [[chess engine]]s such as [[Sargon (chess)|Sargon]], [[IPPOLIT]], [[Stockfish (chess)|Stockfish]], [[Crafty]], [[Fruit (chess engine)|Fruit]], [[Leela Chess Zero]] and [[GNU Chess]] which can be downloaded (or source code otherwise obtained) from the [[Internet]] free of charge.
== Types and features of chess software ==
Perhaps the most common type of chess software are programs that simply play chess. A human player makes a move on the board, the AI calculates and plays a subsequent move, and the human and AI alternate turns until the game ends. The [[chess engine]], which calculates the moves, and the [[graphical user interface]] (GUI) are sometimes separate programs. Different engines can be connected to the GUI, permitting play against different styles of opponent. Engines often have a simple text [[command-line interface]], while GUIs may offer a variety of piece sets, board styles, or even 3D or animated pieces. Because recent engines are so capable, engines or GUIs may offer some way of handicapping the engine's ability, to improve the odds for a win by the human player. [[Universal Chess Interface]] (UCI) engines such [[Fritz (chess)|Fritz]] or [[Rybka]] may have a built in mechanism for reducing the [[Elo rating]] of the engine (via UCI's uci_limitstrength and uci_elo parameters). Some versions of [[Fritz (chess)|Fritz]] have a Handicap and Fun mode for limiting the current engine or changing the percentage of mistakes it makes or changing its style. [[Fritz (chess)|Fritz]] also has a Friend Mode where during the game it tries to match the level of the player.
[[File:Chess screenshot.png|thumb|Screenshot of [[List of macOS components#Chess|Chess]], a component of [[macOS]]]]
Chess databases allow users to search through a large library of historical games, analyze them, check statistics, and formulate an opening repertoire. [[Chessbase]] (for PC) is a common program for these purposes amongst professional players, but there are alternatives such as [[Shane's Chess Information Database]] (Scid) <ref>[http://scid.sourceforge.net/ http://scid.sourceforge.net] SCID.</ref> for Windows, Mac or Linux, [[Chess Assistant]]<ref>{{cite web |url=http://www.convekta.com/about.asp |title= Chess Assistant Chess Website:: About Us|website=www.convekta.com |archive-url=https://web.archive.org/web/20080820180940/http://www.convekta.com/about.asp |archive-date=August 20, 2008}}</ref> for PC,<ref>[http://www.exachess.com/ http://www.exachess.com] ExaChess for Mac</ref> Gerhard Kalab's Chess PGN Master for Android<ref>{{cite web|url=http://kalab.com/pgnviewer/|title=Chess PGN Master}}</ref> or Giordano Vicoli's Chess-Studio for iOS.<ref>https://www.facebook.com/chessstudioapp/ {{User-generated source|certain=yes|date=March 2022}}</ref>
Programs such as [[Playchess]] allow players to play against one another over the internet.
Chess training programs teach chess. [[Chessmaster]] had playthrough tutorials by IM [[Josh Waitzkin]] and GM [[Larry Christiansen]]. [[Stefan Meyer-Kahlen]] offers [[Shredder (chess)|Shredder]] Chess Tutor based on the Step coursebooks of Rob Brunia and Cor Van Wijgerden. Former [[World Chess Championship|World Champion]] [[Magnus Carlsen]]'s [[Play Magnus Group|Play Magnus company]] released a [[Play Magnus (mobile app)|Magnus Trainer app]] for Android and iOS. [[Chessbase]] has [[Fritz and Chesster]] for children. Convekta provides a large number of training apps such as CT-ART and its Chess King line based on tutorials by GM Alexander Kalinin and Maxim Blokh.
There is also [[software for handling chess problems]].
== Computers versus humans ==
{{Main|Human–computer chess matches}}
After discovering refutation screening—the application of [[alpha–beta pruning]] to optimizing move evaluation—in 1957, a team at [[Carnegie Mellon University]] predicted that a computer would defeat the world human champion by 1967.<ref>{{cite journal|last1=Simon|first1=H.A.|last2=Newell|first2=A.|title=Heuristic problem solving: The next advance in operations research|journal=Operations Research|date=1958|volume=6|issue=1|page=7|doi=10.1287/opre.6.1.1|url=https://home.mis.u-picardie.fr/~furst/docs/Newell_Simon_Heuristic_Problem_Solving_1958.pdf|access-date=10 February 2018}}</ref> It did not anticipate the difficulty of determining the right order to evaluate moves. Researchers worked to improve programs' ability to identify [[killer heuristic]]s, unusually high-scoring moves to reexamine when evaluating other branches, but into the 1970s most top chess players believed that computers would not soon be able to play at a [[Senior Master (chess)|Master]] level.{{r|hapgood19821223_30}} In 1968, [[International Master]] [[Computer chess bet|David Levy made a famous bet]] that no chess computer would be able to beat him within ten years,{{r|douglas197812}} and in 1976 [[Senior Master (chess)|Senior Master]] and professor of psychology [[Eliot Hearst]] of [[Indiana University]] wrote that "the only way a current computer program could ever win a single game against a master player would be for the master, perhaps in a drunken stupor while playing 50 games simultaneously, to commit some once-in-a-year blunder".{{r|hapgood19821223_30}}
In the late 1970s chess programs suddenly began defeating highly skilled human players.{{r|hapgood19821223_30}} The year of Hearst's statement, [[Northwestern University]]'s [[Chess 4.5]] at the [[Paul Masson]] American Chess Championship's [[Chess title#Expert|Class B]] level became the first to win a human tournament. Levy won his bet in 1978 by beating [[Chess 4.7]], but it achieved the first computer victory against a Master-class player at the tournament level by winning one of the six games.<ref name="douglas197812">{{cite news | url=https://archive.org/stream/byte-magazine-1978-12/1978_12_BYTE_03-12_Life#page/n85/mode/2up | title=Chess 4.7 versus David Levy | work=BYTE | date=December 1978 | access-date=17 October 2013 | author=Douglas, J R | page=84}}</ref> In 1980, [[Belle (chess machine)|Belle]] began often defeating Masters. By 1982 two programs played at Master level and three were slightly weaker.{{r|hapgood19821223_30}}
The sudden improvement without a theoretical breakthrough was unexpected, as many did not expect that Belle's ability to examine 100,000 positions a second—about eight plies—would be sufficient. The Spracklens, creators of the successful microcomputer program ''[[Sargon (chess)|Sargon]]'', estimated that 90% of the improvement came from faster evaluation speed and only 10% from improved evaluations. ''[[New Scientist]]'' stated in 1982 that computers "play ''terrible'' chess ... clumsy, inefficient, diffuse, and just plain ugly", but humans lost to them by making "horrible blunders, astonishing lapses, incomprehensible oversights, gross miscalculations, and the like" much more often than they realized; "in short, computers win primarily through their ability to find and exploit miscalculations in human initiatives".<ref name="hapgood19821223_30"/>
By 1982, microcomputer chess programs could evaluate up to 1,500 moves a second and were as strong as mainframe chess programs of five years earlier, able to defeat a majority of amateur players. While only able to look ahead one or two plies more than at their debut in the mid-1970s, doing so improved their play more than experts expected; seemingly minor improvements "appear to have allowed the crossing of a psychological threshold, after which a rich harvest of human error becomes accessible", ''New Scientist'' wrote.{{r|hapgood19821223_30}} While reviewing ''SPOC'' in 1984, ''[[BYTE]]'' wrote that "Computers—mainframes, minis, and micros—tend to play ugly, inelegant chess", but noted [[Robert Byrne (chess player)|Robert Byrne]]'s statement that "tactically they are freer from error than the average human player". The magazine described ''SPOC'' as a "state-of-the-art chess program" for the IBM PC with a "surprisingly high" level of play, and estimated its USCF rating as 1700 (Class B).<ref name="byte198403">{{cite news | url=https://archive.org/stream/byte-magazine-1984-03-rescan/1984_03_BYTE_09-03_Simulation#page/n289/mode/2up | title=SPOC / The Chess Master | work=BYTE | date=March 1984 | access-date=8 September 2015 |author1=Flock, Emil |author2=Silverman, Jonathan | pages=288–294}}</ref>
At the 1982 [[North American Computer Chess Championship]], [[Monroe Newborn]] predicted that a chess program could become world champion within five years; tournament director and International Master [[Michael Valvo]] predicted ten years; the Spracklens predicted 15; [[Ken Thompson]] predicted more than 20; and others predicted that it would never happen. The most widely held opinion, however, stated that it would occur around the year 2000.<ref name="stinson198201">{{cite news | url=http://www.cgwmuseum.org/galleries/index.php?year=1982&pub=6&id=3 | title=Chess Championship: Machines Play, People Watch | work=Softline | date=Jan 1982 | access-date=13 July 2014 | author=Stinson, Craig | page=6}}</ref> In 1989, Levy was defeated by [[Deep Thought (chess computer)|Deep Thought]] in an exhibition match. Deep Thought, however, was still considerably below World Championship level, as the reigning world champion, [[Garry Kasparov]], demonstrated in two strong wins in 1989. It was not until a 1996 match with [[International Business Machines|IBM's]] [[IBM Deep Blue|Deep Blue]] that Kasparov lost his first game to a computer at tournament time controls in [[Deep Blue versus Kasparov, 1996, Game 1|Deep Blue versus 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 (chess)|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]]''.
{{Chess diagram
|tright
|[[Deep Blue versus Kasparov, 1996, Game 1|Deep Blue vs. Kasparov, 1996, game 1]]
| | | | | | | |
| | | | | | | |rl
| | | | | |qd| |kd
| | | |ql| | |nl|
| | | |pd| | | |
|pl|pl| | | |pd|pl|pl
| | | | | |nd| |kl
| | | | |rd| | |
|Final position
}}
With increasing processing power and improved evaluation functions, chess programs running on commercially available workstations began to rival top-flight players. In 1998, [[REBEL (chess)|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 chess|blitz]] games (five minutes plus five seconds [[Time control#Chess|Fischer delay]] 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½.<ref>{{cite web|url=http://www.rebel.nl/anand.htm |title=Rebel vs Anand |publisher=Rebel.nl |access-date=2010-04-03}}</ref> 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 (chess)|Junior]] and [[Fritz (chess)|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 [[Chess middlegame|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.{{Citation needed|date=January 2008}}
In January 2003, Kasparov played [[Junior (chess)|Junior]], another chess computer program, in New York City. The match ended 3–3.
In November 2003, Kasparov played [[X3D Fritz]]. The match ended 2–2.
In 2005, [[Hydra (chess)|Hydra]], a dedicated chess computer with custom hardware and sixty-four processors and also winner of the 14th [[International Paderborn Computer Chess Championship|IPCCC]] in 2005, defeated seventh-ranked [[Michael Adams (chess player)|Michael Adams]] 5½–½ in a six-game match (though Adams' preparation was far less thorough than Kramnik's for the 2002 series).<ref>{{cite web|url=http://www.chessbase.com/newsdetail.asp?newsid=2476 |title=Chess News – Adams vs Hydra: Man 0.5 – Machine 5.5 |date=28 June 2005 |publisher=ChessBase.com |access-date=2010-04-03}}</ref>
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 ([[Blunder of the century|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.<ref>[https://www.nytimes.com/2006/12/05/crosswords/chess/05cnd-chess.html Once Again, Machine Beats Human Champion at Chess] New York Times, December 5, 2006</ref> According to Newborn, for example, "the science is done".<ref>{{cite news| url=https://www.nytimes.com/2006/12/05/crosswords/chess/05cnd-chess.html | work=The New York Times | title=Once Again, Machine Beats Human Champion at Chess | date=5 December 2006 | access-date=30 April 2010}}</ref>
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.<ref>[http://www.ddj.com/hpc-high-performance-computing/184405171 Computer Chess: The Drosophila of AI] October 30, 2002</ref> 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, are not directly compared.<ref>[http://www.aaai.org/ojs/index.php/aimagazine/article/viewFile/753/671 Deep Thought wins Fredkin Intermediate Prize], [[Hans Berliner]]</ref> In 2016, the [[Swedish Chess Computer Association]] rated computer program [[Komodo (chess)|Komodo]] at 3361.
[[Chess engine]]s continue to improve. In 2009, chess engines running on slower hardware have reached the [[Grandmaster (chess)|grandmaster]] level. A [[mobile phone]] won a [[category (chess tournament)|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.<ref name=PF4GM>{{cite web|url=https://theweekinchess.com/html/twic771.html#13 |title=Pocket Fritz 4 wins Copa Mercosur |publisher=Chess.co.uk |access-date=2010-04-03 |url-status=dead |archive-url=https://web.archive.org/web/20110930232108/https://theweekinchess.com/html/twic771.html#13 |archive-date=2011-09-30 }}</ref> Pocket Fritz 4 searches fewer than 20,000 positions per second.<ref name=PF420K>Stanislav Tsukrov, Pocket Fritz author. [http://hiarcs.net/forums/viewtopic.php?t=2537&start=67 Pocket Fritz 4 searches less than 20,000 positions per second.]</ref> 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. This has been proven in numerous occasions, such as at Freestyle Chess events.
Players today are inclined to treat chess engines as analysis tools rather than opponents.<ref>{{cite web|url=http://www.dw.com/en/world-chess-champion-magnus-carlsen-the-computer-never-has-been-an-opponent/a-19186058|title=World chess champion Magnus Carlsen: 'The computer never has been an opponent'|publisher=Deutsche Welle|date=16 April 2016|access-date=26 August 2016}}</ref> Chess grandmaster [[Andrew Soltis]] stated in 2016 "The computers are just much too good" and that world champion [[Magnus Carlsen]] won't play computer chess because "he just loses all the time and there's nothing more depressing than losing without even being in the game."<ref name="npr 20 years">{{cite news |title=20 Years Later, Humans Still No Match For Computers On The Chessboard |url=https://www.npr.org/sections/alltechconsidered/2016/10/24/499162905/20-years-later-humans-still-no-match-for-computers-on-the-chessboard |access-date=28 June 2020 |work=NPR.org |date=2016 |language=en}}</ref>
== Computer methods ==
Since the era of mechanical machines that played rook and king endings and electrical machines that played other games like [[hex (board game)|hex]] in the early years of the 20th century, scientists and theoreticians have sought to develop a procedural representation of how humans learn, remember, think and apply knowledge, and the game of chess, because of its daunting complexity, became the "[[Drosophila]] of artificial intelligence (AI)".{{refn|group=Note|What this means is that chess, like the common fruit fly, is a simple and more accessible and familiar paradigm to experiment with technology that can be used to produce knowledge about other, more complex systems.}} The procedural resolution of complexity became synonymous with thinking, and early computers, even before the chess automaton era, were popularly referred to as "electronic brains". Several different schema were devised starting in the latter half of the 20th century to represent knowledge and thinking, as applied to playing the game of chess (and other games like checkers):
* search based (brute force vs selective search)
** Search in search based schema ([[minimax]]/[[Alpha–beta pruning|alpha-beta]], [[Monte Carlo tree search]])
** Evaluations in search based schema ([[machine learning]], [[Artificial neural network|neural networks]], [[Texel (graphics)|texel]] tuning, [[genetic algorithm]]s, [[gradient descent]], [[reinforcement learning]])
* [[Knowledge-based systems|knowledge based]] (PARADISE, [[endgame tablebases]])
Using "ends-and-means" heuristics a human chess player can intuitively determine optimal outcomes and how to achieve them regardless of the number of moves necessary, but a computer must be systematic in its analysis. Most players agree that [[combinatorial search#Lookahead|looking at least five moves ahead]] (ten [[ply (game theory)|plies]]) when necessary is required to play well. Normal tournament rules give each player an average of three minutes per move. On average there are more than 30 legal moves per chess position, so a computer must examine a quadrillion possibilities to look ahead ten plies (five full moves); one that could examine a million positions a second would require more than 30 years.<ref name="hapgood19821223_30">{{cite news | url=https://books.google.com/books?id=_n1vr0_RbXoC&pg=PA827 | title=Computer chess bad-human chess worse | work=New Scientist | date=23–30 December 1982 | access-date=22 January 2015 | author=Hapgood, Fred | pages=827–830 }}{{Dead link|date=December 2023 |bot=InternetArchiveBot |fix-attempted=yes }}</ref>
The earliest attempts at procedural representations of playing chess predated the digital electronic age, but it was the stored program digital computer that gave scope to calculating such complexity. Claude Shannon, in 1949, laid out the principles of algorithmic solution of chess. In that paper, the game is represented by a "tree", or digital data structure of choices (branches) corresponding to moves. The nodes of the tree were positions on the board resulting from the choices of move. The impossibility of representing an entire game of chess by constructing a tree from first move to last was immediately apparent: there are an average of 36 moves per position in chess and an average game lasts about 35 moves to resignation (60-80 moves if played to checkmate, stalemate, or other draw). There are 400 positions possible after the first move by each player, about 200,000 after two moves each, and nearly 120 million after just 3 moves each.
So a limited lookahead (search) to some depth, followed by using domain-specific knowledge to evaluate the resulting terminal positions was proposed. A kind of middle-ground position, given good moves by both sides, would result, and its evaluation would inform the player about the goodness or badness of the moves chosen. Searching and comparing operations on the tree were well suited to computer calculation; the representation of subtle chess knowledge in the evaluation function was not. The early chess programs suffered in both areas: searching the vast tree required computational resources far beyond those available, and what chess knowledge was useful and how it was to be encoded would take decades to discover.
The developers of a chess-playing computer system must decide on a number of fundamental implementation issues. These include:
* [[Graphical user interface]] (GUI) – how moves are entered and communicated to the user, how the game is recorded, how the time controls are set, and other interface considerations
* [[Board representation (chess)|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;
* [[Evaluation function|Leaf evaluation]] – how to evaluate the value of a board position, if no further search will be done from that position.
[[Adriaan de Groot]] interviewed a number of chess players of varying strengths, and concluded that both [[chess master|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 equivalent of this in computer chess are [[evaluation function]]s for leaf evaluation, which correspond to the human players' pattern recognition skills, and the use of machine learning techniques in training them, such as Texel tuning, [[stochastic gradient descent]], and [[reinforcement learning]], which corresponds to building experience in human players. This allows modern programs to examine some lines in much greater depth than others by using forwards pruning and other selective heuristics to simply not consider moves the program assume to be poor through their evaluation function, in the same way that human players do. The only fundamental difference between a computer program and a human in this sense is that a computer program can search much deeper than a human player could, allowing it to search more nodes and bypass the [[horizon effect]] to a much greater extent than is possible with human players.
=== Graphical user interface ===
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 [[algebraic chess notation|long algebraic notation]], but today users expect chess programs to understand standard [[algebraic chess notation]].
Starting in the late 1990s, programmers began to develop separately ''engines'' (with a [[command-line interface]] which calculates which moves are strongest in a position) or a ''[[graphical user interface]]'' (GUI) which provides the player with a chessboard they can see, and pieces that can be moved. Engines communicate their moves to the GUI using a protocol such as the Chess Engine Communication Protocol (CECP) or [[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 [[chess engine]].)
Developers have to decide whether to connect the engine to an opening book and/or endgame [[tablebase]]s or leave this to the GUI.
=== Board representations ===
{{Main|Board representation (chess)}}
The [[data structure]] used to represent each chess position is key to the performance of move generation and [[Punctuation (chess)#Position evaluation symbols|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 coding|huffman coded]] positions for compact long-term storage.
=== Search techniques ===
Computer chess programs consider chess moves as a [[game tree]]. In theory, they examine all moves, then all counter-moves to those moves, then all moves countering them, and so on, where each individual move by one player is called a "[[ply (game theory)|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).
==== Minimax search====
{{further|Alpha–beta pruning|minimax}}
One particular type of search algorithm used in computer chess are [[minimax]] search algorithms, where at each ply the "best" move by the player is selected; one player is trying to maximize the score, the other to minimize it. By this alternating process, one particular terminal node whose evaluation represents the searched value of the position will be arrived at. Its value is backed up to the root, and that evaluation becomes the valuation of the position on the board. This search process is called minimax.
A naive implementation of the minimax algorithm 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. [[Alpha–beta pruning]], a system of defining upper and lower bounds on possible search results and searching until the bounds coincided, is typically used to reduce the search space of the program.
In addition, various selective search heuristics, such as [[quiescence search]], forward pruning, search extensions and search reductions, are also used as well. These heuristics are triggered based on certain conditions in an attempt to weed out obviously bad moves (history moves) or to investigate interesting nodes (e.g. check extensions, [[passed pawn]]s on seventh [[rank (chess)|rank]], etc.). These selective search heuristics 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 or reduced, there is a risk cutting out interesting nodes.
==== Monte Carlo tree search ====
{{further|Monte Carlo tree search}}
Monte Carlo tree search (MCTS) is a heuristic search algorithm which expands the search tree based on random sampling of the search space. A version of Monte Carlo tree search commonly used in computer chess is PUCT, Predictor and Upper Confidence bounds applied to Trees.
DeepMind's [[AlphaZero]] and [[Leela Chess Zero]] uses MCTS instead of minimax. Such engines use [[batch processing|batching]] on [[graphics processing units]] in order to calculate their [[evaluation function]]s and policy (move selection), and therefore require a [[parallel computing|parallel]] search algorithm as calculations on the GPU are inherently parallel. The minimax and alpha-beta pruning algorithms used in computer chess are inherently serial algorithms, so would not work well with batching on the GPU. On the other hand, MCTS is a good alternative, because the random sampling used in Monte Carlo tree search lends itself well to parallel computing, and is why nearly all engines which support calculations on the GPU use MCTS instead of alpha-beta.
==== Other optimizations ====
Many other optimizations can be used to make chess-playing programs stronger. For example, [[transposition table]]s are used to record positions that have been previously evaluated, to save recalculation of them. [[Refutation table]]s 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). The drawback is that transposition tables at deep ply depths can get quite large – tens to hundreds of millions of entries. IBM's Deep Blue transposition table in 1996, for example was 500 million entries. Transposition tables that are too small can result in spending more time searching for non-existent entries due to threshing than the time saved by entries found. Many chess engines use [[pondering]], searching to deeper levels on the opponent's time, similar to human beings, to increase their playing strength.
Of course, faster hardware and additional memory can improve chess program playing strength. Hyperthreaded architectures can improve performance modestly if the program is running on a single core or a small number of cores. Most modern programs are designed to take advantage of multiple cores to do parallel search. Other programs are designed to run on a general purpose computer and allocate move generation, parallel search, or evaluation to dedicated processors or specialized co-processors.
==== History ====
The [[Claude Shannon#Shannon's computer chess program|first paper]] on search was by [[Claude Shannon]] in 1950.<ref name="wheland197810">{{cite news | url=https://archive.org/stream/byte-magazine-1978-10/1978_10_BYTE_03-10_Chess_for_the_Microcomputer#page/n167/mode/2up | title=A Computer Chess Tutorial | work=BYTE | date=October 1978 | access-date=17 October 2013 | author=Wheland, Norman D. | page=168}}</ref> He predicted the two main possible search strategies which would be used, which he labeled "Type A" and "Type B",<ref name="shannon">{{Harvcol|Shannon|1950}}</ref> before anyone had programmed a computer to play chess.
Type A programs would use a "[[brute-force search|brute force]]" approach, examining every possible position for a fixed number of moves using a pure naive [[minimax|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 10<sup>9</sup> positions involved in looking three moves ahead for both sides (six [[Ply (game theory)|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. An later search algorithm called [[alpha–beta pruning]], a system of defining upper and lower bounds on possible search results and searching until the bounds coincided, reduced the branching factor of the game tree logarithmically, but it still was not feasible for chess programs at the time to exploit the exponential explosion of the tree.
Second, it ignored the problem of quiescence, trying to only evaluate a position that is at the end of an [[exchange (chess)|exchange]] of pieces or other important sequence of moves ('lines'). He expected that adapting minimax to cope with this would greatly increase the number of positions needing to be looked at and slow the program down still further. 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.
This led naturally to what is referred to as "selective search" or "type B search", using chess knowledge (heuristics) to select a few presumably good moves from each position to search, and prune away the others without searching. Instead of wasting processing power examining bad or trivial moves, Shannon suggested that type B programs would use two improvements:
# Employ a [[quiescence search]].
# Employ forward pruning; i.e. 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. However, early attempts at selective search often resulted in the best move or moves being pruned away. As a result, little or no progress was made for the next 25 years dominated by this first iteration of the selective search paradigm. The best program produced in this early period was Mac Hack VI in 1967; it played at the about the same level as the average amateur (C class on the United States Chess Federation rating scale).
Meanwhile, hardware continued to improve, and in 1974, brute force searching was implemented for the first time in the Northwestern University Chess 4.0 program. In this approach, all alternative moves at a node are searched, and none are pruned away. They discovered that the time required to simply search all the moves was much less than the time required to apply knowledge-intensive heuristics to select just a few of them, and the benefit of not prematurely or inadvertently pruning away good moves resulted in substantially stronger performance.
In the 1980s and 1990s, progress was finally made in the selective search paradigm, with the development of [[quiescence search]], null move pruning, and other modern selective search heuristics. These heuristics had far fewer mistakes than earlier heuristics did, and was found to be worth the extra time it saved because it could search deeper and widely adopted by many engines. While many modern programs do use [[alpha-beta search]] as a substrate for their search algorithm, these additional selective search heuristics used in modern programs means that the program no longer does a "brute force" search. Instead they heavily rely on these selective search heuristics to extend lines the program considers good and prune and reduce lines the program considers bad, to the point where most of the nodes on the search tree are pruned away, enabling modern programs to search very deep.
In 2006, [[Rémi Coulom]] created [[Monte Carlo tree search]], another kind of type B selective search. In 2007, an adaption of Monte Carlo tree search called Upper Confidence bounds applied to Trees or UCT for short was created by Levente Kocsis and Csaba Szepesvári. In 2011, Chris Rosin developed a variation of UCT called Predictor + Upper Confidence bounds applied to Trees, or PUCT for short. PUCT was then used in [[AlphaZero]] in 2017, and later in [[Leela Chess Zero]] in 2018.
=== Knowledge versus search (processor speed) ===
In the 1970s, most chess programs ran on super computers like Control Data Cyber 176s or Cray-1s, indicative that during that developmental period for computer chess, processing power was the limiting factor in performance. Most chess programs struggled to search to a depth greater than 3 ply. It was not until the hardware chess machines of the 1980s, that a relationship between processor speed and knowledge encoded in the evaluation function became apparent.
It has been estimated that doubling the computer speed gains approximately fifty to seventy [[Elo rating system|Elo]] points in playing strength {{harvcol|Levy|Newborn|1991|p=192}}.
=== Leaf evaluation ===
{{main|Evaluation function}}
For most chess positions, computers cannot look ahead to all possible final positions. Instead, they must look ahead a few [[Ply (game theory)|plies]] and compare the possible positions, known as leaves. The algorithm that evaluates leaves is termed the "evaluation function", and these algorithms are often vastly different between different chess programs. Evaluation functions typically evaluate positions in hundredths of a pawn (called a centipawn), where by convention, a positive evaluation favors White, and a negative evaluation favors Black. However, some evaluation function output win/draw/loss percentages instead of centipawns.
Historically, handcrafted evaluation functions 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 (chess)|pawn]], 3 points for a [[knight (chess)|knight]] or [[bishop (chess)|bishop]], 5 points for a [[rook (chess)|rook]], and 9 points for a [[queen (chess)|queen]]. (See [[Chess piece relative value]].) The [[king (chess)|king]] is sometimes given an arbitrarily high value such as 200 points ([[Claude Shannon#Shannon's computer chess program|Shannon's paper]]) to ensure that a checkmate outweighs all other factors {{Harvcol|Levy|Newborn|1991|pp=45}}. In addition to points for pieces, most handcrafted evaluation functions 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). [[Machine learning]] techniques such as Texel turning, [[stochastic gradient descent]], or [[reinforcement learning]] are usually used to optimise handcrafted evaluation functions.
Most modern evaluation functions make use of [[Artificial neural network|neural networks]]. The most common evaluation function in use today is the [[efficiently updatable neural network]], which is a shallow neural network whose inputs are [[piece-square table]]s. Piece-square tables are a set of 64 values corresponding to the squares of the chessboard, and there typically exists a piece-square table for every piece and colour, resulting in 12 piece-square tables and thus 768 inputs into the neural network. In addition, some engines use [[deep neural networks]] in their evaluation function. Neural networks are usually trained using some [[reinforcement learning]] algorithm, in conjunction with [[supervised learning]] or [[unsupervised learning]].
The output of the evaluation function is a single scalar, quantized in centipawns or other units, which is, in the case of handcrafted evaluation functions, a weighted summation of the various factors described, or in the case of neural network based evaluation functions, the output of the head of the neural network. The evaluation putatively represents or approximates the value of the subtree below the evaluated node as if it had been searched to termination, i.e. the end of the game. During the search, an evaluation is compared against evaluations of other leaves, eliminating nodes that represent bad or poor moves for either side, to yield a node which by convergence, represents the value of the position with best play by both sides.
== Endgame tablebases ==
{{Main|Endgame tablebase}}
Endgame play had long been one of the great weaknesses of chess programs because of the depth of search needed. Some otherwise master-level programs were unable to win in positions where even intermediate human players could force a win.
To solve this problem, computers have been used to analyze some [[chess endgame]] positions completely, starting with [[king (chess)|king]] and [[pawn (chess)|pawn]] against king. Such endgame tablebases 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 (computer programmer)|Ken Thompson]] was a pioneer in this area.
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 (chess)|rook]] against king and [[queen (chess)|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 returned the best moves.
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 {{Harvcol|Levy|Newborn|1991|pp=144–48}}, {{Harvcol|Nunn|2002|p=49}}.
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{{snd}} 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 Tablebase, the De Koning Database and the [[Eugene Nalimov|Nalimov]] Tablebase which is used by many chess programs such as [[Rybka]], [[Shredder (chess)|Shredder]] and [[Fritz (chess)|Fritz]]. Tablebases for all positions with six pieces are available.<ref>{{cite web|author=Kirill Kryukov |url=http://kirill-kryukov.com/chess/tablebases-online/ |title=Endgame Tablebases Online |publisher=Kirill-kryukov.com |access-date=2010-04-03}}</ref> Some seven-piece endgames have been analyzed by Marc Bourzutschky and Yakov Konoval.<ref>{{cite web|url=http://www.xs4all.nl/~timkr/chess2/diary_16.htm |title=Open chess diary 301–320 |publisher=Xs4all.nl |access-date=2010-04-03}}</ref> Programmers using the Lomonosov supercomputers in Moscow have completed a chess tablebase for all endgames with seven pieces or fewer (trivial endgame positions are excluded, such as six white pieces versus a lone black [[king (chess)|king]]).<ref>[http://tb7.chessok.com/shared-positions http://tb7.chessok.com] Lomonosov website allowing registered user to access 7-piece tablebase, and a forum with positions found.</ref><ref>[https://www.chess.com/forum/view/endgames/who-wins-from-this-puzzle "Who wins from this? (chess puzzle)"] An example chess position found from the Lomonosov chess tablebase.</ref> In all of these endgame databases it is assumed that castling is no longer possible.
Many 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. 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' 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.
The Nalimov tablebases, which use state-of-the-art [[Data compression|compression]] techniques, require 7.05 [[Gigabyte|GB]] of hard disk space for all five-piece endings. To cover all the six-piece endings requires approximately 1.2 [[Terabyte|TB]]. It is estimated that a seven-piece tablebase requires between 50 and 200 [[Terabyte|TB]] of storage space.<ref>The Rybka Lounge / Computer Chess / Tablebase sizes, http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=9380 {{Webarchive|url=https://web.archive.org/web/20170627041247/http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=9380 |date=2017-06-27 }}, 19th June 2012</ref>
Endgame databases featured prominently in 1999, when Kasparov played an exhibition match on the Internet against the [[Kasparov versus the World|rest of the world]]. A seven piece [[Queen (chess)|Queen]] and [[pawn (chess)|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.
The most popular endgame tablebase is syzygy which is used by most top computer programs like [[Stockfish (chess)|Stockfish]], [[Leela Chess Zero]], and [[Komodo (chess)|Komodo]]. It is also significantly smaller in size than other formats, with 7-piece tablebases taking only 18.4 TB.<ref>{{cite web |url=https://lichess.org/blog/W3WeMyQAACQAdfAL/7-piece-syzygy-tablebases-are-complete |title=7-piece Syzygy tablebases are complete |website=lichess.org |access-date=2023-10-02}}</ref>
For a current state-of-the art chess engine like Stockfish, a table base only provides a very minor increase in playing strength (approximately 3 Elo points for syzygy 6men as of Stockfish 15).<ref>{{Cite web |title=Useful data |url=https://github.com/official-stockfish/Stockfish/wiki/Useful-data |access-date=2023-10-12 |website=GitHub |language=en}}</ref>
== Opening book ==
Chess engines, like human beings, may save processing time as well as select strong variations as expounded by the masters, by referencing an [[Chess opening book|opening book]] stored in a disk database. Opening books cover the opening moves of a game to variable depth, depending on opening and variation, but usually to the first 10-12 moves (20-24 ply). Since the openings have been studied in depth by the masters for centuries, and some are known to well into the middle game, the valuations of specific variations by the masters will usually be superior to the general heuristics of the program.
While at one time, playing an out-of-book move in order to put the chess program onto its own resources might have been an effective strategy because chess opening books were selective to the program's playing style, and programs had notable weaknesses relative to humans, that is no longer true today.{{when|date=April 2020}} The opening books stored in computer databases are most likely far more extensive than even the best prepared humans, and playing an early out-of-book move may result in the computer finding the unusual move in its book and saddling the opponent with a sharp disadvantage. Even if it does not, playing out-of-book may be much better for tactically sharp chess programs than for humans who have to discover strong moves in an unfamiliar variation over the board.
In modern engine tournaments, opening books are used to force the engines to play intentionally unbalanced openings to reduce the draw rate and to add more variety to the games.<ref>{{Cite web |title=TCEC Openings FAQ |url=https://tcec-chess.com/articles/TCEC_Openings_FAQ.html |access-date=2023-10-12 |website=tcec-chess.com}}</ref>
== Computer chess rating lists ==
{{see also|Chess engine#Ratings}}
[[Chess Engines Grand Tournament|CEGT]],<ref>{{Citation | url=http://www.husvankempen.de/nunn/rating.htm | title=CEGT 40/20 | date=12 October 2008 | publisher=[[Chess Engines Grand Tournament]] | access-date=21 October 2008 | archive-url=https://web.archive.org/web/20120301182317/http://www.husvankempen.de/nunn/rating.htm | archive-date=1 March 2012 | url-status=dead | df=dmy-all }}</ref> CSS,<ref>{{Citation | url=http://www.computerschach.de/index.php?option=com_wrapper&Itemid=242 | title=Computerschach und Spiele – Eternal Rating | date=18 March 2007 | publisher= Computerschach und Spiele | access-date=21 May 2008}}</ref> [[Swedish Chess Computer Association|SSDF]],<ref>{{Citation | url=http://ssdf.bosjo.net/list.htm | title=The SSDF Rating List | publisher=[[Swedish Chess Computer Association]] | date=26 September 2008 | access-date=20 October 2008}}</ref> WBEC,<ref>{{Citation | url=http://wbec-ridderkerk.nl/html/BayesianElo_ed15.htm | title=BayesianElo Ratinglist of WBEC Ridderkerk | access-date=20 July 2008}}</ref> [[REBEL (chess)|REBEL]],<ref>{{cite web | url=https://rebel13.nl/misc/gambit-rating-list.html | title=Gambit Rating List | publisher=Home of the Dutch Rebel | date=January 30, 2021 | access-date=December 12, 2021}}</ref> FGRL,<ref>{{cite web | url=http://fastgm.de | title=FGRL | publisher=FastGM's Rating List | access-date=December 12, 2010}}</ref> and IPON<ref>{{cite web | url=http://www.inwoba.de/bayes.html | title=IPON | publisher=Ingo Bauer | date=November 16, 2016 | access-date=February 3, 2016 | archive-url=https://web.archive.org/web/20190125041233/http://inwoba.de/bayes.html | archive-date=January 25, 2019 | url-status=dead }}</ref> maintain rating lists allowing fans to compare the strength of engines. Various versions of [[Stockfish (chess)|Stockfish]], [[Komodo (chess)|Komodo]], [[Leela Chess Zero]], and [[Fritz (chess)|Fat Fritz]] dominate the rating lists in the early 2020s.
CCRL (Computer Chess Rating Lists) is an organisation that tests computer [[chess engine]]s' [[Elo rating system|strength]] by playing the programs against each other. CCRL was founded in 2006 to promote computer-computer competition and tabulate results on a rating list.<ref name=CCRL>CCRL, http://ccrl.chessdom.com/ {{Webarchive|url=https://web.archive.org/web/20220121151824/http://ccrl.chessdom.com/ |date=2022-01-21 }}, 14 November 2021</ref>
The organisation runs three different lists: 40/40 (40 minutes for every 40 moves played), 40/4 (4 minutes for every 40 moves played), and 40/4 [[Chess960|FRC]] (same time control but Chess960).<ref group=Note name=Note1/> Pondering (or [[permanent brain]]) is switched off and timing is adjusted to the AMD64 X2 4600+ (2.4 GHz) [[CPU]] by using [[Crafty 19.17 BH]] as a benchmark. Generic, neutral [[chess opening book|opening books]] are used (as opposed to the engine's own book) up to a limit of 12 moves into the game alongside 4 or 5 man [[tablebases]].<ref name=CCRL /><ref>CCRL Discussion Board, http://kirill-kryukov.com/chess/discussion-board/viewtopic.php?f=7&t=2808, 19 June 2012</ref><ref>Adam's Computer Chess Pages, http://adamsccpages.blogspot.co.uk/2012/05/ccrl.html, 19 June 2012</ref>
== History ==
=== Pre-computer age ===
[[File:Ajedrecista primero1.JPG|thumb|[[El Ajedrecista]]]]
The idea of creating a chess-playing machine dates back to the eighteenth century. Around 1769, the chess playing [[automaton]] called [[Mechanical Turk|The Turk]], created by [[Kingdom of Hungary|Hungarian]] inventor [[Wolfgang von Kempelen|Farkas Kempelen]], 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, built by Spanish engineer [[Leonardo Torres Quevedo]], which played a king and rook versus king ending, 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.
=== Early software age: selective search and Botvinnik ===
Since then, chess enthusiasts and [[computer engineer]]s have built, with increasing degrees of seriousness and success, chess-playing machines and computer programs. 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. Botvinnik’s interest in Computer Chess started in the 50s, favouring chess algorithms based on Shannon's selective type B strategy, as discussed along with Max Euwe 1958 in Dutch Television. 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 which won a correspondence chess match against the Kotok-McCarthy-Program led by John McCarthy in 1967.(see [[Kotok-McCarthy]]). Later he advised the team that created the chess program Kaissa at Moscow’s Institute of Control Sciences. Botvinnik had his own ideas to model a Chess Master's Mind. After publishing and discussing his early ideas on attack maps and trajectories at Moscow Central Chess Clubin 1966, he found Vladimir Butenko as supporter and collaborator. Butenko first implemented the 15x15 vector attacks board representation on a M-20 computer, determining trajectories. After Botvinnik introduced the concept of Zones in 1970, Butenko refused further cooperation and began to write his own program, dubbed Eureka. In the 70s and 80s, leading a team around Boris Stilman, Alexander Yudin, Alexander Reznitskiy, Michael Tsfasman and Mikhail Chudakov, Botvinnik worked on his own project 'Pioneer' - which was an Artificial Intelligence based chess project. In the 90s, Botvinnik already in his 80s, he worked on the new project 'CC Sapiens'.
=== Later software age: full-width search ===
One developmental milestone occurred when the team from [[Northwestern University]], which was responsible for the [[Chess (Northwestern University)|Chess]] series of programs and won the first three [[Association for Computing Machinery|ACM]] [[World Computer Chess Championship#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. The type A implementation 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, and that had been successfully started by the Russian ITEP in 1965.
=== Rise of chess machines ===
In 1978, an early rendition of Ken Thompson's hardware chess machine [[Belle (chess machine)|Belle]], entered and won the North American Computer Chess Championship over the dominant Northwestern University Chess 4.7.
=== Microcomputer revolution ===
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 [[IBM Deep Blue|Deep Blue]], a brute-force machine capable of examining 500 million nodes per second, defeated World Champion Garry Kasparov, marking the first time a computer has defeated a reigning world chess champion in standard time control.
=== Super-human chess ===
In 2016, [[NPR]] asked experts to characterize the playing style of computer chess engines. [[Murray Campbell]] of IBM stated that "Computers don't have any sense of aesthetics... They play what they think is the objectively best move in any position, even if it looks absurd, and they can play any move no matter how ugly it is." Grandmasters Andrew Soltis and [[Susan Polgar]] stated that computers are more likely to retreat than humans are.<ref name="npr 20 years"/>
=== Neural network revolution ===
While [[Artificial neural network|neural networks]] have been used in the [[evaluation function]]s of chess engines since the late 1980s, with programs such as NeuroChess, Morph, Blondie25, Giraffe, [[AlphaZero]], and [[MuZero]],<ref>{{citation|title=Learning to Play the Game of Chess|last=Thurn|first=Sebastian|year=1995|publisher=MIT Press|url=https://proceedings.neurips.cc/paper/1994/file/d7322ed717dedf1eb4e6e52a37ea7bcd-Paper.pdf|access-date=12 December 2021}}</ref><ref>{{citation|title=A Self-Learning, Pattern-Oriented Chess Program|last=Levinson|first=Robert|year=1989|publisher=ICCA Journal|volume=12|issue=4}}</ref><ref name="Giraffe">{{citation|title=Giraffe: Using Deep Reinforcement Learning to Play Chess|last=Lai|first=Matthew|date=4 September 2015|arxiv=1509.01549v1}}</ref><ref>{{Cite arXiv|eprint = 1712.01815|last1 = Silver|first1 = David|last2 = Hubert|first2 = Thomas|last3 = Schrittwieser|first3 = Julian|last4 = Antonoglou|first4 = Ioannis|last5 = Lai|first5 = Matthew|last6 = Guez|first6 = Arthur|last7 = Lanctot|first7 = Marc|last8 = Sifre|first8 = Laurent|last9 = Kumaran|first9 = Dharshan|last10 = Graepel|first10 = Thore|last11 = Lillicrap|first11 = Timothy|last12 = Simonyan|first12 = Karen|last13 = Hassabis|first13 = Demis|title = Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm|year = 2017|class = cs.AI}}</ref><ref name="MuZero">{{cite journal|arxiv=1911.08265|first1=Julian|last1=Schrittwieser|first2=Ioannis|last2=Antonoglou|title=Mastering Atari, Go, chess and shogi by planning with a learned model|last3=Hubert|last9=Hassabis|first11=Timothy|last11=Lillicrap|first10=Thore|last10=Graepel|first9=Demis|first8=Edward|first3=Thomas|last8=Lockhart|last7=Guez|first6=Simon|last6=Schmitt|first5=Laurent|last5=Sifre|first4=Karen|last4=Simonyan|first7=Arthur|journal=Nature|year=2020|volume=588|issue=7839|pages=604–609|doi=10.1038/s41586-020-03051-4|pmid=33361790|bibcode=2020Natur.588..604S|s2cid=208158225}}</ref> neural networks did not become widely adopted by chess engines until the arrival of [[efficiently updatable neural network]]s in the summer of 2020. Efficiently updatable neural networks were originally developed in [[computer shogi]] in 2018 by Yu Nasu,<ref name="Nasu">{{cite web|title=Efficiently Updatable Neural-Network-based Evaluation Function for computer Shogi|author=Yu Nasu|url=https://www.apply.computer-shogi.org/wcsc28/appeal/the_end_of_genesis_T.N.K.evolution_turbo_type_D/nnue.pdf|date=April 28, 2018|language=Japanese}}</ref><ref name="Nasu2">{{cite web|title=Efficiently Updatable Neural-Network-based Evaluation Function for computer Shogi (Unofficial English Translation)|author=Yu Nasu|website=[[GitHub]]|url=https://github.com/asdfjkl/nnue/blob/main/nnue_en.pdf|date=April 28, 2018|language=English}}</ref> and had to be first ported to a derivative of Stockfish called Stockfish NNUE on 31 May 2020,<ref>{{cite web|url=https://github.com/nodchip/Stockfish/releases/tag/stockfish-nnue-2020-05-30|title=Release stockfish-nnue-2020-05-30|website=Github|last=Noda|first=Hisayori|date=30 May 2020|access-date=12 December 2021}}</ref> and integrated into the official Stockfish engine on 6 August 2020,<ref name="Introducing NNUE Evaluation">{{cite web|title=Introducing NNUE Evaluation|url=https://blog.stockfishchess.org/post/625828091343896577/introducing-nnue-evaluation|date=6 August 2020}}</ref><ref name="Joost VandeVondele">{{cite web|title= official-stockfish / Stockfish, NNUE merge|url=https://github.com/official-stockfish/Stockfish/issues/2823#issue-665540175|author=Joost VandeVondele|website=[[GitHub]]|date=July 25, 2020}}</ref> before other chess programmers began to adopt neural networks into their engines.
Some people, such as the [[Royal Society]]'s [[Venki Ramakrishnan]], believe that [[AlphaZero]] lead to the widespread adoption of neural networks in chess engines.<ref>{{cite book |title=[[Possible Minds: Twenty-five Ways of Looking at AI]] |date=2019 |publisher=Penguin Press |isbn=978-0525557999 |edition=Kindle| page=174| chapter=[[Venki Ramakrishnan]]: Will Computers Become Our Overlords?}}</ref> However, AlphaZero influenced very few engines to begin using neural networks, and those tended to be new experimental engines such as [[Leela Chess Zero]], which began specifically to replicate the AlphaZero paper. The [[deep neural network]]s used in AlphaZero's evaluation function required expensive [[graphics processing units]], which were not compatible with existing chess engines. The vast majority of chess engines only use [[central processing units]], and computing and processing information on the GPUs require special [[Library (computing)|libraries]] in the backend such as [[Nvidia]]'s [[CUDA]], which none of the engines had access to. Thus the vast majority of chess engines such as [[Komodo (chess)|Komodo]] and [[Stockfish (chess)|Stockfish]] continued to use handcrafted evaluation functions until [[efficiently updatable neural network]]s were ported to computer chess in 2020, which did not require either the use of GPUs or libraries like CUDA at all. Even then, the neural networks used in computer chess are fairly shallow, and the [[deep reinforcement learning]] methods pioneered by AlphaZero are still extremely rare in computer chess.
=== Timeline ===
* 1769 – [[Wolfgang von Kempelen]] builds [[Mechanical Turk|the Turk]]. Presented as a chess-playing automaton, it is secretly operated by a human player hidden inside the machine.
* 1868 – Charles Hooper presents the [[Ajeeb]] automaton{{snd}} which also has a human chess player hidden inside.
* 1912 – [[Leonardo Torres y Quevedo]] builds [[El Ajedrecista]], a machine that could play [[wikibooks:Chess/The Endgame/King and Rook vs. King|King and Rook versus King endgames]].
* 1941 – Predating comparable work by at least a decade, [[Konrad Zuse]] develops computer chess algorithms in his [[Plankalkül]] programming formalism. Because of the circumstances of the Second World War, however, they were not published, and did not come to light, until the 1970s.
* 1948 – [[Norbert Wiener]]'s book ''Cybernetics'' describes how a chess program could be developed using a depth-limited minimax search with an [[evaluation function]].
* 1950 – [[Claude Shannon]] publishes "Programming a Computer for Playing Chess", one of the first papers on the algorithmic methods of computer chess.
* 1951 – [[Alan Turing]] is first to publish a program, developed on paper, that was capable of playing a full game of chess (dubbed [[Turochamp]]).<ref>Chess, a subsection of chapter 25, Digital Computers Applied to Games, of Faster than Thought, ed. B. V. Bowden, Pitman, London (1953). [https://web.archive.org/web/20031124134110/http://www.turingarchive.org/browse.php/B/7 Online].</ref><ref>[http://www.chessgames.com/perl/chessgame?gid=1356927 A game played by Turing's chess algorithm]</ref>
* 1952 – [[Dietrich Prinz]] develops a program that solves chess problems.
{{Chess diagram 6x6
| tright
|
|rd|nd|qd|kd|nd|rd
|pd|pd|pd|pd|pd|pd
| | | | | |
| | | | | |
|pl|pl|pl|pl|pl|pl
|rl|nl|ql|kl|nl|rl
| '''[[Los Alamos chess]]'''. This simplified version of chess was played in 1956 by the [[MANIAC I]] computer.
}}
* 1956 – [[Los Alamos chess]] is the first program to play a chess-like game, developed by Paul Stein and Mark Wells for the [[MANIAC I]] computer.
* 1956 – [[John McCarthy (computer scientist)|John McCarthy]] invents the [[alpha–beta pruning|alpha–beta]] search algorithm.
* 1957 – The first programs that can play a full game of chess are developed, one by Alex Bernstein<ref>{{cite web|url=http://www.chessville.com/BillWall/EarlyComputerChessPrograms.htm |title=Chessville – Early Computer Chess Programs – by Bill Wall – Bill Wall's Wonderful World of Chess |publisher=Archive.is |access-date=1 December 2014 |url-status=bot: unknown |archive-url=https://archive.today/20120721202324/http://www.chessville.com/BillWall/EarlyComputerChessPrograms.htm |archive-date=21 July 2012 }}</ref> and one by [[Russia]]n programmers using a [[BESM]].
* 1958 – NSS becomes the first chess program to use the alpha–beta search algorithm.
* 1962 – The first program to play credibly, [[Kotok-McCarthy]], is published at [[Massachusetts Institute of Technology|MIT]].
* 1963 – Grandmaster [[David Bronstein]] defeats an [[Minsk family of computers|M-20]] running an early chess program.<ref>[http://www.chessgames.com/perl/chessgame?gid=1238081 David Bronstein v M-20, replay at Chessgames.com]</ref>
* 1966–67 – The first chess match between computer programs is played. [[Moscow]] [[Institute for Theoretical and Experimental Physics]] (ITEP) defeats Kotok-McCarthy at [[Stanford University]] by telegraph over nine months.
* 1967 – [[MacHack (chess)|Mac Hack VI]], by [[Richard Greenblatt (programmer)|Richard Greenblatt]] et al. introduces [[transposition table]]s and employs dozens of carefully tuned move selection heuristics; it becomes the first program to defeat a person in tournament play. Mac Hack VI played about C class level.
* 1968 – Scottish chess champion [[David Levy (chess player)|David Levy]] makes a 500 [[pound (monetary unit)|pound]] bet with AI pioneers [[John McCarthy (computer scientist)|John McCarthy]] and [[Donald Michie]] that no computer program would win a chess match against him within 10 years.
* 1970 – [[Monty Newborn]] and the [[Association for Computing Machinery]] organize the first [[North American Computer Chess Championship]]s in New York.
* 1971 – [[Ken Thompson]], an American Computer scientist at Bell Labs and creator of the Unix operating system, writes his first chess-playing program called "chess" for the earliest version of [[Unix]].<ref name="ritchie01">{{cite journal | journal=ICGA Journal | volume=24 | issue=2 |date=June 2001 | url=https://www.bell-labs.com/usr/dmr/www/ken-games.html| title=Ken, Unix and Games | author=[[Dennis Ritchie]]}}</ref>
* 1974 – [[David Levy (chess player)|David Levy]], Ben Mittman and [[Monty Newborn]] organize the first [[World Computer Chess Championship]] which is won by the Russian program [[Kaissa]].
* 1975 – After nearly a decade of only marginal progress since the high-water mark of Greenblatt's MacHack VI in 1967, Northwestern University Chess 4.5 is introduced featuring full-width search, and innovations of bitboards and iterative deepening. It also reinstated a transposition table as first seen in Greenblatt's program. It was thus the first program with an integrated modern structure and became the model for all future development. Chess 4.5 played strong B-class and won the 3rd World Computer Chess Championship the next year.<ref>{{cite web|url=https://link.springer.com/content/pdf/bbm%3A978-1-4612-5515-4%2F1.pdf|title=Appendix CHESS 4.5: Competition in 1976 }}</ref> Northwestern University Chess and its descendants dominated computer chess until the era of hardware chess machines in the early 1980s.
* 1976 – In December, Canadian programmer [[Peter R. Jennings]] releases [[Microchess]], the first game for microcomputers to be sold.<ref>{{cite web|url=https://www.computerhistory.org/chess/orl-4334404555680/|title = Oral History of Peter Jennings | Mastering the Game | Computer History Museum}}</ref>
[[File:BorisChess.jpg|thumb|Released in 1977, Boris was one of the first chess computers to be widely marketed. It ran on a Fairchild F8 8-bit microprocessor with only 2.5 KiB ROM and 256 byte RAM.]]
* 1977 – In March, Fidelity Electronics releases [[Chess Challenger]], the first dedicated chess computer to be sold. The [[International Computer Chess Association]] is founded by chess programmers to organize computer chess championships and report on research and advancements on computer chess in their journal. Also that year, Applied Concepts released [[Boris (chess computer)|Boris]], a dedicated chess computer in a wooden box with plastic chess pieces and a folding board.
* 1978 – [[David Levy (chess player)|David Levy]] wins the bet made 10 years earlier, defeating [[Chess (Northwestern University)|Chess 4.7]] in a six-game match by a score of 4½–1½. The computer's victory in game four is the first defeat of a human master in a tournament.<ref name="douglas197812"/>
* 1979 – [[Frederic Friedel]] organizes a match between IM [[David Levy (chess player)|David Levy]] and [[Chess (Northwestern University)|Chess 4.8]], which is broadcast on German television. Levy and Chess 4.8, running on a CDC Cyber 176, the most powerful computer in the world, fought a grueling 89 move draw.
* 1980 – Fidelity computers win the World Microcomputer Championships each year from 1980 through 1984. In Germany, Hegener & Glaser release their first [[Mephisto (chess computer)|Mephisto]] dedicated chess computer. The USCF prohibits computers from competing in human tournaments except when represented by the chess systems' creators.<ref name="byte198101">{{cite news | url=https://archive.org/stream/byte-magazine-1981-01/1981_01_BYTE_06-01_Hand-held_Computers#page/n293/mode/2up | title=New Restrictions | work=BYTE | date=January 1981 | access-date=18 October 2013 | page=292}}</ref> The Fredkin Prize, offering $100,000 to the creator of the first chess machine to defeat the world chess champion, is established.
* 1981 – [[Cray Blitz]] 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.
* 1984 – The German Company Hegener & Glaser's ''[[Mephisto (chess computer)|Mephisto]]'' line of dedicated chess computers begins a long streak of victories (1984–1990) in the World Microcomputer Championship using dedicated computers running programs [[ChessGenius]] and [[REBEL (chess)|Rebel]].
* 1986 – Software Country (see [[Software Toolworks]]) released ''[[Chessmaster]] 2000'' based on an engine by David Kittinger, the first edition of what was to become the world's best selling line of chess programs.
* 1987 – [[Frederic Friedel]] and physicist Matthias Wüllenweber found [[Chessbase]], releasing the first chess database program. Stuart Cracraft releases [[GNU Chess]], one of the first '[[chess engine]]s' to be bundled with a separate [[graphical user interface]] (GUI), {{proper name|chesstool}}.<ref>{{cite web|url=https://web.cecs.pdx.edu/~trent/gnu/bull/02/nb.html#SEC6|title = GNU's Bulletin, vol. 1 no. 2}}</ref>
* 1988 – [[HiTech]], developed by [[Hans Berliner]] and [[Carl Ebeling]], wins a match against grandmaster [[Arnold Denker]] 3½–½. [[Deep Thought (chess computer)|Deep Thought]] shares first place with [[Tony Miles]] in the Software Toolworks Championship, ahead of former world champion [[Mikhail Tal]] and several grandmasters including [[Samuel Reshevsky]], [[Walter Browne]] and [[Mikhail Gurevich (chess player)|Mikhail Gurevich]]. It also defeats grandmaster [[Bent Larsen]], making it the first computer to beat a GM in a tournament. Its [[Elo rating system|rating]] for performance in this tournament of 2745 (USCF scale) was the highest obtained by a computer player.<ref>Hsu (2002) p. 292</ref><ref>Newborn (1997) p. 159</ref>
* 1989 – Deep Thought demolishes David Levy in a 4-game match 0–4, bringing to an end his famous series of wagers starting in 1968.
* 1990 – On April 25, former world champion [[Anatoly Karpov]] lost in a simul to Hegener & Glaser's Mephisto Portorose M68030 chess computer.<ref>Selective Search. June 1990</ref>
* 1991 – The [[ChessMachine]] based on Ed Schröder's [[REBEL (chess)|Rebel]] wins the World Microcomputer Chess Championship
* 1992 – [[ChessMachine]] wins the 7th [[World Computer Chess Championship]], the first time a microcomputer beat [[mainframe computer|mainframes]]. GM [[John Nunn]] releases ''Secrets of Rook Endings'', the first book based on endgame tablebases developed by [[Ken Thompson]].
* 1993 – Deep Thought-2 loses a four-game match against [[Bent Larsen]]. Chess programs running on personal computers surpass Mephisto's dedicated chess computers to win the Microcomputer Championship, marking a shift from dedicated chess hardware to software on multipurpose personal computers.
* 1995 – [[Fritz (chess)|Fritz 3]], running on a 90Mhz Pentium PC, beats Deep Thought-2 dedicated chess machine, and programs running on several super-computers, to win the 8th [[World Computer Chess Championship]]s in Hong Kong. This marks the first time a chess program running on commodity hardware defeats specialized chess machines and massive super-computers, indicating a shift in emphasis from brute computational power to algorithmic improvements in the evolution of chess engines.
* 1996 – IBM's [[Deep Blue (chess computer)|Deep Blue]] loses a six-game match against [[Garry Kasparov]], 2–4.
* 1997 – [[Deep Blue (chess computer)|Deep(er) Blue]], a highly modified version of the original, wins a six-game match against [[Garry Kasparov]], 3.5-2.5.
* 2000 – [[Stefan Meyer-Kahlen]] and Rudolf Huber draft the [[Universal Chess Interface]], a protocol for GUIs to talk to engines that would gradually become the main form new engines would take.
* 2002 – [[Vladimir Kramnik]] draws an eight-game match against [[Deep Fritz]].
* 2003 – Kasparov draws a six-game match against [[Deep Junior]] and draws a four-game match against [[X3D Fritz]].
* 2004 – a team of computers ([[Hydra (chess)|Hydra]], [[Deep Junior]] and [[Fritz (chess)|Fritz]]) wins 8½–3½ against a strong human team formed by [[Veselin Topalov]], [[Ruslan Ponomariov]] and [[Sergey Karjakin]], who had an average [[Elo rating system|Elo]] rating of 2681. Fabien Letouzey releases the source code for Fruit 2.1, an engine quite competitive with the top closed-source engines of the time. This leads many authors to revise their code, incorporating the new ideas.
* 2005 – [[Rybka]] wins the [[International Paderborn Computer Chess Championship|IPCCC]] tournament and very quickly afterwards becomes the strongest engine.<ref>[http://www.rybkachess.com/docs/PADERBORNCOMPUTER.htm International Paderborn Computer Chess Championship 2005]</ref>
* 2006 – The world champion, [[Vladimir Kramnik]], is defeated 4–2 by [[Deep Fritz]].
* 2009 – [[Pocket Fritz]]. 4 running on a smartphone, wins Copa Mercosur, an International Master level tournament, scoring 9½/10 and earning a performance rating of 2900.<ref name=PF4GM/> A group of pseudonymous Russian programmers release the source code of Ippolit, an engine seemingly stronger than [[Rybka]]. This becomes the basis for the engines Robbolito and Ivanhoe, and many engine authors adopt ideas from it.
* 2010 – Before the [[World Chess Championship 2010]], Topalov prepares by sparring against the supercomputer Blue Gene with 8,192 processors capable of 500 trillion (5 × 10<sup>14</sup>) floating-point operations per second.<ref>{{cite web|url=http://www.chessbase.com/newsdetail.asp?newsid=6361 |title=Challenger uses supercomputer at the world chess championship|date=25 May 2010|publisher=Chessbase }}</ref> Rybka developer, [[Vasik Rajlich]], accuses Ippolit of being a clone of Rybka.
* 2011 – The ICGA strips Rybka of its WCCC titles.<ref>{{cite web |url=http://www.chessvibes.com/reports/rybka-disqualified-and-banned-from-world-computer-chess-championships/ |title= Rybka disqualified and banned from World Computer Chess Championships | ChessVibes|website=www.chessvibes.com |archive-url=https://web.archive.org/web/20140330145657/http://www.chessvibes.com/reports/rybka-disqualified-and-banned-from-world-computer-chess-championships/ |archive-date=30 March 2014}}</ref><ref name=AGMoJiCCpo>{{cite news|last=Riis|first=Dr. Søren|title=A Gross Miscarriage of Justice in Computer Chess (part one)|url=http://www.chessbase.com/newsdetail.asp?newsid=7791|access-date=19 February 2012|newspaper=Chessbase News|date=2 January 2012}}</ref>
* 2017 – [[AlphaZero]], a neural net-based digital automaton, beats [[Stockfish (chess)|Stockfish]] 28–0, with 72 draws, in a 100-game match.
* 2018 - [[Efficiently updatable neural network]] (NNUE) evaluation is invented for [[computer shogi]].<ref>[[Yu Nasu]] (2018). ''ƎUИИ Efficiently Updatable Neural-Network based Evaluation Functions for Computer Shogi''. Ziosoft Computer Shogi Club, [https://github.com/ynasu87/nnue/blob/master/docs/nnue.pdf pdf] (Japanese with English abstract)</ref>
* 2019 – [[Leela Chess Zero]] (LCZero v0.21.1-nT40.T8.610), a chess engine based on AlphaZero, defeats [[Stockfish (chess)|Stockfish]] 19050918 in a 100-game match with the final score 53.5 to 46.5 to win [[Top Chess Engine Championship|TCEC]] season 15.<ref>https://cd.tcecbeta.club/archive.html?season=15&div=sf&game=1 TCEC season 15</ref>
* 2020 - NNUE is added to [[Stockfish (chess)|Stockfish]] evaluation, noticeably increasing its strength.<ref name="Introducing NNUE Evaluation"/><ref name="Joost VandeVondele"/>
== Categorizations ==
=== Dedicated hardware ===
These chess playing systems include custom hardware with approx. dates of introduction (excluding dedicated microcomputers):
* [[Belle (chess machine)|Belle]] 1976
* Bebe, a strong [[bit-slice processor]] 1980
* [[HiTech]] 1985
* [[ChipTest]] 1985
* [[Deep Thought (chess computer)|Deep Thought]] 1987
* Deep Thought 2 (Deep Blue prototype)~1994
* [[IBM Deep Blue|Deep Blue]] 1996, 1997
* [[Hydra (chess)|Hydra]], predecessor was called Brutus 2002
* [[AlphaZero]] 2017 (used Google's [[Tensor Processing Unit]]s for neural networks, but the hardware is not specific to Chess or games)
** [[MuZero]] 2019 (similar hardware to its predecessor AlphaZero, non-specific to Chess or e.g. Go), learns the rules of Chess
=== Commercial dedicated computers ===
[[File:Boris Diplomat Electronic Chess Computer by Chafitz, Inc., Rockville, Maryland, Model Bd-1, Red LED Display, Made in U.S.A., Circa 1979 (Electronic Chess Computer).jpg|thumb|Boris Diplomat (1979) travel chess computer]]
[[File:Fidelity Chess Challenger Voice.jpg|thumb|Fidelity Voice Chess Challenger (1979), the first talking chess computer]]
[[File:Fidelity Chess Challenger Voice speech output.flac|thumb|Speech output from Voice Chess Challenger]]
[[File:Chess computers at the Computer History Museum.jpg|thumb|Milton Bradley Grandmaster (1983), the first commercial self-moving chess computer]]
[[File:Novag Super Constellation, 2.jpg|thumb|Novag Super Constellation (1984), known for its human-like playing style]]
[[File:DGT Centaur 4.jpg|thumb|DGT Centaur (2019), a modern chess computer based on [[Stockfish (chess)|Stockfish]] running on a [[Raspberry Pi]]]]
In the late 1970s to early 1990s, there was a competitive market for dedicated chess computers. This market changed in the mid-1990s when computers with dedicated processors could no longer compete with the fast processors in personal computers.
* Boris in 1977 and Boris Diplomat in 1979, chess computers including pieces and board, sold by Applied Concepts Inc.
* Chess Challenger, a line of chess computers sold by Fidelity Electronics from 1977 to 1992.<ref>{{cite web|url=http://www.ismenio.com/chess_cc1.html|title=Fidelity Chess Challenger 1 – World's First Chess Computer|first=Ismenio|last=Sousa|access-date=25 September 2016}}</ref> These models won the first four [[World Microcomputer Chess Championship]]s.{{citation needed|date=June 2017}}
* [[ChessMachine]], an [[ARM architecture|ARM]]-based dedicated computer, which could run two engines:
** "The King", which later became the [[Chessmaster]] engine, was also used in the TASC R30 dedicated computer.
** Gideon, a version of [[REBEL (chess)|Rebel]], in 1992 became the first microcomputer to win the [[World Computer Chess Championship]].<ref>{{Cite journal|url=https://research.tilburguniversity.edu/en/publications/the-7th-world-computer-chess-championship-report-on-the-tournamen|title=The 7th World Computer-Chess Championship: Report on the tournament, Madrid, Spain, November 23-27, 1992|journal=ICCA Journal|year=1992|volume=15|issue=4|pages=208–209|last1=van den Herik|first1=H.J.|last2=Herschberg|first2=I. S.}}</ref>
* Excalibur Electronics sells a line of beginner strength units.
* [[Mephisto (chess computer)|Mephisto]], a line of chess computers sold by Hegener & Glaser. The units won six consecutive [[World Microcomputer Chess Championship]]s.{{citation needed|date=June 2017}}
* Novag sold a line of tactically strong computers, including the Constellation, Sapphire, and Star Diamond brands.
* Phoenix Chess Systems makes limited edition units based around [[StrongARM]] and [[XScale]] processors running modern engines and emulating classic engines.
* [[Saitek]] sells mid-range units of intermediate strength. They bought out Hegener & Glaser and its Mephisto brand in 1994.
Recently, some hobbyists have been using the [[Multi Emulator Super System]] to run the chess programs created for Fidelity or Hegener & Glaser's Mephisto computers on modern 64-bit operating systems such as [[Windows 10]].<ref>{{cite web|url=http://rebel13.nl/rebel13/rebel%2013.html |title=Download | Home of the Dutch Rebel |publisher=Rebel13.nl |date= |accessdate=2022-08-31}}</ref> The author of [[REBEL (chess)|Rebel]], Ed Schröder has also adapted three of the Hegener & Glaser Mephisto's he wrote to work as UCI engines.<ref>{{cite web|url=http://rebel13.nl/dedicated/dedicated%20as%20uci.html |title=Dedicated as UCI | Home of the Dutch Rebel |publisher=Rebel13.nl |date= |accessdate=2022-08-31}}</ref>
=== DOS programs ===
These programs can be run on MS-DOS, and can be run on 64-bit Windows 10 via emulators such as [[DOSBox]] or [[Qemu]]:<ref>{{cite web |url=http://rebel13.nl/download/more%20dos%20oldies.html |title=More DOS oldies |access-date=2018-12-02 |archive-date=2018-12-03 |archive-url=https://web.archive.org/web/20181203055650/http://rebel13.nl/download/more%20dos%20oldies.html |url-status=dead }}</ref>
* [[Chessmaster 2000]]
* [[Colossus Chess]]
* [[Fritz (chess)|Fritz]] 1–3
* [[Kasparov's Gambit]]
* [[REBEL (chess)|Rebel]]
* [[Sargon (chess)|Sargon]]
* [[Socrates II]]
== Notable theorists ==
Well-known computer chess theorists include:
* [[Georgy Adelson-Velsky]], a Soviet and Israeli mathematician and computer scientist
* [[Hans Berliner]], American computer scientist and world correspondence chess champion, design supervisor of HiTech (1988)
* [[Mikhail Botvinnik]], Soviet electrical engineer and world chess champion, wrote ''Pioneer''
* [[Alexander Brudno]], Russian computer scientist, first elaborated the alphabeta pruning algorithm
* [[Feng-hsiung Hsu]], the lead developer of [[Deep Blue (chess computer)|Deep Blue]] (1986–97)
* Professor [[Robert Hyatt]] developed [[Cray Blitz]] and [[Crafty]]<ref>{{cite web|url=http://www.cis.uab.edu/info/faculty/hyatt/hyatt.html |title=Dr. Robert Hyatt's home page |publisher=Cis.uab.edu |date=2004-02-01 |access-date=2010-04-03}}</ref>
* [[Danny Kopec]], American Professor or Computer Science and International Chess Master, developed Kopec-Bratko test
* [[Alexander Kronrod]], Soviet computer scientist and mathematician
* Professor [[Monroe Newborn]], chairman of the computer chess committee for the Association for Computing Machinery
* [[Claude E. Shannon]], American computer scientist and mathematician
* [[Alan Turing]], English computer scientist and mathematician
== Solving chess ==
{{Main|Solving chess}}
The prospects of completely [[solved game|solving]] chess are generally considered to be rather remote. It is widely conjectured that no computationally inexpensive method to solve chess exists even in the 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 search]]er 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 at least 10<sup>43</sup><ref name="Shannon1950">The size of the state space and game tree for chess were first estimated in {{Citation | author = [[Claude Shannon]] | title = Programming a Computer for Playing Chess | journal = Philosophical Magazine | volume = 41 | issue = 314 | year = 1950 | url = http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf | access-date = 30 December 2008 | url-status = dead | archive-url = https://web.archive.org/web/20100706211229/http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf | archive-date = 6 July 2010 }} Shannon gave estimates of 10<sup>43</sup> and 10<sup>120</sup> respectively, smaller than the estimates in the [[Game complexity]] table, which are from [[Victor Allis]]'s thesis. See [[Shannon number]] for details.</ref> to 10<sup>47</sup>), 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]],<ref>{{Citation |author1=Aviezri Fraenkel |author2=D. Lichtenstein | title = Computing a perfect strategy for n×n chess requires time exponential in n | journal = J. Combin. Theory Ser. A | volume = 31 | year = 1981 | pages = 199–214 | doi = 10.1016/0097-3165(81)90016-9 | issue = 2| doi-access = }}</ref> 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.
[[Martin Gardner]]'s [[Minichess]], played on a 5×5 board with approximately 10<sup>18</sup> possible board positions, has been solved; its game-theoretic value is 1/2 (i.e. a draw can be forced by either side), and the forcing strategy to achieve that result has been described.
Progress has also been made from the other side: as of 2012, all 7 and fewer pieces (2 kings and up to 5 other pieces) endgames have been solved.
== Chess engines ==
{{Main|Chess engine}}
A "chess engine" is software that calculates and orders which moves are the strongest to play in a given position. Engine authors focus on improving the play of their engines, often just importing the engine into a [[graphical user interface]] (GUI) developed by someone else. Engines communicate with the GUI by standardized protocols such as the nowadays ubiquitous [[Universal Chess Interface]] developed by [[Stefan Meyer-Kahlen]] and Franz Huber. There are others, like the Chess Engine Communication Protocol developed by Tim Mann for [[GNU Chess]] and [[Winboard]]. [[Chessbase]] has its own proprietary protocol, and at one time Millennium 2000 had another protocol used for [[ChessGenius]]. Engines designed for one operating system and protocol may be ported to other OS's or protocols.
Chess engines are regularly matched against each other at dedicated [[chess engine#Tournaments|chess engine tournaments]].
== Chess web apps ==
In 1997, the [[Internet Chess Club]] released its first Java client for playing chess online against other people inside one's webbrowser.<ref>{{cite web |url=http://www.chessclub.com/CoffeeHouse.html |title=CoffeeHouse: The Internet Chess Club Java Interface |access-date=2019-07-08 |archive-url=https://web.archive.org/web/19970620110903/http://www.chessclub.com/CoffeeHouse.html |archive-date=1997-06-20 |url-status=dead }}</ref> This was probably one of the first chess web apps. [[Free Internet Chess Server]] followed soon after with a similar client.<ref>{{cite web |url=http://www.freechess.org/ |title=FICS - Free Internet Chess Server |access-date=2019-07-08 |archive-url=https://web.archive.org/web/19981212025054/http://www.freechess.org/ |archive-date=1998-12-12 |url-status=live }}</ref> In 2004, [[International Correspondence Chess Federation]] opened up a web server to replace their email-based system.<ref>{{cite web |url=http://www.iccf-webchess.com/ |title=Archived copy |access-date=2004-08-31 |archive-url=https://web.archive.org/web/20040831025215/http://www.iccf-webchess.com/ |archive-date=2004-08-31 |url-status=live }}</ref> [[Chess.com]] started offering Live Chess in 2007.<ref>{{cite web|url=http://www.chess.com/echess/|archive-url = https://web.archive.org/web/20071006143047/http://www.chess.com/echess/|archive-date = 2007-10-06|title = Play Daily (Correspondence) Chess}}</ref> [[Chessbase]]/[[Playchess]] has long had a downloadable client, and added a web-based client in 2013.<ref>{{cite web |url=http://play.chessbase.com/js/apps/playchess/ |title=Play Chess Online for Free |website=play.chessbase.com |access-date=11 January 2022 |archive-url=https://web.archive.org/web/20131217045511/http://play.chessbase.com/js/apps/playchess/ |archive-date=17 December 2013 |url-status=dead}}</ref>
Another popular web app is tactics training. The now defunct Chess Tactics Server opened its site in 2006,<ref>{{cite web |url=http://chess.emrald.net/ |title=Chess Tactics Server |access-date=2006-04-08 |archive-url=https://web.archive.org/web/20060408052731/http://chess.emrald.net/ |archive-date=2006-04-08 |url-status=dead }}</ref> followed by Chesstempo the next year,<ref>{{cite web |url=http://chesstempo.com/ |title=Chess Tactics |access-date=2007-06-13 |archive-url=https://web.archive.org/web/20070613100847/http://chesstempo.com/ |archive-date=2007-06-13 |url-status=live }}</ref> and [[Chess.com]] added its Tactics Trainer in 2008.<ref>{{cite web |url=http://www.chess.com/tactics |title=Chess Puzzles - Improve Your Chess by Solving Tactics |access-date=2008-02-18 |archive-url=https://web.archive.org/web/20080218082614/http://www.chess.com/tactics |archive-date=2008-02-18 |url-status=live }}</ref> [[Chessbase]] added a tactics trainer web app in 2015.<ref>{{cite web|url=http://training.chessbase.com/js/apps/Training/|archive-url=https://web.archive.org/web/20150504000924/http://training.chessbase.com/js/apps/Training/|archive-date=2015-05-04|title=Chess Tactics Online}}</ref>
[[Chessbase]] took their chess game database online in 1998.<ref>{{cite web |url=http://www.chessbase-online.com/ |title=Chessbase Online, Searching a high quality database of Chessgames. Free Chess Games.ChessBase-Online |website=www.chessbase-online.com |access-date=11 January 2022 |archive-url=https://web.archive.org/web/20000511014758/http://www.chessbase-online.com/ |archive-date=11 May 2000 |url-status=dead}}</ref> Another early chess game databases was Chess Lab, which started in 1999.<ref>{{cite web |url=http://www.chesslab.com/PositionSearch.html |title=Java chess games: Database search, analysis |access-date=2019-07-08 |archive-url=https://web.archive.org/web/19990219143550/http://www.chesslab.com/PositionSearch.html |archive-date=1999-02-19 |url-status=live }}</ref> [[New In Chess]] had initially tried to compete with [[Chessbase]] by releasing a NICBase program for [[Windows 3.x]], but eventually, decided to give up on software, and instead focus on their online database starting in 2002.<ref>{{cite web |url=http://www31.ws26.temphost.nl/NICBase/ |title=NICBase Online |access-date=2002-10-08 |archive-url=https://web.archive.org/web/20021008054123/http://www31.ws26.temphost.nl/NICBase/ |archive-date=2002-10-08 |url-status=live }}</ref>
One could play against the engine [[Shredder (chess)|Shredder]] online from 2006.<ref>{{cite web |url=http://www.shredderchess.com/play-chess-online.html |title=Play Chess Online - Shredder Chess |access-date=2006-12-05 |archive-url=https://web.archive.org/web/20061205205401/http://www.shredderchess.com/play-chess-online.html |archive-date=2006-12-05 |url-status=live }}</ref> In 2015, [[Chessbase]] added a play Fritz web app,<ref>{{cite web |url=http://fritz.chessbase.com/ |title=Home |website=fritz.chessbase.com}}</ref> as well as My Games for storing one's games.<ref>{{cite web |url=http://mygames.chessbase.com/ |title=Home |website=mygames.chessbase.com}}</ref>
Starting in 2007, [[Chess.com]] offered the content of the training program, Chess Mentor, to their customers online.<ref>{{cite web |url=http://www.chess.com/chessmentor/ |title=Chess Lessons - Learn with Online Courses |access-date=2007-12-14 |archive-url=https://web.archive.org/web/20071214214334/http://www.chess.com/chessmentor/ |archive-date=2007-12-14 |url-status=live }}</ref> Top GMs such as [[Sam Shankland]] and [[Walter Browne]] have contributed lessons.
== See also ==
* [[List of chess software]]
* [[History of chess engines]]
* [[Computer checkers]]
* [[Computer Go]]
* [[Computer Othello]]
* [[Computer shogi]]
==Notes==
{{reflist|group=Note|refs=
<ref name=Note1>The first number refers to the number of moves which must be made by each engine, the second number refers to the number of minutes allocated to make all of these moves. The repeating time control means that the time is reset after each multiple of this number of moves is reached. For example, in a 40/4 time control, each [[chess engine|engine]] would have 4 minutes to make 40 moves, then a new 4 minutes would be allocated for the next 40 moves and so on, until the game was complete.</ref>
}}
== References ==
{{reflist|colwidth=30em}}
{{Creative Commons text attribution notice|cc=bysa3|url=https://www.chessprogramming.org/index.php?title=Mikhail_Botvinnik&action=history|author(s)=Chess Programming Wiki}}
==Sources==
*{{Citation
|last=Hsu|first=Feng-hsiung|author-link=Feng-hsiung Hsu
|year=2002
|title=Behind Deep Blue: Building the Computer that Defeated the World Chess Champion
|publisher=[[Princeton University Press]]
|isbn=0-691-09065-3}}
*{{Citation
|surname1=Levy|given1=David|author-link1=David Levy (chess player)
|surname2=Newborn|given2=Monty
|year=1991
|title=How Computers Play Chess
|publisher=Computer Science Press
|isbn=0-7167-8121-2}}
* {{Citation|surname=Newborn|given=Monty|title=Computer Chess|publisher=Academic Press, New York|year=1975}}
*{{Citation
|last=Newborn|first=Monty
|year=1997
|title=Kasparov versus Deep Blue: Computer Chess Comes of Age
|publisher=Springer
|isbn=0-387-94820-1}} (This book actually covers computer chess from the early days through the first match between Deep Blue and Garry Kasparov.)
*{{Citation
|surname1=Nunn|given1=John|author-link1=John Nunn
|year=2002
|title=Secrets of Pawnless Endings
|publisher=[[Gambit Publications]]
|isbn=1-901983-65-X}}
*{{Citation|surname=Shannon|given=Claude E.|author-link=Claude Elwood Shannon|year=1950|title=Programming a Computer for Playing Chess|journal=Philosophical Magazine|volume=Ser.7, Vol. 41|issue=314|url=http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf|access-date=21 June 2009|url-status=dead|archive-url=https://web.archive.org/web/20100706211229/http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf|archive-date=6 July 2010}}
*[http://www.computerhistory.org/chess/ Mastering the Game: A History of Computer Chess] at [http://www.computerhistory.org/ Computer History Museum]
* [https://web.archive.org/web/20091028083247/http://www.geocities.com/SiliconValley/Lab/7378/comphis.htm Bill Wall's Computer Chess History Timeline]
==Further reading==
*[http://www.loopchess.com/fritz_reul_thesis_revision_1.pdf New Architectures in Computer Chess – Thesis on How to Build A Chess Engine]
*{{Citation|last=Coles|first=L. Stephen|title=Computer Chess: The Drosophila of AI|date=October 30, 2002|publisher=[[Dr. Dobb's Journal]]|url=http://www.ddj.com/hpc-high-performance-computing/184405171}}
*{{Citation
|last=Huberman (Liskov)|first=Barbara Jane|title=A program to play chess end games|year=1968|publisher=Stanford University Department of Computer Science, Technical Report CS 106, Stanford Artificial Intelligence Project Memo AI-65|author-link=Barbara Liskov}}
* Lasar, Matthew (2011). [https://arstechnica.com/gaming/news/2011/08/force-versus-heuristics-the-contentious-rise-of-computer-chess.ars Brute force or intelligence? The slow rise of computer chess]". ''[[Ars Technica]]''.
* 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). [http://www.cs.mcgill.ca/~newborn/TheoOctopusAtCasc06.pdf ''Theo and Octopus at the 2006 World Championship for Automated Reasoning Programs''], Seattle, Washington, August 18, 2006
*{{Citation|last=Stiller|first=Lewis|title=Multilinear Algebra and Chess Endgames|publisher=[[Mathematical Sciences Research Institute]], Games of No Chance, MSRI Publications, Volume 29|year=1996|location=Berkeley, California|url=http://www.msri.org/publications/books/Book29/files/stiller.pdf|access-date=21 June 2009}}
== External links ==
{{Wiktionary}}
{{Commons category|Computer chess}}
* [http://www.computerchess.org.uk/ccrl/4040/ List of chess engine ratings and game files in PGN format]
* [http://www.computerhistory.org/chess/ Mastering the Game: A History of Computer Chess] at the [[Computer History Museum]]
* [http://ed-thelen.org/comp-hist/ACM-ComputerChessWall.html ACM Computer Chess by Bill Wall]
* [https://www.chesshistory.com/winter/extra/computers.html "Computer Chess" by Edward Winter]
* [http://www.chessbin.com Computer Chess Information and Resources] {{Webarchive|url=https://web.archive.org/web/20190118031801/http://www.chessbin.com/ |date=2019-01-18 }} – blog following the creation of a computer chess engine
* [http://www.xs4all.nl/~timkr/chess2/honor.htm Defending Humanity's Honor], an article by [[Tim Krabbé]] about "anti-computer style" chess
* [http://horizonchess.com/FAQ/Winboard/egtb.html A guide to Endgame Tablebases]
* GameDev.net – Chess Programming by François-Dominic Laramée Part [http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-i-getting-started-r1014 1] {{Webarchive|url=https://web.archive.org/web/20110918175142/http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-i-getting-started-r1014 |date=2011-09-18 }} [http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-ii-data-structures-r1046 2] {{Webarchive|url=https://web.archive.org/web/20110927174532/http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-ii-data-structures-r1046 |date=2011-09-27 }} [http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-iii-move-generation-r1126 3] {{Webarchive|url=https://web.archive.org/web/20110919031614/http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-iii-move-generation-r1126 |date=2011-09-19 }} [http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-iv-basic-search-r1171 4] {{Webarchive|url=https://web.archive.org/web/20110919072227/http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-iv-basic-search-r1171 |date=2011-09-19 }} [http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-v-advanced-search-r1197 5] {{Webarchive|url=https://web.archive.org/web/20110920045740/http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-v-advanced-search-r1197 |date=2011-09-20 }} [http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-vi-evaluation-functions-r1208 6] {{Webarchive|url=https://web.archive.org/web/20110807031136/http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-vi-evaluation-functions-r1208 |date=2011-08-07 }}
* [http://www.frayn.net/beowulf/theory.html Colin Frayn's Computer Chess Theory Page]
* {{cite web|url= http://members.home.nl/matador/Inside%20Rebel.pdf |title="How REBEL Plays Chess" by Ed Schröder }} {{small|(268 KB)}}
* [http://plan9.bell-labs.com/~ken/chesseg.html "Play chess with God"] {{Webarchive|url=https://archive.today/20121129222242/http://plan9.bell-labs.com/~ken/chesseg.html |date=2012-11-29 }} – for playing chess against Ken Thompson's endgame database
* [http://www.chessprogramming.org Chess programming wiki]
* [http://talkchess.com/forum/index.php Computer Chess Club Forums]
* [http://www.youtube.com/watch?v=wljgxS7tZVE The Strongest Computer Chess Engines Over Time]
=== Media ===
*[http://video.google.com/videoplay?docid=-1583888480148765375 The History of Computer Chess: An AI Perspective] {{Webarchive|url=https://web.archive.org/web/20060614024002/http://video.google.com/videoplay?docid=-1583888480148765375 |date=2006-06-14 }} – a full lecture featuring Murray Campbell (IBM Deep Blue Project), Edward Feigenbaum, [[David Levy (chess)|David Levy]], John McCarthy, and Monty Newborn. at [http://www.computerhistory.org/ Computer History Museum]
{{Chess}}
{{Authority control}}
[[Category:Computer chess| ]]
[[Category:Electronic games]]
[[Category:Game artificial intelligence]]' |
New page wikitext, after the edit (new_wikitext) | '{{Short description|Computer hardware and software capable of playing chess}}
{{about||the 2013 film|Computer Chess (film)|chess played over the Internet|Online chess}}
[[Image:RS Chess Computer.JPG|thumb|1990s pressure-sensory chess computer with LCD screen]]
{{Chess programming series}}
'''Computer chess''' includes both hardware (dedicated computers) and [[software]] capable of playing [[chess]]. Computer chess provides opportunities for players to practice even in the absence of human opponents, and also provides opportunities for analysis, entertainment and training. Computer chess applications that play at the level of a [[Chess title|chess grandmaster]] or higher are available on hardware from [[supercomputer]]s to [[Smartphone|smart phones]]. Standalone chess-playing machines are also available. [[Stockfish (chess)|Stockfish]], [[Leela Chess Zero]], [[GNU Chess]], [[Fruit (software)|Fruit]], and other free open source applications are available for various platforms.
Computer chess applications, whether implemented in hardware or software, utilize different strategies than humans to choose their moves: they use [[Heuristic (computer science)|heuristic methods]] to build, search and evaluate [[Tree (data structure)|trees]] representing sequences of moves from the current position and attempt to execute the best such sequence during play. Such trees are typically quite large, thousands to millions of nodes. The computational speed of modern computers, capable of processing tens of thousands to hundreds of thousands of nodes or more per second, along with extension and reduction heuristics that narrow the tree to mostly relevant nodes, make such an approach effective.
The first chess machines capable of playing chess or reduced chess-like games were software programs running on digital computers early in the [[vacuum-tube computer]] age (1950s). The early programs played so poorly that even a beginner could defeat them. Within 40 years, in 1997, [[chess engine]]s running on super-computers or specialized hardware were capable of [[Deep Blue versus Garry Kasparov|defeating even the best human players]]. By 2006, [[Human–computer chess matches|programs running on desktop PCs]] had attained the same capability. In 2006, [[Monty Newborn]], Professor of Computer Science at [[McGill University]], declared: "the science has been done". Nevertheless, [[solving chess]] is not currently possible for modern computers due to the [[Game complexity|game's extremely large number of possible variations]].<ref>{{cite web |last1=Sreedhar |first1=Suhas |title=Checkers, Solved! |url=https://spectrum.ieee.org/computing/software/checkers-solved |website=IEEE Spectrum |date=2 July 2007 |publisher=Institute of Electrical and Electronics Engineers}}</ref>
Computer chess was once considered the "[[Drosophila]] of AI", the edge of [[knowledge engineering]]. The field is now considered a scientifically completed paradigm, and playing chess is a mundane computing activity.<ref>{{Cite journal|url=https://pubmed.ncbi.nlm.nih.gov/22530382/|pmid = 22530382|year = 2012|last1 = Ensmenger|first1 = N.|title = Is chess the drosophila of artificial intelligence? A social history of an algorithm|journal = Social Studies of Science|volume = 42|issue = 1|pages = 5–30|doi = 10.1177/0306312711424596|s2cid = 968033}}</ref>
== Availability and playing strength ==
[[File:Frans Morsch name on the ICs.jpg|thumb|Computer chess IC bearing the name of developer Frans Morsch (see [[Mephisto (chess computer)|Mephisto]])]]
Chess machines/programs are available in several different forms: stand-alone chess machines (usually a microprocessor running a software chess program, but sometimes as a specialized hardware machine), software programs running on standard PCs, web sites, and apps for mobile devices. Programs run on everything from super-computers to smartphones. Hardware requirements for programs are minimal; the apps are no larger than a few megabytes on disk, use a few megabytes of memory (but can use much more, if it is available), and any processor 300Mhz or faster is sufficient. Performance will vary modestly with processor speed, but sufficient memory to hold a large [[transposition table]] (up to several gigabytes or more) is more important to playing strength than processor speed.
Most available commercial chess programs and machines can play at super-grandmaster strength (Elo 2700 or more), and take advantage of multi-core and hyperthreaded computer CPU architectures. Top programs such as [[Stockfish (chess)|Stockfish]] have surpassed even world champion caliber players. Most chess programs comprise a chess engine connected to a GUI, such as [[Winboard]] or [[Chessbase]]. Playing strength, time controls, and other performance-related settings are adjustable from the GUI. Most GUIs also allow the player to set up and to edit positions, to reverse moves, to offer and to accept draws (and resign), to request and to receive move recommendations, and to show the engine's analysis as the game progresses.
There are thousands of [[chess engine]]s such as [[Sargon (chess)|Sargon]], [[IPPOLIT]], [[Stockfish (chess)|Stockfish]], [[Crafty]], [[Fruit (chess engine)|Fruit]], [[Leela Chess Zero]] and [[GNU Chess]] which can be downloaded (or source code otherwise obtained) from the [[Internet]] free of charge.
== Types and features of chess software ==
Perhaps the most common type of chess software are programs that simply play chess. A human player makes a move on the board, the AI calculates and plays a subsequent move, and the human and AI alternate turns until the game ends. The [[chess engine]], which calculates the moves, and the [[graphical user interface]] (GUI) are sometimes separate programs. Different engines can be connected to the GUI, permitting play against different styles of opponent. Engines often have a simple text [[command-line interface]], while GUIs may offer a variety of piece sets, board styles, or even 3D or animated pieces. Because recent engines are so capable, engines or GUIs may offer some way of handicapping the engine's ability, to improve the odds for a win by the human player. [[Universal Chess Interface]] (UCI) engines such [[Fritz (chess)|Fritz]] or [[Rybka]] may have a built in mechanism for reducing the [[Elo rating]] of the engine (via UCI's uci_limitstrength and uci_elo parameters). Some versions of [[Fritz (chess)|Fritz]] have a Handicap and Fun mode for limiting the current engine or changing the percentage of mistakes it makes or changing its style. [[Fritz (chess)|Fritz]] also has a Friend Mode where during the game it tries to match the level of the player.
[[File:Chess screenshot.png|thumb|Screenshot of [[List of macOS components#Chess|Chess]], a component of [[macOS]]]]
Chess databases allow users to search through a large library of historical games, analyze them, check statistics, and formulate an opening repertoire. [[Chessbase]] (for PC) is a common program for these purposes amongst professional players, but there are alternatives such as [[Shane's Chess Information Database]] (Scid) <ref>[http://scid.sourceforge.net/ http://scid.sourceforge.net] SCID.</ref> for Windows, Mac or Linux, [[Chess Assistant]]<ref>{{cite web |url=http://www.convekta.com/about.asp |title= Chess Assistant Chess Website:: About Us|website=www.convekta.com |archive-url=https://web.archive.org/web/20080820180940/http://www.convekta.com/about.asp |archive-date=August 20, 2008}}</ref> for PC,<ref>[http://www.exachess.com/ http://www.exachess.com] ExaChess for Mac</ref> Gerhard Kalab's Chess PGN Master for Android<ref>{{cite web|url=http://kalab.com/pgnviewer/|title=Chess PGN Master}}</ref> or Giordano Vicoli's Chess-Studio for iOS.<ref>https://www.facebook.com/chessstudioapp/ {{User-generated source|certain=yes|date=March 2022}}</ref>
Programs such as [[Playchess]] allow players to play against one another over the internet.
Chess training programs teach chess. [[Chessmaster]] had playthrough tutorials by IM [[Josh Waitzkin]] and GM [[Larry Christiansen]]. [[Stefan Meyer-Kahlen]] offers [[Shredder (chess)|Shredder]] Chess Tutor based on the Step coursebooks of Rob Brunia and Cor Van Wijgerden. Former [[World Chess Championship|World Champion]] [[Magnus Carlsen]]'s [[Play Magnus Group|Play Magnus company]] released a [[Play Magnus (mobile app)|Magnus Trainer app]] for Android and iOS. [[Chessbase]] has [[Fritz and Chesster]] for children. Convekta provides a large number of training apps such as CT-ART and its Chess King line based on tutorials by GM Alexander Kalinin and Maxim Blokh.
There is also [[software for handling chess problems]].
== Computers versus humans ==
{{Main|Human–computer chess matches}}
After discovering refutation screening—the application of [[alpha–beta pruning]] to optimizing move evaluation—in 1957, a team at [[Carnegie Mellon University]] predicted that a computer would defeat the world human champion by 1967.<ref>{{cite journal|last1=Simon|first1=H.A.|last2=Newell|first2=A.|title=Heuristic problem solving: The next advance in operations research|journal=Operations Research|date=1958|volume=6|issue=1|page=7|doi=10.1287/opre.6.1.1|url=https://home.mis.u-picardie.fr/~furst/docs/Newell_Simon_Heuristic_Problem_Solving_1958.pdf|access-date=10 February 2018}}</ref> It did not anticipate the difficulty of determining the right order to evaluate moves. Researchers worked to improve programs' ability to identify [[killer heuristic]]s, unusually high-scoring moves to reexamine when evaluating other branches, but into the 1970s most top chess players believed that computers would not soon be able to play at a [[Senior Master (chess)|Master]] level.{{r|hapgood19821223_30}} In 1968, [[International Master]] [[Computer chess bet|David Levy made a famous bet]] that no chess computer would be able to beat him within ten years,{{r|douglas197812}} and in 1976 [[Senior Master (chess)|Senior Master]] and professor of psychology [[Eliot Hearst]] of [[Indiana University]] wrote that "the only way a current computer program could ever win a single game against a master player would be for the master, perhaps in a drunken stupor while playing 50 games simultaneously, to commit some once-in-a-year blunder".{{r|hapgood19821223_30}}
In the late 1970s chess programs suddenly began defeating highly skilled human players.{{r|hapgood19821223_30}} The year of Hearst's statement, [[Northwestern University]]'s [[Chess 4.5]] at the [[Paul Masson]] American Chess Championship's [[Chess title#Expert|Class B]] level became the first to win a human tournament. Levy won his bet in 1978 by beating [[Chess 4.7]], but it achieved the first computer victory against a Master-class player at the tournament level by winning one of the six games.<ref name="douglas197812">{{cite news | url=https://archive.org/stream/byte-magazine-1978-12/1978_12_BYTE_03-12_Life#page/n85/mode/2up | title=Chess 4.7 versus David Levy | work=BYTE | date=December 1978 | access-date=17 October 2013 | author=Douglas, J R | page=84}}</ref> In 1980, [[Belle (chess machine)|Belle]] began often defeating Masters. By 1982 two programs played at Master level and three were slightly weaker.{{r|hapgood19821223_30}}
The sudden improvement without a theoretical breakthrough was unexpected, as many did not expect that Belle's ability to examine 100,000 positions a second—about eight plies—would be sufficient. The Spracklens, creators of the successful microcomputer program ''[[Sargon (chess)|Sargon]]'', estimated that 90% of the improvement came from faster evaluation speed and only 10% from improved evaluations. ''[[New Scientist]]'' stated in 1982 that computers "play ''terrible'' chess ... clumsy, inefficient, diffuse, and just plain ugly", but humans lost to them by making "horrible blunders, astonishing lapses, incomprehensible oversights, gross miscalculations, and the like" much more often than they realized; "in short, computers win primarily through their ability to find and exploit miscalculations in human initiatives".<ref name="hapgood19821223_30"/>
By 1982, microcomputer chess programs could evaluate up to 1,500 moves a second and were as strong as mainframe chess programs of five years earlier, able to defeat a majority of amateur players. While only able to look ahead one or two plies more than at their debut in the mid-1970s, doing so improved their play more than experts expected; seemingly minor improvements "appear to have allowed the crossing of a psychological threshold, after which a rich harvest of human error becomes accessible", ''New Scientist'' wrote.{{r|hapgood19821223_30}} While reviewing ''SPOC'' in 1984, ''[[BYTE]]'' wrote that "Computers—mainframes, minis, and micros—tend to play ugly, inelegant chess", but noted [[Robert Byrne (chess player)|Robert Byrne]]'s statement that "tactically they are freer from error than the average human player". The magazine described ''SPOC'' as a "state-of-the-art chess program" for the IBM PC with a "surprisingly high" level of play, and estimated its USCF rating as 1700 (Class B).<ref name="byte198403">{{cite news | url=https://archive.org/stream/byte-magazine-1984-03-rescan/1984_03_BYTE_09-03_Simulation#page/n289/mode/2up | title=SPOC / The Chess Master | work=BYTE | date=March 1984 | access-date=8 September 2015 |author1=Flock, Emil |author2=Silverman, Jonathan | pages=288–294}}</ref>
At the 1982 [[North American Computer Chess Championship]], [[Monroe Newborn]] predicted that a chess program could become world champion within five years; tournament director and International Master [[Michael Valvo]] predicted ten years; the Spracklens predicted 15; [[Ken Thompson]] predicted more than 20; and others predicted that it would never happen. The most widely held opinion, however, stated that it would occur around the year 2000.<ref name="stinson198201">{{cite news | url=http://www.cgwmuseum.org/galleries/index.php?year=1982&pub=6&id=3 | title=Chess Championship: Machines Play, People Watch | work=Softline | date=Jan 1982 | access-date=13 July 2014 | author=Stinson, Craig | page=6}}</ref> In 1989, Levy was defeated by [[Deep Thought (chess computer)|Deep Thought]] in an exhibition match. Deep Thought, however, was still considerably below World Championship level, as the reigning world champion, [[Garry Kasparov]], demonstrated in two strong wins in 1989. It was not until a 1996 match with [[International Business Machines|IBM's]] [[IBM Deep Blue|Deep Blue]] that Kasparov lost his first game to a computer at tournament time controls in [[Deep Blue versus Kasparov, 1996, Game 1|Deep Blue versus 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 (chess)|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]]''.
{{Chess diagram
|tright
|[[Deep Blue versus Kasparov, 1996, Game 1|Deep Blue vs. Kasparov, 1996, game 1]]
| | | | | | | |
| | | | | | | |rl
| | | | | |qd| |kd
| | | |ql| | |nl|
| | | |pd| | | |
|pl|pl| | | |pd|pl|pl
| | | | | |nd| |kl
| | | | |rd| | |
|Final position
}}
With increasing processing power and improved evaluation functions, chess programs running on commercially available workstations began to rival top-flight players. In 1998, [[REBEL (chess)|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 chess|blitz]] games (five minutes plus five seconds [[Time control#Chess|Fischer delay]] 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½.<ref>{{cite web|url=http://www.rebel.nl/anand.htm |title=Rebel vs Anand |publisher=Rebel.nl |access-date=2010-04-03}}</ref> 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 (chess)|Junior]] and [[Fritz (chess)|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 [[Chess middlegame|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.{{Citation needed|date=January 2008}}
In January 2003, Kasparov played [[Junior (chess)|Junior]], another chess computer program, in New York City. The match ended 3–3.
In November 2003, Kasparov played [[X3D Fritz]]. The match ended 2–2.
In 2005, [[Hydra (chess)|Hydra]], a dedicated chess computer with custom hardware and sixty-four processors and also winner of the 14th [[International Paderborn Computer Chess Championship|IPCCC]] in 2005, defeated seventh-ranked [[Michael Adams (chess player)|Michael Adams]] 5½–½ in a six-game match (though Adams' preparation was far less thorough than Kramnik's for the 2002 series).<ref>{{cite web|url=http://www.chessbase.com/newsdetail.asp?newsid=2476 |title=Chess News – Adams vs Hydra: Man 0.5 – Machine 5.5 |date=28 June 2005 |publisher=ChessBase.com |access-date=2010-04-03}}</ref>
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 ([[Blunder of the century|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.<ref>[https://www.nytimes.com/2006/12/05/crosswords/chess/05cnd-chess.html Once Again, Machine Beats Human Champion at Chess] New York Times, December 5, 2006</ref> According to Newborn, for example, "the science is done".<ref>{{cite news| url=https://www.nytimes.com/2006/12/05/crosswords/chess/05cnd-chess.html | work=The New York Times | title=Once Again, Machine Beats Human Champion at Chess | date=5 December 2006 | access-date=30 April 2010}}</ref>
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.<ref>[http://www.ddj.com/hpc-high-performance-computing/184405171 Computer Chess: The Drosophila of AI] October 30, 2002</ref> 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, are not directly compared.<ref>[http://www.aaai.org/ojs/index.php/aimagazine/article/viewFile/753/671 Deep Thought wins Fredkin Intermediate Prize], [[Hans Berliner]]</ref> In 2016, the [[Swedish Chess Computer Association]] rated computer program [[Komodo (chess)|Komodo]] at 3361.
[[Chess engine]]s continue to improve. In 2009, chess engines running on slower hardware have reached the [[Grandmaster (chess)|grandmaster]] level. A [[mobile phone]] won a [[category (chess tournament)|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.<ref name=PF4GM>{{cite web|url=https://theweekinchess.com/html/twic771.html#13 |title=Pocket Fritz 4 wins Copa Mercosur |publisher=Chess.co.uk |access-date=2010-04-03 |url-status=dead |archive-url=https://web.archive.org/web/20110930232108/https://theweekinchess.com/html/twic771.html#13 |archive-date=2011-09-30 }}</ref> Pocket Fritz 4 searches fewer than 20,000 positions per second.<ref name=PF420K>Stanislav Tsukrov, Pocket Fritz author. [http://hiarcs.net/forums/viewtopic.php?t=2537&start=67 Pocket Fritz 4 searches less than 20,000 positions per second.]</ref> 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. This has been proven in numerous occasions, such as at Freestyle Chess events.
Players today are inclined to treat chess engines as analysis tools rather than opponents.<ref>{{cite web|url=http://www.dw.com/en/world-chess-champion-magnus-carlsen-the-computer-never-has-been-an-opponent/a-19186058|title=World chess champion Magnus Carlsen: 'The computer never has been an opponent'|publisher=Deutsche Welle|date=16 April 2016|access-date=26 August 2016}}</ref> Chess grandmaster [[Andrew Soltis]] stated in 2016 "The computers are just much too good" and that world champion [[Magnus Carlsen]] won't play computer chess because "he just loses all the time and there's nothing more depressing than losing without even being in the game."<ref name="npr 20 years">{{cite news |title=20 Years Later, Humans Still No Match For Computers On The Chessboard |url=https://www.npr.org/sections/alltechconsidered/2016/10/24/499162905/20-years-later-humans-still-no-match-for-computers-on-the-chessboard |access-date=28 June 2020 |work=NPR.org |date=2016 |language=en}}</ref>
== Computer methods ==
Since the era of mechanical machines that played rook and king endings and electrical machines that played other games like [[hex (board game)|hex]] in the early years of the 20th century, scientists and theoreticians have sought to develop a procedural representation of how humans learn, remember, think and apply knowledge, and the game of chess, because of its daunting complexity, became the "[[Drosophila]] of artificial intelligence (AI)".{{refn|group=Note|What this means is that chess, like the common fruit fly, is a simple and more accessible and familiar paradigm to experiment with technology that can be used to produce knowledge about other, more complex systems.}} The procedural resolution of complexity became synonymous with thinking, and early computers, even before the chess automaton era, were popularly referred to as "electronic brains". Several different schema were devised starting in the latter half of the 20th century to represent knowledge and thinking, as applied to playing the game of chess (and other games like checkers):
* search based (brute force vs selective search)
** Search in search based schema ([[minimax]]/[[Alpha–beta pruning|alpha-beta]], [[Monte Carlo tree search]])
** Evaluations in search based schema ([[machine learning]], [[Artificial neural network|neural networks]], [[Texel (graphics)|texel]] tuning, [[genetic algorithm]]s, [[gradient descent]], [[reinforcement learning]])
* [[Knowledge-based systems|knowledge based]] (PARADISE, [[endgame tablebases]])
Using "ends-and-means" heuristics a human chess player can intuitively determine optimal outcomes and how to achieve them regardless of the number of moves necessary, but a computer must be systematic in its analysis. Most players agree that [[combinatorial search#Lookahead|looking at least five moves ahead]] (ten [[ply (game theory)|plies]]) when necessary is required to play well. Normal tournament rules give each player an average of three minutes per move. On average there are more than 30 legal moves per chess position, so a computer must examine a quadrillion possibilities to look ahead ten plies (five full moves); one that could examine a million positions a second would require more than 30 years.<ref name="hapgood19821223_30">{{cite news | url=https://books.google.com/books?id=_n1vr0_RbXoC&pg=PA827 | title=Computer chess bad-human chess worse | work=New Scientist | date=23–30 December 1982 | access-date=22 January 2015 | author=Hapgood, Fred | pages=827–830 }}{{Dead link|date=December 2023 |bot=InternetArchiveBot |fix-attempted=yes }}</ref>
The earliest attempts at procedural representations of playing chess predated the digital electronic age, but it was the stored program digital computer that gave scope to calculating such complexity. Claude Shannon, in 1949, laid out the principles of algorithmic solution of chess. In that paper, the game is represented by a "tree", or digital data structure of choices (branches) corresponding to moves. The nodes of the tree were positions on the board resulting from the choices of move. The impossibility of representing an entire game of chess by constructing a tree from first move to last was immediately apparent: there are an average of 36 moves per position in chess and an average game lasts about 35 moves to resignation (60-80 moves if played to checkmate, stalemate, or other draw). There are 400 positions possible after the first move by each player, about 200,000 after two moves each, and nearly 120 million after just 3 moves each.
So a limited lookahead (search) to some depth, followed by using domain-specific knowledge to evaluate the resulting terminal positions was proposed. A kind of middle-ground position, given good moves by both sides, would result, and its evaluation would inform the player about the goodness or badness of the moves chosen. Searching and comparing operations on the tree were well suited to computer calculation; the representation of subtle chess knowledge in the evaluation function was not. The early chess programs suffered in both areas: searching the vast tree required computational resources far beyond those available, and what chess knowledge was useful and how it was to be encoded would take decades to discover.
The developers of a chess-playing computer system must decide on a number of fundamental implementation issues. These include:
* [[Graphical user interface]] (GUI) – how moves are entered and communicated to the user, how the game is recorded, how the time controls are set, and other interface considerations
* [[Board representation (chess)|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;
* [[Evaluation function|Leaf evaluation]] – how to evaluate the value of a board position, if no further search will be done from that position.
[[Adriaan de Groot]] interviewed a number of chess players of varying strengths, and concluded that both [[chess master|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 equivalent of this in computer chess are [[evaluation function]]s for leaf evaluation, which correspond to the human players' pattern recognition skills, and the use of machine learning techniques in training them, such as Texel tuning, [[stochastic gradient descent]], and [[reinforcement learning]], which corresponds to building experience in human players. This allows modern programs to examine some lines in much greater depth than others by using forwards pruning and other selective heuristics to simply not consider moves the program assume to be poor through their evaluation function, in the same way that human players do. The only fundamental difference between a computer program and a human in this sense is that a computer program can search much deeper than a human player could, allowing it to search more nodes and bypass the [[horizon effect]] to a much greater extent than is possible with human players.
=== Graphical user interface ===
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 [[algebraic chess notation|long algebraic notation]], but today users expect chess programs to understand standard [[algebraic chess notation]].
Starting in the late 1990s, programmers began to develop separately ''engines'' (with a [[command-line interface]] which calculates which moves are strongest in a position) or a ''[[graphical user interface]]'' (GUI) which provides the player with a chessboard they can see, and pieces that can be moved. Engines communicate their moves to the GUI using a protocol such as the Chess Engine Communication Protocol (CECP) or [[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 [[chess engine]].)
Developers have to decide whether to connect the engine to an opening book and/or endgame [[tablebase]]s or leave this to the GUI.
=== Board representations ===
{{Main|Board representation (chess)}}
The [[data structure]] used to represent each chess position is key to the performance of move generation and [[Punctuation (chess)#Position evaluation symbols|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 coding|huffman coded]] positions for compact long-term storage.
=== Search techniques ===
Computer chess programs consider chess moves as a [[game tree]]. In theory, they examine all moves, then all counter-moves to those moves, then all moves countering them, and so on, where each individual move by one player is called a "[[ply (game theory)|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).
==== Minimax search====
{{further|Alpha–beta pruning|minimax}}
One particular type of search algorithm used in computer chess are [[minimax]] search algorithms, where at each ply the "best" move by the player is selected; one player is trying to maximize the score, the other to minimize it. By this alternating process, one particular terminal node whose evaluation represents the searched value of the position will be arrived at. Its value is backed up to the root, and that evaluation becomes the valuation of the position on the board. This search process is called minimax.
A naive implementation of the minimax algorithm 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. [[Alpha–beta pruning]], a system of defining upper and lower bounds on possible search results and searching until the bounds coincided, is typically used to reduce the search space of the program.
In addition, various selective search heuristics, such as [[quiescence search]], forward pruning, search extensions and search reductions, are also used as well. These heuristics are triggered based on certain conditions in an attempt to weed out obviously bad moves (history moves) or to investigate interesting nodes (e.g. check extensions, [[passed pawn]]s on seventh [[rank (chess)|rank]], etc.). These selective search heuristics 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 or reduced, there is a risk cutting out interesting nodes.
==== Monte Carlo tree search ====
{{further|Monte Carlo tree search}}
Monte Carlo tree search (MCTS) is a heuristic search algorithm which expands the search tree based on random sampling of the search space. A version of Monte Carlo tree search commonly used in computer chess is PUCT, Predictor and Upper Confidence bounds applied to Trees.
DeepMind's [[AlphaZero]] and [[Leela Chess Zero]] uses MCTS instead of minimax. Such engines use [[batch processing|batching]] on [[graphics processing units]] in order to calculate their [[evaluation function]]s and policy (move selection), and therefore require a [[parallel computing|parallel]] search algorithm as calculations on the GPU are inherently parallel. The minimax and alpha-beta pruning algorithms used in computer chess are inherently serial algorithms, so would not work well with batching on the GPU. On the other hand, MCTS is a good alternative, because the random sampling used in Monte Carlo tree search lends itself well to parallel computing, and is why nearly all engines which support calculations on the GPU use MCTS instead of alpha-beta.
==== Other optimizations ====
Many other optimizations can be used to make chess-playing programs stronger. For example, [[transposition table]]s are used to record positions that have been previously evaluated, to save recalculation of them. [[Refutation table]]s 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). The drawback is that transposition tables at deep ply depths can get quite large – tens to hundreds of millions of entries. IBM's Deep Blue transposition table in 1996, for example was 500 million entries. Transposition tables that are too small can result in spending more time searching for non-existent entries due to threshing than the time saved by entries found. Many chess engines use [[pondering]], searching to deeper levels on the opponent's time, similar to human beings, to increase their playing strength.
Of course, faster hardware and additional memory can improve chess program playing strength. Hyperthreaded architectures can improve performance modestly if the program is running on a single core or a small number of cores. Most modern programs are designed to take advantage of multiple cores to do parallel search. Other programs are designed to run on a general purpose computer and allocate move generation, parallel search, or evaluation to dedicated processors or specialized co-processors.
==== History ====
The [[Claude Shannon#Shannon's computer chess program|first paper]] on search was by [[Claude Shannon]] in 1950.<ref name="wheland197810">{{cite news | url=https://archive.org/stream/byte-magazine-1978-10/1978_10_BYTE_03-10_Chess_for_the_Microcomputer#page/n167/mode/2up | title=A Computer Chess Tutorial | work=BYTE | date=October 1978 | access-date=17 October 2013 | author=Wheland, Norman D. | page=168}}</ref> He predicted the two main possible search strategies which would be used, which he labeled "Type A" and "Type B",<ref name="shannon">{{Harvcol|Shannon|1950}}</ref> before anyone had programmed a computer to play chess.
Type A programs would use a "[[brute-force search|brute force]]" approach, examining every possible position for a fixed number of moves using a pure naive [[minimax|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 10<sup>9</sup> positions involved in looking three moves ahead for both sides (six [[Ply (game theory)|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. A later search algorithm called [[alpha–beta pruning]], a system of defining upper and lower bounds on possible search results and searching until the bounds coincided, reduced the branching factor of the game tree logarithmically, but it still was not feasible for chess programs at the time to exploit the exponential explosion of the tree.
Second, it ignored the problem of quiescence, trying to only evaluate a position that is at the end of an [[exchange (chess)|exchange]] of pieces or other important sequence of moves ('lines'). He expected that adapting minimax to cope with this would greatly increase the number of positions needing to be looked at and slow the program down still further. 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.
This led naturally to what is referred to as "selective search" or "type B search", using chess knowledge (heuristics) to select a few presumably good moves from each position to search, and prune away the others without searching. Instead of wasting processing power examining bad or trivial moves, Shannon suggested that type B programs would use two improvements:
# Employ a [[quiescence search]].
# Employ forward pruning; i.e. 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. However, early attempts at selective search often resulted in the best move or moves being pruned away. As a result, little or no progress was made for the next 25 years dominated by this first iteration of the selective search paradigm. The best program produced in this early period was Mac Hack VI in 1967; it played at the about the same level as the average amateur (C class on the United States Chess Federation rating scale).
Meanwhile, hardware continued to improve, and in 1974, brute force searching was implemented for the first time in the Northwestern University Chess 4.0 program. In this approach, all alternative moves at a node are searched, and none are pruned away. They discovered that the time required to simply search all the moves was much less than the time required to apply knowledge-intensive heuristics to select just a few of them, and the benefit of not prematurely or inadvertently pruning away good moves resulted in substantially stronger performance.
In the 1980s and 1990s, progress was finally made in the selective search paradigm, with the development of [[quiescence search]], null move pruning, and other modern selective search heuristics. These heuristics had far fewer mistakes than earlier heuristics did, and was found to be worth the extra time it saved because it could search deeper and widely adopted by many engines. While many modern programs do use [[alpha-beta search]] as a substrate for their search algorithm, these additional selective search heuristics used in modern programs means that the program no longer does a "brute force" search. Instead they heavily rely on these selective search heuristics to extend lines the program considers good and prune and reduce lines the program considers bad, to the point where most of the nodes on the search tree are pruned away, enabling modern programs to search very deep.
In 2006, [[Rémi Coulom]] created [[Monte Carlo tree search]], another kind of type B selective search. In 2007, an adaption of Monte Carlo tree search called Upper Confidence bounds applied to Trees or UCT for short was created by Levente Kocsis and Csaba Szepesvári. In 2011, Chris Rosin developed a variation of UCT called Predictor + Upper Confidence bounds applied to Trees, or PUCT for short. PUCT was then used in [[AlphaZero]] in 2017, and later in [[Leela Chess Zero]] in 2018.
=== Knowledge versus search (processor speed) ===
In the 1970s, most chess programs ran on super computers like Control Data Cyber 176s or Cray-1s, indicative that during that developmental period for computer chess, processing power was the limiting factor in performance. Most chess programs struggled to search to a depth greater than 3 ply. It was not until the hardware chess machines of the 1980s, that a relationship between processor speed and knowledge encoded in the evaluation function became apparent.
It has been estimated that doubling the computer speed gains approximately fifty to seventy [[Elo rating system|Elo]] points in playing strength {{harvcol|Levy|Newborn|1991|p=192}}.
=== Leaf evaluation ===
{{main|Evaluation function}}
For most chess positions, computers cannot look ahead to all possible final positions. Instead, they must look ahead a few [[Ply (game theory)|plies]] and compare the possible positions, known as leaves. The algorithm that evaluates leaves is termed the "evaluation function", and these algorithms are often vastly different between different chess programs. Evaluation functions typically evaluate positions in hundredths of a pawn (called a centipawn), where by convention, a positive evaluation favors White, and a negative evaluation favors Black. However, some evaluation function output win/draw/loss percentages instead of centipawns.
Historically, handcrafted evaluation functions 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 (chess)|pawn]], 3 points for a [[knight (chess)|knight]] or [[bishop (chess)|bishop]], 5 points for a [[rook (chess)|rook]], and 9 points for a [[queen (chess)|queen]]. (See [[Chess piece relative value]].) The [[king (chess)|king]] is sometimes given an arbitrarily high value such as 200 points ([[Claude Shannon#Shannon's computer chess program|Shannon's paper]]) to ensure that a checkmate outweighs all other factors {{Harvcol|Levy|Newborn|1991|pp=45}}. In addition to points for pieces, most handcrafted evaluation functions 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). [[Machine learning]] techniques such as Texel turning, [[stochastic gradient descent]], or [[reinforcement learning]] are usually used to optimise handcrafted evaluation functions.
Most modern evaluation functions make use of [[Artificial neural network|neural networks]]. The most common evaluation function in use today is the [[efficiently updatable neural network]], which is a shallow neural network whose inputs are [[piece-square table]]s. Piece-square tables are a set of 64 values corresponding to the squares of the chessboard, and there typically exists a piece-square table for every piece and colour, resulting in 12 piece-square tables and thus 768 inputs into the neural network. In addition, some engines use [[deep neural networks]] in their evaluation function. Neural networks are usually trained using some [[reinforcement learning]] algorithm, in conjunction with [[supervised learning]] or [[unsupervised learning]].
The output of the evaluation function is a single scalar, quantized in centipawns or other units, which is, in the case of handcrafted evaluation functions, a weighted summation of the various factors described, or in the case of neural network based evaluation functions, the output of the head of the neural network. The evaluation putatively represents or approximates the value of the subtree below the evaluated node as if it had been searched to termination, i.e. the end of the game. During the search, an evaluation is compared against evaluations of other leaves, eliminating nodes that represent bad or poor moves for either side, to yield a node which by convergence, represents the value of the position with best play by both sides.
== Endgame tablebases ==
{{Main|Endgame tablebase}}
Endgame play had long been one of the great weaknesses of chess programs because of the depth of search needed. Some otherwise master-level programs were unable to win in positions where even intermediate human players could force a win.
To solve this problem, computers have been used to analyze some [[chess endgame]] positions completely, starting with [[king (chess)|king]] and [[pawn (chess)|pawn]] against king. Such endgame tablebases 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 (computer programmer)|Ken Thompson]] was a pioneer in this area.
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 (chess)|rook]] against king and [[queen (chess)|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 returned the best moves.
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 {{Harvcol|Levy|Newborn|1991|pp=144–48}}, {{Harvcol|Nunn|2002|p=49}}.
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{{snd}} 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 Tablebase, the De Koning Database and the [[Eugene Nalimov|Nalimov]] Tablebase which is used by many chess programs such as [[Rybka]], [[Shredder (chess)|Shredder]] and [[Fritz (chess)|Fritz]]. Tablebases for all positions with six pieces are available.<ref>{{cite web|author=Kirill Kryukov |url=http://kirill-kryukov.com/chess/tablebases-online/ |title=Endgame Tablebases Online |publisher=Kirill-kryukov.com |access-date=2010-04-03}}</ref> Some seven-piece endgames have been analyzed by Marc Bourzutschky and Yakov Konoval.<ref>{{cite web|url=http://www.xs4all.nl/~timkr/chess2/diary_16.htm |title=Open chess diary 301–320 |publisher=Xs4all.nl |access-date=2010-04-03}}</ref> Programmers using the Lomonosov supercomputers in Moscow have completed a chess tablebase for all endgames with seven pieces or fewer (trivial endgame positions are excluded, such as six white pieces versus a lone black [[king (chess)|king]]).<ref>[http://tb7.chessok.com/shared-positions http://tb7.chessok.com] Lomonosov website allowing registered user to access 7-piece tablebase, and a forum with positions found.</ref><ref>[https://www.chess.com/forum/view/endgames/who-wins-from-this-puzzle "Who wins from this? (chess puzzle)"] An example chess position found from the Lomonosov chess tablebase.</ref> In all of these endgame databases it is assumed that castling is no longer possible.
Many 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. 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' 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.
The Nalimov tablebases, which use state-of-the-art [[Data compression|compression]] techniques, require 7.05 [[Gigabyte|GB]] of hard disk space for all five-piece endings. To cover all the six-piece endings requires approximately 1.2 [[Terabyte|TB]]. It is estimated that a seven-piece tablebase requires between 50 and 200 [[Terabyte|TB]] of storage space.<ref>The Rybka Lounge / Computer Chess / Tablebase sizes, http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=9380 {{Webarchive|url=https://web.archive.org/web/20170627041247/http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=9380 |date=2017-06-27 }}, 19th June 2012</ref>
Endgame databases featured prominently in 1999, when Kasparov played an exhibition match on the Internet against the [[Kasparov versus the World|rest of the world]]. A seven piece [[Queen (chess)|Queen]] and [[pawn (chess)|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.
The most popular endgame tablebase is syzygy which is used by most top computer programs like [[Stockfish (chess)|Stockfish]], [[Leela Chess Zero]], and [[Komodo (chess)|Komodo]]. It is also significantly smaller in size than other formats, with 7-piece tablebases taking only 18.4 TB.<ref>{{cite web |url=https://lichess.org/blog/W3WeMyQAACQAdfAL/7-piece-syzygy-tablebases-are-complete |title=7-piece Syzygy tablebases are complete |website=lichess.org |access-date=2023-10-02}}</ref>
For a current state-of-the art chess engine like Stockfish, a table base only provides a very minor increase in playing strength (approximately 3 Elo points for syzygy 6men as of Stockfish 15).<ref>{{Cite web |title=Useful data |url=https://github.com/official-stockfish/Stockfish/wiki/Useful-data |access-date=2023-10-12 |website=GitHub |language=en}}</ref>
== Opening book ==
Chess engines, like human beings, may save processing time as well as select strong variations as expounded by the masters, by referencing an [[Chess opening book|opening book]] stored in a disk database. Opening books cover the opening moves of a game to variable depth, depending on opening and variation, but usually to the first 10-12 moves (20-24 ply). Since the openings have been studied in depth by the masters for centuries, and some are known to well into the middle game, the valuations of specific variations by the masters will usually be superior to the general heuristics of the program.
While at one time, playing an out-of-book move in order to put the chess program onto its own resources might have been an effective strategy because chess opening books were selective to the program's playing style, and programs had notable weaknesses relative to humans, that is no longer true today.{{when|date=April 2020}} The opening books stored in computer databases are most likely far more extensive than even the best prepared humans, and playing an early out-of-book move may result in the computer finding the unusual move in its book and saddling the opponent with a sharp disadvantage. Even if it does not, playing out-of-book may be much better for tactically sharp chess programs than for humans who have to discover strong moves in an unfamiliar variation over the board.
In modern engine tournaments, opening books are used to force the engines to play intentionally unbalanced openings to reduce the draw rate and to add more variety to the games.<ref>{{Cite web |title=TCEC Openings FAQ |url=https://tcec-chess.com/articles/TCEC_Openings_FAQ.html |access-date=2023-10-12 |website=tcec-chess.com}}</ref>
== Computer chess rating lists ==
{{see also|Chess engine#Ratings}}
[[Chess Engines Grand Tournament|CEGT]],<ref>{{Citation | url=http://www.husvankempen.de/nunn/rating.htm | title=CEGT 40/20 | date=12 October 2008 | publisher=[[Chess Engines Grand Tournament]] | access-date=21 October 2008 | archive-url=https://web.archive.org/web/20120301182317/http://www.husvankempen.de/nunn/rating.htm | archive-date=1 March 2012 | url-status=dead | df=dmy-all }}</ref> CSS,<ref>{{Citation | url=http://www.computerschach.de/index.php?option=com_wrapper&Itemid=242 | title=Computerschach und Spiele – Eternal Rating | date=18 March 2007 | publisher= Computerschach und Spiele | access-date=21 May 2008}}</ref> [[Swedish Chess Computer Association|SSDF]],<ref>{{Citation | url=http://ssdf.bosjo.net/list.htm | title=The SSDF Rating List | publisher=[[Swedish Chess Computer Association]] | date=26 September 2008 | access-date=20 October 2008}}</ref> WBEC,<ref>{{Citation | url=http://wbec-ridderkerk.nl/html/BayesianElo_ed15.htm | title=BayesianElo Ratinglist of WBEC Ridderkerk | access-date=20 July 2008}}</ref> [[REBEL (chess)|REBEL]],<ref>{{cite web | url=https://rebel13.nl/misc/gambit-rating-list.html | title=Gambit Rating List | publisher=Home of the Dutch Rebel | date=January 30, 2021 | access-date=December 12, 2021}}</ref> FGRL,<ref>{{cite web | url=http://fastgm.de | title=FGRL | publisher=FastGM's Rating List | access-date=December 12, 2010}}</ref> and IPON<ref>{{cite web | url=http://www.inwoba.de/bayes.html | title=IPON | publisher=Ingo Bauer | date=November 16, 2016 | access-date=February 3, 2016 | archive-url=https://web.archive.org/web/20190125041233/http://inwoba.de/bayes.html | archive-date=January 25, 2019 | url-status=dead }}</ref> maintain rating lists allowing fans to compare the strength of engines. Various versions of [[Stockfish (chess)|Stockfish]], [[Komodo (chess)|Komodo]], [[Leela Chess Zero]], and [[Fritz (chess)|Fat Fritz]] dominate the rating lists in the early 2020s.
CCRL (Computer Chess Rating Lists) is an organisation that tests computer [[chess engine]]s' [[Elo rating system|strength]] by playing the programs against each other. CCRL was founded in 2006 to promote computer-computer competition and tabulate results on a rating list.<ref name=CCRL>CCRL, http://ccrl.chessdom.com/ {{Webarchive|url=https://web.archive.org/web/20220121151824/http://ccrl.chessdom.com/ |date=2022-01-21 }}, 14 November 2021</ref>
The organisation runs three different lists: 40/40 (40 minutes for every 40 moves played), 40/4 (4 minutes for every 40 moves played), and 40/4 [[Chess960|FRC]] (same time control but Chess960).<ref group=Note name=Note1/> Pondering (or [[permanent brain]]) is switched off and timing is adjusted to the AMD64 X2 4600+ (2.4 GHz) [[CPU]] by using [[Crafty 19.17 BH]] as a benchmark. Generic, neutral [[chess opening book|opening books]] are used (as opposed to the engine's own book) up to a limit of 12 moves into the game alongside 4 or 5 man [[tablebases]].<ref name=CCRL /><ref>CCRL Discussion Board, http://kirill-kryukov.com/chess/discussion-board/viewtopic.php?f=7&t=2808, 19 June 2012</ref><ref>Adam's Computer Chess Pages, http://adamsccpages.blogspot.co.uk/2012/05/ccrl.html, 19 June 2012</ref>
== History ==
=== Pre-computer age ===
[[File:Ajedrecista primero1.JPG|thumb|[[El Ajedrecista]]]]
The idea of creating a chess-playing machine dates back to the eighteenth century. Around 1769, the chess playing [[automaton]] called [[Mechanical Turk|The Turk]], created by [[Kingdom of Hungary|Hungarian]] inventor [[Wolfgang von Kempelen|Farkas Kempelen]], 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, built by Spanish engineer [[Leonardo Torres Quevedo]], which played a king and rook versus king ending, 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.
=== Early software age: selective search and Botvinnik ===
Since then, chess enthusiasts and [[computer engineer]]s have built, with increasing degrees of seriousness and success, chess-playing machines and computer programs. 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. Botvinnik’s interest in Computer Chess started in the 50s, favouring chess algorithms based on Shannon's selective type B strategy, as discussed along with Max Euwe 1958 in Dutch Television. 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 which won a correspondence chess match against the Kotok-McCarthy-Program led by John McCarthy in 1967.(see [[Kotok-McCarthy]]). Later he advised the team that created the chess program Kaissa at Moscow’s Institute of Control Sciences. Botvinnik had his own ideas to model a Chess Master's Mind. After publishing and discussing his early ideas on attack maps and trajectories at Moscow Central Chess Clubin 1966, he found Vladimir Butenko as supporter and collaborator. Butenko first implemented the 15x15 vector attacks board representation on a M-20 computer, determining trajectories. After Botvinnik introduced the concept of Zones in 1970, Butenko refused further cooperation and began to write his own program, dubbed Eureka. In the 70s and 80s, leading a team around Boris Stilman, Alexander Yudin, Alexander Reznitskiy, Michael Tsfasman and Mikhail Chudakov, Botvinnik worked on his own project 'Pioneer' - which was an Artificial Intelligence based chess project. In the 90s, Botvinnik already in his 80s, he worked on the new project 'CC Sapiens'.
=== Later software age: full-width search ===
One developmental milestone occurred when the team from [[Northwestern University]], which was responsible for the [[Chess (Northwestern University)|Chess]] series of programs and won the first three [[Association for Computing Machinery|ACM]] [[World Computer Chess Championship#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. The type A implementation 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, and that had been successfully started by the Russian ITEP in 1965.
=== Rise of chess machines ===
In 1978, an early rendition of Ken Thompson's hardware chess machine [[Belle (chess machine)|Belle]], entered and won the North American Computer Chess Championship over the dominant Northwestern University Chess 4.7.
=== Microcomputer revolution ===
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 [[IBM Deep Blue|Deep Blue]], a brute-force machine capable of examining 500 million nodes per second, defeated World Champion Garry Kasparov, marking the first time a computer has defeated a reigning world chess champion in standard time control.
=== Super-human chess ===
In 2016, [[NPR]] asked experts to characterize the playing style of computer chess engines. [[Murray Campbell]] of IBM stated that "Computers don't have any sense of aesthetics... They play what they think is the objectively best move in any position, even if it looks absurd, and they can play any move no matter how ugly it is." Grandmasters Andrew Soltis and [[Susan Polgar]] stated that computers are more likely to retreat than humans are.<ref name="npr 20 years"/>
=== Neural network revolution ===
While [[Artificial neural network|neural networks]] have been used in the [[evaluation function]]s of chess engines since the late 1980s, with programs such as NeuroChess, Morph, Blondie25, Giraffe, [[AlphaZero]], and [[MuZero]],<ref>{{citation|title=Learning to Play the Game of Chess|last=Thurn|first=Sebastian|year=1995|publisher=MIT Press|url=https://proceedings.neurips.cc/paper/1994/file/d7322ed717dedf1eb4e6e52a37ea7bcd-Paper.pdf|access-date=12 December 2021}}</ref><ref>{{citation|title=A Self-Learning, Pattern-Oriented Chess Program|last=Levinson|first=Robert|year=1989|publisher=ICCA Journal|volume=12|issue=4}}</ref><ref name="Giraffe">{{citation|title=Giraffe: Using Deep Reinforcement Learning to Play Chess|last=Lai|first=Matthew|date=4 September 2015|arxiv=1509.01549v1}}</ref><ref>{{Cite arXiv|eprint = 1712.01815|last1 = Silver|first1 = David|last2 = Hubert|first2 = Thomas|last3 = Schrittwieser|first3 = Julian|last4 = Antonoglou|first4 = Ioannis|last5 = Lai|first5 = Matthew|last6 = Guez|first6 = Arthur|last7 = Lanctot|first7 = Marc|last8 = Sifre|first8 = Laurent|last9 = Kumaran|first9 = Dharshan|last10 = Graepel|first10 = Thore|last11 = Lillicrap|first11 = Timothy|last12 = Simonyan|first12 = Karen|last13 = Hassabis|first13 = Demis|title = Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm|year = 2017|class = cs.AI}}</ref><ref name="MuZero">{{cite journal|arxiv=1911.08265|first1=Julian|last1=Schrittwieser|first2=Ioannis|last2=Antonoglou|title=Mastering Atari, Go, chess and shogi by planning with a learned model|last3=Hubert|last9=Hassabis|first11=Timothy|last11=Lillicrap|first10=Thore|last10=Graepel|first9=Demis|first8=Edward|first3=Thomas|last8=Lockhart|last7=Guez|first6=Simon|last6=Schmitt|first5=Laurent|last5=Sifre|first4=Karen|last4=Simonyan|first7=Arthur|journal=Nature|year=2020|volume=588|issue=7839|pages=604–609|doi=10.1038/s41586-020-03051-4|pmid=33361790|bibcode=2020Natur.588..604S|s2cid=208158225}}</ref> neural networks did not become widely adopted by chess engines until the arrival of [[efficiently updatable neural network]]s in the summer of 2020. Efficiently updatable neural networks were originally developed in [[computer shogi]] in 2018 by Yu Nasu,<ref name="Nasu">{{cite web|title=Efficiently Updatable Neural-Network-based Evaluation Function for computer Shogi|author=Yu Nasu|url=https://www.apply.computer-shogi.org/wcsc28/appeal/the_end_of_genesis_T.N.K.evolution_turbo_type_D/nnue.pdf|date=April 28, 2018|language=Japanese}}</ref><ref name="Nasu2">{{cite web|title=Efficiently Updatable Neural-Network-based Evaluation Function for computer Shogi (Unofficial English Translation)|author=Yu Nasu|website=[[GitHub]]|url=https://github.com/asdfjkl/nnue/blob/main/nnue_en.pdf|date=April 28, 2018|language=English}}</ref> and had to be first ported to a derivative of Stockfish called Stockfish NNUE on 31 May 2020,<ref>{{cite web|url=https://github.com/nodchip/Stockfish/releases/tag/stockfish-nnue-2020-05-30|title=Release stockfish-nnue-2020-05-30|website=Github|last=Noda|first=Hisayori|date=30 May 2020|access-date=12 December 2021}}</ref> and integrated into the official Stockfish engine on 6 August 2020,<ref name="Introducing NNUE Evaluation">{{cite web|title=Introducing NNUE Evaluation|url=https://blog.stockfishchess.org/post/625828091343896577/introducing-nnue-evaluation|date=6 August 2020}}</ref><ref name="Joost VandeVondele">{{cite web|title= official-stockfish / Stockfish, NNUE merge|url=https://github.com/official-stockfish/Stockfish/issues/2823#issue-665540175|author=Joost VandeVondele|website=[[GitHub]]|date=July 25, 2020}}</ref> before other chess programmers began to adopt neural networks into their engines.
Some people, such as the [[Royal Society]]'s [[Venki Ramakrishnan]], believe that [[AlphaZero]] lead to the widespread adoption of neural networks in chess engines.<ref>{{cite book |title=[[Possible Minds: Twenty-five Ways of Looking at AI]] |date=2019 |publisher=Penguin Press |isbn=978-0525557999 |edition=Kindle| page=174| chapter=[[Venki Ramakrishnan]]: Will Computers Become Our Overlords?}}</ref> However, AlphaZero influenced very few engines to begin using neural networks, and those tended to be new experimental engines such as [[Leela Chess Zero]], which began specifically to replicate the AlphaZero paper. The [[deep neural network]]s used in AlphaZero's evaluation function required expensive [[graphics processing units]], which were not compatible with existing chess engines. The vast majority of chess engines only use [[central processing units]], and computing and processing information on the GPUs require special [[Library (computing)|libraries]] in the backend such as [[Nvidia]]'s [[CUDA]], which none of the engines had access to. Thus the vast majority of chess engines such as [[Komodo (chess)|Komodo]] and [[Stockfish (chess)|Stockfish]] continued to use handcrafted evaluation functions until [[efficiently updatable neural network]]s were ported to computer chess in 2020, which did not require either the use of GPUs or libraries like CUDA at all. Even then, the neural networks used in computer chess are fairly shallow, and the [[deep reinforcement learning]] methods pioneered by AlphaZero are still extremely rare in computer chess.
=== Timeline ===
* 1769 – [[Wolfgang von Kempelen]] builds [[Mechanical Turk|the Turk]]. Presented as a chess-playing automaton, it is secretly operated by a human player hidden inside the machine.
* 1868 – Charles Hooper presents the [[Ajeeb]] automaton{{snd}} which also has a human chess player hidden inside.
* 1912 – [[Leonardo Torres y Quevedo]] builds [[El Ajedrecista]], a machine that could play [[wikibooks:Chess/The Endgame/King and Rook vs. King|King and Rook versus King endgames]].
* 1941 – Predating comparable work by at least a decade, [[Konrad Zuse]] develops computer chess algorithms in his [[Plankalkül]] programming formalism. Because of the circumstances of the Second World War, however, they were not published, and did not come to light, until the 1970s.
* 1948 – [[Norbert Wiener]]'s book ''Cybernetics'' describes how a chess program could be developed using a depth-limited minimax search with an [[evaluation function]].
* 1950 – [[Claude Shannon]] publishes "Programming a Computer for Playing Chess", one of the first papers on the algorithmic methods of computer chess.
* 1951 – [[Alan Turing]] is first to publish a program, developed on paper, that was capable of playing a full game of chess (dubbed [[Turochamp]]).<ref>Chess, a subsection of chapter 25, Digital Computers Applied to Games, of Faster than Thought, ed. B. V. Bowden, Pitman, London (1953). [https://web.archive.org/web/20031124134110/http://www.turingarchive.org/browse.php/B/7 Online].</ref><ref>[http://www.chessgames.com/perl/chessgame?gid=1356927 A game played by Turing's chess algorithm]</ref>
* 1952 – [[Dietrich Prinz]] develops a program that solves chess problems.
{{Chess diagram 6x6
| tright
|
|rd|nd|qd|kd|nd|rd
|pd|pd|pd|pd|pd|pd
| | | | | |
| | | | | |
|pl|pl|pl|pl|pl|pl
|rl|nl|ql|kl|nl|rl
| '''[[Los Alamos chess]]'''. This simplified version of chess was played in 1956 by the [[MANIAC I]] computer.
}}
* 1956 – [[Los Alamos chess]] is the first program to play a chess-like game, developed by Paul Stein and Mark Wells for the [[MANIAC I]] computer.
* 1956 – [[John McCarthy (computer scientist)|John McCarthy]] invents the [[alpha–beta pruning|alpha–beta]] search algorithm.
* 1957 – The first programs that can play a full game of chess are developed, one by Alex Bernstein<ref>{{cite web|url=http://www.chessville.com/BillWall/EarlyComputerChessPrograms.htm |title=Chessville – Early Computer Chess Programs – by Bill Wall – Bill Wall's Wonderful World of Chess |publisher=Archive.is |access-date=1 December 2014 |url-status=bot: unknown |archive-url=https://archive.today/20120721202324/http://www.chessville.com/BillWall/EarlyComputerChessPrograms.htm |archive-date=21 July 2012 }}</ref> and one by [[Russia]]n programmers using a [[BESM]].
* 1958 – NSS becomes the first chess program to use the alpha–beta search algorithm.
* 1962 – The first program to play credibly, [[Kotok-McCarthy]], is published at [[Massachusetts Institute of Technology|MIT]].
* 1963 – Grandmaster [[David Bronstein]] defeats an [[Minsk family of computers|M-20]] running an early chess program.<ref>[http://www.chessgames.com/perl/chessgame?gid=1238081 David Bronstein v M-20, replay at Chessgames.com]</ref>
* 1966–67 – The first chess match between computer programs is played. [[Moscow]] [[Institute for Theoretical and Experimental Physics]] (ITEP) defeats Kotok-McCarthy at [[Stanford University]] by telegraph over nine months.
* 1967 – [[MacHack (chess)|Mac Hack VI]], by [[Richard Greenblatt (programmer)|Richard Greenblatt]] et al. introduces [[transposition table]]s and employs dozens of carefully tuned move selection heuristics; it becomes the first program to defeat a person in tournament play. Mac Hack VI played about C class level.
* 1968 – Scottish chess champion [[David Levy (chess player)|David Levy]] makes a 500 [[pound (monetary unit)|pound]] bet with AI pioneers [[John McCarthy (computer scientist)|John McCarthy]] and [[Donald Michie]] that no computer program would win a chess match against him within 10 years.
* 1970 – [[Monty Newborn]] and the [[Association for Computing Machinery]] organize the first [[North American Computer Chess Championship]]s in New York.
* 1971 – [[Ken Thompson]], an American Computer scientist at Bell Labs and creator of the Unix operating system, writes his first chess-playing program called "chess" for the earliest version of [[Unix]].<ref name="ritchie01">{{cite journal | journal=ICGA Journal | volume=24 | issue=2 |date=June 2001 | url=https://www.bell-labs.com/usr/dmr/www/ken-games.html| title=Ken, Unix and Games | author=[[Dennis Ritchie]]}}</ref>
* 1974 – [[David Levy (chess player)|David Levy]], Ben Mittman and [[Monty Newborn]] organize the first [[World Computer Chess Championship]] which is won by the Russian program [[Kaissa]].
* 1975 – After nearly a decade of only marginal progress since the high-water mark of Greenblatt's MacHack VI in 1967, Northwestern University Chess 4.5 is introduced featuring full-width search, and innovations of bitboards and iterative deepening. It also reinstated a transposition table as first seen in Greenblatt's program. It was thus the first program with an integrated modern structure and became the model for all future development. Chess 4.5 played strong B-class and won the 3rd World Computer Chess Championship the next year.<ref>{{cite web|url=https://link.springer.com/content/pdf/bbm%3A978-1-4612-5515-4%2F1.pdf|title=Appendix CHESS 4.5: Competition in 1976 }}</ref> Northwestern University Chess and its descendants dominated computer chess until the era of hardware chess machines in the early 1980s.
* 1976 – In December, Canadian programmer [[Peter R. Jennings]] releases [[Microchess]], the first game for microcomputers to be sold.<ref>{{cite web|url=https://www.computerhistory.org/chess/orl-4334404555680/|title = Oral History of Peter Jennings | Mastering the Game | Computer History Museum}}</ref>
[[File:BorisChess.jpg|thumb|Released in 1977, Boris was one of the first chess computers to be widely marketed. It ran on a Fairchild F8 8-bit microprocessor with only 2.5 KiB ROM and 256 byte RAM.]]
* 1977 – In March, Fidelity Electronics releases [[Chess Challenger]], the first dedicated chess computer to be sold. The [[International Computer Chess Association]] is founded by chess programmers to organize computer chess championships and report on research and advancements on computer chess in their journal. Also that year, Applied Concepts released [[Boris (chess computer)|Boris]], a dedicated chess computer in a wooden box with plastic chess pieces and a folding board.
* 1978 – [[David Levy (chess player)|David Levy]] wins the bet made 10 years earlier, defeating [[Chess (Northwestern University)|Chess 4.7]] in a six-game match by a score of 4½–1½. The computer's victory in game four is the first defeat of a human master in a tournament.<ref name="douglas197812"/>
* 1979 – [[Frederic Friedel]] organizes a match between IM [[David Levy (chess player)|David Levy]] and [[Chess (Northwestern University)|Chess 4.8]], which is broadcast on German television. Levy and Chess 4.8, running on a CDC Cyber 176, the most powerful computer in the world, fought a grueling 89 move draw.
* 1980 – Fidelity computers win the World Microcomputer Championships each year from 1980 through 1984. In Germany, Hegener & Glaser release their first [[Mephisto (chess computer)|Mephisto]] dedicated chess computer. The USCF prohibits computers from competing in human tournaments except when represented by the chess systems' creators.<ref name="byte198101">{{cite news | url=https://archive.org/stream/byte-magazine-1981-01/1981_01_BYTE_06-01_Hand-held_Computers#page/n293/mode/2up | title=New Restrictions | work=BYTE | date=January 1981 | access-date=18 October 2013 | page=292}}</ref> The Fredkin Prize, offering $100,000 to the creator of the first chess machine to defeat the world chess champion, is established.
* 1981 – [[Cray Blitz]] 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.
* 1984 – The German Company Hegener & Glaser's ''[[Mephisto (chess computer)|Mephisto]]'' line of dedicated chess computers begins a long streak of victories (1984–1990) in the World Microcomputer Championship using dedicated computers running programs [[ChessGenius]] and [[REBEL (chess)|Rebel]].
* 1986 – Software Country (see [[Software Toolworks]]) released ''[[Chessmaster]] 2000'' based on an engine by David Kittinger, the first edition of what was to become the world's best selling line of chess programs.
* 1987 – [[Frederic Friedel]] and physicist Matthias Wüllenweber found [[Chessbase]], releasing the first chess database program. Stuart Cracraft releases [[GNU Chess]], one of the first '[[chess engine]]s' to be bundled with a separate [[graphical user interface]] (GUI), {{proper name|chesstool}}.<ref>{{cite web|url=https://web.cecs.pdx.edu/~trent/gnu/bull/02/nb.html#SEC6|title = GNU's Bulletin, vol. 1 no. 2}}</ref>
* 1988 – [[HiTech]], developed by [[Hans Berliner]] and [[Carl Ebeling]], wins a match against grandmaster [[Arnold Denker]] 3½–½. [[Deep Thought (chess computer)|Deep Thought]] shares first place with [[Tony Miles]] in the Software Toolworks Championship, ahead of former world champion [[Mikhail Tal]] and several grandmasters including [[Samuel Reshevsky]], [[Walter Browne]] and [[Mikhail Gurevich (chess player)|Mikhail Gurevich]]. It also defeats grandmaster [[Bent Larsen]], making it the first computer to beat a GM in a tournament. Its [[Elo rating system|rating]] for performance in this tournament of 2745 (USCF scale) was the highest obtained by a computer player.<ref>Hsu (2002) p. 292</ref><ref>Newborn (1997) p. 159</ref>
* 1989 – Deep Thought demolishes David Levy in a 4-game match 0–4, bringing to an end his famous series of wagers starting in 1968.
* 1990 – On April 25, former world champion [[Anatoly Karpov]] lost in a simul to Hegener & Glaser's Mephisto Portorose M68030 chess computer.<ref>Selective Search. June 1990</ref>
* 1991 – The [[ChessMachine]] based on Ed Schröder's [[REBEL (chess)|Rebel]] wins the World Microcomputer Chess Championship
* 1992 – [[ChessMachine]] wins the 7th [[World Computer Chess Championship]], the first time a microcomputer beat [[mainframe computer|mainframes]]. GM [[John Nunn]] releases ''Secrets of Rook Endings'', the first book based on endgame tablebases developed by [[Ken Thompson]].
* 1993 – Deep Thought-2 loses a four-game match against [[Bent Larsen]]. Chess programs running on personal computers surpass Mephisto's dedicated chess computers to win the Microcomputer Championship, marking a shift from dedicated chess hardware to software on multipurpose personal computers.
* 1995 – [[Fritz (chess)|Fritz 3]], running on a 90Mhz Pentium PC, beats Deep Thought-2 dedicated chess machine, and programs running on several super-computers, to win the 8th [[World Computer Chess Championship]]s in Hong Kong. This marks the first time a chess program running on commodity hardware defeats specialized chess machines and massive super-computers, indicating a shift in emphasis from brute computational power to algorithmic improvements in the evolution of chess engines.
* 1996 – IBM's [[Deep Blue (chess computer)|Deep Blue]] loses a six-game match against [[Garry Kasparov]], 2–4.
* 1997 – [[Deep Blue (chess computer)|Deep(er) Blue]], a highly modified version of the original, wins a six-game match against [[Garry Kasparov]], 3.5-2.5.
* 2000 – [[Stefan Meyer-Kahlen]] and Rudolf Huber draft the [[Universal Chess Interface]], a protocol for GUIs to talk to engines that would gradually become the main form new engines would take.
* 2002 – [[Vladimir Kramnik]] draws an eight-game match against [[Deep Fritz]].
* 2003 – Kasparov draws a six-game match against [[Deep Junior]] and draws a four-game match against [[X3D Fritz]].
* 2004 – a team of computers ([[Hydra (chess)|Hydra]], [[Deep Junior]] and [[Fritz (chess)|Fritz]]) wins 8½–3½ against a strong human team formed by [[Veselin Topalov]], [[Ruslan Ponomariov]] and [[Sergey Karjakin]], who had an average [[Elo rating system|Elo]] rating of 2681. Fabien Letouzey releases the source code for Fruit 2.1, an engine quite competitive with the top closed-source engines of the time. This leads many authors to revise their code, incorporating the new ideas.
* 2005 – [[Rybka]] wins the [[International Paderborn Computer Chess Championship|IPCCC]] tournament and very quickly afterwards becomes the strongest engine.<ref>[http://www.rybkachess.com/docs/PADERBORNCOMPUTER.htm International Paderborn Computer Chess Championship 2005]</ref>
* 2006 – The world champion, [[Vladimir Kramnik]], is defeated 4–2 by [[Deep Fritz]].
* 2009 – [[Pocket Fritz]]. 4 running on a smartphone, wins Copa Mercosur, an International Master level tournament, scoring 9½/10 and earning a performance rating of 2900.<ref name=PF4GM/> A group of pseudonymous Russian programmers release the source code of Ippolit, an engine seemingly stronger than [[Rybka]]. This becomes the basis for the engines Robbolito and Ivanhoe, and many engine authors adopt ideas from it.
* 2010 – Before the [[World Chess Championship 2010]], Topalov prepares by sparring against the supercomputer Blue Gene with 8,192 processors capable of 500 trillion (5 × 10<sup>14</sup>) floating-point operations per second.<ref>{{cite web|url=http://www.chessbase.com/newsdetail.asp?newsid=6361 |title=Challenger uses supercomputer at the world chess championship|date=25 May 2010|publisher=Chessbase }}</ref> Rybka developer, [[Vasik Rajlich]], accuses Ippolit of being a clone of Rybka.
* 2011 – The ICGA strips Rybka of its WCCC titles.<ref>{{cite web |url=http://www.chessvibes.com/reports/rybka-disqualified-and-banned-from-world-computer-chess-championships/ |title= Rybka disqualified and banned from World Computer Chess Championships | ChessVibes|website=www.chessvibes.com |archive-url=https://web.archive.org/web/20140330145657/http://www.chessvibes.com/reports/rybka-disqualified-and-banned-from-world-computer-chess-championships/ |archive-date=30 March 2014}}</ref><ref name=AGMoJiCCpo>{{cite news|last=Riis|first=Dr. Søren|title=A Gross Miscarriage of Justice in Computer Chess (part one)|url=http://www.chessbase.com/newsdetail.asp?newsid=7791|access-date=19 February 2012|newspaper=Chessbase News|date=2 January 2012}}</ref>
* 2017 – [[AlphaZero]], a neural net-based digital automaton, beats [[Stockfish (chess)|Stockfish]] 28–0, with 72 draws, in a 100-game match.
* 2018 - [[Efficiently updatable neural network]] (NNUE) evaluation is invented for [[computer shogi]].<ref>[[Yu Nasu]] (2018). ''ƎUИИ Efficiently Updatable Neural-Network based Evaluation Functions for Computer Shogi''. Ziosoft Computer Shogi Club, [https://github.com/ynasu87/nnue/blob/master/docs/nnue.pdf pdf] (Japanese with English abstract)</ref>
* 2019 – [[Leela Chess Zero]] (LCZero v0.21.1-nT40.T8.610), a chess engine based on AlphaZero, defeats [[Stockfish (chess)|Stockfish]] 19050918 in a 100-game match with the final score 53.5 to 46.5 to win [[Top Chess Engine Championship|TCEC]] season 15.<ref>https://cd.tcecbeta.club/archive.html?season=15&div=sf&game=1 TCEC season 15</ref>
* 2020 - NNUE is added to [[Stockfish (chess)|Stockfish]] evaluation, noticeably increasing its strength.<ref name="Introducing NNUE Evaluation"/><ref name="Joost VandeVondele"/>
== Categorizations ==
=== Dedicated hardware ===
These chess playing systems include custom hardware with approx. dates of introduction (excluding dedicated microcomputers):
* [[Belle (chess machine)|Belle]] 1976
* Bebe, a strong [[bit-slice processor]] 1980
* [[HiTech]] 1985
* [[ChipTest]] 1985
* [[Deep Thought (chess computer)|Deep Thought]] 1987
* Deep Thought 2 (Deep Blue prototype)~1994
* [[IBM Deep Blue|Deep Blue]] 1996, 1997
* [[Hydra (chess)|Hydra]], predecessor was called Brutus 2002
* [[AlphaZero]] 2017 (used Google's [[Tensor Processing Unit]]s for neural networks, but the hardware is not specific to Chess or games)
** [[MuZero]] 2019 (similar hardware to its predecessor AlphaZero, non-specific to Chess or e.g. Go), learns the rules of Chess
=== Commercial dedicated computers ===
[[File:Boris Diplomat Electronic Chess Computer by Chafitz, Inc., Rockville, Maryland, Model Bd-1, Red LED Display, Made in U.S.A., Circa 1979 (Electronic Chess Computer).jpg|thumb|Boris Diplomat (1979) travel chess computer]]
[[File:Fidelity Chess Challenger Voice.jpg|thumb|Fidelity Voice Chess Challenger (1979), the first talking chess computer]]
[[File:Fidelity Chess Challenger Voice speech output.flac|thumb|Speech output from Voice Chess Challenger]]
[[File:Chess computers at the Computer History Museum.jpg|thumb|Milton Bradley Grandmaster (1983), the first commercial self-moving chess computer]]
[[File:Novag Super Constellation, 2.jpg|thumb|Novag Super Constellation (1984), known for its human-like playing style]]
[[File:DGT Centaur 4.jpg|thumb|DGT Centaur (2019), a modern chess computer based on [[Stockfish (chess)|Stockfish]] running on a [[Raspberry Pi]]]]
In the late 1970s to early 1990s, there was a competitive market for dedicated chess computers. This market changed in the mid-1990s when computers with dedicated processors could no longer compete with the fast processors in personal computers.
* Boris in 1977 and Boris Diplomat in 1979, chess computers including pieces and board, sold by Applied Concepts Inc.
* Chess Challenger, a line of chess computers sold by Fidelity Electronics from 1977 to 1992.<ref>{{cite web|url=http://www.ismenio.com/chess_cc1.html|title=Fidelity Chess Challenger 1 – World's First Chess Computer|first=Ismenio|last=Sousa|access-date=25 September 2016}}</ref> These models won the first four [[World Microcomputer Chess Championship]]s.{{citation needed|date=June 2017}}
* [[ChessMachine]], an [[ARM architecture|ARM]]-based dedicated computer, which could run two engines:
** "The King", which later became the [[Chessmaster]] engine, was also used in the TASC R30 dedicated computer.
** Gideon, a version of [[REBEL (chess)|Rebel]], in 1992 became the first microcomputer to win the [[World Computer Chess Championship]].<ref>{{Cite journal|url=https://research.tilburguniversity.edu/en/publications/the-7th-world-computer-chess-championship-report-on-the-tournamen|title=The 7th World Computer-Chess Championship: Report on the tournament, Madrid, Spain, November 23-27, 1992|journal=ICCA Journal|year=1992|volume=15|issue=4|pages=208–209|last1=van den Herik|first1=H.J.|last2=Herschberg|first2=I. S.}}</ref>
* Excalibur Electronics sells a line of beginner strength units.
* [[Mephisto (chess computer)|Mephisto]], a line of chess computers sold by Hegener & Glaser. The units won six consecutive [[World Microcomputer Chess Championship]]s.{{citation needed|date=June 2017}}
* Novag sold a line of tactically strong computers, including the Constellation, Sapphire, and Star Diamond brands.
* Phoenix Chess Systems makes limited edition units based around [[StrongARM]] and [[XScale]] processors running modern engines and emulating classic engines.
* [[Saitek]] sells mid-range units of intermediate strength. They bought out Hegener & Glaser and its Mephisto brand in 1994.
Recently, some hobbyists have been using the [[Multi Emulator Super System]] to run the chess programs created for Fidelity or Hegener & Glaser's Mephisto computers on modern 64-bit operating systems such as [[Windows 10]].<ref>{{cite web|url=http://rebel13.nl/rebel13/rebel%2013.html |title=Download | Home of the Dutch Rebel |publisher=Rebel13.nl |date= |accessdate=2022-08-31}}</ref> The author of [[REBEL (chess)|Rebel]], Ed Schröder has also adapted three of the Hegener & Glaser Mephisto's he wrote to work as UCI engines.<ref>{{cite web|url=http://rebel13.nl/dedicated/dedicated%20as%20uci.html |title=Dedicated as UCI | Home of the Dutch Rebel |publisher=Rebel13.nl |date= |accessdate=2022-08-31}}</ref>
=== DOS programs ===
These programs can be run on MS-DOS, and can be run on 64-bit Windows 10 via emulators such as [[DOSBox]] or [[Qemu]]:<ref>{{cite web |url=http://rebel13.nl/download/more%20dos%20oldies.html |title=More DOS oldies |access-date=2018-12-02 |archive-date=2018-12-03 |archive-url=https://web.archive.org/web/20181203055650/http://rebel13.nl/download/more%20dos%20oldies.html |url-status=dead }}</ref>
* [[Chessmaster 2000]]
* [[Colossus Chess]]
* [[Fritz (chess)|Fritz]] 1–3
* [[Kasparov's Gambit]]
* [[REBEL (chess)|Rebel]]
* [[Sargon (chess)|Sargon]]
* [[Socrates II]]
== Notable theorists ==
Well-known computer chess theorists include:
* [[Georgy Adelson-Velsky]], a Soviet and Israeli mathematician and computer scientist
* [[Hans Berliner]], American computer scientist and world correspondence chess champion, design supervisor of HiTech (1988)
* [[Mikhail Botvinnik]], Soviet electrical engineer and world chess champion, wrote ''Pioneer''
* [[Alexander Brudno]], Russian computer scientist, first elaborated the alphabeta pruning algorithm
* [[Feng-hsiung Hsu]], the lead developer of [[Deep Blue (chess computer)|Deep Blue]] (1986–97)
* Professor [[Robert Hyatt]] developed [[Cray Blitz]] and [[Crafty]]<ref>{{cite web|url=http://www.cis.uab.edu/info/faculty/hyatt/hyatt.html |title=Dr. Robert Hyatt's home page |publisher=Cis.uab.edu |date=2004-02-01 |access-date=2010-04-03}}</ref>
* [[Danny Kopec]], American Professor or Computer Science and International Chess Master, developed Kopec-Bratko test
* [[Alexander Kronrod]], Soviet computer scientist and mathematician
* Professor [[Monroe Newborn]], chairman of the computer chess committee for the Association for Computing Machinery
* [[Claude E. Shannon]], American computer scientist and mathematician
* [[Alan Turing]], English computer scientist and mathematician
== Solving chess ==
{{Main|Solving chess}}
The prospects of completely [[solved game|solving]] chess are generally considered to be rather remote. It is widely conjectured that no computationally inexpensive method to solve chess exists even in the 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 search]]er 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 at least 10<sup>43</sup><ref name="Shannon1950">The size of the state space and game tree for chess were first estimated in {{Citation | author = [[Claude Shannon]] | title = Programming a Computer for Playing Chess | journal = Philosophical Magazine | volume = 41 | issue = 314 | year = 1950 | url = http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf | access-date = 30 December 2008 | url-status = dead | archive-url = https://web.archive.org/web/20100706211229/http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf | archive-date = 6 July 2010 }} Shannon gave estimates of 10<sup>43</sup> and 10<sup>120</sup> respectively, smaller than the estimates in the [[Game complexity]] table, which are from [[Victor Allis]]'s thesis. See [[Shannon number]] for details.</ref> to 10<sup>47</sup>), 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]],<ref>{{Citation |author1=Aviezri Fraenkel |author2=D. Lichtenstein | title = Computing a perfect strategy for n×n chess requires time exponential in n | journal = J. Combin. Theory Ser. A | volume = 31 | year = 1981 | pages = 199–214 | doi = 10.1016/0097-3165(81)90016-9 | issue = 2| doi-access = }}</ref> 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.
[[Martin Gardner]]'s [[Minichess]], played on a 5×5 board with approximately 10<sup>18</sup> possible board positions, has been solved; its game-theoretic value is 1/2 (i.e. a draw can be forced by either side), and the forcing strategy to achieve that result has been described.
Progress has also been made from the other side: as of 2012, all 7 and fewer pieces (2 kings and up to 5 other pieces) endgames have been solved.
== Chess engines ==
{{Main|Chess engine}}
A "chess engine" is software that calculates and orders which moves are the strongest to play in a given position. Engine authors focus on improving the play of their engines, often just importing the engine into a [[graphical user interface]] (GUI) developed by someone else. Engines communicate with the GUI by standardized protocols such as the nowadays ubiquitous [[Universal Chess Interface]] developed by [[Stefan Meyer-Kahlen]] and Franz Huber. There are others, like the Chess Engine Communication Protocol developed by Tim Mann for [[GNU Chess]] and [[Winboard]]. [[Chessbase]] has its own proprietary protocol, and at one time Millennium 2000 had another protocol used for [[ChessGenius]]. Engines designed for one operating system and protocol may be ported to other OS's or protocols.
Chess engines are regularly matched against each other at dedicated [[chess engine#Tournaments|chess engine tournaments]].
== Chess web apps ==
In 1997, the [[Internet Chess Club]] released its first Java client for playing chess online against other people inside one's webbrowser.<ref>{{cite web |url=http://www.chessclub.com/CoffeeHouse.html |title=CoffeeHouse: The Internet Chess Club Java Interface |access-date=2019-07-08 |archive-url=https://web.archive.org/web/19970620110903/http://www.chessclub.com/CoffeeHouse.html |archive-date=1997-06-20 |url-status=dead }}</ref> This was probably one of the first chess web apps. [[Free Internet Chess Server]] followed soon after with a similar client.<ref>{{cite web |url=http://www.freechess.org/ |title=FICS - Free Internet Chess Server |access-date=2019-07-08 |archive-url=https://web.archive.org/web/19981212025054/http://www.freechess.org/ |archive-date=1998-12-12 |url-status=live }}</ref> In 2004, [[International Correspondence Chess Federation]] opened up a web server to replace their email-based system.<ref>{{cite web |url=http://www.iccf-webchess.com/ |title=Archived copy |access-date=2004-08-31 |archive-url=https://web.archive.org/web/20040831025215/http://www.iccf-webchess.com/ |archive-date=2004-08-31 |url-status=live }}</ref> [[Chess.com]] started offering Live Chess in 2007.<ref>{{cite web|url=http://www.chess.com/echess/|archive-url = https://web.archive.org/web/20071006143047/http://www.chess.com/echess/|archive-date = 2007-10-06|title = Play Daily (Correspondence) Chess}}</ref> [[Chessbase]]/[[Playchess]] has long had a downloadable client, and added a web-based client in 2013.<ref>{{cite web |url=http://play.chessbase.com/js/apps/playchess/ |title=Play Chess Online for Free |website=play.chessbase.com |access-date=11 January 2022 |archive-url=https://web.archive.org/web/20131217045511/http://play.chessbase.com/js/apps/playchess/ |archive-date=17 December 2013 |url-status=dead}}</ref>
Another popular web app is tactics training. The now defunct Chess Tactics Server opened its site in 2006,<ref>{{cite web |url=http://chess.emrald.net/ |title=Chess Tactics Server |access-date=2006-04-08 |archive-url=https://web.archive.org/web/20060408052731/http://chess.emrald.net/ |archive-date=2006-04-08 |url-status=dead }}</ref> followed by Chesstempo the next year,<ref>{{cite web |url=http://chesstempo.com/ |title=Chess Tactics |access-date=2007-06-13 |archive-url=https://web.archive.org/web/20070613100847/http://chesstempo.com/ |archive-date=2007-06-13 |url-status=live }}</ref> and [[Chess.com]] added its Tactics Trainer in 2008.<ref>{{cite web |url=http://www.chess.com/tactics |title=Chess Puzzles - Improve Your Chess by Solving Tactics |access-date=2008-02-18 |archive-url=https://web.archive.org/web/20080218082614/http://www.chess.com/tactics |archive-date=2008-02-18 |url-status=live }}</ref> [[Chessbase]] added a tactics trainer web app in 2015.<ref>{{cite web|url=http://training.chessbase.com/js/apps/Training/|archive-url=https://web.archive.org/web/20150504000924/http://training.chessbase.com/js/apps/Training/|archive-date=2015-05-04|title=Chess Tactics Online}}</ref>
[[Chessbase]] took their chess game database online in 1998.<ref>{{cite web |url=http://www.chessbase-online.com/ |title=Chessbase Online, Searching a high quality database of Chessgames. Free Chess Games.ChessBase-Online |website=www.chessbase-online.com |access-date=11 January 2022 |archive-url=https://web.archive.org/web/20000511014758/http://www.chessbase-online.com/ |archive-date=11 May 2000 |url-status=dead}}</ref> Another early chess game databases was Chess Lab, which started in 1999.<ref>{{cite web |url=http://www.chesslab.com/PositionSearch.html |title=Java chess games: Database search, analysis |access-date=2019-07-08 |archive-url=https://web.archive.org/web/19990219143550/http://www.chesslab.com/PositionSearch.html |archive-date=1999-02-19 |url-status=live }}</ref> [[New In Chess]] had initially tried to compete with [[Chessbase]] by releasing a NICBase program for [[Windows 3.x]], but eventually, decided to give up on software, and instead focus on their online database starting in 2002.<ref>{{cite web |url=http://www31.ws26.temphost.nl/NICBase/ |title=NICBase Online |access-date=2002-10-08 |archive-url=https://web.archive.org/web/20021008054123/http://www31.ws26.temphost.nl/NICBase/ |archive-date=2002-10-08 |url-status=live }}</ref>
One could play against the engine [[Shredder (chess)|Shredder]] online from 2006.<ref>{{cite web |url=http://www.shredderchess.com/play-chess-online.html |title=Play Chess Online - Shredder Chess |access-date=2006-12-05 |archive-url=https://web.archive.org/web/20061205205401/http://www.shredderchess.com/play-chess-online.html |archive-date=2006-12-05 |url-status=live }}</ref> In 2015, [[Chessbase]] added a play Fritz web app,<ref>{{cite web |url=http://fritz.chessbase.com/ |title=Home |website=fritz.chessbase.com}}</ref> as well as My Games for storing one's games.<ref>{{cite web |url=http://mygames.chessbase.com/ |title=Home |website=mygames.chessbase.com}}</ref>
Starting in 2007, [[Chess.com]] offered the content of the training program, Chess Mentor, to their customers online.<ref>{{cite web |url=http://www.chess.com/chessmentor/ |title=Chess Lessons - Learn with Online Courses |access-date=2007-12-14 |archive-url=https://web.archive.org/web/20071214214334/http://www.chess.com/chessmentor/ |archive-date=2007-12-14 |url-status=live }}</ref> Top GMs such as [[Sam Shankland]] and [[Walter Browne]] have contributed lessons.
== See also ==
* [[List of chess software]]
* [[History of chess engines]]
* [[Computer checkers]]
* [[Computer Go]]
* [[Computer Othello]]
* [[Computer shogi]]
==Notes==
{{reflist|group=Note|refs=
<ref name=Note1>The first number refers to the number of moves which must be made by each engine, the second number refers to the number of minutes allocated to make all of these moves. The repeating time control means that the time is reset after each multiple of this number of moves is reached. For example, in a 40/4 time control, each [[chess engine|engine]] would have 4 minutes to make 40 moves, then a new 4 minutes would be allocated for the next 40 moves and so on, until the game was complete.</ref>
}}
== References ==
{{reflist|colwidth=30em}}
{{Creative Commons text attribution notice|cc=bysa3|url=https://www.chessprogramming.org/index.php?title=Mikhail_Botvinnik&action=history|author(s)=Chess Programming Wiki}}
==Sources==
*{{Citation
|last=Hsu|first=Feng-hsiung|author-link=Feng-hsiung Hsu
|year=2002
|title=Behind Deep Blue: Building the Computer that Defeated the World Chess Champion
|publisher=[[Princeton University Press]]
|isbn=0-691-09065-3}}
*{{Citation
|surname1=Levy|given1=David|author-link1=David Levy (chess player)
|surname2=Newborn|given2=Monty
|year=1991
|title=How Computers Play Chess
|publisher=Computer Science Press
|isbn=0-7167-8121-2}}
* {{Citation|surname=Newborn|given=Monty|title=Computer Chess|publisher=Academic Press, New York|year=1975}}
*{{Citation
|last=Newborn|first=Monty
|year=1997
|title=Kasparov versus Deep Blue: Computer Chess Comes of Age
|publisher=Springer
|isbn=0-387-94820-1}} (This book actually covers computer chess from the early days through the first match between Deep Blue and Garry Kasparov.)
*{{Citation
|surname1=Nunn|given1=John|author-link1=John Nunn
|year=2002
|title=Secrets of Pawnless Endings
|publisher=[[Gambit Publications]]
|isbn=1-901983-65-X}}
*{{Citation|surname=Shannon|given=Claude E.|author-link=Claude Elwood Shannon|year=1950|title=Programming a Computer for Playing Chess|journal=Philosophical Magazine|volume=Ser.7, Vol. 41|issue=314|url=http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf|access-date=21 June 2009|url-status=dead|archive-url=https://web.archive.org/web/20100706211229/http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf|archive-date=6 July 2010}}
*[http://www.computerhistory.org/chess/ Mastering the Game: A History of Computer Chess] at [http://www.computerhistory.org/ Computer History Museum]
* [https://web.archive.org/web/20091028083247/http://www.geocities.com/SiliconValley/Lab/7378/comphis.htm Bill Wall's Computer Chess History Timeline]
==Further reading==
*[http://www.loopchess.com/fritz_reul_thesis_revision_1.pdf New Architectures in Computer Chess – Thesis on How to Build A Chess Engine]
*{{Citation|last=Coles|first=L. Stephen|title=Computer Chess: The Drosophila of AI|date=October 30, 2002|publisher=[[Dr. Dobb's Journal]]|url=http://www.ddj.com/hpc-high-performance-computing/184405171}}
*{{Citation
|last=Huberman (Liskov)|first=Barbara Jane|title=A program to play chess end games|year=1968|publisher=Stanford University Department of Computer Science, Technical Report CS 106, Stanford Artificial Intelligence Project Memo AI-65|author-link=Barbara Liskov}}
* Lasar, Matthew (2011). [https://arstechnica.com/gaming/news/2011/08/force-versus-heuristics-the-contentious-rise-of-computer-chess.ars Brute force or intelligence? The slow rise of computer chess]". ''[[Ars Technica]]''.
* 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). [http://www.cs.mcgill.ca/~newborn/TheoOctopusAtCasc06.pdf ''Theo and Octopus at the 2006 World Championship for Automated Reasoning Programs''], Seattle, Washington, August 18, 2006
*{{Citation|last=Stiller|first=Lewis|title=Multilinear Algebra and Chess Endgames|publisher=[[Mathematical Sciences Research Institute]], Games of No Chance, MSRI Publications, Volume 29|year=1996|location=Berkeley, California|url=http://www.msri.org/publications/books/Book29/files/stiller.pdf|access-date=21 June 2009}}
== External links ==
{{Wiktionary}}
{{Commons category|Computer chess}}
* [http://www.computerchess.org.uk/ccrl/4040/ List of chess engine ratings and game files in PGN format]
* [http://www.computerhistory.org/chess/ Mastering the Game: A History of Computer Chess] at the [[Computer History Museum]]
* [http://ed-thelen.org/comp-hist/ACM-ComputerChessWall.html ACM Computer Chess by Bill Wall]
* [https://www.chesshistory.com/winter/extra/computers.html "Computer Chess" by Edward Winter]
* [http://www.chessbin.com Computer Chess Information and Resources] {{Webarchive|url=https://web.archive.org/web/20190118031801/http://www.chessbin.com/ |date=2019-01-18 }} – blog following the creation of a computer chess engine
* [http://www.xs4all.nl/~timkr/chess2/honor.htm Defending Humanity's Honor], an article by [[Tim Krabbé]] about "anti-computer style" chess
* [http://horizonchess.com/FAQ/Winboard/egtb.html A guide to Endgame Tablebases]
* GameDev.net – Chess Programming by François-Dominic Laramée Part [http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-i-getting-started-r1014 1] {{Webarchive|url=https://web.archive.org/web/20110918175142/http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-i-getting-started-r1014 |date=2011-09-18 }} [http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-ii-data-structures-r1046 2] {{Webarchive|url=https://web.archive.org/web/20110927174532/http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-ii-data-structures-r1046 |date=2011-09-27 }} [http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-iii-move-generation-r1126 3] {{Webarchive|url=https://web.archive.org/web/20110919031614/http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-iii-move-generation-r1126 |date=2011-09-19 }} [http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-iv-basic-search-r1171 4] {{Webarchive|url=https://web.archive.org/web/20110919072227/http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-iv-basic-search-r1171 |date=2011-09-19 }} [http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-v-advanced-search-r1197 5] {{Webarchive|url=https://web.archive.org/web/20110920045740/http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-v-advanced-search-r1197 |date=2011-09-20 }} [http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-vi-evaluation-functions-r1208 6] {{Webarchive|url=https://web.archive.org/web/20110807031136/http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-vi-evaluation-functions-r1208 |date=2011-08-07 }}
* [http://www.frayn.net/beowulf/theory.html Colin Frayn's Computer Chess Theory Page]
* {{cite web|url= http://members.home.nl/matador/Inside%20Rebel.pdf |title="How REBEL Plays Chess" by Ed Schröder }} {{small|(268 KB)}}
* [http://plan9.bell-labs.com/~ken/chesseg.html "Play chess with God"] {{Webarchive|url=https://archive.today/20121129222242/http://plan9.bell-labs.com/~ken/chesseg.html |date=2012-11-29 }} – for playing chess against Ken Thompson's endgame database
* [http://www.chessprogramming.org Chess programming wiki]
* [http://talkchess.com/forum/index.php Computer Chess Club Forums]
* [http://www.youtube.com/watch?v=wljgxS7tZVE The Strongest Computer Chess Engines Over Time]
=== Media ===
*[http://video.google.com/videoplay?docid=-1583888480148765375 The History of Computer Chess: An AI Perspective] {{Webarchive|url=https://web.archive.org/web/20060614024002/http://video.google.com/videoplay?docid=-1583888480148765375 |date=2006-06-14 }} – a full lecture featuring Murray Campbell (IBM Deep Blue Project), Edward Feigenbaum, [[David Levy (chess)|David Levy]], John McCarthy, and Monty Newborn. at [http://www.computerhistory.org/ Computer History Museum]
{{Chess}}
{{Authority control}}
[[Category:Computer chess| ]]
[[Category:Electronic games]]
[[Category:Game artificial intelligence]]' |
All external links in the new text (all_links) | [
0 => 'https://spectrum.ieee.org/computing/software/checkers-solved',
1 => 'https://pubmed.ncbi.nlm.nih.gov/22530382/',
2 => 'https://doi.org/10.1177%2F0306312711424596',
3 => 'https://pubmed.ncbi.nlm.nih.gov/22530382',
4 => 'https://api.semanticscholar.org/CorpusID:968033',
5 => 'http://scid.sourceforge.net/',
6 => 'https://web.archive.org/web/20080820180940/http://www.convekta.com/about.asp',
7 => 'http://www.convekta.com/about.asp',
8 => 'http://www.exachess.com/',
9 => 'http://kalab.com/pgnviewer/',
10 => 'https://home.mis.u-picardie.fr/~furst/docs/Newell_Simon_Heuristic_Problem_Solving_1958.pdf',
11 => 'https://doi.org/10.1287%2Fopre.6.1.1',
12 => 'https://books.google.com/books?id=_n1vr0_RbXoC&pg=PA827',
13 => 'https://archive.org/stream/byte-magazine-1978-12/1978_12_BYTE_03-12_Life#page/n85/mode/2up',
14 => 'https://archive.org/stream/byte-magazine-1984-03-rescan/1984_03_BYTE_09-03_Simulation#page/n289/mode/2up',
15 => 'http://www.cgwmuseum.org/galleries/index.php?year=1982&pub=6&id=3',
16 => 'http://www.rebel.nl/anand.htm',
17 => 'http://www.chessbase.com/newsdetail.asp?newsid=2476',
18 => 'https://www.nytimes.com/2006/12/05/crosswords/chess/05cnd-chess.html',
19 => 'http://www.ddj.com/hpc-high-performance-computing/184405171',
20 => 'http://www.aaai.org/ojs/index.php/aimagazine/article/viewFile/753/671',
21 => 'https://web.archive.org/web/20110930232108/https://theweekinchess.com/html/twic771.html#13',
22 => 'https://theweekinchess.com/html/twic771.html#13',
23 => 'http://hiarcs.net/forums/viewtopic.php?t=2537&start=67',
24 => 'http://www.dw.com/en/world-chess-champion-magnus-carlsen-the-computer-never-has-been-an-opponent/a-19186058',
25 => 'https://www.npr.org/sections/alltechconsidered/2016/10/24/499162905/20-years-later-humans-still-no-match-for-computers-on-the-chessboard',
26 => 'https://archive.org/stream/byte-magazine-1978-10/1978_10_BYTE_03-10_Chess_for_the_Microcomputer#page/n167/mode/2up',
27 => 'http://kirill-kryukov.com/chess/tablebases-online/',
28 => 'http://www.xs4all.nl/~timkr/chess2/diary_16.htm',
29 => 'http://tb7.chessok.com/shared-positions',
30 => 'https://www.chess.com/forum/view/endgames/who-wins-from-this-puzzle',
31 => 'https://web.archive.org/web/20170627041247/http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=9380',
32 => 'https://lichess.org/blog/W3WeMyQAACQAdfAL/7-piece-syzygy-tablebases-are-complete',
33 => 'https://github.com/official-stockfish/Stockfish/wiki/Useful-data',
34 => 'https://tcec-chess.com/articles/TCEC_Openings_FAQ.html',
35 => 'https://web.archive.org/web/20120301182317/http://www.husvankempen.de/nunn/rating.htm',
36 => 'http://www.husvankempen.de/nunn/rating.htm',
37 => 'http://www.computerschach.de/index.php?option=com_wrapper&Itemid=242',
38 => 'http://ssdf.bosjo.net/list.htm',
39 => 'http://wbec-ridderkerk.nl/html/BayesianElo_ed15.htm',
40 => 'https://rebel13.nl/misc/gambit-rating-list.html',
41 => 'http://fastgm.de/',
42 => 'https://web.archive.org/web/20190125041233/http://inwoba.de/bayes.html',
43 => 'http://www.inwoba.de/bayes.html',
44 => 'https://web.archive.org/web/20220121151824/http://ccrl.chessdom.com/',
45 => 'https://proceedings.neurips.cc/paper/1994/file/d7322ed717dedf1eb4e6e52a37ea7bcd-Paper.pdf',
46 => 'https://arxiv.org/abs/1509.01549v1',
47 => 'https://arxiv.org/abs/1712.01815',
48 => 'https://arxiv.org/archive/cs.AI',
49 => 'https://arxiv.org/abs/1911.08265',
50 => 'https://ui.adsabs.harvard.edu/abs/2020Natur.588..604S',
51 => 'https://doi.org/10.1038%2Fs41586-020-03051-4',
52 => 'https://pubmed.ncbi.nlm.nih.gov/33361790',
53 => 'https://api.semanticscholar.org/CorpusID:208158225',
54 => 'https://www.apply.computer-shogi.org/wcsc28/appeal/the_end_of_genesis_T.N.K.evolution_turbo_type_D/nnue.pdf',
55 => 'https://github.com/asdfjkl/nnue/blob/main/nnue_en.pdf',
56 => 'https://github.com/nodchip/Stockfish/releases/tag/stockfish-nnue-2020-05-30',
57 => 'https://blog.stockfishchess.org/post/625828091343896577/introducing-nnue-evaluation',
58 => 'https://github.com/official-stockfish/Stockfish/issues/2823#issue-665540175',
59 => 'https://web.archive.org/web/20031124134110/http://www.turingarchive.org/browse.php/B/7',
60 => 'http://www.chessgames.com/perl/chessgame?gid=1356927',
61 => 'https://archive.today/20120721202324/http://www.chessville.com/BillWall/EarlyComputerChessPrograms.htm',
62 => 'http://www.chessgames.com/perl/chessgame?gid=1238081',
63 => 'https://www.bell-labs.com/usr/dmr/www/ken-games.html',
64 => 'https://link.springer.com/content/pdf/bbm:978-1-4612-5515-4%2F1.pdf',
65 => 'https://www.computerhistory.org/chess/orl-4334404555680/',
66 => 'https://archive.org/stream/byte-magazine-1981-01/1981_01_BYTE_06-01_Hand-held_Computers#page/n293/mode/2up',
67 => 'https://web.cecs.pdx.edu/~trent/gnu/bull/02/nb.html#SEC6',
68 => 'http://www.rybkachess.com/docs/PADERBORNCOMPUTER.htm',
69 => 'http://www.chessbase.com/newsdetail.asp?newsid=6361',
70 => 'https://web.archive.org/web/20140330145657/http://www.chessvibes.com/reports/rybka-disqualified-and-banned-from-world-computer-chess-championships/',
71 => 'http://www.chessvibes.com/reports/rybka-disqualified-and-banned-from-world-computer-chess-championships/',
72 => 'http://www.chessbase.com/newsdetail.asp?newsid=7791',
73 => 'https://github.com/ynasu87/nnue/blob/master/docs/nnue.pdf',
74 => 'http://www.ismenio.com/chess_cc1.html',
75 => 'https://research.tilburguniversity.edu/en/publications/the-7th-world-computer-chess-championship-report-on-the-tournamen',
76 => 'http://rebel13.nl/rebel13/rebel%2013.html',
77 => 'http://rebel13.nl/dedicated/dedicated%20as%20uci.html',
78 => 'https://web.archive.org/web/20181203055650/http://rebel13.nl/download/more%20dos%20oldies.html',
79 => 'http://rebel13.nl/download/more%20dos%20oldies.html',
80 => 'http://www.cis.uab.edu/info/faculty/hyatt/hyatt.html',
81 => 'https://web.archive.org/web/20100706211229/http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf',
82 => 'http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf',
83 => 'https://doi.org/10.1016%2F0097-3165(81)90016-9',
84 => 'https://web.archive.org/web/19970620110903/http://www.chessclub.com/CoffeeHouse.html',
85 => 'http://www.chessclub.com/CoffeeHouse.html',
86 => 'http://www.freechess.org/',
87 => 'https://web.archive.org/web/19981212025054/http://www.freechess.org/',
88 => 'http://www.iccf-webchess.com/',
89 => 'https://web.archive.org/web/20040831025215/http://www.iccf-webchess.com/',
90 => 'https://web.archive.org/web/20071006143047/http://www.chess.com/echess/',
91 => 'http://www.chess.com/echess/',
92 => 'https://web.archive.org/web/20131217045511/http://play.chessbase.com/js/apps/playchess/',
93 => 'http://play.chessbase.com/js/apps/playchess/',
94 => 'https://web.archive.org/web/20060408052731/http://chess.emrald.net/',
95 => 'http://chess.emrald.net/',
96 => 'http://chesstempo.com/',
97 => 'https://web.archive.org/web/20070613100847/http://chesstempo.com/',
98 => 'http://www.chess.com/tactics',
99 => 'https://web.archive.org/web/20080218082614/http://www.chess.com/tactics',
100 => 'https://web.archive.org/web/20150504000924/http://training.chessbase.com/js/apps/Training/',
101 => 'http://training.chessbase.com/js/apps/Training/',
102 => 'https://web.archive.org/web/20000511014758/http://www.chessbase-online.com/',
103 => 'http://www.chessbase-online.com/',
104 => 'http://www.chesslab.com/PositionSearch.html',
105 => 'https://web.archive.org/web/19990219143550/http://www.chesslab.com/PositionSearch.html',
106 => 'http://www31.ws26.temphost.nl/NICBase/',
107 => 'https://web.archive.org/web/20021008054123/http://www31.ws26.temphost.nl/NICBase/',
108 => 'http://www.shredderchess.com/play-chess-online.html',
109 => 'https://web.archive.org/web/20061205205401/http://www.shredderchess.com/play-chess-online.html',
110 => 'http://fritz.chessbase.com/',
111 => 'http://mygames.chessbase.com/',
112 => 'http://www.chess.com/chessmentor/',
113 => 'https://web.archive.org/web/20071214214334/http://www.chess.com/chessmentor/',
114 => 'https://www.facebook.com/chessstudioapp/',
115 => 'http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=9380',
116 => 'http://ccrl.chessdom.com/',
117 => 'http://kirill-kryukov.com/chess/discussion-board/viewtopic.php?f=7&t=2808',
118 => 'http://adamsccpages.blogspot.co.uk/2012/05/ccrl.html',
119 => 'https://cd.tcecbeta.club/archive.html?season=15&div=sf&game=1',
120 => 'https://www.wikidata.org/wiki/Q1122588#identifiers',
121 => 'https://www.chessprogramming.org/index.php?title=Mikhail_Botvinnik&action=history',
122 => 'http://www.computerhistory.org/chess/',
123 => 'http://www.computerhistory.org/',
124 => 'https://web.archive.org/web/20091028083247/http://www.geocities.com/SiliconValley/Lab/7378/comphis.htm',
125 => 'http://www.loopchess.com/fritz_reul_thesis_revision_1.pdf',
126 => 'https://arstechnica.com/gaming/news/2011/08/force-versus-heuristics-the-contentious-rise-of-computer-chess.ars',
127 => 'http://www.cs.mcgill.ca/~newborn/TheoOctopusAtCasc06.pdf',
128 => 'http://www.msri.org/publications/books/Book29/files/stiller.pdf',
129 => 'http://www.computerchess.org.uk/ccrl/4040/',
130 => 'http://ed-thelen.org/comp-hist/ACM-ComputerChessWall.html',
131 => 'https://www.chesshistory.com/winter/extra/computers.html',
132 => 'http://www.chessbin.com/',
133 => 'https://web.archive.org/web/20190118031801/http://www.chessbin.com/',
134 => 'http://www.xs4all.nl/~timkr/chess2/honor.htm',
135 => 'http://horizonchess.com/FAQ/Winboard/egtb.html',
136 => 'http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-i-getting-started-r1014',
137 => 'https://web.archive.org/web/20110918175142/http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-i-getting-started-r1014',
138 => 'http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-ii-data-structures-r1046',
139 => 'https://web.archive.org/web/20110927174532/http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-ii-data-structures-r1046',
140 => 'http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-iii-move-generation-r1126',
141 => 'https://web.archive.org/web/20110919031614/http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-iii-move-generation-r1126',
142 => 'http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-iv-basic-search-r1171',
143 => 'https://web.archive.org/web/20110919072227/http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-iv-basic-search-r1171',
144 => 'http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-v-advanced-search-r1197',
145 => 'https://web.archive.org/web/20110920045740/http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-v-advanced-search-r1197',
146 => 'http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-vi-evaluation-functions-r1208',
147 => 'https://web.archive.org/web/20110807031136/http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-vi-evaluation-functions-r1208',
148 => 'http://www.frayn.net/beowulf/theory.html',
149 => 'http://members.home.nl/matador/Inside%20Rebel.pdf',
150 => 'http://plan9.bell-labs.com/~ken/chesseg.html',
151 => 'https://archive.today/20121129222242/http://plan9.bell-labs.com/~ken/chesseg.html',
152 => 'http://www.chessprogramming.org/',
153 => 'http://talkchess.com/forum/index.php',
154 => 'http://www.youtube.com/watch?v=wljgxS7tZVE',
155 => 'http://video.google.com/videoplay?docid=-1583888480148765375',
156 => 'https://web.archive.org/web/20060614024002/http://video.google.com/videoplay?docid=-1583888480148765375',
157 => 'https://d-nb.info/gnd/4010456-4',
158 => 'http://olduli.nli.org.il/F/?func=find-b&local_base=NLX10&find_code=UID&request=987007558867005171',
159 => 'https://id.loc.gov/authorities/sh94007898'
] |
Links in the page, before the edit (old_links) | [
0 => 'http://www.cis.uab.edu/info/faculty/hyatt/hyatt.html',
1 => 'http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf',
2 => 'http://www.computerhistory.org/chess/',
3 => 'http://www.computerhistory.org/',
4 => 'http://video.google.com/videoplay?docid=-1583888480148765375',
5 => 'http://www.xs4all.nl/~timkr/chess2/honor.htm',
6 => 'http://horizonchess.com/FAQ/Winboard/egtb.html',
7 => 'http://www.frayn.net/beowulf/theory.html',
8 => 'http://plan9.bell-labs.com/~ken/chesseg.html',
9 => 'http://www.ddj.com/hpc-high-performance-computing/184405171',
10 => 'http://www.cs.mcgill.ca/~newborn/TheoOctopusAtCasc06.pdf',
11 => 'http://www.loopchess.com/fritz_reul_thesis_revision_1.pdf',
12 => 'http://www.chessbin.com/',
13 => 'http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-i-getting-started-r1014',
14 => 'http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-ii-data-structures-r1046',
15 => 'http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-iii-move-generation-r1126',
16 => 'http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-iv-basic-search-r1171',
17 => 'http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-v-advanced-search-r1197',
18 => 'http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-vi-evaluation-functions-r1208',
19 => 'http://ed-thelen.org/comp-hist/ACM-ComputerChessWall.html',
20 => 'http://www.husvankempen.de/nunn/rating.htm',
21 => 'http://www.computerschach.de/index.php?option=com_wrapper&Itemid=242',
22 => 'http://ssdf.bosjo.net/list.htm',
23 => 'http://wbec-ridderkerk.nl/html/BayesianElo_ed15.htm',
24 => 'http://www.rebel.nl/anand.htm',
25 => 'http://www.aaai.org/ojs/index.php/aimagazine/article/viewFile/753/671',
26 => 'http://hiarcs.net/forums/viewtopic.php?t=2537&start=67',
27 => 'http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=9380',
28 => 'http://www.computerchess.org.uk/ccrl/4040/',
29 => 'http://www.chessbase.com/newsdetail.asp?newsid=2476',
30 => 'http://kirill-kryukov.com/chess/tablebases-online/',
31 => 'http://www.xs4all.nl/~timkr/chess2/diary_16.htm',
32 => 'http://www.chessgames.com/perl/chessgame?gid=1356927',
33 => 'http://www.chessgames.com/perl/chessgame?gid=1238081',
34 => 'http://www.rybkachess.com/docs/PADERBORNCOMPUTER.htm',
35 => 'http://www.chessbase.com/newsdetail.asp?newsid=6361',
36 => 'http://www.chessbase.com/newsdetail.asp?newsid=7791',
37 => 'http://www.chessvibes.com/reports/rybka-disqualified-and-banned-from-world-computer-chess-championships/',
38 => 'http://www.cgwmuseum.org/galleries/index.php?year=1982&pub=6&id=3',
39 => 'http://talkchess.com/forum/index.php',
40 => 'https://web.archive.org/web/20140330145657/http://www.chessvibes.com/reports/rybka-disqualified-and-banned-from-world-computer-chess-championships/',
41 => 'https://archive.org/stream/byte-magazine-1984-03-rescan/1984_03_BYTE_09-03_Simulation#page/n289/mode/2up',
42 => 'https://archive.org/stream/byte-magazine-1978-12/1978_12_BYTE_03-12_Life#page/n85/mode/2up',
43 => 'https://archive.org/stream/byte-magazine-1978-10/1978_10_BYTE_03-10_Chess_for_the_Microcomputer#page/n167/mode/2up',
44 => 'https://archive.org/stream/byte-magazine-1981-01/1981_01_BYTE_06-01_Hand-held_Computers#page/n293/mode/2up',
45 => 'http://www.dw.com/en/world-chess-champion-magnus-carlsen-the-computer-never-has-been-an-opponent/a-19186058',
46 => 'https://web.archive.org/web/20091028083247/http://www.geocities.com/SiliconValley/Lab/7378/comphis.htm',
47 => 'https://www.nytimes.com/2006/12/05/crosswords/chess/05cnd-chess.html',
48 => 'https://arstechnica.com/gaming/news/2011/08/force-versus-heuristics-the-contentious-rise-of-computer-chess.ars',
49 => 'http://tb7.chessok.com/shared-positions',
50 => 'https://www.chess.com/forum/view/endgames/who-wins-from-this-puzzle',
51 => 'http://kirill-kryukov.com/chess/discussion-board/viewtopic.php?f=7&t=2808',
52 => 'http://adamsccpages.blogspot.co.uk/2012/05/ccrl.html',
53 => 'https://home.mis.u-picardie.fr/~furst/docs/Newell_Simon_Heuristic_Problem_Solving_1958.pdf',
54 => 'http://www.chessprogramming.org/',
55 => 'https://web.archive.org/web/20071006143047/http://www.chess.com/echess/',
56 => 'https://web.archive.org/web/20131217045511/http://play.chessbase.com/js/apps/playchess/',
57 => 'https://web.archive.org/web/20150504000924/http://training.chessbase.com/js/apps/Training/',
58 => 'http://fritz.chessbase.com/',
59 => 'http://mygames.chessbase.com/',
60 => 'https://web.archive.org/web/20000511014758/http://www.chessbase-online.com/',
61 => 'http://rebel13.nl/rebel13/rebel%2013.html',
62 => 'http://rebel13.nl/dedicated/dedicated%20as%20uci.html',
63 => 'http://rebel13.nl/download/more%20dos%20oldies.html',
64 => 'https://web.cecs.pdx.edu/~trent/gnu/bull/02/nb.html#SEC6',
65 => 'https://www.computerhistory.org/chess/orl-4334404555680/',
66 => 'https://cd.tcecbeta.club/archive.html?season=15&div=sf&game=1',
67 => 'https://www.bell-labs.com/usr/dmr/www/ken-games.html',
68 => 'http://www.chessclub.com/CoffeeHouse.html',
69 => 'https://web.archive.org/web/19970620110903/http://www.chessclub.com/CoffeeHouse.html',
70 => 'http://www.freechess.org/',
71 => 'https://web.archive.org/web/19981212025054/http://www.freechess.org/',
72 => 'http://www.iccf-webchess.com/',
73 => 'https://web.archive.org/web/20040831025215/http://www.iccf-webchess.com/',
74 => 'https://web.archive.org/web/20060408052731/http://chess.emrald.net/',
75 => 'http://chess.emrald.net/',
76 => 'http://chesstempo.com/',
77 => 'https://web.archive.org/web/20070613100847/http://chesstempo.com/',
78 => 'http://www.chess.com/tactics',
79 => 'https://web.archive.org/web/20080218082614/http://www.chess.com/tactics',
80 => 'http://www.chesslab.com/PositionSearch.html',
81 => 'https://web.archive.org/web/19990219143550/http://www.chesslab.com/PositionSearch.html',
82 => 'http://www31.ws26.temphost.nl/NICBase/',
83 => 'https://web.archive.org/web/20021008054123/http://www31.ws26.temphost.nl/NICBase/',
84 => 'http://www.shredderchess.com/play-chess-online.html',
85 => 'https://web.archive.org/web/20061205205401/http://www.shredderchess.com/play-chess-online.html',
86 => 'http://www.chess.com/chessmentor/',
87 => 'https://web.archive.org/web/20071214214334/http://www.chess.com/chessmentor/',
88 => 'https://web.archive.org/web/20120301182317/http://www.husvankempen.de/nunn/rating.htm',
89 => 'https://web.archive.org/web/20100706211229/http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf',
90 => 'http://scid.sourceforge.net/',
91 => 'http://www.convekta.com/about.asp',
92 => 'https://web.archive.org/web/20080820180940/http://www.convekta.com/about.asp',
93 => 'http://www.exachess.com/',
94 => 'http://kalab.com/pgnviewer/',
95 => 'https://www.facebook.com/chessstudioapp/',
96 => 'http://www.youtube.com/watch?v=wljgxS7tZVE',
97 => 'https://www.npr.org/sections/alltechconsidered/2016/10/24/499162905/20-years-later-humans-still-no-match-for-computers-on-the-chessboard',
98 => 'https://research.tilburguniversity.edu/en/publications/the-7th-world-computer-chess-championship-report-on-the-tournamen',
99 => 'https://books.google.com/books?id=_n1vr0_RbXoC&pg=PA827',
100 => 'https://www.chesshistory.com/winter/extra/computers.html',
101 => 'http://www.ismenio.com/chess_cc1.html',
102 => 'https://www.wikidata.org/wiki/Q1122588#identifiers',
103 => 'http://www.msri.org/publications/books/Book29/files/stiller.pdf',
104 => 'http://members.home.nl/matador/Inside%20Rebel.pdf',
105 => 'https://d-nb.info/gnd/4010456-4',
106 => 'https://blog.stockfishchess.org/post/625828091343896577/introducing-nnue-evaluation',
107 => 'https://github.com/official-stockfish/Stockfish/issues/2823#issue-665540175',
108 => 'https://github.com/ynasu87/nnue/blob/master/docs/nnue.pdf',
109 => 'https://theweekinchess.com/html/twic771.html#13',
110 => 'https://web.archive.org/web/20110930232108/https://theweekinchess.com/html/twic771.html#13',
111 => 'http://www.chess.com/echess/',
112 => 'http://training.chessbase.com/js/apps/Training/',
113 => 'http://ccrl.chessdom.com/',
114 => 'https://proceedings.neurips.cc/paper/1994/file/d7322ed717dedf1eb4e6e52a37ea7bcd-Paper.pdf',
115 => 'https://www.apply.computer-shogi.org/wcsc28/appeal/the_end_of_genesis_T.N.K.evolution_turbo_type_D/nnue.pdf',
116 => 'https://github.com/asdfjkl/nnue/blob/main/nnue_en.pdf',
117 => 'https://github.com/nodchip/Stockfish/releases/tag/stockfish-nnue-2020-05-30',
118 => 'https://rebel13.nl/misc/gambit-rating-list.html',
119 => 'http://fastgm.de/',
120 => 'https://web.archive.org/web/20190125041233/http://inwoba.de/bayes.html',
121 => 'http://www.inwoba.de/bayes.html',
122 => 'https://arxiv.org/abs/1509.01549v1',
123 => 'https://ui.adsabs.harvard.edu/abs/2020Natur.588..604S',
124 => 'https://api.semanticscholar.org/CorpusID:208158225',
125 => 'https://link.springer.com/content/pdf/bbm:978-1-4612-5515-4%2F1.pdf',
126 => 'http://play.chessbase.com/js/apps/playchess/',
127 => 'http://www.chessbase-online.com/',
128 => 'https://web.archive.org/web/20181203055650/http://rebel13.nl/download/more%20dos%20oldies.html',
129 => 'https://spectrum.ieee.org/computing/software/checkers-solved',
130 => 'https://pubmed.ncbi.nlm.nih.gov/22530382/',
131 => 'https://api.semanticscholar.org/CorpusID:968033',
132 => 'https://web.archive.org/web/20031124134110/http://www.turingarchive.org/browse.php/B/7',
133 => 'https://doi.org/10.1177%2F0306312711424596',
134 => 'https://pubmed.ncbi.nlm.nih.gov/22530382',
135 => 'https://doi.org/10.1287%2Fopre.6.1.1',
136 => 'https://arxiv.org/abs/1712.01815',
137 => 'https://arxiv.org/abs/1911.08265',
138 => 'https://doi.org/10.1038%2Fs41586-020-03051-4',
139 => 'https://pubmed.ncbi.nlm.nih.gov/33361790',
140 => 'https://doi.org/10.1016%2F0097-3165(81)90016-9',
141 => 'https://id.loc.gov/authorities/sh94007898',
142 => 'https://arxiv.org/archive/cs.AI',
143 => 'https://lichess.org/blog/W3WeMyQAACQAdfAL/7-piece-syzygy-tablebases-are-complete',
144 => 'https://github.com/official-stockfish/Stockfish/wiki/Useful-data',
145 => 'https://tcec-chess.com/articles/TCEC_Openings_FAQ.html',
146 => 'https://web.archive.org/web/20170627041247/http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=9380',
147 => 'https://web.archive.org/web/20190118031801/http://www.chessbin.com/',
148 => 'https://web.archive.org/web/20110918175142/http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-i-getting-started-r1014',
149 => 'https://web.archive.org/web/20110927174532/http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-ii-data-structures-r1046',
150 => 'https://web.archive.org/web/20110919031614/http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-iii-move-generation-r1126',
151 => 'https://web.archive.org/web/20110919072227/http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-iv-basic-search-r1171',
152 => 'https://web.archive.org/web/20110920045740/http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-v-advanced-search-r1197',
153 => 'https://web.archive.org/web/20110807031136/http://www.gamedev.net/page/resources/_/reference/programming/artificial-intelligence/gaming/chess-programming-part-vi-evaluation-functions-r1208',
154 => 'http://olduli.nli.org.il/F/?func=find-b&local_base=NLX10&find_code=UID&request=987007558867005171',
155 => 'https://archive.today/20121129222242/http://plan9.bell-labs.com/~ken/chesseg.html',
156 => 'https://web.archive.org/web/20220121151824/http://ccrl.chessdom.com/',
157 => 'https://web.archive.org/web/20060614024002/http://video.google.com/videoplay?docid=-1583888480148765375',
158 => 'https://archive.today/20120721202324/http://www.chessville.com/BillWall/EarlyComputerChessPrograms.htm',
159 => 'https://www.chessprogramming.org/index.php?title=Mikhail_Botvinnik&action=history'
] |
