Probe EGT in quiescence?

phhnguyen · Post by **phhnguyen** » Sun May 21, 2017 1:35 pm

hgm wrote: It doesn't matter how long it takes to convert. You don't search all the way to conversion, you only search until you enter the EGT. Even in a position with 4 defenders each this is often a matter of moving an Elephant away from e2, pulling back an Advisor from e1, stepping the King forward, and moving the Rook to the enemy half. That is only 9 ply. After that the EGT probe gives you the DTM. The static evaluation for KR*K* (used when there is no EGT hit) has a special term that encourages exposing the strong-side King, overruling its normal tendency to savely hide it behind defenders. This makes the search usually go for the most efficient move sequence straight away.

It is always OK if you are happy with your EGT

For me, I am not a fan of searching for endgames. As I have written some endgames require over 30 (not only 9 plies) correct moves for their first captures. My testing program gave up on that after searching a long time, say 1 h on my laptop (Intel core 7 2.5 G). Hope yours could do much better.

BTW, I have added few positions at the end of this post. Could you try with your EGT? If your program can solve them correctly, I will add some more difficult (I need time to search from my database).

A full KR*K* EGT is pretty big: my indexing scheme uses 119 'Palace states' and 29 'Elephant states', for a total of 3,451 defender constellations. (This includes 16*7 = 112 'broken positions' where an Elephant collides with a King, but this is too small a fraction to bother.) If I would also have that number of constellations for the KEEAA of the attacking side I would alread be at 11M (ignoring a few more broken positions because of King facing). Adding a Rook that can go anywhere then gives 1G positions (2G if you do both sides to move). Uncompressed that would be barely feasible on a machine with 4G RAM (which is still pretty common). And now try it for KHH*K*, where the confinement of the Horses to the enemy half is less perfect than with R, but still works pretty well. This would contain 90G positions. With my scheme K"H'H'K* (where H' indicates confinement to enemy half, and K" confinement to the back rank) only takes 10.5M positions. Because of the sizes the choice is often not between having full KX*K* or partial K"X'K* for everything, but between having K"X'K* for many X and having nothing at all for most X.

It seems all your sizes are a bit strange and different (larger) from mine. I use the work of Fang & Hsu (Construction of Chinese Chess Endgame databases by Retrograde Analysis).

There are totally 3339 combinations of defenders. All tables of an one-but-not-pawn-attacking-piece (say KR*K*) take only 550 MB for one side or 1100 MB (uncompressed) for 2 sides.

Total of all tables of HH (KHH*K*) is 23 GB (uncompressed) for one side.

All tables of two-attacking-pieces (CC, CH, CP, HH, HP, PP) but no Rook (since Rook + any piece is mostly a sure win) take about 170 GB for one side in uncompressed format.

Some positions for testing EGT:

noobpwnftw · Post by **noobpwnftw** » Sun May 21, 2017 6:40 pm

Probing DTx tablebases during search is not really necessary, you can simply probe WDL tablebases and give it a pesudo-mate score, then probe DTx tablebases when you actually reached that position.

I'm hosting a comprehensive set of DTC/DTM tablebases online, with a public query interface. Also accepting requests to build any useful set within 1TB memory size.

For your above positions:
1. http://www.chessdb.cn/query_en/?2b6/4a4 ... /2BRK4%20w
2. http://www.chessdb.cn/query_en/?2b6/4a4 ... BRK1B2%20w
3. http://www.chessdb.cn/query_en/?2b6/R3a ... /2B1K4%20w

Available set lists are here:
DTC: http://www.chessdb.cn/egtb_info.html
DTM: http://www.chessdb.cn/egtb_info_dtm.html

I hope this is useful for you.

hgm · Post by **hgm** » Sun May 21, 2017 7:19 pm

phhnguyen wrote:For me, I am not a fan of searching for endgames. As I have written some endgames require over 30 (not only 9 plies) correct moves for their first captures.

We are still not connecting. There is no need to search to the first capture. One only has to search up to the position where the extra defenders are moved out of the way, which in most positions is much earlier.

BTW, I have added few positions at the end of this post. Could you try with your EGT? If your program can solve them correctly, I will add some more difficult (I need time to search from my database).

