Gaviota's Endgame Tablebases

[hgm]

OK, thx. I already suspected it must be recognizers. Apparently KPK is good enough here, and you don't need some more general evaluation of passers that cannot be stopped by the King.

Joker still has no such thing; it is still waiting for me to make some time available to work on the on-the-fly retrograde analysis for positions like this.

[Sven]

What kind of extensions do you use in Gaviota that it sees the solution in 16 ply? Joker (which does not use any extensions in positions like this) needs 28 ply to find the promotion even after Rxg5 fxg5! Do you have recognizers for Pawn endings?

I have some internal recognizer that is literally like a kpk bitbase. Most of the positions are solved with heuristics, and the rest from a simple retrograde analysis. It builds at startup almost instantaneously.

In fact, Gaviota without TBs should see this earlier than 16 plies unless I am missing something. I will take a look.

Do you mean that your recognizer covers kpk only? I think that in this test position only a small portion of the tree is spent at kpk positions. I can imagine that there are more kqkp positions being visited in a non-TB search. E.g. the main line you gave ends up in this position:

[d]8/5kPK/8/8/8/3p4/8/8 b - - 1 7

where kpk recognizers would not help very much IMO.

Sven

[bob]

OK, thx. I already suspected it must be recognizers. Apparently KPK is good enough here, and you don't need some more general evaluation of passers that cannot be stopped by the King.

Joker still has no such thing; it is still waiting for me to make some time available to work on the on-the-fly retrograde analysis for positions like this.

I am not sure how a recognizer can lead to a specific mate announcement, however. Crafty has specific evaluation code to recognize won, drawn or lost KPK endings, with perfect accuracy. But it doesn't return any sort of mate score.

[michiguel]

Are you asking about finding the mate with endgame tables?

I was asking about the case that took 16 ply, which is listed as without tablebase probing. At least, I suppose that is what `probing depth = None´ means. But I think only Miguel could answer that.

Correct, when it says "none" it means tablebases were switched off, rather than the depth was "none". Sorry about the confusion.

Miguel

[michiguel]

OK, thx. I already suspected it must be recognizers. Apparently KPK is good enough here, and you don't need some more general evaluation of passers that cannot be stopped by the King.

Joker still has no such thing; it is still waiting for me to make some time available to work on the on-the-fly retrograde analysis for positions like this.

I am not sure how a recognizer can lead to a specific mate announcement, however. Crafty has specific evaluation code to recognize won, drawn or lost KPK endings, with perfect accuracy. But it doesn't return any sort of mate score.

It does not return a mate score in that case but it sees Rxg5! with a big score. I can post the logs later. I did not do it because the point was to see what happens with the tablebases "on".

Miguel

[michiguel]

What kind of extensions do you use in Gaviota that it sees the solution in 16 ply? Joker (which does not use any extensions in positions like this) needs 28 ply to find the promotion even after Rxg5 fxg5! Do you have recognizers for Pawn endings?

I have some internal recognizer that is literally like a kpk bitbase. Most of the positions are solved with heuristics, and the rest from a simple retrograde analysis. It builds at startup almost instantaneously.

In fact, Gaviota without TBs should see this earlier than 16 plies unless I am missing something. I will take a look.

Do you mean that your recognizer covers kpk only? I think that in this test position only a small portion of the tree is spent at kpk positions. I can imagine that there are more kqkp positions being visited in a non-TB search. E.g. the main line you gave ends up in this position:

[d]8/5kPK/8/8/8/3p4/8/8 b - - 1 7

where kpk recognizers would not help very much IMO.

Sven

Good observation and that it will explain why it sees it at ply 16 and not earlier. kpk helps in the "main" (main as in what a human player considers as critical, conceptually) line: Rxg5 fxg5/ g7 Kf7/ Kf5 Kg8/ Kg4 Kf7/ Kxg5 Kxg7/ Kf5 Kf7/ Kxe5. It takes a lot of plies to know that this position is absolutely won without proper knowledge, recognizers, or bitbases. KPK may be helping in those side lines.

Miguel

[michiguel]

I have my own tablebase generator for my engine Gaviota with all 5 pieces (not compressed). There is implemented some sort of a cache system to reduce access to disk (64Mb but only a fraction is filled in the following position). There is a lot of room for improvement but it seems that is working fine.

Testing with this position (Best move Rxg5!)

[d]8/8/4kpP1/4p1n1/4K3/3P2R1/8/8 w - - 0 1

I had these results. Looks like it is most convenient to probe the tablebases when the depth remaining is more than 2. It does not diminish the node rate and there is a clear benefit. The efficiency of hits of the table base cache is about 80%.

Code: Select all

--------------------------------------
 Probing     Rate      Solution
 depth       knps    ply     time (s)
-------------------------------------
 all         167      8       0.3
 >1          355      9       0.9
 >2          568     10       0.8
 >3          564     11       2.7
 >4          564     12       5.6
 None        614     16     476.3
--------------------------------------

Of course, this is just one position. Is there a good test suite? Is the probing depth what other people are doing? Any opinions on this? Is there a position that is particularly harsh for the hard drive that I can test?

I guess this must have been thoroughly tested with Nalimov's tables. Note that mine are not compressed (at least yet, I am not sure it is worth the trouble for speed purposes).

When the probing depth is > 2 the output Gaviota has is at the end.

The solution is tricky and very instructive 1. Rxg5 fxg5 2. g7 Kf7 3. Kf5! Kg8! 4. Kg4!! Kf7 5. Kxg5 e4! 6. Kh6! exd3 7. Kh7 and white wins.

if 3 ... Kxg7 4. Kxg5 wins easily
if 4. Kxg5 Kxg7 is a draw
if 6. dxe4 Kxg7 is a draw

Without 1. Rxg5 is hard to see a win for white, and it most likely is a draw after the g6 pawn falls (Ke7-Kf8-Kg7).

Code: Select all

         2   1       0.0    +0.23  1.Rxg5 fxg5
         3   1       0.0    +1.73  1.Ke3
         3   1:      0.0    +1.73  1.Ke3
        35   2       0.0    +1.96  1.Ke3 Ke7
        62   2:      0.0    +1.96  1.Ke3 Ke7
       197   3       0.0    +1.82  1.Ke3 Ke7 2.Rg2
       268   3:      0.0    +1.82  1.Ke3 Ke7 2.Rg2
       652   4       0.0    +1.68  1.Ke3 Ke7 2.Rg2 Kf8
       780   4:      0.0    +1.68  1.Ke3 Ke7 2.Rg2 Kf8
      2423   5       0.0    +1.88  1.Ke3 Ke7 2.Rg2 Ke6 3.Rf2
      2759   5:      0.0    +1.88  1.Ke3 Ke7 2.Rg2 Ke6 3.Rf2
      7141   6       0.0    +2.03  1.Ke3 Ke7 2.Rg2 Ke6 3.Rg1 Ke7
      7682   6:      0.0    +2.03  1.Ke3 Ke7 2.Rg2 Ke6 3.Rg1 Ke7
     24661   7       0.0    +1.75  1.Ke3 Ke7 2.Rg4 Kf8 3.d4 exd4+ 4.Rxd4
                                   Ne6
     25387   7:      0.1    +1.75  1.Ke3 Ke7 2.Rg4 Kf8 3.d4 exd4+ 4.Rxd4
                                   Ne6
     33010   8       0.1      :-(  1.Ke3
     34195   8       0.1      :-(  
     73631   8       0.1    +1.01  1.Ke3 Ke7 2.d4 exd4+ 3.Kf4 Kf8 4.Kf5
                                   Kg7 5.Rb3
     74229   8:      0.1    +1.01  1.Ke3 Ke7 2.d4 exd4+ 3.Kf4 Kf8 4.Kf5
                                   Kg7 5.Rb3
    158161   9       0.3    +1.30  1.Ke3 Ke7 2.d4 exd4+ 3.Kf4 Kf8 4.Ra3
                                   Ke7 5.Ra7+ Ke6 6.g7 Nh3+ 7.Ke4
    163879   9:      0.4    +1.30  1.Ke3 Ke7 2.d4 exd4+ 3.Kf4 Kf8 4.Ra3
                                   Ke7 5.Ra7+ Ke6 6.g7 Nh3+ 7.Ke4
    372703  10       0.8    +1.66  1.Ke3 Ke7 2.d4 exd4+ 3.Kf4 Ne6+ 4.Kf5
                                   Ng7+ 5.Ke4 Kd6 6.Rf3 f5+ 7.Kxd4 Ne6+
                                   8.Ke3
    381458  10       0.8      :-)  1.Rxg5
    381912  10       0.8      :-)  1.Rxg5
    382371  10       0.8      :-)  1.Rxg5
    668535  10       1.4      :-)  1.Rxg5
    671883  10       1.4  +Mat_24  1.Rxg5 fxg5 2.g7 Kf7 3.Kf5 Kg8 4.Kg4
                                   Kf7 5.Kxg5 <EMPTY> <=TRANS
    671885  10:      1.4  +Mat_24  1.Rxg5 fxg5 2.g7 Kf7 3.Kf5 Kg8 4.Kg4
                                   Kf7 5.Kxg5 <EMPTY> <=TRANS
    671891  11       1.4  +Mat_24  1.Rxg5 fxg5 2.g7 <=TRANS
    754371  11:      1.5  +Mat_24  1.Rxg5 fxg5 2.g7 <=TRANS
    754377  12       1.5  +Mat_24  1.Rxg5 fxg5 2.g7 <=TRANS
    938202  12:      1.8  +Mat_24  1.Rxg5 fxg5 2.g7 <=TRANS
    938208  13       1.8  +Mat_24  1.Rxg5 fxg5 2.g7 <=TRANS
   1518511  13:      2.8  +Mat_24  1.Rxg5 fxg5 2.g7 <=TRANS
   1518517  14       2.8  +Mat_24  1.Rxg5 fxg5 2.g7 <=TRANS
   3071098  14:      5.3  +Mat_24  1.Rxg5 fxg5 2.g7 <=TRANS
   3071104  15       5.3  +Mat_24  1.Rxg5 fxg5 2.g7 <=TRANS

I am not quite sure I follow. Do you have _all_ 5 piece endings available? If so, why is the hit rate 80%? It should be 100% assuming

I have all 5 piece endings.
For now, in this first experiment, I probed when I had 5 pieces or less (having all 5 piece endings I do not need to specify to probe just after a capture).

What I meant is for 100 times I probe them, 80 times I find the solution is my own implemented cache, and 20 times I have to go to the disk (which might be in its own cache but I do not know).
I start with the cache completely empty, so most of the first probes are not going to hit my cache.

Is this number reasonable?

(1) you only probe after a capture or promotion;

(2) you only probe when you have 5 pieces or less.

as far as the probing depth goes, I have to tune this for the hardware I use. My 15K scsi drives are very fast, both seeking and latency delays. On those I can probe deeper in the tree, but I still restrict it to the first N plies of the search where N is the nominal search depth before extensions.

[Dann Corbit]

By hit and miss for TB probe, what is usually meant is:
hits == "I found this position when I probed"
misses == "I failed to find this position"
You might add additional stats for:
hash tb hits
hash tb misses
if you want to use the 'usual' nomenclature.

The:
misses == "I failed to find this position"
nomenclature is quite useful if you are missing some tablebase files (which is likely in the 6 man case and certain in the seven man case)

[rjgibert]

if 3 ... Kxg7 4. Kxg5 wins easily
if 4. Kxg5 Kxg7 is a draw
if 6. dxe4 Kxg7 is a draw

Surely, you meant to say:

if 4.Kxg5 e4 is a draw

Yes?

[michiguel]

if 3 ... Kxg7 4. Kxg5 wins easily
if 4. Kxg5 Kxg7 is a draw
if 6. dxe4 Kxg7 is a draw

Surely, you meant to say:

if 4.Kxg5 e4 is a draw

Yes?

Yes, I hate typing chess variations. e4/ dxe4 and now Kxg7 is a draw. In the other line, e4 does not work because of Kh6, which here does not make sense because the king is in g8.

Miguel