EGTB question

[Stef Luijten]

Can someone explain to me why the NALIMOV EGTB's have separate files for white to move and black to move? I always assumed that chess has perfect 'color symmetry', that is: you can change the colors of all pieces of any position (white becomes black, black becomes white) and swap the side to move, and you will end up with a perfectly equivalent position (of course if there are pawns on the board you will also need to flip the board...). Am I missing something here?

[Dann Corbit]

It's really 'dominant side to move' or something like that. The names are a little funny.

If the tablebase file is symmetrical, e.g. KQkq, then only one tablebase file is needed. But if it is KQkr then reversing the colors won't help.

[Sven Schüle]

Hi Stef,

e.g. a KQkr position with white to move may be completely different from the same position but black to move.

For positions without pawns, swapping piece colors and swapping side to move allow four different positions when given a fixed set of piece locations:
a. original
b. only piece colors swapped
c. only side to move swapped
d. both
"Color symmetry" means a==d and b==c (in terms of symmetry), so there are two really different positions left.

With pawns on board, there are similar facts but a bit more complex. Only one example here: KPkp, there is no way to make these two positions "identical" in terms of symmetry:

[diag]2k5/P7/2K5/8/8/8/7p/8 w - - 0 1[/diag]
2k5/P7/2K5/8/8/8/7p/8 w - - 0 1

[diag]2k5/P7/2K5/8/8/8/7p/8 b - - 0 1[/diag]
2k5/P7/2K5/8/8/8/7p/8 b - - 0 1

Sven

[Reinhard Scharnagl]

Indeed those positions could be represented by two with always only white at move:

[diag]2k5/P7/2K5/8/8/8/7p/8 w - - 0 1[/diag]
2k5/P7/2K5/8/8/8/7p/8 w - - 0 1

[diag]8/7P/8/8/8/2k5/p7/2K5 w - - 0 1[/diag]
8/7P/8/8/8/2k5/p7/2K5 w - - 0 1

(switching pieces' colors and mirroring up to down)

Reinhard.

P.S.: positions having pawns could be normalized by mirroring left to right, to place the white king on files form a to d only. Above color transformation would keep that alignment and thus not increase the number of necessary positions.

[Stef Luijten]

But a KQkr position with white to move can be made completely equivalent to a KRkq position with black to move. I think there is a color symmetry in this case, so why do we need two separate EGTB files? Isn't one KQKR-file enough, dealing with all cases?

[Reinhard Scharnagl]

Suppose to have a given position without pawns in it. Then you would be able to do following:

a) mirror up/down and switch colors, if Black is to move
b) rotate the board until w-King is from a-d and 1-4
c) mirror position along diagonal a1-h8 until w-King is with the bottom side
d) mirror along diagonal a1-h8 if w-King is upon that diagonal until b-King is with the bottom side

If now additional pieces will be added to such a normalized position, their coordinates are absolute, because no further transformation could be done without (possibly) destroying the normalization of both Kings. Thus added Qr positions are separated from qR positions. Nevertheless only positions with White to move have to be encoded.

Reinhard.

P.S.: there might be an exception for positions, where all additional pieces are placed upon the a1-h8 diagonal, or switching colors would keep the normalisation.

P.P.S.: It seems, that only positions having normalized both Kings within the triangle a1-d1-d4 could share positions with changed colors then. Implementing that could lead to a saving of about 10.25%, but I am not sure about that.

[Sven Schüle]

But a KQkr position with white to move can be made completely equivalent to a KRkq position with black to move. I think there is a color symmetry in this case, so why do we need two separate EGTB files? Isn't one KQKR-file enough, dealing with all cases?

Hi Stef,
a KQkr file contains positions with a white queen and a black rook. A KRkq file would contain positions with a white rook and a black queen. You have two choices, either have these two files with always white to move, or only have KQkr but with entries for white and for black to move. Usually the second form is preferred, but I think both are semantically equivalent.

Sven

[H.G.Muller]

But a KQkr position with white to move can be made completely equivalent to a KRkq position with black to move. I think there is a color symmetry in this case, so why do we need two separate EGTB files? Isn't one KQKR-file enough, dealing with all cases?