These are indeed a bit harder. The first takes nearly 4 minutes (single core on my laptop):

Code: Select all

dep	score	nodes	time	&#40;not shown&#58;  tbhits	knps	seldep&#41;
 24	  #29 	1.96G	13&#58;33.33	e1f0 e7f7 d0d1 f7f8 d1f1 e8f7 e2g4 d7e8 e0e1 e8d7 e1e2 c9e7 d2e1 a7c5 f1f3 d7e8 f3i3 e8d7 i3i8 
 23	  #29 	1.00G	6&#58;59.32	e1f0 e7f7 d0d1 f7f8 d1f1 e8f7 e2g4 d7e8 e0e1 e8d7 e1e2 c9e7 f1f5 a7c5 d2e1 
 22	  #29 	538.7M	3&#58;41.93	e1f0 e7f7 d0d1 f7f8 d1f1 e8f7 e2g4 d7e8 e0e1 a7c5 f1i1 c9a7 e1e2 e8d7 i1i8 f8f9 e2f2 f9e9 i8i9 e9e8 i9d9 c5e7 d2e1 
 21	+21.12 	289.1M	1&#58;57.43	e1f0 e7f7 d0d1 f7f8 d1f1 e8f7 f0e1 d7e8 f1h1 e8d7 e0f0 f8e8 h1f1 e8e9 f1f7 d7e8 f7h7 e9d9 h7h9 d9d8 h9e9 e8d7 f0e0 
 20	+21.00 	160.2M	1&#58;02.14	e1f0 e7f7 d0d1 f7f8 d1f1 e8f7 f0e1 d7e8 f1h1 e8d7 h1h8 f8f9 h8h9 f9f8 e0f0 f8e8 h9f9 e8d8 f9f7 d7e8 f7f8 a7c5 
 19	+21.00 	98.4M  	0&#58;37.50	e1f0 e7f7 d0d1 f7f8 d1f1 e8f7 f0e1 d7e8 f1h1 e8d7 h1h8 f8f9 h8h9 f9f8 e0f0 f8e8 h9f9 e8d8 f9f7 d7e8 f7f8 a7c5 
 18	+2.48 	47.5M  	0&#58;18.08	c0a2 e7f7 d0b0 f7f8 e2g4 a7c5 a2c0 f8f9 b0b6 f9e9 b6h6 c9e7 e0f0 e8f9 f0f1 c5a7 f1f2 a7c5 
 17	+2.48 	27.3M  	0&#58;10.51	c0a2 e7f7 d0b0 f7f8 e2g4 c9e7 b0b6 f8f9 a2c0 f9e9 b6c6 e7c5 c6e6 a7c9 
 16	+2.48 	12.2M  	0&#58;04.79	c0a2 e7f7 d0b0 f7f8 e2g4 c9e7 b0b6 f8f9 a2c4 f9e9 b6c6 a7c9 c6c7 e9d9 c7d7 e8d7 c4e2 
 15	+2.48 	5.15M  	0&#58;01.98	c0a2 e7f7 d0b0 f7f8 e2c4 f8f9 b0b5 c9e7 b5f5 f9e9 a2c0 a7c9 f5h5 e8f9 h5h6 d7e8 
 14	+2.48 	2.43M  	0&#58;00.95	c0a2 e7f7 d0b0 f7f8 e2c4 f8f9 b0b5 c9e7 a2c0 f9e9 b5e5 a7c5 e5e4 e9f9 
 13	+2.48 	962458	0&#58;00.41	c0a2 e7f7 d0b0 f7f8 e2c4 f8f9 b0b5 c9e7 b5f5 f9e9 a2c0 a7c9 f5e5 e8f7 
 12	+2.48 	429682	0&#58;00.20	c0a2 e7f7 d0b0 f7f8 e2c4 f8f9 b0b5 c9e7 a2c0 a7c5 b5b6 f9e9 
 11	+2.48 	228277	0&#58;00.11	c0a2 e7f7 d0b0 f7f8 e2c4 f8f9 b0b5 c9e7 b5f5 f9e9 a2c0 a7c9 
 10	+2.48 	101084	0&#58;00.06	c0a2 e7f7 d0c0 f7f8 c0c6 f8f9 e2g4 f9e9 c6e6 a7c5 
  9	+2.44 	67415  	0&#58;00.03	c0a2 e7f7 d0c0 f7f8 c0c6 f8f9 c6f6 f9e9 e2g4 c9e7 
  8	+2.52 	21369  	0&#58;00.01	c0a2 e7f7 e2c4 a7c5 d0d1 f7f8 a2c0 
  7	+2.44 	13005  	0&#58;00.01	c0a2 e7f7 d0c0 f7f8 c0c4 f8f9 c4f4 f9e9 
  6	+2.52 	2870    	0&#58;00.00	c0a2 e8d9 a2c4 e7e8 e2g4 e8e9 
  5	+2.40 	965      	0&#58;00.00	c0a2 a7c5 a2c4 c5a7 e1f2 
  4	+2.56 	358      	0&#58;00.00	c0a2 a7c5 e2c4 e7f7 
  3	+2.40 	165      	0&#58;00.00	c0a2 a7c5 a2c4 
  2	+2.56 	38        	0&#58;00.00	e2c4 a7c5 
  1	+9.64 	9          	0&#58;00.00	c0a2

