5-1 EGTB's

[vb4]

Hi Eveyrone,

Its been a while since I have asked about this subject. I am wondering if anyone knows if anyone is working on generating them yet. I am in the process of getting a new system and I would be willing to try and generate them if someone could modify Eugene's code. Keep in mind I am aware of the fact that due to his indexing scheme engines wont be able to using the tablebases but all I am interested in generating is his infamous table base stat files.

Thanks in advance,

Les

[jkominek]

Dear Les,

Your plea is heard and not forgotten -- and can be answered in the affirmative for both your indirect ("if anyone knows?") and direct forms ("if anyone is?"). In the attached tar file you will find - hot off the grill - tbs files for 15 of the 70 5-1 tablebases. These are all pawnless. The other 20 pawnless tablebases are ready to be queued up, pending some touch-ups to the code. Stay tuned to this space for their arrival.

As is always true of endgame work, the pawnfull games are harder to implement and generate. I don't know what I can promise for these, but can pledge to look into it over the coming holidays.

About the statistics: as would be expected of totally unbalanced positions, wtm never loses and btm never wins. In fact, wtm always wins except for when the pieces are uncoordinated; in particular kbbbbk (13.5%), kbbbnk (0.005%) and knnnnk (tiny faction). kqqqqk takes at most 3 moves to win, but when black is to move there are a substantial number of draws due to stalemate (4.9%). The longest losses by black are 34 moves for kbbnnk (5 occurances) and 33 moves for kbbbnk (25 occurances). I haven't yet extracted the extrema positions for review, but intend to do so.

The "broken" position counts are for what is basically Heinz/Wirth indexing, something considerably simpler than the Nalimov scheme. Actually, there is no Nalimov indexing for 5-1 tablebases, since he never invented one. The reason is simple ... or the opposite of simple, depending on your point of view. Complexity! It's ironic that while the 5-1 bases are the smallest and most useless of their 6-man ilk, they are the most complicated to add. I suppose you could say that the ratio of motivation to complexity is so low that no one (until yours truly) found it compelling to crack this nut. Or got scared away. The code in tbgen is - shall we say - not readily given to modification. [Doubly so for me. I don't program in C++.]

The 2x15 tablebase files are 28GB in size, uncompressed. I do plan to share compressed versions of these files on emule, once thoroughly verified. (It will be interesting to see who actually wants them.)

Which brings me to the issue of ... verification. It's still pretty basic at this stage. So please, consider the stats to be "tentative". What I've done is simplify the indexing of the entire 3-6 man bases, and regenerated the dependencies all the way down to kbk etc. As a sanity check, I verify that the tbs stats are identical to the known reference set, ignoring broken counts. I have not yet performed the standard internal consistency check, which is a necessary (but not sufficient) condition for release. One can also give a sampling of positions to a chess engine known to play endgames strongly. Should it every find a faster mate something is definitely not right. I wouldn't mind assistance from the community in performing random spot checks.

And in case you are wondering, the full 5-1 set contains 622 billion positions. Assuming a compression ratio of 4-5, someone wanting a truly complete 6man set will need to download an extra 120-160 GB of data. When available.

john

[jkominek]

Hmm. My session timed-out while composing, and it seems the attachment got lost in the shuffle. Let me post again.

john

[vb4]

Dear Les,

Your plea is heard and not forgotten

<SSS> Great going John I am so excitied that you are generating these for the most part useless egtb's as others have said but to me it will allow me to complete my study of egtb's 3 to 6. You know I will be watching patiently for the arrival of others.

BTW John how long does it take to complete one of the tablebase files and what equipment are you running and what language are you using?

Good work and thx,

Les

-- and can be answered in the affirmative for both your indirect ("if anyone knows?") and direct forms ("if anyone is?"). In the attached tar file you will find - hot off the grill - tbs files for 15 of the 70 5-1 tablebases. These are all pawnless. The other 20 pawnless tablebases are ready to be queued up, pending some touch-ups to the code. Stay tuned to this space for their arrival.

As is always true of endgame work, the pawnfull games are harder to implement and generate. I don't know what I can promise for these, but can pledge to look into it over the coming holidays.

