Some DTM50 work.

[galen]

I've been working for a few months on building DTM50 tables, with up to six men. Since I was inspired by a thread here (which I cite!), and since this is probably an interested community, I'm posting a draft write-up of my results so far. I also see that in the interim another thread has been posted here with some 5-man results, which at cursory glance look consonant with my own (I'll give 'em a closer look later).

Here's my current draft: http://galen.metapath.org/egtb50/

Best!

[Kirill Kryukov]

Hi galen, thank you for sharing your very interesting results!

Can you verify your tables against Kronsteen's ones?

Do you think you could compute all 6-piece tables using 64 GB or RAM?

Are you planning to release the generator, the tables, or to make a web-interface?

Welcome to this forum!

[syzygy]

Here's my current draft: http://galen.metapath.org/egtb50/

Some available tablebases attempt to incorporate R50 in various ways, but in my view none are satisfactory. The most common is to add a "DTZ50" metric, which counts down to an irreversible move. It's not quite right, however, as it fails to account for which player made the last irreversible move, and so can be off by a half-move.

I think the DTZ50-metric is generally understood to refer to the number of plies, which completely solves this one-off problem.

Of course in practical implementations a table might still store the number of moves if all distances are smaller than 100 ply anyway.

[galen]

Hi, thanks for the welcome!

Can you verify your tables against Kronsteen's ones?

I'll do this soon. Confirmation is a beautiful thing.

Do you think you could compute all 6-piece tables using 64 GB or RAM?

Many more of them, certainly, but all? I'm sure not. What enabled me to tackle any at all were the drawishness and symmetries of those minor piece match-ups. When a position is uniformly drawn, all one has to record in memory is that it's a draw. But when someone can win, one must record all sorts of data about the depth to mate for each possible depth to zero, as well as metadata to index this table, which, even compacted as it is, runs about 10-15 bytes per position. A match-up with more wins also means more winning lines, so probably more possible depths and thus more bytes per position. Well, there are things that could be done to curb this, but still I'm guessing a few hundred gigabytes for an arbitrary one.

And of course the symmetries.... E.g., restricting to opposite-squared bishops is a factor of 4 versus two arbitrary pieces.

