Jump to content

Chess engine

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Oscar (talk | contribs) at 22:31, 10 September 2018 (updating url to moved website). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In computer chess, a chess engine is a computer program that analyses chess or chess variant positions and makes decisions on the best chess moves.[1] The chess engine decides which moves to make, but typically does not interact directly with the user. Most chess engines do not have their own graphical user interface (GUI) but are rather console applications that communicate with a GUI such as Chessbase, XBoard, WinBoard or Gnome Chess via a standard protocol. This allows the user to play against multiple engines without learning a new user interface for each, and allows different engines to play against each other.

Interface protocol

The command-line interface of GNU Chess became the initial de facto standard, called the "Chess Engine Communication Protocol" and was first supported by XBoard. When XBoard was ported to the Windows operating system as WinBoard, this protocol was popularly renamed to 'WinBoard Protocol'. The WinBoard Protocol was itself upgraded and the two versions of the protocols are referred to as: 'WinBoard Protocol 1' (original version) and 'WinBoard Protocol 2' (newer version). There is another protocol, the Universal Chess Interface. Some engines support both major protocols, and each protocol has its supporters. The Winboard Protocol is more popular but many chess engine developers feel that the Universal Chess Interface is easier to implement. Some interfaces support both protocols, while others, such as WinBoard, support only one and depend on subsidiary interpreters to translate.

Increasing strength

Chess engines increase in playing strength each year. This is partly due to the increase in processing power that enables calculations to be made to ever greater depths in a given time. In addition, programming techniques have improved, enabling the engines to be more selective in the lines that they analyze and to acquire a better positional understanding. A chess engine often uses a vast previously computed opening "book" to increase its playing strength for the first several moves up to possibly 20 moves or more in deeply analyzed lines.[citation needed]

Some chess engines maintain a database of chess positions, along with previously computed evaluations and best moves, in effect, a kind of "dictionary" of recurring chess positions. Since these positions are pre-computed, the engine merely plays one of the indicated moves in the database, thereby saving compute time, resulting in stronger, more rapid play.

Some chess engines use endgame tablebases to increase their playing strength during the endgame. An endgame tablebase includes all possible endgame positions with small groups of material. Each position is conclusively determined as a win, loss, or draw for the player whose turn it is to move, and the number of moves to the end with best play by both sides. The tablebase identifies for every position the move which will win the fastest against an optimal defense, or the move that will lose the slowest against an optimal offense. Such tablebases are available for all chess endgames with seven pieces or fewer (trivial endgame positions are excluded, such as six white pieces versus a lone black king).[2][3]

When the maneuvering in an ending to achieve an irreversible improvement takes more moves than the horizon of calculation of a chess engine, an engine is not guaranteed to find the best move without the use of an endgame tablebase, and in many cases can fall foul of the fifty-move rule as a result. Many engines use permanent brain (speculative analysis while the opponent is thinking) as a method to increase their strength.

Distributed computing is also used to improve the software code of chess engines. In 2013, the developers of the Stockfish chess playing program started using distributed computing to make improvements in the software code.[4][5][6] As of June 2017, a total of more than 745 years of CPU time has been used to play more than 485 million chess games, with the results being used to make small and incremental improvements to the chess-playing software.[7]

Comparisons

Tournaments

The results of computer tournaments give one view of the relative strengths of chess engines. However, tournaments do not play a statistically significant number of games for accurate strength determination. In fact, the number of games that need to be played between fairly evenly matched engines, in order to achieve significance, runs into the thousands and is, therefore, impractical within the framework of a tournament.[8] Most tournaments also allow any types of hardware, so only engine/hardware combinations are being compared.

Historically, commercial programs have been the strongest engines. If an amateur engine wins a tournament or otherwise performs well (for example, Zappa in 2005), then it is quickly commercialized. Titles gained in these tournaments garner much prestige for the winning programs, and are thus used for marketing purposes.

Ratings