About the statistics: as would be expected of totally unbalanced positions, wtm never loses and btm never wins. In fact, wtm always wins except for when the pieces are uncoordinated; in particular kbbbbk (13.5%), kbbbnk (0.005%) and knnnnk (tiny faction). kqqqqk takes at most 3 moves to win, but when black is to move there are a substantial number of draws due to stalemate (4.9%). The longest losses by black are 34 moves for kbbnnk (5 occurances) and 33 moves for kbbbnk (25 occurances). I haven't yet extracted the extrema positions for review, but intend to do so.

The "broken" position counts are for what is basically Heinz/Wirth indexing, something considerably simpler than the Nalimov scheme. Actually, there is no Nalimov indexing for 5-1 tablebases, since he never invented one. The reason is simple ... or the opposite of simple, depending on your point of view. Complexity! It's ironic that while the 5-1 bases are the smallest and most useless of their 6-man ilk, they are the most complicated to add. I suppose you could say that the ratio of motivation to complexity is so low that no one (until yours truly) found it compelling to crack this nut. Or got scared away. The code in tbgen is - shall we say - not readily given to modification. [Doubly so for me. I don't program in C++.]

The 2x15 tablebase files are 28GB in size, uncompressed. I do plan to share compressed versions of these files on emule, once thoroughly verified. (It will be interesting to see who actually wants them.)

Which brings me to the issue of ... verification. It's still pretty basic at this stage. So please, consider the stats to be "tentative". What I've done is simplify the indexing of the entire 3-6 man bases, and regenerated the dependencies all the way down to kbk etc. As a sanity check, I verify that the tbs stats are identical to the known reference set, ignoring broken counts. I have not yet performed the standard internal consistency check, which is a necessary (but not sufficient) condition for release. One can also give a sampling of positions to a chess engine known to play endgames strongly. Should it every find a faster mate something is definitely not right. I wouldn't mind assistance from the community in performing random spot checks.

And in case you are wondering, the full 5-1 set contains 622 billion positions. Assuming a compression ratio of 4-5, someone wanting a truly complete 6man set will need to download an extra 120-160 GB of data. When available.

john

[jkominek]

<SSS> Great going John I am so excitied that you are generating these for the most part useless egtb's as others have said but to me it will allow me to complete my study of egtb's 3 to 6. You know I will be watching patiently for the arrival of others.

BTW John how long does it take to complete one of the tablebase files and what equipment are you running and what language are you using?

Good work and thx,

Les

You're welcome. Many of us are wondering exactly what will emerge from your study.

I'm using a Quad-Core Xeon X5355 at 2.66GHz with 16 GB of RAM, when it is not being allocated to more serious tasks. (It's not a personal computer but belongs to our University group.) kqrbnk consumes 12GB and I want to hold it all in main memory. The computation times depend on the number of positions (duplicate pieces cuts down on unique positions), and on how quickly mate is reached, on average. kqqqqk completes in 15 minutes, while for kbbnnk it is closer to six hours. The times will get progressively longer as I work through the remaining list.

The program is C++ still, as it is a derivative of tbgen.cpp. Intentionally, I'm taking a conservative route compared to writing a new program from scratch. When I said that I "don't" program in C++ what that means is I don't choose to, unless circumstances dictate otherwise.

On an interesting side note, earlier this morning and afternoon I attend a series of lectures on M45/Hadoop, the new supercomputing cluster that Yahoo is making available to us for research.

See http://yhoo.client.shareholder.com/pres ... eID=275236.

If this cluster were devoted to just one task I've estimated that constructing the full 7-man set would take 1.75-2 years (it has enough hard drive capacity now), and the 8-man set would take 100 years. Research projects have to be approved by a steering committee, and I have a difficult time imagining that chess endgame calculations would make it through, so don't hold your breath. But I have given some serious thought to how one would fully utilize a 4000 CPU cluster. The task is not so well suited to the "Map/Reduce/Collect" programming paradigm that is coming into fashion for large-scale computation, and so calls for some heavy hammering to bend it into shape.

Mind you, if there is a wealthy patron out there who declares "let me build you a supercomputer to compute these tablebases and give them to Anand so that he is better equipped to defeat Kramnik (or vice versa)" I would jump at that chance. Anyone have connections?

john

[vb4]

<SSS> Great going John I am so excitied that you are generating these for the most part useless egtb's as others have said but to me it will allow me to complete my study of egtb's 3 to 6. You know I will be watching patiently for the arrival of others.

BTW John how long does it take to complete one of the tablebase files and what equipment are you running and what language are you using?

Good work and thx,

Les

