7-men Syzygy attempt

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.
syzygy
Posts: 4455
Joined: Tue Feb 28, 2012 10:56 pm

Re: 7-men Syzygy attempt

Post by syzygy » Mon May 21, 2018 4:55 pm

syzygy wrote:
Mon May 21, 2018 4:32 pm
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
Posts: 10118
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: 7-men Syzygy attempt

Post by Dann Corbit » Mon May 21, 2018 10:36 pm

noobpwnftw wrote:
Mon May 21, 2018 2:09 pm
syzygy wrote:
Mon May 14, 2018 7:29 pm
duncan wrote:
Mon May 14, 2018 7:14 pm
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.
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.

noobpwnftw
Posts: 360
Joined: Sun Nov 08, 2015 10:10 pm

Re: 7-men Syzygy attempt

Post by noobpwnftw » Mon May 21, 2018 10:38 pm

Dann Corbit wrote:
Mon May 21, 2018 10:36 pm
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
Posts: 10118
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: 7-men Syzygy attempt

Post by Dann Corbit » Mon May 21, 2018 10:55 pm

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.
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.

duncan
Posts: 10339
Joined: Mon Jul 07, 2008 8:50 pm

Re: 7-men Syzygy attempt

Post by duncan » Mon May 21, 2018 11:01 pm

noobpwnftw wrote:
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
Posts: 360
Joined: Sun Nov 08, 2015 10:10 pm

Re: 7-men Syzygy attempt

Post by noobpwnftw » Mon May 21, 2018 11:18 pm

Dann Corbit wrote:
Mon May 21, 2018 10:55 pm
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
Posts: 10118
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: 7-men Syzygy attempt

Post by Dann Corbit » Tue May 22, 2018 3:55 am

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.
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.

User avatar
Nordlandia
Posts: 2452
Joined: Fri Sep 25, 2015 7:38 pm
Location: Sortland, Norway

Re: 7-men Syzygy attempt

Post by Nordlandia » Tue May 22, 2018 5:17 am

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

Syzygy with better compression is doable, i suppose.

Sesse
Posts: 180
Joined: Mon Apr 30, 2018 9:51 pm
Contact:

Re: 7-men Syzygy attempt

Post by Sesse » Tue May 22, 2018 7:31 am

duncan wrote:
Mon May 21, 2018 11:01 pm
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
Posts: 360
Joined: Sun Nov 08, 2015 10:10 pm

Re: 7-men Syzygy attempt

Post by noobpwnftw » Tue May 22, 2018 9:29 am

Sesse wrote:
Tue May 22, 2018 7:31 am
duncan wrote:
Mon May 21, 2018 11:01 pm
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.

Post Reply