5-1 EGTB generation revisited

[Martin Kreuzer]

Hi Guy, Guido,

finally I had time to examine some of the 5-1 EGTB I computed.
Here are some maxdtm results provided by FEG -LL. The positions
are attached. First some general observations:

a) For pawnless endgames, the symmetry group is D_4 (8 elements).
As both of you noted, not all orbits have 8 elements, however.
For pawnful endgames, the symmetry group is S_2 (2 elements).
In the final compression phase, FEG seems to store one position
for each orbit.

b) FEG reports only legal positions (i.e the stm cannot capture the
opposing king, no two pieces are on one square), but it does not check whether these positions are reachable. In the cases where it reports only
unreachable positions at the stated dtm, I have also searched for the
"true" maxdtm for reachable positions.

c) I think it would no be too hard to check certain reachbility criteria: if one side has only a king and it is the sntm (=side not to move) then the king should have a legal move to a square where it is not threatened by two unblockable checks or the opposing king.
The king of the stm (=side to move) should also not be threatened by two
unblockable checks.

d) If it finds more than 100 positions at the stated dtm, FEG reports only the the first 100.

Now some individual endgames:

1) kbbbbk: For wtm, the maxdtm is 13. There are 154 positions.
For btm, at dtm 16 there are 8 positions, but they are all unreachable.
At dtm 15, there are 4 unreachable positions. At dtm 14, there are
46 positions, among them many reachable ones.

2) kbbbnk: For wtm, there are 2 positions at dtm 22. One of them is reachable, so maxdtm is 22.
For btm, maxdtm is 33 and there are 25 positions.

3) kbbnnk: For wtm, at dtm 25 there is 1 unreachable position. At dtm 22 there are 2 positions, one of which is reachable.
For btm, at maxdtm 34, there are 5 positions, one of which is reachable.

4) kbbbpk: For wtm, maxdtm is 24 and there are 45 positions.
For btm, maxdtm is 30 and there are 4 positions. They are essentially equivalent and very nice: White: Kh2, Bg1, Ba6, Bd8, Pb7; B: Ka5 (black to move)
After 1. ... Ka6: White can only underpromote 2. b2N. Then 2. ... Kb7 3. Nd7 Kc7
wins another bishop and draws out the game. This could be a good starting idea for composing an endgame study.

5) knnnnk: wtm has maxdtm 18 with 1153 positions, btm has maxdtm 21 with 330 positions.

6) kqqrrk was also mentioned in this thread: wtm has maxdtm 4. There are 10 positions, and all of them are reachable. For btm, we have maxdtm 4 and 57632 positions.

7) kqqppk: For wtm, maxdtm is 5 with 2386 positions and for btm, maxdtm is 9 with 111292 positions to choose from.

It is correct that FEG does not return fen strings, but its output can be converted without too much trouble. So, I hope the attached files are useful. I will report further findings later.

Have a merry and happy holiday season! Cordial greetings,
Martin Kreuzer

[Arpad Rusz]

4) kbbbpk: For wtm, maxdtm is 24 and there are 45 positions.
For btm, maxdtm is 30 and there are 4 positions. They are essentially equivalent and very nice: White: Kh2, Bg1, Ba6, Bd8, Pb7; B: Ka5 (black to move)
After 1. ... Ka6: White can only underpromote 2. b2N. Then 2. ... Kb7 3. Nd7 Kc7
wins another bishop and draws out the game. This could be a good starting idea for composing an endgame study.

Martin Kreuzer

You are right: that is a good idea for composing a study. But it was already discovered by Troitzky who published the next study in Novoye Vremja in 1895:
5k2/8/8/3R4/6K1/8/3b2pP/8 w - - 0 1
draw

Another study (there are many) with that ending is:
Van_Breukelen(Schakend Nederland - 1978)
2R5/8/8/2b3K1/k7/8/6pP/8 w - - 0 1
draw

[guyhaw]