Hi John and thx for yor reply and other points of interests. When I am done with my study I certainly will post it and look for comments and feedback from you and anyone else. I am so happy to hear your interest or curiousity in finishing the 5-1 set and you have a great opportunity with the universities cmptr. This completion will allow me to further support some interesting trands I am finding. As each new EGTB set is done allows me to see further down the line to either support or refute these trends.

I guess when your done with this 5-1 set you will start implementing that gigantic cluster to "wrap up" the 7 piece EGTB!!! <S> Just kidding but it certainly sounds exciting based on your guesstimates.

Talk to you soon,

Les

You're welcome. Many of us are wondering exactly what will emerge from your study.

I'm using a Quad-Core Xeon X5355 at 2.66GHz with 16 GB of RAM, when it is not being allocated to more serious tasks. (It's not a personal computer but belongs to our University group.) kqrbnk consumes 12GB and I want to hold it all in main memory. The computation times depend on the number of positions (duplicate pieces cuts down on unique positions), and on how quickly mate is reached, on average. kqqqqk completes in 15 minutes, while for kbbnnk it is closer to six hours. The times will get progressively longer as I work through the remaining list.

The program is C++ still, as it is a derivative of tbgen.cpp. Intentionally, I'm taking a conservative route compared to writing a new program from scratch. When I said that I "don't" program in C++ what that means is I don't choose to, unless circumstances dictate otherwise.

On an interesting side note, earlier this morning and afternoon I attend a series of lectures on M45/Hadoop, the new supercomputing cluster that Yahoo is making available to us for research.

See http://yhoo.client.shareholder.com/pres ... eID=275236.

If this cluster were devoted to just one task I've estimated that constructing the full 7-man set would take 1.75-2 years (it has enough hard drive capacity now), and the 8-man set would take 100 years. Research projects have to be approved by a steering committee, and I have a difficult time imagining that chess endgame calculations would make it through, so don't hold your breath. But I have given some serious thought to how one would fully utilize a 4000 CPU cluster. The task is not so well suited to the "Map/Reduce/Collect" programming paradigm that is coming into fashion for large-scale computation, and so calls for some heavy hammering to bend it into shape.

Mind you, if there is a wealthy patron out there who declares "let me build you a supercomputer to compute these tablebases and give them to Anand so that he is better equipped to defeat Kramnik (or vice versa)" I would jump at that chance. Anyone have connections?

john

[jkominek]

The weekend is over now, which means EGTB work must fall into hiatus until next Saturday. Before I duck away, though, let me post the stats files for all 35 5-1 pawnless tablebases. Again, these are tentative results, so please treat them as such. (Not that there is strong reason to believe they are erroneous, but verification awaits -- and bugs happens.)

The longest loss by btm remains at 34 move. More than one combination shares this honour. And curiously, both kqbnnk and kqrbbk possess exactly (and only) 1 draw when white is on move.

Indications are that the pawnless 5-1 set will compress to about 15 GB total.

john

[vb4]

Hi John,

Just doing a followup to see if you had begun the generation of the 5-1 egtb's for the postions containing pawns.

Thanks,

Les

[jkominek]

Hi, thanks for your interest.

Efforts have been diverted recently, as anticipated.

As of my last checkpoint I can report progress on pawnfull 51p, though it is not finished work. The sets kqqqpk, krrrpk, kbbbpk, and knnnpk have been generated, but not verified, so I'm going to sit on the tbs files until that's performed.

All of the 51 pawnless files have been verified for consistency by the way. Meaning: the DTM of each position is compared to the min/max of the successor positions (depending on whether white or black is on move). The two numbers must agree in all cases. This is not a guarantee of correctness (the checkmated positions that seed retrograde analysis could be wrong), or of completeness (the move generator could skip legal moves). But since this work is an extension of Nalimov's tbgen, and I haven't messed with the move generator in any significant way, the pedigree at least is good, if not my defacement.

Moving forward, I can see extra diligence is required to ensure correct treatment en passant (Darn that rule!).

Did I mention other bothers such as an impending shortage of hard disk space? So it goes.

john

[ernest]

Hi, thanks for your interest.
.............
john

Hi John,
What is the difference between your 5-1 generation and Martin Kreuzer's one (1 year ago)?
http://kirr.homeunix.org/chess/discussi ... f=6&t=1938

Can you compare (check) your results with his?

[jkominek]

