ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

End-game evaluation
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
H.G.Muller



Joined: 10 Mar 2006
Posts: 12765
Location: Amsterdam
PostPost subject: Re: End-game evaluation    Posted: Tue Nov 08, 2011 10:14 pm Reply to topic Reply with quote
For 4 pieces a complete retrograde analysis on 8x8, even just for the first few moves, is probably too costly. Reason is that there are usually lots of edge mates, almost all non-forcible, and even just identifying these mates takes a significant fraction of the time needed to build the entire EGT. But I guess it would be good enough for the first few iterations to only consider positions with the white King on a3,b3,c3, the black King on c2,c1,b1,a1,a2,a3, and the white pieces everywhere. That should tell you if the pieces in principle are able to perform the final mating steps. You would find that two Dababbas can do it, though:

[d]6R1/8/8/8/K7/8/8/k5R1 w
   ::    ::    :: WR ::
::    ::    ::    ::    
   ::    ::    ::    ::
::    ::    ::    ::    
WK ::    ::    ::    ::
::    ::    ::    ::    
   ::    ::    ::    ::
BK    ::    ::    WR    

Mate in 11 with 2 Dababbas

1. Kb3 Kb1 2. De1 {closes the trap} Ka1 3. Dc1+ Kb1 4. Dc3 Ka1 5. De8 Kb1 6. Dc8 Ka1 7. Da8 Kb1 8. Da6 Ka1 9. Kb2! {triangulates} Ka2 10. Da4+ Ka1 11. Da3#

But as you can see from the complete statistics only 680 out of 2M btm positions are won:

Code:
KDD_K

                 like          unlike
WON.wtm   346220     371840
K capture   346220     368584
other            0       3256
  0.       1823704    1881164
 10.             0         16
 11.             0          8
 12.             0         16
 13.             0         32
 14.             0        176
 15.             0         52
 16.             0        240
 17.             0         32
 18.             0         96
 19.             0          4
 20.             0          8
WON.btm          0        680
stalemate      456        348
W check      51712      54192
LEGAL      1824160    1882192
TOTAL      1875872    1936384


The beginning of this does not really differ spectacularly from what you see with Camel + Wazir, though:

Code:
KCW_K

WON.wtm    3781436
K capture   809720
other      2971716
  0.        737536
 10.            84
 11.            18
 12.            26
 13.           122
 14.           172
 15.           396
 16.           308
 17.           730
 18.          1048
 19.          1492
 20.          1121
 21.          1267
 22.           698
 23.          1109
 24.           936
 25.          1001
 26.          1441
 27.          1231
 28.          1490
 29.          1500
 30.          1267
 31.          1178
 32.          1146
 33.          1232
 34.           563
 35.           608
 36.           809
 37.          1499
 38.          1177
 39.           560
 40.           248
 41.           199
 42.           404
 43.           440
 44.           154
 45.           330
 46.           264
 47.           210
 48.           514
 49.           410
 50.           720
 51.          1224
 52.          2450
 53.          2650
 54.          3470
 55.          4504
 56.          5796
 57.          9145
 58.         11572
 59.         14216
 60.         20626
 61.         32617
 62.         47723
 63.         63105
 64.         91688
 65.        127635
 66.        175735
 67.        225274
 68.        271017
 69.        301921
 70.        310095
 71.        285314
 72.        238836
 73.        177634
 74.        111629
 75.         64539
 76.         33995
 77.         16270
 78.          8608
 79.          5433
 80.          3632
 81.          2056
 82.          1071
 83.           473
 84.           214
 85.           112
 86.            30
 87.            10
WON.btm    2702441
stalemate     1937
W check     370342
LEGAL      3441914
TOTAL      3812256


There are still only 154 mate-in-34 positions (counting starts at 10 in my generator for technical reasons), and at that point it is not clearat all this is a generally won end-game. What you saw upto then is a lengthy and cumbersome drive of the bare King from the wrong corner into the right one. (Camel is color-bound, neither Wazir or Camel can move from c1 to a1 in 3 moves, but Camel can attack a1 and c1 at the same time in its own corner, while Wazir can move from c1 to b1 in 3 moves, so an edge-mate is possible there, and only there.) That you can drive the bare King to the edge at all turns out only later, and requires another 25 moves or so. But in the end 70% of all btm and 99% of all wtm positions is won.

Compare that to Zebra+Ferz:

Code:
KZF_K

WON.wtm     832447
K capture   754740
other        77707
  0.       3670601
 10.            53
 11.            40
 12.            25
 13.            48
 14.            96
 15.           124
 16.           179
 17.           272
 18.           428
 19.           410
 20.           820
 21.           832
 22.           910
 23.           748
 24.           596
 25.           876
 26.          1064
 27.           792
 28.           592
 29.           311
 30.           412
 31.           499
 32.           294
 33.           326
 34.           361
 35.           258
 36.           148
 37.           142
 38.            97
 39.            90
 40.            90
 41.           162
 42.           290
 43.           322
 44.           704
 45.           592
 46.          1636
 47.           661
 48.          1166
 49.           392
 50.           596
 51.           159
 52.           214
 53.            35
 54.            81
 55.             6
 56.             6
