Gaviota's Endgame Tablebases

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
michiguel
Posts: 6401
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Gaviota's Endgame Tablebases

Post by michiguel » Sun Dec 07, 2008 10:53 pm

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&#58;      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&#58;      1.5  +Mat_24  1.Rxg5 fxg5 2.g7 <=TRANS
    754377  12       1.5  +Mat_24  1.Rxg5 fxg5 2.g7 <=TRANS
    938202  12&#58;      1.8  +Mat_24  1.Rxg5 fxg5 2.g7 <=TRANS
    938208  13       1.8  +Mat_24  1.Rxg5 fxg5 2.g7 <=TRANS
   1518511  13&#58;      2.8  +Mat_24  1.Rxg5 fxg5 2.g7 <=TRANS
   1518517  14       2.8  +Mat_24  1.Rxg5 fxg5 2.g7 <=TRANS
   3071098  14&#58;      5.3  +Mat_24  1.Rxg5 fxg5 2.g7 <=TRANS
   3071104  15       5.3  +Mat_24  1.Rxg5 fxg5 2.g7 <=TRANS

User avatar
hgm
Posts: 24957
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Gaviota's Endgame Tablebases

Post by hgm » Mon Dec 08, 2008 10:52 am

How do you define 'solution time'? Is that the time it takes before it finds the winning move, or before it finds the nearest checkmate?

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! :shock: Do you have recognizers for Pawn endings?

bob
Posts: 20918
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Gaviota's Endgame Tablebases

Post by bob » Mon Dec 08, 2008 4:38 pm

michiguel wrote: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 &#40;s&#41;
-------------------------------------
 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&#58;      0.0    +1.73  1.Ke3
        35   2       0.0    +1.96  1.Ke3 Ke7
        62   2&#58;      0.0    +1.96  1.Ke3 Ke7
       197   3       0.0    +1.82  1.Ke3 Ke7 2.Rg2
       268   3&#58;      0.0    +1.82  1.Ke3 Ke7 2.Rg2
       652   4       0.0    +1.68  1.Ke3 Ke7 2.Rg2 Kf8
       780   4&#58;      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&#58;      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&#58;      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&#58;      0.1    +1.75  1.Ke3 Ke7 2.Rg4 Kf8 3.d4 exd4+ 4.Rxd4
                                   Ne6
     33010   8       0.1      &#58;-(  1.Ke3
     34195   8       0.1      &#58;-(  
     73631   8       0.1    +1.01  1.Ke3 Ke7 2.d4 exd4+ 3.Kf4 Kf8 4.Kf5
                                   Kg7 5.Rb3
     74229   8&#58;      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&#58;      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      &#58;-)  1.Rxg5
    381912  10       0.8      &#58;-)  1.Rxg5
    382371  10       0.8      &#58;-)  1.Rxg5
    668535  10       1.4      &#58;-)  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&#58;      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&#58;      1.5  +Mat_24  1.Rxg5 fxg5 2.g7 <=TRANS
    754377  12       1.5  +Mat_24  1.Rxg5 fxg5 2.g7 <=TRANS
    938202  12&#58;      1.8  +Mat_24  1.Rxg5 fxg5 2.g7 <=TRANS
    938208  13       1.8  +Mat_24  1.Rxg5 fxg5 2.g7 <=TRANS
   1518511  13&#58;      2.8  +Mat_24  1.Rxg5 fxg5 2.g7 <=TRANS
   1518517  14       2.8  +Mat_24  1.Rxg5 fxg5 2.g7 <=TRANS
   3071098  14&#58;      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

(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.

bob
Posts: 20918
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Gaviota's Endgame Tablebases

Post by bob » Mon Dec 08, 2008 4:43 pm

hgm wrote:How do you define 'solution time'? Is that the time it takes before it finds the winning move, or before it finds the nearest checkmate?

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! :shock: Do you have recognizers for Pawn endings?
Are you asking about finding the mate with endgame tables?

Uri Blass
Posts: 8794
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Gaviota's Endgame Tablebases

Post by Uri Blass » Mon Dec 08, 2008 5:41 pm

I think that Ke3 also wins
1.Ke3 Ke7 2.Rg4 Kf8 3.d4 so the position is not good test position.

User avatar
hgm
Posts: 24957
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Gaviota's Endgame Tablebases

Post by hgm » Mon Dec 08, 2008 5:58 pm

bob wrote: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.

bob
Posts: 20918
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Gaviota's Endgame Tablebases

Post by bob » Mon Dec 08, 2008 8:38 pm

hgm wrote:
bob wrote: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.
OK. My program certainly won't find that mate with a 16 ply search...

User avatar
michiguel
Posts: 6401
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: Gaviota's Endgame Tablebases

Post by michiguel » Mon Dec 08, 2008 9:32 pm

hgm wrote:How do you define 'solution time'? Is that the time it takes before it finds the winning move, or before it finds the nearest checkmate?
When it fails high. In this case, when the fail high is resolved, it finds the move and the shortest mate.
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! :shock: 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.

Miguel

Sven
Posts: 3882
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Gaviota's Endgame Tablebases

Post by Sven » Mon Dec 08, 2008 9:34 pm

Uri Blass wrote:I think that Ke3 also wins
1.Ke3 Ke7 2.Rg4 Kf8 3.d4 so the position is not good test position.
Hi Uri,

maybe you are right stating that White wins also with your line (probably you want to reply to 3...exd4 with 4.Kf4! followed by 5.Kf5 with the idea Rd4-d7). But do you think it is a tablebase win in 24 moves (like 1.Rxg5) or even less? I don't think so since Gaviota would have found it. And even if it were, the position would still remain a good test position for the purpose of checking tablebase code since after 1.Rxg5 you get a 6-men pawn ending that frequently converts into 5-men very quickly.

Perhaps Miguel can tell us whether Gaviota finds a tablebase win in your line.

Sven

User avatar
michiguel
Posts: 6401
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: Gaviota's Endgame Tablebases

Post by michiguel » Mon Dec 08, 2008 9:42 pm

bob wrote:
hgm wrote:
bob wrote: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.
OK. My program certainly won't find that mate with a 16 ply search...
Mine neither if I deactivate the recognizer that I mentioned in a response to HGM.

Miguel

Post Reply