Open Source bitbase program

[Daniel Mehrmann]

You don't need to publish the EGTB code, all you need to do for each bitbase is:
- loop over all possible positions
- probe EGTB to see if the position is win, draw or loss
- update the bitbase accordingly.

Well, that's a nice idea. I like your lazy side.

Best,
Daniel

[Peter Fendrich]

The generation itself is a minor issue but how to compress them intelligently is the challenge. The Nalimov EGTB can be used only to a certain depth in order to not kill the performance of the program. With bitbases held in RAM the engine can go deeper and detect the win/draw earlier. The cost is of cource lack of information about the shortest line and therefore risking to miss how to avoid or utlilise the 50-move rule.

Compression and fast access is the main questions for bitbases IMHO.

/Peter

[hgm]

One should distinguish the matter of probing EGTs during search, or actually playing an end-game for which a TB exists.

In the former case it is hardly interesting to know how long a win is. The important thing is that you can get there. Once you have accomplished that feat, it is early enough to start to worry about the 'how?'. For a loss pretty much the same holds: either your opponent also has the TB, and then it doesn't matter because you will certainly lose no matter what. Or he hasn't, and then you would like to pull a swindle and hope he can't find it. But the longest wins are not necessarily the most difficult to find. Your own evaluation would probably give a better indication of how difficult it will be for your opponent to find the win than the DTM.

In drawn positions this is even more important, as even a Nalimov TB would not give you any information except that it is a draw. And as far as swindle prospects are concerned, you probably would like to play a drawn position from KBPPKB (with unlike B) than one from KKB. Yet according to the TBs they are equally drawn.

It might be important how you treat positions that are drawn, but winnable if not for the 50-move rule. If you are on the losing side, you would of course want to consider such positions a draw, as you apparently have the TB. On the winning side you might prefer to avoid this positions as long as there is no need to simplify, as you will risk a certain draw if he has the TB. Only if your normal search also runs into a certain draw (e.g. 50-move rule), you would prefer such drawn positions over dead draws.

