7-men EGTB Bounty

[syzygy]

We already have seen some long checkmates reported by Marc Bourzutschky. Yes they attracted a lot of attention. The result is that no one is working in this direction anymore, and we don't have any usable 7-men tablebases.

Interesting point of view! You could well be right.

I agree that speed and size advantages are not the most important points, but they may be considerable when choosing between 1 TB and 1.5 TB to download.

But the difference in size between DTZ and DTZ50 will not be close to a factor 1.5 at all. (Does anyone have statistics on the percentage of positions with DTZ/DTC>50 in typical 6-piece tables?)

Anyway, the decision between DTZ and DTZ50 can be made when the actual generation starts, unless the generation and/or compression code is for some reason limited in the range of values it can handle, in which case the choice is easy.

Btw, for the moment it seems more realistic to me to first aim for a (re)generation of all 6-piece tables using code that is open, efficient, uses sane indexing and ideally is prepared for 7-piece generation, together with a really good compressor that is specially adapted to tablebases.

Since the idea is to have 7-piece tables for practical play, should the format lend itself to access during search, or just at the root node? (And does anyone know what kind of storage devices will be available around 2025? )

[diepchess]

Good initiative.
As usual bad execution though.

Just one question: whose money and how much?
It doesn't take much to open up my format, if i'd be required to generate it all myself
that's another issue, especially the 6vs1 is total useless to generate

Here a cut'n paste when listing the entire set of 3 to 7 men including 5 1, 6 1 :

1500 kqqqbpk 0 175368329040 -- -- -- -- 0 0
1501 kqqqbnk 0 59792058480 -- -- -- -- 0 0
1502 kqqqbbk 0 29896029240 -- -- -- -- 0 0
1503 kqqqrpk 0 175368329040 -- -- -- -- 0 0
1504 kqqqrnk 0 59792058480 -- -- -- -- 0 0
1505 kqqqrbk 0 59792058480 -- -- -- -- 0 0
1506 kqqqrrk 0 29896029240 -- -- -- -- 0 0
1507 kqqqqpk 0 43842082260 -- -- -- -- 0 0
1508 kqqqqnk 0 14948014620 -- -- -- -- 0 0
1509 kqqqqbk 0 14948014620 -- -- -- -- 0 0
1510 kqqqqrk 0 14948014620 -- -- -- -- 0 0
1511 kqqqqqk 0 2989602924 -- -- -- -- 0 0
In total 1511 egtbs using 624494750822780 entries
egtb command (or help):

[diepchess]

Good initiative.
As usual bad execution though.

Just one question: whose money and how much?
It doesn't take much to open up my format, if i'd be required to generate it all myself
that's another issue, especially the 6vs1 is total useless to generate

Here a cut'n paste when listing the entire set of 3 to 7 men including 5 1, 6 1 :

1500 kqqqbpk 0 175368329040 -- -- -- -- 0 0
1501 kqqqbnk 0 59792058480 -- -- -- -- 0 0
1502 kqqqbbk 0 29896029240 -- -- -- -- 0 0
1503 kqqqrpk 0 175368329040 -- -- -- -- 0 0
1504 kqqqrnk 0 59792058480 -- -- -- -- 0 0
1505 kqqqrbk 0 59792058480 -- -- -- -- 0 0
1506 kqqqrrk 0 29896029240 -- -- -- -- 0 0
1507 kqqqqpk 0 43842082260 -- -- -- -- 0 0
1508 kqqqqnk 0 14948014620 -- -- -- -- 0 0
1509 kqqqqbk 0 14948014620 -- -- -- -- 0 0
1510 kqqqqrk 0 14948014620 -- -- -- -- 0 0
1511 kqqqqqk 0 2989602924 -- -- -- -- 0 0
In total 1511 egtbs using 624494750822780 entries
egtb command

Dam i wrote a lot of stuff here but somehow the forum can't handle cut'n pastes from my macbookpro and all text i wrote has gone.

[diepchess]

Ok let me try to rewrite what i had typed.

