Felicity EGTB generators and probers

[syzygy]

I'm afraid an SSD would wear out very quickly when abused in this way. But HDDs perform well on sequential reads and writes, and compression should also help a lot.

I wonder if the SSD wear out is still true in 2024.

Every time the manufacturing process is improved, the SSD makers just add another bit to each cell to convert the increased quality into increased capacity. TLC NAND-based SSDs (3 bits per cell) support between 300 and 1000 write cycles, which might be insufficient for generating even just a single 8-men TB.

SLC NAND-based SSDs support between 60k and 100k write cycles and one third the memory density. But I suspect they are far more than 3x as expensive as TLC NAND-based SSDs per TB.

Without having all the data necessary to calculate this through, I suspect HDDs are still the much better option for this type of job.

[syzygy]

There are “Data Centre” SSDs, e.g. Kingston DC600M with 7.7 TB which can sustain 1 Drive Write Per Day for 5 years. Goes for €700 here in the Netherlands. Wouldn’t that be robust enough for on disk generation?

That would be only 1825 write cycles.

The Kingston DC600M seems to have "3D TLC NAND", which apparently supports between 1500 and 5000 write cycles (consistent with the 1825 number):
https://en.wikipedia.org/wiki/Flash_mem ... _endurance

[Rein Halbersma]

There are “Data Centre” SSDs, e.g. Kingston DC600M with 7.7 TB which can sustain 1 Drive Write Per Day for 5 years. Goes for €700 here in the Netherlands. Wouldn’t that be robust enough for on disk generation?

That would be only 1825 write cycles.

The Kingston DC600M seems to have "3D TLC NAND", which apparently supports between 1500 and 5000 write cycles (consistent with the 1825 number):
https://en.wikipedia.org/wiki/Flash_mem ... _endurance

There are also 60 (sequential writes) DWPD SSDs (Micron XTR series) that go for $1600 for 1.92 TB. So 4 of these are 10x as expensive as a single Kingston SSD for 60x the number of writes.

I haven’t been able to find an enterprise HDD with a DWPD greater than 1 (and there are articles on Tom’s hardware suggesting SSDs rival HDDs in reliability).

For people having the budget, I think you can use SSD’s as an expendable piece of scratch memory for generation, and then storing the results on much larger and inexpensive read only SSD or HDD.

[syzygy]

There are “Data Centre” SSDs, e.g. Kingston DC600M with 7.7 TB which can sustain 1 Drive Write Per Day for 5 years. Goes for €700 here in the Netherlands. Wouldn’t that be robust enough for on disk generation?

That would be only 1825 write cycles.

The Kingston DC600M seems to have "3D TLC NAND", which apparently supports between 1500 and 5000 write cycles (consistent with the 1825 number):
https://en.wikipedia.org/wiki/Flash_mem ... _endurance

There are also 60 (sequential writes) DWPD SSDs (Micron XTR series) that go for $1600 for 1.92 TB. So 4 of these are 10x as expensive as a single Kingston SSD for 60x the number of writes.

I haven’t been able to find an enterprise HDD with a DWPD greater than 1 (and there are articles on Tom’s hardware suggesting SSDs rival HDDs in reliability).

Are HDDs advertised with a guaranteed DWPD? I don't think HDDs will suffer from massive sequential read and write processes. There is no intrinsic limit on the number of rewrites of a disk sector. This is dfferent for flash memory.

For general use it might be true that SSDs rival HDDs in reliability, but here we are considering the specific use case of massive sequential read and write operations. (I assume Wu and Beal's algorithm only needs sequential disk operations. Otherwise it would have been useless in pre-SSD times.)

For people having the budget, I think you can use SSD’s as an expendable piece of scratch memory for generation, and then storing the results on much larger and inexpensive read only SSD or HDD.

But do they have a real advantage over HDDs? They are faster, but for the same price you can have a lot more HDDs (which you can use in parallel on the same system, or you can build multiple systems to generate tables in parallel).

But by the time that 1 petabyte of WDL data becomes managable, things may be different .

[Rein Halbersma]

Are HDDs advertised with a guaranteed DWPD? I don't think HDDs will suffer from massive sequential read and write processes. There is no intrinsic limit on the number of rewrites of a disk sector. This is different for flash memory.

I think the HDD failure mode is not the magnetic property of the disk but rather the spinning and mechanical wear. The Western Digital Enterprise HDDs are rated at 550 TB writes per year. I haven't found more reliable guarantees.

For an 8TB HDD, that's 70 total rewrites per year. So does that seem inadequate for Thompson or Wu& Beal heavy disk dependent generation?

The Kingston SSDs are rated at 365 rewrites of their capacity. Whichever way I look at it, SSDs come out better in all aspects except price per TB.

For general use it might be true that SSDs rival HDDs in reliability, but here we are considering the specific use case of massive sequential read and write operations. (I assume Wu and Beal's algorithm only needs sequential disk operations. Otherwise it would have been useless in pre-SSD times.)

Perhaps the 1990s HDDs were more reliable in terms of DWPD (i.e. independent from the capacity growth) than the current generation?

[syzygy]

I think the HDD failure mode is not the magnetic property of the disk but rather the spinning and mechanical wear. The Western Digital Enterprise HDDs aret I do rated at 550 TB writes per year. I haven't found more reliable guarantees.

For an 8TB HDD, that's 70 total rewrites per year. So does that seem inadequate for Thompson or Wu& Beal heavy disk dependent generation?

But the 550 TB/year number reported by WD (which seems to refer to total data transfer, not total writes) has meaning only for a particular workload. I guess WD reports this number only because nowadays people expect such a number based on their experience with SSDs. And I guess this number is based on a HDD configured to spin down when idle, which might just prevent a global apocalypse but will kill the HDD.

HDDs can keep their platters spinning for many years without any problem if you keep them spinning. And during read and write operations the head does not touch the platter, so it will hardly wear out. The main problem are head seeks during random I/O, but with sequential reads and writes head seeks are not really an issue. The 550 TB/year number reported by WD will not be based on massive sequential I/O.

For read-only workloads an SSD will be far more reliabile than a HDD.
For random I/O workloads, an SSD will be far more reliable than a HDD.
But sequential workloads with a lot of writes will favour HDDs heavily.

It is true that SSDs become "more reliable" (in terms of total data written) as their capacity increases, whereas this is not really the case for HDDs. But HDD reliability should not be an issue for purely sequential workloads.

[phhnguyen]

Of course there are cheaper methods of data storage than RAM. Disk drives of 1TB are sort of standard.

Generating the 7-piece tables on a big PC with at least 1TB of RAM is possible, too.
...
16 GB of RAM is enough to generate the 6-piece tables "in RAM".

I agreed we could use some computers with small memory sizes to generate endgames with multi-times larger sizes. However, the question is if it is worth doing that.

Generating an EGTB using on-fly large data stored on hard disks may slow down 5-10 times, compared with one using RAM only. Instead of waiting for a few months, we may have to wait for years!

I had some bad experiences when generating EGTBs with limited memory computers about 20 years ago when I tried to generate an Xiangqi EGTB on 2 computers with 8-16 GB RAM and run them over a year. It was terrible: electricity bills increased significantly, the generating was interrupted many times by electricity cuts, hardware faulted, hard disks failed… All the above, was a too tiring, lonely and boring process of checking, fixing code, recompiling, rerunning, backing up (weekly, monthly), managing works (copying files, backing up to CD/DVD, separating tasks between computers), and waiting. After a few months, you might lose almost all patience and motivation to work with it (generating).

The EGTB became too large and stored on several hard disks as well as on multiple DVD boxes (it was a disaster and downed morale whenever some hard disks or DVDs were broken). I don’t have a good Internet connection. Therefore, copying and sending hard disks/DVDs were the only way to contribute but that was expensive, slow and inconvenient at that time.

After all, I think I should create a new EGTB within a maximum of 6 months only. Not worth spending more. Therefore, I will generate endgames mainly in RAM even though I can support using disks for someone who wants.

To generate huge endgames requiring huge RAM, I am considering buying some old workstations with the RAM I need and the prices are quite reasonable. Their CPUs may be a bit out of date but they may be faster than the newer ones using mainly hard disks (but I’m not sure about that since I have not tested any of them).

Of course, it is ideal if someone with better hardware steps in to help generate those EGTBs.

[phhnguyen]

I think I have a viable algorithm for handling perpetuals. The basic idea is, when generating white wins, to specially mark btm positions that have no 'safe' moves to a non-won wtm position left, but still have some such unsafe moves. as candidate losses. (Where 'safe' means non-checking and not attacking any unprotected piece with non-K or non-P, and no R with H or C.) And then mark all wtm predecessors of such marked btm positions as candidate wins.

If an iteration added candidate losses, we then reaxamine all those, to see if any of their unsafe 'escapes' goes to a wtm position not marked as candidate win. If so, their status is chaned to 'cleared loss', and that of their predecessors to 'cleared wins'. This can lead to further clearing of their btm predecessors. If there is nothing left to clear, the remaining canditates are changed into wins and losses, as these correspond to checking/chasing cycles without exit. The cleared positions then revert back to candidates, and we continue with the next iteration.

I usually represent each board position as a byte, one bit for indicating won wtm positions, and 7 bits for the DTM of the lost btm positions. (That allows DTM up to 128, which is rathere generous.) But we need extra coding for the candidate and cleared marking. Wtm positions where white is checked can never be lost with btm, though, as black would capture the King. So we can use that to allow encoding more info of these wtm positions. For chasing this is less clear; if the chasing side (i.e. b.ack) had the move here he could convert to a simpler end-game by capturing the chased piece. Usually that would be to a non-lost position, as he now gained a piece, meaning there is also no DTM to encode in the btm position before the capture.

So we can reserve codes 2-201 for combinations of DTM 1-100 for btm, and the wtm won/non-won state, while codes 0 and 1 would indicate the wtm state for positions that are still undecided with btm. Codes 202-255 would then be available for marking positions that are parts of potential checking/chasing loops.

The generation would start with marking all positions where white is 'threatened', i.e. in check or has a hanging piece. The code in the 204-253 range should indicate which piece is threatened, to distinguish and allow 1-chases-many loops. During iteration this makes it easy to see whether black moves are safe by probing the EGT. Codes 202-205 are used to indicate btm candidate and cleared positions, with wtm won/non-won state. To avoid having to revert cleared positions to candidates every iteration, we swap the meaning of those codes every iteration.

If a so-far undecided btm position at some point during generation loses its last safe escape, we give it the current DTM code for candidate loss(without altering the wtm state). All wtm predecessors that were not yet won, and have threatened codes, will get those codes changed to the candidate form for the specific threat(s).

Clearing will have to be done in a way that is specific for the threatened piece. Candidate losses that have a move to a cleared win

* to be continued...

My simple solution is to use two special values in endgames: Perpetual_Check and Perpetual_Chase. We need some support from engines: whenever an engine gets those values it should check the current context and convert them into scores with the right added plies and it knows to avoid or repeat. Of course, the generator must implement the code to detect perpetual check/chase positions.

[hgm]

Generating an EGTB using on-fly large data stored on hard disks may slow down 5-10 times, compared with one using RAM only. Instead of waiting for a few months, we may have to wait for years!

But is stead of hours, you might have to wait a day. It probably would not be a very good idea from an economic point of view to spend many tens of thousands dollars on memory so that you could finish the job in a day instead of in a week, never having to use the memory again.

It all depends on what your final goal is, in terms of gigabyte-hours. If you have to work for a year to earn the money to buy a computer that does it in a day instead of a month with the computer you already have, it in fact took you a year instead of a month...

[hgm]

My simple solution is to use two special values in endgames: Perpetual_Check and Perpetual_Chase. We need some support from engines: whenever an engine gets those values it should check the current context and convert them into scores with the right added plies and it knows to avoid or repeat. Of course, the generator must implement the code to detect perpetual check/chase positions.

I cannot imagine how exactly that would work. Have you tried it on, say, KRPKR?