Thursday, November 8, 2012

Chess Engine

A chess engine is a computer program that calculates chess position and chess moves.[1]
The chess engine decides what 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 XBoard, WinBoard or glChess 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 interface support both protocols whereas others, such as WinBoard, support only one and depend on subsidiary interpreters, such as Polyglot, to translate.

[edit] 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 analyse and to acquire a better positional understanding.

Some chess engines use endgame tablebases to increase their playing strength during the endgame. An endgame tablebase is a database of 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. Endgame tablebases in all cases identify the absolute best move in all positions included (identifying the move that wins fastest against perfect defense, or the move that loses slowest against optimal opposition). Such tablebases are available for all positions containing three to six pieces (counting the kings) and for some seven-piece combinations. 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 as a method to increase their strength.

[edit] Comparisons

[edit] 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 [2]. Most tournaments also allow any types of hardware, so only engine/hardware combinations are being compared.

Historically, commercial programs have been the strongest engines. To some extent, this is a self-fulfilling prophecy; 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.

[edit] 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.
  • All listed engines are 64-bit
These differences affect the results, and make direct comparisons between rating lists difficult.
Rating listTime control
(moves/minutes)
Year
started
Last updatedEngine/platform
entries
Games
played
Top three enginesRating
CCRL[2]40/40[3]
Ponder OFF
2005October 13, 20121241417,873Houdini 2.0c x64 4CPU
Critter 1.6a x64 4CPU
Stockfish2.2.2 x64 4CPU
3251
3243
3206
CEGT[4]40/20[5]
Ponder ON
2006October 14, 20121067620,333Houdini 1.5a x64 6CPU
Critter 1.6 x64 4CPU
Stockfish 2.3 x64 4CPU
3101
3056
3056
IPON[6]5m+3s
~16min/game
Ponder ON
2006October 17, 2012110213,250Houdini 3.0 STD x64 1CPU
Komodo 5 x64 1CPU
Critter 1.4a x64 1CPU
3096
3011
2990
SWCR[7]40/10
Ponder ON
2009January 17, 201267161,160Houdini 2.0c x64 1CPU
Critter 1.4 x64 1CPU
Rybka 4 Exp. 42 x64 1CPU
3019
2980
2968
SSDF[8]40/120
Ponder ON
1984June 28, 2012311121,472Deep Rybka 4 x64 2GB Q6600 2.4GHz
Naum 4.2 MP x64 2GB Q6600 2.4GHz
Deep Shredder 12 x64 2GB Q6600 2.4GHz
3221
3138
3115
WBEC[9]40/40
Ponder ON
2001May 15, 2011226
(Historically: 850+[10])
100,749Rybka 4 x64 2CPU
Stockfish 2.0.1 x64 2CPU
Thinker 5.5.4A1 x64 2CPU
3124
3121
3114
  • 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, not the absolute level of the numbers. 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 computer chess engines should be rated at least in the range of top human performances, and probably significantly higher.

Missing from many rating lists are IPPOLIT and its derivatives (e.g. Fire [3]). Although very strong and open source, there are allegations from commercial software interests that they were derived from disassembled binary of Rybka.[11] Due to the controversy, all these engines have been blacklisted from many tournaments and rating lists. Although Rybka has been accused of being based on Fruit, it is not blacklisted from computer chess tournaments or rating lists.[12] In June 2011, the ICGA claimed Rybka was derived from Fruit and Crafty and Rybka has been banned from the International Computer Games Association World Computer Chess Championship, and its previous victories (2007, 2008, 2009, and 2010) has been revoked.[13] The ICGA was criticized for this decision by Dr. Søren Riis, a longstanding supporter of the Rybka program.[14] All rating lists continue to include Rybka.

[edit] 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.[15] Then there are the BT2450 and BT2630 test suites by Hubert Bednorz and Fred Toennissen. These suites measure the tactical capability of the engine[16] and have been used at least by REBEL.[17] There is also a general test suite called Brilliancy by Dana Turnmire. The suite has been compiled mostly from How to Reassess Your Chess Workbook.[18]
Strategic Test Suite (STS) by Swaminathan and Dann Corbit, tests chess engine's strategical strength.[19]