For the second it could not find a win even after 1.5 hour. For the third my patience ran out after 30 min, when it had not found a win yet. I experimented a bit with the third position: When I delete all extra defenders it of course finds the win instantly, because the root is already in the EGT. (Well, it needs 4 ply, because in the first 3 ply I do not probe the EGT, to make sure the engine would not make a perpetual chase in a drawn position, and lose because of that after all.) With only the Elephant on e2 it finds a win in 5 sec; this does not alter when I put the second Elephant on c0. (This Elephant can be completely ignored from the beginning, and this is indeed what the engine does.) With both Elephant and Advisor on the e-file it is hard, however: the engine needs 25 min to see it can win an Elephant, but still cannot do it in such a way that all obstruction by its own defenders has been cleared. So there still is no mate score, but it of course knows KR*KEAA is a certain win.

Note, however, that this is using the normal search until it can probe K"R'K*. It should be possible to greatly improve on that with the given partial EGT. For one, the search can probably ignore extra defenders that are already out of the way, or moves that would put the Rook on its own board half. This would reduce the branching factor of the search. In addition, when the equivalence condition between KR*K* and K"R'K* is not satisfied (Rook on own half, or obstructing defenders), the probe could still be made ignoring the obstructing defenders and/or projecting the Rook onto the 6th rank, for the purpose of guiding the search. When such a probe returns a draw, the search could be strongly reduced (LMR fashion). This will trim away nodes in branches where the Rook side is just fooling around, allowing the opponent to reorganize his defense into a constellation that is Rook-resistant. This would ' funnel' the search into the lines that keep the losing side under pressure.

It seems all your sizes are a bit strange and different (larger) from mine. I use the work of Fang & Hsu (Construction of Chinese Chess Endgame databases by Retrograde Analysis).

There are totally 3339 combinations of defenders.

Well, that is the 3451 - 112 I mentioned. I don't bother squeezing out the 112 broken positions; that saves only 3%. Savings become only relevant when they are a factor 25-50, so that you can afford an extra piece.

All tables of an one-but-not-pawn-attacking-piece (say KR*K*) take only 550 MB for one side or 1100 MB (uncompressed) for 2 sides.

OK, I see. This makes use of left-right symmetry, which roughly divides the numbers I gave by 2.

Total of all tables of HH (KHH*K*) is 23 GB (uncompressed) for one side.

All tables of two-attacking-pieces (CC, CH, CP, HH, HP, PP) but no Rook (since Rook + any piece is mostly a sure win) take about 170 GB for one side in uncompressed format.

That is still way too big to fit in RAM.

Some positions for testing EGT:

[/quote]

noobpwnftw · Post by **noobpwnftw** » Sun May 21, 2017 7:25 pm

Longest DTC I have so far:

I think we don't need to worry too much about DTx sizes, they will eventually grow too large when you add more and more pieces.

My current set of corresponding WDL tablebases already reached 2TB after compression, so I'm more interested in:
- using fast NNs to replace WDL tablebases
- somehow ignore pieces that makes no difference

Any ideas?

