7-men Syzygy attempt

[syzygy]

There are 3570 pawnless 6-piece antichess tables and 4830 pawnful ones.

These are actually the numbers of 2, 3, 4, 5 and 6-piece tables.

If I made no mistake, the numbers of antichess tables are as follows:

Code: Select all

# pieces  pawnless  pawnful   total
   2          15         6       21
   3          75        51      126
   4         295       272      567
   5         875      1057     1932
   6        2310      3444     5754
   7        5390     15120    20510

[Dann Corbit]

do you know if the new generator will also work for 8 pieces ?

In theory it should work. In practice you'll need a very very big machine and a lot of patience.

It would probably be a good idea to rewrite the generator to use a more space-efficient indexing scheme during generation. Generation of the biggest table should then fit in about 41 TB (so let's say 48 TB) and most tables would need half of that or less. The current scheme would need 57.75 TB (so basically a 64 TB machine).

The bigger 8-piece tables will fill more than 2^32 64-byte blocks with compressed data, which means the format will need a relatively small extension to deal with them.

In practice, building full 7-piece tables is going to take more than half a year on my two machines, with 8-piece at current speed it probably gonna take a century to build the full set. So I'd just wait for the hardware developments to reach that reasonable level first.

While we wait, I'm getting extra storage ready for other interesting metrics(like DTM50) or variations(antichess, suiside) if there is interest, so after having full 7-piece DTZ50 on standard done, shall we try building stuff like those?

The DTM is very interesting because it plays perfect chess. The others only lead to wins, but can even do awful things like throw away a piece to get to a known win.

[noobpwnftw]

The DTM is very interesting because it plays perfect chess. The others only lead to wins, but can even do awful things like throw away a piece to get to a known win.

Define "perfect".

[Dann Corbit]

By perfect I mean that every move is optimal from the supplied root position. No move results in a shorter mate.
It is also possible to preserve maximal material if there are several paths to checkmate, all of the same length.

DTZ tables do not guarantee shortest mate. Only a sure win.
Same for bitbase.

I guess I see it like this:
bitbase -> show winning moves if there are any, show drawing moves if no winning moves. Theoretically possible to not win a won game if you pick a bad path.
DTZ -> similar but better information. I do not know if you can toss a win, but I suspect it is possible if you do not choose the shortest path to the win and the 100 ply counter gets exhausted.
DTM -> optimal moves.

Now, if it is not DTM50, then the chess programmer will have to look at the distance returned and at his 100 ply counter to see if it is cursed or blessed. But it still offers the best possible move path, albeit with more work on the programmer's part.

[duncan]

In practice, building full 7-piece tables is going to take more than half a year on my two machines, with 8-piece at current speed it probably gonna take a century to build the full set. So I'd just wait for the hardware developments to reach that reasonable level first.

any estimate how long for the hardware developments to reach that reasonable level first. 7-10 years ?

[noobpwnftw]

By perfect I mean that every move is optimal from the supplied root position. No move results in a shorter mate.
It is also possible to preserve maximal material if there are several paths to checkmate, all of the same length.

DTZ tables do not guarantee shortest mate. Only a sure win.
Same for bitbase.

I guess I see it like this:
bitbase -> show winning moves if there are any, show drawing moves if no winning moves. Theoretically possible to not win a won game if you pick a bad path.
DTZ -> similar but better information. I do not know if you can toss a win, but I suspect it is possible if you do not choose the shortest path to the win and the 100 ply counter gets exhausted.
DTM -> optimal moves.

Now, if it is not DTM50, then the chess programmer will have to look at the distance returned and at his 100 ply counter to see if it is cursed or blessed. But it still offers the best possible move path, albeit with more work on the programmer's part.

Your best possible DTM path must ignore 50-move rule completely, because there may be multiple times that you need to pick the sub-optimal DTM move in favor of a counter reset. In fact, you wouldn't be able to know if a win under 50-move rule is actually achievable without expansive search, it would need looking for all possible paths for which satisfies the counter by raising some DTM but still the overall shortest.

DTM50 basically stores the counter along with DTM(I guess), and when the counter reaches 100 ply then it is blessed/cursed and considered drawn at next iteration, when there is a zeroing move the counter gets reset while the DTM keeps going. It looks not difficult to do aside from doubling memory requirements. But I guess it would be too different from current Syzygy implementation in other parts and probably immense in file size.

[Dann Corbit]

Probably ignorant on my part, but could it be possible to pass in the current game state to the EGTB reader method of a DTM file?
It would then have knowledge of the visited positions and the half move clock.
Instead of a simple lookup, it would require a search.
I don't see why it would not work, but probably it is just my lack of vision in understanding how these files really work.

[Nordlandia]

Remember Galen's DTM50 was uncompressed raw files. http://galen.metapath.org/egtb50/

Syzygy with better compression is doable, i suppose.

[Sesse]

any estimate how long for the hardware developments to reach that reasonable level first. 7-10 years ?

An entity that really wanted to could probably already build 8-man tables; you just need to parallelize the generation and have tons of hardware. E.g., at some point when I worked in Google, I made a simple tablebase generator that worked as a MapReduce (I never built more than 4-man tables or something, though). For reference, Google did a 50 PB MapReduce already in 2012, so the amounts of data that need to be shuffled are clearly within range of practicality.

[noobpwnftw]

any estimate how long for the hardware developments to reach that reasonable level first. 7-10 years ?

An entity that really wanted to could probably already build 8-man tables; you just need to parallelize the generation and have tons of hardware. E.g., at some point when I worked in Google, I made a simple tablebase generator that worked as a MapReduce (I never built more than 4-man tables or something, though). For reference, Google did a 50 PB MapReduce already in 2012, so the amounts of data that need to be shuffled are clearly within range of practicality.

Well, for some reason the 7-piece demands were around about 15 years ago and up till now we see only one entity Lomonosov that actually did it in practice, at least in the public. I bet it is more beneficial somehow for all those supercomputers and large clusters to do their petabyte scale word counting MRs than building some tablebases.