Martin,
FEG's indexing scheme makes whole-EGT verification impractical. I expressed my concern to Johan de Koning at the time but he was confident that FEG - the 'Final Endgame Generator' - was ok. This only heightened my concern.
FEG was never 'final' nor correct. Marc Boursutschky found that it did not convert correctly into KNNK wins of maxDTM 0 (or 1?), a bug that has since been corrected. Obvious tip: never call any software-version 'final': the hubris is an invitation to the Giver of Software Bugs.
As I'm not confident that I understand what FEG is doing with P-less position-equivalence (in LOF, and query), or endgames with Bishops, I'd be interested in your sets of maxDTM positions - especially where these are perusably small supplied complete by FEG - as I won't be much wiser without them.
Good endgames for this would be (wtm, all) KQBBNK, KRRBNK, KBBBNK, KBBNNK, KBNNNK, KRBBNK, KRBNNK, KRRNNK and KQNNNK.
Regards - g

[guyhaw]

Martin,
I somehow missed yr last post, but I now see that of the endgames whose maxDTMs I expressed interest in, you have produced maxDTM information for KBBBNK and KBBNNK.
For KBBBNK, my wtm maxDTM expectations line up with the FEG and GAF stats, but I'm not in line with FEG for btm maxDTMs (my '48' v your 25).
For KBBNNK, I'm exactly x2 compared with the FEG and GAF stats which agree.
I'm assuming that the LOG-stats/LOF-stats difference is about board symmetries (and equivalence classes of positions) as LOG/LOF == 2 for P-ful endgames (on which my expectations and FEG/GAF stats invariably agree). I'm therefore just dividing the LOF-stats by a consideration for 'like men' (2!, 2!*2! or 3!) to derive my expectations.
However, I'm not coming up with the right figures. Any ideas? I'm assuming Nalimov stats would be 'in the same area' as FEG stats.
g

[Martin Kreuzer]

Dear Guy and everybody interested,

attached I post the maxdtm statistics and sample positions
of the endgames you asked for. Before discussing them in detail
let me briefly address some of your remarks:

a) Do you have any knowledge of the FEG indexing scheme?
b) Do you know how FEG compresses the files it computes?
c) Do you have any way of querying the FEG EGTB other than
using Chessbase?

As for the comparison to the Nalimov statistics files, it would
not be too difficult (and has been done by Marc) to compute
some of the 4+2 or 3+3 EGTB using FEG and to compare the stats.

Now let me briefly go through the maxdtm stats of the 7 requested endgames:

1) KBNNNK: For wtm, at dtm 21 there is 1 unreachable position
(up to the D_4 symmetry). Moreover, at dtm 21 there is 1 unreachable
position, at dtm 20 there is no position, and at dtm 19 there is
one unreachable position. Hence the true maxdtm is 18 where there are
18 positions, including many reachable ones.

For btm, the situation is much simpler: maxdtm is 34 with 3 positions.

2) KQBBNK: For wtm, the maxdtm is 7 with 1 (reachable) positions.
For btm, the maxdtm is 33 with 24 positions (including reachable ones).

3) KQNNNK: For wtm, the maxdtm is 9 with 9 positions to choose from.
For btm, the maxdtm is 21 and there are 322 positions.

4) KRBBNK: For wtm, the maxdtm is 19 with 2 positions. For btm, the
maxdtm is 33 with 24 positions (as suggested by the *.log file).

5) KRBNNK: For wtm, at dtm 21 there is 1 unreachable position.
The next positions are at maxdtm 16, where we find 11 positions
(including reachable ones).

For btm, the maxdtm is 34 with 5 (reachable) positions.

6) KRRBNK: For wtm, we have 1 reachable position at maxdtm 10.
For btm, we have 44 positions (including many reachable ones)
at maxdtm 29.

7) KRRNNK: For wtm, there is 1 unreachable position at dtm 10.
Moreover, there are 17 positions at dtm 9, but all of them appear to be unreachable. Hence maxdtm is 8 where we find 162 positions, including reachable ones.

For btm, the maxdtm is 15 with 3 (reachable) positions.


