Bitbase indexing and en passant

[Tord Romstad]

I've started working towards adding bitbases to Stockfish. I'm not personally very interested in bitbases, but it is a popularly requested feature, and it's a good opportunity to learn about data compression.

Right now, I'm working on indexing. This seems very straightforward, with the exception of en passant captures. What's the usual way of handling these when indexing a position? Currently I do it by allowing 56 rather than only 48 values for the location of a pawn, where the 8 special values correspond to a pawn on a particular file which can be captured en passant. This works, but I hope it is possible to come up with something more compact without increasing the complexity too much.

[Gian-Carlo Pascutto]

There's a paper from Ernst Heinz about this, IIRC.

One trick is that ep is only possible with at least 2 pawns. So put them on the same squares.

[Sven]

I've started working towards adding bitbases to Stockfish. I'm not personally very interested in bitbases, but it is a popularly requested feature, and it's a good opportunity to learn about data compression.

Right now, I'm working on indexing. This seems very straightforward, with the exception of en passant captures. What's the usual way of handling these when indexing a position? Currently I do it by allowing 56 rather than only 48 values for the location of a pawn, where the 8 special values correspond to a pawn on a particular file which can be captured en passant. This works, but I hope it is possible to come up with something more compact without increasing the complexity too much.

Would it be acceptable to keep positions where e.p. is possible in a separate bitbase which is indexed differently? For indexing you could use the 14 possible combinations (per colour) of the affected two pawns as a base. Everything else could remain just the same. This could perhaps have the following advantages:

a) smaller size of bitbases, at least for the specialized e.p. bitbases;
b) simplified access to the standard, non-e.p. bitbases since no e.p. handling is necessary there;
c) clear separation of the most important standard case from the rare, very special e.p. case.

You would have to manage more bitbases in total, but I'm not even sure whether their total size would be bigger or smaller than with other approaches.

I must admit that I never tried this, which is simply due to the fact that I never even tried to investigate in implementing bitbases. But once I had already started to play with tablebases, and at that time I had this idea.

What do you think about it?

Sven

[sje]

This is essentially the same as my scheme for my version two tablebases where a pawn that has just had a double advance is indexed as if it were on its first rank.

A minor caution is needed as another man may be on the same first rank square and in this case the position should not necessarily be treated as being post-capture/illegal.

[hgm]

The best ay to index end-games with Paws is to divide them up in P-slices, (sub-sets of positons with Pawns in the same place), and make a small EGT for each P-slice. (Logically each P-slice is a different EGT, as they are connected by irreversible moves only.) To get the start address of P-slice a look-up (hash) table can be used. This makes it easier to fully exploit the exchange symmetry of the Pawns (wich can give you huge factprs if there are many Pawns). An additional advantage is that you don't have to bother with board symmetry within the -slice, as the presence of the Pawns fully breaks them.

In this scheme you would simply add an extra P-slice for positions with e.p. rights.

[Tord Romstad]

Thanks to all of you for your suggestions! Everything looks a bit ugly and awkward, but I suppose that's the nature of en passant captures. If we could travel back in time and persuade whomever invented the en passant rule to find some other hobby than chess, the world would be a better place -- at least for chess programmers.

[michiguel]

Thanks to all of you for your suggestions! Everything looks a bit ugly and awkward, but I suppose that's the nature of en passant captures. If we could travel back in time and persuade whomever invented the en passant rule to find some other hobby than chess, the world would be a better place -- at least for chess programmers.

En passant is not a problem. Advancing a pawn two squares was the origin of all problems when you think about it. Indirectly, it generated the problem of having en passant.

Anyway, in Gaviota tablebases, I do not store ep at all. When probing a position with ep, the score is determined by the fact that the side to move can chose between the score of the position without the ep, or the score of the position in which the ep is captured (negative score and corrected by a ply). The side to move chooses whatever is best between those two options. The whole thing is hidden in the probing function. This implies an extra probe (hidden) that happens very rarely. This probing function is the same for both the calculation of the tablebases and the probing performed by the engine during play.

