Probe EGT in quiescence?

[noobpwnftw]

Certainly it does contain those basic combinations you've mentioned, they are essential to any bigger tablebases. But there isn't any download page, are you referring to the list pages?

If so, loading the list pages would take a while (~3mb in html), perhaps you can try refreshing and wait a bit. Also, they are ordered by (defending of) attacking pieces, not alphabetically, so try searching for the word "KPK", "KAABBRKAABB" within the page. Combinations without attacking pieces for both sides(e.g. KAK, KAKB) are omitted since they are always draw.

I provide FTP download for the tablebases, with cyclone's free generator & probing tool. Current size for DTC tablebases alone is 6.51 TB of 7900 combinations.

[hgm]

It is OK since the second one is a draw - any move is actually acceptable. However I think draw is one of the big problems for endgame searching. All moves could lead to the draw, the search cannot narrow the tree. It could spend too much time but cannot make the right conclusions.

In KRKEEAA the default assumption is draw. So in a drawn position the result will be correct no matter how shallow the search is. It is only the wins that need to be recognize. You always have this problem when you use EGT, and are at the point where the search reaches them. If the root is still outside the EGT, but can only force entry of the EGT in drawn positions, it will refuse to convert if the heuristic eval suggests something better than draw. E.g. if you have KR*K*, but not KR*KP*, and you are in a drawn KRKPEEAA position, it will refuse to take the Pawn, to keep up the delusion that it is ahead. And it is not difficult avoiding to take the Pawn forever. The knowledge that certain KRK* positions are drawn can only propagate to earlier stages of the game if the predecessors evaluate them as drawish too. Erring towards a draw is not fatal, because the winning side must by definition be able to force a winning conversion in a finite number of moves, so the search will eventually find it. But usually there is no way to force the strong side to make a drawing conversion.

The KRK* EGT can be usefully employed for this, however: you can probe it in KRKP* positions, omitting the Pawn, and if it is a draw there, apply a drawishness correction to the heuristic eval. Then only positions that would be won without the Pawn remain 'unclear'. They could be draw, when the Pawn gives the weak side the opportunity to avoid zugzwangs that would otherwise be losing, and making a detour to get the Pawn would give him the time he needs to reorganize his defenders into a non-losing constellation. But the Rook side cannot stay in such unclear positions forever, then, because stalling with pointless moves would allow the weak side to reorganize his defense anyway.

This is really not any different when you approach a partial EGT through positions in the part that was omitted. You have to score such positions as drawish.

Also the second position is quite close to the first one. If your EGT have not enough sophisticated information, it may make your engine get hard for one of them.

Well, the idea is to store enough information to allow a shallow search to find a win, if there is one, and assume draw by default. The position you give seems to need a very large amount of manoeuvring with the Rook before the Advisors and Elephant can be moved out of the Palace files.

Note that this is relatively rare. Of the 119 Palace states (Kings and Advisors) 36 already satisfy the equivalence condition (King in front of all Advisors). And 22 out of the 29 Elephant states satisfy it (e2 empty). So a quite substantial fraction of KR*K* is in fact identical to KRK*, which in itself again can ignore the King rank. Most other positions are just a few moves removed from it. Elephant obstruction can always be cured in a single move. And 21 Palace states can be cleared in a single move (stepping the King forward, or withdrawing an Advisor).

The question is whether you will have time to make this moves without losing a win you would have without the obstruction. Position 3 shows that this can be quite long, preventing you to find the win in an acceptable search depth. But it should be possible to cure this in a way far cheaper than adding a complete set of defenders to the strong side. Note that if Rook manoeuvring is required, it can usually be done entirely on the opponent half, so that it is not affected by its own defenders. So KR'*K*, which is half the size of KR*K* because it omits positions with the Rook on its own half, would probably never need more than just a few moves to be reached. (Position 3 is already in it.) Within this, there are only two different Elephant states: e2 occupied, or e2 empty. All EEAA constellations with e2 empty are equivalent, and so are all positions with an Elephant there. So instead of 29 Elephant states, you have only 2, saving a factor 14.5. The Advisors are a bit more cumbersome; if I counted right the 119 Palace states fall in 68 equivalence classes. (This assumes it is never useful to obstruct a King that already had a clear view.) But that is still nearly a factor 2.