phhnguyen · Post by **phhnguyen** » Mon May 22, 2017 3:15 am

hgm wrote: For the second it could not find a win even after 1.5 hour.

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.

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.

hgm wrote: For the third my patience ran out after 30 min, when it had not found a win yet. I experimented a bit with the third position: When I delete all extra defenders it of course finds the win instantly, because the root is already in the EGT. (Well, it needs 4 ply, because in the first 3 ply I do not probe the EGT, to make sure the engine would not make a perpetual chase in a drawn position, and lose because of that after all.) With only the Elephant on e2 it finds a win in 5 sec; this does not alter when I put the second Elephant on c0. (This Elephant can be completely ignored from the beginning, and this is indeed what the engine does.) With both Elephant and Advisor on the e-file it is hard, however: the engine needs 25 min to see it can win an Elephant, but still cannot do it in such a way that all obstruction by its own defenders has been cleared. So there still is no mate score, but it of course knows KR*KEAA is a certain win.

Note, however, that this is using the normal search until it can probe K"R'K*. It should be possible to greatly improve on that with the given partial EGT. For one, the search can probably ignore extra defenders that are already out of the way, or moves that would put the Rook on its own board half. This would reduce the branching factor of the search. In addition, when the equivalence condition between KR*K* and K"R'K* is not satisfied (Rook on own half, or obstructing defenders), the probe could still be made ignoring the obstructing defenders and/or projecting the Rook onto the 6th rank, for the purpose of guiding the search. When such a probe returns a draw, the search could be strongly reduced (LMR fashion). This will trim away nodes in branches where the Rook side is just fooling around, allowing the opponent to reorganize his defense into a constellation that is Rook-resistant. This would ' funnel' the search into the lines that keep the losing side under pressure.

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.

hgm wrote:
All tables of two-attacking-pieces (CC, CH, CP, HH, HP, PP) but no Rook (since Rook + any piece is mostly a sure win) take about 170 GB for one side in uncompressed format.
That is still way too big to fit in RAM.

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

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.

phhnguyen · Post by **phhnguyen** » Mon May 22, 2017 3:32 am

noobpwnftw wrote:Probing DTx tablebases during search is not really necessary, you can simply probe WDL tablebases and give it a pesudo-mate score, then probe DTx tablebases when you actually reached that position.

I'm hosting a comprehensive set of DTC/DTM tablebases online, with a public query interface. Also accepting requests to build any useful set within 1TB memory size.

For your above positions:
1. http://www.chessdb.cn/query_en/?2b6/4a4 ... /2BRK4%20w
2. http://www.chessdb.cn/query_en/?2b6/4a4 ... BRK1B2%20w
3. http://www.chessdb.cn/query_en/?2b6/R3a ... /2B1K4%20w

Available set lists are here:
DTC: http://www.chessdb.cn/egtb_info.html
DTM: http://www.chessdb.cn/egtb_info_dtm.html

I hope this is useful for you.

Thanks Guo, very impressed work!!!

Do you keep your data in uncompressed format? Is there any chess engine which are using your EGT?

We need some positions which have very long distances for the first capture (actually it is DTC) to test endgame searching. Can you help us to find some? Say, for endgame KAABBRKAABB, DTC > 30 plies. Many thanks

noobpwnftw · Post by **noobpwnftw** » Mon May 22, 2017 4:50 am

phhnguyen wrote:
noobpwnftw wrote:Probing DTx tablebases during search is not really necessary, you can simply probe WDL tablebases and give it a pesudo-mate score, then probe DTx tablebases when you actually reached that position.

I'm hosting a comprehensive set of DTC/DTM tablebases online, with a public query interface. Also accepting requests to build any useful set within 1TB memory size.

For your above positions:
1. http://www.chessdb.cn/query_en/?2b6/4a4 ... /2BRK4%20w
2. http://www.chessdb.cn/query_en/?2b6/4a4 ... BRK1B2%20w
3. http://www.chessdb.cn/query_en/?2b6/R3a ... /2B1K4%20w

Available set lists are here:
DTC: http://www.chessdb.cn/egtb_info.html
DTM: http://www.chessdb.cn/egtb_info_dtm.html