I think this is the easiest way to deal with it. The ugliness is hidden in only one function. This design does not allow the ugliness to spread all over the place and I do not believe it causes problems with performance.

Miguel

[diep]

Thanks to all of you for your suggestions! Everything looks a bit ugly and awkward, but I suppose that's the nature of en passant captures. If we could travel back in time and persuade whomever invented the en passant rule to find some other hobby than chess, the world would be a better place -- at least for chess programmers.

You would find it acceptable if a footsoldier can promote unseen by the enemy?

[wgarvin]

The best ay to index end-games with Paws is to divide them up in P-slices, (sub-sets of positons with Pawns in the same place), and make a small EGT for each P-slice. (Logically each P-slice is a different EGT, as they are connected by irreversible moves only.) To get the start address of P-slice a look-up (hash) table can be used. This makes it easier to fully exploit the exchange symmetry of the Pawns (wich can give you huge factprs if there are many Pawns). An additional advantage is that you don't have to bother with board symmetry within the -slice, as the presence of the Pawns fully breaks them.

In this scheme you would simply add an extra P-slice for positions with e.p. rights.

Another advantage of this P-slicing is that you can generate a P-slice in its entirety using only a couple of "predecessor" P-slices. Because the pawn moves are irreversible, you don't have to do numerous passes over the entire endgame in order to resolve all of the positions. Instead you can resolve entire P-slices one at a time. With careful indexing of the pawns (read: careful numbering of the P-slices), you can probably do this without explicitly management of the dependencies between P-slices. And the indexing of the non-pawns within each P-slice can be the same for the whole ending, and you might be able to apply bulk counting or other tricks to that part.

[wgarvin]

Thanks to all of you for your suggestions! Everything looks a bit ugly and awkward, but I suppose that's the nature of en passant captures. If we could travel back in time and persuade whomever invented the en passant rule to find some other hobby than chess, the world would be a better place -- at least for chess programmers.

En passant is not a problem. Advancing a pawn two squares was the origin of all problems when you think about it. Indirectly, it generated the problem of having en passant.

Anyway, in Gaviota tablebases, I do not store ep at all. When probing a position with ep, the score is determined by the fact that the side to move can chose between the score of the position without the ep, or the score of the position in which the ep is captured (negative score and corrected by a ply). The side to move chooses whatever is best between those two options. The whole thing is hidden in the probing function. This implies an extra probe (hidden) that happens very rarely. This probing function is the same for both the calculation of the tablebases and the probing performed by the engine during play.

I think this is the easiest way to deal with it. The ugliness is hidden in only one function. This design does not allow the ugliness to spread all over the place and I do not believe it causes problems with performance.

Miguel

I'm still not sure if I believe that the way you describe will always work.

This came up before, and I haven't seen anyone explain why it would always work.
http://www.talkchess.com/forum/viewtopi ... ht=#266471

Yes, once you get into the situation with the EP capture possibility, a 1-ply search will resolve the correct value for that position. But what about the positions leading up to it? Imagine a situation where the positions leading up to the one with the EP square were considered won or lost, only because the tablebase generator didn't know about the EP capture possibility. e.g. where it believes that the player who double-pushes the pawn will force a win by that move (and would have eventually lost by making any other move). Except that, once he gets into that position, his opponent can make the EP capture and he can't actually win.

If there are any positions where this actually happens, it would result in the engine believing it could win until it sees the position with the EP square and then going... "oops"!

So I question whether you can truly know that your bitbase or tablebase is 100% correct, if you don't build the knowledge of en-passant into the tablebase generator. Even if there are no "problem" positions of this sort in the actual endgames, it might be nice to have a generator which could prove that, rather than just crossing our fingers and hoping for the best. I guess Nalimov's tablebases include enpassant, so maybe this question could be answered by scanning the data in them.

[Edit: Oh wait... I missed the part where you said that you do the same probe when generating the tablebases. That sounds like it should work properly. My gripe is with the idea that ignoring ep during generation, could be patched up using that 1-ply search in the engine.]