NALIMOV Endgame Tablebases

An endgame tablebase is a computerized database that contains precalculated exhaustive analysis of a chessendgame position. It is typically used by a computer chess engine during play, or by a human or computer that is retrospectively analysing a game that has already been played.

The tablebase contains the game-theoretical value (win, loss, or draw) of each possible move in each possible position, and how many moves it would take to achieve that result with perfect play. Thus, the tablebase acts as anoracle, always providing the optimal moves. Typically the database records each possible position with certainpieces remaining on the board, and the best moves with White to move and with Black to move.

Tablebases are generated by retrograde analysis, working backwards from a checkmated position. Tablebases have solved chess for every position with six or fewer pieces (including the two kings). The solutions have profoundly advanced the chess community's understanding of endgame theory. Some positions which humans had analyzed as draws were proved to be winnable; the tablebase analysis could find a mate in more than a hundred moves, far beyond the horizon of humans, and beyond the capability of a computer during play. Tablebases have enhanced competitive play and facilitated the composition of endgame studies. They provide a powerful analytical tool.

Endgame tablebases for other board games like checkers,[1] chess variants[2] or Nine Men's Morris[3] exist, but without a specific mention of the game, one is talking about chess.


If you're experiencing difficulties viewing the tablebase it's suggested to use Firefox or Chrome web browsers.

Please enter max. 6 pieces (incl. kings).
NEW! All 6-men tables online (except 5 vs. 1).





                                
 
 Online Interfaces to Endgame Tablebases

Historically Nalimov Tablebases were computed by Eugene Nalimov and distributed by Robert Hyatt via FTP. Gradually Nalimov was releasing more and more gigabytes of 6-men tablebases and at some point Bob's FTP could not handle the load. 6-men tablebases were removed from FTP and disappeared from online space. The only way to get them was by personal communication with other chess fans.

In November 2005 several enthusiasts started a project to find and share all surviving tablebases. Many people joined contributing files they managed to save. At the same time Nalimov was continuing to release new 6-men tablebases that were now shared via this project.

In August 2006 the last 6-men tablebases were computed, completing the 3-to-6-men tablebase collection of about 1.2 Terabytes. Thanks to community support, the whole collection is now freely available online on eD2K/KAD network.

Thanks to Eugene Nalimov, Andrew Kadatch, Robert Hyatt, Kyrill Kryukov, Nelson Hernandez for generating, compressing, and publishing the databases and offering them for free. Special thanks to k4it.de for implementation. 

These web-sites allow you to probe endgame positions online using your browser.

Pros of probing online:

  • You don't need any EGTB files on your computer (saving hundreds of gigabytes of space).
  • You don't need any chess software either, just a browser.

Cons:

  • You can check only one position at a time.
  • You can check only position that itself falls within 6-men table, those servers don't do any search.

Links:

 -

Chess endgame Nalimov! 
Blackboard Nalimova on Chess Motor Narod.ru



  Using electronic endgame databases for chess, chess program at any stage of the chess endgame knows won the chess position, or no man's played, and how many moves needed to complete a game of chess. Chess endgame database known as "Tablebases" and are, as a rule, in a staggered format Nalimov (Nalimova table). Tables Nalimova (Nalimov) - is the most common variant of universal chess endgame databases. Recognize and use it all the leading world chess program to play chess. Also there Nalimov format individual chess endgame database created exclusively for their authors chess programs. The most famous of them - it Tablebases for chess program Shredder, Scorpio, Gaviota. Appeal to the chess database Tablebases significantly increases the strength of the game of chess chess program in the endgame. First select parameters chess engine "Use Tablebases" and the path to the configuration Tablebases Shakhmanov engine, you get a completely accurate assessment of the chess endgame position. Use electronic chess endgame database to practice the game of chess endings chess games and learning difficult chess endgame positions. Even the best experts on the game of chess will not be able to give you more skilled help than the one you get using electronic chess endgame databases. On this page you can download the most famous electronic chess endgame database to play chess online for 3-4-5 curly endings.


File archiver 7-Zip File Manager download



p / p
Endgame
Figures
Size
Download
1
Tables Nalimov
3-4
29,4 MB
2
Tables Nalimov
3-4-5
220 files, 7,03 GB
3
EGBB Scorpio
3-4
4,35 MB
4
EGBB Scorpio
3-4-5
322 MB
5
Shredder all345.tbe
3-4-5
157 MB
6
Gaviota EGTB
3-4-5
6,8 GB

 

Endgame Tablebases Online
6-men endgame analysis free for everyone

by Kirill Kryukov

News

March 30, 2008
This site changed the address, please update your bookmarks.
March 3, 2008
Removed broken link to eMule help site (which disappeared).
Added link to www.emulehelp.tk site which has useful guides about configuring various routers and firewalls to work with eMule.
February 27, 2008
Corrected link to "incomplete tablebase problem" explanation in Aaron Tay's FAQ.
Corrected link to Winboard Forum.
Corrected link to Dieter Bürßner's list of most important endgames.
Added link to wikipedia article in the introduction.
February 21, 2008
Added lnks to Norm Pruitt's sites with 3-to-5-men EGTB.
February 20, 2008
Norm Pruitt tells me that his FTP site is online again. Thanks Norm!
February 19, 2008
Added link to 3-4-5-men Nalimov tablebases hosted by Joshua Shriver. Thanks, Josh!
Added link to John Tamplin's online interface to endgame tables,posted by ernest in EGTB Forum. (Thanks to Guy Haworth for reminding me!)
February 17, 2008
John Kominek found an error in stat file kbpkn.tbs. He posted his logic and the correct file here. I updated the all-5-men-32p-tbs.zip archive on this site with the corrected file. Thanks, John!
February 8, 2008
One year ago I submitted our links to the eMule Content Database. Now Nalimov 6-men tablebases is second most popular release, next only to eMule itself. I suspect this is just because of enormous number of files we share. Still this is encouraging!
February 2, 2008

(Older news are archived here).

Introduction

Many chess enthusiasts would like to do 6-men endgame analysis, but no one wants to host 1 TB of files for download. So we have to help ourselves. This page is an attempt to organize a persistent online availability of the whole set of Nalimov 6-men tablebases.This project depends solely on chess lovers community, it's up to us to choose if we will download any tablebases for free, or if we will have to buy them on DVD from Chessbase etc..

If you are not sure what endgame tablebases are or how to use them, you can learn the basics from Wikipediaor from Aaron Tay's EGTB Guide.

eMule

We use eDonkey and KAD networks, and eMule software for sharing the tablebase files, so if you want to download them you will have to install eMule(or aMule if you use Mac or Linux). If you are new to eMule please take a look at thetutorial, and official help pages.Here you can learn how to set up eMule behind a firewall or router.

Some hints about configuring eMule the best way by our eMule expert Thomas:Thread 1,Thread 2. If you will have any questions or problems, please ask atEGTB forum. Good luck!

Please keep sharing the files after you downloaded them.

3-4-5 men bases

Just in case you don't have them, you should download and install all 3-4-5 men tables before even thinking of using 6-men tables. You can get them from Bob Hyatt, ChesslibNorm Pruitt (also FTP) or Joshua Shriver, but you might as well try using eMule and download them by these links:

6-men endgame tablebases

All files in this section are "emulecollections" - simple text files containing one or several ed2k links. Paste those links into your eMule and it will start trying to download the files.

Smileys show 'spread status' of each tablebase:
– Super-shared tablebase – All files have 10 full sources (peers with complete files).
– Well-shared tablebase – At least 3 full sources exist.
– At least one full source exist - a recently shared base, not spread yet.
– Tablebase disappeared from the network. It was available for some while, but now the original releaser disconnected before anyone else could get the files. If you have any sets marked with this smiley, please share them online!
– Tablebase was never released yet.
If you notice that some tablebase is spread more, or less, than stated here, please drop me email and I'll update this page.

The download order is completely up to you. A few things that you may consider:
1. It's good to get small bases before trying the big ones. The best start would be KNNKNN and KBBKBB.
2. It's better to get pawnless bases before getting those with pawns, to avoid the possible "incomplete tablebase problem".
3. You will have better experience if you start with bases which are already shared by many people ( and ).
4. You may like to download tablebases by "importance" order, which is based on statistics of occurrance of each ending in real games. Several such lists exist: by Dieter Bürßner,Nelson Hernandez, and Peter Kasinski.
5. You may like to first download tablebases for endgames where longer checkmates are possible.

[ Sorted by piece value: P⇒N⇒B⇒R⇒Q | Sorted by alphabet: B⇒N⇒P⇒Q⇒R ]

4+2 without pawns


4+2 with pawns



3+3 without pawns


3+3 with pawns


Additional information

Checking tablebase integrity

Tablebase files are big and anything can happen while you download, copy or keep them. You should always check their integrity after you downloaded new files, and also before sharing new tablebases. You can either check them using md5sum program and *.md5 files from this page, or with Wilhelm program. If you prefer Wilhelm be sure to use the latest version - 1.50, as earlier versions may incorrectly report corrupted files. Aaron's FAQ also has detailed explanation.

Caution! A number of people seem to have corrupted files now, for various bases. I can tell because when I search in eMule for the bases that I have, I see not only the links to the same files, but also links to the files with same names and same size, but with different hash. I urge everyone to re-check the tablebases before sharing any new files, and after you downloaded a new files too.

Other ways to download 6-men tablebases

Several members of this community volanteered to host some of the 6-men tablebases for those who can't use eMule for some reason. Servers known to me are listed here. (Please let me know if you know other servers, or if one of the listed servers is dead).

Please try to share with eMule all files downloaded from those sites.

Engines which support 6-men Nalimov endgame tablebases

Commercial engines accessing 6-men Nalimov tables in search: Chess Tiger 15.0, Fruit 2.2.1, Gandalf 6.0, Rybka 1.1 - 2.3.2a, Shredder 9.

Free engines accessing 6-men Nalimov tables in search: Crafty 21.5, Yace 0.99.87, Spike 1.2 Turin, Colossus 2007c.

Online interfaces to endgame tablebases

These web-sites allow you to probe endgame positions online using your browser.

Pros of probing online:

  • You don't need any EGTB files on your computer (saving hundreds of gigabytes of space).
  • You don't need any chess software either, just a browser.

Cons:

  • You can check only one position at a time.
  • You can check only position that itself falls within 6-men table, those servers don't do any search.

Links:

Other types of tablebases

Scorpio bitbases by Daniel Shawul are used by Scorpio, latest Toga and by other engines, thanks to open source probing code. You can download them from eD2K/KAD network with these liks (You need eMule for these links to work):

After you downloaded them, check their integrity with the included MD5 files, move all 3-4-5 files and "egbbdll.dll" into single directory, and point your engines to that directory. Run some endgame tests to see if the engine is really using those bitbases.

Source code of Scorpio bitbases compressor and probing code is available at Scorpio homepage.

Thanks

The biggest thanks go to Eugene Nalimov and Andrew Kadatch, who generated the "Nalimov tablebases" and who are providing the probing code for free to many engine authors.

Thanks to Daniel Shawul for creating Scorpio bitbases and sharing them along with the access code.

Following people contributed to this project by sharing their tablebases, sending links, making suggestions, and active discussion (in no particular order):Dan Wulff, A. Steen, Chuck Wilson, Joachim Rang, Sarah Bird, Alberto Gueci, Vincent Diepeveen, Thomas Mayer, Richard Pijl,Renze Steenhuisen, Gordon Evans, Nelson Hernandez, Keith Ian Price, Wilfried Eberl,Guy Haworth, Rafael Andrist, Eiko Bleicher, Ryan Hirst, Marc Bourzutschky, Joshua Shriver, Thomas Scherk, John Kominek, Norm Pruitt/PAKman.