a) good idea to award money. Who is gonna pay for it?
b) do you realize that all 7 men in non-WDL format are like 624TB uncompressed which makes it against 200TB compressed.
non-WDL egtbs compress maximum factor 4.
This VERSUS WDL it'll be at most 5 TB or so. Though tough to manage now, it's possible to execute.
Storing the files at different tapes for example (white to move at tape X and black to move at tape Y).
c) generation of WDL versus non-WDL is not a problem at all. It's just more i/o load to the raid array.
This really isn't the problem. Instead of a 3TB array you need a 5TB array that's all.
the new harddrives are bloody fast. Getting a 5TB array is not so easy by the way.
You need raid10. Say 8 disks of 1 TB each gives a 4 TB array. EGTB generation is difficult to do in jbod or raid-5.
d) in creating engines there is less and less money nowadays. This was clear to many of us start of 21st century of course.
that has a big impact however for EGTBs also. They already influenced relative little games, nowadays they influence it
even less. Seldom you have a game that you win/lose/draw because you didn't have the right EGTB. The huge search depths
and improved evaluation functions have contributed to that a lot. For Diep i would guess it's 0.5 point in an event. Note that
Diep is a program that likes to exchange pieces. The rybka type clones do not exchange quickly, they keep their pieces on the board.
For those engines EGTBs is less relevant even. So improving the engine, if they have the time to work on their engine anyway,
has a priority then over EGTB work.

Ok now let's see whether this posts ok. Doh.

[diepchess]

The most improtant question is:

Do you want all 7 men WDL quickly, say within 1 or 2 years, or do you want to get all DTZ in 16 years from now?
Note 10 years from now implies that the harddrive sizes keep doubling in size quite a number of times.

It's possible to have say 4TB of storage now for some nerds.
Maybe even a raid-5 array just for storage of 7TB is possible, but that would be just 1 or 2 persons.
So not so relevant.

So all WDL's you CAN compress stored right now. It's just a generation type question.

the DTZ's however you need a minimum of 150TB of storage space or so. Let's assume 200 for now.

4TB is possible to achieve now. Let's assume a doubling in harddrive sizes each 18 months.

200 / 4TB = 50x

1.5 years * (log 50 / log 2) = 1.5 * 5.6 = 8.4 years.

Now that's really optimistic guys, as i have to see whether by 2017 we have at home drives of 50TB.
On paper it is all very well possible of course, if you look how fast storage has gone.

Yet it's a big discrepancy that nowadays we are busy and calculating in tens of gigaflops and gigabytes per second
bandwidth. Tens of GB's per second in fact.

Yet i/o speed is 133MB/s to a 1TB drive.
That's a big bottleneck for DTZ.

Vincent

[diepchess]

i/o requirements.

If you would calculate the 7 men at a todays machine with todays 3 gigabit bandwidth drives (effectively 133 to 150 MB/s).

How much i/o do we need to calculate it.

Let's assume DTC now and i'm just calculating a lowerbound. In reality it is factors more than below.

624 T entries
for each of the 50 passes we need : 1 lookup for every semi-legal move.
we need to calculate win and loss, so 50 passes for max / min
we need to write results.

Real rough estimate: 8 bytes per pass PER POSITION.
If you calculate more realistic you'll get even more horrified.

624T * 2 * 50 * 8 = 500Petabyte i/o

Now if you would do that at a single drive that gets 133MB/s that's gonna take a while.

500P = 500k T = 500M G = 500G M

==> 500G / 133 ==>

So that's 4 billion seconds.
A year has like 31.5 million seconds

4000 / 31.5 = 126 years

Sounds not too long to you?
Well remember it's a lowerbound. Reality is a lot more grim.

With WDL and raid10 things move a lot faster there. Really a lot.
Besides my dual opteron machine which has a raid10 array (note outdated old harddrives),
who has a raid10 array here of terabytes?

Who is willing to PAY to buy one?

So not convince his university to buy it, but buy it himself.

Wanting to solve the 7 men using non-wdl methods is quite madness. WDL is our only hope.

Vincent

[diepchess]

See my posting above. The question is not writing "a" 7 men generator. You need to write one that really optimizes everything for i/o bandwidth.
There is plenty of cpu speed, there is plenty of harddrive space to generate (storage is another issue even with WDL, as it's quite tempting
to store files uncompressed for faster generation speed). there is plenty of cores to do whatever idiocy.

Writing a really optimized EGTB generator for the 7 men with pawns is a very interesting task.
Make 1 or 2 mistakes and it takes 10 years longer to get the job done.

All that effort, how much elo does it bring?

Well what i do know is that such a machine needs its raid10 array at the disk itself. That means with a big array you're gonna burn effectively
nearly a kilowatt, as you need probably a 2 socket machine or so to speedup generation speed (CPU's are not *that* fast to keep up with
i/o speed).

Because of huge taxes here (in itself energy is not that expensive, in fact bigger companies get it 20 times cheaper) is 450 euro a month
to the energy bill. Now *that* is a big price. End of 90s i searched for someone to generate the 6 men using my software.
Found no one. If you google for it you might still find those postings back then in rgcc/CCC. Nalimov paid his own machines and powerbills.

That's why you guys use the nalimov 6 men.