Good point. Those were generated by a program called FEG - "Final Endgame Generator" - a tool from the old ChessMaster suite. (ChessMaster was commercial but the FEG tool was free, though closed source.) Much of the discussion in these boards revolved around converting the statistics files from FEG for Nalimov, since the two are not equivalent. Suggestions were made but no one, as far as I know, wrote a statistics converter (to the dismay of Les). However if I remember correctly they differed only in pawnless configurations. For pawnfull positions they are the same? I'll follow up on that.

john

[vb4]

Hi John,

Thanks for your response. Out of curiousity would you say the convergence of a solution in these 5-1 pawn or pawnless positions converge quickly to a solution? Secondly would you expect there to be a big difference of the convergence onto a solution between the pawn and pawnless positions?

I am very thankful that you have been kind enough to battle this thing! As far as your running out of storage <S> I dont have any answers for you there.

I will keep an eye for your posts.

Thanks John,

Les

[jshriver]

If there is a linux port or if I can compile it, I'd be willing to generate some of the 5-1 tables and host them on my site.

Let me know
-Josh

[jkominek]

That's a nice offer Josh. I have 70 GB of free space. With some shuffling I should be able to manage. Though, I like the idea of adopting you as a beta tester if you are up for that -- once the potholes in the code have been filled, that is. Progress has slowed in January as I've needed to attend to higher priority jobs, so at this moment I can't offer an ETA.

john

[jshriver]

Well I have about 800gigs free on my main desktop, and a bit more on my server. I also have a P4 3ghz w/ HT available, a AMD64 dual core 3ghz machine available, and a 2ghz machine as well that I could let burn for 5-1.

So the CPU is here, and time spent doing something useful is better than time wasted idle Just need the code. Heck I'd even be willing to put Windows on 2 of my non desktop/server machines to get the 5-1 done (I have a win2k license and win xp license sitting idle).

BTW I can also host the resulting dataset. My uplink sucks, but once it's on the server it's on a nice pipe.

Let me know
jshriver<AT>gmail.com

[guyhaw]

May I catch up with the 5-1 situation.
At the last count, quite a lot of these were done, in I think FEG format, and close-out seemed possible.
I am interested in the usual stats:
- number of positions at (what?) maxDTM depth
- number of zugs (would all be of Type 1 ... wtm =, btm loss) and number of zugs at (what?) maxDTM depth
Of course, the number of maximal positions is rather affected by the fact that the depth count is in winner's moves rather than plies, and this really shows up when there are lots of positions at a shallow maxDTx depth - but that's the state of the art at the moment.
g

[jkominek]

Hi John,
I will keep an eye for your posts.

This is an eyeball alertness quiz.

Attached are two archive files. One with Nalimov-style stats files for the 35 pawnless 5-1 endgames. The second has four pawnfull stats files, for positions of the form kxxxpk, x={b,n,r,q}. All of these files have been cross-validated against deKoning's FEG program. This means: all the counts are identical except for broken and drawn. Such values are not reported in the FEG format.

In a later post I'll describe the cross-validation in some detail. It's easy for positions with pawns; not so easy without.

Out of curiousity would you say the convergence of a solution in these 5-1 pawn or pawnless positions converge quickly to a solution?

A a general rule, the more unbalanced the material the faster the convergence. I love kqqqqk.

Secondly would you expect there to be a big difference of the convergence onto a solution between the pawn and pawnless positions?

Games with pawns converge more slowly. Or interpreting your question in a different way, is the potential of a pawn promoting to a queen more valuable than an already available piece? Clearly kqqqqk is going to checkmate faster than kqqqpk (on average), but what of the others? The stats files argue that it is better to have the piece.

I am very thankful that you have been kind enough to battle this thing!
Les

It's more of a battle than is generally realized. The effort requires perfect results, but the size of the data slopping around increases the probability of random errors from negligible to tangible. I've moved files across network storage only to find that the md5 checksum did not confirm. Any movement, compression or decompression requires a sanity check. I'm now planning of linking the md5 library into my tbgen2 program itself, so that a checksum is generated both before and after the data is written to disk. And another one after the data is compressed.

(I smile at suggestions that we should be able to "just solve" chess now that Schaeffer has solved checkers. Uh, no. Not even 5x5 minature chess is currently within reach. This is no fault of Schaeffer -- at least not directly.)

Currently in progress are kxxypk positions. These consume more memory than the largest computer I have access to, and so I'm working on implementing pawn slicing to bring the requirements down within manageable limits. This has its own complications.

