bitbase sharing

[Daniel Shawul]

Hi Vincent
my Generator is very slow. i didnt even care to implement
the forward retrograde generator, because my intention was to
generate only 5 pieces. KBBKN took me 3 days using 256M ram!
with more ram this might reduce to within hours though.
I am okay with this but others are definetly not going to like this.
If anyone is interested i can send it to them, but for a release it needs
a lot of impovement.
i have to implement a faster generator and buy some more ram before
i think of 6 men. Also compression is another issue that i have 0 knwoledge. A rough implementation i did using Huffman + Rle
is two times inferior compared to Kadatch's both in compression ratio, and decompression speed.

How many days does a typical single 7 men (like KRPPKRP) take.
I guess that generation is also disk based, so it might take way too
much time.
Good luck with your new year plan.
daniel

[diepeveen]

Hi All
I have written a dll to access scorpio bitbases. Anyone can
use 4 piece bitbases by just adding a few lines of code to load the
dll, and access it with an exported function. I chose the dll solution because
1) this doesn't add to the size of execuatble
2) no need to recompile engine code when updates are made like for
example new bitbases are added.
One (serious?) disadvantage is that this doesn't work on linux and mac OS.
I don't know what to do about this. Any suggestions are welcome.
The source code is ugly, so anything other than adding it to engine's code
is preferable.
I have modified TSCP to access the bitbases. So if any one wants to use it,
just drop me an email.
daniel

Hello Daniel,

You are ignoring the question whether you want to release it under GPL.

Vincent

[Daniel Shawul]

Yes . To be more exact i will use BSD style, since this
is what my engine use,and the move generator is taken from it.
Do you have intention to release yours? I would like to see it.
Daniel

[Pedro Castro]

[diag]4N3/5R2/8/8/P2K2k1/8/8/2r5 b - - 0 60[/diag]

FEN: 4N3/5R2/8/8/P2K2k1/8/8/2r5 b - - 0 60

Problem with bitbases?

In this position, when having activated the bitbases, the evaluation of the engine is:

DanaSah v1.8.2:
1 00:00 3 3 -4,75 Rh4
1 00:00 7 7 -4,70 Rg5
1 00:00 45 45 -4,68 Td1+ Re4
1 00:00 57 57 -4,46 Tc2
2 00:00 453 453 -4,67 Tc2 a5
2 00:00 543 543 -4,63 Td1+ Rc3 Te1
3 00:00 1.010 1.010 -4,63 Td1+ Rc3 Tc1+ Rd3 Te1
4 00:00 4.232 70.533 -4,70 Tc2 Cf6+ Rf5 a5 Td2+ Rc3
5 00:00 9.868 164.466 -4,81 Tc2 a5 Td2+ Re3 Ta2 Cf6+ Rf5
5 00:00 18.618 232.725 -4,75 Td1+ Rc3 Te1 Cf6+ Rg5 a5 Te2
5 00:00 23.511 261.233 -4,71 Ta1 Cf6+ Rg5 Ce4+ Rg6 Tf6+ Rg7
6 00:00 54.025 415.576 0,00 Ta1 Cf6+ Rg5 Ce4+ Rg6 Tf6+ Rg7 a5 Txa5
7 00:00 87.355 545.968 0,00 Ta1 Cf6+ Rg5 Ce4+ Rg6 Tf6+ Rg7 a5 Txa5 Rc4
8 00:00 173.630 723.458 0,00 Ta1 Cf6+ Rg5 Ce4+ Rg6 Tf6+ Rg7 a5 Txa5 Rc4 Rh7
9 00:00 527.961 879.935 0,00 Rg5 a5 Td1+ Rc3 Ta1 Tg7+ Rh5 Rd3 Txa5 Th7+ Rg4
10 00:00 893.494 940.520 0,00 Rg5 a5 Td1+ Rc3 Ta1 Tg7+ Rh5 Rd3 Txa5 Th7+ Rg4 Rc2 Tb5
11 00:10 9.374.041 926.288 -4,26 Rg5 Cd6 Ta1 Ce4+ Rg6 Ta7 Txa4+ Txa4 Rf5 Ta5+ Re6 Tb5 Re7
11 00:20 19.201.773 953.888 -3,86 Td1+ Rc4 Tc1+ Rb4 Tb1+ Ra5 Rg5 Tc7 Ta1 Tc5+ Rf4 Cc7 Txa4+ Rxa4 Re4 Tc4+ Re5
12 00:31 29.813.544 961.727 -4,08 Td1+ Rc4 Tc1+ Rb3 Ta1 Tf2 Txa4 Rxa4 Rh5 Ra5 Rh6 Te2 Rg6

