Probe EGT in quiescence?

[phhnguyen]

Hi all,

I have been working on a new design of an EGT (for Xiangqi) and planing to use it in quiescence for few-men endgames.

Plan:
- evaluation function will be cut endgame code, at least for known endgames in that EGT
- all EGT files will be pre-loaded into memory. Small endgames will be in uncompressed when the larger ones will be in compressed forms
- the EGT uses DTM metric
- probe the EGT everywhere, from alphabeta to quiescence functions

Not sure if it (probing in quiescence) works since I found very few posts / pages about it.

Any idea, experience, suggestion?

Thanks in advance

[jdart]

You can try it, but memory access can be a bottleneck for programs, especially when the memory being accessed is large enough that you are incurring cache misses. So you may find that EGT everywhere hurts your performance. Profiling will show if this an issue.

--Jon

[hgm]

In the latest version of HaQiKi D (which I used in last year's Computer Olympiad) I use memory-loaded EGT, and probe them in every node. I don't think the memory-access cost would hurt more than usual: most engines do probe hash in QS, which doesn't have better chances for being a cache hit. The EGT probe simply replaces the hash probe, with a guaranteed hit. (Normal hash probes would often be wasted effort, because the position was not in the TT.)

So when the material key indicates we are in an end-game for which we have EGT, Search immediately returns the score corresponding to the DTM found in the EGT (i.e. INF - DTM, or 0).

To keep the EGT small I only use 'partial EGT'. By this I mean the following: when you want to win with Rook + King against King + four defenders, the squares along a file on your own board half not on the King rank are all equivalent for the Rook. So I imagine that for the Rook the board is only 9x6 instead of 9x10. Likewise, only the file of the attacking King matters, like the Palace is x1 instead of 3x3. You just have to allow null-moving during the EGT generation, for representing a rank-switch of Rook or King to burn a tempo and avoid zugzwang.

So in probing I map the attacking King to 1st rank, and a Rook on rank 0-4 to 6th rank before the probe.

I can use that same EGT even when the attacking side has defenders too, provided that:
* The elephant eye (e2) is empty
* All Advisers are on ranks behind the King
For that to help the engine should be able to recognize draws in positions where this these conditions are not satisfied, or it would try to hide the fact that it is draw from itself by keeping the King behind an Adviser or by keeping an Elephant on e2. One way to do that is probe KRKEEAA like the defenders of the attacking side are not there. If that is a draw, the extra defenders will not hep you. If not, (i.e. in positions where the extra defenders might be obstructing a win you would otherwise have) you can search on (or use the heuristic eval in a leaf). It will only take a few moves to step the King in front of the Advisers, and possibly get an Elephant out of the way, after which you can probe KRKEEAA successfully. There is no way for the engine to hide a draw then, because stalling would allow the weak side to organize his defense in a way that would make the draw recognizable in the KRKEEAA probe.

[Fabio Gobbato]

In my engine I probe syzygy also in qs, it's a little improvement at tc=5:00

[phhnguyen]

In my engine I probe syzygy also in qs, it's a little improvement at tc=5:00

Interesting!

Do you use WDL tables only or all (include full tables)? I guess you use those tables in compressed forms as its origin. Correct? Did you test with faster games (and saw no improvement) or just tc=5:00

Thanks a lot

[phhnguyen]

In the latest version of HaQiKi D (which I used in last year's Computer Olympiad) I use memory-loaded EGT, and probe them in every node. I don't think the memory-access cost would hurt more than usual: most engines do probe hash in QS, which doesn't have better chances for being a cache hit. The EGT probe simply replaces the hash probe, with a guaranteed hit. (Normal hash probes would often be wasted effort, because the position was not in the TT.)

So when the material key indicates we are in an end-game for which we have EGT, Search immediately returns the score corresponding to the DTM found in the EGT (i.e. INF - DTM, or 0).

Thanks for a long and detail post!

Some few questions:
- Is your program multithreading?
- Do you use compressed or uncompressed EGT?

To keep the EGT small I only use 'partial EGT'. By this I mean the following: when you want to win with Rook + King against King + four defenders, the squares along a file on your own board half not on the King rank are all equivalent for the Rook. So I imagine that for the Rook the board is only 9x6 instead of 9x10. Likewise, only the file of the attacking King matters, like the Palace is x1 instead of 3x3. You just have to allow null-moving during the EGT generation, for representing a rank-switch of Rook or King to burn a tempo and avoid zugzwang.

So in probing I map the attacking King to 1st rank, and a Rook on rank 0-4 to 6th rank before the probe.

I can use that same EGT even when the attacking side has defenders too, provided that:
* The elephant eye (e2) is empty
* All Advisers are on ranks behind the King

Interesting ideas and works!!! I have been working on reducing EGT sizes too.

Did you check the correctness of all cases with a full EGT? For me, those positions are more sophisticated than your above describing. The board in the below image is an example.

BTW, look like you may save some space for some tables with fewer defenders for attacking side (say KRK*) but not for more defender cases (say KRAAEEK*)?

For that to help the engine should be able to recognize draws in positions where this these conditions are not satisfied, or it would try to hide the fact that it is draw from itself by keeping the King behind an Adviser or by keeping an Elephant on e2. One way to do that is probe KRKEEAA like the defenders of the attacking side are not there. If that is a draw, the extra defenders will not hep you. If not, (i.e. in positions where the extra defenders might be obstructing a win you would otherwise have) you can search on (or use the heuristic eval in a leaf).

I am not clear about that idea. Do you mean you have KRKAAEE only but not KRAAEEKAAEE and trying to probe KRKAAEE even your board is KRAAEEKAAEE?

If you have not the big one you may save a lot of space but correctness is a big problem. If you have both, probe both for a given position is clearly no gain.

It will only take a few moves to step the King in front of the Advisers, and possibly get an Elephant out of the way, after which you can probe KRKEEAA successfully. There is no way for the engine to hide a draw then, because stalling would allow the weak side to organize his defense in a way that would make the draw recognizable in the KRKEEAA probe.

As my understand, the situation is more complicated than that. The board in the below image is a win for the white. However it is a draw if the white side has not the Elephant in e2.

King's rank is another problem we cannot simply omit. Same below board but if I set the King to d2 (instead of d1), it is a draw.

[hgm]

- Is your program multithreading?

It is SMP (my only engine to support that), but it uses processes rather than threads. It uses a simple shared-hash scheme.

- Do you use compressed or uncompressed EGT?

I use uncompressed EGT only.

Did you check the correctness of all cases with a full EGT? For me, those positions are more sophisticated than your above describing. The board in the below image is an example.

No, I did not check, and I am in fact convinced that the DTM given by the partial EGT is not always the shortest. But for my goal that doesn't matter; the only reason for having the EGT is to recognize won positions and make sure the engine will win them. That it might take a few moves longer than theoretically necessary, because the winning side does want to force the mate without his Rook visiting his own half of the board doesn't disturb me.

What I do is map the defending Elephant and Advisor locations to a unique number, where incomplete sets of defenders also have their own number. That number is then used in indexing the EGT. So the EGT would contain all of KEEAA, KEEA, KEAA, KEE, KEA, KAA, KE, KA and K for the defending side. For KRK* I then generate an EGT as if the Rook was not allowed to visit his own board half. I think that once the Rook is there, it doesn't have to leave it to get the fastest mate, as the 6th rank is never obstructed and can be used for lateral movement. If the fastest would require a number of moves to be made with the Rook on its own half first, the search will find that. Because positions with the Rook there are not in the EGT, the search would not be cut, and if the position is indeed won, it would search such moves until it can enter the EGT.

I am not clear about that idea. Do you mean you have KRKAAEE only but not KRAAEEKAAEE and trying to probe KRKAAEE even your board is KRAAEEKAAEE?

Indeed. Because the part of KRK* that is in the EGT has the Rook always on the enemy half, the attacker's AAEE will never obstruct the Rook. So if they also do not obstruct the King (i.e. no Elephant on e2, King in front of all Advisors), they can be completely ignored.

As my understand, the situation is more complicated than that. The board in the below image is a win for the white. However it is a draw if the white side has not the Elephant in e2.

King's rank is another problem we cannot simply omit. Same below board but if I set the King to d2 (instead of d1), it is a draw.

Hmm, I had not realized the extra defender could be helpful. But I don't think it wrecks the scheme. The point is that this position is not in KRK* (because of the extra E, and the R being on its own half), and does not satisfy the condition for equivalence (because the E is on e2). So the probe on the analoguous position in KRK* (with the Rook on d6) would not be used to cut the search, but just to correct the evaluation to a draw in case this is in a leaf, and let the search continue otherwise. This means you get the wrong result for this position in a leaf, but this gets corrected when you search deeper.

This is the price you pay for a smaller EGT, and to be expected. The smaller the EGT, the later you will enter it. In positions where you cannot probe (but could have with the larger EGT) you rely on a heuristic evaluation, which is not perfect. Using the KRK* probe to make the score drawish whenever the analogous KRK* position is a draw is already far more accurate than any other heuristic I could make to score K*RK* positions. It is only very rarely off.

The actual output of HaQiKi D on the given position is:

Code: Select all

 16	  #24 	17.8M  	0:05.32	d1e1 e8d8 e2g4 g9e7 d0d5 
 15	  #24 	9.59M  	0:02.94	d1e1 e8d8 e2g4 g9e7 d0d5 
 14	  #24 	4.92M  	0:01.59	d1e1 e8d8 e2g4 g9e7 d0d5 
 13	  #24 	2.37M  	0:00.84	d1e1 e8d8 e2g4 g9e7 d0d5 
 12	  #24 	1.14M  	0:00.46	d1e1 e8d8 e2g4 g9e7 d0d5 
 11	  #24 	527290	0:00.19	d1e1 e8d8 e2g4 g9e7 d0d5 
 10	  #24 	249604	0:00.09	d1e1 e8d8 e2g4 g9e7 d0d5 
  9	  #24 	123179	0:00.05	d1e1 e8d8 e2g4 g9e7 d0d5 
  8	  #24 	61225  	0:00.03	d1e1 e8d8 e2g4 g9e7 d0d5 
  7	+14.80 	19389  	0:00.02	d1e1 e8e7 d0d6 e7e8 d6d7 e8e9 d7f7 
  6	+14.80 	8967    	0:00.02	d1e1 e8e7 d0d6 e7e8 d6d7 e8e9 d7f7 
  5	+1.68 	3475    	0:00.01	d1e1 e8e7 d0d6 d7e8 d6e6 e7d7 
  4	+1.68 	1182    	0:00.01	d1e1 e8d8 e2g4 f7e8 
  3	+1.56 	387      	0:00.01	d1e1 e8d8 e1e0 
  2	+1.68 	65        	0:00.01	d1e1 e8d8 
  1	+5.84 	14        	0:00.01	d1e1 
 

So it sees mate in 24 here, and as soon as it sees it the PV is only 5 ply to the winning EGT probe. It needs to make the winning King move using the Elephant as shield, and then it needs two more moves to get the Elephant out of the way, and the Rook on the enemy half. Then it enters the EGT and finds a DTM there (which is then corrected for the preceding search ply).

In KRK* with the Rook on the enemy half, it is not relevant on which rank the attacking King is. So that King rank does not affect the EGT index (shrinking the EGT by anpther factor 3)

With the King on d2 instead, it indeed finds a drawish score:

Code: Select all

 24	+1.68 	50.5M  	0:22.15	d0c0 e8f8 e2g0 f8f9 c0c9 f9f8 d2e2 f7e8 c9c4 e8f7 e2f2 d7e8 c4c9 e8f9 c9d9 f9e8 d9e9 e8f9 g0i2 f9e8 e9b9 e8d7 b9b8 d7e8 b8d8 i7g5 
 23	+1.68 	41.9M  	0:18.03	d0c0 e8f8 e2g0 f8f9 c0c9 f9f8 c9d9 f7e8 d9e9 e8f7 e9b9 d7e8 d2e2 e8f9 e2f2 f9e8 b9e9 
 22	+1.68 	32.4M  	0:13.59	d0c0 e8f8 e2g0 f8f9 c0c9 f9f8 d2e2 f7e8 c9c4 e8f7 e2f2 d7e8 c4e4 e8d9 e4e7 d9e8 g0i2 i7g5 e7c7 g5i7 c7c9 e8d7 c9c8 d7e8 
 21	+1.68 	26.1M  	0:10.64	d0c0 e8f8 e2g0 f8f9 c0c9 f9f8 c9d9 f7e8 d9e9 e8f7 g0i2 f7e8 d2e2 f8f7 i2g0 f7f8 e2e1 f8f7 e1e0 f7f8 g0e2 e8f7 
 20	+1.68 	20.1M  	0:08.01	d0c0 e8f8 e2g0 f7e8 c0c9 e8f7 c9d9 f7e8 d9e9 e8f7 g0i2 d7e8 e9b9 e8f9 b9d9 f9e8 d9a9 e8d7 a9b9 d7e8 
 19	+1.68 	15.5M  	0:06.06	d0c0 e8f8 e2g0 f7e8 c0c9 e8f7 c9e9 f7e8 g0e2 f8f7 e2c4 f7f8 e9c9 f8f7 c9c6 f7f8 c6f6 e8f7 d2e2 d7e8 
 18	+1.68 	11.4M  	0:04.36	d0c0 e8f8 e2g0 f7e8 c0c9 e8f7 c9d9 d7e8 d9a9 e8f9 d2e2 f9e8 e2f2 e8d7 a9d9 d7e8 d9e9 e8f9 
 17	+1.68 	8.29M  	0:03.11	d0c0 e8f8 e2g0 f7e8 c0c9 f8f7 c9c5 f7f8 d2e2 e8f7 e2f2 d7e8 c5c9 e8d7 c9c8 d7e8 c8d8 i7g5 
 16	+1.68 	5.83M  	0:02.15	d0c0 e8f8 e2g0 f7e8 c0c9 f8f7 c9c5 f7f8 d2e2 e8f7 e2f2 d7e8 c5c9 e8d7 c9d9 d7e8 
 15	+1.68 	3.87M  	0:01.41	d0c0 e8f8 e2g0 f7e8 c0c9 f8f7 c9e9 f7f8 e9b9 e8f7 b9d9 d7e8 
 14	+1.68 	2.39M  	0:00.87	d0c0 e8f8 e2g0 f7e8 c0c9 f8f7 c9e9 f7f8 e9b9 e8f7 
 13	+1.68 	1.48M  	0:00.55	d0c0 e8f8 e2g0 f7e8 c0c9 e8f7 c9d9 d7e8 d9b9 e8d7 b9b8 d7e8 g0i2 f8f9 
 12	+1.68 	785772	0:00.29	d0c0 e8f8 e2g0 f7e8 c0c9 e8f7 c9d9 d7e8 d9e9 e8d7 g0e2 d7e8 
 11	+1.68 	405545	0:00.16	d0c0 e8f8 e2g0 f7e8 c0c9 e8f7 c9c8 f8f9 c8d8 f7e8 g0i2 i7g5 
 10	+1.72 	204747	0:00.08	d0c0 e8f8 e2g0 f7e8 c0c9 e8f7 c9e9 d7e8 g0i2 e8d7 
  9	+1.68 	111689	0:00.04	d0c0 e8f8 e2g0 f7e8 c0f0 e8f7 f0f5 d7e8 f5e5 f8f9 
  8	+1.68 	49425  	0:00.02	d0c0 e8f8 e2g0 f7e8 c0c9 f8f7 c9e9 g9e7 
  7	+1.68 	22751  	0:00.01	d0c0 e8f8 c0c8 f8f9 c8c9 f9f8 e2c4 f7e8 c9e9 f8f7 
  6	+1.68 	11149  	0:00.00	d0c0 e8f8 c0f0 d7e8 e2c4 f8f9 
  5	+1.68 	5469    	0:00.00	d0c0 e8f8 c0c8 f8f9 c8c9 f9f8 e2c4 d7e8 
  4	+1.64 	1996    	0:00.00	e2g4 e8e9 g4i2 i7g5 
  3	+1.24 	771      	0:00.00	d0c0 e8e7 d2d1 
  2	+1.68 	61        	0:00.00	e2g4 e8e9 
  1	+5.56 	15        	0:00.00	e2g4 

At d=1 it returns the 'naive' evaluation, happy that it is a Rook vs EAA ahead, because it did not have the opportunity to probe the EGT yet. (The EGT only contains positions with the winning side to move.) After that the score gets drawish, because there is no way to get to a winning position in the EGT, no matter how deep you search.

[Fabio Gobbato]

In search and qsearch I probe only wdl. Syzygy are compressed. I haven't tried with a shorter time control, I think that with a short tc there wouldn't be much improvement.

[phhnguyen]

Amazing your program can search out the mate with that such long distance to mate!!!

I have tried several index schemes which are based on a deep full search. Their index space reduces are sometimes so huge and tempting!!!

Unfortunately after testing I have to dump them all since searching deeply means we cannot get hit or have correct results from quiescence. In many cases searching out a mate is impossible.

Even your program can find the mate by searching the given position from the root I still doubt if it can find from middle search and quiescence - just one wrong move the white side may miss the chance to win. Furthermore, above position is still easy since the white side has so few defenders.

I have seen many harder positions for searching when they have so long distance to convert, for example, over 30 half-moves for the first capture, and more defenders involving, say full 8 defenders for both sides. The search nodes may increase so badly, I think, almost all engines cannot find out those mates in real matches. Again, if they do only one wrong move, they may lose the change to win

IMO, the way you scheme indexes in your current EGT (did not count when the Rook in his own half board side and / or when the King is not in the open file…) would bring a huge trouble to the search:

- it is actually worse than a bitbase EGT to keep searching progress because even the bitbase does not provide DTM but it still help the search on limiting the number of searching positions. In other hand, your EGT does not provide any clue / tip when it does not get hit

- the way you ignore the attacking piece (in his own half side) and / or open King… somewhat is reasonable for Rook, but not for other pieces, say Cannon, since Cannon may attack mainly from his own board side, using his side defenders as Cannon’s mounts


IMO, it could be better to use a full traditional EGT instead of using a small EGT + searching deeply. (I called it traditional since I am working on a new one without using deep search but still reduce the size significantly - I will release soon after checking everything). A full traditional EGT for all one-attacking-piece and all defender configurations (KR*K*, KC*K*, KH*K*, KP*K*) may take about totally 3.8 GB in uncompressed, 1 byte per position format. It is still OK to load all into memory for model computers. You may easily reduce their sizes by throwing aways one side data, use fewer bit per position and / or compress them (two sides compressed data < 300 MB or one side < 150MB - very easy to load and store them all in the memory).

[hgm]

Amazing your program can search out the mate with that such long distance to mate!!!

But it cannot. It only searches 5 ply deep, as you can see from the PV. After that it finds the remaining DTM in the EGT. (The nominal depth has to be 8 ply for this, because it finds the mate in a side branch that is reduced by LMR.) At this depth it starts to hit positions in the partial KRK* EGT (ignoring the extra Elephant because it is no longer on e2), and finds a mate in 21 there. Which from the root is a mate in 24.

I have tried several index schemes which are based on a deep full search. Their index space reduces are sometimes so huge and tempting!!!

Unfortunately after testing I have to dump them all since searching deeply means we cannot get hit or have correct results from quiescence. In many cases searching out a mate is impossible.

Normally you would not get correct results (or in fact any results) from EGT probing for positions that are not in the EGT, without further search. But extra strong-side defenders that do not obstruct King or Rook can be completely ignored. So The parts of KREEAAK* with the A on d0 and f0, the E on a2 and g4, the King on d1 and the Rook on rank 5-9 (as well as many other constellations of A, E and K) are identically the same as the part of KRK*. And inside the latter, the parts with the King on d0, d1 and d2 are all identical.

You can simply see this as a smart form of compression, where you avoid storing multiple copies of the same data. When I already have KRK*, those parts of KREEAAK* that are identical to it do not have to be stored in KREEAAK* (and KREAAK*, KREEAK*, etc.), if the probing routine is smart enough to divert the probe for such positions to KRK*, as part of its 'decompression' algorithm.

Even your program can find the mate by searching the given position from the root I still doubt if it can find from middle search and quiescence - just one wrong move the white side may miss the chance to win. Furthermore, above position is still easy since the white side has so few defenders.

When the search doesn't reach the EGT, you cannot probe it. Again a universal truth. It would be best to have tables for all positions in the game tree of Xiangqi. Unfortunately the Universe is not large enough to hold these. Storage space is limited, and the larger the tables, the slower their access will be. If the EGT get too large to fit in memory, you will have to compress/decompress, or wait for disk I/O. That also takes extra time. Doing a shallow search might be faster than decompressing a block of EGT data in order to find the position in it, or reading it from the disk. So awarding a search extension of, say, 5 ply in QS positions where it is guaranteed that you will hit a partial EGT in 5 ply (possibly using a dedicated search optimizede for KR*K* positions) might outperform a design where you access a full EGT that has to be loaded from disk.

I have seen many harder positions for searching when they have so long distance to convert, for example, over 30 half-moves for the first capture, and more defenders involving, say full 8 defenders for both sides. The search nodes may increase so badly, I think, almost all engines cannot find out those mates in real matches. Again, if they do only one wrong move, they may lose the change to win

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.

IMO, the way you scheme indexes in your current EGT (did not count when the Rook in his own half board side and / or when the King is not in the open file…) would bring a huge trouble to the search:

- it is actually worse than a bitbase EGT to keep searching progress because even the bitbase does not provide DTM but it still help the search on limiting the number of searching positions. In other hand, your EGT does not provide any clue / tip when it does not get hit

But this is comparing apples and oranges. Of course having more information is always better, given infinite resources. But with finite resources it is better to remove less important information, even if it is in principle useful, to make room for more imprtant information. If keeping a full KREEAAKEEAA bitbase in RAM leaves no space to have a KHHEEAAKEEAA bitbase, all the problems you metion would now occur when you have two Horses instead of a Rook.

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.

- the way you ignore the attacking piece (in his own half side) and / or open King… somewhat is reasonable for Rook, but not for other pieces, say Cannon, since Cannon may attack mainly from his own board side, using his side defenders as Cannon’s mounts

Indeed. Obviously I do not use this for EGT with Cannons. With Horses it is sometimes useful to cross the River for manoeuvring, and a mate can take longer when you don't want to do that. But you can build the EGT for K"HHK* with Horses that are allowed to go everywhere, so that all DTM are correct, and then only store the K"H'H'K* part. The DTM might not be valid when c4 or g4 is occupied by an Elephant, so you would have to adapt the equivalence condition when probing for a position with extra Elephants on the strong side.

IMO, it could be better to use a full traditional EGT instead of using a small EGT + searching deeply. (I called it traditional since I am working on a new one without using deep search but still reduce the size significantly - I will release soon after checking everything). A full traditional EGT for all one-attacking-piece and all defender configurations (KR*K*, KC*K*, KH*K*, KP*K*) may take about totally 3.8 GB in uncompressed, 1 byte per position format. It is still OK to load all into memory for model computers. You may easily reduce their sizes by throwing aways one side data, use fewer bit per position and / or compress them (two sides compressed data < 300 MB or one side < 150MB - very easy to load and store them all in the memory).

Well, besides K"R'K* I also have K"H'H'K*, K"H'P'K*, K"P'P'K* and several KCxKy combinations.