(Please tell me if I forgot to mention someone, or if you have any correction)

Of course, many more people are joining by downloading and sharing the tablebase files, and by keeping them shared. Sharing the tablebase files is the meaning of this project, this page is simply an index page to make it easier to find them.

Feedback

If you have any questions, comments, ideas, suggestions, or any contribution, the best you can do is posting it inEndgame Tablebases Forumwhere other people involved with EGTB will see it.

Alternatively you can post in general chess discussion boards likeComputer Chess Cluband Winboard Forum, or contact me privately.


Created in 2005-2009 by Kirill Kryukov
Page last updated on March 26, 2009

 

 

 

A guide to Endgames Tablebase

From Aaron Tay

Introduction

This page was initially part of my web site on setting up of Winboard engines. However, I discovered that many visitors to my site, were actually looking for information on setting up endgame tablebases. Given the fact that my Winboard web site was already very long, I decided to start a new web site using the information already available in the original page as a base. I added information from the various web sites and past posts at Rec.games.chess.computer and the Computer Chess Club.

I'm a layman who is largely unfamiliar with the technical details of endgame tablebases. As such much of the technical detail here is only available thanks to the kind permission of experts such as E.A. Heinz,Guy Haworth, (both frequent contributors to ICGA journals on this topic) Anders Thulin (from rec.games.chess.computer) , Robert Hyatt, Bruce Moreland and especially Dieter Buerssner (all of those are authors of strong chess programs that use endgame tablebases). I would be grateful if you can email me if you spot any errors.

I hope that you will find this web site useful. If so, please help sign my guest book.

Yours Sincerely,

Aaron Tay
01-04-2001
My PGP - DH/DSS 4096/1024 Key



Further information

As of April 2006, one of the best places to obtain further information about endgame tablebases is at the following forum . I highly recommend it, if you have further questions, particularly technical ones.


Latest Changes

(To skip to FAQ table of contents )

31-05-2003 Made available replacements for flawed EDGB file sets installed by Chessmaster 9000 .

09-05-2003 Knightdreamer now supports bitbases.Also available as a dll for free use\ with other engines. Bitbase section rewritten.

01-03-2003 Yace now released uses 3 and 4 piece bitbases stored in memory.

06-02-2003 Added explanation of how endgame tablebases are generally constructed.

26-06-2003 E.A. Heinz's reference added. Bitbase section reorganised.

23-09-2003 More 6 piece tablebases loaded on Hyatt's FTP site. Including 6 piece tablebases with pawns.

23-05-2004 New viewer site by Convekta allowing access to 6 piece tablebases added

25-07-2004 DVD Endgame Turbo by Chessbase contains a corrupted file for the KRPPKR endgame.

08-10-2004 Added alternative site for online searching of Nalimov tablebase results here.

01-12-2005 Add more sites for searching online Nalimov tablebase results. Added link to emule collection of tablebase sites.Added Scorpio uses bitbases and offers dll for use.

25-04-2006 Cleaned up sections on six piece tablebase, and download sections.


Table Of contents


[A.1] What is a endgame tablebase? How do they work? How much stronger will it make my chess program play?

Chess endgame tablebases (EGTBs) are special databases that stores all possible positions with a given material balance and their results.

Note about terminology

Why not call them endgame "database" instead of "tablebases"? I have no idea, in fact Chessmaster's version of them are called EGDB (EndGame DataBase) , but regardless of what they are called they are similar in principle. In this FAQ, I shall use the terms Endgame tablebases because these are the names they are most widely known by.)

For example, there is one tablebase file (normally named KNNKP) that covers positions where one side has a King and 2 knights, while the other side has a king and a pawn and yet another tablebase file (KQK) that covers all positions where one side has a King and Queen, while the other side has a lone King.There are more endgame tablebase files of course, though naturally the more pieces on the board, the bigger the Endgame tablebase file.

Each endgame tablebase file allows the user to check what the result is with best play. For example, the KNNKP tablebase,can allow you to input a specific position with such a material configuration, and find out what the result should be with best play. Nalimov endgame tablebases (one of several types of tablebases),for example could tell you if that position is a forced win and if so in how many moves, or a draw with best play.

One thing to note is that,the raw endgame tablebases files are highly compressed,and require that you use some kind of graphic browser software, before you can view the files. .However, many Chess playing programs [See here for a list] can use endgame tablebases automatically,which will allow them to play that endgame perfectly.

Most chess engines don't even need to reach the position covered in an endgame tablebases to use the tablebases. For example, a few moves before such a position, the engine calculates (but does not play yet) a series of exchanges that leads directly to a position in the tablebase. The engine will then look up (or probe) the tablebase and get the results for that hypothetical position. This should help improve play of course.

But how are tablebases constructed in the first place?Basically endgame tablebases are database files of stored endgame positions calculated using retrograde analysis.Here's a basic layman explanation on how tablebases are constructed Here's another explanation by Bruce Moreland, author of Ferret (who has generated endgame tablebases of his own design).

The algorithm works via induction.

How these things works is that all possible positions are examined, and positions where one side is mated *now* are marked (apparently legal piece configuration, with one side to move, in check, and unable to get out of check). These are called "mated in 0" positions.

Once this is done, all positions with each side to move are examined, and if any of them can reach a mated in 0 position, these are marked as "mate in 1".

Now, we look at everything again and search for positions where all possible moves lead to "mate in 1" positions. These are marked as mated in 2.

Now, we try to reach "mated in 2", these are "mate in 2".

Next is a bit different, because we look for cases where it is impossible to avoid either "mate in 2" or "mate in 1". These are "mated in 3".

And so on, until no progress is made. The rest of the positions are proven to be draws.

It's a little trickier if it's possible to convert to a won ending, if you are trying to make a "distance to mate" database. You have to be careful of this idea of "no progress", because there are gaps. There might be a mate in 105 in KBP vs KN, but there might not be a mate in 95. This is because the mate in 105 might involve immediate conversion to a KBN vs KN, and yes, such positions do exist.

How much stronger will it make my chess program play?