Nowadays having no job as we speak there is more considerations.
What's needed is a bunch of cores and a 2TB raid10 array (mininum size for WDL generation).

Thanks,
Vincent

[jkominek]

Congratulations Kirill! You've started a thread so enticing it brought Vincent out of the woodwork.

The most improtant question is:
Do you want all 7 men WDL quickly, say within 1 or 2 years, or do you want to get all DTZ in 16 years from now?
Vincent

Exactly. What are the ambitions of "the community"? -- not that it speaks with a single voice of course. Perhaps kk's contest rules will stipulate a multi-metric generator. Eager users will churn out what they want, in the time frame they see fit.

All your advocacy for bitbases has an obvious rejoinder. Turn the clock back to 1995 and tell Eugene that his project is madness. What is different now?

jk

[Kirill Kryukov]

Just one question: whose money and how much?

Money of whoever will decide to donate. I personally will contribute a modest sum. How much the total will turn out will depend on how badly this world needs usable 7-men tablebases. Your guess is as good as mine.

The important point of this project is that those who really want to see the 7-men tablebases (like me) will have a way to make it appear sooner (without personally investing time to code the generator), rather than just wait.

It doesn't take much to open up my format, if i'd be required to generate it all myself
that's another issue, especially the 6vs1 is total useless to generate

In my understanding, at least one generated 61p set should be included with the generator, to show that the generator and probing code indeed work with 61p.

May be it's a naive idea, as I am not sure that a generated knnnnpk proves that the generator will handle kqrbnpk. Another possibility is to instead pay half of the bounty first, and another half after one year of successful maintenance. This way we may not need any precomputed tables, just the generator itself.

In any case the idea is that the majority of the tables will be generated by the community.

[Kirill Kryukov]

I agree that speed and size advantages are not the most important points, but they may be considerable when choosing between 1 TB and 1.5 TB to download.

But the difference in size between DTZ and DTZ50 will not be close to a factor 1.5 at all. (Does anyone have statistics on the percentage of positions with DTZ/DTC>50 in typical 6-piece tables?)

Anyway, the decision between DTZ and DTZ50 can be made when the actual generation starts, unless the generation and/or compression code is for some reason limited in the range of values it can handle, in which case the choice is easy.

I'm not sure if I am missing something, but you need at least 2 bytes to store a DTZ, and only 1 byte to store a DTZ50. It may contribute to the difference?

Btw, for the moment it seems more realistic to me to first aim for a (re)generation of all 6-piece tables using code that is open, efficient, uses sane indexing and ideally is prepared for 7-piece generation, together with a really good compressor that is specially adapted to tablebases.

Since the idea is to have 7-piece tables for practical play, should the format lend itself to access during search, or just at the root node? (And does anyone know what kind of storage devices will be available around 2025? )

Yes, this is an important question. To find the right balance between compresesion strength and the speed of random access. I think that access during search is a very important use.

Perhaps two formats can be defined in the requirement:

A. "archival" format - compressed as much as possible, a single access is still feasible without decompressing the whole file. (Say in a few seconds). This format is good for file exchange.

B. "search" format - larger than "A", but allows for a relatively fast probing.

In this case the probing code will be required to automatically use whatever of two formats is present. Also a separate program will be needed that converts between the formats.

Finding a good compromise between the two (fast access, small size) would be ideal, if possible.

[Kirill Kryukov]

4000 / 31.5 = 126 years

Sounds not too long to you?
Well remember it's a lowerbound. Reality is a lot more grim.

If 126 CPU years is the measure, then I'd estimate at most 10 years before completion, assuming the storage is available. You are underestimating the community, I think.

I personally feel that WDL would be harmful, as it would distract our attention from DTZ, draw resources, and slow down the generation of the really important DTZ (or DTZ50) tables.

It will be really easy to convert the DTZ50 tables into the WDL tables, if someone will need it, but not the other way around. So I think that DTZ50 generator should have priority at the moment.

[Kirill Kryukov]

Congratulations Kirill! You've started a thread so enticing it brought Vincent out of the woodwork.

Easy to do - just post a thread with the word "money" in it.

[guyhaw]

Kyrill has a good idea, which if I may I will generalise to "How can we re-invigorate EGT generation?"

7-man EGTs is an obvious goal, but there are other goals and many have been mentioned implicitly above:

- EGTs to the DTR/DTZR, DTZ or DTZ50 metrics
- EGTs including positions with castling rights (can be simply added now: there are no moves to positions with increased castling rights.)
- more soundly parallelised code [there are question-marks about EN's code here]
- better software for managing and 'booting up' EGTs: do we need them all checking before the engine is prepared to start?
- better software for mining EGTs [WILHELM is no longer developed, CQL is difficult to use]

What exists now?

Marc Bourzutschky produced a code which produces DTC, DTM, DTZ and DTZk EGTs and I've used it. It is supposed to produce DTC and DTM EGTs to a k-move rule, but I haven't used that and have no idea how it works: I presume it does, knowing MB's work.

If MB is still interested in EGTs (and everyone burns out and moves on sometime), a sensible step would be for MB's code to be made available so that [my recommendation] the DTZ and DTZ50 EGTs could be made available. They exist for all 5-man and 6-man P-less endgames on John Tamplin's computers, so - for those endgames - it is only necessary to find a way to make them available. There is one 'try' in the pipeline at the moment.

The 'Depth By the Rule' (DTR) metric, supported by the DTZR metric, is (IMHO, but I'm possibly pre-disposed to it) 'the business'. It tells you what the maximum move-count 'to mate' is if White/Black are minimaxing this. It was defined and discussed in two ICGA_J papers of mine. The proposed algorithms could now be better described, and there was even a flaw, corrected in the second short ICGA_J note 'Depth By the Rule'. As someone stated above, DTR can be 'frozen' because it is determined by the next longer phase of play, which is why DTZR - Depth to (move-count) Zeroing (move, while minimaxing DTR as first priority) is needed. DTZR may be greater (or less than, another thing I missed, first time round, Black can optionally capture into a long phase) than DTZ. (DTR, DTZR) is in effect a two-component metric. If anyone thinks DTR/DTZR is as easy to compute as DTZ, I'd be delighted to hear from them as I don't currently believe that (though I am more hopeful than I was when I first conceived DTR).

Anyway, DTR/DTZR for 5- and 6-man games is certainly what I would like to see. DTR has the advantage that it tells you (or in practice, a computer) how much the fallible opponent has to concede if a k-move draw (for whatever 'k') is to be avoided. The 50-move rule is not relevant to Chess Compositions, can be suspended by Tournament Directors, and might be changed by FIDE as it has been in the past. MB championed the production of the DTZ50 EGTs in the absence of DTR/DTZR EGTs, and I'm grateful to him for that, so I can see why DTZ50 EGTs are attractive, but they are not the last word and are supercedable.

I'm a DTR fan also because I think 5- and 6-man DTR EGTs would tell us quite a lot about the nature of chess. I'm a DTZ fan because it allows P-endgame EGTs to be sliced up according to set positions of Pawns (but there has to be a hedge against the slicing going too far, as in KPPKPP.)

I'm a fan of WDL EGTs: I'd rather not call them 'Bitbases' as that name is too close to an implementation detail. I think there's something to be written by the SHREDDER team on their effective contribution but it may not be their priority. I believe that the existence of WDL EGTs expedites the later creation of EGTs to a metric, as there is no need to check out potential backed-up losses which are in fact draws or wins.

Yakov Konoval has a brilliant new, fast DTC-EGT code, albeit written in Pentium Assembler which doesn't meet the portability criterion. It is not parallelised afaik, and it does use a new indexing-scheme which facilitates EGT Generation. MB ran it in production mode to create the first 7-man EGTs, and I think might have converted the EGTs to more of a 'Nalimov format' for in-game use. MB must have some large discs on tap! The form of the EGT index determines how well the EGT can be used for what later. YK is also busy and not visibly active on EGTs, though I believe his DTC-code works across the whole range of 7-man EGTs. It would be good if he and MB would share their insights and even code with a wider group of people, especially if they are 'bowing out'.

Any production process needs the likes of CRC block-checks, MD5sum, x-check-verification against past work (by linear comparisons or, e.g., max/zug spot-checks).

I hope that clarifies a few things: I'd be happy to see a re-invigoration of EGT-generation/promulgation initiatives.

Guy

[Kirill Kryukov]

Guy, do you have any link to any open description about DTZR? We can't base a community supported bounty on a metric that is only described in a payed journal. Or may be you can explain it in simple words here.

DTR is clearly out of the question because it is much less useful practically than DTZ, while being more complex to compute.

Or do you propose a double-metric tablebase format?

[guyhaw]

I could make the original papers defining and discussing DTR/DTZR available here, but I don't think that's the best route.

DTR = the largest move-count that will be seen in a winning line to mate, provided White/Black are minimaxing this quantity.
DTZR = the least number of moves to complete the current phase, given that White/Black are minimaxing DTR as 1st priority.

The 'DTR' EGT could have a two-number cell (DTR, DTZR), or the two numbers could be stored separately. DTR >= DTZR so it would only be necessary to store (DTR-DTZR, DTZR) in fact, which would no doubt help with cell-sizes and compression.

In moving, the attacker will decrement DTR by 1 if possible, and will always decrement DTZR by 1, whether DTR is decremented or not.
a) if DTR = DTZR, the move can go to a (DTR, DTZR-1), or to a (DTR-1, DTZR-1)
b) if DTR > DTZR, the move can only go to a (DTR, DTZR-1) position
Doing this in reverse, 'unmoving' as in EGT-generation:
a) if DTR = DTZR, this backs up (if depth is in plies) to a (DTR+1, DTZR+1) position
b) if DTR > DTZR, this backs up to a (DTR, DTZR+1) position