I hope this is useful for you.
Thanks Guo, very impressed work!!!

Do you keep your data in uncompressed format? Is there any chess engine which are using your EGT?

We need some positions which have very long distances for the first capture (actually it is DTC) to test endgame searching. Can you help us to find some? Say, for endgame KAABBRKAABB, DTC > 30 plies. Many thanks

About the format, it is a propriety format used by cyclone chess engine. But there isn't much mystery anyway, indexing eliminates board symmetry and use near-optimal piece folding. DTx data is compressed with LZMA, WDL data is compressed with LZ4.

If you are looking for some testing positions for a certain piece set, you can first find the longest DTC position in my list, then make some sub-optimal moves, this way you can get as many positions fulfilling certain criteria as you wish. Web query defaults to DTM results, you can switch to DTC by choosing metric on the left.

9/3ka1R2/3ab4/9/6b2/9/9/4BA3/4A4/5KB2 w
This has the longest DTC for KAABBRKAABB.

I also have API interface so that you can do above automatically.
http://www.chessdb.cn/cloudbook_api.html

phhnguyen · Post by **phhnguyen** » Mon May 22, 2017 5:30 am

noobpwnftw wrote: About the format, it is a propriety format used by cyclone chess engine. But there isn't much mystery anyway, indexing eliminates board symmetry and use near-optimal piece folding. DTx data is compressed with LZMA, WDL data is compressed with LZ4.

Wow, are you the author of cyclone? The engine is so good!

Yes agreed, look like so far EGTs are not a mystery for chess engines. However I want to know clearly their limits, especially in new model hardware where memory become so huge. Do you load your EGT into memory and probe it in quiescence?

I will test with my new EGT of course, but still busy for the new design - it may take me some months before I could start testing.

noobpwnftw wrote: If you are looking for some testing positions for a certain piece set, you can first find the longest DTC position in my list, then make some sub-optimal moves, this way you can get as many positions fulfilling certain criteria as you wish. Web query defaults to DTM results, you can switch to DTC by choosing metric on the left.

9/3ka1R2/3ab4/9/6b2/9/9/4BA3/4A4/5KB2 w
This has the longest DTC for KAABBRKAABB.

I also have API interface so that you can do above automatically.
http://www.chessdb.cn/cloudbook_api.html

Thanks for the nice position. Hope HGM's engine could solve it.

noobpwnftw · Post by **noobpwnftw** » Mon May 22, 2017 5:58 am

phhnguyen wrote: Wow, are you the author of cyclone? The engine is so good!

Yes agreed, look like so far EGTs are not a mystery for chess engines. However I want to know clearly their limits, especially in new model hardware where memory become so huge. Do you load your EGT into memory and probe it in quiescence?

No, I'm not the author of that engine, I co-authored the tablebases and provided hardware for building very large ones.

The engine usually only probe WDL tablebases, having some uncompressed block cache in memory, mainly it probes from disk since we have a very large set of tablebases.

Probing is performed along with static eval limited by a minimum probe depth, a winning / losing hit will result in pseudo-mate score and search functions will treat them as if mated. We don't really care about search results after hits since we already have oracle knowledge. When root position has a DTx hit, we probe a limited depth of moves just to print a reasonable PV.

phhnguyen · Post by **phhnguyen** » Mon May 22, 2017 8:19 am

I have seen the download page of that engine (cyclone). I am impressed by the sizes of its EGT (over 1 TB) and large number of attacking pieces involving!

However, I was surprised that I cannot find out from the download page some very basic EGTs, say one attacking piece with all defender combinations (such as KRK, KRAAEEKAAEE...). Perhaps I was missing somethings? (I don't know Chinese and have never used cyclone).

If those basic EGTs are missing, I think the gain from EGTs will be so small because of having so large data but low hit.

Probe EGT in quiescence?

Re: Probe EGT in quiescence?

Re: Probe EGT in quiescence?

Re: Probe EGT in quiescence?

Re: Probe EGT in quiescence?

Re: Probe EGT in quiescence?

Re: Probe EGT in quiescence?

Re: Probe EGT in quiescence?

Re: Probe EGT in quiescence?

Re: Probe EGT in quiescence?

Re: Probe EGT in quiescence?