Endgame tablebases allow chess programs to play better in 2 situations. Firstly, when the endgame position covered by the tablebase occurs on the board. This is most always a gain for the chess engine (assuming you don't have a incomplete tablebase set). Unfortunately, the current set of endgame tablebases (5 pieces or less) cover mostly simple endgame positions that most chess engines can handle either by a combination of search or knowledge programmed in. So most engines will not gain much from using tablebases this way (except in rare positions).

A much greater gain is achieved by the fact that chess engines can consult tablebases as a kind of oracle to decide whether to exchange down into a endgame covered by the tablebase.This allows the range of positions to be covered to be much larger. A chess engine can for example avoid exchanging down to losing positions (even if they are very deep) or win by converting into a absolutely won endgame.

And yet, people have estimated that most engines gain at most 25 elo from using them, and many have found no significant difference in playing strength. Experiments results by Robert Allgeuer and Les Fernandez using Crafty and Yace show no significant difference in playing strength.

In this article I listed 5 possible weaknesses of endgame tablebases that might cause this. Of the 5, some are quite rare (problems #2,#3) or can be avoided (problems #1) , except for the last problem which is the resulting slow down from accessing the hard-disk.

Robert Allgeuer did a interesting experiment with Yace. And basically he found that while endgame tablebases allowed engines to reach and win such positions, in games where such positions were not reached they played weaker. By considering games where positions covered by endgame tablebases was actually reached on board ,Yace with tablebases played significantly better (about 115 Elo) On the other hand, in games where such positions was not reached, Yace with endgame tablebases played significantly weaker (about 94 elo). The implication was that in such games, using endgame tablebases was a liability. Robert writes "Apparently statistically for each game they successfully maneuver into a won 5 piece position, they also lose another one during the preceding endgame, so that overall this effect more or less cancels out the advantages of tablebases."

The above results can be still extended by using different time controls, egtb caches, engines (some like SOS claim to be heavily dependent on tablebases because the author has stripped out all endgame related knowledge covered in tablebases) , but it seems that using the current set of tablebases (3-4-5 pieces), you can't expect more then a minimal strength increase if any. Still you might want to use tablebases for learning and analysis purposes.



[A.2] What are the different endgame tablebases formats out there? What are the differences?

There are various kinds of Tablebase formats widely in use, including Ken Thompson,Steven J. Edwards,Eugene Nalimov Tablebases and Chessmaster/De Koning EDGB (in the order in which they first appeared). While these are popular, some programmers have chosen to use endgame tablebases of their own design, for example Bruce Moreland's Ferret

In general though, they fall into 2 types of tablebases. Distance to mate (DTM) and Distance to Conversion (DTC)tablebases. Roughly in layman terms, the difference is as follows.

  • Distance to mate (DTM) - DTM tablebase stores the shortest possible mate (in ply) for each position. Eg Nalimov tablebases
  • Distance to conversion (DTC) - DTC tablebases stores the shortest number of ply between each position and a "conversion". A conversion is either a pawn promotion or a piece being captured or checkmate. Eg Thompson tablebases.
  • In addition, Distance to zeroing (DTZ) and the superior Distance to rule (DTR)tablebases have being proposed to overcome the fact that DTM and DTC do not recognise the fifty move rule. Only in theory so far.

The tablebases also various in other ways Dr Robert Hyatt [Author of Crafty] explains the differences between them as follows [in a posting to rec.games.chess.comp 26/10/2000]

"Edwards (Tablebase): Distance to mate values stored. The main problem with these is that they are larger than the others.

Nalimov (Tablebase): Distance to mate values just like Edwards, but Eugene's files are compressed, and they may be used in the compressed form, with no penalty of any kind. Rather than way over 30 gigabytes for all of the 3-4-5 piece files, you end up with about 7.5 gigs.

Thompson (Tablebase): Distance to conversion (capture which takes you to a smaller ending class). These are difficult to use in their compressed form, from inside a chess engine. They also provide different info than Eugene's database... i.e. it tells you something, but it doesn't differentiate between losing and drawing as the Nalimov files do.

Best choice: Nalimov. Nearly every chess engine supports those... "

This was of course written before the release of the De Koning EDGB format used by Chessmaster 9000 only in August 2002. Nalimov still remains the most popular tablebase format since it's supported by the largest number of engines.

About Chessmaster endgame tablebase / De Koning EDGB

De Koning EDGB - Propertry format used by only Chessmaster 9000. Like the Nalimov tablebase it is a Distance to mate tablebase. Unlike the Nalimov tablebase though, it stores only wins from the white point of view (similar to Thomson)."(It) searches only for wins for White. All positions that are not proven to be won by White are stored as unknown. These unknowns might be draws, or lost by White, or (in large numbers) illegal." [From FEG or Final endgame generator for Chessmaster 9000 ]

Note the original version of the endgame generator had a minor flaw, and the EDGBs that shipped with the CDs also had this flaw. See here for more

Other differences between the De Koning and Nalimov formats are

This change means that besides the usual pawn promotion case problems there are other "dependencies" problems between EGTB files (my comments)

  • Chessmaster 9000 currently does not probe the Tablebase in search but according to email correspondence this is a decision design and there is nothing in principle that stops this from occurring.

  • De Koning EDGB are slightly smaller than compressed Nalimov endgame files in general.The full De Koning EGDBs came up to about 5.7 GB , the EGDB's can function with only either the WTM or BTM files.[Note during generation, you need both files!] This can reduce the space required to as little as 2.7 GB which is extremely light on hard-disk space compared to the 7.5 GB (as quoted by most people) required for Nalimov tablebaes.

  • The Chessmaster EDGB format generation process is also faster compared to Nalimov. (Full set of 5 piece tablebase take 5 days on 1.2 GHZ Athlon) It also requires much less free RAM (less than 13MB to be precise). The generator also makes generating 6-man with KWWWWB possible on a 32 bit computer possible , but that requires about 300MB (which isn't a lot by todays standards) of free RAM

  • 4 piece KxyK + KxKy 23 MB
    5 piece KxyzK 1.25 GB
    5 piece KxyKz 3.47 GB
    5 piece KxKyz 1.04 GB (The numbers designate the full set. For simple lookup the half set will do (either wtm or btm). The half set is somewhat smaller than half of the full set.)

  • Otherwise De Koning EDGB's are similar to Nalimov in terms of castling and 50 moves rule (see below).

More about Nalimov and Compressed Nalimov tablebases

Nalimov tablebases are nearly "perfect" since they take into account en Passant. However, they don't take into account castling, but this flaw is probably of interest only to Chess problem Hobbyists.

In general, though almost all modern Chess programs [including most Winboard programs] use Nalimov Tablebases partly because they are non-propriety and partly because they are more efficient. Also some of the 6 pieces Tablebases are now available in the Nalimov format. The Nalimov tablebases comes in 2 forms, uncompressed and compressed. The compressed ones end with the extension "emd".

Most of the modern Chess programs( e.g. Crafty supports to the use of the compressed Nalimov format from versions 16.5 onwards) can use the tablebases in compressed form by uncompressing and using them on the fly as needed. One exception I'm aware of is a old version of Esc , a Winboard program released on 4 Feb 2001 which uses only the uncompressed form. If you generated the Nalimov tablebases yourself (see Section [A.8] ), they will already in the uncompressed form before applying datacomp.exe. datacomp.exe can also be used in reverse to get uncompressed Nalimov tablebases from compressed ones.

Other uncommon types of Tablebases

Bitbases

There are other types of less common tablebases that work quite differently from those mentioned above. They generally go by the term "bitbases".

There is a short articleby Roland Piffer, author of Patzer explaining what bitbases are. Unfortunately, it's available only in German.

Here's a layman explanation attempted by yours truly.Unlike normal tablebases that store the full distance to mate or conversion, bitbases only stores information about whether a position is a forced win or loss. Sometimes, this alone is enough to help a chess engine to discard lines quickly. However bitbases (unlike typical TBs like Nalimov tablebases) does not store the exact score (eg mate in x) and hence cannot be used to work out the best winning line directly. However because bitbases need only store whether a position is a win or draw as opposed to whether it is mate in x (where x can be anything from 1-128 or more), they are naturally smaller and faster to access and can fit into the computer's RAM. They can be used together with more traditional Endgame Tablebases (Nalimov etc).

Yet another note about terminology

The term "bitbases" comes about because it requires only one bit to store the results for each position. Again, the naming might differ, e.g. knightdreamer calls them Endgame models (egm).

E.A Heinz was probably the first one to pioneer the concept. They were integrated into his chess program "DarkThought" by late 1996 and proved their practical viability during the 1997 WMCC in Paris where "DarkThought" employed them throughout the whole tournament. In addition, he also published an article on it in ICCJA (see below) in 1999. Eventually bit-based endgame databases started to appear in many other microcomputer chess programs (e.g. According to E.A Heinz,Chrilly Donninger integrated them into "Nimzo" based on the ICCA Journal article cited below).
E.A. Heinz. "Knowledgeable encoding and querying of endgame databases." ICCA Journal, Vol. 22, No. 2, pages 81-97, June 1999. (published by the ICCA; preprint available from http://lcs.supertech.lcs.mit.edu/~heinz/ps/know_edb.ps.gz or http://www.i-u.de/schools/heinz/ps/know_edb.ps.gz )

Unlike normal endgame tablebases where there are only a few standard formats used by almost all chess engines, so far no open standard bitbase format exists and the few chess engine programmers who have implemented this idea, use bitbases of his own design. These are the ones that I'm aware of which use a form of bitbases.

1) Nimzo 8 uses proprietary "Nimzo tablebases" (probably a form of bitbase too) that are stored in RAM for faster access.

2) Patzer, which is available as part of the GambitSoft Winboard Edition II package uses bitbases too.

3) Yace versions (after 0.68) also use bitbases.Yace uses bitbases for 3+4 pieces only and this is stored in memory . This allows Yace to access them in Quiescience search without much slowdown compared to using Nalimov tablebases.

4) Knightdreamer does something similar with it's own Egmprobe.Like Yace's bitbases, there are currently only 4 men tablebases and are small enough to be loaded in RAM. More technical details, A decision tree grown with an ID3-style algorithm is used to predict if a position is won, lost or drawn. Eugene Nalimov's EGTBs are used as an oracle. An accuracy above 99% is reached for most endgames. A table with the exceptions is compressed with run length encoding and huffman codes. The exception table is probed on the fly, without generating any decompressed tables. Knightdreamer uses this to "adjust scores" (increase scores if there is a absolute win, divide the score to get a score closer to zero if a draw is possible with best play) to help aid scoring (used in pruning too) but does not consider any wins found by EGM as a absolute win. This is because occasionally knightdreamer is unable to win absolutely won games, or may misplay technically drawn positions. Most interestingly, EgmProbe is distributed as a DLL for free for non-commercial engines. To download all the egms for all 5 pieces tablebase (except for 4-1) go to http://cap.connx.com/Contrib/Johan/KnightD33.zip(211 mb).

5) Delfi has internal bitbase tablebases (stronger side wins/draws) for almost all the 4 men tablebases except N vs P and R vs B and KRPKR. For more information.

6) Scorpio you uses bitbases up to 4 piece. He also offers a dll to access these bitbases for those interested. Fruit Gambit and latista uses this too.

7)GAFS

Guido from G6 [ a group of 6 Italians Winboard engine authors] has announced a new endgame tablebase format - GAFS .Guido writes

It is also possible to generate EGTBs with 2 bits per positions (win, loss, draw, illegal position). There is also a very small object file to link to the chess program in order to use 8 bits and/or 2 bits EGTBs and this is possible inside the same run. The idea was that 2 bits tablebases could be sufficient during the search process before entering a tabulated ending, while inside the ending only 8 bits EGTBs can give the correct move. I don't use compression at least for now. To the persons that tried to use my EGTBs I suggested to read the result on the disk file (without loading the file in RAM), and save it in the hash table. If the number of different positions to read, i.e. access to the file, are not very high (no more than some thousands), the cost in time should be acceptable, as a single access to the disk can cost some ms.

You can find more information on http://users.libero.it/rigel_g/ . The only known available chess engine that uses it is Madeline (look for info on the engine)

8) By 2005, there are now many more engines that use bitbases, many of their own design. Examples include Kiwi, Slowchess,Glaurung .

I have also heard of tablebases being generated for other Chess variants like Losing Chess , but I have not be able to find more information.

NEW! [04-01-02] Sjeng 11.2 now allows you to self generate 2 and some 3 tablebases for suicide Chess.KKFchess does the same for various variants as well as supporting normal Nalimov tablebases.

If you have more information,web sites with more information about endgame tablebases to link to, or clarifications that you want to make, please emailme

Note: For the rest of the FAQ, unless I state otherwise, endgame tablebases refer to Nalimov tablebases.


[A.3] Where can I learn more about the endgame table formats?

For Nalimov tablebases you need written permission from him. You might want to look at probe.txt which is part of TBGen.zip. Which can be normally be found in most places which allow EGTBs to be downloaded)which if I understand correctly, gives instructions on how to hook up your Chess Engine to probe Nalimov's tablebases.Looking at open source programs might also help for example, "probe.c" file from BeoWulf or egtb.c file from Crafty.This post might also help .

Attention! For Chess programmers trying to learn more about the format to figure out how to make their Chess programs use Eugene Nalimov tablebases, : Dr Ernst A. Heinz who is the author of the Chess program, Dark Thought and author of the book " Scalable Search in Computer Chess " writes:

"My WWW pages at http://supertech.lcs.mit.edu/~heinz/contain preprints of two interesting texts about the index schemes of endgame databases for chess (incl. Eugene Nalimov's).Specifically, you might want to take a look at:

* E.V. Nalimov, G.McC.Haworth, and E.A. Heinz. "Space-efficient indexing of chess endgame tables." In ICGA Journal, Vol. 23, No. 3, pages 148-162, September 2000. (published by the ICCA; preprint available from http://supertech.lcs.mit.edu/~heinz/ps/NHH_ICGA.ps.gz

* E.A. Heinz. "Endgame databases and efficient index schemes."In ICCA Journal, Vol. 22, No. 1, pages 22-32, March 1999. (published by the ICCA; preprint available from http://supertech.lcs.mit.edu/~heinz/ps/edb_index.ps.gz

[In a posting to rec.games.chess.comp, 03/13/2001]

You can download for free the FEG or Final endgame generator for Chessmaster 9000 . It comes with a nice document file that explains clearly in layman terms what endgame tablebases are and summarises some of the issues involved.


[A.4] What are the Chess programs that support endgame tables? Which format do they support?

Here's a small list.

Program Name Endgame Tablebase types supported

Fritz 6.0+

Nalimov

Junior 6.0+

Nalimov

HIARCS 7.32+

Nalimov

Nimzo8+

Nalimov, Nimzo Tablebases

Chess Tiger 14.0+*

Nalimov

Rebel Tiger 2.0*

Nalimov

Chessmaster 9000 and up

De Koning format (new)

Shredder 5.0+

Nalimov , Thompson

Chess Genius 6.5

Thompson

Patzer**,Yace Paderborn

Nalimov , Bitbases

Knightdreamer,Delfi

Bitbases

Crafty***

Nalimov

Gromit 2.2,Dragon [Pre-4.0],Bionic

Edwards

Most free Winboard engines****

Nalimov

SCID

Nalimov

Madeleine

Nalimov and GAFS

* The latest update 02/04/2001.Refer to Rebel Web site . Prior versions did not have any endgame tablebase support.

** Available as part of the GambitSoft Winboard Edition II package.

*** Old versions of Crafty used Edwards Tablebases.Crafty 15.21 onwards supports only Nalimov tablebases. Crafty 16.5 onwards also supports the use of compressed Eugene Nalimov tablebases.

**** For a full list of Winboard engines that support tablebases , refer to Engine Overview page by Leo Dijksman

Effects of GUI like Chessbase/Chessmaster

Additional note, when Chess engines are used in Chessbase GUI or Chessmaster 9000, the GUI will use any tablebases available once the position on the board matches that of the relevant tablebase. But this does not mean that the Chess engine itself "uses" the tablebases in it's search etc.


[A.5] Where can I get endgame tablebase?

Nalimov tablebase

If you own only Fritz 6 or any Chessbase engine, you will have the 3-4 men Compressed nalimov tablebases, but you might want more. You basically have 3 choices. You can buy , download or generate them. [From easiest to most difficult.]

Chessmaster EDGB or De Koning EDGB

If you own Chessmaster 9000, it will already come with all 4 piece tablebases together with some 5 piece tablebases, particularly the KRPKP and KQPKQ and their respective depedencies.The set that comes in the CD is as follows

KQRKR,KRQKR,KRKRR,KRRKR,KRBKR,KRKRB,KRNKR,KRKRN,KRPKR KRKRP,KQQKQ,KQKQQ,KQRKQ,KQKQR,KQBKQ,KQKQB,KQNKQ,KQKQN KQPKQ,KQKQP,KBBKN,KNKBB,KNNKP,KPKNN

Unfortunately, at time of writing 21 September 2002, there is no place to download or buy De Keoning tablebases for Chessmaster 9000, so you will have to or generate them yourself.

Thompson Tablebases

Thompson Tablebases was the first endgame tablebases to be widely used by chess programs. Older versions of chessbase , Fritz etc used to support them. Unfortunately, they are not used much today, because they are largely inferior to Nalimov's. (E.g They don't cover en-passant, not all 5 piece tablebases available, they are larger, slower to generate and use , and only one side to move was generated). I don't know of any place where they are available for download (not sure if that's legal), and while they used to be for sale, it's likely they are not now.

