Question to syzygy author

[syzygy]

I still don't understand why if

Code: Select all

LeadPawnIdx[leadPawnsCnt - 1][mappedLeadSq] = idx;

then, in the actual encoding, we use it in this way

Code: Select all

idx = LeadPawnIdx[leadPawnsCnt - 1][23 - MapToEdges[squares[0]] / 2];

instead of

Code: Select all

idx = LeadPawnIdx[leadPawnsCnt - 1][MapToEdges[squares[0]]];

I think I have to ask you this question
The original code reads as follows:

Code: Select all

  idx = pawnidx[t][flap[pos[0]]];

where

Code: Select all

static const ubyte flap[] = {
  0, 0, 0, 0, 0, 0, 0, 0,
  0, 6, 12, 18, 18, 12, 6, 0,
  1, 7, 13, 19, 19, 13, 7, 1,
  2, 8, 14, 20, 20, 14, 8, 2,
  3, 9, 15, 21, 21, 15, 9, 3,
  4, 10, 16, 22, 22, 16, 10, 4,
  5, 11, 17, 23, 23, 17, 11, 5,
  0, 0, 0, 0, 0, 0, 0, 0
};

Your MapToEdges[] is my ptwist[]:

Code: Select all

static const ubyte ptwist[] = {
  0, 0, 0, 0, 0, 0, 0, 0,
  47, 35, 23, 11, 10, 22, 34, 46,
  45, 33, 21, 9, 8, 20, 32, 44,
  43, 31, 19, 7, 6, 18, 30, 42,
  41, 29, 17, 5, 4, 16, 28, 40,
  39, 27, 15, 3, 2, 14, 26, 38,
  37, 25, 13, 1, 0, 12, 24, 36,
  0, 0, 0, 0, 0, 0, 0, 0
};

So things seem to be OK.
The reason I change the order in ptwist[] compared to flap[] is that this allows me to place the non-leading pawns in (renumbered) squares 0 to ptwist[square_of_leading_pawn]-1.

A recurring trick in the encoding function is this. I have k like pieces (same color, same type) that can be in n (remapped) squares 0 to n-1. The number of possibilities for this is Bin(n, k), which is basic combinatorics. But how to find an actual mapping of sets of squares s_1, ...., s_k to a number in 0...Bin(n,k)-1? There is a surprisingly easy formula. First sort the squares to get 0 <= s_1 < s_2 < ... < s_k < n (this is critical). Now the formula is:

Code: Select all

idx = Bin(s_1, 1) + Bin(s_2, 2) + ... + Bin(s_k, k).

(See this and this post.)

I noticed that you moved the step of sorting on ptwist[] / MapToEdges[] to before the horizontal flip. I think that will lead to problems if two non-leading pawns are in symmetric positions, because their positions now have to be swapped. You wrote:

Code: Select all

    // Encode leading pawns. Note that any previous horizontal flip preserves
    // the order because MapToEdges[] is (almost) flip invariant.

but I think the flip only "almost" preserves the order, which is not enough.

P.S: I have tried the latter: it crashes.

Even if it did not crash, any change in the indexing scheme would need a corresponding change in the generator (and a regeneration of all tables).

[Michel]

A recurring trick in the encoding function is this. I have k like pieces (same color, same type) that can be in n (remapped) squares 0 to n-1. The number of possibilities for this is Bin(n, k), which is basic combinatorics. But how to find an actual mapping of sets of squares s_1, ...., s_k to a number in 0...Bin(n,k)-1? There is a surprisingly easy formula. First sort the squares to get 0 <= s_1 < s_2 < ... < s_k < n (this is critical). Now the formula is:
Code:
idx = Bin(s_1, 1) + Bin(s_2, 2) + ... + Bin(s_k, k).

That's really nice!!

I did manage to find the formula on Google

https://books.google.be/books?id=6nXRBQ ... al&f=false

(see 5.22).

[syzygy]

Also I wonder about the overhead caused by the use of "std::short". Usually only a single element needs to be sorted, i.e. no sorting is necessary at all. Two is already somewhat exceptional and three or more is very rare.

I don't think the compiler can determine at compile-time that the number of elements to be sorted will be very small, so it is up to the std::short implementation to first check the number of elements at run-time and then invoke a simple quadratic sort.

Well, my background is C

[syzygy]

A recurring trick in the encoding function is this. I have k like pieces (same color, same type) that can be in n (remapped) squares 0 to n-1. The number of possibilities for this is Bin(n, k), which is basic combinatorics. But how to find an actual mapping of sets of squares s_1, ...., s_k to a number in 0...Bin(n,k)-1? There is a surprisingly easy formula. First sort the squares to get 0 <= s_1 < s_2 < ... < s_k < n (this is critical). Now the formula is:
Code:
idx = Bin(s_1, 1) + Bin(s_2, 2) + ... + Bin(s_k, k).

That's really nice!!

I did manage to find the formula on Google

https://books.google.be/books?id=6nXRBQ ... al&f=false

(see 5.22).

Yes, it's the same.

As I mentioned at the end of the thread I linked to, the formula was also given in this post by a user named "guido": But he is too pessimistic about the decoding step (or did not realise how difficult solving diophantine equations is in general).

It seems my encoding functions from 2000 already used it::

Code: Select all

	  index += p2 + p3*(p3-1)/2 + p4*(p4-1)*(p4-2)/6;

but not entirely consistenly. I guess I figured it out while writing all these 25 very specific functions (I think I wrote 13 above, but by mistake I only counted the lines):

Code: Select all

