FairyGen

FairyGen is a computer program to calculate End-Game Tables for chess end-games that might contain fairy pieces. FairyGen is freeware, and can be downloaded from http://hgm.nubati.net/fairygen.zip. This archive contains a number of Windows .exe files, as well as source code that can be used to generate binaries on other platforms. FairyGen can be run from a command-prompt window; e.g. the command

4men KQ.KR

issued in the folder where you unzipped the archive would generate an EGT for the end-game Queen vs Rook (with orthodox Kings). After FairyGen is done generating, it has to be terminated by hitting the Ctrl-C key (to exit from a loop where you can request move info for individual positions in a rather cumbersome way). The statistics of the EGT will then be left in a file 'rep2.txt' (which will be overwritten for each run).

What are End-Game Tables?

EGT contain, for every possible position with a given set of chess men on the board, how many moves it takes to force a 'winning event', or a special code when the position cannot be won. Depending on the flavor of the EGT this winning event can be a checkmate or stalemate, ('Distance To Mate), but it can also be a capture that leads to a position known to be won in an end-game with fewer men ('Distance To Conversion').

On an 8x8 board (to which FairyGen is restricted), each additional chess piece drives up the size of the EGT by a factor 64. So a 5-men EGT will contain 64 to the power 5 = 1 billion positions. Symmetry will reduce this number, though; when all chess men are 8-fold symmetric, and the board is square, only 1/8 of all positions have to be tabulated, (128 million), and the other positions can be mapped on those by means of reflections and rotations of the board. Conventionally the tabulated position will be the one that has the white King in the triangle spanned by the board squares a1-d1-d4. When the white King is on the diagonal a1-d4, FairyGen will use the second white piece as a 'tie breaker', listing only positions where it is in the triangle a1-h1-h8. (For the 9% of the remaining positions that have both these pieces on the diagonal, both diagonally mirrored positions are in the EGT; it isn't worth it to make things more complex for a space savings of a mere 9%.) So white always has to have at least two pieces; there is no provision for generating 2-men EGT of royal vs royal (which in principle could be won for unlike royals, or force stalemate even with equal royals).

FairyGen is a 'one-sided' EGT generator, meaning it will only distinguisn wins for white (and list their duration) vs non-wins, without figuring out whether the latter will be draws or losses. To get the losses you would have to generate an EGT with the reverse material (where they then show up as wins). For each position the EGT contains a single byte, holding the distance to the win (in full moves) with black to move, or the information whether the game is won or not with white to move. So a 5-men EGT with 8-fold symmetric pieces will be 128MB in size. FairyGen will not save the EGT on a file unless requested to do so, however. Note that an EGT does not hold any information to describe positions themselves; to which position a winning distance refers is purely determined by its location in the EGT (the 'index').

EGTs are generated by first constructing all checkmates, and then working backwards in time to determine all mated-in-1 positions, and from those all mated-in-2, etc. (retrograde solving). Likewise one first solves all 3-men positions that can be set up with the given material, which will give the 4-men positions that can be won through an immediate capture. These (plus the 4-men mates) will then be the starting point for retrograde solving of all 4-men positions, etc. In FairyGen one can choose to have it continue counting from the eventual mate (DTM), therough the -m option. By default it starts counting at the latest capture. This DTC is more useful, because it allows you to distinguish 'tactical wins' (which happens because a piece was hanging, or could be forked or skewered on the first move) from positions that are won by strategic superiority of the given material. E.g. in KR.KQ there will still be wins for the Rook with black to move (because the King was in check with the Queen more than 2 squares behind it), but these don't tell you anything about the relative strength of Queen and Rook, as any piece in the same location would have suffered the same fate. In the DTC statistics these show up as 'lost-in-1' positions, making it easy to discard them in the true Q vs R statistics. But in DTM they could have any DTM, depending on how long the Rook still needs to checkmate the bare King after it gobbled up the Queen. In DTC mode Fairy-Gen will first generate DTM for all smaller end-games, and then generate the EGT for the complete set of pieces, starting with a DTC of 10. (Which should really have been 0, so you should subtract 10 to get the true DTC. Sorry about that.)

Pieces

FairyGen can only handle normal leapers and (possibly finite-range) sliders/riders, and compounds thereof. It cannot handle hoppers, lame leapers or bent sliders (and also not the degenerate case of the latter, where the slider just changes stride but not direction, such as ski-sliders). The pieces are defined in a file piecedef.ini, where each line contains the (single-letter) name of the piece, a colon, and then a list of moves, given as 'dX,dY' pairs for the file and rank changes X and Y of a single move step. The pairs can optionally be suffixed by additional specs behind a comma. The letter 'c' there limits the move to captures, the letter 'n' to non-captures, while an 's' makes it a sliding move. A number (which must be the first behind the comma) would specify a finite range (and imply sliding). An asterisk '*' means the given specs of step and move rights also applies to all eight symmetry-equivalent steps in other directions. A '+' similarly indicates it applies to the eight directions obtained from it by horizontal and vertical mirroring, but this would take a special version of FairyGen that doesn't enforce diagonal symmetry (and is currently not included in the package) to work. (For purely orthogonal or diagonal steps * and + would be equivalent.)

The end-game to generate is specified as the list of white pieces followed by a period, and then the black pieces (e.g. KBB.KN). The letters correspond to those in the piecedef.ini file. The first-mentioned piece of either color will be considered the royal one.

Interpreting the statistics

It is not trivial to interpret the statistics of the EGT (i.e. how many times a certain DTC or DTM occurred, and which fraction of the positions was won in total with black or white to move). This because a quite large fraction of the positions is not tactically quiet, and immediately converts to an entirely different end-game. E.g. a dead draw like KNN.K has 25% of the positions with white to move won, because the black King happens to be in check and can be captured. (Of course one could elect to not count these, and correct the total for them. To this end FairyGen always prints the number of King captures amongst the white-to-move wins with the statistics.) And a pair of Knights is still comparatively weak; a Queen covers a much larger fraction of the board, on average. If black has a piece next to King strong enough to draw against the white material, there is a similar probability this piece will disappear before he gets the chance to move it, and in only 10% of these cases the remaining King will have been protecting it (and thus might recapture). So over 50% wtm wins in a hopelessly drawn ending is quite usual, as other tactics (e.g. fork followed by capture) can gain white a piece too.

Statistics is skewed in the opposit direction when black has the move. Then in 20-70% of the cases (depending on how many and powerful pieces black has, and how many result-swinging targets white offers) will not be won for white because black instantly captures a white piece (or King). This reduces the number of btm wins in the heavily won KQ.KR to just 46%. And that makes it difficult to see whether the end-game is a general or just a partial win from the btm stats. But there is also contamination in the other direction, which makes recognition of dead draws difficult: in the initial position black can be in check and forked or skewered, losing a piece, and thus the game. E.g. Chancellor vs Archbishop is a pretty bleak draw, but still 7.6% of the btm positions is a white win. Especially with very strong pieces initial tactics heavily contaminates the results for the end-game itself.

If the uncompensated loss of a piece for the stong side brings him in a lost end-game, the frequency of this can be obtained from the wins in the reverse end-game. E.g. as said only 46% of the btm positions in KQ.KR (i.e. with Rook to move) is won for the Queen, but in KR.KQ 50% of the wtm positions (also with Rook to move) is won for the Rook. From the DTC specification in KR.KQ we see that all Q losses are either immediate of after 1 move, i.e. all tactical. (And by generating a DTM EGT of KR.KQ we can see that 75% of the wins take more than 2 moves to mate, and must thus cannot have been instant mates, and must have gained the Queen instead.) This leaves only 4% for draws, already showing the large superiority of the Queen in cases where it is not lost before it can move. But it is still under-estimating it, because we don't know how many of these draws were caused by trading R for Q (so that they were not really Q vs R battles either).

This doesn't work if tactical loss of a white piece does not immediately lose the game, e.g. in KQ.KNN. The reverse end-game KNN.KQ then is also a dead draw. To solve that problem future versions of FairyGen will support an option -b, which makes it consider all positions where black has a bare King as a win for white. Then loss of the Queen in KNN.KQ, and even trading it in KR.KQ, would show up as a win when the Knights or Rook can force it. (This doesn't care about baring of the white King, so it cannot be used for Shatranj end-games!) Under these rules KR.KQ has 54% (wtm) wins, and they are all in 1 or 2 moves (i.e. tactical). So KQ.KR is either won for white with btm (46%), lost to white in 1 or 2 moves because black has tactics to gain or trade the Queen, and virtually no draws. For the white wins, it can still be useful to see how many moves they took to convert; FairyGen prints the sum of DTC=0, 1 or 2 frequencies, which can be used to see which fraction of the white wins is tactical, and how the fraction of remaining 'lengthy wins' compares to the number of non-converting ('fortress') draws. When super-pieces are involved, which can deliver a series of checks to get an aim on an isolated piece before gobbling it up, it would even be better to also correct the white wins for 'deep tactics' (e.g. DTC up to 5).

Options

FairyGen has a number of options to modify the rules under which the EGT is calculated. With option -0 (zero!) the defending side is allowed to play null moves (i.e. pass his turn) in positions where he would not be stalemated otherwise. This can be used to determine if zugzwang is essential for forcing the mate. E.g. KR.K ceases to be a win in this case. The option -s will cause stalemate to be considered a win. This option is useful even for end-games of chess variants that do not have this rule, to determine whether the strong side in principle has the power to force a King into a corner, even if for some tactical reason it cannot force checkmate there. (E.g. KNN.K becomes a general win with this option.)