The third position is one of the longest mate for KR*K*. That is why your engine was struggling. However it is not the hardest one for search function. There are many positions have longer distance for the first capture.

Well, as mentioned before the distance to the first capture is irrelevant. What makes it difficult is that you need so many Rook moves before you can move away the Elephant.

Come one. You are going to WCCC this year to win, aren't you?

I will of course go to the Olympiad, since it is practically next door, but there is no chance at all that I would win. Last year I ended last place of 4 (with 0 points), and I haven't done any work on the program since then. The year before (2015) I had a won KR*K* end-game against XieXie, but it was too difficult for the engine; this is why I added the EGT. But XieXie was rewritten, and in 2016 even beat Chimo. The problem is that my evaluation sucks. HaQiKi D could have drawn one game against Chimo last year, by taking a Pawn in KRPPEEKRPEAA ( 2eak4/4a1P2/9/8p/9/4r3P/9/E3E4/9/1R1K5 b 0 54 ), but it preferred to take the two Elephants instead.

It is doable. I don't have the real number atm (my EGT data stored in several hard disks in uncompressed format) but for roughly estimating, all above two attacking pieces may be compressed from 170 GB into under 20 GB. If they are in WDL format, they may take totally < 10 GB. It is loadable into memory of many model computers.

Well, my biggest machine has 8 GB. And the EGT only seem to serve the purpose to know more precisely in how many moves it will be checkmated, if I wouldn't make the evaluation less stupid. Currently it prefers lost end-games over drawn ones way before it enters the EGT stage. Although KRP*KRP* might have saved the game against Chimo. But I suppose that one is not included in the 10GB set you mention...

[hgm]

I had a look at a simplified version of position 3, where I left out one Elephant and one Advisor (only those at e1 and e2 remained: 2e6/R3ak3/5a3/9/2e6/9/9/4E4/4A4/3K5 w 0 1 ). Even then, finding the mate takes 87 min. It takes 33 ply before it enters the partial EGT:

Code: Select all

 34	  #42 	3.72G	1:27:00	a8a5 c9a7 a5b5 e8d9 b5b7 f7e8 b7i7 f8f9 i7i9 f9f8 i9i5 f8f9 i5f5 f9e9 f5e5 e9f9 e1f0 e8d7 e5h5 d7e8 h5f5 f9e9 f5e5 e9f9 e2c4 e8d7 e5h5 d9e8 h5h7 f9e9 d0e0 e9f9 e0e1 
 33	+16.52 	2.00G	45:17.22	a8a5 c9a7 a5b5 e8d9 b5b7 f7e8 b7i7 f8f9 i7i9 f9f8 i9i5 f8f9 i5f5 f9e9 f5e5 e9f9 e2c4 e8d7 e5h5 d7e8 h5f5 f9e9 f5e5 e9f9 d0d1 e8d7 e5h5 d9e8 h5h9 f9f8 h9h7 a7c9 h7h8 f8f9 h8h9 f9f8 h9c9 c5e7 c9c6 e7c9 
 32	+15.40 	157.7M	32:23.32	a8a5 c9a7 a5b5 e8d9 b5b7 f7e8 b7i7 f8f9 i7i9 f9f8 i9i5 f8f9 i5f5 f9e9 f5e5 e9f9 e2c4 e8d7 e5h5 d7e8 h5f5 f9e9 f5e5 e9f9 d0e0 e8d7 e5i5 d7e8 i5f5 f9e9 f5e5 e9f9 e1f0 a7c9 e5c5 f9e9 
 31	+15.04 	3.48G	25:23.38	a8a5 c9a7 a5b5 e8d9 b5b7 f7e8 b7i7 f8f9 i7i9 f9f8 i9i5 f8f9 i5f5 f9e9 f5e5 e9f9 d0e0 e8d7 e5f5 f9e9 f5h5 d7e8 e0f0 e8f9 h5e5 d9e8 f0e0 e9d9 e1f0 e8d7 e0d0 a7c9 e5c5 c9e7 c5e5 
 30	+1.88 	2.39G	17:29.14	a8a5 c9a7 a5b5 e8d9 e2g4 f8f9 d0d1 f9e9 d1d2 c5e7 b5b6 f7e8 b6f6 a7c9 f6c6 e8f9 e1f0 d9e8 g4i2 c9a7 i2g0 a7c5 c6d6 e7c9 g0i2 c9e7 d6b6 e8d9 i2g0 f9e8 

