Bitbase indexing and en passant

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Tord Romstad
Posts: 1808
Joined: Wed Mar 08, 2006 8:19 pm
Location: Oslo, Norway

Bitbase indexing and en passant

Post by Tord Romstad » Fri Aug 14, 2009 8:03 am

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
Posts: 1138
Joined: Sat Dec 13, 2008 6:00 pm
Contact:

Re: Bitbase indexing and en passant

Post by Gian-Carlo Pascutto » Fri Aug 14, 2009 10:04 am

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
Posts: 3819
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Bitbase indexing and en passant

Post by Sven » Fri Aug 14, 2009 1:44 pm

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.
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

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: Bitbase indexing and en passant

Post by sje » Fri Aug 14, 2009 2:57 pm

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.

User avatar
hgm
Posts: 23474
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Bitbase indexing and en passant

Post by hgm » Sun Aug 16, 2009 8:53 am

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
Posts: 1808
Joined: Wed Mar 08, 2006 8:19 pm
Location: Oslo, Norway

Re: Bitbase indexing and en passant

Post by Tord Romstad » Sun Aug 16, 2009 8:46 pm

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.

User avatar
michiguel
Posts: 6387
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: Bitbase indexing and en passant

Post by michiguel » Sun Aug 16, 2009 11:37 pm

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.
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
Posts: 1780
Joined: Thu Mar 09, 2006 10:54 pm
Location: The Netherlands
Contact:

Re: Bitbase indexing and en passant

Post by diep » Mon Aug 17, 2009 6:21 am

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.
You would find it acceptable if a footsoldier can promote unseen by the enemy?

wgarvin
Posts: 838
Joined: Thu Jul 05, 2007 3:03 pm
Location: British Columbia, Canada

Re: Bitbase indexing and en passant

Post by wgarvin » Tue Aug 18, 2009 11:48 pm

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.
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
Posts: 838
Joined: Thu Jul 05, 2007 3:03 pm
Location: British Columbia, Canada

Re: Bitbase indexing and en passant

Post by wgarvin » Wed Aug 19, 2009 12:03 am

michiguel wrote:
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.
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.]

Post Reply