7-men Syzygy attempt

[Rein Halbersma]

One of my two machines only have 1TB memory, so now I let it build pawnful ones to avoid using the -d option. Expectation is that they will finish 5+2 pawnless and 6+1 pawnful in about the same time. Then I may move on to 4+3 pawnless and 5+2 pawnful. Eventually one can work on 4(p)+3 and the other on 4+3(p).

Is it sound to arrange tasks like this? I think they will not require each other's ongoing sets to proceed their own work.

Yes, 6+1, 5+2 and 4+3 can be built independently.

I'm working on fixing DTZ generation for the few tables with very high DTZ.

Then I'll look into making the generator more efficient for tables with multiple pieces of the same type and colour. But that won't be trivial.

What exactly is the problem with identical pieces? Enumeration and (un)ranking k-subsets can be done efficiently on bitboards.

[Nordlandia]

Is it likely Seagate IronWolf 12 TB to be sufficient for storing 7-man wdl?

Adjudication only need wdl as source.

10 TB price: 350 dollar.

12 TB price: 435 dollar.

WD 12TB My Book Duo Desktop for 415.77 dollar at amazon.

[syzygy]

One of my two machines only have 1TB memory, so now I let it build pawnful ones to avoid using the -d option. Expectation is that they will finish 5+2 pawnless and 6+1 pawnful in about the same time. Then I may move on to 4+3 pawnless and 5+2 pawnful. Eventually one can work on 4(p)+3 and the other on 4+3(p).

Is it sound to arrange tasks like this? I think they will not require each other's ongoing sets to proceed their own work.

Yes, 6+1, 5+2 and 4+3 can be built independently.

I'm working on fixing DTZ generation for the few tables with very high DTZ.

Then I'll look into making the generator more efficient for tables with multiple pieces of the same type and colour. But that won't be trivial.

What exactly is the problem with identical pieces? Enumeration and (un)ranking k-subsets can be done efficiently on bitboards.

The problem is adapting the current code to do that.

I have a bunch of macros like this:

Code: Select all

#define FILL_OCC \
  occ = 0; \
  for (i = n - 1, idx2 = idx; i > 1; i--, idx2 >>= 6) \
    bit_set(occ, p[i] = idx2 & 0x3f); \
  bit_set(occ, p[0] = KK_inv[idx2][0]); \
  bit_set(occ, p[1] = KK_inv[idx2][1]);

This reads out the position encoded in idx and creates an occupancy bitboard occ and an array of piece positions p[].

So the white king and black king are encoded in the index as 0-461 shifted by 6*(n-2). The remaining n-2 pieces are encoded as 0-63, occupying 6 bits of the index each.

If there identical pieces, I could change the indexing scheme to let pieces 2 and 3 occupy 11 bits (2048 >= 64*63/2), halving the table size during generation.

Then I have some functions to make moves by transforming the idx (long64 is just uint64_t):

Code: Select all

#define MIRROR_A1H8&#40;x&#41; (((&#40;x&#41; & mask_a1h8&#41; << 3&#41; | ((&#40;x&#41; >> 3&#41; & mask_a1h8&#41;)