I'm almost embarrassed to admit that I've been working under only 8 GiB (my plan has been to not buy more memory till it's time for a new machine). With some extra byte-packing, I've been able to knock down bishop pair vs. bishop and knight, which has been added to that draft (edited accordingly). I've also tackled most of queen versus three identical minor pieces, though it's not written up yet. I tried rook and knight vs. bishop pair, but ran out of memory; I suspect even 12 GiB might be enough for that. (If the bishops are on the same color, it's likely far too undrawish.)

To be concrete, once I hit about 500m positions with wins I was all but out of memory. Even in a "drawish" match-up, a decent % of positions are wins because of an immediate capture or the like. An arbitrary pawnless match-up has about 20 billion positions (removing D_4 symmetries), so there's a big gap.

Are you planning to release the generator, the tables, or to make a web-interface?

Web interface: Probably not. That would be a whole additional project, and it would further involve hosting many gigabytes of tables. I haven't written probing code, either; in fact, the tables are stored as big ASCII files, and loaded in in this form as needed (which isn't efficient, but a drop in the bucket compared to the whole computation).

The tables: Well, I suppose I could collect them and upload them somewhere. They are large, of course. Also, I'm happy to share any that are of interest. I've even generated some involving various "fairy" pieces, e.g., wazirs.

The generator: Ah, yes, the code. I would definitely like to put it together and put it out there, but it's in a chaotic state right now and not exactly user-friendly. Switching between modes involves commenting and uncommenting out blocks of code and recompiling. There are tunable parameters that must be calibrated for best memory usage, and this would have to be documented. And, there's many incomplete layers of refactoring; when I started out, two knights vs. pawn was the holy grail and I didn't think I'd go further, but I kept adding more and more cases on, and it's not all cleaned up yet. Anyway, making it presentable, and dare I say actually useful, would be an effort. So, yes I'd like to, but it probably won't be soon.

[galen]

Here's my current draft: http://galen.metapath.org/egtb50/

Some available tablebases attempt to incorporate R50 in various ways, but in my view none are satisfactory. The most common is to add a "DTZ50" metric, which counts down to an irreversible move. It's not quite right, however, as it fails to account for which player made the last irreversible move, and so can be off by a half-move.

I think the DTZ50-metric is generally understood to refer to the number of plies, which completely solves this one-off problem.

Of course in practical implementations a table might still store the number of moves if all distances are smaller than 100 ply anyway.

Hm, well I had checked out in particular chess.jaet.org, where for example it appears to be indifferent between the top two moves here:

http://chess.jaet.org/cgi-bin/dtx?fen=8 ... %2F8%2F8+w

I guess I don't know how common this problem is. I looked at your tablebase code on github (which is very nice work, by the way!), and I see you handle this correctly. So, I see your point; I'll revise my text to reflect that not all DTZ50 tablebases are created equal.

[galen]

Can you verify your tables against Kronsteen's ones?

I've now gone through all the claims in Kronsteen's post, and verified them against my table as all correct, modulo a few nitpicks, which I'll post in the other thread.

[kronsteen]

Hi,
Sorry to have been so long to reply. I'm extremely busy nowadays...

First of all, I shall congratulate galen for his DTM50 work, and above all for his blog that perfectly explains what DTM50 is, what is the influence of the move counter and how two positions identical on the board with different move counters can lead to completely different winning lines and outcomes. I intended to write such a blog myself but never found the time to do it. I strongly hope that such information will help the chess community understand what is the true nature of DTM50, realize that DTM50 tablebases are a realistic prospect (heavier than other tables for sure, but still manageable) and perhaps that the future of EGTs lies in 50-move rule compliant tablebases, the trend having begun with syzygy's DTZ50 tables that seem to get a lot of popularity. I see the medium term future with a possible release of DTM50 tables up to 5-men and even up to 6-men if somebody writes the generator, with a strong possibility of building a full pack DTM+DTZ50+DTM50 that should match everybody's needs (fastest mate, fastest engine access for ELO performance, 50 move rule on / off...). I expect a 6-men DTM50 full set to be around 3-4 TB with proper compression, meaning that it could fit in a cheap single HDD.

For now I'm going through galen's findings and claims and check them against my own DTM50 tables. I've checked the first part up to knnkp and everything matches my tables exactly. I therefore agree with all « big » knnkp findings, the maximal position at mc=0 (mate in 112), the maximal position at mc>0 (mate in 128, mc=4 or 5) and the position with the most (26) different mating distances according to different MC values. I've also made a fast read of other DTM50 5-men galen's results (kbbkn, krbkr, kqpkq...), all of them are looking good. I'll check them soon.

Galen, perhaps you are interested in checking our DTM50 EGTs against each other. I won't have the time to do it myself, but I could try to send you my tables one way or another (Currently I've built all 3-men, all 4-men (including kpkp with en passant) and all 3vs2/2vs3 with 0 or 1 pawn. All tables are 15 GB in zipped format, several hundred GBs uncompressed. The indexing scheme is extremely basic and easy to understand). I could also send the generator sources which are of course much smaller but I'm a c++ newbie and my code is slow, harsh and very unfriendly to use so I wouldn't recommend it.

Best and looking forward,

k

[kronsteen]

(continued) checking galen's results :

2 bishops vs knight : same results – only a typo in 2nd position (PC=80 or 81 instead of PC=79 or 81)
rook+bishop vs rook : results for the 2nd position (Kb4 Rh3 Bg8 / Kb1 Rf6) are off 1 move : My TBs give mate in 17 for PC up to 67, in 19 for PC=68-69, in 20 for PC=70-73, in 21 for PC=74-75, in 22 for PC=76-77, draw for PC=78+.
queen+pawn vs queen : the 1st position (Kg7 Qc3 Pd2 / Kh1 Qh4) is also a win in 138 for PC=96

Everything else about these endings is OK, including positions with most different mate lengths and positions with highest cost of PC.

Galen also posted positions 4vs1 and 3vs2 with 2pawns. I haven't built these TBs for now but they're in my plan - completing all 5-men for the end of the year

[galen]

Hi Kronsteen, great to have you on this thread!

First, the errors you pointed out: I rechecked those two positions against my tablebases, and they agree with your corrections. I clearly made a few off-by-one errors writing up the results. Thanks very much for your careful checking! And, I'm glad that the tables themselves are (so far) corroborated.

