bitbase sharing

[Daniel Shawul]

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

[Ryan Benitez]

Thanks Daniel, I hope people take advantage of this as I am sure many programs can greatly benefit from your great bitbases.

Ryan

[Robert Allgeuer]

Daniel,
as a matter of interest:
have you generated the bitbases by yourself from scratch or have you used the Nalimov EGTBs as oracle?

Thanks
Robert

[Daniel Shawul]

Yes i used Nalimov TBs to create the bitbases , like every one else does.
I haven't thought this could be a problem before I post here.
It is possible to generate the *same* data from other free TB generatros , or
write a generator using retrograde analysis (which is very unlikely).
Anyway i have asked Eugene for permission , so if the answer is no it means
i have to use one of the above options.
Daniel

[Fabien Letouzey]

Hi Daniel,

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.

Linux and Mac OS X also handle their own DLL format (.so files). If your code is neatly separated from the engine, i.e. there is an include file that describes the API and a set of .c(pp) files that contains the implementation (with no main() ), there is a way to build a library file from the compiled object files. Of course I assume you use only portable functions like malloc() and fread().

I used to build libraries for my own often-used functions, but I switched to including them into every project for Windows-compatibility reasons.

Fabien.

[Robert Allgeuer]

Yes i used Nalimov TBs to create the bitbases , like every one else does.
I haven't thought this could be a problem before I post here.
It is possible to generate the *same* data from other free TB generatros , or
write a generator using retrograde analysis (which is very unlikely).
Anyway i have asked Eugene for permission , so if the answer is no it means
i have to use one of the above options.
Daniel

no problem at all, I jsut asked because of interest.

Thanks
Robert

[Daniel Shawul]

I just started writing generator for table bases.
I used the forward retrograde analysis method, as described
by Jasper's thesis paper.You will find the link in the bitbase dicussion thread on page 3.
I generated the KRK tb, and it turns out that maximum mate length is 17, which assured me that i am doing things right.
The forward method can be used upto 5 men.I will create the TBs
both in DTM and WDL. I don't know about compression , so anyone with expertise can join the project. I will just create raw data and some one can write the compression/decompression.
TBs when finished will be liscenced BSD style , so anyone can use them.
daniel

[H.G.Muller]

I also wrote a program to generate table-bases in RAM, and it works efficiently enough to wonder why people precompute such table bases and store them on disk. For instance, it finds a mate-in-29 position in the KQKR endgame in 124 sec on a rather run-of-the-mill laptop. (It does not continue building the table-base once it has determined the score of the position you give it.) And I do not even use symmetry reduction in that case. For 5 pieces symmetry reduction would be essential not to exceed the memory capacity of my laptop: 65^5 = 1.19G, while 8-fold symmetry reduces this to 178 MB.

I did not implement the symmetry, because the presence of pawns breaks the symmetry anyway, and I consider end-games with pawns much more relevant than those with only pieces. Within the available memory it can do about 6-7 pawns, depending on the situation.

Nevertheless I am a bit disappointed in what the table bases can achieve. Transposition tables might be a much more practical way than table bases for good end-gaming. Although they store ~8 times as much information per position, the information in the transposition table is much more relevant. For instance, a king might be tied to the neighborhood of a defended passed pawn to prevent trivial win, enormously reducing the number of relevant positions compared to a table base that has that king roaming the board.

[Uri Blass]

I also wrote a program to generate table-bases in RAM, and it works efficiently enough to wonder why people precompute such table bases and store them on disk. For instance, it finds a mate-in-29 position in the KQKR endgame in 124 sec on a rather run-of-the-mill laptop. (It does not continue building the table-base once it has determined the score of the position you give it.) And I do not even use symmetry reduction in that case. For 5 pieces symmetry reduction would be essential not to exceed the memory capacity of my laptop: 65^5 = 1.19G, while 8-fold symmetry reduces this to 178 MB.

I did not implement the symmetry, because the presence of pawns breaks the symmetry anyway, and I consider end-games with pawns much more relevant than those with only pieces. Within the available memory it can do about 6-7 pawns, depending on the situation.