static long64 __inline__ MakeMove0&#40;long64 idx, int wk&#41;
&#123;
  long64 idx2 = idx >> shift&#91;1&#93;;
  int bk = KK_inv&#91;idx2&#93;&#91;1&#93;;
  idx &= ~mask&#91;0&#93;;
  idx ^= sq_mask&#91;wk&#93;;
  if &#40;mirror&#91;wk&#93;&#91;bk&#93; < 0&#41; idx = MIRROR_A1H8&#40;idx&#41;;
  return idx | (&#40;long64&#41;KK_map&#91;wk&#93;&#91;bk&#93; << shift&#91;1&#93;);
&#125;

static long64 __inline__ MakeMove1&#40;long64 idx, int bk&#41;
&#123;
  int wk = KK_inv&#91;idx >> shift&#91;1&#93;&#93;&#91;0&#93;;
  idx &= ~mask&#91;0&#93;;
  if &#40;mirror&#91;wk&#93;&#91;bk&#93; < 0&#41; idx = MIRROR_A1H8&#40;idx&#41;;
  return idx | (&#40;long64&#41;KK_map&#91;wk&#93;&#91;bk&#93; << shift&#91;1&#93;);
&#125;

static long64 __inline__ MakeMove2&#40;long64 idx, int k, int sq&#41;
&#123;
  return idx | (&#40;long64&#41;sq << shift&#91;k&#93;);
&#125;

MakeMove0 move the white king, MakeMove1 moves the black king, MakeMove2 moves any of the other pieces (the position of the piece being moved having already been masked out).

So I'll have to adapt this to let MakeMove0 and MakeMove1 properly mirror pieces 2 and 3 into the three axes and I'll need to rename MakeMove2 and insert a MakeMove2 and MakeMove3 to move pieces 2 and 3.

A bunch of other stuff needs to be adapted in a similar way. For example, I have this macro to perform an operation on all positions reachable by unmoves:

Code: Select all

#define RETRO(func, ...) \
  do { int j; \
    if (pcs_opp[0] == 0) \
      func##_pivot0(table_opp, idx, occ, p, ##__VA_ARGS__); \
    else \
      func##_pivot1(table_opp, idx, occ, p, ##__VA_ARGS__); \
    for (j = 1; pcs_opp[j] >= 0; j++) { \
      int k = pcs_opp[j]; \
      func(k, table_opp, idx & ~mask[k], occ, p , ##__VA_ARGS__); \
    } \
  } while (0)

I'll need to add func##_piece2 and func##_piece3 steps and corresponding function implementations.

So this will basically need a fork of the whole generator (or a separate set of source files).

Ideally, I would do this not only for tables with two identical pieces, but also for tables with three or four identical pieces or with two sets of two identical pieces. And ideally, the identical pieces do need to be in positions 2 and 3 (good if they are Ns) but may also be at the end (good if they are Qs).

Now I have a question for you: do you think C++ template programming could be of use here? For example to produce a generator program for each specific piece combination?


A possible alternative is to let go of time-efficient indexing during generation and to switch to the indexing I use for the compressed table format. Since memory bandwidth is the limiting factor, this may be a good idea.

[syzygy]

[pgn][FEN "R7/8/7B/8/8/7k/1R2q3/Q1K5 b - - 0 1"]
[Annotator "syzygy-tables.info"]

{ DTZ -80 } 1... Qe1+ 2. Kc2 Qe4+ 3. Kb3 Qd5+ 4. Kb4 Qb7+ 5. Kc5 Qc7+ 6. Kd5 Qf7+ 7. Kc6 Qe6+ 8. Kb5 Qd5+ 9. Kb6 Qd6+ 10. Ka7 Qd4+ 11. Kb7 Qe4+ 12. Kb6 Qd4+ 13. Kc7 Qc5+ 14. Kd7 Qf5+ 15. Ke7 Qh7+ 16. Kd8 Qh8+ 17. Kd7 Qh7+ 18. Kc6 Qe4+ 19. Kd6 Qd4+ 20. Ke6 Qe4+ 21. Kf7 Qc4+ 22. Kf8 Qc5+ 23. Kg8 Qd5+ 24. Kh8 Qe5+ 25. Bg7 Qh5+ 26. Kg8 Qd5+ 27. Kf8 Qd6+ 28. Kf7 Qd7+ 29. Kf6 Qd6+ 30. Kf5 Qd7+ 31. Ke4 Qg4+ 32. Kd3 Qf3+ 33. Kc4 Qc6+ 34. Kb4 Qb7+ 35. Ka5 Qc7+ 36. Ka4 Qc6+ 37. Rb5 Qc4+ 38. Ka3 Qg4 39. Qa2 Qd1 40. Qb3+ Qd3 41. Qxd3+ { KQRRBvK with DTZ -4 } 41... Kg2 42. Rb1 Kf2 43. Rg1 Kxg1 { KQRBvK with DTZ 3 } 44. Qc2 Kf1 45. Qf2+ Kxf2 { KRBvK with DTZ 17 } 46. Kb2 Ke3 47. Ra4 Kd3 48. Be5 Kd2 49. Ra3 Ke1 50. Kc2 Ke2 51. Rg3 Ke1 52. Bd4 Ke2 53. Bf2 Kf1 54. Kd1 Kxf2 { KRvK with DTZ 11 } 55. Ra3 Kf1 56. Ra2 Kg1 57. Ke1 Kh1 58. Kf2 Kh2 59. Ra3 Kh1 60. Rh3# { Checkmate } 1-0[/pgn]
DTZ-optimal play has its problems

[Nordlandia]

I know syzygy don't always go for shortest mates. My idea is if syzygy somehow did go for shorest mates, those extra moves can potentially save a good amount of space. Mate in 49 versus 60 mean less space used, just a thought.

[d]R7/8/7B/8/8/7k/1R2q3/Q1K5 b - -

[pgn][Event "White mates in 48"]
[Site "Lomonosov Tablebases"]
[Date "????.??.??"]
[Round "http://tb7.chessok.com/probe"]
[White "?"]
[Black "?"]
[Result "1-0"]
[SetUp "1"]
[FEN "R7/8/7B/8/8/7k/1R2q3/Q1K5 b - -"]

1...Qe1+ 2.Kc2 Qe4+ 3.Kc3 Qc6+ 4.Kb4 Qb7+ 5.Kc5 Qc7+ 6.Kd5 Qf7+ 7.Kd4 Qf6+ 8.
Kc5 Qf5+ 9.Kb6 Qf6+ 10.Ka7 Qd4+ 11.Kb7 Qe4+ 12.Kb6 Qd4+ 13.Kc7 Qc5+ 14.Kd7
Qf5+ 15.Ke7 Qh7+ 16.Kd8 Qh8+ 17.Kd7 Qh7+ 18.Kc6 Qe4+ 19.Kd6 Qd4+ 20.Ke6 Qe4+
21.Kf7 Qc4+ 22.Kg7 Qd4+ 23.Kh7 Qe4+ 24.Kh8 Qe5+ 25.Bg7 Qh5+ 26.Kg8 Qd5+ 27.Kf8
Qd6+ 28.Kf7 Qd7+ 29.Kf6 Qd6+ 30.Kg5 Qe5+ 31.Kg6 Qe4+ 32.Kf6 Qd4+ 33.Ke6 Qg4+
34.Kd6 Qg6+ 35.Kc5 Qf5+ 36.Kb6 Qe6+ 37.Ka7 Qe7+ 38.Rb7 Qc5+ 39.Ka6 Qc4+ 40.Ka5
Qc5+ 41.Ka4 Qc4+ 42.Ka3 Qc5+ 43.Rb4 Qf5 44.Bh6 Qd5 45.Qf1+ Kg3 46.Rb3+ Qxb3+
47.Kxb3 Kg4 48.Rg8+ Kh4 49.Qh1# 1-0[/pgn]

[Rein Halbersma]

What exactly is the problem with identical pieces? Enumeration and (un)ranking k-subsets can be done efficiently on bitboards.

The problem is adapting the current code to do that.

I have a bunch of macros like this:

Code: Select all

#define FILL_OCC \
  occ = 0; \
  for (i = n - 1, idx2 = idx; i > 1; i--, idx2 >>= 6) \
    bit_set(occ, p[i] = idx2 & 0x3f); \
  bit_set(occ, p[0] = KK_inv[idx2][0]); \
  bit_set(occ, p[1] = KK_inv[idx2][1]);

This reads out the position encoded in idx and creates an occupancy bitboard occ and an array of piece positions p[].

So the white king and black king are encoded in the index as 0-461 shifted by 6*(n-2). The remaining n-2 pieces are encoded as 0-63, occupying 6 bits of the index each.

If there identical pieces, I could change the indexing scheme to let pieces 2 and 3 occupy 11 bits (2048 >= 64*63/2), halving the table size during generation.

Then I have some functions to make moves by transforming the idx (long64 is just uint64_t):

Code: Select all

#define MIRROR_A1H8&#40;x&#41; (((&#40;x&#41; & mask_a1h8&#41; << 3&#41; | ((&#40;x&#41; >> 3&#41; & mask_a1h8&#41;)

static long64 __inline__ MakeMove0&#40;long64 idx, int wk&#41;
&#123;
  long64 idx2 = idx >> shift&#91;1&#93;;
  int bk = KK_inv&#91;idx2&#93;&#91;1&#93;;
  idx &= ~mask&#91;0&#93;;
  idx ^= sq_mask&#91;wk&#93;;
  if &#40;mirror&#91;wk&#93;&#91;bk&#93; < 0&#41; idx = MIRROR_A1H8&#40;idx&#41;;
  return idx | (&#40;long64&#41;KK_map&#91;wk&#93;&#91;bk&#93; << shift&#91;1&#93;);
&#125;

static long64 __inline__ MakeMove1&#40;long64 idx, int bk&#41;
&#123;
  int wk = KK_inv&#91;idx >> shift&#91;1&#93;&#93;&#91;0&#93;;
  idx &= ~mask&#91;0&#93;;
  if &#40;mirror&#91;wk&#93;&#91;bk&#93; < 0&#41; idx = MIRROR_A1H8&#40;idx&#41;;
  return idx | (&#40;long64&#41;KK_map&#91;wk&#93;&#91;bk&#93; << shift&#91;1&#93;);
&#125;

static long64 __inline__ MakeMove2&#40;long64 idx, int k, int sq&#41;
&#123;
  return idx | (&#40;long64&#41;sq << shift&#91;k&#93;);
&#125;

MakeMove0 move the white king, MakeMove1 moves the black king, MakeMove2 moves any of the other pieces (the position of the piece being moved having already been masked out).

So I'll have to adapt this to let MakeMove0 and MakeMove1 properly mirror pieces 2 and 3 into the three axes and I'll need to rename MakeMove2 and insert a MakeMove2 and MakeMove3 to move pieces 2 and 3.

A bunch of other stuff needs to be adapted in a similar way. For example, I have this macro to perform an operation on all positions reachable by unmoves:

Code: Select all

#define RETRO(func, ...) \
  do { int j; \
    if (pcs_opp[0] == 0) \
      func##_pivot0(table_opp, idx, occ, p, ##__VA_ARGS__); \
    else \
      func##_pivot1(table_opp, idx, occ, p, ##__VA_ARGS__); \
    for (j = 1; pcs_opp[j] >= 0; j++) { \
      int k = pcs_opp[j]; \
      func(k, table_opp, idx & ~mask[k], occ, p , ##__VA_ARGS__); \
    } \
  } while (0)

I'll need to add func##_piece2 and func##_piece3 steps and corresponding function implementations.

So this will basically need a fork of the whole generator (or a separate set of source files).

Ideally, I would do this not only for tables with two identical pieces, but also for tables with three or four identical pieces or with two sets of two identical pieces. And ideally, the identical pieces do need to be in positions 2 and 3 (good if they are Ns) but may also be at the end (good if they are Qs).

Now I have a question for you: do you think C++ template programming could be of use here? For example to produce a generator program for each specific piece combination?


A possible alternative is to let go of time-efficient indexing during generation and to switch to the indexing I use for the compressed table format. Since memory bandwidth is the limiting factor, this may be a good idea.

So IIUC, your indexing for an N-piece db is essentially 462 times an N-2 digit base-64 number? And you do make/undo move directly on the index rather than going to a bitboard, moving and going back to the index?

In draughts, indexing is a 4-piece digit in the combinatorial number system, where each digit represents the entire bitboard of a piece type (black kings/men, white kings/men). Each bitboard of K pieces is a K-subset. Make/undo moves is done via the roundabout way. This is probably slower than what you do, but it saves a lot of space if K>=4.

For draughts-type indexing, you don't really need C++ templates. I don't know your method well enough to recommend them for you either. I would expect that simple overloads with 2, 3, and 4 arguments is easy enough, unless you can write your functions for general N, then you can write a single function template with a variadic number of arguments.

[syzygy]

I know syzygy don't always go for shortest mates. My idea is if syzygy somehow did go for shorest mates, those extra moves can potentially save a good amount of space. Mate in 49 versus 60 mean less space used, just a thought.

It doesn't exactly work like that.

[koedem]

I know syzygy don't always go for shortest mates. My idea is if syzygy somehow did go for shorest mates, those extra moves can potentially save a good amount of space. Mate in 49 versus 60 mean less space used, just a thought.

But if you can convert in 40 moves instead of mate in 49 your numbers are on average smaller. (I don't know how exactly DTZ values are stored but I have to assume smaller is better)

[syzygy]

So IIUC, your indexing for an N-piece db is essentially 462 times an N-2 digit base-64 number? And you do make/undo move directly on the index rather than going to a bitboard, moving and going back to the index?

Yes. Of course only during generation.

In draughts, indexing is a 4-piece digit in the combinatorial number system, where each digit represents the entire bitboard of a piece type (black kings/men, white kings/men). Each bitboard of K pieces is a K-subset. Make/undo moves is done via the roundabout way. This is probably slower than what you do, but it saves a lot of space if K>=4.

My approach does not make sense for draughts where all tables with >= 5 pieces (which is small) have at least one duplicate piece. With chess there are many 6-piece tables without duplicate pieces, and if you want to generate 6-piece tables you need enough memory to deal with the biggest ones. For 7-piece tables the story is similar, except that total generation time (and memory bandwidth limits) may make it worthwhile to reconsider the approach.

For draughts-type indexing, you don't really need C++ templates. I don't know your method well enough to recommend them for you either. I would expect that simple overloads with 2, 3, and 4 arguments is easy enough, unless you can write your functions for general N, then you can write a single function template with a variadic number of arguments.

I wonder if C++ templates could be used for the code generation I would need. Instead of
https://github.com/syzygy1/tb/blob/ed76 ... c#L71-L115
I'd like to give the compiler two strings of pieces like KRNN and KBB and have it generate:
- check_loss<WHITE> which tries out king moves, rook moves, NN moves, and
- check_loss<BLACK> which tries out king moves, BB moves.

[syzygy]

I know syzygy don't always go for shortest mates. My idea is if syzygy somehow did go for shorest mates, those extra moves can potentially save a good amount of space. Mate in 49 versus 60 mean less space used, just a thought.

But if you can convert in 40 moves instead of mate in 49 your numbers are on average smaller. (I don't know how exactly DTZ values are stored but I have to assume smaller is better)

You are right.