Question to syzygy author

[syzygy]

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.

Sorry, here I went wrong.
The removed sort also sorts from highest ptwist[] to lowest. The binomial sum formula then goes from the last element to the first. You did not change this.

So the only problem is that flipping does break the sorting order in case of two symmetric non-leading pawns. Breaking the sorting order results in the binomial sum formula not calculating the right value. (There is only one right value; any other value corresponds to a different position or no position at all. There is absolutely no point in returning the TB value for another position than the one being probed, as should be obvious.)

Non-leading pawns on d2, e2 should give Bin(10, 1) + Bin(11, 2) = 65. Getting the order wrong gives Bin(11, 1) + Bin(10, 2) = 56. But 56 corresponds to Bin(1, 1) + Bin(11, 2), which means pawns on d7 and d2. If there are pawns on d2 and e2, you do not want to return the value for a position with pawns on d2 and d7.

[mcostalba]

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.

I have reversed the loop:

Code: Select all

        for &#40;int i = 1; i < leadPawnsCnt; ++i&#41;
            idx += Binomial&#91;i&#93;&#91;MapToEdges&#91;squares&#91;leadPawnsCnt - i&#93;&#93;&#93;;

It is squares[leadPawnsCnt - i], not squares


P.S: After every change I check test the code running a fixed 10 ply search on 600 endgame positions and I verify that the number of searched nodes (the 'bench' in SF forum jargon) does not change. This is how we usually verify that a given patch does not introduce a functional change in SF and it is a very sensible test, even a minimal change is detected. It could theoretically happen that we miss a very subtle functional change, but I would not expect to miss a broken encoding of the leading pawns!

[mcostalba]

Non-leading pawns on d2, e2 should give Bin(10, 1) + Bin(11, 2) = 65. Getting the order wrong gives Bin(11, 1) + Bin(10, 2) = 56.

But how can you get the wrong order if the squares are sorted?

How can you have Bin(11, xx) before Bin(10, xx)? How can you have 11 before 10?

[Rein Halbersma]

But he is too pessimistic about the decoding step (or did not realise how difficult solving diophantine equations is in general).