Chess engine rating lists aim to provide statistically significant measures of relative engine strength. These lists play multiple games between engines on standard hardware platforms, so that processor differences are factored out. Some also standardize the opening books, in an attempt to measure the strength differences of the engines only. These lists not only provide a ranking, but also margins of error on the given ratings. Also rating lists typically play games continuously, publishing many updates per year, compared to tournaments which only take place annually.

There are a number of factors that vary among the chess engine rating lists:

  • Time control. Longer time controls, such as 40 moves in 120 minutes, are better suited for determining tournament play strength, but also make testing more time-consuming.
  • Hardware used. Faster hardware with more memory leads to stronger play.
  • 64-bit (vs. 32-bit) hardware and operating systems favor bitboard-based programs
  • Multiprocessor vs. single processor hardware.
  • Ponder settings (speculative analysis while the opponent is thinking) aka Permanent Brain.
  • Transposition table sizes.
  • Opening book settings.

These differences affect the results, and make direct comparisons between rating lists difficult.

Rating list Time control
(moves/minutes) 		Year
started 		Last updated Engine/platform
entries 		Games
played 		Top three engines Rating
CCRL[9] 40/40[a]
Ponder OFF 		2005 February 24, 2018 2050 798,040 Stockfish 9 x64
Houdini 6.0 x64
Komodo 11.2 x64
 3449
3411
3405
CEGT[10] 40/20[b]
Ponder OFF 		2006 February 25, 2018 1555 1,107,155 Stockfish 9.0 x64
Houdini 6.0 x64
Komodo 11.2 x64
 3504
3442
3422
IPON[11] 5m+3s
~16min/game
Ponder ON 		2006 February 5, 2018 203 529,930 Stockfish 9
Houdini 6.02
Komodo 11.2.2 		3380
3350
3319
  • Note that the listings in the above table only count the best entry for a given engine.