ply 6,7,8,9 eval = 0

Without bitbases

DanaSah v1.8.2:
1 00:00 3 3 -4,75 Rh4
1 00:00 7 7 -4,70 Rg5
1 00:00 45 45 -4,68 Td1+ Re4
1 00:00 57 57 -4,46 Tc2
2 00:00 453 453 -4,67 Tc2 a5
2 00:00 543 543 -4,63 Td1+ Rc3 Te1
3 00:00 1.012 25.300 -4,63 Td1+ Rc3 Tc1+ Rd3 Te1
4 00:00 4.244 84.880 -4,70 Tc2 Cf6+ Rf5 a5 Td2+ Rc3
5 00:00 10.449 174.150 -4,81 Tc2 a5 Td2+ Re3 Ta2 Cf6+ Rf5
5 00:00 19.904 284.342 -4,75 Td1+ Rc3 Te1 Cf6+ Rg5 a5 Te2
6 00:00 62.708 482.369 -4,70 Td1+ Rc4 Td2 Cf6+ Rf5 a5 Re6 Ce4 Rxf7 Cxd2
6 00:00 97.852 575.600 -4,59 Ta1 Cf6+ Rh4 Ta7 Td1+ Rc3 Rg5
7 00:00 181.222 697.007 -4,59 Ta1 Cf6+ Rf5 Cd5+ Rg6 Ta7 Td1+ Rc4 Td2 a5
7 00:00 328.693 782.602 -4,56 Td1+ Rc4 Ta1 Rb3 Rg5 Tg7+ Rh6 Ta7
8 00:00 533.864 821.329 -4,60 Td1+ Rc4 Rg5 a5 Ta1 Rb5 Ta2 Ra6
9 00:01 1.196.869 861.056 -4,60 Td1+ Rc4 Tc1+ Rd3 Rg5 a5 Td1+ Rc4 Ta1 Rb5 Ta2 Ra6
10 00:03 3.447.913 904.964 -4,65 Td1+ Rc5 Ta1 Rb5 Tb1+ Ra6 Td1 a5 Td2 Cf6+ Rf5 Rb5
11 00:11 10.330.194 929.810 -4,65 Td1+ Rc4 Ta1 Rb5 Tb1+ Ra6 Tb2 a5 Te2 Cd6 Td2 Ce4 Te2

[Pedro Castro]

It should be a problem with my engine

FEN: 4N3/5R2/8/8/P2K2k1/8/8/2r5 b - - 0 1

Tscpegbb:
1 00:00 20 20 -4,52 Tc2
2 00:00 194 194 -4,62 Td1+ Re3 Rg5
3 00:00 1.240 1.240 -4,62 Td1+ Rc4 Tc1+ Rd3 Rg5
4 00:00 7.018 233.933 -4,67 Td1+ Rc3 Tc1+ Rd2 Tc5 Cd6
5 00:00 40.056 445.066 -3,60 Ta1 Cf6+ Rg5 Ce4+ Rg6 Td7 Txa4+
6 00:00 155.774 519.246 -3,50 Td1+ Rc5 Ta1 Cf6+ Rg5 Ce4+ Rg6 Td7 Txa4
7 00:03 1.936.177 537.826 -4,04 Ta1 Cf6+ Rf5 Ce4+ Re6 Tf6+ Re7 Ta6 Txa4+ Txa4 Re6
8 00:19 10.944.599 562.704 -4,08 Td1+ Rc4 Rg5 Tg7+ Rf5 Te7 Ta1 Rb4 Txa4+ Rxa4 Rg6

[Stef Luijten]

Just a wild idea: 'we' can of course start a joint EGTB software development project under the GPL, to really make it open and freely available for everybody.