As a last point, I want to make clear that these files supercede my earlier posting. Some of those files have errors. Even if I can't do a position-by-position comparison, cross-checking against the FEG results has proven instrumental in detecting and eliminating bugs.

john

[vb4]

Hi John,

Thanks for your update! I am glad their are a few of us still interested in the 5-1 pawn and pawnless egtb's. I am studying these egtb's and need to have a complete set of perfect information on each EGTB or I cant includde it in my study obviously. Keep me posted as things progress, good work!!

Thanks,

Les

[jkominek]

Keep me posted as things progress.

My attention has been directed elsewhere for the past month, but recently I've been able to squeeze out a few more pawnfull tbs files. Here are six new ones.

prev: kqqqpk krrrpk kbbbpk knnnpk
new: kqqrpk kqqbpk kqqnpk kqrrpk kqbbpk kqnnpk

These have been cross-checked against the FEG stats without discrepancy (excepting draw counts).

By next weekend I think there will be another six available.

john

[vb4]

Hi John,

I just came across your update regarding the pawnful 5-1 egtb's. I am thrilled that you had additional time to generate them. I would think that they probably take less time to generate then a less inbalanced position ie 3-3 etc. I will keep checking in on your progress.

Once again thx John,

Les

[jkominek]

Here are the next six pawnfull stats. That makes for 16/35.

prev: kqqqpk krrrpk kbbbpk knnnpk
kqqrpk kqqbpk kqqnpk kqrrpk kqbbpk kqnnpk
new: krbbpk krnnpk kbnnpk krrbpk krrnpk kbbnpk

Lopsided positions are faster with my program, definitely, because they converge more quickly and there are more opportunities for like-men reductions. Curiously, FEG, which I'm using for verification, is the other way around. It can run faster on balanced positions than unbalanced. I believe this is due to the fact (or appearance of) that it computes in an unfolded index space; only in the finalization stage are the symmetries folded down.

john

[izesk]

Hi jkominek!

Could you please tell me when are you going to share in eMule at least verified 5-1 tablebases.
Thank you very much.

[jkominek]

Hello izesk!

Thank you for your interest. It's an honour to have someone register with the forum just to ask me a question.

I suppose the honest - if wiggly - answer is "as soon as I can." I'd like to start tackling 7-man tables by mid-summer. Figuring backwards that means finishing 5-1 by, say, June. But since this is an intermittent, after regular-work effort, we're reluctant to commit to a detailed schedule. Who's "we"? Why the long lineage of Thompson, Edwards, and Nalimov. You think I'm going to mess with that great tradition?!

Let me shift the angle from when to what. I have some hard criteria to respect, plus preferences. I'd prefer to release the entire 5-1 set of 70 tables in whole. I'd like to release them with corresponding bitbases, though this is a lower priority. I'd also prefer to have one or two beta testers generate the tables independently and get identical results. (It wouldn't hurt having multiple share points either.) Of course passing verification is mandatory. This means an internal consistency check, and cross-comparison to FEG. Ideal would be a one-to-one comparison, but in absence of that I'm using the stats signature. It's also possible to extract the first hundred or so positions at each DTM depth from the FEG tables -- I'd like to use these as a quality check, but haven't yet. Extracting sample max positions and mutual zugs would be nice for completeness (read: for guyhaw). Again in the mandatory category: a minimalist program for accessing the tables, plus sufficient documentation to let other programmers use it.

Regarding the generator, the next stage are positions with two pawns on a side. tbgen2 implements pawns-first indexing, which means that when the pawns fixed on the board the corresponding endgame positions occupy a contiguous block in the tablebase. This is the way forward, I believe, but it has necessitated a substantial reworking of the original tbgen program. There remain issues to iron out.

john

[Kirill Kryukov]

Again in the mandatory category: a minimalist program for accessing the tables, plus sufficient documentation to let other programmers use it.

Yes this is important, good to hear that you are planning it. Releasing tables without access code will be like pkunzip.zip. In ideal case I'd like to see probing code (free and open source) that can access both Nalimov and your tables via the same API.. Or may be bitbases too.

[jkominek]

It's easy to agree that that would be desirable. But have you noticed how long it takes (Wilhelm) to load the 6-man tables -- and how much memory the indexes consume? A machine with 2GB is barely enough. What the hey? This madness has got to end!

jk