I agree that there is a future for DTM50 tables, and that our work should prove to the chess community that it really can be done. DTZ50 tables such as syzygy's excellent generator can be efficient and will find a win if a win there is, but there will always be chess enthusiasts clamoring to know exactly how far off a mate is, and bulkier tables such as ours are in general needed for the answer.

I haven't yet built any 5-man tables with two or more pawns. My handling of pawns and promotions right now is pretty unsatisfactory and I'd like to rework it. But, I got more interested in pushing into 6-man territory than continuing to wrangle with pawn logic. Plus I've been tinkering with improving time and memory usage; for perspective, my most recent run, of kqrkr, took a little under 3 hours.

Of course, memory is the real limitation. I could pretty much right now build arbitrary 6-man pawnless non-5v1 tables with the existing codebase, except for the tiny wrinkle that it would require a few hundred GB of RAM to do it.

I don't have as much spare time myself at this moment (in that I'm travelling most of Jan/Feb). But, if we want to try comparing tables, maybe it'd be best to start with one or two-- perhaps you can upload to a hosting service-- and I'll see what I can figure out. Although, since you've checked your results against my text, it's looking pretty positive.

Eventually, I may focus more on getting the code and the table-probing more user-friendly and structured. The code in particular is awfully hairy right now.

[kronsteen]

.

if we want to try comparing tables, maybe it'd be best to start with one or two-- perhaps you can upload to a hosting service-- and I'll see what I can figure out. Although, since you've checked your results against my text, it's looking pretty positive.

Since our TB results have matched exactly so far, there is every reason to believe that most of our results, if not all, should also match. Therefore I think that we can readily set as a goal the full cross-verification of all TBs that have been generated by both of us.

My TBs are in a raw binary format that is easy to read so it should be immediate for you to build a code that checks them against yours. I would recommend kbbkb for a first try. This TB is small (6Mb packed) due to the extremely drawish nature of the ending, but has positions with multiple DTM50 values (up to 3) so it is a good choice for a first test in real size. If you are OK with that, I'll send you the TB with a checksum and a 'readme' in a PM. Other TBs will require using some big file transfer service such as dl.free.fr, but this shouldn't be much of a problem.

[kronsteen]

Of course, memory is the real limitation. I could pretty much right now build arbitrary 6-man pawnless non-5v1 tables with the existing codebase, except for the tiny wrinkle that it would require a few hundred GB of RAM to do it.

Maybe the solution to this problem is to write down the results of each iteration on disk, and to keep on RAM only the information needed for next iterations. This isn’t required when there is plenty of RAM such as in my case for now (5-men DTM50 generator running on 16 GB of RAM) but will certainly be a key issue if the idea is to build a 6-men DTM50 generator capable of running on a standard PC equipped with 64 GB or even 32 GB of RAM. I haven’t fully assessed the problem for now, but I believe that a DTM50 generator using a standard backward propagating algorithm such as mine (find losses in 0, then wins in 1, then losses in 1, then wins in 2 etc…) needs only 2 bytes per position to be held in RAM for each iteration : the highest PC at which the position is known to be a win or loss (whatever the exact DTM50 values are for all lower PC values), and the lowest PC at which the position is known to be a 50-move rule draw (the status of the position being unknown between these values of PC). Illegal and drawn positions at PC=0 will require even less than 2 bytes. A pawnless 6-men ending of the most complicated type (kqnkrb) has 12 G positions so 24 GB of RAM should be sufficient, and for pawnful 6-men the most complicated type (kqpkrb) has 36 G positions so 64 GB of RAM should be enough, and there is also the possibility of cutting such endings into pawn slices which should cut down the RAM requirements by a factor of 6.

[galen]

My TBs are in a raw binary format that is easy to read so it should be immediate for you to build a code that checks them against yours. I would recommend kbbkb for a first try. This TB is small (6Mb packed) due to the extremely drawish nature of the ending, but has positions with multiple DTM50 values (up to 3) so it is a good choice for a first test in real size. If you are OK with that, I'll send you the TB with a checksum and a 'readme' in a PM. Other TBs will require using some big file transfer service such as dl.free.fr, but this shouldn't be much of a problem.

Hey, sorry about the delay, just starting to get back to this now. Sure, go ahead and send me the files and I'll take a look. kbbkb is a good candidate.