This would need a document/protocol first, to clearly define the following:
* what to store (DTM? DTC? etc)
* how to store it
* what type of compression algorithm (this needs to be under the GPL as well)
* specification of the interface (C/C++): headers and functions for engines to access the databases
* routines for generation of the tablebases (should be an integral part of the library, I think).
* etc.

I am a novice to EGTB's, but willing to learn & contribute.

Stef

[Daniel Shawul]

Hi Stef
Something like this has been discussed in this forum some time ago.
But AFAIK no joint effort is made. I think everybody tries on his own.
I started my own some time ago to make a free tablebase generator and probing code.

-> generates DTM / WDL up to 5 pieces
-> own compression/decompression using huffman . very poor overall, so
i might switch to the free Zip.
-> uses a dll for probing bitbases . A similar approach is intended for linux users

If any body is interested to participate in the project,i am willing to combine effort.
daniel

[H.G.Muller]

My generator does the KbbKn in 285 sec now. (Not making use of exchange symmetry for the bishops, i.e. treating them as different pieces and calculating the - rather uninteresting - TB for bishops on equal color as a subset). At first I thought it should be possible to do this much faster, but it seems the number of moves for the losing side it has to consider on average before it finds one to a position that is not lost is simply larger than I expected. Rewriting the move generator in assempbler would probably speed it up a lot: I looked at the compiler output (gcc under cygwin) and the code is really stupid, even with -O2 compilation. It uses branches in stead of conditional-move instructions!

I don't know where this puts my code on the scale of things; if it is considered of value I am willing to contribute the ideas behind the code to a joint project.

As for something befitting this season: I also produced some of the less common TBs, and did you know that three kings beat K+R almost every time (i.e. if none of the kings is trivially captured in the initial position)?

[diag]8/8/7K/3K4/8/8/3k4/K4r2[/diag]
FEN: 8/8/7K/3K4/8/8/3k4/K4r2 w - -

White to move forces a winning conversion in 85 moves

(The white king on d5 is the royal one, the other two are just commoners, i.e. they can be exposed to capture.)

[Daniel Shawul]

Is your generator is a forward retrograde analyzer?
with this it is possible to generate it within 5 minutes,
since lots of those positions are draws and they dont have to revisted everytime. Plus i am generating them on virtual memory (256mb) which can multiply the generation time by a huge factor.

[H.G.Muller]

Is your generator is a forward retrograde analyzer?

To be honest, I don't really know what that means.

I devised the algorithm myself. To work its way from DTM (or DTC) = n to DTM = n+1 it first marks all parents of the DTM=n positions as won (in a single bit flag) and labels all grandparents as potential DTM = n+1. (Is this the retrograde thing?) In a second pass it then eliminates all (n+1) labels on positions that can reach at least one not-yet-lost positions in a normal move.

I don't think the important timesaving comes from that most positions are draws (although that would help): In KbbKn virtually every position that does not have a hanging bishop is won (not counting bishops on the same color, of course). With other algorithms you could also immediately label those as certain draws, and not waste anymore time on them in later passes.

As for the virtual memory, I think in principle any operating system nowadays uses virtual memory, but if the amount of memory you use fits well within the physical memory, there is no penalty on that. A 5-men TB needs 160MB, and my laptop has 512MB, so there is no problem. I do notice, however, that the first big program I run under cygwin takes a minute or so extra time to start up, with a lot of disk I/O. Probably the OS creates a swap file in that time (which it subsequently never uses).

[Daniel Shawul]

I think it is similar.
I only read about it in this paper.
http://www.daimi.au.dk/~doktoren/master_thesis/handin/
it has lot of stuff on tablebases in general.

[Daniel Shawul]

I think it is similar.
I only read about it in this paper.
http://www.daimi.au.dk/~doktoren/master_thesis/handin/
it has lot of stuff on tablebase generation, compression using
binary trees ..

[H.G.Muller]

Hmm, the description of the algorithms in this paper is not very clear. I have the impression, though, that both 'forward' and 'backward' algorithms that are described there are different from the one I use: they seem to work ply by ply, while I go in steps of a full move. The reported performane is not very impressive: even with the more efficient 'backward' algorithm KbbKn seems to take 20 min on a 3GHz Pentium 4 with 1GB RAM, where it takes me < 5 min on a 1.3 GHz Celeron with 512 MB.