The 'one EGT' (which is easier to refer to) and the 'DTR-DTZR' idea just occurred to me, so your 'bounty' initiative has already yielded results - for free.

The DTR EGT will throw light on such endgames as KNNKP, KQPKQ, KRPKR and KBBKNN (which takes a big hit under the 50-move rule). Incidentally, the maxDTZ50 position for KBBKNN has a great demo of _not_ taking a N but going for a 20+-move mate in the KBBKNN phase itself. See what I mean about learning from other metrics?!

DTR says what the 'finesse challenge' is for the attacker if DTR > the 'k' of whatever k-move rule is in place at the time. Observation of human play shows that humans are quite adept at conceding depth even when they play well and retain the win under time-pressure.

I conjecture that the larger the balanced endgame, the greater the expected depth of the position [though that may be a definition of 'balanced' ]. This would mean that more and more sophisticated techniques will be needed by chess-engines for 'optimal' play against fallible and less well-informed opposition.

For example, in KQPKQ with DTR > k, it might be possible with a small DTZR to P-advance quickly, but this does not use the k-move budget in the current phase, and this can be used for a 'longer play' giving the opposition more opportunity to concede in DTR terms. So how should the attacker best play? It's a question I'm writing up about at the moment, and I also use the idea of 'learning about the opponent' as described in my 'Reference Fallible Agent' work.

I hope that's clear. Do ask if not. g

[guyhaw]

Jonathan Schaeffer wrote about the errors that occurred in producing the Checkers EGTs. Whoever (or whatever community) creates EGTs, they will need to be rigorous (in conformance with a set of 'rules') to make sure that errors do not creep in.

On a 800TB/200TB scale (and I agree with VD's acreage figures, see previous posts), compiler, processor, disc-write/copy errors and human error creep in.

There is a set of people I know and trust to do this work (based on their experience, enlightenment and results), and I only need two hands to count them: KT (retired), EN (ditto), NW (ditto), PK (ditto), MB, YK, ... This is unfortunate, as a community approach to production would be a good thing.

I agree with VD that WDL EGTs are good news, in themselves and as stepping-stones to DTx EGTs.

g

[guyhaw]

Some data published in 2005 about DTM, DTC, DTZ, DTZ50 EGT sizes. Note that, as DTZ50 EGTs are only produced when maxDTZ > 50, they don't occupy that large an acreage. Note also the idea of the delta(DTZ, DTZ50) EGT: DTZ50 >= DTZ or 'new draw'.

3- to 5-man P-less: DTM (1,822 MB), DTC (71.29% of that), DTZ (71.29% - same EGTs as DTC), DTZ50 (0%), delta(DTZ, DTZ50) (0%)

3- to 5-man with Ps: DTM (5,579 MB), DTC (59.14% of that), DTZ (43.36%), DTZ50 (15.36%), delta(DTZ, DTZ50) (0.70%)

3- to 5-man all: DTM (7,401 MB), DTC (52.13%), DTZ (50.24%), DTZ50 (11.58%), delta(DTZ, DTZ50) (0.53%)

3-3 & 4-2 P-less: DTM (220,623 MB), DTC (56.37%), DTZ (56.37% - same EGTs as DTC), DTZ50 (20.56%), delta(DTZ, DTZ50) (1.11%)

So, if one had an indexing system to a set of EGTs saying whether they were DTM, DTC, DTZ or DTZ560 (or all 4), there could be economies. Note that DTZ50 EGTs + delta(DTZ, DTZ50) EGTs are much smaller than DTM EGTs.

g

[guyhaw]

In my first algorithm descriptions re generating DTR EGTs, I aimed to create the 'next level of DTR' positions in one cycle.
I now see that this is not the way to go, but rather, for efficiency, backing up positions 'of the same depth' to 'positions of the same depth':

a) for DTR > DTZR, I should create sets of positions for each (DTR, DTZR) as in this order: (DTR, 0), (DTR, 1), (DTR, 2), ... , (DTR, DTZR = DTR-1)
b) for DTR = DTZR, the creation of the (DTR, DTZR) positions pulls on (DTR, DTR-1) positions and on (DTR-1, DTR-1) positions ...
... but is the only cycle to pull from two sets of already identified positions