I took a look at the line it found, to see how it is done. It seems that it is possible to force a critical position, where white could afford a turn pass without losing the win, using nothing else than the Rook. (R:e5, K:f9, A:e8,d9, E:a7,c5). White then uses his 'free move' to open up the Palace files for his King.

It seems to me it should be possible to build an EGT of RK* (so without white King), which describes how far away you are from reaching such a position where white can afford a tempo loss, and have white play according to this EGT as long as his King is obstructed. Once he reaches the critical position, he then does the next move to 'expose' his King. If the King is then completely exposed, he can start playing according to KRK*. If more moves are required to expose it, he keeps using the EGT for reaching the critical position again.

This is formaly similar to DTC tables: you can split up the entire KR*K* EGT into segments that differ in the number of moves it takes to completely expose the King (the 'obstruction number'). In the original position 3 this was 5 moves: one for the Elephant, one to withdraw the Advisor on e1, two to withdraw the Advisor on d2, and one to step the King in front of the Advisors. Assuming that it is never needed to decrease the exposure, the moves that alter the obstruction number can be treated as irreversible moves, and the segments of different obstruction number as separate EGT. A move that lowers the obstruction number is then a 'conversion' between those EGTs.

So you would have KR0K* = KRK*, KR1K*, ..., KR6K*. My suspicion is that all KRnK* with n>0 could be equal to each other. They would contain the DTE: Distance To Exposure. They could be built under the worst-case assumption, that black is totally unhindered by the white King. When this is not the case in reality, black sometimes cannot do the move that the EGT would have considered optimal defense, and the DTE would decrease more than a single move on that turn. As it seems that forcing the critical position in general should be done with the Rook on the enemy half, to keep the Elephants under attack and threaten sideway checks at the same time to skewer King and Advisor, only the parts of the EGT with the Rook on the enemy half are needed. Which is a good thing, because only these are independent of the constellation of strong-side defenders.

If this scheme works, all that is needed is a K"R'K* DTM EGT (3*45*29*119 = 466K positions for black-to-move), and a R'K* DTE EGT (45*29*119 = 155K positions). The DTM can be pessimistically estimated as the maximum DTM of KRK* plus n times the maximum DTE of RK*, where n is the obstruction number.

[phhnguyen]

Certainly it does contain those basic combinations you've mentioned, they are essential to any bigger tablebases. But there isn't any download page, are you referring to the list pages?

I knew you have full basic EGTs since I have visited your page of EGTs, found some and check their sizes already (what is my most concerned at the moment ).

I am just curious how commercial engines (such as cyclone) contribute and use EGTs. is its home page www . ccyclone . com ? From that I found a link to the page https : // pan.baidu . com/s/1hq1XCcW#list/path=%2F which shows some EGTs with many attacking pieces involving but I cannot found basic ones (such as KRAKAA)

[noobpwnftw]

Certainly it does contain those basic combinations you've mentioned, they are essential to any bigger tablebases. But there isn't any download page, are you referring to the list pages?

I knew you have full basic EGTs since I have visited your page of EGTs, found some and check their sizes already (what is my most concerned at the moment ).

I am just curious how commercial engines (such as cyclone) contribute and use EGTs. is its home page www . ccyclone . com ? From that I found a link to the page https : // pan.baidu . com/s/1hq1XCcW#list/path=%2F which shows some EGTs with many attacking pieces involving but I cannot found basic ones (such as KRAKAA)

