Trying to understand Retrograde analysis (EGTB generation)

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
mphuget
Posts: 8
Joined: Fri Mar 01, 2019 11:46 am
Full name: Marc-Philippe HUGET

Trying to understand Retrograde analysis (EGTB generation)

Post by mphuget » Fri Jan 10, 2020 7:08 am

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
Posts: 10243
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Trying to understand Retrograde analysis (EGTB generation)

Post by Dann Corbit » Fri Jan 10, 2020 8:01 am

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
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

mphuget
Posts: 8
Joined: Fri Mar 01, 2019 11:46 am
Full name: Marc-Philippe HUGET

Re: Trying to understand Retrograde analysis (EGTB generation)

Post by mphuget » Fri Jan 10, 2020 8:09 am

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

User avatar
hgm
Posts: 23881
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Trying to understand Retrograde analysis (EGTB generation)

Post by hgm » Fri Jan 10, 2020 8:40 am

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 .

User avatar
phhnguyen
Posts: 542
Joined: Wed Apr 21, 2010 2:58 am
Location: Australia
Full name: Nguyen Hong Pham
Contact:

Re: Trying to understand Retrograde analysis (EGTB generation)

Post by phhnguyen » Fri Jan 10, 2020 11:39 am

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 :)
https://banksiagui.com
A freeware chess GUI, based on opensource Banksia - the chess tournament manager

User avatar
Ovyron
Posts: 3082
Joined: Tue Jul 03, 2007 2:30 am

Re: Trying to understand Retrograde analysis (EGTB generation)

Post by Ovyron » Fri Jan 10, 2020 4:45 pm

phhnguyen wrote:
Fri Jan 10, 2020 11:39 am
- 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...)

User avatar
hgm
Posts: 23881
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Trying to understand Retrograde analysis (EGTB generation)

Post by hgm » Fri Jan 10, 2020 6:57 pm

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.

User avatar
hgm
Posts: 23881
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Trying to understand Retrograde analysis (EGTB generation)

Post by hgm » Fri Jan 10, 2020 7:00 pm

phhnguyen wrote:
Fri Jan 10, 2020 11:39 am
- 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.

User avatar
phhnguyen
Posts: 542
Joined: Wed Apr 21, 2010 2:58 am
Location: Australia
Full name: Nguyen Hong Pham
Contact:

Re: Trying to understand Retrograde analysis (EGTB generation)

Post by phhnguyen » Sat Jan 11, 2020 6:02 am

Ovyron wrote:
Fri Jan 10, 2020 4:45 pm
phhnguyen wrote:
Fri Jan 10, 2020 11:39 am
- 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).
Last edited by phhnguyen on Sat Jan 11, 2020 6:27 am, edited 1 time in total.
https://banksiagui.com
A freeware chess GUI, based on opensource Banksia - the chess tournament manager

User avatar
phhnguyen
Posts: 542
Joined: Wed Apr 21, 2010 2:58 am
Location: Australia
Full name: Nguyen Hong Pham
Contact:

Re: Trying to understand Retrograde analysis (EGTB generation)

Post by phhnguyen » Sat Jan 11, 2020 6:06 am

hgm wrote:
Fri Jan 10, 2020 7:00 pm
phhnguyen wrote:
Fri Jan 10, 2020 11:39 am
- 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.
https://banksiagui.com
A freeware chess GUI, based on opensource Banksia - the chess tournament manager

Post Reply