Question on Stockfish and SyzygyCache UCI option

[Zenmastur]

Non-uniform byte distribution in KRBvsKBP.RTBZ:




Non-uniform byte distribution in an uncompressed 4GB EGTB file:



Uniform byte distribution after compression of this file at ~ 20 to 1:



Regards,

Forrest

[Zenmastur]

I see why the files are the way they are. I haven't read the entire thread yet

You mentioned the use of a small dictionary used for compression. I'm wondering how small?

I have the same basic idea, but instead of producing a dictionary for each file I want to use the same dictionary for all files. It would be built offline using sample data from a representative group of files. Since all the TB's will be pawn-ful and can be several TB in size, the only "real" restriction on size of the dictionary will be encoding speed. From testing the optimal size for a single file with a dictionary built specifically for that file seems to be about 2-MB. Using a 16-MB dictionary doesn't gain much in the way of additional compression but only slows the encoding slightly (25%). This still allows encoding speeds in the good range (~30MB/sec). Since I can increase the size of the dictionary by a factor of eight and still have reasonable encoding speed I think its possible to construct a dictionary the will yield compression ratios almost as good as a 2-MB file specific dictionary.

The advantage of doing it this way is that the dictionary is known in advance and compression encoding can be done while the database is still being built.

Assuming a modest 12 to 1 compression (I actually expect closer to 16 to 1) ratio a machine with 128-Gb of ram could hold the entire contents of a 1.44 TB EGTB and still have 8-GB left over for the OS and generation program. While 128-GB is a lot of RAM many of the new desktop motherboards can handle this much memory.

This would considerably ease the problem of having enough ram to generate table-bases of a specific size. Once the EGTB is generated it could be re-compressed using the algorithm of your choice. i.e. an algorithm more probing friendly like current Syzygy files etc.

Regards,

Forrest

[syzygy]

I don't know what compression ratio your getting but it looks like it's possible to compress the files another 25-40%.

I'm sure you haven't tested on the bigger files (the ones that matter).

Since I limit the compression to 65536 values per 64-byte block, the most highly compressible tables can probably be compressed further. But the bigger tables are 98% or so random data for any general purpose compresser (only the index tables can be compressed a bit). Those are the tables that matter. Try it.

I didn't actually test it on any of your files since I don't have uncompressed versions of them, but the statistics I was looking at came from KRBvsKBP.RTBZ which is one of the largest file.

Duh... Have fun.

[hgm]

Assuming a modest 12 to 1 compression (I actually expect closer to 16 to 1) ratio a machine with 128-Gb of ram could hold the entire contents of a 1.44 TB EGTB and still have 8-GB left over for the OS and generation program.

It makes no sense whatsoever to hold a pawny EGT in RAM. It would just be occupying RAM with data that is not used, and would never be used. 8GB RAM should be more than enough to hold all the data you need (uncompressed) for building any pawny 7-men without any speed loss.

[Zenmastur]

Assuming a modest 12 to 1 compression (I actually expect closer to 16 to 1) ratio a machine with 128-Gb of ram could hold the entire contents of a 1.44 TB EGTB and still have 8-GB left over for the OS and generation program.

It makes no sense whatsoever to hold a pawny EGT in RAM. It would just be occupying RAM with data that is not used, and would never be used. 8GB RAM should be more than enough to hold all the data you need (uncompressed) for building any pawny 7-men without any speed loss.

These aren't general purpose table-bases. i.e Not all of the possible positions are considered, just those required to solve for the specific board position under consideration. They're not designed to be used as part of a chess playing program per say. Most of these positions have more than 7 men in them. E.G. I have done one position with 14 pieces (mostly pawns that are locked) although most have 8-12 men. e.g.

[d]7R/8/1b1pkpp1/1P1n4/4p1P1/1B6/3K4/8 b - - 0 52

or this

[d]6k1/6p1/3r3p/p1N5/P1P5/4PKPP/8/8 w - - 0 43


So what you are saying is that I should be able to everything needed to solve these position into a reasonable amount of ram with-out using compression, is that correct?

Regards,

Forrest

[Zenmastur]

Just to clarify the types of positions a little...

Not all the positions are as complicated as the ones in my previous post.

[d]8/8/P2kp3/3p4/1P2n3/5R2/5p2/2K5 b - - 0 53