That one is also provided by me. It is a complete set, just organized in different folders due to file number limit(2k per folder).
Naming is also different, its K+(defender A->B)+attacker R->N->C->P so your KRAKAA would be named by KARKAA.

[phhnguyen]

In KRKEEAA the default assumption is draw. So in a drawn position the result will be correct no matter how shallow the search is. It is only the wins that need to be recognize. You always have this problem when you use EGT, and are at the point where the search reaches them. If the root is still outside the EGT, but can only force entry of the EGT in drawn positions, it will refuse to convert if the heuristic eval suggests something better than draw. E.g. if you have KR*K*, but not KR*KP*, and you are in a drawn KRKPEEAA position, it will refuse to take the Pawn, to keep up the delusion that it is ahead. And it is not difficult avoiding to take the Pawn forever. The knowledge that certain KRK* positions are drawn can only propagate to earlier stages of the game if the predecessors evaluate them as drawish too. Erring towards a draw is not fatal, because the winning side must by definition be able to force a winning conversion in a finite number of moves, so the search will eventually find it. But usually there is no way to force the strong side to make a drawing conversion.

The KRK* EGT can be usefully employed for this, however: you can probe it in KRKP* positions, omitting the Pawn, and if it is a draw there, apply a drawishness correction to the heuristic eval. Then only positions that would be won without the Pawn remain 'unclear'. They could be draw, when the Pawn gives the weak side the opportunity to avoid zugzwangs that would otherwise be losing, and making a detour to get the Pawn would give him the time he needs to reorganize his defenders into a non-losing constellation. But the Rook side cannot stay in such unclear positions forever, then, because stalling with pointless moves would allow the weak side to reorganize his defense anyway.

This is really not any different when you approach a partial EGT through positions in the part that was omitted. You have to score such positions as drawish.

Look like your solution is overcomplicated to me. If you don't have KR*KP* why you insist on probing the position KR*KP*? Just wait a bit more, the search may lead you to the right EGT you have when the "redundant" pieces get captured.

In other hand, probing KR*K* in a KR*KP* may give more trouble than gain. If you have a KR*KP* you must have subtables KR*K* and KP*K*, probing directly those subtables is much more simpler. Furthermore, KR*K* + KP*K* is much smaller on sizes, compared with KR*KP* (throw KR*KP* aways if you want to save space)

Well, my biggest machine has 8 GB. And the EGT only seem to serve the purpose to know more precisely in how many moves it will be checkmated, if I wouldn't make the evaluation less stupid. Currently it prefers lost end-games over drawn ones way before it enters the EGT stage. Although KRP*KRP* might have saved the game against Chimo. But I suppose that one is not included in the 10GB set you mention...

Upgrading memory is so cheap

All the best to you and your engines in WCCC

[phhnguyen]

I had a look at a simplified version of position 3, where I left out one Elephant and one Advisor (only those at e1 and e2 remained: 2e6/R3ak3/5a3/9/2e6/9/9/4E4/4A4/3K5 w 0 1 ). Even then, finding the mate takes 87 min. It takes 33 ply before it enters the partial EGT:

Look like your EGT is good when it could help your engine. However clearly it is not good enough to against traditional ones when those positions could be solved in microsecond. I think it is good enough only if you could reduce the time to under a minute.

Code: Select all

 34	  #42 	3.72G	1:27:00	a8a5 c9a7 a5b5 e8d9 b5b7 f7e8 b7i7 f8f9 i7i9 f9f8 i9i5 f8f9 i5f5 f9e9 f5e5 e9f9 e1f0 e8d7 e5h5 d7e8 h5f5 f9e9 f5e5 e9f9 e2c4 e8d7 e5h5 d9e8 h5h7 f9e9 d0e0 e9f9 e0e1 
 33	+16.52 	2.00G	45:17.22	a8a5 c9a7 a5b5 e8d9 b5b7 f7e8 b7i7 f8f9 i7i9 f9f8 i9i5 f8f9 i5f5 f9e9 f5e5 e9f9 e2c4 e8d7 e5h5 d7e8 h5f5 f9e9 f5e5 e9f9 d0d1 e8d7 e5h5 d9e8 h5h9 f9f8 h9h7 a7c9 h7h8 f8f9 h8h9 f9f8 h9c9 c5e7 c9c6 e7c9 
 32	+15.40 	157.7M	32:23.32	a8a5 c9a7 a5b5 e8d9 b5b7 f7e8 b7i7 f8f9 i7i9 f9f8 i9i5 f8f9 i5f5 f9e9 f5e5 e9f9 e2c4 e8d7 e5h5 d7e8 h5f5 f9e9 f5e5 e9f9 d0e0 e8d7 e5i5 d7e8 i5f5 f9e9 f5e5 e9f9 e1f0 a7c9 e5c5 f9e9 
 31	+15.04 	3.48G	25:23.38	a8a5 c9a7 a5b5 e8d9 b5b7 f7e8 b7i7 f8f9 i7i9 f9f8 i9i5 f8f9 i5f5 f9e9 f5e5 e9f9 d0e0 e8d7 e5f5 f9e9 f5h5 d7e8 e0f0 e8f9 h5e5 d9e8 f0e0 e9d9 e1f0 e8d7 e0d0 a7c9 e5c5 c9e7 c5e5 
 30	+1.88 	2.39G	17:29.14	a8a5 c9a7 a5b5 e8d9 e2g4 f8f9 d0d1 f9e9 d1d2 c5e7 b5b6 f7e8 b6f6 a7c9 f6c6 e8f9 e1f0 d9e8 g4i2 c9a7 i2g0 a7c5 c6d6 e7c9 g0i2 c9e7 d6b6 e8d9 i2g0 f9e8 

I took a look at the line it found, to see how it is done. It seems that it is possible to force a critical position, where white could afford a turn pass without losing the win, using nothing else than the Rook. (R:e5, K:f9, A:e8,d9, E:a7,c5). White then uses his 'free move' to open up the Palace files for his King.

It seems to me it should be possible to build an EGT of RK* (so without white King), which describes how far away you are from reaching such a position where white can afford a tempo loss, and have white play according to this EGT as long as his King is obstructed. Once he reaches the critical position, he then does the next move to 'expose' his King. If the King is then completely exposed, he can start playing according to KRK*. If more moves are required to expose it, he keeps using the EGT for reaching the critical position again.

This is formaly similar to DTC tables: you can split up the entire KR*K* EGT into segments that differ in the number of moves it takes to completely expose the King (the 'obstruction number'). In the original position 3 this was 5 moves: one for the Elephant, one to withdraw the Advisor on e1, two to withdraw the Advisor on d2, and one to step the King in front of the Advisors. Assuming that it is never needed to decrease the exposure, the moves that alter the obstruction number can be treated as irreversible moves, and the segments of different obstruction number as separate EGT. A move that lowers the obstruction number is then a 'conversion' between those EGTs.

So you would have KR0K* = KRK*, KR1K*, ..., KR6K*. My suspicion is that all KRnK* with n>0 could be equal to each other. They would contain the DTE: Distance To Exposure. They could be built under the worst-case assumption, that black is totally unhindered by the white King. When this is not the case in reality, black sometimes cannot do the move that the EGT would have considered optimal defense, and the DTE would decrease more than a single move on that turn. As it seems that forcing the critical position in general should be done with the Rook on the enemy half, to keep the Elephants under attack and threaten sideway checks at the same time to skewer King and Advisor, only the parts of the EGT with the Rook on the enemy half are needed. Which is a good thing, because only these are independent of the constellation of strong-side defenders.

If this scheme works, all that is needed is a K"R'K* DTM EGT (3*45*29*119 = 466K positions for black-to-move), and a R'K* DTE EGT (45*29*119 = 155K positions). The DTM can be pessimistically estimated as the maximum DTM of KRK* plus n times the maximum DTE of RK*, where n is the obstruction number.

I have seen some good points in your ideas. However, they needed to test thoroughly (I have dumped many ideas since they cannot pass the tests or gain too little when added more troubles). From my experience, you may need to build a full traditional EGT first, then test your new ideas by verifying results with that.

Good luck

[phhnguyen]

Assuming that it is never needed to decrease the exposure, the moves that alter the obstruction number can be treated as irreversible moves, and the segments of different obstruction number as separate EGT. A move that lowers the obstruction number is then a 'conversion' between those EGTs.

To help you a bit with your thought I show you the above assuming is not supported firmly. In the bellow board a decrease exposure (2. Ad0e1) is the shortest move to win. I think we may find out the cases when decrease exposure moves are compulsory to win too

Code: Select all

6e2/3ka4/5a2e/9/9/9/9/9/4R4/2EAK4 w 0 0
. . . . . . e . .  9
. . . k a . . . .  8
. . . . . a . . e  7
. . . . . . . . .  6
. . . . . . . . .  5
. . . . . . . . .  4
. . . . . . . . .  3
. . . . . . . . .  2
. . . . R . . . .  1
. . E A K . . . .  0
a b c d e f g h i  
0) Re1d1 1) ae8d7 2) Ad0e1 3) af7e8 4) Rd1c1 5) ae8f7 6) Ke0d0 7) kd8e8 8) Rc1d1 9) eg9e7 10) Ae1f0 11) ke8d8 12) Rd1d7 13) kd8e8 14) Kd0e0 15) ei7g5 16) Rd7d9 17) ke8f8 18) Rd9g9 19) eg5i7 20) Rg9g8 21) kf8f9 22) Rg8g7 23) ei7g9 24) Rg7f7 25) kf9e9 26) Ke0e1 27) ke9e8 28) Rf7g7 29) ke8d8 30) Rg7g8 31) kd8d9 32) Rg8e8 33) ee7c5 34) Re8e9 35) kd9d8 36) Re9g9 37) ec5e7 38) Rg9f9 39) kd8e8 40) Rf9f7 41) ke8d8 42) Rf7e7 43) kd8d9 44) Re7d7

[hgm]

Thanks for this position. I checked out the solution, because at first glance it seemed that after 2) Ke1 instead of 2) Ad0e1 you are immediately fully exposed, and can do everything with the King you could otherwise do, while black cannot. The point, however, is that in the fastest mate you want to put the Rook in front of the King to form a battery. So it hurts when K and R are on the same rank.

I don't think this is relevant for the proposed scheme, however. Because that scheme only involved the part of the EGT with the Rook on the enemy half (KR'K* and the auxiliary R'K*). In those the King can never obstruct the Rook. It would be up to the search to find the best moves while the Rook is still on its own half, and this could very well involve moves that decrease exposure. In some cases it might be possible to prune Elephant moves, like in the current example (but not for, say, an Elephant on a2 when the Rook is on a0, where moving the Elephant would be the only way to attack an Elephant on a7 in a single move).

So it would be very interesting to know if there are positions where it is necessary to decrease exposure with the Rook on the enemy half. Like you say, it might be necessary to search the full KR*K* for those. That should be feasible, though. It would be nice if there aren't any won positions where all winning moves decrease exposure. It would be even nicer if every won position always has at least one move that doesn't decrease exposure in its set of optimal moves.

The question the is how long it can take in the worst case before the Rook can be moved to the enemy half. I still believe that once the Rook is there, there never is any need to move it back to its own half, for an optimally fast mate. It seems it is always better to be on 6th rank than on any square on your own half, because from 6th rank you cannot be blocked from reaching c9 or g9. And if a tempo has to be wasted to apply zugzwang, it should always be possible to step the King along a file between 1st and 2nd rank if all defenders are on 0th rank, or pull back a defender if they aren't.

In the position you give the Rook only reaches the enemy half in the 13th ply. But it seems to me that 8) Rc1c7, attacking the Advisor from the side instead of the front, would be just as good, so that you could already hit the EGT with an optimal path after 9 ply. A sub-optimal path would only take 5 ply here.