That is the crux: The KQkr EGTB does not contain any positions with KRkq. To make use of the symmetry you point out, you would first have to include all the KRkq positions, which completely defeats the purpose (which is to reduce the size of the TB).
In fact the use of symmetry in the presence of pawns is of the same questionable value, and more often than not self-defeating: To make use of the left-right mirror symmetry in (say) the KPk end-game with the P in the b file, you would first have to add all positions with pawns in the g file. Thus in the end this saves nothing, it merely adds a needless complication to your EGTB generator, which now has to check all the time if the white King crosses the median.

The key to doing big TBs (like 7 or 8 men) is to decompose them into fragments that are as independent as possible, so that you can completely work them out independently, without taxing your cache or RAM resources too much and without having to refer (often) to other fragments that are in the mean time stored on a much slower device. Pawns are ideally suited for that: as long as you work on a KPPkpp end-game with c,d vs d,e pawns, for instance, you will never have to consult the 6-men TB fragments with pawns in other files. Just very small subsets of the 5-men TB's (those with 3 pawns in a limited number of combinations in the c,d and e files), which can be easily cached in memory, while the TB fragment itself contains less than 64x64x6x6x6x6/4 = 1,32M (the division by 4 coming from permuting pawns). And of course to the various 6-men TBs with Queens, which is much more of a problem.

In fact you can make use of the forward nature of the pawns to define even smaller sub-fragments, that do not only confine the pawns to a file, but to a specific square. When you are working on the sub-fragment with pawns on (say) c4,d3-d7,e4 (a sub-fragment containing less than 4096 positions in the KPPkpp end-game!), you only have to refer to 4 other sub-fragments from this 6-men TB, whith each of the pawns advanced by one square. A Commodore 64-could do it! For today's computers it only becomes a (modest) challenge if there are two more pieces on the board, say KRPPkrpp. Then the sub-fragments still only measure 16MB, so that many of them can be cached in DRAM, and you can work your way backwards through the TB at RAM-speed, rater than disk-speed. Of course there will be very many sub-fragments, so it still takes a long time.

The major problem is again conversion to end-games with promoted pawns. KQQRkqqr is quite hope-less. From KRPPkrpp you can directly convert only to KQRPkrpp and KRPPkqrp, though. So the key is to do these extremely skewed TBs. If you are making TBs for DTC rather than DTM you can apply tricks, since for the KRPPkrpp TB you then only have to know if a position you can convert to in KQRPkrpp is won, and not in how many moves. Presumably you can then solve this latter end-game giving the strong side a handicap aimed at reducing the number of positions or the fragment size. In particular, you could forbid the strong side to have more than one Queen, or forbid him to move his pawns altogheter. I expect the end-game to remain fully won despite such restriction, due to the overwhelming power of the extra Queen.

[Daniel Shawul]

Nalimov has kQkr.wtm and KQkr.btm but no kRkq!!
Alternatively you could have KQKr.wtm and KRkq.wtm which i think
chessmaster tbs are. As far as i know, they have the same advantage. Mine is like Nalimov's.
daniel

[H.G.Muller]

The difference is that Nalimov's TBs also include (and give DTM) for lost positions. So a Nalimov KQkr TB is really a combination of a Chessmaster KQkr and KRkq TB. In that case it is true that the .wtm positions in one are the exact counterparts of the .btm positions in the other.

[Stef Luijten]

But a KQkr position with white to move can be made completely equivalent to a KRkq position with black to move. I think there is a color symmetry in this case, so why do we need two separate EGTB files? Isn't one KQKR-file enough, dealing with all cases?

Hi Stef,
a KQkr file contains positions with a white queen and a black rook. A KRkq file would contain positions with a white rook and a black queen. You have two choices, either have these two files with always white to move, or only have KQkr but with entries for white and for black to move. Usually the second form is preferred, but I think both are semantically equivalent.

Sven

Sven, thanks! this is what I thought but wasn't completely sure about!
My question was indeed not related to disk space, but merely about the organization of EGTB's, which is (as you mention) a design choice.
Stef