I am not sure why you would need to solve a polynomial. Without spatial symmetry considerations, unranking a valid index of K identical pieces on a board of N squares (with the index in the range [0... Binomial(N;K)-1] is efficiently done using a greedy algorithm

Code: Select all

void combination_unrank(unsigned N, unsigned K, size_t index, unsigned (&tuple)[K])
{       
        assert&#40;index < Binomial&#40;N, K&#41;); 
        unsigned sq_k = N;
        for &#40;unsigned k = K; k > 0; --k&#41; &#123;
                while &#40;Binomial&#40;sq_k, k&#41; > index&#41;
                        --sq_k;
                tuple&#91;k&#93; = sq_k;
                index -= Binomial&#40;sq_k, k&#41;;
        &#125;
&#125;

You can also use a bitboard instead of a tuple of squares to store the result. Or did I misunderstand it and do you have such code already?

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?

This is a long-standing problem in combinatorics. I don't think there is a generic answer yet. See this Q&A on MathOverflow http://mathoverflow.net/questions/94133 ... -instances

The author Geoffrey Irving is the guy who solved Pentago and co-solved Kalah.

[syzygy]

Non-leading pawns on d2, e2 should give Bin(10, 1) + Bin(11, 2) = 65. Getting the order wrong gives Bin(11, 1) + Bin(10, 2) = 56.

But how can you get the wrong order if the squares are sorted?

But you sort them before the flip and the flip does not fully preserve the order.

Suppose pawns are on d2, e2, h2.
The ptwist[] values are 11, 10 and 46.
The first sort gives 46, 11, 10, so h2, d2, e2. The leading pawn is h2.
Since we now know the leading file, we can extract the other pieces.
Next, we make sure that the leading pawn is in one of files a, b, c, d.
Since it is on h2, we horizontally flip the board. This gives a2,e2,d2.
The ptwist[] values are now 46,10,11. So this is not sorted anymore.

The binomial sum formula assumes the non-leading pawns are sorted from high to low. It will calculate Bin(11, 1) + Bin (10, 2) = 56. But this is wrong. It should calculate Bin(10, 1) + Bin(11, 2) = 65. That is only possible if the values are properly sorted.

[syzygy]

Or did I misunderstand it and do you have such code already?

Yes, it's easy to unpack an index calculated using the binomial sum formula. I was referring to this post by a user named guido.

A little more complicate and less fast is the inversion process, which corresponds to solve a diophantine equation in N integer variables.

That is not a very good comparison.

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?

This is a long-standing problem in combinatorics. I don't think there is a generic answer yet. See this Q&A on MathOverflow http://mathoverflow.net/questions/94133 ... -instances

The author Geoffrey Irving is the guy who solved Pentago and co-solved Kalah.

Thanks. I guess he also got tired of writing complicated indexing functions

[syzygy]

Suppose pawns are on d2, e2, h2.
The ptwist[] values are 11, 10 and 46.
The first sort gives 46, 11, 10, so h2, d2, e2. The leading pawn is h2.
Since we now know the leading file, we can extract the other pieces.
Next, we make sure that the leading pawn is in one of files a, b, c, d.
Since it is on h2, we horizontally flip the board. This gives a2,e2,d2.
The ptwist[] values are now 46,10,11. So this is not sorted anymore.

Oops, they are now 47, 10, 11. But the point remains: e2 and d2 have changed position.

[Rein Halbersma]

Thanks. I guess he also got tired of writing complicated indexing functions

My understanding of the difficulty of indexing modulo symmetries is the following. The indexing requires a canonical position. This corresponds to using the position's stabilizer subgroup to pick an orbit representative.

You can use Burnside's Lemma to count the number of positions which are symmetric under one of the board symmetry group's subgroups. However, you are over-counting if you simply divide each count by the order of the corresponding subgroup. To get the correct reduced symmetry count, one needs to do Mobius inversions on the lattice of subgroups.

This will lead to an sum of binomials with fractional rather than integral coefficients (the resulting numbers are integral of course), and this will break down the nice binomial indexing scheme. There's some more structure to discover if you use Polya's cycle-index polynomial generalization of Burnside's Lemma, but one pretty soon runs into a case-by-case drudgery.

[syzygy]

Without spatial symmetry considerations, unranking a valid index of K identical pieces on a board of N squares (with the index in the range [0... Binomial(N;K)-1] is efficiently done using a greedy algorithm

I slightly edited it (I find sq_k a bit confusing):

Code: Select all

void combination_unrank(unsigned N, unsigned K, size_t index, unsigned (&tuple)[K])
{
        unsigned sq = N;
        for (unsigned k = K; k > 0; --k) {
                while (Binomial(sq, k) > index)
                        --sq;
                tuple[k] = sq;
                index -= Binomial(sq, k);
        }
}

(So your tuple starts at 1.)
This is certainly the most obvious approach, but for some reason mine is different. And perhaps less efficient:

Code: Select all

void combination_unrank(unsigned N, unsigned K, size_t index, unsigned (&tuple)[K])
{
        for (unsigned k = K; k > 1; --k) {
                unsigned sq = k - 1;
                while &#40;Binomial&#40;sq, k - 1&#41; <= index&#41; &#123;
                        index -= Binomial&#40;sq, k - 1&#41;;
                        sq++;
                &#125;
                tuple&#91;k&#93; = sq;
        &#125;
        tuple&#91;1&#93; = index;
&#125;

(I do not guarantee the absence of off-by-one errors.)
Hmm, mine should indeed be less efficient. Yours is linear in N and mine seems to be quadratic on average. Skipping the last loop is of course also possible in your approach.

Very good, I can speed up the permutation part of my generator

I am guessing I originally picked my approach because Binomial(sq, k-1) is a polynomial in sq of one degree less than Binomial(sq, k). But with a simple table that makes no difference.

I vaguely remember realising that I could compare to Binomial(sq, k) and skip the subtractions, but as long as I keep counting from k-1 and up it would not really matter. But that approach loses where it runs over the same squares repeatedly, which is avoided by starting from the end of the board. The only disadvantage of your approach is that you need to know where to start (but that information will normally be available).

Hmm, I only really lose if there are 3 or more like pieces, so generation time is unlikely to improve by a large factor

[Michel]

Yours is linear in N and mine seems to be quadratic on average. Skipping the last loop is of course also possible in your approach.

It is possble to do the unmapping in O(k) since you know the inner while loop (in Rein's modified code) will exit when sq is of the order of fact(k)*root^k(index). So you can do a small loop around that value (I haven't bothered to look for exact bounds).

Of course for small k the overhead will probably be too large.