The published algorithms have the advantage that they also determine the won positions for the other side. (Not very interesting for KbbKn, though...). My algorithm does not distinguish drawn and lost for the side it is calculating for, and only identifies wins.

From reading the paper I did get some ideas how to speed it up still further, though, inspired by the 'forward' algorithm. In my way of doing things, the first step (identifying the checkmates) takes much (a factor 10-100) longer than subsequent steps: starting from the systematically generated black-king-less positions it marks the parents (reached by retrograde moves forced to be king 'uncaptures') as black-in-check (= lost with white to move, due to an apparently illegal move of black) and the grandparents as potential checkmates (positions from which black could wander into check). In the second pass it screens all those potential checkmates, by ordinary forward move generation, to see if black can 'escape' to a non-black-in-check position.

The number of positions from which black could wander into check is extremely large, though, usually more than half of all positions. (With a single queen, even if she is in a corner, there are only 12 squares on the board from where the enemy king could not step in check!) So labeling the states takes very long, and in the end achieves hardly anything. So it actually saves 25 sec to not identify the potential checkmates, but in the first pass simply consider all postions as potential checkmates, and screen them for moves that evade the check. Especially since for the few that were not potential checkmates, the very first forward move that is tried of course reveals it is 'not guilty'.

In later iterations this does not work (and certainly not in KbbKn), because only a very small fraction of the states gets labeled as 'potential mate in n+1', and it really saves a lot of time only to screen those. But even though we restrict ourselves to screening positions for which at least one of the escape routes was plugged on the previous iteration, they still have to be screened several (~5) times, because initially there are many escapes and it takes many iterations before all evasive pathways are finally cut off. Especially the later screenings are expensive, because many forward moves have to be tried before one of the remaining few escapes is found. This is exactly the problem from which the forward algorithm suffers as well.

A lot could be gained from keeping track of wich move was the escape from a certain position on the last screening attempt. On re-screening we could resume the effort at that move. All preceeding moves were to quicker defeat, and will stay like that. As long as the DTM is not determined, we could for instance store the move number in the DTM field of the TB, reserving the highest DTM codes for this purpose. (With K+N there are only 16 moves, so if we have 7 bits available for DTM we could reserve 1-110 for true DTM, 111 for stalemate, and 112-127 for the saving move.) I could imagine that even the 'forward' algorithm becomes very competative: checking if the indicated escape move still leads to an 'undecided' position might take hardly more work than checking if the position itself was labeled as a 'potential mate in ...' Especially if there is a quick way to calculate the location in the tablebase from the move number (e.g. a small table that translates move numbers to an offset that we have to add to the index of the current position to get the index of the target position).

I tried this, but in my case it did not work very well, because my table-bases includes all smaller ones with subsets of the pieces, so forward moves can be captures, making it hard to figure out the index of the target state: the move vector is not enough, one also has to know if anything was captured, what it was, and where. I don't know how to get all that without move generation. But if one does the subset TBs first (as is usually done), escapes due to conversion to a non-lost position of smaller end-game of course are permanent escapes, and states from which such an escape is possible can immediately and permanently be marked as drawn-or-lost (e.g. by assigning them the stalemate code for DTM) and never have to be re-checked again. (In much the same way as I now treat positions in which black 'escapes' by capturing the white king: such positions can never become lost for black, because white-king-less positions can never turn into 'lost-for-black', and are in fact not even in the TB).

[Alex Morozov]

I wrote my own egtb generator for my engine "booot" one year ago. Now i am writing egtb generatoe for russian draughts program. I have some experience in speed improvement. Email me booot@rambler.ru.

[H.G.Muller]

I tried yet another trick, which I believe is a bit like the retrograde algorithm of the thesis:

Rather than screening potential wins on every iteration, and aborting the forward move generation as soon as the first escape to a non-win is found, I pre-emptively screen every position on the first iteration (just after marking all the states with black in check). When doing this I don't stop at the first escape found, but I count the total number of escapes, and store it in the DTM field (coded as DTM = 100-128).