So for probing during search, bitbases can really give you al the information you need. If you are actually in an EGTB ending, you can easily afford to probe the Nalimov, no matter how expensive it is, as you only need to do a 1-ply search then. Which is just as well, as there are some difficult-to-win end-games for which a bit-base gives you zero information. (e.g. KQKR might be problematic to win through your normal search at short time control, bit the bitbase will only tell you that it is always won if you don't give up your Queen.)

[Alessandro Scotti]

In Kiwi I tried an "intelligent" approach. Every bitbase has a "predictor" function that independently tries to decide whether a position is win/draw/loss. The bitbase itself does not encode "absolute" WDL scores, but rather the "delta" from the predicted value. The idea is that with a good predictor most entries in the bitbase become zero, and long sequences of zeroes compress very well. I did several mistakes in my implementation but anyway I think the idea is interesting.
Another very viable approach is to just take and zip everything... that's what Delfi does and IIRC it gets 3 & 4 men BB in about 1 MB.

[Allard Siemelink]

The generation itself is a minor issue but how to compress them intelligently is the challenge. The Nalimov EGTB can be used only to a certain depth in order to not kill the performance of the program. With bitbases held in RAM the engine can go deeper and detect the win/draw earlier. The cost is of cource lack of information about the shortest line and therefore risking to miss how to avoid or utlilise the 50-move rule.

Compression and fast access is the main questions for bitbases IMHO.

/Peter

A nice approach, that I think is used by KnightDreamer, would be to use an (ID-3 generated) binary decision tree . This decision tree would be built of boolean expressions such as "king is check", "king in pawn sq" etc.
Simple bitbases would compress to a few bytes. For example, KQK would only need the ID3 tree with a few nodes to answer, e.g.

Code: Select all

"white to move?" 
true : WIN
false: "black k attacks Q?" 
        true :"white K defends Q?" 
                true : WIN 
                false: DRAW
        false: WIN

The good thing is that you would not have to worry about how to combine the boolean expressions with if/and/or, the id3 algorithm takes care of that.

Once the binary decision tree gets too large/deep, you could compress the remaining subtree with zlib/7zip or perhaps you could use OBDD's.
You may want to take a look at this link: http://www.daimi.au.dk/~doktoren/master_thesis
It explains how to compress endgame databases using binary decision diagrams. The advantage is that de obdd's can be probed without decompressing them first.

I am not sure how well this compression would work for 5 or or more men endgame bitbases though.

[Daniel Shawul]

The bitbase generating code as well as the compression code is open source. It used to be on Dann's ftp but i don't know if it is still there after Dann's harddisk crashed. The generator is very slow and didn't want to improve it. because of this it took me 3/4months to generate all bitbases.
I am sure it might have been better to invest a little bit on improving speed of generation but i was too lazy to even try it.

[Daniel Shawul]

Hi alessandro
In my experiecnce predition really is disappointing when it comes to 5 men bitbases.
I wrote predictors for each group separately
predictor3piece
predictor4piece
predictor5piece
You can use the actualy bitbase score for 3/4pieces assuming they are in RAM, but that
didnt bring much. Now when a 5 men bitbases are probed, first the static exchange evaluator
is called , which makes capture moves and call the predictors recursively. Mine was a quiescene search.
It is easy to write an accurate SEE since we have only 5 pieces.
The problem is you can't really do good prediction for bitbases which add significantly to the total size.
Those you can are usually compressed well if you have a decent compression algorithm.
I got a 10% improvement from prediction of 5 men which is disapponting compared to the effort i've put.
Then when only one side to move bitbases are used,ie by removing the larger of the two, it turns
out the improvement went down to 1 or 2%, which is when i understood i have been wasting my time
with prediction.
IMO-YMMV

[Allard Siemelink]

The bitbase generating code as well as the compression code is open source. It used to be on Dann's ftp but i don't know if it is still there after Dann's harddisk crashed. The generator is very slow and didn't want to improve it. because of this it took me 3/4months to generate all bitbases.
I am sure it might have been better to invest a little bit on improving speed of generation but i was too lazy to even try it.

Wow, it really took that long to generate all bitbases?

Too bad that I have seemed to encounter an EP bug in at least one of them.
Happened the other day while running the MES endgame test #32: suddenly a winning egbb score dropped to a draw when searching deeper.
Turns out that according to the egbb this position is a draw:

[D]8/5p2/8/6Pk/5K2/6P1/8/8 b - - 0 13

but is is really won for white: f5 will not draw due to gxf6 (en passant)
(See also http://www.lokasoft.nl/uk/tbweb.htm)

Come to think of it, perhaps you never claimed to support en passant captures? Since if you did, there surely would have been an ep-parameter to probe the egbb...
Of course, even without EP I am very happy that bright can use your bitbases.

[Alessandro Scotti]

Hi alessandro
In my experiecnce predition really is disappointing when it comes to 5 men bitbases.

Hi Daniel,
yes it's disappointing but somewhat expected, I think one can start to see the symptoms also in some 4 men bitbases. Anyway many 5 men positions are very difficult to predict and I think your 10% improvement is a very good result. Of course with current hardware 10% is not so significant but then again how would we know if you hadn't tried?
Actually I developed Kiwi on a 700 MHz Athlon with 256 MB of RAM and not much more of free HD space, so 5 men were a dream for me and I liked the idea of bundling all 3 and 4 men bitbases with the engine with as little overhead as possible (a la Delfi). I still like the idea but today I have a much better PC and a lot of testers have monster hardware, so spending a few hundreds MB for bitbases is quite less frightening!

[Daniel Shawul]

It took very long due to slow algorithm and slow machine (256mb ram). 512mb is the miniumum i think.

Yes enpassant captures are not included. I should have added a note to the readme. Well i never saw it happen on the board. It should be easy to add enpassant and distribute new kkppx bitbases.