I hope that these statistics and the attached positions will be useful.
If you have further suggestions of "interesting" endgames, please let me know.
Best wishes for the New Year!

Greetings,
Martin Kreuzer

[guido]

Dear Guy and everybody interested,

attached I post the maxdtm statistics and sample positions
of the endgames you asked for. Before discussing them in detail
let me briefly address some of your remarks:

a) Do you have any knowledge of the FEG indexing scheme?
b) Do you know how FEG compresses the files it computes?
c) Do you have any way of querying the FEG EGTB other than
using Chessbase?

As for the comparison to the Nalimov statistics files, it would
not be too difficult (and has been done by Marc) to compute
some of the 4+2 or 3+3 EGTB using FEG and to compare the stats.

Now let me briefly go through the maxdtm stats of the 7 requested endgames:

1) KBNNNK: For wtm, at dtm 21 there is 1 unreachable position
(up to the D_4 symmetry). Moreover, at dtm 21 there is 1 unreachable
position, at dtm 20 there is no position, and at dtm 19 there is
one unreachable position. Hence the true maxdtm is 18 where there are
18 positions, including many reachable ones.

For btm, the situation is much simpler: maxdtm is 34 with 3 positions.

2) KQBBNK: For wtm, the maxdtm is 7 with 1 (reachable) positions.
For btm, the maxdtm is 33 with 24 positions (including reachable ones).

3) KQNNNK: For wtm, the maxdtm is 9 with 9 positions to choose from.
For btm, the maxdtm is 21 and there are 322 positions.

4) KRBBNK: For wtm, the maxdtm is 19 with 2 positions. For btm, the
maxdtm is 33 with 24 positions (as suggested by the *.log file).

5) KRBNNK: For wtm, at dtm 21 there is 1 unreachable position.
The next positions are at maxdtm 16, where we find 11 positions
(including reachable ones).

For btm, the maxdtm is 34 with 5 (reachable) positions.

6) KRRBNK: For wtm, we have 1 reachable position at maxdtm 10.
For btm, we have 44 positions (including many reachable ones)
at maxdtm 29.

7) KRRNNK: For wtm, there is 1 unreachable position at dtm 10.
Moreover, there are 17 positions at dtm 9, but all of them appear to be unreachable. Hence maxdtm is 8 where we find 162 positions, including reachable ones.

For btm, the maxdtm is 15 with 3 (reachable) positions.


I hope that these statistics and the attached positions will be useful.
If you have further suggestions of "interesting" endgames, please let me know.
Best wishes for the New Year!

Greetings,
Martin Kreuzer

Hi Martin,

For your initial questions I'm sorry to have no answer to give (:-() while for the 7 endgames I analyzed your statements with much interest.

Even if my comparison with gafs was not done in all the details, I found only differences in the number of positions, but this should depend mainly on the elimination of gafs of symmetrical positions in respect to the diagonal a1-h8.

I checked also the illegality of the unreachable positions and confirm all your conclusions. Without the backmove check it is impossible to find them. In some cases two backmoves would be necessary.
In gafs I did only an incomplete control on double checks (this corresponds to a very limited backmove check), so I considered legal almost all those positions you correctly signalled as unreachable.

An exception to this happened in KRRNNK where for btm maxdtm I found only 2 positions instead of 3.
Initially I thought that this depended on the symmetry but examining the positions in details I concluded that gafs set as illegal the third position reported in the file krrnnk_b15.dtn because the bK is checked by two wN and this is illegal/unreachable (I exclude also a double check of bishops and other double checks).
Another interesting observation in this endgame is that the first two positions could give origin by diagonal symmetry to two other equivalent positions. The fact that the positions in FEG are only 3 and not 5 indicates that if a king in on the diagonal a1-h8 FEG seems to force the other king to stay only in the lower triangle a1-h1-h8. If the asymmetry was due to a piece different from the king, then FEG would have considered both the equivalent cases.
But ... the first position in kbbbbk_w13.dtm doesn't respect this rule! So I don't know what to conclude!