After that I never have to label or screen a position as a potential mate: if it is the parent of a state just declared a win for white with white to move, I simply decrease the count. Since this gives me the number of remaining escapes, I know immediately if the state now can be declared a 'win in ...' (namely if the count hits zero, meaning that no escapes are left) or not. So after that first iteration, the algorithm requires only one pass through the TB to advance one full move.

Strangely enough, the speedup is not what I would expect. The time spend on the second pass drops from 123 sec to 61 sec. But the time needed for identifying grandparents and decreasing their count (and occasionally labeling them as won in n+1) goes up from 137 sec to 180 sec. This is very mysterious, I would have thought that determining if the DTM field contains a count (DTM>100) and then decreasing the count takes equal time as determining if the field did not already contain a (quicker) DTM (DTM == 0), and then setting it to n+1 to label it as a 'potential'. Both require a test with equal probability of succes (all fields that were 0 in the old algorithm now contain counts), and both make the field dirty by writing it.

Nevertheless, overall time dropped from 290 sec to 248 sec. This despite the fact that in the new algorithm it really hurts that all positions with bishops on the same color are in the TB as well: About 30 sec is spent counting the number of escapes for those states, and this is a complete waste of time, since subsequently these counts will never be decreased. This highlights the fact that which way is optimal depends on the end-game: if eventually almost all positions will be classified as won (and thus have to be fully screened eventually by trying every forward move to no avail) it pays to do the screening pre-emptively. If the end-game will hardly have any won states, it is much more efficient to screen the few states that will be identified as potential wins as they occur, even if you have to repeat that a few times, since not many of them will be identified as such, and the few that are are quickly rejected after trying a few forward moves. The KbbKn is nasty in this respect, because it mixes and end-game that is a total draw (like bishops) to one that is almost totally won (unlike bishops).

[Alex Morozov]

Endgame KBNK is always winning for strong side. But there are much positions were DTM >30. How can you handle this evaluations with your algorithm?

[H.G.Muller]

With the algorithm above I can still handle DTM upto 100. This suffices for the KbbKn (which goes up to 78, I think.) For the 'undecided' positions it is not the DTM that matters but the maximum number of moves the losing side has in a certain position. For KbbKn this is 16 (8 for K, 8 for N), so 28 is more than suficient. If the losing side has K+Q we would need more (27+8=35), but one could simply devote DTM codes 90-125 to the number of moves, and 1-90 for DTM (assumng a 7-bit DTM field in the TB).

Of course this trick limits the maximum DTM one can handle. But in view of the 50-move rule DTMs much larger than 50 are of questionable value anyway. So ~80 can be just as much an arbitrary cutoff as 127... (The most tedious 5-men end-game I encountered was bishop+commoner against nightrider (KkbKh), which is also a total win but requires 307 moves to conversion!)

[Pedro Castro]

The other day I presented a position that gave me problems with my engine, I have found a position that not only gives problems with my engine but also with Latista and tscpegbb that have incorporate the bitbases.

[diag]8/4k3/R7/8/P2KN3/8/8/r7 w - - 1 2[/diag]

FEN: 8/4k3/R7/8/P2KN3/8/8/r7 w - - 1 2

