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