WON.btm      18955
stalemate     1602
W check     121098
LEGAL      3691158
TOTAL      3812256


Here there are 159 mate-in-41 positions, and what happened until then does not seem so different from the KCWK case. But unlike the latter,it quickly peters out after that, and not even 0.5% of all btm positions is won. It is really not possible to tell the C+W can do the drive before the system becomes super-critical after 38 iterations, and that Z+F cannot do it before you reach iteration 45...

So I guess there is no shortcut for building the entire tablebase. It should be possible to do that significantly faster than the released version does it. (But the highly optimized version, which could do a 4-men in about 2 sec, was a DTM generator not supporting slider/leaper compouds.)
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Subject Author Date/Time
End-game evaluation H.G.Muller Tue Oct 04, 2011 11:44 am
      Re: End-game evaluation Evert Glebbeek Tue Oct 04, 2011 1:02 pm
            Re: End-game evaluation H.G.Muller Tue Oct 04, 2011 2:20 pm
      Re: End-game evaluation Oliver Uwira Tue Oct 04, 2011 1:59 pm
      Re: End-game evaluation Jon Dart Tue Oct 04, 2011 2:10 pm
            Re: End-game evaluation Jon Dart Tue Oct 04, 2011 2:13 pm
      Re: End-game evaluation Kevin Hearn Tue Oct 04, 2011 8:19 pm
            Re: End-game evaluation Pawel Koziol Wed Oct 05, 2011 10:46 am
      Re: End-game evaluation H.G.Muller Mon Oct 10, 2011 8:09 am
            Re: End-game evaluation H.G.Muller Mon Oct 10, 2011 9:00 am
                  Re: End-game evaluation Evert Glebbeek Mon Oct 10, 2011 1:04 pm
                  Re: End-game evaluation Ed Schroder Mon Nov 07, 2011 10:15 pm
            Re: End-game evaluation H.G.Muller Wed Oct 19, 2011 10:16 am
                  Re: End-game evaluation Michael Hoffmann Wed Oct 19, 2011 11:48 am
                        Re: End-game evaluation H.G.Muller Wed Oct 19, 2011 1:24 pm
                              Re: End-game evaluation Michael Hoffmann Wed Oct 19, 2011 2:53 pm
                                    Re: End-game evaluation Volker Annuss Wed Oct 19, 2011 4:53 pm
                                    Re: End-game evaluation H.G.Muller Wed Oct 19, 2011 4:54 pm
                                          Re: End-game evaluation H.G.Muller Sat Oct 22, 2011 5:29 pm
                                                Re: End-game evaluation H.G.Muller Mon Nov 07, 2011 7:28 pm
                                                      Re: End-game evaluation Evert Glebbeek Mon Nov 07, 2011 8:33 pm
                                                            Re: End-game evaluation Evert Glebbeek Mon Nov 07, 2011 9:02 pm
                                                                  Re: End-game evaluation H.G.Muller Mon Nov 07, 2011 9:40 pm
                                                            Re: End-game evaluation H.G.Muller Tue Nov 08, 2011 11:16 am
                                                                  Re: End-game evaluation Evert Glebbeek Tue Nov 08, 2011 5:50 pm
                                                                        Re: End-game evaluation H.G.Muller Tue Nov 08, 2011 8:16 pm
                                                                              Re: End-game evaluation Evert Glebbeek Tue Nov 08, 2011 8:52 pm
                                                                                    Re: End-game evaluation H.G.Muller Tue Nov 08, 2011 10:14 pm
                                                      Re: End-game evaluation Karlo Bala Jr. Mon Nov 07, 2011 11:59 pm
                                                            Re: End-game evaluation H.G.Muller Tue Nov 08, 2011 7:30 am
                                                                  Re: End-game evaluation Kevin Hearn Tue Nov 08, 2011 9:58 am
                                                                        Re: End-game evaluation H.G.Muller Tue Nov 08, 2011 12:40 pm
                                                                              Re: End-game evaluation Evert Glebbeek Tue Nov 08, 2011 5:53 pm
      Re: End-game evaluation Mark Lefler Mon Oct 10, 2011 4:08 pm
            Re: End-game evaluation H.G.Muller Mon Oct 10, 2011 9:09 pm
                  Re: End-game evaluation H.G.Muller Mon Oct 10, 2011 9:58 pm
                  Re: End-game evaluation H.G.Muller Tue Oct 11, 2011 8:50 am
                        Re: End-game evaluation H.G.Muller Tue Oct 18, 2011 6:36 pm
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads