New Website, dedicated to my 7-men tablebase generator

[h.g.muller]

Now that I have started coding work on my 7-men EGT generator, I thought it a good idea to already put the description of its design and the algorithm it will be using on my website. So I have now devoted a section of 14 web pages to tablebases, in addition to the two pages I already had. You can find them at:

http://home.hccnet.nl/h.g.muller/EGT7/7-men.html

Feedback will be welcome.

[koistinen]

Nice explanation of K-slice Streaming. Now I at least understand it in part.
The way I'd do it might be different: Have one leap include pawn moves that cause a diagonal flip and the other moves that cause a horisontal flip.
Vertical flips would only ever be caused by moves to/from d4 so I'd simply treat that as a special case and accept using more memory for that square.
That way for 3-4 I'd reduce the size by almost a factor of 32 compared to storing the full bitbase and it would easily fit in 8GB despite the move Kd4c5 and taking two steps each leap complicating things.
That leaves 2-5 and I believe there is some good algorithm to exploit the fact that very few of the btm positions are lost.

[koistinen]

Now I think I understand your K-streaming better.
Say the white pieces are KQR, then you might assign moves within a-b, c-d, e-f, g-h to one leap and the other king moves to the other.
Then load KabQxR, (x being the fixed position of the queen and the actual position the one after mirrorings).
Do the leap within that partition and store the result, then do the same for, KcdQxR, KefQxR and KghQxR respectively for each x that has not yet been processed.
For the second leap, do KaQRy, KbcQRy, KdeQRy, KfgQRy and KhQRy respectively for each y that has not yet been processed.
If you need to save more memory, split each partition into smaller parts, say 1-2*-3*, 2--3*-4*, 3-4*-5*, etc with * indicating partial leap computation.

About your website, it would be helpful if the title was in a form like: Leapfrog tablebase generator - K-slice Streaming
Then I could navigate my open tabs more easily.

[koistinen]

I wrote a small program to compute how much the symmetry of multiple pieces of same type can reduce size of database for the 7-man endgames and got the following results:
$ gcc -O2 -Wall count.c
$ ./a.out |grep -v [Pp]|sort|awk '{print $1}'|uniq -c
4 120,
44 12,
56 1,
44 24,
276 2,
156 4,
156 6,
$ ./a.out |grep [Pp]|sort|awk '{print $1}'|uniq -c
1 120,
26 12,
195 1,
26 24,
544 2,
174 4,
174 6,

As you can see only 56 of the pawnless endgames have no extra symmetry.

The attached code is a little silly, but I think it works and if not it should be obvious.

[h.g.muller]

I followed your recommendation for the web-page titles.

It s true that in 7-men EGTs you have so many pieces that it becomes difficult (and thus rare) to have them all different. But I am not only interested in the 4 orthodox piece types, and with more piece types the fraction that has doublets is much smaller.

Note that the EGTs with triplets (or worse) are of little practical interest. So basically only those with 'degeneracy factor' 1, 2 or 4 are important. Note that Leapfrog as I am building it now can exploit a single doublet for white, by using the two equal pieces as 'symmetry indicator pieces', almost automatically. (Only the mapping from square numbers of these two pieces to chunks in the TB file has to be initialized differently.)

The 276 doubly-degenarate 7-men are composed as 4 6+1, 48 5+2, 72 4+3 where the white has a doublet, 16 4+3 where black has a doublet, 16 3+4 where white has a doublet, 72 3+4 where black has a doublet, and 48 2+5. The latter I cannot do at all, because I am currently limited to 4 black pieces. So of those I can do, 4+48+72+16 = 140 have a white doublet, and 16+72 = 88 have a black doublet. In the latter case I do not have any reduction, while a factor 2 would have been possible.

The 4-fold degenerate 7-men have two doublets. For 6+1 (12) and 5+2 (24) both doublets must be white. For 4+3 and 3+4 they must be of different color, wich can be realized in 48 different ways (each). 2+5 I cannot do and 1+6 does not count. So in all 132 cases I can do there is a white doublet, meaning I reap a factor 2 reduction where a factor 4 would have been theoretically possible.

So of the interesting 56 + 276 + 156 = 488 pawnless 7-men, I will be able to build 52 + 228 + 132 = 412. (There are 4 2+5 with all different pieces I cannot build.) Counting those where I reduce the size by a factor two by making use of white exchange symmetry as 1/2, I have to do 276 units of work. Completely exploiting the symmetry, the work would have been 52 + 228/2 + 132/4 = 52 + 114 + 33 = 199. So by not exploiting exchange symmetry other than for a single white doublet, I fail to reduce the total amount of work by 28%. I think that is acceptable.

[koistinen]

Thank you for the web-page titles.
We have different goals but in part they overlap. My interest is mainly in how to efficiently compute, with computing all 7-man endgames for standard chess a part of that. Also I like affordable computing, so as long as the hardware is not too expensive it might interest me. Storing and making available the result for use by all is also interesting. I don't mind if the computing is mostly done by others, as long as the results can be checked.

If you are doing the other endgames I can concentrate on 2-5 Need to start doing the 4-man though, as the 2-1 are the only ones I have done so far.

I have split the statistics for pawnless 7-man into 4-3, 5-2, 6-1 and 7-0.

Code: Select all

$ gcc -O2 -Wall count.c
$ ./a.out|grep -v P|grep -e '-...$'|sort|awk '{print $1}'|uniq -c      16 12
     24 1
     88 2
     48 4
     24 6
$ gcc -O2 -Wall count.c
$ ./a.out|grep -v P|grep -e '-..$'|sort|awk '{print $1}'|uniq -c
     16 12
     24 1
     88 2
     48 4
     24 6
$ ./a.out|grep -v P|grep -e '-.$'|sort|awk '{print $1}'|uniq -c
      4 1
     16 24
     48 2
     24 4
     48 6
$ ./a.out|grep -v P|grep -v -e '-'|sort|awk '{print $1}'|uniq -c
      4 120
     12 12
     12 24
      4 2
     12 4
     12 6

[guyhaw]

I am wondering if hgm's proposed approach to 7-man EGTs will generate correct EGTs for less than 7 men. If so, its correctness may be verified against existing Nalimov DTM EGTs which are [reasonably] assumed to be correct.

I'm wondering how generic and portable the concepts are: the more they are, the more the verification against existing EGTs will encourage us that 7-man EGTs might be ok.

g

[h.g.muller]

I am writing the generator such that it can handle 6-men as well as 7-men EGTs. But although much of the code will be in common, some code will be specific to the 7-men case. So strictly speaking, it wouldn't prove anything if the 6-men generated this way are correct.

I guess the best way to test aong these lines would be to build in a special test mode, where one black piece is completely ignored. (I.e. a piece that has no moves, and does not block any moves of other pieces of either color.) Building a 7-men would then reproduce 64 times the corresponding 6-men.