FEG <-> Nalimov stats conversion cracked

[jkominek]

Hi All,

This is a brief note to announce that I've solved the problem of reconciling DeKoning (FEG) and Nalimov stats files. Rather important, for now we have two independent "signatures" available for each tablebase, which can be validated against each other. Some limitations apply. I'll explain in greater detail when the weekend arrives, for the explanation is fairly lengthy.

Q1. Does anyone have the *.lof and *.log files for 3-3 and 4-2 6-man tables? I'd appreciate copies to extend my comparisons. Has anyone computed these tables?

Q2. I'm currently downloading 5-1 tables from Kirill's ftp site to serve as the basis for more extensive checks of my tbgen2-generated files. However KBBPPK_B.J08 and KQQQNK_W.J02 are missing. Martin K. - can you upload these again?

john

P.S. This is my 64th posting. A very chessic number.

[guyhaw]

I would be surprised if there is a generic algorithm for converting FEG stats to Nalimov stats for P-less endgames. Nalimov removes all symmetries except when both Kings are on a main diagonal, while FEG removes none.
I can't remember whether the FEG stats need dividing by k! when there are k-like-men. However, the P-less stats just need dividing by an additional factor of two. I also cannot remember whether FEG 'gets it right' in winner's moves when the loser is forced to convert: I think it's ok.
Certainly, Marc B has the FEG stats up to and including KPPKPP, and maybe he sent them to me a long time ago. I'll look around my PC shortly.

I'm in the market for FEG stats on 5-1 endgames but not the FEG EGTs themselves. Can anyone zip them up and attach to a message here?
g

[jkominek]

Try expanding your sense of the term "generic" ... The trick to reconciling pawnless stats is to run through all positions, separating out those with both kings on the same diagonal. Since, unlike Marc B., I have no idea how to read FEG tablebase files, I scan my own. There is no other way.

Details later, but to briefly jog your memory:
a) You do need to divide by j!...k! like men.
b) Because of the above, treatment of pawnfull stats is not just a matter of dividing by 2.
c) FEG has more symmetries than Nalimov, not fewer (kings on the same diagonal).
d) In unbalanced positions two FEG files must be combined to equal one Nalimov file.

Attached are the FEG 51 stats as generated last year by Martin Kreuzer, available for your purchase. Consider your account pre-paid.

john

[guyhaw]

JK: thanks, and for the prepayment. I found my tabulation of Martin Kreuzer's not-then-completed FEG stats from 2006 and I see that:

- your (Martin Kreuzer's) zipfile completes the FEG 5-1 stats so 'kudos' to MK,
- LOG/LOF = 2 for P-ful endgames, and varies from 4.00 to 8.00 for P-less endgames (not necessarily being an integer either),
- I was dividing the LOF stats by x1!...xn! when Like Men are involved,
- I have some 'GAF' stats alongside, but I don't remember what 'GAF' stood for - and they don't always agree with the FEG stats

g

[jkominek]

With the author being a Guido Antonelli, we can all strike a guess at one half of the acronym GAFS. I wonder if FS is "final system"? This forum has not seen Guido in half a year. At one time he posted with regularity and in abundant detail.

john

[guyhaw]

Yes, I think the 'F' was for 'Final' - always an unfortunate choice of acronym.
Of course, my FEG LOG/LOF ratio is only for the maxDTM counts, and so are more likely to vary from 4.00 to 8.00. I guess that all the maxDTM positions for KBBNNK and KBNNNK have diagonal symmetry.
I guess the next questions are (a) who has the FEG 5-1 EGTs, (b) has anyone got FEN lists of maxDTM positions, and (c) has anyone found any zugs where White cannot back out of stalemating Black?
g

[guyhaw]

Confirmed: GAFS was originated by 'guido', always confusing for me . He was post-processing his stats by attempting to eliminate unreachable positions. I do not recommend this, despite the fact that it is somewhat unsatisfactory to have an unreachable position as the exemplar maxDTM position. The problems with 'elimination' are that (a) others are probably not doing so (the same way) so stats-comparison is a problem, (b) it is difficult to say if all unreachable positions have been reached, and (c) in FischerRandom Chess, some of these positions might be reachable!
The FEG LOF stats of maxDTM positions for P-ful endgames should be those reached by the Nalimov route, and the P-less ones may be slightly lower as Nalimov counts the reflection of a position with 2 Ks on the diagonal as an extra position (unless it is absolutely symmetric). I think that when LOG/LOF = 4 for P-less endgames, the LOF stats will be the same as the Nalimov stats as the latter cannot be higher.
I only have MB's FEG LOF stats for 3-3p EGTs, but have asked him if he can supply the other FEG stats here.
g

[guyhaw]

jk - do you now have reliable 'Nalimov style' stats for 5-1 EGTs? If so, I am interested in what they are: index-range, wtm/btm win/draw/loss/broken etc.
Thanks - g

[Martin Kreuzer]

Q2. I'm currently downloading 5-1 tables from Kirill's ftp site to serve as the basis for more extensive checks of my tbgen2-generated files. However KBBPPK_B.J08 and KQQQNK_W.J02 are missing. Martin K. - can you upload these again?

john

Hi John,
due to professional and private activities (new job, new house, ...), I have not been active here for a while.
But recently I saw your post. I found and uploaded the two missing/damaged files.

Is your tbgen2 code public?

Grettings, Martin

[jkominek]

Martin - thank you for the upload. It's been indispensable. Would you be interested in devoting your computer to FEG for another year? For, say, 42 and 42p. It is a little-known fact that FEG can generate 7-man tablebases, except for the 6-1 variety. 4-2 is necessary prep for 5-2, and it would be reassuring to have (what is believed to be) a reliable cross-check.

john

[jkominek]

Is your tbgen2 code public?

Getting closer. My intention to release it as open source. Before releasing it I'd like to conscript a beta tester, and before conscripting a beta tester I want to shake out all problems known to me. By "it" I mean: the data, example access code, some utilities, a desktop search application, and the generator. Not sure if it will be one lump package or released in stages. The desktop app will be midway in complexity between web-query pages and Wilhelm - I can't even figure out some of Wilhelm's features - and where many people can pitch in. In my estimation the "release early, release often" philosophy of open source does not mesh with egtb generation. Putting faulty code into the wild would be disconcerting, to say the least, and bad data a disaster to clean up.

Originally my goal was to crank out Nalimov-style 5-1 tables and be done with it. But when I grasped the amount of effort involved -- double the number of index functions! complicated processing of unblockable checks!! inscrutable template recursion!!! 1TB of free disk space required!!!! -- I adjusted. My new goal: enable 7 and 8-men table generation, and to give the effort an initial push. So, the rewrite is involved. Pawns-first indexing, simplified (but less space-efficient) index calculation, full 8-way pawnless symmetry, reordered position generation, simplified bit patterning, mmap virtual addressing, a higher degree of parallelism, integrated md5 calculation, better compression, and so on. J’adoube.

john

[gambit3]

Martin - thank you for the upload. It's been indispensable. Would you be interested in devoting your computer to FEG for another year? For, say, 42 and 42p. It is a little-known fact that FEG can generate 7-man tablebases, except for the 6-1 variety. 4-2 is necessary prep for 5-2, and it would be reassuring to have (what is believed to be) a reliable cross-check.

john

apparrently, it is an even littler-known fact that feg can generate up to kwwwwkbbbb, so long as the position has <6 men on each side, so 5v2, 4v3, 5v3, 4v4, 5v4, and even 5v5 tables are possible with it. not bad for a 16 bit executable :>
also, with feg, it is implied that when generating any table, you will generate its opposite number materially speaking, since unlike nalimov, feg doesn't store losses. so when generating kqqkqr for white, you need also to generate kqrkqq for black to have the complete stats. likewise when generating kqqqkq black you must generate kqkqqq white in order to have complete stats. thus, the pawnless stats are identical to nalimov, whereas the pawned stats must be divided by 2. please bear in mind that this is true for EVERY combination of tables in feg, so that kqqkqq for white needs kqqkqq for black AS WELL AS the 5 man dependancies for the stats to be accurate for feg.

an afterthought:
i would be curious to see the comparison (on comparbale hardware) of a run of feg over a middle-of-the-road 5 man table on the windows vs. a linux/wine or linux/vmware platform. by this i mean the time stats for each part of the process for each ply are recorded in the .log files. it might be interesting to see the results...

[Vegan]

Is your tbgen2 code public?

Getting closer. My intention to release it as open source. Before releasing it I'd like to conscript a beta tester, and before conscripting a beta tester I want to shake out all problems known to me. By "it" I mean: the data, example access code, some utilities, a desktop search application, and the generator. Not sure if it will be one lump package or released in stages. The desktop app will be midway in complexity between web-query pages and Wilhelm - I can't even figure out some of Wilhelm's features - and where many people can pitch in. In my estimation the "release early, release often" philosophy of open source does not mesh with egtb generation. Putting faulty code into the wild would be disconcerting, to say the least, and bad data a disaster to clean up.

Originally my goal was to crank out Nalimov-style 5-1 tables and be done with it. But when I grasped the amount of effort involved -- double the number of index functions! complicated processing of unblockable checks!! inscrutable template recursion!!! 1TB of free disk space required!!!! -- I adjusted. My new goal: enable 7 and 8-men table generation, and to give the effort an initial push. So, the rewrite is involved. Pawns-first indexing, simplified (but less space-efficient) index calculation, full 8-way pawnless symmetry, reordered position generation, simplified bit patterning, mmap virtual addressing, a higher degree of parallelism, integrated md5 calculation, better compression, and so on. J’adoube.

john

Well I was contemplating the work myself back around 2006. Adding 51 is not really necessary, most engines can beat up on a lone king easy enough with 4 pieces to work with. Adding 43 and 52 would be good and even 44 and 53. The house of pain, with 54, would stress even the best machines on the drawing board. 55 likely exceeds the capability of a 64-bit machine.

Remember besides TBGEN there is the EGTB.CPP that needs extension to allow engines to be able to consult the tablebases.

I suggest the new TBGEN be open source, and free to use to encourage wide adoption.

[jkominek]

Adding 51 is not really necessary, most engines can beat up on a lone king easy enough with 4 pieces to work with. Adding 43 and 52 would be good and even 44 and 53. The house of pain, with 54, would stress even the best machines on the drawing board. 55 likely exceeds the capability of a 64-bit machine.

The reasons for engaging 51 are 1) completeness, 2) the learning experience, and 3) dependencies. 52 depends upon 51 (and 42); 53 depends on 52; 54 depends on 53; 55 depends on 54.