Nevertheless I am a bit disappointed in what the table bases can achieve. Transposition tables might be a much more practical way than table bases for good end-gaming. Although they store ~8 times as much information per position, the information in the transposition table is much more relevant. For instance, a king might be tied to the neighborhood of a defended passed pawn to prevent trivial win, enormously reducing the number of relevant positions compared to a table base that has that king roaming the board.

I do not understand
1)why do you need 65^5 for 5 piece tablebases when there are only 64 squares in the board.

There are basically 64*63*62*61*60*2 positions when you consider side to move and do not consider symmetry.
With pawns you can reduce 64 to 48

2)If you use symmetry consideration then you can reduce it by a factor of 2 regardless of pawns because you can assume without loss of generalization that the white king is in a-d files.

On the other side you need to consider side to move so you practically have less than 64*63*62*61*60 positions for every table.

If it has no pawn you can reduce it again by symmetry and if you have pawns you can reduce 64 to 48.

Uri

[H.G.Muller]

The pieces might be be captured, and I use a 65th square to park them when this is the case. I agree I am a bit generous, not making use of the fact that no two pieces can occupy the same square and that kings can't be captured (in my implementation, they actually can: I generate the mate positions from in-check positions, which I again generate from time-reversed moving from positions with one king lacking).

The difference between a factor 65 or 62 is immaterial: 4-piece databases always fit in memory easily, for 5 pieces they fit easily after the symmetry reduction that restricts the white king to the 10 fields of a triangular board sector, and would not fit by at least a factor 3 without it. So there is little point in squeezing out the extra few percent of storage, what I lose in size of the database I gain back in calculation speed because of the more straightforward decoding of the database index to board position (as a radix 65 number).

As for the pawns: since the effort was aimed at creating the database during the match, I am not interested in databases for all KPPKP end games, just in those for the pawns that happen to be on the board. This gives a much larger reduction than symmetry could ever give you: if I have a pawn on e4 in KPK it only has 6 possible positions (also counting captured and on its promotion square, which is my starting situation from which I work back and has to be in the database). So why bother about the 42 (or 50) other positions with one pawn? Restricting myself to the reachable positions buys a lot larger reduction than symmetry, at the expense of having no symmetry left at all. (Exept for very special pawn formations, such as KPPKPP with both parties having pawns in the K and Q file.)

So I simply generate all reacheable pawn positions recursively and store them in a hash table, and the size of my table base is then the number of pawn formations times the appropriate power of 65. In fact I even distinguish pawn formations that can be reached only through capture of another piece (not a pawn), because although there might be many more they need one power of 65 less due to the missing piece. So if I have for instance a white pawn on e3 and a black one on e5, there are only 3 positions with both pawns on the board, 6 with the black pawn missing, 5 with the white pawn missing, and 1 without pawns altogether. These 15 are all that can occur in a king's end-game. If both sides would have (say) a bishop the pawns can migrate to the d or f files, leading to an extra 10x5 + 8x6 = 98 pawn formations with one bishop lacking, and 10x8 = 80 with both bishops lacking (perhaps less, depending where the first capture can be made for a bishop of the given color). The number of table-base entries is then 65*65*33*33*15 = 69M for the two-bishop positions, and 65*65*33*178 = 25M for the single-bishop positions, which easily fits in memory and might need ~15-20 minutes of construction time. This seems acceptable, since after that moving will be instantaneous.

[Daniel Shawul]

I am a bit confused here. Do you generate the tables after you look at the actual board. For example when you detect a pawn ending, you start
generating KPK table? Ok 3 piece tables may be generated fast, what about 4 pieces? Also what do you do when a conversion occurs. KPK might go in to KQK or KRK?
daniel

[Daniel Shawul]

I can also add that generating the relevant (on actual board) position is not that important , because the main benefit of TBs is detecting transpositions in to won endgames. Once the position occured , many engines can solve it without the help of TBs.

[H.G.Muller]

For example when you detect a pawn ending, you start generating KPK table?

This was indeed the intention (I must mention that after a 15-year break I re-entered the computer-chess arena only 2.5 month ago, so not everything works as intended yet...)