I'll also include a link to my expanded output file for that case, which should be interesting especially for lurkers here. I tried to attach it, but at 12 MB it must've been too large, so I used a random hosting service. It gives the mate length and optimal move(s) for each non-drawn position and count. It's an xz-compressed text file and assumes all D4 symmetries; the king is always in the a1-a4-d4 triangle.

kbbkb: http://s000.tinyupload.com/?file_id=351 ... 2318375461

And, I'll throw in the same for kpkp, now that I got (I think) en passant working. It uses bilateral and color symmetries. Maybe you can tell me if it looks about right:

kpkp: http://s000.tinyupload.com/index.php?fi ... 7081748408

[kronsteen]

Sent you a pm with my kpkp and kbbkb DTM50 TBs

[h.g.muller]

Maybe the solution to this problem is to write down the results of each iteration on disk, and to keep on RAM only the information needed for next iterations.

Indeed, this seems the way to go. If the working set consists of 2 bytes per board position (one byte for each side to move), the bytes could hold the DTM in full moves.

For efficiency it would be nice if one would also keep track of the 'win front'. This could be stored as a (sparse) bitmap, and possibly even compressed. One would need two such bitmaps: one to indicate the positions from which we should generate retro-moves, and the one we are building for the next iteration. From a btm position we would generate retro-moves, and if they lead to positions that have a higher DTM than our own + 1, we would lower their DTM to ours + 1, and make it part of the new win front. From a wtm position the retro-moves would always lead to btm positions with higher DTM, but we would have to verify them with forward moves to find the largest DTM they lead to (which could be 'undecided'), and set their DTM to that. If that lowers their DTM, they would also be added to the new win front.

At the end of the iteration, the old win-front bitmap could be discarded, and the new win-front, before taking its place, would have to be traversed again to find the DTM of all positions in it, and flush these to disk.

One would iterate by DTZ (which, unlike DTM, needs to be measured in ply). So one would start retro-moving from all checkmates and un-capturing from all won positions in successor EGTs in the first iteration, to get all positions with DTZ=1 (ply), i.e. which can be won even when the ply counter equals 99. The parents of checkmates would of course get DTM=1; those before a conversion would get the DTM of the position they lead to in the successor EGT (+1 if they are white moves).

[galen]

Of course, memory is the real limitation. I could pretty much right now build arbitrary 6-man pawnless non-5v1 tables with the existing codebase, except for the tiny wrinkle that it would require a few hundred GB of RAM to do it.

Maybe the solution to this problem is to write down the results of each iteration on disk, and to keep on RAM only the information needed for next iterations. This isn’t required when there is plenty of RAM such as in my case for now (5-men DTM50 generator running on 16 GB of RAM) but will certainly be a key issue if the idea is to build a 6-men DTM50 generator capable of running on a standard PC equipped with 64 GB or even 32 GB of RAM. I haven’t fully assessed the problem for now, but I believe that a DTM50 generator using a standard backward propagating algorithm such as mine (find losses in 0, then wins in 1, then losses in 1, then wins in 2 etc…) needs only 2 bytes per position to be held in RAM for each iteration : the highest PC at which the position is known to be a win or loss (whatever the exact DTM50 values are for all lower PC values), and the lowest PC at which the position is known to be a 50-move rule draw (the status of the position being unknown between these values of PC).

I agree that an idea like this of saving partial results to disk has real potential. There would likely be a cost in speed and disk access, possibly large, but it would make it possible to build larger tables with existing RAM. I've mulled ways of doing this, and my thoughts are a bit different from your proposal. Essentially, each iteration would produce a "best achievable in n plies" for each n. To generate the next iteration, we only need to store in memory the best so far; longer mates doable in fewer plies than we have available are no longer relevant, and can be left on disk. (This might be similar to what h.g.muller meant by the win front.)

My current code combines two plies per full iteration, I think it's called leapfrogging, so we might prefer to store two mate lengths per position. I'm a bit hazy on how all the details will work out. Since I don't have 40 GB lying around, I haven't tried it, even as a proof of concept. My current method uses 4 bits per drawn position and uses symmetries aggressively, which allowed me to complete (e.g.) kbnknn and knnnkr in my paltry 8 GiB.

A pawnless 6-men ending of the most complicated type (kqnkrb) has 12 G positions so 24 GB of RAM should be sufficient, and for pawnful 6-men the most complicated type (kqpkrb) has 36 G positions so 64 GB of RAM should be enough, and there is also the possibility of cutting such endings into pawn slices which should cut down the RAM requirements by a factor of 6.

