Question about bitbases

[Thomas Gaksch]

Hi,
first of all i have to say that i have no idea how bitbases internally work. So sorry for my "silly" question.
I have noticed in engine games that the most valuable information you need from bitbases is the draw score. If an engine knows which positions are draws the engine is always/mostly able to win (if it is an winning position) or draw (if you only can draw). so i only would need the positions in the bitbases which are draws. all winning/loosing positions are worthless. if you only store draw positions in bitbases could it be that they are much less in size and that it would be faster to probe them?

Thomas

[Harald]

Hi,
first of all i have to say that i have no idea how bitbases internally work. So sorry for my "silly" question.
I have noticed in engine games that the most valuable information you need from bitbases is the draw score. If an engine knows which positions are draws the engine is always/mostly able to win (if it is an winning position) or draw (if you only can draw). so i only would need the positions in the bitbases which are draws. all winning/loosing positions are worthless. if you only store draw positions in bitbases could it be that they are much less in size and that it would be faster to probe them?

Thomas

As I understand it bitbases are derived from endgame tablebases. They
don't have the number of moves to something, but only the information
draw/not draw in 1 bit or win/draw/loss in 2 bits per position. You use
tablebases to build bitbases. The data is just a big array of these 1 or 2
bits. One byte of the array has 8 or 4 entries. The trick is to derive the
index from the position. Typically the board and side to move are
mirrored, flipped and rotated for a normalisation. Start with the remaining
pieces signature for different parts of your bitbase. Then there are at most
10 squares for the white king, many squares for the black king, and so on
for the other pieces. Multiply these numbers to get the index or shift and
or them. Google for
"Heinz: Knowledgeable encoding and querying of endgame databases".
There may even be other methods, too, but I don't know them.

In this approach you have all positions in the bitbase and 1 bit per
position to signal a draw. If you want to have draw positions in a bitbase
only, you have to reverse the idea. Do not store a draw-bit but find a way
to enumerate, store and find the draw positions in the database. I don't
know how to do this.

Harald

[Thomas Gaksch]

Hello Harald,
thanks a lot for your detailed answer. Do you know how much positions are draw in a 3-4-5 piece endgame.

Thomas

[Dirt]

Hello Harald,
thanks a lot for your detailed answer. Do you know how much positions are draw in a 3-4-5 piece endgame.

Thomas

The .tbs files that sometimes come with the tablebase files contain this information as text. For example, krrrk.tbs contains this:

Code: Select all

 
wtm: Mate in   5:           105
wtm: Mate in   4:        131128
wtm: Mate in   3:       1923698
wtm: Mate in   2:       4392844
wtm: Mate in   1:       1809313
wtm: Broken positions:  6387602
btm: Lost in   0:        625861
btm: Lost in   1:       2366951
btm: Lost in   2:       5979449
btm: Lost in   3:       6239768
btm: Lost in   4:       1344238
btm: Lost in   5:        533834
btm: Lost in   6:        211504
btm: Lost in   7:         11906
btm: Draws:              159329

[pedrox]

Hi Thomas,

I do not agree that those positions won / lost the bitbases are useless. I think that those positions help to enter to simplify the positions and go into winning positions and also the evaluation received helps advance the engine.

[Edmund]

... You use tablebases to build bitbases. ...

You don't necessarily need tablebases to build bitbases


I wrote a little Bitbase generator like this:

To generate a table, which marks all positions won for white:
1) Go through all possible positions for BTM
2) if Black can't make any move, that saves him (eg in check-mate, or possible moves are all marked won for white) then
3) mark all positions from where white can get to this as won for white
4) for all these positions check all positions, from where black can reach this positions
5) continue with 2)

It doesn't take the information of Mate in n to generate a tablebase


Secondly, if you know of a position if it is won or drawn/lost for either side, you can find out the actual state of the position.
It only takes a 1 ply search.
eg: If a position is drawn for WTM and BTM has no possible moves that would lead to a position won for Black, the position is drawn

[wgarvin]

... You use tablebases to build bitbases. ...

You don't necessarily need tablebases to build bitbases


I wrote a little Bitbase generator like this:

To generate a table, which marks all positions won for white:
1) Go through all possible positions for BTM
2) if Black can't make any move, that saves him (eg in check-mate, or possible moves are all marked won for white) then
3) mark all positions from where white can get to this as won for white
4) for all these positions check all positions, from where black can reach this positions
5) continue with 2)

It doesn't take the information of Mate in n to generate a tablebase


Secondly, if you know of a position if it is won or drawn/lost for either side, you can find out the actual state of the position.
It only takes a 1 ply search.
eg: If a position is drawn for WTM and BTM has no possible moves that would lead to a position won for Black, the position is drawn

One problem with that approach is that it doesn't know about the 50-move rule. So your bitbase might end up saying "strong side wins" when in fact it can't really win from that position because of the 50-move rule. This is probably only a problem for 6-piece bitbases (and maybe a handful of the 5-piece ones? I can't remember).

The best approach I know of, is to generate DTC50 databases and then convert those into W/L/D information for bitbases.

How to compress these bitbases efficiently is an open question too. Although some other people have tried it without success, I still believe that the best way to compress bitbases will turn out to be, using a combination of simple heuristics for each endgame to try and predict the results, and storing only the differences between the predicted bitbase and the real bitbase. I've been wanting to experiment with that for about 7 or 8 years now, but I'm too lazy to do all the necessary steps leading up to that (building DTC50 bitbases for all endings up to 5 pieces, etc).

[Dirt]

if you only store draw positions in bitbases could it be that they are much less in size and that it would be faster to probe them?

Thomas

Actually, I don't think they would be much smaller. Since most end games either contain very few won or very few lost positions (or both), I expect the compression algorithm squeezes most of that out anyway. Where it can't, you probably would find the information useful.

[Edmund]

... One problem with that approach is that it doesn't know about the 50-move rule. So your bitbase might end up saying "strong side wins" when in fact it can't really win from that position because of the 50-move rule. This is probably only a problem for 6-piece bitbases (and maybe a handful of the 5-piece ones? I can't remember).

The best approach I know of, is to generate DTC50 databases and then convert those into W/L/D information for bitbases.
...

Current Nalimov TBs do not consider this issue either. And in my opinion, this 50-move rule was only put into practice for human-human games, to avoid useless moving of pieces, just to prolong the game. It does not consider current developments in the computerchess field.

...
How to compress these bitbases efficiently is an open question too. Although some other people have tried it without success, I still believe that the best way to compress bitbases will turn out to be, using a combination of simple heuristics for each endgame to try and predict the results, and storing only the differences between the predicted bitbase and the real bitbase. I've been wanting to experiment with that for about 7 or 8 years now, but I'm too lazy to do all the necessary steps leading up to that (building DTC50 bitbases for all endings up to 5 pieces, etc). ...

Nice idea about the prediction and the storing of differences. I had this idea at one point as well. As an example .. in KQKR WTM it would be enough to say "if not White_king in check or White queen threatened White wins" only the remaining X_ray attacks etc would have to be considered ... splitting the total size by a factor 2 or so easily.