One of the first tasks of endgame computation is figuring out the dependency graphs. The full graph up to 9 men is BIG! I once used the graph layout program 'dot' to visualize it. As I remember, pdf and postscript files failed because I exceeded an internal limit of the file format. When I switched to svg format, I could find no reader that could render the file. Similar situation for raster graphics format. Perhaps if I dropped all labels and shrunk the node size it could be made to fit within limits, but then it wouldn't be much of a visualization aid.

These figures provide an idea of the complexity. Double the number of nodes to get the tablebase count.

Code: Select all

Men Nodes  Edges
2   1      0
3   5      9
4   30     99
5   110    495
6   365    2025
7   1001   6435
8   2520   18153
9   5720   45045
10  12190  103275

Also, arguing that strong chess engines can play winning lines in highly unbalanced positions misses the point. With respect to their chosen metric, endgame tables provide complete and perfect knowledge. Endgame tables stand alone on their own merits. While they can be used by software chess programs, they are not subservient to them.

john

P.S. I've been absent from the forum for a few months as I have a bunch of work-related obligations ongoing. It may take 2-4 weeks to clear my plate sufficiently to revisit EGTB generation.

[Vegan]

I did a few calculations to estimate the file sizes for various tablebases to estimate how many file servers would be needed to the proposed tablebase generator, there are 5 basic piece types for estimating the number of files. Moving from 6 to 7 pieces needs about 58x the number of positions.

For each part in the 42, adding one to make 43, we get 5x more files than there are in 42 (including pawns). For a queen, rook or knight each part will be 58x bigger than the corresponding 42 part. For a bishop the part will be 32x larger, and for a pawn it will be 48x larger. To calculate the exact number is based on the uncompressed sizes.

Now with these estimates, no optimization based on symmetry etc was considered. From this basis I created an educated estimate of how many servers would be needed.

http://contract-developer.dyndns.biz/ar ... limov.html

Once the machine is built, work on the full 7 piece set can be done.

[vb4]

Hi John,

So nice to see you back here <s>. Listen if you need a hand cleaning up that plate of yours give me a shout <S>.

Take care,

Les