I've found slicing by pawn position indispensable. There are three ways to do it: by file, by rank, or by square. I haven't tried the first, but by rank cuts a factor of six, which one would expect to be sufficient if the 4-times smaller promoted-to ending was doable. However, I've also done a few slicing by square, and recently had to do it again to build the biggest monster yet, kbbknp for w+ and opp bishops, where I could barely get each square in memory. I'll be writing up results soon, but here's the deepest mate:

8/K2pk2n/7B/8/8/8/B7/8 b - - 0 1


Black plays 1. ... Kd6, and White mates in 151. There is also a position where White mates in 159 if PC=2, that is, if White squandered only a single move.

[h.g.muller]

I would always slice by square. Why not use the extra reduction if you can?

[galen]

I would always slice by square. Why not use the extra reduction if you can?

Well, if you don't need it, you don't need it. For instance, kpk takes maybe a megabyte; splitting it into 40 kb chunks would be pointless, and there is time overhead and code complexity associated with slicing. Splitting kppkp into 25,944 parts would be similarly excessive, and take much longer to run, at least with my code. In general, I have been slicing only as much as needed to fit into memory, and in the "typical" case by-rank should be appropriate.

[h.g.muller]

My argument would be that in the end, to do the biggest thing that can be done, you would need that code complexity anyway. And once you have it, you might as well use it for the cases that did not really need it, rather than writing specialized code for that.

I don't see why slicing would slow things down. Basically it is just doing the same things in a different order. And the smaller your working set, the faster the program would typically run. Going to 4KB slices might seem unnecessary when you have 16GB RAM, but it means you can run from the L1 cache rather than from RAM.

[kronsteen]

Ok, I think I got it. Our ideas are different because my generator back propagates DTM when galen's (and also the one h.g. muller has in mind) back propagates DTZ (a good sign being that my generator and galen's one have totally different designs and up to now have produced results that match exactly). The reason why I made this choice is that I thought back propagating DTZ would require full pawn slicing, which I found too messy to implement : for example, before starting to evaluate a position with a wp on a6 (wtm), you need to know the DTM50@PC=0 value for the successor position with the wp on a7 (btm), and you'll have that only after a full 50 iteration cycle. Back propagating DTZ is done on reversible moves only, and pawn moves must be treated just like captures and promotions, i.e. moves leading to a "successor ending" whose results must have been computed before and stored in a separated file (or buffer) that is used as entry data for the iteration cycle. Am I correct ?

Nevertheless, back propagating DTZ certainly works, and I think that both of you express the same general idea (with different words) about how to design a RAM efficient DTM50 6-men generator based on DTZ back propagation. I also think that it works, or at least it sounds like good.

8/K2pk2n/7B/8/8/8/B7/8 b - - 0 1
Black plays 1. ... Kd6, and White mates in 151. There is also a position where White mates in 159 if PC=2, that is, if White squandered only a single move.

Wow. Max DTM for kbbknp is "only" 131 – looking at this, who ever still thinks of the 50 move rule as a long win sterilizer ?
If you target 6-men endings with 2 white (or black) bishops (in order to cut down the size by 4, doing the part with opposite coloured bishops only), maybe you can also try kbbpkr.

[galen]

I don't see why slicing would slow things down. Basically it is just doing the same things in a different order. And the smaller your working set, the faster the program would typically run. Going to 4KB slices might seem unnecessary when you have 16GB RAM, but it means you can run from the L1 cache rather than from RAM.

I suppose you could argue it's a flaw in my implementation, but yes as things stand it slows things down a great deal. I'll give one example. To compute (e.g.) knkp, it is necessary to load from disk and uncompress into memory all "underlying" tables, such as knkn, krkn, kqkn, kqk, krk, etc., which are used to populate the target table. When not slicing or slicing by rank, all or at least the four-man tables only have to be loaded once each, but if by square it has to be done repeatedly. I suppose one countermeasure would be to keep the uncompressed tables in memory, or uncompress only part of the underlying tables (somehow), or pre-slice the underlying tables, or who knows, but (e.g.) the first solution means more resident in RAM, and with multiple pawns it can become complicated to keep track of what tables to keep around, what order to do the subtables in to minimize storage, etc.