When I started programming my generator I considered important to eliminate all the possible illegal positions because this is done once for all before starting the iteration cycles with the advantage of eliminating this positions from all the successive analyses in each cycle, with a sensible reduction of cpu time. I remain on this opinion because the differences in the number of positions in the statistics with FEG and TBGEN are not negligible in particular with like pieces. Also a comparison of the different number of positions computed by different generators could be interesting to investigate.

Thank you for all your works and best wishing for the New Year.
Guido

[Martin Kreuzer]

Hi all,

now I have posted the next five 5-1 EGTB, namely

kbbppk, kqbnpk, kqrnpk, and krbnpk.

they are complete with stats files and md5sums, as usual.
Altogether 56 EGTB have been posted now. I have already computed
all 65 EGTB with at most two pawns and the five EGTB with 3 or 4 pawns are under way.
I will keep posting EGTB and update you accordingly.

Warm regards and best wishes for 2007!
Martin Kreuzer

[vb4]

Hi all,

now I have posted the next five 5-1 EGTB, namely

kbbppk, kqbnpk, kqrnpk, and krbnpk.

they are complete with stats files and md5sums, as usual.
Altogether 56 EGTB have been posted now. I have already computed
all 65 EGTB with at most two pawns and the five EGTB with 3 or 4 pawns are under way.
I will keep posting EGTB and update you accordingly.

Warm regards and best wishes for 2007!
Martin Kreuzer

Hi Martin,

Can you tell me where I can pick up these stat files? Also can you tell me how many you have completed of the 5-1 files uo till now?

THanks,

Les

[Martin Kreuzer]

Hi Les,

all the files are on the account egtb51 (see the first page of this thread) provided by Kirill (thanks a lot!). As mentioned in my post, I have now finished the computation of 65 of the 70 EGTB with 5-1 men, but so far
I have posted only 56. The rest will follow soon.

Greetings,
Martin Kreuzer

[vb4]

Hi Les,

all the files are on the account egtb51 (see the first page of this thread) provided by Kirill (thanks a lot!). As mentioned in my post, I have now finished the computation of 65 of the 70 EGTB with 5-1 men, but so far
I have posted only 56. The rest will follow soon.

Greetings,
Martin Kreuzer

Hi Martin,

First let me say you have done alot of work in the generation of these tb's as well as some of the other individuals out here. Martin is there any utility out there that you are aware of that can convert your statistics into a format similar to Eugenes?

Thanks again,

Les

[Martin Kreuzer]

Hi all,

now I have posted four new 5-1 EGTB, namely

KNNPPK, KQBPPK, KQNNPK, and KQNPPK.

They are complete with md5sums and stats files. Altogether 60 such EGTB have been posted now.
I am in the process of posting the next 5.

Les: At the moment I do not see a clear way to transform the FEG statistics to Nalimov *.tbs file format.
The reason is that FEG treats symmetries differently: they are removed only in the final compactification phase.
Thus the statistics reported during the computation shows higher numbers of positions than would be given after symmetries have been taken into account.
Using the FEG -LL option, it is still possible to determine exact numbers of positions for each dtm, but this may involve a lot of work.
Moreover, as discussed between Guido and me, FEG does not consider reachability of positions.

Greetings and best wishes,
Martin Kreuzer

[Martin Kreuzer]

Hi all,

now I have posted 5 new EGTB of type 5-1, namely

KBNNPK, KBNPPK, KRBPPK, KRNNPK, and KRNPPK.

They are complete with md5sums and stats files, as usual. Now 65 EGTB of type 5-1 are posted in total.
For the remaining five, I have already computed two and estimate that I will be finished in about a week.

Cordial greetings,
Martin Kreuzer

[guyhaw]

Martin,
I'm catching up with your determined 5-1 work after an extended holiday in Egypt (great monuments, grinding poverty and disfunctional infrastructure) and Jordan (more relaxed; Petra is a 'must visit').

Small slip perhaps: in your maxdtm2 zipfile, you have a kqbbnk_w5.dtm file; should this be kqbbnk_w7.dtm?
You had some questions about FEG to which I can only give partial, unsatisfactory answers.
The FEG indexing scheme is different from Nalimov's and is apparently the key to FEG being able to use less space at generation time than Nalimov: it is also 'the inspiration' for the indexing scheme used by Yakov Konoval. I don't know any more than that.
I don't know how FEG compresses its files: it could be a different scheme from the Kadatch scheme used by Nalimov, and even if the same, could use different block sizes. It seems that the Russian school of Computer Science excels in compression schemes, partly out of necessity because in the old days they were behind on scale of computers. I suspect that today, different compression schemes have their pros and cons but that none dominate across the board.
One can only query FEG EGTs with Chessmaster, not with Chessbase.
Marc Bourzutschky has obviously developed a way of converting FEG EGTs reliably to Nalimov format, after which they may be accessed by whatever software, and Nalimov stats can be produced. These, for P-less endgames, may differ from FEG stats.

Would be interested in your lists of extracted maxDTM positions for those P-ful endgames where there are few maxDTM positions. Before trying to understand what is going on with the FEG stats on P-less situations, we might as well confirm that we understand the P-ful situation. Target endgames in ~priority order:
KBBPPK, KBNPPK, KQBBPK, KQBNPK, KQNPPK, KRBBPK, KRBNPK, KRNPPK; KBNNPK, KNNPPK, KQBPPK, KQQBPK, KQRNPK, KRBPPK, KRRBPK, KRRNPK, KRRRPK.
g

[guyhaw]

Martin,
I'd also be interested in DTM-minimaxing lines from example maxDTM positions - one nominal maxDTM position per endgame, whether are reachable or not, but reachable ones preferred where there is a choice.
It's only necessary to go to the first capture, as Eiko Bleicher's site is available for 4-1 endgames: there will presumably be early captures in btm maxDTM positions, and probably in wtm ones as well.
g

[Martin Kreuzer]

Hi all,

now I have computed and posted the final five EGTB of type 5-1, namely

KQPPPK, KRPPPK, KBPPPK, KNPPPK, and KPPPPK.

They are on egtb51, complete with stats files and md5sums.
My next plan is to use the files to do some "higher level statistics".

Guy: Thank you for the corrections and the suggestions.
When I have some spare time again, I will start collecting the maxdtm and other statistics for the endgames you mentioned.
I will also try to see if it is possible to create *.tbs like files and maxdtm lines.
(I am optimistic, as always.)

Best wishes,
Martin

[guyhaw]

As expected, LOG/LOF == 2 for the number of P-ful maxDTM positions (and presumably for all the other depths), so I think 'LOF' merely involves some sort of position-count reduction for board-symmetry.
All LOF-numbers divide exactly by whatever is needed to account for 'like men'.
Depth 33 and 246-positions feature a lot in the last five btm maxDTMs: clearly, the piece is being lopped off to leave the same set of positions.
Probably counter-productive to go for Nalimov-format '.tbs' statsfiles for FEG results: the Nalimov format is not ideal (missing lines where there's a zero, missing right justification) and the numbers are different.
Even if you have to hack maxDTM lines manually with Chessmaster, it's only necessary to go to a 5-man position, easy when it's btm. In a DTC-minimaxing line, White would force-sac in most cases.
I look fwd to yr further results. Thanks again.
g

[guyhaw]

If maxDTM, loser to move > maxDTM, winner to move - which it is for 90% of the 5-1(p) endgames - then Black is making a capture from its maxDTM positions. Thus, the btm maxDTM 5-1(p) positions/depths will be easily checked against Nalimov 4-1(p) EGTs.
I suspect that, quite often, the wtm maxDTM positions will be such that White cannot retreat from the bK without losing a piece. These will also be easily verified against 4-1(p) Nalimov EGTs.
I don't know enough about forward-search to know why SHREDDER (in this case) cannot serve up a mate in 8 when searching 16 plies deep. Maybe others do.
g