If maxDTR = the maximum DTR for and endgame, there are 0.5*maxDTR^2 cycles (*2 for wtm and btm), which is not as good as maxDTR*2 cycles. However, the cycles will be backing up less positions at each turn, so the effect is not as bad as it seems.

g

[kronsteen]

I agree with g, DTZR solves the problem of DTR I mentioned above, as it shows winning lines. It is also clear way of progress to show, not only winning lines but also “good ones”. It opens a new path for TBs, moving from purely theoretical knowledge to practical knowledge where purpose is to maximize chances of inducing a fatal error by opponent in order to win (or draw). But we are entering a subjective, and therefore virtually endless, debate here. Much work seems to have been already done about this, I believe.

DTZR remains a very technical metric which won’t be understood by the common player. DTZR gives a line of play, which is truly good, but when asked “why this line ?”, answer may be too technical for many players. Chess players are not all engineers. Other metrics don’t fall into this. DTM explanation is immediate. DTC and DTZ show distance to a move (capture, promotion, pawn push) which may be practically considered as a “milestone”. DTZ50 does this according to 50-move rule.

Other problem is that DTZR alone is somewhat incomplete as this is a two-number metric. If it is to be completed by DTR (or DTR-DTZR) in order to have full position assessment, I fear that this will take a lot of space storage, as DTR will almost never contain small figures (1, 2, 3…) which certainly play a big role in DTZ space savings. Has DTR+DTZR already be computed on 5-men in order to compare its weight to DTM ? If not, finding that DTR+DTZR weighs as much as DTM, and even more, wouldn’t be a surprise.

Finally, if I’m not mistaken, DTZR has another drawback, it is unsuitable to take former non-zeroing moves into position analysis. Only DTZ(50) own this capability.

So, if we are still talking about 7-men, DTR/DTZR are not the quickest route to them. But I agree that DTR/DTZR will raise very interesting new knowledge. May be worth a try on 5-men first ? If conclusive, could be extended to 6-men.

For 7-men, according to what has been posted in this topic, quickest route and best practical choice seems currently DTZ50 (or maybe DTZ). Glad to know that DTZ50 3-6 men work is already partially done. I also believe that DTZ50+DTM form a powerful duo, and completing DTZ50 for 6-men will make it available to 6-men. Only disappointing news are that DTZ cuts down size only roughly by a factor of two, which means that DTZ50 (or DTZ) 7-men heads for 100 TB.

[guyhaw]

I thank kronsteen for the previous contribution: amongst other things, it encourages me to think I'm explaining the DTR-metric in a way that can be understood now. It's a tricky concept, in absolute terms as well as in comparison to DTC/M/Z(50), and aspects of it have escaped me for years, even though I dreamed it up in the first place.

For the future, I suggest that, by 'the DTR depth', we mean the (DTR, DTZR) number-pair. By the same token, by 'DTR metric', we mean the 2D-measure of a position in (DTR, DTZR) space. A bit tricky that I'm using 'DTR' for two concepts and maybe that can be improved on. Anyway, the nomenclature is convenient.

The DTR metric appears 'very technical' in that it does not relate to an immediate DTC/M/Z objective which can be easily described. "White/Black are minimaxing the length of the longest phase of play" might be understandable.

The merits of this were visible in the DTZ50 work with MB and J Tamplin. JT found a KQPKQ position where one could push the P (on the h-file I think) for a win, but that jumped into a 50+-move phase and led to a draw claim. The only move that ducked this was the DTZ50-optimal one, and that took exactly 50-moves to push the Pawn. There are some really extreme positions out there in the sea of chess that you cannot find without a computer and EGTs.

Of course, there is no reason why the computer should not go down the DTZ-, DTC- or DTM-optimal line, provided there's no way this can land it with a superlong phase. But, as instanced above, there are positions where none of the DTC/M/Z-optimal moves avoid an avoidable 50-move draw.

I'm not too worried about space for the DTR metric. In fact, I'd always like to have the DTZ EGTs next to my engine (provided it understands that they are DTZ and not DTM EGTs: try working out why!). There's always the situation of trying to finesse quickly enough out of a superlong current phase, and quite often it is the current phase that is longer than the next ones (except that the KQP(h)PKQ situation is different around h7). 6-man P-ful DTZ EGTs have not been computed but I'm sure they could be on today's kit, and you would then see those DTZ EGTs compressing to much less than 50% of the DTM EGTs.

