Trying to understand Retrograde analysis (EGTB generation)

[mphuget]

Hello all,

I try to figure out retrograde analysis (especially when generating EGTB). From all the mate positions, going backward on the first move is easy, who checks the king, and I generate all possible moves from this attacking piece to every square on the board leading to mate in 1.

But when this is the next ply, the side that will be mated in two plies, I don't know what to do: generating all the possible positions leading to this one? So I do that for several plies and I search for the shortest path to mate which gives me the DTM?

Regarding EGTB, when do I decide to stop going backward?

Thanks in advance for your help
mph

[Dann Corbit]

https://www.chessprogramming.org/Retrograde_Analysis
http://home.hccnet.nl/h.g.muller/EGT7/7-men.html

A word on this:
It is fun and interesting to examine and code an algorithm for EGTB, but there are a lot of implementations available already. If you want to do it for your own enjoyment, there is nothing wrong with that. And if people did not try to improve on existing ideas, we would not have the better and better implementations that are now freely available.

But now, an important downside. There are a lot of EGTB formats, and all of them are big. So if they proliferate, that is actually a problem. If you store the full Nalimov set and the full Syzgyzy set, that is a lot of disk space. Storing one full seven man file set is many thousands of dollars just for the storage.

Just something to think about. I am not trying to dissuade you, but just making sure you thought about both ends of the problem

[mphuget]

Thanks, Dann for your answer.

Actually, I don't want to propose another format, Syzygy works fine for me and the reason for this post is curiosity. When I will manage to play backward, I could have a better idea of how multithreading could be used to improve the speed, even if I am sure https://github.com/syzygy1/tb already some good work on it. Told you, curiosity...

mph

[hgm]

Supposing white is the winning side, after you generated all mates-in-1, you make all black retrograde moves from those. This brings you to positions that are 'potentially mated in 2'. These then have to be verified, by generating all black prograde moves, to see if any of them reaches a (white-to-move) position that is not yet identified as 'mate-in-N'. If there is any such move the potentially-mated position reverts to being 'undecided'; otherwise it becomes a mated-in-N. And then you continue from the mated-in-1 as you did from the checkmates, etc.

For some explanation, and a code example, see http://home.hccnet.nl/h.g.muller/EGTB.html .

The verification step can sometimes beneficially be replaced by doing it once and for all in an initialization step: count the number of legal moves in every possible position. And then, when a retrograde black move brings you to a potentially lost position, you just decrease its 'escape count'. One this then hits zero, the position becomes mated-in-N, otherwise it remains 'undecided'. See for instance the JavaScript 3-men generator at http://hgm.nubati.net/rules/EGT.html .

[phhnguyen]

I don't have any problem if you create a new format for your EGTB. I have my own format too (for both standard chess and another chess variant). The most important you have fun and you can work with it in the long term - it is interesting but sometimes it may be so buggy and so tired. Of course, the majority of users only accept if your EGTBs have some new things and/or big advantages.

IMO, there is still a huge space/chance for newcomers. For example, people are still waiting for some new generators/EGTBs:
- Fast in-memory 3-4 men generators: generate 3-4 men in memory only within few seconds in typical desktop computers (your knowledge about multithreading may contribute well here)
- A similar Syzygy EGTB but using DTM
- Any new EGTBs with sizes under 70-80% of current ones. i.e., if you create a new DTM one and currently Gaviota 5 men EGTB size is 6.5 GB => yours need < 5 GB to be successful
- EGTBs for other chess variants

Good luck and have fun with EGTB generators

[Ovyron]

- Any new EGTBs with sizes under 70-80% of current ones.

I think this can be achieved by only storing useful positions, because about 70-80% of 7men EGTBs will never be reached or queried, so it's wasted space. Once someone comes up with a solution for this I expect 8men EGTB and 9men EGTB to come up surprisingly soon and be surprisingly small (though, since by definition they'd be incomplete, they'd probably need a new name as well...)

[hgm]

But the problem is that EGTB do not store any positions. They just store results (as 1 or 2 bits, in a WDL EGT), and to which position this result applies is implied by the location (index) of it in the EGT. This cannot be done if there is no fixed relation between the position and the index, such as would happen when you want to skip positions. Then you would have to accompany the result with some indication of the position to which it applies, which will drive up the space requirement by a factor 10-20. That you can then earn 70% of that back by leaving out the irrelevant positions is only meager compensation.

This might not apply to EGTs with many Pawns, which, because of the irreversible nature of Pawn moves, are not really a single EGT, but can be broken down into many independent 'P-slices', each with a fixed Pawn constellation. There some of the P-slices can be obviously irrelevant. E.g. those with 3 or 4 7th rank Pawns would never originate from optimal play, as you would have promoted and mated the opponent with the resulting Queen long before you could have marched up all the other Pawns to 7th rank. So those P-slices you could discard, and it wouldn't have any effect on the indexing of the important P-slices.

[hgm]

- Fast in-memory 3-4 men generators: generate 3-4 men in memory only within few seconds in typical desktop computers (your knowledge about multithreading may contribute well here)

This goal was reached already many years ago. Generating a typical 4-men like KBNK takes only about 100 msec on my laptop, using the 'PrettyFast' algorithm.

[phhnguyen]

- Any new EGTBs with sizes under 70-80% of current ones.

I think this can be achieved by only storing useful positions, because about 70-80% of 7men EGTBs will never be reached or queried, so it's wasted space. Once someone comes up with a solution for this I expect 8men EGTB and 9men EGTB to come up surprisingly soon and be surprisingly small (though, since by definition they'd be incomplete, they'd probably need a new name as well...)

I agreed that there are many ideas can help to achieve that saving. However, as HGM pointed out, not all ideas can help, some ideas won't work at all, some ideas may work with some endgames but not all. EGTB's developers need to work, try and error to figure out. They also need to balance between size-speed-complicated issues.

IMO, Syzygy EGTB is a good example of intergrading some clever/small improvement ideas which lead to an amazing result: a cut off 2/3 of total size (Syzygy 5 men size is under 1 GB, if it had data for both sides, the size should be around 2 GB, 1/3 of Gaviota 5 men).

[phhnguyen]

- Fast in-memory 3-4 men generators: generate 3-4 men in memory only within few seconds in typical desktop computers (your knowledge about multithreading may contribute well here)

This goal was reached already many years ago. Generating a typical 4-men like KBNK takes only about 100 msec on my laptop, using the 'PrettyFast' algorithm.

Can you update the information? Can all or only a few endgames of 3-4 men be generated on-fly in a reasonable time?

If the achievement is known, developers can simply push it up, say target to 5 men.