And I really see no gain for all this. Memory access has never so far as I can tell been any kind of bottleneck (in re the L1 cache), and at any rate I've got a bunch of ideas for possible optimizations bouncing about in my head which I expect would yield far more benefit than trying to untie the above knot.

This is just a perspective from my experience, so your mileage may vary. Have you built generators of your own? Maybe the way you did it avoided the above problem completely.

My argument would be that in the end, to do the biggest thing that can be done, you would need that code complexity anyway. And once you have it, you might as well use it for the cases that did not really need it, rather than writing specialized code for that.

My argument is that pawnful tables are 4x the size of pawnless ones due to the fewer symmetries, so if one was able to build the underlying table resulting from promotion in memory, one should be able to build something with 1/6 of 4x the size in memory (slicing by rank). This heuristic went wrong in one case (kbbknp for w+), but it was easy to switch to by-square generation for that case. With two pawns, it is about 1/9 the size of an equal pawnless table slicing by rank, so one would predict that this measure would never be necessary.

[galen]

Ok, I think I got it. Our ideas are different because my generator back propagates DTM when galen's (and also the one h.g. muller has in mind) back propagates DTZ (a good sign being that my generator and galen's one have totally different designs and up to now have produced results that match exactly). The reason why I made this choice is that I thought back propagating DTZ would require full pawn slicing, which I found too messy to implement : for example, before starting to evaluate a position with a wp on a6 (wtm), you need to know the DTM50@PC=0 value for the successor position with the wp on a7 (btm), and you'll have that only after a full 50 iteration cycle. Back propagating DTZ is done on reversible moves only, and pawn moves must be treated just like captures and promotions, i.e. moves leading to a "successor ending" whose results must have been computed before and stored in a separated file (or buffer) that is used as entry data for the iteration cycle. Am I correct ?

Your description is close, and maybe more like it ought to be. I store all the lists of mates/cutoffs in the table, and when computing the value of a move I take the "meet" or "join" of these lists to compute the value so far for a position. When I'm slicing by pawn, I do something closer to what you describe, where every rank or square is a separate file, and a flag indicating slicing turns on various optimizations. I don't do any slicing for 4-man as of now (didn't need to, so didn't bother), and so I just iterate repeatedly till I get no new information on a pass. When I do slice, it roughly counts backwards through DTZ, but due to the two-ply-per-pass leapfrogging, and the fact that mates and captures aren't perfectly sync'ed up, it doesn't hew exactly to DTZ. Future work may require me to address this.

Nevertheless, back propagating DTZ certainly works, and I think that both of you express the same general idea (with different words) about how to design a RAM efficient DTM50 6-men generator based on DTZ back propagation. I also think that it works, or at least it sounds like good.

I'm increasingly tempted to put together a proof of concept for this idea, even if I won't be able to do much with it. Maybe next time I have a healthy stretch of free time. Also, I've found Amazon AWS instances can be rented with as much as 244 GB, so if I'm willing to spend a few bucks for science I could really go crazy. My code is now able to parallelize its iterations, so it would be a lot faster on a multcore setup if I don't have to worry about CPU overheating.

8/K2pk2n/7B/8/8/8/B7/8 b - - 0 1
Black plays 1. ... Kd6, and White mates in 151. There is also a position where White mates in 159 if PC=2, that is, if White squandered only a single move.

Wow. Max DTM for kbbknp is "only" 131 – looking at this, who ever still thinks of the 50 move rule as a long win sterilizer ?

Indeed! The longest DTM wins for endings like krnknn and kqnkrbn generally involve an extremely deep capture, followed by a quick win with the material advantage, so that the 50-move rule will collapse most of them. But those involving a pawn are a whole different beast, and deep wins like this where the pawn moves slowly down (or up) the board will I hope continue to appear.

If you target 6-men endings with 2 white (or black) bishops (in order to cut down the size by 4, doing the part with opposite coloured bishops only), maybe you can also try kbbpkr.

So, I should elaborate on my current constraints. I can only build 6-man tables that are sufficiently drawish (how drawish depends on how many symmetries and other reductions I can exploit), or that I can pawn-slice enough. This applies both to the table being built and any it depends on. So, for kbbknp and knnkpp for w+, I had to have kbbkqn w+, and so on, all of which are very drawish (since I am only considering White wins); White's winning chances are quite poor if Black manages to promote, especially with knnkxx, where White has little hope if Black has a piece (though e.g. even knnkqn was pretty large). But kbbpkr would require for starters kqbbkr, which is not drawish at all and well outside my reach; similar remarks apply to krrpkq, kqppkq, etc.