So you could store (DTR, DTZR) along the DTZ EGTs as (DTR-DTZ, DTR-DTZR), two positive numbers, from which (DTR, DTZR) can be derived given DTZ.

Inspired by Jansen's focus on 'Fallible Opponents', I created the 'Reference Fallible Endgame Player' - and that's written up in the ICGA_J. The idea is that you can measure the typical fallibility of opponents (in terms of stochastically-dumbed-down infallible players) playing KQKR, KNNKP, KBBKN, KQPKQ etc - and take that into a consideration of what might be the best move if you are in these endgames.

Currently, a good strategy for endgame play seems to be SV+BZoZRoR-ZR+ ... (notice the '+' at the end), which means 'subset moves in this filter-sequence':

SV+ ... only choose moves that maximise value (i.e., play winning moves rather than drawing moves rather than losing moves - obvious enough)
SB ... 'ban' any moves that allow Black to force White (retaining the win) to a previous position [an interesting algorithm being written up now]
SZo ... only consider moves that allow one to finish the current phase in the available moves (or use SZ- if there are none): uses DTZ EGTs of course
SZRo ... only consider moves that chase a DTR objective that can be achieved in the available moves (or use SZR- if there are none)
SR- ... minimise DTR
SZR+ ... maximise DTZR (knowing that positions will not repeat thereby, or the phase be unavoidably superlong)

but this can be improved around 'ZRoR-' by risking depth if the opponent is seen to be fallible enough for this to be worthwhile. It may be that a longjump to a position adding 1 to DTR but taking DTZR to 48 would be good news, giving the opponent plenty of rope to hang themselves with. Jansen showed way back that if the attacker was playing random win-preserving moves, there was a KQKR position where playing a non-DTC-optimal 'KR' move was best.

No the (DTR, DTZR) EGTs, or as I'd prefer them implemented, the (DTR-DTZ, DTR-DTZR) EGTs have not been computed, and that's a challenge for the future. Up to 5-man, it's an in-RAM computation so no big deal: 6-man would take time though.

Readers might like to amuse themselves by working out, starting from the smallest endgames, when they stop being {(0, 0)}. Maybe even KNKP and KPKP have their subtleties. Another challenge is to identify what endgames can be followed by an endgame with a greater maxDTZ.

Yakov Konoval's program computes to the DTC metric, on the grounds that - in lopsided endgames - the quickest thing is to 'sac' a piece but leave a win (but that ! might leave one with a superlong phase). An ambition is to move to the DTZ-metric, but the whole business of managing the slicing of an endgame/EGT into an appropriate number of bits has not been done yet afaik.

g

[syzygy]

I'm not sure if I am missing something, but you need at least 2 bytes to store a DTZ, and only 1 byte to store a DTZ50. It may contribute to the difference?

A special purpose compressor will compress symbols corresponding to position values instead of individual bytes. If I am correct in estimating that most (all?) tables will have very few values > 50, then those positions will require a relatively large amount of compressed space, but there will be so few it will not be noticeable.

Perhaps two formats can be defined in the requirement:

A. "archival" format - compressed as much as possible, a single access is still feasible without decompressing the whole file. (Say in a few seconds). This format is good for file exchange.

B. "search" format - larger than "A", but allows for a relatively fast probing.

My engine uses WDL tables for probing during search and DTZ for probing at the root. (Smaller tables during search are advantageous for caching.)

In any event there should be WDL tables, as they can be easily generated anyway, and 6-piece WDL(50) tables are all you need to generate 7 piece DTZ(50) tables, so decrease system requirements for 7-piece tablebase generation.

[syzygy]

DTR = the largest move-count that will be seen in a winning line to mate, provided White/Black are minimaxing this quantity.

Wherein move-count is the value of the "50-move counter". (Not the number of moves in the winning line, as that would give DTM.)

DTZR = the least number of moves to complete the current phase, given that White/Black are minimaxing DTR as 1st priority.

Should that not be "the" number of moves to complete the current phase?

What ends a phase for you? A zeroing move, a move that lowers DTR, or either?
(My guess is that "either" is preferable, as it leads to smaller values.)

The 'DTR' EGT could have a two-number cell (DTR, DTZR), or the two numbers could be stored separately. DTR >= DTZR so it would only be necessary to store (DTR-DTZR, DTZR) in fact, which would no doubt help with cell-sizes and compression.

In moving, the attacker will decrement DTR by 1 if possible, and will always decrement DTZR by 1, whether DTR is decremented or not.

If DTR is decremented (or a zeroing move is reached), DTZR may be increased. (As you said, DTR >= DTZR, so it cannot be the case that DTZR is decremented at every move.)