[edit] Categorizations

[edit] Freely available

There are hundreds of freely available chess engines which conform to one of the above communication protocols. Many run on Windows or are open source. The top 50 strongest, freely available engines, according to the CCRL 40/40 rating list, are listed here.[20] Others may be found by examining the rating lists or external links.
Engine (strongest version)Author (Country)EloCPUSource
Alaric v707Peter Fendrich (Sweden)2759Binary, non-commercial
Bison v9.11Ivan Bonkin (Russia)2828GPLv3
Bobcat v2.75Alex Morozov (Ukraine)280764-bit
Booot v5.1.0Alex Morozov (Ukraine)2947Source, non-commercial
Bright v0.4aAllard Siemelink (Netherlands)30024CPUBinary, non-distributable
BugChess2 v1.9Francois and Jean-Philippe Karr (France)286764-bitBinary, non-commercial
Chronos v1.9.9Guillermo Filia (Argentina)284364-bitBinary
Colossus Chess 2008bMartin Bryant (England)2746Binary
Crafty v23.4Robert Hyatt (USA)295064-bit 4CPUSource, non-commercial
Critter v1.2Richard Vida (Slovakia)325464-bit 4CPUBinary
Cyclone v3.4
(derived from Fruit v2.1)
Fabien Letouzey (France), Thomas Gaksch (Germany),
Norman Schmidt
29712CPUGPLv2+
Cyrano v0.6b17Harald Johnsen (France)2745GPLv2
Daydreamer v1.75Aaron Becker (USA)277232-bitSource, license?
Delfi v5.4Fabio Cavicchio (Italy)28242CPUSource, non-distributable
Deuterium 10.01.27.213Ferdinand Mosca (Philippines)2770Binary
Dirty 25Aug2011Pradu Kannan (USA), Fonzy Bluemers (Netherlands),
Andres Valverde (Spain)
2797
Doch v1.2Don Dayley (USA)299064-bit
E.T. Chess 13.01.08Eric Triki (France)2749Binary
Frenzee Feb08Sune Fischer (Denmark)287764-bit
Fruit v2.3.1Fabien Letouzey (France), Ryan Benitez (USA)2886GPLv2+
Gaviota v0.83FM Miguel A. Ballicora (Argentina)275864-bit 4CPU
Glaurung v2.2
(now developed as Stockfish)
Tord Romstad (Norway)300164-bit 4CPUGPLv3+
Grapefruit v1.0
(derived from Toga II 1.4 beta5c)
Fabien Letouzey (France), Thomas Gaksch (Germany),
Vadim Demichev (Russia)
297732-bit 2CPUGPLv2+
Gull v1.2Vadim Demichev (Russia)302764-bitPublic Domain
Hannibal v1.1Edsel Apostol (Philippines), Sam Hamilton (USA)298864-bitBinary
Houdini v1.5aRobert Houdart (Belgium)329964-bit 4CPUBinary, non-distributable
Jonny v4.00Johannes Zwanzger (Germany)29554CPUBinary, distributable
Komodo v3.0
(last free version)
Don Dailey (USA)321664-bit SSEBinary
Loop 13.6 (Loop 2007)
(last free version)
Fritz Reul (Germany)294264-bit 4CPU
Movei v00.8.438 (10 10 10)Uri Blass (Israel)2769Binary, non-commercial
Naraku v1.4Marco Meloni (Italy)2871Binary, distributable
Naum v2.0
(last free version)
Aleksandar Naumov (Serbia/Canada)280064-bitBinary
Nemo v1.0.1Michael Hoffmann (Germany)294764-bitBinary
Pharaon v3.5.1Franck Zibi (France)27422CPUBinary
Pro Deo v1.74
(freeware version of Rebel)
Ed Schröder (Netherlands)2736Binary, non-commercial
Protector v1.4.0Raimund Heid (Germany)309064-bit 4CPUGPLv3, except endgame
RedQueen 1.0.0Ben-Hur Carlos Langoni Junior (Brazil)273532-bitGPLv3+
Rybka v.2.3.2a
(last free version)
Vasik Rajlich (Czech Republic)312464-bit 4CPUBinary
Scorpio v2.7Daniel Shawul (Ethiopia)285132-bitBSD
Slow Chess Blitz WV2.1Jonathan Kreuzer (USA)2737Source, non-commercial
Spark v1.0Allard Siemelink (Netherlands)308164-bit 4CPUBinary, non-distributable
Spike v1.4 LeidenVolker Böhm and Ralf Schäfer (Germany)31294CPUBinary, non-commercial
Stockfish v2.2.2Tord Romstad (Norway), Marco Costalba (Italy),
Joona Kiiski (Finland)
326464-bit 4CPUGPLv3+
Strelka v5.5Yuri Osipov (Russia)324064-bitBinary
TheMadPrune v1.1.25Fabien Letouzey (France), WH Lowery Jnr (USA)29772CPU
Thinker v5.4C InertLance Perkins (Canada)302964-bit 4CPU
Toga II v1.4.1SE
(derived from Fruit v2.1)
Fabien Letouzey (France), Thomas Gaksch (Germany)30074CPUGPLv2+
Tornado v4.4Engin Ustun (Germany)284132-bitBinary, non-commercial
Twisted Logic 20100131xEdsel Apostol (Philippines)286464-bit
Umko v1.0Borko Boskovic (Slovenia)293264-bitGPLv3+