The next big ending I'm close to tackling is kqkbbp w+ opp bishops. I have kqkqbb, kqkrbb (another big one!), and kqkbbb, but haven't been able to get kqkbbn. I may find a way soon. Also, I'm mulling working with what I have to build a (probably very good) approximation to kqkbbp, as a sort of preview.

I have thought about trying to hook Nalimov tables to my generator, and then using existing DTM tables which are known to be 50-move safe. But this might be a big undertaking as I know next to nothing about the format, and it might not help anyway, since underpromotions such as to kbbnkr have to be considered and are very likely to be affected by the 50-move rule.

[kronsteen]

I have thought about trying to hook Nalimov tables to my generator, and then using existing DTM tables which are known to be 50-move safe. But this might be a big undertaking as I know next to nothing about the format, and it might not help anyway, since underpromotions such as to kbbnkr have to be considered and are very likely to be affected by the 50-move rule

I’m also wanting DTM in order to progress towards the future DTM50 TB format I described on the paper I sent you, and the easiest way by far for me is rebuilding the tables from scratch with a homemade DTM generator. Such a generator is very easy to write from a DTM50 generator (at least from mine, maybe it’s also the case from yours), runs faster, eats less RAM, produces TBs directly on the right format and needn’t to be run on endings that are not affected by the 50-move rule.

[guyhaw]

This is very interesting work featuring two relatively new innovations:

- multiple, ply-count-related, DTM50 depths per 'physical' position (pace e.p.), and
- the use of the functional programming language HASKELL (and only Joe Hurd has used an FPL (HOL) on EGTs before).


Just to correct some minor typos (as the move-lists seem not to have been copy/pasted from a valid pgn file):

- KQPKQ: '9. Ka6' should I think be '9. Ke6' and '72. ... Qb6+' should be '72. ... Qb7+'
- KBBKNN: the two capture moves are obviously incorrect. '26. Kxh1' should be '26. Bxh1' and '74. Kxb1' should be '74. Kxh7'

For KPPKP, Diagram 1 could usefully be reflected so that it coincides with Diagram 2 of KQPKQ after 1...g4" ... 5.e8=Q''''.

The KNNKP DTM50-mate in 112 ... and the kick-off of the 26 different lines from 8/p7/2N3K1/8/8/8/2N1k3/8 w would be welcome additions to the blog.

Thanks, and thanks in advance,

g

[galen]

This is very interesting work featuring two relatively new innovations:

- multiple, ply-count-related, DTM50 depths per 'physical' position (pace e.p.), and
- the use of the functional programming language HASKELL (and only Joe Hurd has used an FPL (HOL) on EGTs before).

Yeah, I'm a bit of a functional programming junkie. My undergraduate thesis was about FP, and my PhD thesis used computer code written in Haskell. A project like this involving giant tables really worked my Haskell chops. For example, there was no margin for memory leaks.

Just to correct some minor typos (as the move-lists seem not to have been copy/pasted from a valid pgn file):

- KQPKQ: '9. Ka6' should I think be '9. Ke6' and '72. ... Qb6+' should be '72. ... Qb7+'
- KBBKNN: the two capture moves are obviously incorrect. '26. Kxh1' should be '26. Bxh1' and '74. Kxb1' should be '74. Kxh7'

Yes, thanks, you are right about all of these! I generated all of these lines manually one move at a time, having to correct for symmetries in my head, so I shouldn't be surprised there are errors. I need to write code to automate this process so I can mass-produce more lines error-free. On my "to do" list.

I have a new draft up which fixes these errors and adds a new section on knnkpp. I have also generated kbbnkq for opp b's but not written it up, and hope to generate kqkbbp sometime relatively soon.

The KNNKP DTM50-mate in 112 ... and the kick-off of the 26 different lines from 8/p7/2N3K1/8/8/8/2N1k3/8 w would be welcome additions to the blog.

The latter may wait till I can generate the lines more efficiently; also, I don't want to bog the text down with too many long lines, so I might split off a separate page with heavier details if I keep adding more.

The kick-off is actually pretty simple: White plays Na5 for PC up to 52, and for the rest Kf5 or N6d4+ (it doesn't matter).