DanaSah v1.8.5:
1 00:00 23 23 0,00 Txa4+ Txa4
2 00:00 316 316 -4,04 Txa4+ Txa4 Re6
3 00:00 1.247 124.700 0,00 Txa4+ Txa4 Re6 Rc4
4 00:00 2.249 112.450 0,00 Txa4+ Txa4 Rg6 Ta7
5 00:00 6.188 206.266 -4,42 Txa4+ Txa4 Rg6 Ta6+ Rf5 Tf6+ Rg4 Cc5
5 00:00 12.960 324.000 -4,41 Ta2 Ta7+ Rg6 Cc5 Td2+ Re5
6 00:00 32.722 467.457 -4,50 Ta2 Cc3 Td2+ Re3 Tc2 Ta7+ Re6 Tc7
7 00:00 81.916 585.114 -4,45 Ta2 Cc3 Td2+ Re3 Tc2 Ta7+ Re6 Tc7 Re5
8 00:00 154.190 700.863 -4,46 Ta2 Cc3 Ta1 Rd5 Txa4 Cxa4 Re7
9 00:00 289.155 781.500 -4,58 Ta2 Cc3 Ta1 Rd5 Tc1 Ta7+ Rg6 Tc7 Tc2
9 00:00 607.406 832.063 -4,52 Ta3 Ta7+ Re6 Cc3 Ta1 Ta6+ Rf5 Ta7 Txa4+ Cxa4
10 00:01 1.063.420 878.859 -4,56 Ta3 Cc3 Re7 Th6 Ta1 Cd5+ Rf7 Cc3 Te1
11 00:03 3.113.218 912.967 -4,62 Ta3 a5 Ta2 Re5 Re8 Cc3 Txa5+ Txa5 Rd7 Cd1 Rc6
11 00:03 3.508.769 913.741 -4,56 Re7 a5 Rd7 Rd5 Rc7 Cc3 Txa5+ Txa5 Rb6 Ta3 Rc7
12 00:04 4.581.690 929.348 -4,62 Re7 a5 Rd7 Rd5 Td1+ Rc5 Tc1+ Rd4 Td1+ Re5 Ta1 Rd5 Td1+ Re5 Rc7
13 00:09 8.622.220 938.217 -4,62 Re7 a5 Rf7 Re5 Ta2 Ta7+ Rg6 Cc3 Ta3 Cb1 Txa5+ Txa5 Rg5 Ta7

In ply 3 and 4, then Rxa4 Rxa4, la eval = 0 ????


Latista:
3 00:00 12.431 177.585 -0,01 Txa4+ Txa4
4 00:00 12.467 178.100 -0,01 Txa4+ Txa4
5 00:00 13.189 164.862 -18,87 Txa4+ Txa4 Re6 Ta5 Rd7
5 00:00 19.372 161.433 -4,83 Ta3 Cd6+ Rf8 Ta8+ Re7 Ce4
5 00:00 22.386 149.240 -4,74 Ta2 Ta7+ Rg6 Ta6+ Rf7 Rd3
6 00:00 36.283 157.752 -4,86 Ta2 Re5 Tc2 Ta7+ Rg6 a5
6 00:00 63.312 166.610 -4,83 Td1+ Re5 Td8 Ta7+ Rg6 a5 Tf8
7 00:00 108.626 175.203 -4,80 Td1+ Re3 Tb1 a5 Te1+ Rd4 Td1+ Re3 Td8
8 00:01 280.141 185.523 -4,83 Td1+ Re3 Te1+ Rf4 Th1 a5 Th4+ Re3 Th3+ Rd4 Th2
9 00:05 1.053.874 185.868 -4,86 Td1+ Re5 Td7 Cg5+ Rg7 a5 Td2 Ta7+ Rg6 Ce4

In ply 3 and ply 4, them Rxa4 Rxa4, eval = 0 ?????

Tscpegbb:
1 00:00 17 17 -3,40 Txa4+
2 00:00 95 95 -4,04 Txa4+ Txa4 Re6
3 00:00 480 480 0,00 Txa4+ Txa4 Re6 Ta6+
4 00:00 3.401 3.401 -4,26 Txa4+ Txa4 Re6 Ta5 Rd7
5 00:00 25.091 313.637 -4,52 Txa4+ Txa4 Re6 Cc3 Rf5 Ca2
6 00:00 173.232 541.350 -4,52 Txa4+ Txa4 Re6 Cc3 Rf5 Ta5+ Rf4 Ca4
7 00:02 1.560.034 636.748 -4,58 Re8 Cc5 Rf7 Tc6 Txa4+ Cxa4 Re7 Cb2

In ply 3 then Rxa4 Rxa4 eval = 0 ?????

[H.G.Muller]

R = King? But in some of the variations it jumps from d7 to g6! R = Centaur?

Anyway, it seems your bitbase contains errors. Better read it out directly with some bitbase browser for the position after the rook captures a7, than to try to deduce the contenst from how programs that consult it play...

[Pedro Castro]

sorry, analyze of engine is in spanish

C = Caballo = Knight = N
A = Alfil = Bishop = B
T = Torre = Rook = R
D = Dama = Queen = Q
R = Rey = King = K