[edit] Pedagogical

These open source chess programs were expressly written to teach the craft of chess programming.
There is also source-available proprietary software.
These small programs are written for hobby or to win programming contests, currently able to play all legal chess moves although with limited text interface.

[edit] Commercial

These chess programs are sold commercially. Most of these also include their own user interface.

[edit] Private

NameAuthorCountry
ApiChessMax HimamFrance
AzraëlChristopher ConkieUnited Kingdom
CarnivorMichael SherwinUSA
CheetahRalf SchäferGermany
CheplaMikael BäckmanSweden
ChimpAndy DuplainUnited Kingdom
ChironUbaldo Andrea FarinaItaly
CipollinoGiancarlo delli ColliItaly
CogitoJoerg SchaeferGermany
Cowrie ChessChan RasjidSingapore
CzolgistaTomasz KazimierskiPoland
DiepVincent DiepeveenThe Netherlands
Dr. TheopolisCorby NicholsUSA
EdlChessStephan EdlichGermany
EGMPawel KobylarzPoland
EichhörnchenWieland BelkaGermany
Ferret
past winner of the World Computer Speed Chess Championship
Bruce MorelandUSA
FlywheelDon CrossUSA
FrecciaStefano GemmaItaly
GrokPeter KapplerUSA
HansDamfGerd IsenbergGermany
Hector for ChessCsaba JerglerHungary
Ikarus
past winner of the World Computer Speed Chess Championship
KallistoBart WeststrateNetherlands
LearningLemmingSam HamiltonUSA
MeneChessShaun HoweUnited Kingdom
MoneypennyMatt ShoemakerUSA
NaltaP312Yves CatineauFrance
NightmareJoost BuijsNetherlands
NowMark LeflerUSA
NullmoverMichael LangeveldNetherlands
OlympusJoshua ShriverUSA
PandixGyula HorváthHungary
PebbleAdam GoodwinUSA
PhilidorChristian Barreteau and Bruno LucasFrance
Purple HazeVincent OllivierFrance
SibylMilikas AnastasiosGreece
SillyconLasse HansenNorway
SpandrelRobert PurvesNew Zealand
SymbolicSteven EdwardsUSA
TelepathCharles RobersonUSA
TinkerBrian RichardsonUSA
TwilightChessTony PalettaFrance
TzunamiIvo TopsNetherlands
Vlad TepesHenk FennemaNetherlands
WaDuuttieMaarten ClaessensNetherlands
WasterGeoff WestwoodUnited Kingdom
WeidJaap WeidemannSouth Africa
XiniXTony van Roon-WertenNetherlands
ZManuel DíazSpain
ZetaSrdja MatovicMontenegro
ZigguratDavid NorrisUnited States
ZilchMike LeanyUSA

