Fritz Endgame Turbo 3 - Part 1

COMPUTERS AND ENDGAMES

Endgames are tricky for computers to play because brute force calculation doesn't always make the grade. As we've discussed in previous columns, chess computer programs typically have a ten to twenty ply (i.e. half-move) lookahead depending on the level or time controls you've set for a game or how long you let the engine examine a position in Infinite Analysis mode. This means that a chess engine is looking no more than five to ten moves ahead. That's fine and dandy in tactical middlegames. But endgames are a different story. It might take five moves just for a pawn to promote (assuming that there's no possible interference by the opponent, i.e. his King is outside the "square of the pawn"). Keep in mind that this means five moves to a promotion, with an unknown number of moves to follow to achieve a checkmate. Chess engines really aren't capable of looking far enough ahead to see the complete course of action to achieve mate -- and this assumes a simple endgame.

Many endgames are at least moderately complex, at least as far as chess engines go. A human player, even just an average club player, might easily see the path to mate (at least in general terms: "Push the pawn, block my opponent's pawn, promote, then use the opposition to drive his King to the edge of the board where I can mate him"). This is called "technique" (and is sometimes why chess authors break off a game just as an endgame begins and simply give the comment "The rest is a matter of technique").

Humans can learn technique and remember it from game to game. Chess engines can't. That's why a lot of chess programs (particularly older ones) can sometimes fail to give mate in "won" positions (the Knight + Bishop vs. lone King mate is a notorious example). So how do programmers solve this problem?

DATABASES AND TABLEBASES

Back in the early 1990's, a partial solution was reached by the legendary Ken Thompson of Bell Labs. He created a set of endgame databases which chess engines could use to provide them with "technique" in simple endgames. Here's an example. Let's say that a chess program has the "won endgame" of King + Rook vs. lone King. This is a pretty simple endgame, but there are a couple of possible pitfalls (as anyone who remembers learning the endgame will tell you). The technique is pretty straightforward: "box in" the enemy King using the Rook, use the power of opposition to drive the enemy King toward the corner, then move the Rook again to make the "box" smaller. Then keep repeating this process until you have the enemy King trapped on the board edge (using your own King's power of opposition) and mate with the Rook. But there are a couple of places where you can slip up and either block your Rook with your own King or otherwise let the enemy King slide away; if you accidentally do this, you have to start the process from scratch all over again. And if you screw it up more than once, your win can easily become a draw due to the fifty-move rule.

Computers used to mess this one up all the time. But Thompson's endgame databases took care of the problem. The database for K+R vs. K contained every possible position of those three pieces (Kings count as pieces for the purposes of endgame databases/tablebases) on the board. The engine could look at the endgame database, thread individual positions together in a logical order, look at the results, and determine the quickest possible path to mate.

The Thompson databases revolutionized computer chess. No longer would engines hack around, making moves that violated the principles of proper technique, hoping to stumble into a mating sequence. Chess engines could now play simple endgame perfectly.

All things were not rosy in paradise, however. There were several flaws in the concept, the two most glaring of which were as follows:

1) In the event of capture (in multi-piece endings) or promotion (in the case of single-pawn endings, which were the only pawn endgames covered by the Thompson databases), the engine couldn't automatically switch from one endgame database to a new one which reflected the material change as part of its analytical process. For example, in the case of a K+R+P vs. King ending, the engine could only see as far ahead as the point at which the pawn promoted. It couldn't switch to a K+Q+R vs. King database as part of its analysis -- it wouldn't switch databases until the pawn promoted in the actual game. This somewhat ties into:

2) In late middlegames (in which the actual material balance covered by an endgame database hadn't yet been reached but was only a single capture away), the engine couldn't access the endgame databases "on the fly" and incorporate the information into its late middlegame analysis. In other words, a position covered by an endgame database had to already be on the board in the actual game before the database could be consulted by the engine.

These problems were solved later in the 1990's by Eugene Nalimov who created an improved form of endgame database, known as a tablebase. Not only could an engine switch automatically from one tablebase to another whenever it became necessary due to a change in material balance, but the engine could also incorporate information from endgame tablebases into its late middlegame analysis even when the endgame hadn't yet appeared on the board in the actual game.

So (using a quick example) in a late middlegame in which both players have a pair of Rooks, a pair of Bishops, and a pair of pawns, the engine might see a position seven moves ahead in which the Bishops and pawns are exchanged off the board, leaving a pure Rook ending. It could then consult a K+R vs. K+R tablebase to extend its analysis out to the game's conclusion and use that information to determine whether the line involving the massive material swap was a good idea.

Using the same material balance in the late middlegame (both players with a pair of Rooks, a pair of Bishops, and a pair of pawns), it might see a potential variation in which material is exchanged to produce a K+R+P vs. K+R ending. The engine not only can use the tablebases to provide information on this configuration of pieces, but can automatically switch to a K+R+Q vs. K+R or K+R+N vs. K+R tablebase to see the results and potential consequences for each promotion.

That's some pretty powerful stuff: "instant technique" available to chess engines not just when the endgame has been reached, but even in late middlegames when analyzing positions where the endgame might be reached. It's thus not surprising that Ken Thompson's pioneering endgame databases have since fallen into disuse, replaced by Eugene Nalimov's tablebases.

And that's what Fritz Endgame Turbo 3 is: a nine DVD set of Nalimov's three-, four-, five-, and six-piece endgame tablebases.

TECHNICAL MATTERS

This increased endgame knowledge available to chess engines comes at a price: storage space. The disk space required for the three- and four-piece tablebases isn't bad at all; in fact, they've sometimes appeared packaged on various chess programs' disks with plenty of space left over for the installation files, opening books, etc. But each time you add a piece to the mix you exponentially increase the amount of storage space needed for that tablebase. That's why the Endgame Turbo 3 comes on nine DVDs (not CDs). The original Endgame Turbo set came on four CDs and had all of the three- and four-piece endings, as well as a good-sized sampling of the most commonly encountered five-piece endings included. But when you start getting into the six-piece endings you have to deal with a huge amount of drive space; as a matter of fact one of the six-piece endings (Queen + 2 pawns vs. Queen -- for the remainder of our discussion I'll refrain from mentioning the Kings, since they're obviously assumed) is so large that it won't even fit on a DVD (more on this later). That's why the latest version of Endgame Turbo ships as a multi-DVD set.

We'll come back to the topic of disk space later, but I'll tell you this much now: a complete installation of all nine DVDs will require about 43 GB of hard drive space.

If you don't have that much drive space available, you can certainly manually copy just some of the tablebases to your hard drive using My Computer or Windows Explorer. There's a possible pitfall you need to be aware of though. When you copy a five- or six-piece tablebase to your drive, you need to make sure you also copy all possible sub-endgames (those that may arise due to promotion or simplification) too or else your larger tablebase won't operate properly.

Let's look at an example, which will also allow us a look at the file naming convention of the tablebases. Tablebase files always end in .emd, but you'll also see a string of letters before the .emd extension. You'll see something which looks like this:

kqbkn.nbb.emd

or

kqbkn.nbw.emd

There are two parts of these file names you need to be concerned about. The first string of letters (to the left of the first dot) tell you the material balance covered by the contents of the file. In both of the above cases the material balance is King + Queen + Bishop vs. King + Knight. So why are there two of these files? There needs to be one for each player (White and Black), and that's what the second string of characters (between the dots) tells you. The letter immediately to the left of the second dot tells you which side has the material advantage. So in the case of the file kqbkn.nbb.emd, Black is the player with the Queen and Bishop, while kqbkn.nbw.emd indicates that the White player has the Queen and Bishop.

This distinction becomes important when you're manually copying files (due to limited disk space available) instead of using the installation program. If you're copying a file like kqbkr.nbb.emd, you don't need to worry about copying any other five-piece files since no pawns are involved. But you do need to make sure to copy all of the sub-endgames which Queen + Bishop vs. Rook can simplify to due to material captures. If you don't, the five-piece file won't be able to automatically switch to the proper four-piece file and you'll end up with bum information. So you also need to copy:

Queen vs. Rook
Bishop vs. Rook
Queen + Bishop vs. King
Queen vs. King
Bishop vs. King
King vs. Rook (in the unlikely event that the Queen and Bishop get blundered away)

in order to be sure that the original five-piece file will have access to simplified material and will provide correct information.

And, of course, this gets even more involved when one of the five-pieces is a pawn, because you need to make sure you also copy all of the five-piece tablebases containing the material the pawn can promote to (and don't forget underpromotions), as well as all of the relevant three- and four-piece endings utilizing any of that material.

The three- and four-piecers aren't really an issue (as described above) because they easily fit on a CD with plenty of space left over (we're talking less than 40 MB here). Once you've copied them to your hard drive, you can safely copy any five-piece endings that don't involve pawns -- changes in the material balance are automatically covered by the three- and four-piece files. Only when copying five-piece files containing pawns do you have to worry about copying all of the "sister" files which contain the possible material to which the pawn can promote.

In the next column we'll talk more about manually copying files. For right now there are just a couple of things you need to remember about the tablebase files:

1) When discussing the number of pieces on the board, Kings are counted as pieces. So a five-piece file contains endgames involving both Kings with one player having two other pieces of wood on the board while his opponent has just one piece besides his King. (This also explains why there are no one-piece or two-piece tablebases -- that'd be dumb).

2) If you're copying the files manually, don't start copying the six-piece files first thinking that you're doing something "better". It's actually worse because the six-piece tablebases are useless without the five-, four-, and three-piece files covering endgames that will come about after simplification. You need to start with the smaller tablebases first and work upward, not the other way around.

Next time we'll discuss some nuts and bolts about installing the files and have a look at the tablebases in action. Until then, have fun!

You can e-mail me with your comments on ChessBase Workshop. All responses will be read, and sending an e-mail to this address grants us permission to use it in a future column. No tech support questions, please.

© 2006, Steven A. Lopez. All rights reserved.