When I detect a KPK ending I generate a KPK tablebase, and since I know which pawn I have it can be a rather small one.

The actual board position remains important even if you want to use the tablebase just as a lookup table for winning conversions. If I have KRPPPKRPP usually the tablebase would be way too big, but a tablebase for the relevant KPPPKPP ending would contain only 5-10M positions. So I make that one to be sure when to exchange the rooks. I coud also make several KRPKPP tablebases, if i am afraid sacrificing a rook might give him any play. Making (or even storing...) a tablebase for all KPPPKPP endings would in itself be a daunting task!

Currently my pawn tablebases are aimed at conversion. After conversion it is no use anymore, which simply means that the engine won't generate any hits in it and resumes to its ordinary mode of searching moves. (It might decide to create a new tablebase for the converted game, however.)

When you say '4-piece', do you mean 4 pieces plus pawns or 4 pieces bare? As I wrote, the latter is no problem at all, KQKR is generated in just a few minutes, without using symmetry. With additional pawns it becomes quickly too hard, of course: the time it takes is simply proportional to the size of the tablebase. This is ~18M for a 4-piece-bare ending (without using symmetry), but even adding a single pawn that is more than halfway multiplies this by ~5.1, and it might take 15 min to construct that.

Performance could be increased, though, by hand-optimizing the code in assembler or a faster CPU (I run on 1.3GHz Celeron now), so everything under 1 hour I still consider feasible.

[Daniel Shawul]

When you say '4-piece', do you mean 4 pieces plus pawns or 4 pieces bare? As I wrote, the latter is no problem at all, KQKR is generated in just a few minutes, without using symmetry. With additional pawns it becomes quickly too hard, of course: the time it takes is simply proportional to the size of the tablebase. This is ~18M for a 4-piece-bare ending (without using symmetry), but even adding a single pawn that is more than halfway multiplies this by ~5.1, and it might take 15 min to construct that.

i meant the bare 4 piece endings. All of the the four piece endings took
me 130 minutes to generate, that is including unnecessary K + 2 vs K endings. Your generator must be much faster than mine. At classical time controls , it might be possible to generate some of the pawn less endings while pondering. But the most important are those with pawns, and these need generation of other sub endings. I don't want to waste any time
generating tbs during a game unless it takes a few seconds.
Daniel

[H.G.Muller]

I agree, the pawn-less endings are more of academic interest, in practice one always has pawns, or at least should have done better thinking while there still were pawns. Absence of pawns really requires an overkill in material to secure a win equivalent to 5-6 pawns where normally 2 do the job...

But this is exactly what brought me to my current approach: the size of the TB explodes with the number of pawns much faster if you allow the pawns to be anywhere than when you limit yourself to where the pawns that you actually have can go.