Edwards Tablebases

There's a generator available somewhere on Dann Corbit's ftp. Also 3-4 piece tablebases available for download on Dann's site.

Bitbases of various formats

Because bitbases are generally small and available for 3-4 tablebases (so as to fit in memory), most either come with the program as separate files (Knightdreamer,Nimzo), are integrated internally (Delfi), or can be generated by the program itself in a couple of minutes or seconds (Yace).


[A.6] Where can I buy tablebases?

Buying Nalimov tablebases

You can buy The Chessbase DVD Endgame Turbo 2 which is a 5 DVD set that has all of the Eugene Nalimov 3,4,5 and some 6 piece tablebase set. Conveka makers of Chess Assistant also sells all 3-4-5 Nalimov tablebases in either a DVD set and another set consisting of the above plus some 6 peice tablebases in 2 DVDs.

Buying Chessmaster EDGB or De Koning EDGB

As yet, this is not available.

Buying Thompson tablebases

You used to be able get Thompson Tablebase with certain software packages like the "World Champion package" from Millennium System. Chessbaseused to sell a 4 CD set of 5 men Thompson Tablebases both separately and for use with Chessbase 7

I have no idea if Edwards Tablebases are available for sale.


[A.7] Where can I download tablebases?

Downloading Nalimov tablebases

You could download them file by file for the 3,4,5 and some 6 men Nalimov compressed Tablebase from UAB ftp. This is the original source and will always have the latest and most complete sets available as soon as Eugene Nalimov sends them. But see comment on 6 piece tablebases. You will need a fast internet connection if you want to download the 5 men tablebases which are very large. , These files are already in compressed emd format, and it doesn't help to further compress them with pkzip etc.

Alternatively, Frank Quisinsky offers all the 3 and 4 men tablebase for download in one 30 meg file.

Another site that you might consider looking at if the UAB site down (unless you want 6 piece tablebases) is is at http://www.chesslib.no/ [click on 'downloads' at the top] .

If for some unusual reason you need uncompressed Nalimov piece sets, you should uncompress them using datacomp.exe that comes with tbgen.exe.

If all these sites are down, you can try downloading them via emule .

Downloading Chessmaster EDGB or De Koning EDGB

No known site exists.

Downloading Edwards Tablebase

Edwards Tablebases (35 meg) are available for download at Dann Corbit's ftp site.


[A.8] How do I generate tablebases on my computer?

Generating Nalimov tablebases

Lastly, you can generate Nalimov tablebases using the tablebase generator tbgen.exe. The same generator is also on the Fritz6 CD. But self generation of 5 men tablebases is not really feasible unless you have a very fast computer with lots of RAM especially. You can find a guide by Mogens Larsen about generating 4 piece tablebases. Antonio Senatore also made a nicepost at the Winboard forumthat offers some guidance if you really want to try to generate 5 pieces tablebases.

See also Section [A.11] .

Generating Chessmaster EDGB / De Koning EDGB

First download the FEG or Final Endgame Generator. When you choose to do a full install, all the tablebases will be copied to c:\mydocuments regardless of the actual directory Chessmaster 9000 in.

Important note: If you use the full installation of Chessmaster with EDGB and/or downloaded and generated other tablebases using FEG version 3.2 (you can check the readme file to check the version) , the tablebases you generated and some that came with the CD are flawed.In a nutshell

Endgames with mates no longer than 1 (eg KNNK) did not contain the black-is-checkmated positions, or rather their wrong value being "not_white_win". This affected also some positions leading to black-is-checkmated by capture (eg KNNKR with the mating move being NxR).

This bug will affect Seven of the 4 piece endgame tablebase and Thirty five of the 5 piece endgame tablebase.

Of those that came with the Chessmaster CD, the following sets:
KNNK,KBKB,KBKN,KBKP,KNKR,KNKB,KNKN,KNNKP,KNKBB falls prey to this bug.

I have generated these file sets and put them into one file for your download. You can them unzip them over the EDGB files installed from the CD. The chessmaster EDGB file sets are 12mb zipped and contain the Jix and Joo files necessary to be used in chessmaster. For the 2 five tablebase set KNKBB and KNNKP, I have made available only the btm files because only those are installed by the chessmaster CD.

Others that are flawed include KNNKQ,KNNKR,KNNKB,KNNKN,KNPKQ,KNPKN,KNPKP,KBKQB,KBKQN,KBKQP,KBKRB,KBKRN, KBKRP,KBKBB,KBKBN,KBKBP,KBKNN,KBKNP,KBKPP,KNKQR,KNKQB,KNKQN,KNKRR
,KNKRB,KNKRN,KNKRP, KNKBN,KNKBP,KNKNN,KNKNP,KPKQR,KPKRR,KPKRB

For more details see this post at CCC. Download the new FEG generator here

To change the directory where chessmaster looks for tablebases edit cm.ini (found in the chessmaster 9000 directory) with a text editor. You need to change the path ofEGDBPath=whatevernewapth where your tablebases are.

A second bug was found on Dec 26, dubbed "the transparent pawn bug". "Affected files are the ones where both sides have at least a Pawn and White has at least a sliding piece. As well as the ones relying on them via promotion (KPPKP) or capture (6-man only) or both. Regarding 3,4,5-man these are KQPKP, KRPKP, KBPKP, KPPKP."

Note, that even though there are some 5 piece tablebases on the CD to save space the 5 piece tablebases on the CD do not come with the WTM files.This means you have to regenerate all the 5 piece tablebases if you want the complete set due to the depedencies.


[A.9] How large are the tablebase files? Can I put then all into one directory? Do I have to use a complete set of 5 men tablebases?

Note the following refers to Nalimov tablebases. Users using Chessmaster format should ignore this section. Chessmaster 9000 itself is not vulnerable to the incomplete tablebase problem.

The more tablebase files you install, the stronger the program will be. However, a full set of 3,4 and 5 Tablebase files takes about 7.05 GB of Hard disk space! BTW many of the "complete" endgame tablebase sets you can buy on CD are not really complete and may exclude some of the less important tablebases for example the so called 4+1 men tablebase sets [KXXXK] on the assumption that those are trivial enough to solve. Most people download a full set of 4 Piece databases and select only a few of the 5 pieces.