[edit] Dedicated hardware

These chess playing systems include custom hardware or run on supercomputers. All are historical; chess supercomputers have not competed in computer tournaments since Hydra played in 2006.

[edit] Commercial dedicated computers

In the 1980s and early 1990s, there was a competitive market for strong dedicated chess computers. Many form-factors were sold, from handheld peg-board computers to wooden auto-sensory boards with state-of-the-art processors. This market changed in the mid-90s when the economical embedded processors in dedicated chess computers could no longer compete with the fast processors in personal computers. Nowadays, most dedicated units sold are of beginner and intermediate strength.
  • Chess Challenger, a line of chess computers sold by Fidelity Electronics from 1977 [4] to 1992. These models won the first four World Microcomputer Chess Championships.
  • ChessMachine, an ARM-based dedicated computer, which could run two engines:
  • Mephisto, a line of chess computers sold by Hegener & Glaser. The units programmed by Richard Lang won six consecutive World Microcomputer Chess Championships. They bought out Fidelity in 1989.
  • Novag sells a line of tactically strong computers, including the Constellation, Sapphire, and Star Diamond brands.
  • Saitek sells mid-range units of intermediate strength. They bought out Hegener & Glaser and its Mephisto brand in 1994.
  • Excalibur Electronics sells a line of beginner strength units. Excalibur was started in 1992 by the son of the founder of Fidelity Electronics.
  • Phoenix Chess Systems makes limited edition units based around StrongARM and XScale processors running modern engines and emulating classic engines

[edit] Historical

These chess programs run on obsolete hardware.

[edit] See also

[edit] Notes and references

  1. ^ blog.chess.com Creating a chess engine from scratch (Part 1: Basics), Link date 28 June 2012
  2. ^ "CCRL 40/40 - Complete list". October 13, 2012. http://www.computerchess.org.uk/ccrl/4040/rating_list_all.html. Retrieved October 18, 2012.
  3. ^ Also available: 40 moves in 4 minutes
  4. ^ "CEGT 40/20". Chess Engines Grand Tournament. October 14, 2012. http://www.husvankempen.de/nunn/rating.htm. Retrieved October 18, 2012.
  5. ^ Also available: 40 moves in 4 minutes, 40 moves in 120 minutes
  6. ^ "IPON". IPON. August 29, 2012. http://www.inwoba.de/index.html. Retrieved August 29, 2012.
  7. ^ "SWCR". SWCR. January 17, 2012. http://www.amateurschach.de/. Retrieved May 21, 2012.
  8. ^ "The SSDF Rating List". Swedish Chess Computer Association. June 28, 2012. http://ssdf.bosjo.net/list.htm. Retrieved October 18, 2012.
  9. ^ "BayesianElo Ratinglist of WBEC Ridderkerk". May 15, 2011. http://wbec-ridderkerk.nl/html/BayesianElo_ed18.htm. Retrieved May 21, 2012.
  10. ^ http://home.scarlet.be/vincentlejeune/Ratings-WBEC-Ed-11-to-16.txt
  11. ^ Chess engine controversy at chessvibes.com, retrieved 28/May/2010
  12. ^ https://webspace.utexas.edu/zzw57/rtc/eval/eval.html
  13. ^ http://www.chessvibes.com/reports/rybka-disqualified-and-banned-from-world-computer-chess-championships/
  14. ^ Riis, Dr. Søren (02.01.2012). "A Gross Miscarriage of Justice in Computer Chess (part one)". Chessbase News. http://www.chessbase.com/newsdetail.asp?newsid=7791. Retrieved 19 February 2012.
  15. ^ Nolot test suite
  16. ^ BT2450 test suite
  17. ^ Rebel
  18. ^ Brilliancy suite TalkChess forum
  19. ^ [1] Strategic Test Suite
  20. ^ Elo ratings taken from "CCRL 40/40, full list". Computer Chess Rating List. January 29, 2012. http://www.computerchess.org.uk/ccrl/4040/rating_list_all.html. Retrieved February 9, 2012.



 

No comments:

Post a Comment