These ratings, although calculated by using the Elo system (or similar rating methods), have no direct relation to FIDE Elo ratings or to other chess federation ratings of human players. Except for some man versus machine games which the SSDF had organized many years ago (which were far from today's level), there is no calibration between any of these rating lists and player pools. Hence, the results which matter are the ranks and the differences between the ratings, and not the absolute values. Also, each list calibrates their Elo via a different method. Therefore, no Elo comparisons can be made between the lists. Nevertheless, in view of recent man versus machine matches, it is generally undisputed that top chess engines are rated at least in the range of the top human players, and probably significantly higher.[citation needed]

Missing from many rating lists are IPPOLIT and its derivatives. Although very strong and open source, there are allegations from commercial software interests that they were derived from disassembled binary of Rybka.[12] Due to the controversy, all these engines have been blacklisted from many tournaments and rating lists. Rybka in turn was accused of being based on Fruit,[13] and in June 2011, the ICGA formally claimed Rybka was derived from Fruit and Crafty and banned Rybka from the International Computer Games Association World Computer Chess Championship, and revoked its previous victories (2007, 2008, 2009, and 2010).[14] The ICGA received some criticism for this decision.[15] Rybka is still included on several society ranking lists.

Test suites

Engines can be tested by measuring their performance on specific positions. Typical is the use of test suites where for each given position there is one best move to find. These positions can be geared towards positional, tactical or endgame play. The Nolot test suite, for instance, focuses on deep sacrifices.[16] The BT2450 and BT2630 test suites measure the tactical capability of a chess engine and have been used by REBEL.[17][18] There is also a general test suite called Brilliancy which was compiled mostly from How to Reassess Your Chess Workbook.[19] The Strategic Test Suite (STS) tests an engine's strategical strength.[20] Another modern test suite is Nightmare II which contains 30 chess puzzles.[21][irrelevant citation]

Categorizations

Dedicated hardware

These chess playing systems include custom hardware or run on supercomputers.

Commercial dedicated computers

In the 1980s and early 1990s, there was a competitive market for dedicated chess computers. This market changed in the mid-90s when computers with dedicated processors could no longer compete with the fast processors in personal computers. Nowadays, most dedicated units sold are of beginner and intermediate strength.

Historical

These chess programs run on obsolete hardware.

Kasparov versus the World (chess game played with computer assistance)

In 1999, Garry Kasparov played a chess game "Kasparov versus the World" over the Internet, hosted by the MSN Gaming Zone. Both sides used computer (chess engine) assistance. The "World Team" included participation of over 50,000 people from more than 75 countries, deciding their moves by plurality vote. The game lasted four months, with Kasparov playing "g7" on his 62nd move and announcing a forced checkmate in 28 moves found with the computer program Deep Junior. The World Team voters resigned on October 22. After the game Kasparov said "It is the greatest game in the history of chess. The sheer number of ideas, the complexity, and the contribution it has made to chess make it the most important game ever played."[24]

Engines for chess variants

Some chess engines have been developed to play chess variants, adding the necessary code to simulate non-standard chess pieces, or to analyze play on non-standard boards. ChessV and Fairy-Max, for example, are both capable of playing variants on a chessboard up to 12×8 in size, such as Capablanca Chess (10×8 board).

For larger boards however, there are few chess engines that can play effectively, and indeed chess games played on an unbounded chessboard (infinite chess) are virtually untouched by chess-playing software.

See also

Notes

  1. ^ Also available: 40 moves in 4 minutes
  2. ^ Also available: 40 moves in 4 minutes, 40 moves in 120 minutes

References

  1. ^ blog.chess.com Creating a chess engine from scratch (Part 1: Basics), Link date 28 June 2012
  2. ^ http://tb7.chessok.com Lomonosov website allowing registered user to access 7-piece tablebase, and a forum with positions found.
  3. ^ "Who wins from this? (chess puzzle)" An example chess position found from the Lomonosov chess tablebase.
  4. ^ "Stockfish Testing Framework". tests.stockfishchess.org. Retrieved 7 March 2014.
  5. ^ "Get Involved". stockfishchess.org. Retrieved 8 March 2014.
  6. ^ Costalba, Marco (1 May 2013). "Fishtest Distributed Testing Framework". talkchess.com. Retrieved 18 April 2014.
  7. ^ "Stockfish Testing Framework - Users". test.stockfishchess.org. Retrieved 17 June 2017.
  8. ^ "mizarchessengine.com". Retrieved 25 September 2016.
  9. ^ "CCRL 40/40 - Index". November 5, 2016. Retrieved November 6, 2016.
  10. ^ "CEGT 40/20". Chess Engines Grand Tournament. February 7, 2016. Retrieved February 9, 2016.
  11. ^ "IPON". IPON. November 16, 2016. Retrieved February 3, 2016.
  12. ^ Chess engine controversy at chessvibes.com, retrieved 28/May/2010
  13. ^ Evaluation
  14. ^ Rybka disqualified and banned from World Computer Chess Championships | ChessVibes
  15. ^ Riis, Dr. Søren (January 2, 2012). "A Gross Miscarriage of Justice in Computer Chess (part one)". Chessbase News. Retrieved 19 February 2012.
  16. ^ Nolot test suite
  17. ^ BT2450 test suite
  18. ^ Rosenboom, Manfred. "Rebel Century FAQ: 3. Using Rebel". Retrieved 25 September 2016.
  19. ^ Brilliancy suite TalkChess forum
  20. ^ [1] Strategic Test Suite
  21. ^ [2] Nightmare II
  22. ^ Sousa, Ismenio. "Fidelity Chess Challenger 1 - World's First Chess Computer". Retrieved 25 September 2016.
  23. ^ "Microchess". Retrieved 25 September 2016.
  24. ^ Harding, T. (2002). 64 Great Chess Games, Dublin: Chess Mail. ISBN 0-9538536-4-0.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Chess_engine&oldid=858981118"