Note you can mix all the different endgame tablebase into one directory if you wish. However if you do decide to split up the files among various directories (there might be some advantage in leaving a small subset of tablebases (clear wins like KXXXK in a chess engine game as opposed to for use in analysis.See here), you might need to check whether the Chess engine/interface you use allows you to point to multiple paths.

NEW! Dieter Buerssner has informed me that in general all Chess engines/interfaces allow the use of separate paths for nalimov tablebases as long as they are separated by " commas, semicolons, or (at non- Windows systems) by colons." I have tried testing with a few engines, most seem to work. For example in Pepito , I add EGTB_PATH C:\fourpiece;g:\fivepiece.

In addition, Dieter offers another interesting tip. " In console mode, or with Alt-F1 (in Winboard) you can probably change the path for many engines. For example for Yace, assuming it had some tbldir in yace.ini, and I saw the analysis of one position with TBs. Then I want to see it without TBs. I would type tbldir nul "

For Crafty you need to set the paths (separated by ;) in the command line (or Winboard.ini) and not in the Crafty.rc file. (I'm not sure if this applies to newer versions anymore)

However if you put all the tablebases in one directory as opposed to splitting them up say by tablebase pieces, it can get confusing to keep track of which tablebases you have and which you don't. You can find some programs that help keep track of this in Section [A.19].

Generally the 5 piece endgames with rooks are reached most frequently and should be downloaded .Important ones include KRPKP, KQPKQ and KPPKP. However, there are some pitfalls that you should be aware of.

If you want to use the KRPKR tablebase [and assuming you have all the 3 and 4 tablebases], make sure that you have the KQRKR one as well. [You might consider adding KRRKR, KRBKR , KRNKN as well but it's probably not necessary] This is to ensure that the promotion cases are included.

endgame problem

If you lack say the KQRKR tablebase, some programs refuse to queen the pawn even if that would lead to a win, because such a move, would cause the program to drop from a position flagged as "win", to a position that is uncertain [although with a high score] since they lack the relevant endgame table.

In the position on the left, I have all the 4 men tablebases but only use one 5 men tablebases- KRKRP. With White to play, instead of queening the pawn with e8=Q, Comet will instead play1 Re4+ ?

1 Re4+ appears superior to 1 e8=Q because from the program's point of view 1 Re4+ leads to a position that is a mate in 16 [obtained from the KRPKP tablebase], while it is unable to search deep enough to see that 1 e8=Q leads to a even faster mate in 15 due to the lack of KQRKP tablebase! As such it prefers a certain mate in 16 to a move that "merely" leads to a high score.
r7/2K1P3/8/4R3/2k5/8/8/8 w - - 0 1

White to move [Picture generated using epdtodiag]

A similar problem can result if you download only the KQPKQ tablebase without KQQKQ , KQRKQ etc..

Some programs like Crafty and Yace are "smart" enough to avoid this problem, but some like Fritz,Tiger,Amy,Comet,Gandalf or The Crazy Bishop[all freely available Winboard engines except for Fritz and Tiger of course] cannot handle this.



noproblem

On the other hand, some positions are not problematic, if there is a quick mate nearby after the pawn promotion that the Chess engine can see.

There is a short mate in 5 after 1 f8=Q+ . As such Comet and most Chess engines * can quickly see this shorter mate and will prefer the pawn promotion move to 1 Ke7 [found in the KRKP tablebase] which leads to a mate in 9.

This is made easier by the availability of the 4 men tablebases as the program need not calculate the position after 1 f8=Q+ Rxf8+ etc since it can use the KRKR etc tablebases. In fact, the only other legal move [besides Rxf8+] after 1 f8=Q+ is Kh7 which leads even to a quicker mate. All this is child's play for Chess programs to calculate

Compare this with the above position, White has 15 other replies after the pawn promotion which doesn't lead to a 4 men tb position.
4K2k/5P2/8/6R1/8/5r2/8/8 w - - 0 1

White to move [Picture generated using epdtodiag]

If you are an author of a Chess program and wish to avoid this problem, what you can do is this. If you find that in the root position it is mate in X from probing the n men tablebases, but after trying every legal move you don't find a mate in X-1 from the tablebase, it must be due to a incomplete tablebase problem and you search without probing the tablebases.

Also take note that not all programs support all the Tablebases. Yace for example, currently does not use the 4+1 tablebases [ King and 3 pieces/pawns on a side versus a alone King] , because such positions are easily won most of the time barring rare cases [Like double rook pawns, wrong coloured bishop and King vers King].

You might also not want to download 6 man Nalimov endgame tablebase (see also here) because I think currently only a few Chess programs support them, although it's usually a simple matter for the programmers to activate them. These include Crafty, Sjeng , Quark , King of Kings[all free Winboard Chess engines ] and perhaps Rebel Tiger . NEW! I have read that the Fritz6 engine itself does not probe the 6 men tablebases, but only uses them when they occur on the board.

* It appears that The Crazy Bishop might just stop searching whenever it finds a forced mate and as such it is "happy" with 1 Ke7 . Which explains why it has problems here, as a mate in 5 is well within it's search abilities.


[A.10] Questions about 6 men tablebases.Which are the most useful?

Generating Nalimov 6 piece tablebases requires the heavy duty use of 64 bit computers and is currently out of reach of most normal users.

As of Jan 2004, all the 3-3 and 4-2 pawnless Nalimov tablebases are done (227 GB). The 4-2 with pawns are being worked on, and some are available. None of the 3-3 with pawns or the 5-1 nalimov tablebases are available yet.

As of Aug 2005, all of the 6 piece tablebases are complete except for the 5-1 set but not all are available publicly.

There appears to be a lot of confusion about which engines can access 6 piece tablebases. This is due to several changes in the nature of the 6 piece tablebases. First there is the "normal" 6 piece tablebases generated before Dec 2002, it is suspected that some of the newer commercial engines like Hiarcs 9 can access this. In Dec 2002, because of the size of the files, each tablebase is broken into 2 parts, i,e "the multifile format". In September 2003, yet another batch of tablebases was released with more changes to the probe code.

Crafty V19.4+ (to be safe use versions above 20) , Wilhelm are confirmed to work with them. Also confirmed working (ability to use in search) according to http://kd.lab.nig.ac.jp/chess/tablebases-online/ are Chess Tiger 15.0, Crafty 19.19, Fruit 2.2.1, Gandalf 6.0, Rybka 1.1, Shredder 9. This refers to the larger multiple split set, normal chess engines can probably handle the older and smaller 6 piece tablebase sets.

Where to get them.

Historically the main source for 6 men Nalimov tablebases has being at Bob Hyatt's ftp . However, as of April 2006, they are still recovering from a hard-disk crash, and there are no 6 piece tablebase there. They intend to recover though, so continue checking.

http://olympuschess.com/tb6/index.html has a very limited number of 6 piece tablebase sets for download, however, the best, most complete and most reliable source for downloading 6 pieces Nalimov tablebases is still via emule here!.

What are the most useful 6 piece tablebases?

It's hard to say, but take a look at the following recommendations based on an analysis of positions reached by humans and computers.. Data about difficulty of winning (probably of draw) and other stats can also be found here in excel format.

Historical information (outdated mostly)

NEW! [Dec 14 2002] - More 6 men tablebases have being uploaded on Hyatt's site. However because of the size of the files (greater than 2 gb) they are broken into 2 parts (For example krnkbn.2.nbw.emd) and it requires a different probing code and currently [Dec 14 2002] no Chess engine can access it yet except Crafty 19.2 which will be released soon.From the user point of view, usage remains the same. As of March 2003, the new version of Wilhem can access them too.

NEW![September 2003] Yet more endgame tablebases produced with more changes to the probing code. This current update includes some of the 4+2 with pawns tablebases, but very few programs can access it. One is wilhelm, the other is Crafty 19.4. Any programs released before them (around Oct 03) are unlikely to be able to use such tablebases.

Here's an explanation by Eugene Nalimov.

New access code would shortly be released in Crafty 19.2. Changes were necessary because (1) you should use 64-bit index to index some of 6-men TBs, (2) even after compression some files were greater than 2Gb, and some OSes cannot handle such files (or handle them in absolutely unportable way), so best solution is to split those files into several smaller ones.

From chess program's point of view the only difference is that INDEX type now should be unsigned 64-bit integer, not unsigned 32-bit integer. Something like 5 minutes of work.

Some unrelated problems are fixed in the code -- reported memory leaks, SMP problems, Mac OS X locks problem that manifested itself in access violation, very slow startup when TBPATH pointed to the CD-ROM drive and there was no disk in that drive, better integrity check for the TBs, etc.

[Eugene Nalimov, CCC posting Dec 13,2002]

The pawnless six men endgame tablebases are almost complete (except for the trivial ones). This is necessary of course to avoid the incomplete endgame tablebase problem (although you can use them to see the results without the best line of play), but it also makes them pretty useless and may actually slow down the Chess engine if it probes useless positions.

Of some interest is the KQQKQQ tablebase. It was one of the first 6 piece tablebase generated back in 1999 especially, to aid in the Kasparov versus World game.

It is estimated a whole set of 6 piece Nalimov tablebases (when ready) will take up at least 1 terrabye (1000 GB).

Unlike the nalimov tablebases it's possible to generate 6 piece Chessmaster tablebases using a normal 32 bit desktop and 512 ram.It has being reported that Marc Bourzutschky, has managed to use Chessmaster 9000's FEG to generate 6 piece tablebases including the KRPPKR in about a month using 3 desktop computers (1.9GHZ and 2.4GHZ P4, and an an old 800MHZ P3). He has completed the above plus ,KQPKQP,KRPKBP,KRPKNP,KPPPKR,KPPPKB,KQPPKQ,KRPPKQ and supporting tablebases, and the size is about 0.5 Terabytes.

In addition certain 7 piece tablebases were completed.See here.


[A.11] How can I find out which tablebase is corrupted? How do I know the endgame tablebases are working?

If you download or generate your own tablebases, there is a possibility that some of them become corrupted. Some chess playing programs do a check and warn you if any of the tablebases are corrupted, but many don't. /p>

In practice though, checking if endgame tablebases are working in general for a chess program is usually a easy affair. Just setup a position, cover by the tablebases, and set the Chess engine to analyze or move. If everything is done correctly, the engine will move instantly, or come up with a instant evaluation score that will not change. Usually, the thinking lines will indicate that the score comes from the endgame tablebase. E.g Crafty will display a <EGTB> in the principle variation.

The above method is fine, except that it will take a long time to check all the tablebase files one by one. Here is what I recommend.

In general, when setting up tablebases, there are 2 possible errors.

  1. The interface is configured incorrectly. Generally this occurs when the path to the tablebase is in error.
  2. The tablebase files are corrupted.

The procedure above checks for the first problem. If you manage to get one tablebase working chances are the path is set correctly or the other tablebase files in the same directly should work, if they are not corrupted.

Here are 3 ways to check for corrupted files.

  • The first solution is to make use of datacomp.exe to check the integrity of the file But you will need to do this using a batch file for each file.
  • The second method involves checking the MD5 sum of each file with the ones posted on the ftp site. See post by William Penn on CCC on "How to use MD5 Sums to verify tablebases".Note you can download Wilhelm a free Chess program with tablebase functions that will do this automatically
  • Lastly, run the endgame tablebases in the original Winboard version of Crafty or Comet. Both will inform you which specific tablebases are damaged.


[A.12] What is datacomp.exe? Where can I get it?

Datacomp.exe is a utility provided by Eugene Nalimov and it's mostly used to compress Nalimov tablebases after you have generated them. Datacomp.exe can be used in reverse as well to uncompress and can be used to verify the integrity of existing tablebases, which is useful to check for errors during download.

You can get it at Dann Corbit's ftp site at http://cap.connx.com/chess-engines/new-approach/TBGEN.ZIP.The files, tbgeni.exe, tbgenm.exe that you get from there are exactly the same except that they have being complied using different compilers. One or the other might be faster for you.

To use datacomp to compress , use the following format:

datacomp e:8192 knk.nbb

Note this allows you to generate only up to 5 piece tablebases. It is not advisable to try for 6 piece tablebases anyway.


[A.13] How do I get Crafty to work with Endgame tablebases?

You need to edit the Crafty.rc file. For example, my line reads tbpath=c:\chesseng\tb . You should edit the line to point to the directory where your endgame tablebase files are currently located. The procedure for setting up endgame tablebases is similar for other Winboard engines that you can download. See my other FAQ on Winboard and Chess engines


[A.14] How can I get Fritz to use Endgame tablebases?

The advice below applies for users of Fritz 6. Users of newer chessbase software like Fritz 7 etc, have the additional option of setting up the tablebase path within the interface.

First, copy all your tablebase files into one directory, say C:\Nalimov

Next locate the file chssbase.ini [Not Chessbase.ini!] . It is usually in your Windows directory. Part of the file is something like this

[Tablebase]

Path=C:\Nalimov

CacheSizeKB=1024

Just edit the path to point to the directory where your endgame tablebase files are currently located and remember to save.This should work for all Chessbase engines including Junior,Nimzo,Hiracs and the new Chessbase engines Shredder and Tiger. For further information, refer to Steve Lopez's T-notes on"Tablebases and Fritz endgame Tablebase", 2 July 2000 and "Using Endgame CDs in Chessbase 7", 21 March 1999

Please note that if the endgame tablebases that you use are corrupted in some way (perhaps through a incomplete download) Fritz/Junior etc will refuse to run. To find out which tablebase is corrupted see Section A.11


[A.15] What is the difference between tablebases download from Dr Hyatt's ftp site and those on the Chessbase endgame turbo CD? Can they be used together?

Generally the tablebases that come in the Chessbase Endgame turbo are in the format kxxkxxnbb.emd compared to that downloaded, which come in the form kxxkxx.nbb.emd .Otherwise I think they should be exactly the same. I have generally found that Fritz can use either form, but you may want to add or remove the dot, if it refuses to work.

Also kxxkxx_nbb.emd should work as well.

In general Nalimov compressed tablebases bought from other commercial companies are also interchangeable with the downloaded ones.


[A.16] What are the files ending with .tbs? What about those ending with nbb and nbw? Do I need both?

Tbs stands for tablebase summary and give stats on the number of positions which are won, losses etc. They are not necessary if you are not interested in such statistics.

Earlier versions of Nalimov's code need the .nbw and .nbb of symmetrical endgames. Later this was changed (when support of 6-men TBs was added). So, engines using the older code will need both, and newer code will only need one. The list of the symmetrical TBs in the code are knkn, kbkb, krkr, kqkq, knnknn, kbbkbb, krrkrr, kqqkqq but not kpkp

There is new Eugene Nalimov code that allows you to use only one nbw file in all cases except when there are symmetrical positions for example in KRKR positions. This may or may not work depending on the Chess engine and probing code used. For access to 6 men tablebase positions, the new Nalimov code but be used, however for symmetric positions like knkn, kbkb, krkr, kqkq, knnknn, kbbkbb, krrkrr, kqqkqq (but it seems not Kpkp) you need both nbb and nbw.

To be safe though it's best to have both (or download nbw first and see if it works), as currently it's not certain how many Chess engines [besides Crafty] use the new Eugene code, and you can't really save much space anyway for the symmetric 4 men tablebases because they are pretty small anyway.

This is unlike the case of Edwards tablebases or Chessmaster's EGDB , where you need only either the file ending with tbb [positions with black to move for Edwards] or tbw [positions with white to move]. But even for those, it's much faster to have both since with only one set, the engine has to do a 2 ply search instead of 1.


[A.17] Help, the endgame tablebases are not working properly!

There are some possible reasons

  1. You specified the wrong pathway for the endgame tablebases.

  2. File is corrupted or in the wrong form , they should be in the form kxxkxx.nbw.emd or kxxkxx.nbb.emd [for compressed Nalimov tablebases]. See Section [A.11]

  3. One of the files either kxxkxx.nbw.emd or kxxkxx.nbb.emd is missing. You need both of them.

  4. You are using the wrong type of endgame table bases or the Chess program does not support the use of endgame tablebases.

To check whether, the endgame tablebase is corrupted (perhaps during download) , you can check the file sizes with the ones available online or use datacomp.exe (which is part of the tbgen) to check. The command you need is datacomp t kxxkxx.emdwhere kxxkxx is the file you want to check. This can be very tedious if you want to check all the endgame tablebase files, so it might be a good idea to use a batch file.

If the Program for some reason refuses to make a obvious winning move [usually queening] in a endgame, it is possible, we have a case of incomplete tablebases. See Section A.9 .


[A.18] Can I use tablebase files in zipped form?

No. Nalimov tablebases in the emd format are already compressed, and there is little if any gain from further zipping them up.Same goes for the Chessmaster EDGB format.


[A.19] Where can I get a useful graphical browser to view and practice endgame tablebases?What about an online searchable database?

Let's do them in reverse order. The following websites allow you to search the results of a given endgame position, if you don't have the tablebase files.Most sites below require Java or at least javascript.

What if you already have the tablebases but need an application to view and search through them?

  • SCID

    Shane Hudson [author of SCID] writes

    "I find Scid very useful for browsing Nalimov tablebases. If a position is winning, it shows which moves mate the fastest, if it is losing it shows which moves survive longest, and if it is drawn it shows which moves keep the position drawn and which moves (if any) lose. Of course, being Scid's author I may be biased... " [Posting to rec.games.chess.computer on 12-01-2001]
    SCID 3.3 and up also keep tracks of which tablebases you have and stores statistics about each tablebase.
  • Wihelm- A free Chess program but more importantly it comes with powerful tablabase functions that allow you to automatically check the integrity of tablebases using MD5 checksums as well as other functions similar to the "endgame oracle"in shredder 6, (see below) The website is in German, but the program is in English/German and there is a good english PDF help file which explains the various tablebase functions.
  • Another alternative including using Fritz, and Chessbase 7 or 8, which has a special engine to view Thompson tablebases.
  • There is also the "endgame oracle" in Shredder 6 and Shredder Classic .
  • Freezer - A commercial tool that uses Nalimov tablebases to help endgame analysis. By "freezing" actually restricting certain features in the position (pawn blocked, king cannot move beyond 4th rank etc), coupled with Nalimov tablebases, it helps clarify certain aspects of endgames like fortresses.
  • GAFS - a program to generate and interrogate tablebases and a library, under the form of an object file, with an example for using these tablebases in a chess program. As cpu time for generation of EGTBs is very high, the program contains an intermediate saving system to avoid loss of the entire work if for any reason the computer goes down or computation must be interrupted; so it is possible to run the program during the night, stop calculation in the morning and restart again in the successive night.


[A.20] Misc Questions

Will we ever have 32 piece tablebases?

To be worked on

Why don't we allow chess engines to access and use endgame tablebases over the internet?

To be worked on

What about doing a distributed peer to peer method of generating endgame tablebase?

To be worked on


Aaron Tay

Last Modified 11/30/2006 13:51:59

 



 

 

Fom wikipedia

Background

Physical limitations of computer hardware aside, in principle it is possible to solve any game under the condition that the complete state is known and there is no random chance. Strong solutions, i.e. algorithms that can produce perfect play from any position,[4] are known for some simple games such as Tic Tac Toe (draw with perfect play) and Connect Four (first player wins). Weak solutions exist for somewhat more complex games, such as checkers (with perfect play on both sides the game is known to be a draw, but it is not known for every position created by less-than-perfect play what the perfect next move would be). Other games, such as chess (from the starting position) and Go, have not been solved because their game complexity is too vast for computers to evaluate all possible positions. To reduce the game complexity, researchers have modified these complex games by reducing the size of the board, or the number of pieces, or both.

Computer chess is one of the oldest domains of artificial intelligence, having begun in the early 1930s. Claude Shannon proposed formal criteria for evaluating chess moves in 1949. In 1951, Alan Turing designed a primitive chess playing program, which assigned values for material and mobility; the program "played" chess based on Turing's manual calculations.[5]However, even as competent chess programs began to develop, they exhibited a glaring weakness in playing the endgame. Programmers added specific heuristics for the endgame – for example, the king should move to the center of the board.[6] However, a more comprehensive solution was needed.

In 1965, Richard Bellman proposed the creation of a database to solve chess and checkers endgames using retrograde analysis.[7][8] Instead of analyzing forward from the position currently on the board, the database would analyze backward from positions where one player was checkmated or stalemated. Thus, a chess computer would no longer need to analyze endgame positions during the game because they were solved beforehand. It would no longer make mistakes because the tablebase always played the best possible move.

In 1970, Thomas Ströhlein published a doctoral thesis[9][10] with analysis of the following classes of endgameKQKKRKKPKKQKRKRKB, and KRKN.[11] In 1977 the KQKR database was used in a match versus Grandmaster Walter Browne, see Computer chess#Using endgame databases.

Ken Thompson and others helped extend tablebases to cover all four- and five-piece endgames, including in particular KBBKNKQPKQ, and KRPKR.[12][13] Lewis Stiller published a thesis with research on some six-piece tablebase endgames in 1995.[14][15]

More recent contributors have included the following people:

  • Eugene Nalimov, after whom the popular Nalimov tablebases are named;
  • Eiko Bleicher, who has adapted the tablebase concept to a program called "Freezer" (see below);
  • Guy Haworth, an academic at the University of Reading, who has published extensively in the ICGA Journal and elsewhere;
  • Marc Bourzutschky and Yakov Konoval, who have collaborated to analyze endgames with seven pieces on the board.
  • Peter Karrer, who constructed a specialized seven-piece tablebase (KQPPKQP) for the endgame of the Kasparov versus The World online match.

The tablebases of all endgames with up to six pieces are available for free download, and may also be queried using web interfaces (see the external links below). Nalimov tablebase requires more than one terabyte of storage space.[16][17]

[edit]Generating tablebases

[edit]Metrics: Depth to conversion and depth to mate











Before creating a tablebase, a programmer must choose a metric of optimality – in other words, he must define at what point a player has "won" the game. Every position can be defined by its distance (i.e. the number of moves) from the desired endpoint. Two metrics are generally used:

  • Depth to mate (DTM). A checkmate is the only way to win a game.
  • Depth to conversion (DTC). The stronger side can also win by capturing material, thus converting to a simpler endgame. For example, in KQKR, conversion occurs when White captures the Black rook.

Haworth has discussed two other metrics, namely "depth to zeroing-move" (DTZ) and "depth by the rule" (DTR). These metrics support the fifty-move rule, but DTR tablebases have not yet been computed, and DTZ tablebases have not yet been generally released to the public.[18]

The difference between DTC and DTM can be understood by analyzing the diagram at right. How White should proceed depends on which metric is used.

MetricPlayDTCDTM
DTC1. Qxd1 Kc8 2. Qd2 Kb8 3. Qd8 mate13
DTM1. Qc7+ Ka8 2. Qa7 mate22

According to the DTC metric, White should capture the rook because that leads immediately to a position which will certainly win (DTC = 1), but it will take two more moves actually to checkmate (DTM = 3). In contrast according to the DTM metric, White mates in two moves, so DTM = DTC = 2.

This difference is typical of many endgames. Usually DTC is smaller than DTM, but the DTM metric leads to the quickest checkmate. Exceptions occur where the weaker side has only a king, and in the unusual endgame of two knights versus one pawn; then DTC = DTM because either there is no defending material to capture or capturing the material does no good. (Indeed, capturing the defending pawn in the latter endgame results in a draw.)

[edit]Step 1: Generating all possible positions

David Levy, How Computers Play Chess










Once a metric is chosen, the first step is to generate all the positions with a given material. For example, to generate a DTM tablebase for the endgame of king and queen versus king (KQK), the computer must describe approximately 40,000 unique legal positions.

Levy and Newborn explain that the number 40,000 derives from a symmetry argument. The Black king can be placed on any of ten squares: a1, b1, c1, d1, b2, c2, d2, c3, d3, and d4 (see diagram). On any other square, its position can be considered equivalent by symmetry of rotation or reflection. Thus, there is no difference whether a Black king in a corner resides on a1, a8, h8, or h1. Multiply this number of 10 by at most 60 (legal remaining) squares for placing the White king and then by at most 62 squares for the White queen. The product 10×60×62 = 37,200. Several hundred of these positions are illegal, impossible, or symmetrical reflections of each other, so the actual number is somewhat smaller.[19][20]

For each position, the tablebase evaluates the situation separately for White-to-move and Black-to-move. Assuming that White has the queen, almost all the positions are White wins, with checkmate forced in not more than ten moves. Some positions are draws because ofstalemate or the unavoidable loss of the queen.

Each additional piece added to a pawnless endgame multiplies the number of unique positions by about a factor of sixty which is the approximate number of squares not already occupied by other pieces.

Endgames with one or more pawns increase the complexity because the symmetry argument is reduced. Since pawns can move forward but not sideways, rotation and vertical reflection of the board produces a fundamental change in the nature of the position.[21] The best calculation of symmetry is achieved by limiting one pawn to 24 squares in the rectangle a2-a7-d7-d2. All other pieces and pawns may be located in any of the 64 squares with respect to the pawn. Thus, an endgame with pawns has a complexity of 24/10 = 2.4 times a pawnless endgame with the same number of pieces.

[edit]Step 2: Evaluating positions using retrograde analysis

Tim Krabbé explains the process of generating a tablebase as follows:

"The idea is that a database is made with all possible positions with a given material [note: as in the preceding section]. Then a subdatabase is made of all positions where Black is mated. Then one where White can give mate. Then one where Black cannot stop White giving mate next move. Then one where White can always reach a position where Black cannot stop him from giving mate next move. And so on, always a ply further away from mate until all positions that are thus connected to mate have been found. Then all of these positions are linked back to mate by the shortest path through the database. That means that, apart from 'equi-optimal' moves, all the moves in such a path are perfect: White's move always leads to the quickest mate, Black's move always leads to the slowest mate."[22]

The retrograde analysis is only necessary from the checkmated positions. Other positions need not be worked from because every position that is not reached from a checkmated position is a draw.[23]

Figure 1 illustrates the idea of retrograde analysis. White mates in two moves with 1. Kc6, leading to the position in Figure 2. Then if 1...Kb8 2. Qb7 mate, and if 1...Kd8 2. Qd7 mate (Figure 3).

Figure 3, before White's second move, is defined as "mate in one ply." Figure 2, after White's first move, is "mate in two ply," regardless of how Black plays. Finally, the initial position in Figure 1 is "mate in three ply" (i.e., two moves) because it leads directly to Figure 2, which is already defined as "mate in two ply." This process, which links a current position to another position that could have existed one ply earlier, can continue indefinitely.

Each position is evaluated as a win or loss in a certain number of moves. At the end of the retrograde analysis, positions which are not designated as wins or losses are necessarily draws.

Figure 1
Solid white.svgabcdefghSolid white.svg
8a8 black kingb8 black kingc8 black kingd8 black kinge8 black kingf8 black kingg8 black kingh8 black king8
7a7 black kingb7 black kingc7 black kingd7 black kinge7 black kingf7 black kingg7 black kingh7 white queen7
6a6 black kingb6 black kingc6 black kingd6 black kinge6 black kingf6 black kingg6 black kingh6 black king6
5a5 black kingb5 black kingc5 black kingd5 white kinge5 black kingf5 black kingg5 black kingh5 black king5
4a4 black kingb4 black kingc4 black kingd4 black kinge4 black kingf4 black kingg4 black kingh4 black king4
3a3 black kingb3 black kingc3 black kingd3 black kinge3 black kingf3 black kingg3 black kingh3 black king3
2a2 black kingb2 black kingc2 black kingd2 black kinge2 black kingf2 black kingg2 black kingh2 black king2
1a1 black kingb1 black kingc1 black kingd1 black kinge1 black kingf1 black kingg1 black kingh1 black king1
Solid white.svgabcdefghSolid white.svg
White to move: mate in three ply (Kc6)
Figure 2
Solid white.svgabcdefghSolid white.svg
8a8 black kingb8 black kingc8 black kingd8 black kinge8 black kingf8 black kingg8 black kingh8 black king8
7a7 black kingb7 black kingc7 black kingd7 black kinge7 black kingf7 black kingg7 black kingh7 white queen7
6a6 black kingb6 black kingc6 white kingd6 black kinge6 black kingf6 black kingg6 black kingh6 black king6
5a5 black kingb5 black kingc5 black kingd5 black kinge5 black kingf5 black kingg5 black kingh5 black king5
4a4 black kingb4 black kingc4 black kingd4 black kinge4 black kingf4 black kingg4 black kingh4 black king4
3a3 black kingb3 black kingc3 black kingd3 black kinge3 black kingf3 black kingg3 black kingh3 black king3
2a2 black kingb2 black kingc2 black kingd2 black kinge2 black kingf2 black kingg2 black kingh2 black king2
1a1 black kingb1 black kingc1 black kingd1 black kinge1 black kingf1 black kingg1 black kingh1 black king1
Solid white.svgabcdefghSolid white.svg
Black to move: mate in two ply (Kd8 or Kb8)
Figure 3
Solid white.svgabcdefghSolid white.svg
8a8 black kingb8 black kingc8 black kingd8 black kinge8 black kingf8 black kingg8 black kingh8 black king8
7a7 black kingb7 black kingc7 black kingd7 black kinge7 black kingf7 black kingg7 black kingh7 white queen7
6a6 black kingb6 black kingc6 white kingd6 black kinge6 black kingf6 black kingg6 black kingh6 black king6
5a5 black kingb5 black kingc5 black kingd5 black kinge5 black kingf5 black kingg5 black kingh5 black king5
4a4 black kingb4 black kingc4 black kingd4 black kinge4 black kingf4 black kingg4 black kingh4 black king4
3a3 black kingb3 black kingc3 black kingd3 black kinge3 black kingf3 black kingg3 black kingh3 black king3
2a2 black kingb2 black kingc2 black kingd2 black kinge2 black kingf2 black kingg2 black kingh2 black king2
1a1 black kingb1 black kingc1 black kingd1 black kinge1 black kingf1 black kingg1 black kingh1 black king1
Solid white.svgabcdefghSolid white.svg
White to move: mate in one ply (Qd7)


[edit]Step 3: Verification

After the tablebase has been generated, and every position has been evaluated, the result must be verified independently. The purpose is to check the self-consistency of the tablebase results.[24]

For example, in Figure 1 above, the verification program sees the evaluation "mate in three ply (Kc6)." It then looks at the position in Figure 2, after Kc6, and sees the evaluation "mate in two ply." These two evaluations are consistent with each other. If the evaluation of Figure 2 were anything else, it would be inconsistent with Figure 1, so the tablebase would need to be corrected.

[edit]Captures, pawn promotion, and special moves

A four-piece tablebase must rely on three-piece tablebases that could result if one piece is captured. Similarly, a tablebase containing a pawn must be able to rely on other tablebases that deal with the new set of material after pawn promotion to a queen or other piece. The retrograde analysis program must account for the possibility of a capture or pawn promotion on the previous move.[25]

Tablebases assume that castling is not possible for two reasons. First, in practical endgames, this assumption is almost always correct. (However, castling is allowed by convention incomposed problems and studies.) Second, if the king and rook are on their original squares, castling may or may not be allowed. Because of this ambiguity, it would be necessary to make separate evaluations for states in which castling is or is not possible.

The same ambiguity exists for the en passant capture, since the possibility of en passant depends on the opponent's previous move. However, practical applications of en passant occur frequently in pawn endgames, so tablebases account for the possibility of en passant for positions where both sides have at least one pawn.

[edit]Using a priori information










According to the method described above, the tablebase must allow the possibility that a given piece might occupy any of the 64 squares. In some positions, it is possible to restrict the search space without affecting the result. This saves computational resources and enables searches which would otherwise be impossible.

An early analysis of this type was published in 1987, in the endgame KRP(a2)KBP(a3), where the Black bishop moves on the dark squares (see example position at right).[26] In this position, we can make the following a priori assumptions:

1. If a piece is captured, we can look up the resulting position in the corresponding tablebase with five pieces. For example, if the Black pawn is captured, look up the newly created position in KRPKB.
2. The White pawn stays on a2; capture moves are handled by the 1st rule.
3. The Black pawn stays on a3; capture moves are handled by the 1st rule.[27]

The result of this simplification is that, instead of searching for 48 * 47 = 2,256 permutations for the pawns' locations, there is only one permutation. Reducing the search space by a factor of 2,256 facilitates a much quicker calculation.

Bleicher has designed a commercial program called "Freezer," which allows users to build new tablebases from existing Nalimov tablebases with a priori information. The program can produce a tablebase for seven-piece positions with blocked pawns, even though seven-piece tablebases are generally not available.[28]

[edit]Applications

[edit]Correspondence chess

Kasparov vs The World, 1999

In correspondence chess, a player may consult a chess computer for assistance, provided that the etiquette of the competition allows this. A six-piece tablebase (KQQKQQ) was used to analyze the endgame that occurred in the correspondence game Kasparov versus The World.[29] Players have also used tablebases to analyze endgames from over-the-board play after the game is over.

Competitive players need to know that tablebases ignore the fifty-move rule. According to that rule, if fifty moves have passed without a capture or a pawn move, either player may claim a draw. FIDE changed the rules several times, starting in 1974, to allow one hundred moves for endgames where fifty moves were insufficient to win. In 1988, FIDE allowed seventy-five moves for KBBKN, KNNKP, KQKBB, KQKNN, KRBKR, and KQPKQ with the pawn on the seventh rank, because tablebases had uncovered positions in these endgames requiring more than fifty moves to win. In 1992, FIDE canceled these exceptions and restored the fifty-move rule to its original standing.[18]Thus a tablebase may identify a position as won or lost, when it is in fact drawn by the fifty-move rule.

Haworth has designed a tablebase that produces results consistent with the fifty-move rule. However most tablebases search for the theoretical limits of forced mate, even if it requires several hundred moves.

[edit]Computer chess

The knowledge contained in tablebases affords the computer a tremendous advantage in the endgame. Not only can computers play perfectly within an endgame, but they can simplify to a winning tablebase position from a more complicated endgame.[30] For the latter purpose, some programs use "bitbases" which give the game-theoretical value of positions without the number of moves until conversion or mate — that is, they only reveal whether the position is won, lost or draw. Sometimes even this data is compressed and the bitbase reveals only whether a position is won or not, making no difference between a lost and a draw game.[23]

However, some computer chess experts have observed practical drawbacks.[31] In addition to ignoring the fifty-move rule, a computer in a difficult position might avoid the losing side of a tablebase ending even if the opponent cannot practically win without himself knowing the tablebase. The adverse effect could be a premature resignation, or an inferior line of play that loses with less resistance than a play without tablebase might offer.

Another drawback is that tablebases require a lot of memory to store the many thousands of positions. The Nalimov tablebases, which use special-purpose compression technique, require 7.05 GB of hard disk space for all five-piece endings. The six-piece endings require approximately 1.2 terabytes.[32][33] Nalimov seven-piece tablebases require more hard drive storage capacity and RAM to operate than will be practical to use for the foreseeable future. Bitbases, however, take much less space. Shredderbases, for example, used by theShredder program, compress all three, four and five piece bases into 157 MB. This is a mere fraction of the 7.05 GB that the Nalimov tablebases require.[34]

Some computers play better overall if their memory is devoted instead to the ordinary search and evaluation function. Modern computers analyze far enough ahead conventionally to handle the elementary endgames without needing tablebases (i.e. without suffering from the horizon effect). It is only for more sophisticated positions that the tablebase will improve significantly over the ordinary computer.

[edit]Endgame theory

In contexts where the fifty-move rule may be ignored, tablebases have answered longstanding questions about whether certain combinations of material are wins or draws. The following interesting results have emerged:

  • KBBKN — Bernhard Horwitz and Josef Kling (1851) proposed that Black can draw by entering a defensive fortress, but tablebases demonstrated a general win, with maximum DTC = 66 or 67 and maximum DTM = 78.[35] (Also see pawnless chess endgame.)
  • KNNKP — Alexey Troitsky established this as a win for the knights if the pawn was blocked behind the Troitzky line. Analysis of the tablebases has clarified that even if the pawn has crossed the Troitzky line, White can sometimes win by forcing zugzwang.[36] Maximum DTC = DTM = 115 moves.
  • KNNNNKQ — The knights win in 62.5 percent of positions, with maximum DTM = 85 moves.[37][38]
  • KQRKQR — Despite the equality of material, the player to move wins in 67.74% of positions.[39] The maximum DTC is 92, and the maximum DTM is 117. In both this endgame and KQQKQQ, the first player to check usually wins.[40]KRNKNN and KRBKNN — Friedrich Amelung had analyzed these two endgames in the 1900s.[41] KRNKNN and KRBKNN are won for the strongest side in 78% and 95% of the cases, respectively.[22][42] Stiller's DTC tablebase revealed several lengthy wins in these endgames. The longest win in KRBKNN has a DTC of 223 and a DTM of 238 moves (not shown). Even more amazing is the position at right, where White wins starting with 1. Ke6! Stiller reported the DTC as 243 moves, and the DTM was later found to be 262 moves.[43]

For some years, this position held the record for the longest computer-generated forced mate (Otto Blathy had composed a "mate in 292 moves" problem already in 1889).[44] However, in May 2006, Bourzutschky and Konoval discovered a KQNKRBN position with an astonishing DTC of 517 moves. This was more than twice as long as Stiller's maximum, and almost 200 moves beyond the previous record of a 330 DTC for a position of KQBNKQB_1001. Bourzutschky wrote, "This was a big surprise for us and is a great tribute to the complexity of chess."[45][46]

In August 2006, Bourzutschky released preliminary results from his analysis of the following seven-piece endgames: KQQPKQQ, KRRPKRR, and KBBPKNN.[24]


Many positions are winnable although at first sight they appear to be non-winnable. For example, this position is a win for Black in 154 moves (during which white pawn is liquidated after around 80 moves) (absolutely non-typical for this kind of endgame) (see Six-Man Endgame Server - http://www.k4it.de/index.php?topic=egtb&lang=en).[citation needed]

[edit]Endgame studies



Since many composed endgame studies deal with positions that exist in tablebases, their soundness can be checked using the tablebases. Some studies have been cooked, i.e. proved unsound, by the tablebases. That can be either because the composer's solution does not work, or else because there is an equally effective alternative that the composer did not consider. Another way tablebases cook studies is a change in the evaluation of an endgame. For instance, the endgame with a queen and bishop versus two rooks was thought to be a draw, but tablebases proved it to be a win for the queen and bishop, so almost all studies based on this endgame are unsound.[47]

For example, Erik Pogosyants composed the study at right, with White to play and win. His intended main line was 1. Ne3 Rxh2 2. O-O-O mate! A tablebase discovered that 1. h4 also wins for White in 33 moves, even though Black can capture the pawn (which is not the best move – in case of capturing the pawn black loses in 21 moves, while Kh1-g2 loses in 32 moves). Coincidentally, the tablebase does not recognize the composer's solution because it includes castling.[48]

While tablebases have cooked some studies, they have assisted in the creation of other studies. Composers can search tablebases for interesting positions, such as zugzwang, using a method called data mining. For all three- to five-piece endgames and pawnless six-piece endgames, a complete list of mutual zugzwangs has been tabulated and published.[49][50][51]

There has been some controversy whether to allow endgame studies composed with tablebase assistance into composing tourneys. In 2003, the endgame composer and expert John Roycroft summarized the debate:

"[N]ot only do opinions diverge widely, but they are frequently adhered to strongly, even vehemently: at one extreme is the view that since we can never be certain that a computer has been used it is pointless to attempt a distinction, so we should simply evaluate a 'study' on its content, without reference to its origins; at the other extreme is the view that using a 'mouse' to lift an interesting position from a ready-made computer-generated list is in no sense composing, so we should outlaw every such position."[52]

Roycroft himself agrees with the latter approach. He continues, "One thing alone is clear to us: the distinction between classical composing and computer composing should be preserved for as long as possible: if there is a name associated with a study diagram that name is a claim of authorship."[52]

Mark Dvoretsky, an International Master, chess trainer, and author, took a more permissive stance. He was commenting in 2006 on a study by Harold van der Heijden, published in 2001, which reached the position at right after three introductory moves. The drawing move for White is 4. Kb4!! (and not 4. Kb5), based on a mutual zugzwang that may occur three moves later.

Dvoretsky comments

"Here, we should touch on one delicate question. I am sure that this unique endgame position was discovered with the help of Thompson’s famous computer database. Is this a 'flaw,' diminishing the composer's achievement?

"Yes, the computer database is an instrument, available to anyone nowadays. Out of it, no doubt, we could probably extract yet more unique positions – there are some chess composers who do so regularly. The standard for evaluation here should be the result achieved. Thus: miracles, based upon complex computer analysis rather than on their content of sharp ideas, are probably of interest only to certain aesthetes."[53]

[edit]"Play chess with God"

On the Bell Labs website, Ken Thompson maintains a link to some of his tablebase data. The headline reads, "Play chess with God."[54]

Regarding Stiller's long wins, Tim Krabbé struck a similar note:

"A grandmaster wouldn't be better at these endgames than someone who had learned chess yesterday. It's a sort of chess that has nothing to do with chess, a chess that we could never have imagined without computers. The Stiller moves are awesome, almost scary, because you know they are the truth, God's Algorithm – it's like being revealed the Meaning of Life, but you don't understand one word."[22]

[edit]Nomenclature

Originally, an endgame tablebase was called an "endgame data base" or "endgame database". This name appeared in both EG and the ICCA Journal starting in the 1970s, and is sometimes used today. According to Haworth, the ICCA Journal first used the word "tablebase" in connection with chess endgames in 1995.[55] According to that source, a tablebase contains a complete set of information, but a database might lack some information.

Haworth prefers the term "Endgame Table", and has used it in the articles he has authored.[56] Roycroft has used the term "oracle database" throughout his magazine, EG.[57]Nonetheless, the mainstream chess community has adopted "endgame tablebase" as the most common name.

[edit]Books

John Nunn has written three books based on detailed analysis of endgame tablebases:

[edit]See also

[edit]Notes

  1. ^ Website of KingsRow about the creation of the eight-piece endgame tablebase
  2. ^ gothicchess.com; examples of long endings for Gothic chess
  3. ^ Ralpf Gasser (1996). "Solving nine men's morris".
  4. ^ Allis, Louis Victor (1994) (PDF). Searching for Solutions in Games and Artificial Intelligence. Department of Computer Science, University of Limburg. p. 8. ISBN 90-900748-8-0. Retrieved 2009-05-03.
  5. ^ Levy & Newborn, pp. 25-38
  6. ^ Levy & Newborn, pp. 129-30
  7. ^ Stiller, p. 84
  8. ^ R. E. Bellman (February 1965). "On the application of dynamic programming to the determination of optimal play in chess and checkers". Proceedings of the National Academy of Sciences of the United States of America 53 (2): 244–246.doi:10.1073/pnas.53.2.244.
  9. ^ T. Ströhlein (1970). Untersuchungen über kombinatorische Spiele [Translation: Investigations on Combinatorial Games] Ph.D. Thesis. Technical University of Munich.
  10. ^ See also "The 'End-Papers'" (PDF). EG (52): 25. July 1978. Retrieved 2007-04-01. "Niblett and Kopec described, and later demonstrated, the optimal 0103 data base. (This work was in fact first done and published by Thomas Strohlein, Munich, in 1970, but only a single analytical line is contained in his doctoral thesis.)"
  11. ^ T. Niblett; A. J. Roycroft (June 1979). "How the GBR Class 0103 Data Base was Created" (PDF). EG (56): 145–46. Retrieved 2007-05-04.
  12. ^ Levy & Newborn, p. 144
  13. ^ See also:
  14. ^ Stiller, pp. 68-113
  15. ^ See also: L. B. Stiller (1991). "Some Results from a Massively Parallel Retrograde Analysis". ICCA Journal.
  16. ^ J. Hurd; G. McC. Haworth.. "Chess Endgame Data Assurance." (PDF). Retrieved 2008-12-13.
  17. ^ Gary M. Danelishen (25 February 2008). The Final Theory of Chess. Open Wiki of Chess Openings. p. 6. ISBN 978-0-9815677-0-9. Retrieved 10 August 2011.
  18. a b G. McC. Haworth (March 2000). "Strategies for Constrained Optimisation" (PDF).ICGA Journal. Archived from the original on 2007-09-29. Retrieved 2009-06-20.
  19. ^ Levy & Newborn, pp. 140-43
  20. ^ See also Stiller 1995:93-98.
  21. ^ Muller, H.G.. "EGTB generator". Retrieved 2009-05-03. "Pawns would break the front-back and diagonal symmetries, because they care about direction in their moves."
  22. a b c Tim Krabbé.. "Stiller's Monsters or Perfection in Chess.". Retrieved 2007-04-01.
  23. a b Aaron Tay. "A guide to Endgames Tablebase". Retrieved 2009-05-02.
  24. a b M. Bourzutschky (2006-08-27). "7-man endgames with pawns". CCRL Discussion Board. Retrieved 2010-06-14.
  25. ^ Stiller, pp. 99-100
  26. ^ H. J. Herik; I. S. Herschberg, N. Naka (1987). "A Six-Men-Endgame Database: KRP(a2)KbBP(a3)". ICGA Journal 10 (4): 163–180.
  27. ^ E. Bleicher (2004-08-26.). "Building Chess Endgame Databases for Positions with many Pieces using A-priori Information." (PDF). Retrieved 2007-04-01.
  28. ^ K. Müller (May 2005). "Freeze!" (PDF). Endgame CornerChessCafe.com. Retrieved 2007-04-01.
  29. ^ E. V. Nalimov; C. Wirth, G. McC. Haworth (1999). "KQQKQQ and the Kasparov–World Game". ICGA Journal 22 (4): 195–212.
  30. ^ Steven A. Lopez (2006-11-11). "Shredderbases". ChessBase.com. Retrieved 2007-04-01.
  31. ^ A. Tay (2002-06-30). "Can use of endgame tablebases weaken play?". Retrieved 2007-04-01.
  32. ^ David Kirkby (2007-03-12). "Endgame Tablebases"ChessDB Tutorial. Retrieved 2007-04-01.
  33. ^ Stefan Meyer-Kahlen. "Shredder Computer Chess Download - Endgame Database Info". Retrieved 2008-08-17.
  34. ^ "Shredder Computer Chess Download - Shredderbases". Retrieved 2008-08-09.
  35. ^ A. J. Roycroft (1984). "Two Bishops Against Knight" (PDF). EG (75): 249. Retrieved 2007-05-04.
  36. ^ D. V. Hooper (1986). "GBR Class 0002.01" (PDF). EG (83): 3. Retrieved 2007-05-04.
  37. ^ Tim Krabbé (2005-04-12). "282. First 7-piece endgame database"Open Chess Diary. Retrieved 2007-03-25.
  38. ^ Emil Vlasák (2005-07-21). "News in 7 piece EGTB". Retrieved 2007-03-25.
  39. ^ G. McC. Haworth (August 2001). "Discarding Like Pieces" (PDF). Archived from the original on 2007-09-29. Retrieved 2007-04-01.
  40. ^ Nunn, p. 379, 384
  41. ^ Stiller, p. 81
  42. ^ Tim Krabbé (2000-04-08). "60. Play chess with God"Open Chess Diary. Retrieved 2007-05-13.
  43. ^ Stiller, pp. 102-8
  44. ^ "Blathy". 2003-06-21. Archived from the original on 2009-10-24. Retrieved 2007-05-04.
  45. ^ Tim Krabbé (2006-03-31). "311. White plays and wins in 330 moves"Open Chess Diary. Retrieved 2007-05-04.
  46. ^ Tim Krabbé (2006-05-26). "316. A 517-move win"Open Chess Diary. Retrieved 2007-05-04.
  47. ^ Nunn, pp. 367-68
  48. ^ Tim Krabbé (2006-09-15). "324. A cooked, correct study"Open chess diary. Retrieved 2007-05-04.
  49. ^ G. McC. Haworth; Editor: J.W.H.M. Uiterwijk (2001). "3–5 Man Mutual Zugzwangs in Chess". Proceedings of the CMG 6th Computer Olympiad Computer-Games Workshop TR CS 01-04.
  50. ^ G. McC. Haworth (2001). "Ken Thompson's 6-man Tables". ICGA Journal.
  51. ^ G. McC. Haworth; P. Karrer, J. A. Tamplin, and C. Wirth (2001). "3–5 Man Chess: Maximals and Mzugs". ICGA Journal 24 (4): 225–30.
  52. a b A. J. Roycroft (July 2003). "Editorial" (PDF). EG (149): 51. Retrieved 2007-05-04.
  53. ^ M. Dvoretsky (July 2006). "Study Composing Tourney" (PDF). The Instructor. ChessCafe.com. Retrieved 2007-04-01.
  54. ^ Ken Thompson (2002-08-21). "Play chess with God". Retrieved 2007-03-25.
  55. ^ Guy Haworth (1995). "Tablebases and Tables" (PDF). EG (137): 151. Retrieved 2007-05-04.
  56. ^ "Publications for Mr Guy Haworth"Information Systems at Reading. The University of Reading. Retrieved 2009-06-20.
  57. ^ For example, in "Proposal For The Guidance Of Tourney Organisers, Composers And Judges: 0. Definitions" (PDF). EG (135): 9. Retrieved 2007-04-01. "odb — otherwise known as total information database or tablebase."

[edit]References

[edit]External links

 

 

 

 

 

 
An endgame tablebase is a computerized database of all chess positions within certain endgames. The tablebase reveals the game-theoretical value of each position (win, loss, or draw), and how many moves it will take to achieve that result with perfect play. Thus, the tablebase acts as an oracle, always providing the optimal moves for both White and Black.


Hint: You can copy the FEN string by selecting and copying it. In most 
browsers you can select the FEN string by triple-clicking on it.

NEW: Many features are also available via keyboard shortcuts: Flip board [f], Input FEN [i],
Back [t], King(s) [1], Queen(s) [2] etc., Move piece / Free [7], Change color [c],
Play best move [b], Move position [arrow keys].


Directory sizes (approx.):

  3-4-5/              7GB
  3+3/               96GB
  4+2/              111GB
  3+3-with-pawns/   430GB
  4+2-with-pawns/   513GB
  Total            1151GB