This position is a little below the average size and can be solved on a single core in about 24 hours using lots of disk IO and about 1-GB of memory. With multiple disks and cores a single machine can solve about (# of cores-1) of these in a day with out much problem. SSD's help speed this process up quite a bit. Right now I'm limited by disk space to about 4-TB for generated table-bases. This just about covers what can be done in a 24 hour period. Of course this makes the machine this is running on useless for anything else. Excluding my wife's laptop, I have 7 desk-top machines and one lap top. Four of the desk-tops are non-functional due to age. Two of the desktops are older and aren't used much but are capable of serving as table-base generators. I figure for the cost of two HD's I can have these generating small to medium size table-bases on a 24/7 basis.

This is fine for the small to medium size problems, larger problems like the one's in my previous post would take several thousand core hours to generate. In between these extremes is a large group of positions that can be done in a few days to a month or so using current methods. I want these to be easier to generate. Being able to readily generate an 8 to 12 man table-based that solves a particular board position is do-able and I think will find applications with a large group of users.

Regards,

Forrest

[hgm]

So what you are saying is that I should be able to everything needed to solve these position into a reasonable amount of ram with-out using compression, is that correct?

Sure. They are basically just non-symmetric 4-men EGT, requiring only 256KB each if you store 1 byte per position (btm 7-bit DTM and wtm won/non-won bit).

You would need to hold the P-slice you are working on, and the successors to seed and probe it. And the number of pre-decessors is typically the number of Pawns. (But those on 2nd-rank count double, as as well as those being able to do PxP captures, and there could be twice as many really tiny capture successors.)

Of course you would have to write the results to disk anyway, if you are not building only to obtain statistics, and loading back the P-slices you need for your next build wouldn't really slow you down, as it is sequential access on 256KB chunks of disk space, which can be stored contiguously. So 2MB RAM would be enough for those positions. You can build them entirely in the L2 cache of a Core 2 Duo!

With a little bit more RAM you could already load the successor P-slices you need for your next build into RAM while you are working on the current build, as asynchrounous I/O. (In so far they don't overlap with the successors of the current build.)

[Zenmastur]

So what you are saying is that I should be able to everything needed to solve these position into a reasonable amount of ram with-out using compression, is that correct?

Sure. They are basically just non-symmetric 4-men EGT, requiring only 256KB each if you store 1 byte per position (btm 7-bit DTM and wtm won/non-won bit).

You would need to hold the P-slice you are working on, and the successors to seed and probe it. And the number of pre-decessors is typically the number of Pawns. (But those on 2nd-rank count double, as as well as those being able to do PxP captures, and there could be twice as many really tiny capture successors.)

Of course you would have to write the results to disk anyway, if you are not building only to obtain statistics, and loading back the P-slices you need for your next build wouldn't really slow you down, as it is sequential access on 256KB chunks of disk space, which can be stored contiguously. So 2MB RAM would be enough for those positions. You can build them entirely in the L2 cache of a Core 2 Duo!

With a little bit more RAM you could already load the successor P-slices you need for your next build into RAM while you are working on the current build, as asynchrounous I/O. (In so far they don't overlap with the successors of the current build.)

I'm not sure I understand your explanation, but I am sure I don't how you think this method will speed up the generation process. If I can store the whole database in memory, I only have to write once to disk. e.g.

[d] 8/8/P2kp3/3p4/1P2n3/5R2/5p2/2K5 b - - 0 53


This position requires about 750 GB of file space uncompressed. Doing it with small chunks takes a long time. I just did it on a very busy system and it took about 51 hours. I assume that if it had the sole use of a HD it would take half this time, and if it had a SSD all to it self, perhaps a short as 12-15 hours. If it were done in memory I suspect that a few hours would suffice.

As it turns out this position is a draw.

[d] 8/8/P2kp3/3p4/1P2n3/5R2/1K3p2/8 b - - 0 53

This, slightly modified position, is a win for white: 1... Kc7 2. a7 Kb7 3. Rf7+ Ka8 4. Ka3 d4 5. Ka4 d3 6. Ka5 Nd6 7. Rxf2 Kxa7 8. Rf3 Nc4+ 9. Kb5 Ne5 10. Rf2 Kb8 11. Kc5 Kc7 12. Rd2 Kb8 13. Rd1 Kc7 14. Kd4 Nc6+ 15. Kc3 Ne5 16. Rc1 Kd6 17. Ra1 Kd7 18. Ra6 Nc6 19. Rb6 Ne5 20. Rb5 Kd6 21. Kd2 Nf3+ 22. Kxd3 Ne5+ 23. Ke4 Nd7 24. Rg5 Kc7 25. Kd4 Kb6 26. Rg7 Kc7 27. Kc4 Kd6 28. b5 Ne5+ 29. Kb4 Nd7 30. Rh7 Nf6 31. Rh8 Ne4 32. Rh2 Kc7 33. Ka5 Kd6 34. b6 Nf6 35. b7 Kc7 36. Ka6 Nd7 37. Rh7 Kd6 38. Rxd7+ Kxd7 39. b8R Kc6 40. Rb5 Kd7 41. Ka5 Kd6 42. Kb4 e5 43. Kc3 Ke6 44. Kd3 Kf5 45. Rb4 Ke6 46. Ke4 Kd7 47. Kd5 Kc7 48. Ra4 Kb6 49. Kd6 e4 50. Rxe4 Kb5 51. Rd4 Kb6 52. Rd5 Kb7 53. Rb5+ Ka6 54. Kc6 Ka7 55. Kc7 Ka6 56. Rh5 Ka7 57. Ra5#


I'm thinking that the process could be sped up even more if I used Syzygy or Namilov as an underlayment (so to speak). This would alleviate the need to calculate all the smaller dependant Tb's in the hierarchy like it does now.

Regards,

Forrest