[syzygy]

Of course, there is no reason why the computer should not go down the DTZ-, DTC- or DTM-optimal line, provided there's no way this can land it with a superlong phase. But, as instanced above, there are positions where none of the DTC/M/Z-optimal moves avoid an avoidable 50-move draw.

Indeed, so having both DTR and another type of table available, the other table can only be followed as long as it does not lead to a position for which move-counter + DTR > k. If you have move-counter + DTR = k you *must* follow the DTR table or risk a draw.

Readers might like to amuse themselves by working out, starting from the smallest endgames, when they stop being {(0, 0)}. Maybe even KNKP and KPKP have their subtleties. Another challenge is to identify what endgames can be followed by an endgame with a greater maxDTZ.

The values will be greater than (0,0) quite often. For many (easy) positions the current phase is not the longest phase. KQKQ and KRKR will work. KQKQ / KRKR will also have lower maxDTZ than KQK / KRK.

DTR can be useful for practical play, but provided k=50 by far the most useful table would be DTZ50 "augmented" with DTR50+ information. Am I right in thinking that no games are ever played with k-move rules for k < 50?

Compressed augmented DTZ50 tables are probably not much bigger than compressed DTZ50 tables. For the moment I am liking this idea a lot!!

I haven't thought this through fully yet, but augmented DTZ50 should:
- not be much larger than DTZ50 and far smaller than DTR
- have full DTZ50 information (including the info that makes kronsteen happy )
- have full information about wins/losses when disregarding the 50-move rule
- give practical strategies to win positions that are drawn on the 50-move rule
- give optimal play for any k-move rule provided k>=50
and generation seems feasible.

[syzygy]

Actually, I believe that this idea can be generalized.

Let (k) = 0 < k_0 < k_1 < k_2 < ... < k_n.

Now define DTR(k) for position p as the pair:
(min{i : p is won under a k_i-move rule}, number of moves to complete current phase)

Now:
DTR( 1 < 2 < 3 < 4 < ... ) = DTR
DTR( inf ) = DTZ
DTR( 50 ) = DTZ50
DTR( 50 < 51 < 52 < 53 < ... ) = DTZ50 "augmented with" DTR50+
DTR( 50 < inf ) = DTZ50 "augmented with" DTZ

DTR( 50 < inf ) will be the smallest compressed table giving all the benefits of both DTZ and DTZ50.

Assuming that in actual tournament play only k-move rules are used with k one of 50, 60, 70, 80, 90, 100, then the smallest table providing all required information is DTR(50 < 60 < 70 < 80 < 90 < 100).

An interesting question is what the difference in size will be between DTR( 50 < inf ) and DTR( 50 < 51 < 52 < 53 < ... ).

[kronsteen]

DTZR = the least number of moves to complete the current phase, given that White/Black are minimaxing DTR as 1st priority.

Should that not be "the" number of moves to complete the current phase?

What ends a phase for you? A zeroing move, a move that lowers DTR, or either?
(My guess is that "either" is preferable, as it leads to smaller values.)

Humans can easily identify zeroing moves, but not moves lowering DTR. The fact that a move lowers DTR is in sometimes a complete mystery for humans. So if purpose is to build a TB that is understandable to humans, zeroing moves may be better. If purpose is to design a playing program, « either » seems better.

Compressed augmented DTZ50 tables are probably not much bigger than compressed DTZ50 tables. For the moment I am liking this idea a lot!!

I haven't thought this through fully yet, but augmented DTZ50 should:
- not be much larger than DTZ50 and far smaller than DTR
- have full DTZ50 information (including the info that makes kronsteen happy )
- have full information about wins/losses when disregarding the 50-move rule
- give practical strategies to win positions that are drawn on the 50-move rule
- give optimal play for any k-move rule provided k>=50
and generation seems feasible.

I like info identifying theroretical wins which are drawn on 50-move rule, because such status carries clear message of hope for superior side and danger for inferior side, and is therefore relevant for practical (and imperfect) play. Providing for these positions some kind of metric in order to identify « how far » they are from a win is even more accurate, so I like augmented DTZ50 idea too.

What kind of info is most relevant for these positions ? DTR info (i.e smallest k which would be required for position to be a win on a k-move rule, with k>50 necessarily), or DTZ info (i.e min number of moves, necessarily >50, required from current position in order to reach a zeroing move which leads to a won position under 50-move rule) ? This is not exactly the same. I tend to prefer last one, as it is probably easier to compute, and is also usable in practical cases when some non-zeroing moves have been previously played before reaching position (which is not the case of DTR).