In the end it is all a matter of economics: how many GB are you willing to store to save 1 sec of pondering. Accessing data on disk also takes time, in fact I suspect that this might be the explanation for your 130 minutes (I counted 30 4-piece endings, 15 KxxK and 15 KxKx, so apparently it took you 260 s per ending. In comparison, the full TB for the won KQKR positions takes me 141 s, (and some seconds more to find a few lost positions, mainly because it has KRK as a subset), and 84 sec for KBNK. The difference might be well explained from not writing the result to disk. I made no effort to make the generator exceptionally clever or efficient, I figured it would spend most of its time fetching table entries from memory as it runs through the full table for every ply it wants to expand, to add the parent states or (every odd ply) mark them for forward checking.

To judge performance: the KQKR database goes to about 72 ply, so it has to work through 18M of memory (the size of a 4-piece TB) every 2 s, an average of ~100 ns per entry. Since this access is strictly sequential, and mostly read-only (to discover that the states in question are not marked) this seems a bit slow: with these DDR memories on a 100 MHz FSB one should be able to read about one 8-byte word per busclock. Of course when it finally finds a marked entry it really has to start working (checking daughters or marking parent states), but eventually every state can be added to the set of won states only once, and only at that time the marking of parents start. Most of the time then probably goes to checking the potentially-lost-for-the-side-to-play situations, although in practice 10-20% of those situations check out as lost-indeed, and the one for which a move can be found that escapes the loss the check is cheap since it can be aborted on the first move that does so. So come to think about is, I am surprised the process is as slow as it is, and if I really worked on it I could probably speed it up a factor 10.

[H.G.Muller]

I am still a bit worried about the performance, it seems unreasonably far from the theoretical maximum. First I figured that this was because it spend most of its time coding and decoding the TB index to board position, and vice versa. So I changed to an even more trivial encoding, that can be updated differentially both ways: the move generator can differentially update the index, and the sequential scan through the TB can differentially update the board. I wrote a new code especially aimed at speed (for pawn-less end-games).

This sped up the process by a factor 3: for the KQKR tablebase (won positions, DTM) it now uses 49 seconds, while to find the mate in 28 that took my old generator 136 sec, it now needs 43 sec. The KBNK TB takes 28 sec (a mate in 29 was found in 23 sec instead of 94 sec).

All this was without use of symmetry (that is next on my Christmass list, so that I can do 5-men TBs), naively I would think that symmetry speeds up the process another factor 6 (so 8 sec for KQKR, and 4,5 sec for KBNK). All this measured on a 1.3GHz Celeron with 512MB DDR RAM. 5-men TBs would still require an uncomfortably long time if you would want to construct them during the match (~ 7 min).

I am still disappointed by this performance. I timed scanning through a 160M TB (the size for 5-men with symmetry), updating the board at the same time, and one scan takes only 0,85 sec. For the 16M 4-men unsymmetrized TB this is only 85 msec. I do 2 scans to get to the next the DTM, one for labelling the potential mate-in-(n+1) as the grandparents of all mate-in-n, and one to check them out (if all daughters are mate-in-n or faster). To get to DTM=33 thus requires only 5,5 sec of scanning time. Most of the time is apparently spend now processing the small fraction of positions that need processing. I am surprised that this takes such a large fraction of the time. This still point to a major inefficiency.

[H.G.Muller]

OK, I did implement symmetry (especially the diagonal symmetry was a pain), and generating the KQRK TB in RAM now takes 7,5 sec. So I jumped tot the next level, and tried my first 5-piece TB, for KRBKR. This took about 220 sec (but is probably not the most difficut one, I picked it because in number of moves per side it is comparable to KQKR).

The main question of course now is: are the results correct? Can anyone help me with this? Is there an easy overview somewhere on the properties of the various end-game's, like longest DTM, or the distribution of the DTMs, that I could compare my numbers against? For KRBKR the longest DTM I found was 63, with white to move, e.g.:

[diag]8/4R1B1/8/8/3K4/8/8/k1r5 w --[/diag]
8/4R1B1/8/8/3K4/8/8/k1r5 w --

with Kd4-d3 as an optimal move to a 'mated-in-62' position.

Can anyone tell me if this is correct?

[Joachim Rang]

seems correct. You can check yourself:

http://www.shredderchess.de/online-scha ... nbank.html

Joachim

[H.G.Muller]

Thanks, that is a very useful link. So far the positions I find as longest DTM seem to check out with this server. I tried a KQQKQ example too (mate in 30). It took 622 sec to generate this TB, which I expect to be the worst case. I did not make use of exchange symmetry of the two white queens, though, which in theory would save a factor 2.

So the positions do check out w.r.t. their DTM, which is encouraging. This does not prove that they are indeed the longest DTM, however. I guess what I really would need is the KRBKR.tbs file. Although I could find such .tbs files for all the 6-men endings on Bob Hyatt's site, they did not seem to be there forr the smaller endings. Does anyone know where I can obtain such files?

[diepeveen]

Hi Daniel,

I just have 1 question to avoid Nalimov problems from repeating once again. Can you put a GPL header on top of all your codefiles and then spread it like that?

That puts an end to all problems forgood and knows for others that what you do you do to be real freeware.

Without GPL header it's clear that you reserve all rights to your code, just lik nalimov, and can do what you want.

Actually there is many persons with their own generators for EGTBs.

I'm actually busy parttime on a 6th attempt now. A real lightning speed fast one. A problem is that those 7 men are giants.

Vincent

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