int encode_11(struct TBEntry *ptr), encode_111(struct TBEntry *ptr);
int encode_1111(struct TBEntry *ptr), encode_12(struct TBEntry *ptr);
int encode_112(struct TBEntry *ptr), encode_13(struct TBEntry *ptr);
int encode_22(struct TBEntry *ptr), encode_1p1(struct TBEntry *ptr);
int encode_1p1p(struct TBEntry *ptr), encode_1p11(struct TBEntry *ptr);
int encode_1p2(struct TBEntry *ptr), encode_1p1p1(struct TBEntry *ptr);
int encode_2p1(struct TBEntry *ptr), encode_1p2p(struct TBEntry *ptr);
int encode_1p111(struct TBEntry *ptr), encode_1p12(struct TBEntry *ptr);
int encode_1p3(struct TBEntry *ptr), encode_1p1p11(struct TBEntry *ptr);
int encode_1p1p2(struct TBEntry *ptr), encode_2p11(struct TBEntry *ptr);
int encode_1p2p1(struct TBEntry *ptr), encode_3p1(struct TBEntry *ptr);
int encode_2p2(struct TBEntry *ptr), encode_1p3p(struct TBEntry *ptr);
int encode_2p2p(struct TBEntry *ptr);

The function encode_22() (for suicide tables like RRvNN) is 377 lines. It maps all orbits of RRvNN under D_4 bijectively to 0...477589. The corresponding function decode_22() has 408 lines.

I extended this "perfect" mapping to all 5-piece combinations using some well-chosen helper functions. Encode_22() became "only" 94 lines, but decode_22() still 315 lines. Most complicated are probably encode_23() and decode_23() with 148 and 569 lines (number of orbits is 9533860).

By that time I realised it is not worth the effort to remove the last 0.1% of symmetry (however, a perfect bijection is convenient to have during generation of the table, except that it is not smart to use such complicated mappings during table generation).

Still, I wonder if there is a generic algorithm for indexing/ranking orbits of certain configurations under a group action. Counting the number of orbits is easy enough using Burnside's Lemma, but finding a bijection?

The title of chapter 9 of Loehr's book is promising, but I seem to have exceeded my reading limit.

[mcostalba]

I think I have to ask you this question

I realized that LeadPawnIdx[] and LeadPawnsGroupSize[] are deeply bounded to MapToEdges[], so I rewrote and unified the init functions in a single (simpler) one:

https://github.com/official-stockfish/S ... .cpp#L1586

As a side effect I have reformulated LeadPawnIdx[] definition to be used like this in the encoding code:

Code: Select all

idx = LeadPawnIdx[leadPawnsCnt - 1][squares[0]];

[mcostalba]

I noticed that you moved the step of sorting on ptwist[] / MapToEdges[] to before the horizontal flip. I think that will lead to problems if two non-leading pawns are in symmetric positions, because their positions now have to be swapped.

Actually in the original code there were 2 sorting of the same pieces: one before and one after flipping, I removed the last one. But you have a point here, I should test with symmetric leading pawns, say one in a2 and another in h7 and see what happens.

[syzygy]

I noticed that you moved the step of sorting on ptwist[] / MapToEdges[] to before the horizontal flip. I think that will lead to problems if two non-leading pawns are in symmetric positions, because their positions now have to be swapped.

Actually in the original code there were 2 sorting of the same pieces: one before and one after flipping, I removed the last one.

The first sort in pawn_file() is not a complete sort, but just finds the leading pawn. I also had to figure out the hard way that sorting all pawns of the leading color in that place does not work. And at that point you cannot yet flip horizontally either, because you still need to extract the other piece locations from the board representation.

So:
- first determine leading pawn to find the correct file;
- using the correct file, extract the remaining piece positions;
- now flip if necessary;
- sort non-leading pawns of leading color;
- use Pawnidx[] and the binomial sum formula to calculate an index for the pawns of the leading color.

But you have a point here, I should test with symmetric leading pawns, say one in a2 and another in h7 and see what happens.

The problem occurs with three pawns, one leading and two symmetric non-leading. E.g. pawns on a2, d2, e2. But there is no good reason to test this and hope for the best. You might not be able to find a case where it goes wrong, but it will go wrong. Any change in the indexing function will go wrong for some position, because you end up probing a different position than the one on the board. The binomial sum formula absolutely requires the squares to be ordered.

[syzygy]

Small inaccuracy:

Code: Select all

    // First we need to locate the right block that stores the value at index "idx".
    // Because each block n stores blockLength[n] + 1 values, the index i of the block
    // that contains the value at position idx is:
    //
    //                      for (i = 0; idx < sum; i++)
    //                          sum += blockLength[i] + 1;

Basically you need to add block lenghts to sum until you exceed idx. To do it completely right, the for loop would need to be this:

Code: Select all

    //                      for (i = -1, sum = 0; sum <= idx; i++)
    //                          sum += blockLength[i + 1] + 1;

Or you could at the same time calculate the offset into the right block:

Code: Select all

    block = 0;
    while (idx >= blockLength[block] + 1)
        idx -= blockLength[block++] + 1;

(Or idx > blockLength[block], which is the same but perhaps less clear.)

[mcostalba]

The problem occurs with three pawns, one leading and two symmetric non-leading. E.g. pawns on a2, d2, e2.

I now realize that this is a non issue : after flipping the pawns you still end up with the same board layout, one pawn in e2 and one in d2.

[syzygy]

The problem occurs with three pawns, one leading and two symmetric non-leading. E.g. pawns on a2, d2, e2.

I now realize that this is a non issue : after flipping the pawns you still end up with the same board layout, one pawn in e2 and one in d2.

Believe me, I know what I am talking about. This is an issue.

It is actually worse, and therefore more obvious, than I thought. The sort that you inserted (too early) sorts from highest ptwist[] to lowest. The sort that you removed sorts from lowest ptwist[] to highest.

And yes, this matters... I wrote this code, so I know.