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.
Bitbase indexing and en passant
Moderators: hgm, Rebel, chrisw
-
- Posts: 1808
- Joined: Wed Mar 08, 2006 9:19 pm
- Location: Oslo, Norway
-
- Posts: 1243
- Joined: Sat Dec 13, 2008 7:00 pm
Re: Bitbase indexing and en passant
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.
One trick is that ep is only possible with at least 2 pawns. So put them on the same squares.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Bitbase indexing and en passant
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:Tord Romstad wrote: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.
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
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: Bitbase indexing and en passant
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.
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.
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Bitbase indexing and en passant
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.
In this scheme you would simply add an extra P-slice for positions with e.p. rights.
-
- Posts: 1808
- Joined: Wed Mar 08, 2006 9:19 pm
- Location: Oslo, Norway
Re: Bitbase indexing and en passant
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.
-
- Posts: 6401
- Joined: Thu Mar 09, 2006 8:30 pm
- Location: Chicago, Illinois, USA
Re: Bitbase indexing and en passant
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.Tord Romstad wrote: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.
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
-
- Posts: 1822
- Joined: Thu Mar 09, 2006 11:54 pm
- Location: The Netherlands
Re: Bitbase indexing and en passant
You would find it acceptable if a footsoldier can promote unseen by the enemy?Tord Romstad wrote: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.
-
- Posts: 838
- Joined: Thu Jul 05, 2007 5:03 pm
- Location: British Columbia, Canada
Re: Bitbase indexing and en passant
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.hgm wrote: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.
-
- Posts: 838
- Joined: Thu Jul 05, 2007 5:03 pm
- Location: British Columbia, Canada
Re: Bitbase indexing and en passant
I'm still not sure if I believe that the way you describe will always work.michiguel wrote: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.Tord Romstad wrote: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.
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
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.]