How many pawn structures are there in total?

[petero2]

There are 444957311 (443702487 with 15 captures max) unique positions with 8 downto 0 pawns.

I can confirm this. Using a dynamic programming algorithm, I get:

Code: Select all

cpt      new     total
 0   5764801   5764801
 1  23193660  28958461
 2  46496688  75455149
 3  63497560 138952709
 4  68237222 207189931
 5  62233372 269423303
 6  50764842 320188145
 7  38677966 358866111
 8  28272322 387138433
 9  20058072 407196505
10  13856056 421052561
11   9303552 430356113
12   6045934 436402047
13   3776874 440178921
14   2251696 442430617
15   1271870 443702487
16    674932 444377419
17    333450 444710869
18    151480 444862349
19     62524 444924873
20     22910 444947783
21      7248 444955031
22      1866 444956897
23       366 444957263
24        46 444957309
25         2 444957311
26         0 444957311
27         0 444957311
28         0 444957311
29         0 444957311
30         0 444957311
31         0 444957311

real    0m42.523s
user    0m42.081s
sys     0m0.440s

[dangi12012]

There are 444957311 (443702487 with 15 captures max) unique positions with 8 downto 0 pawns.

I can confirm this. Using a dynamic programming algorithm, I get:

Code: Select all

30         0 444957311
real    0m42.523s
user    0m42.081s
sys     0m0.440s

Nice find! - I am quite suprised by that performance. It is so fast its hard for me to believe its the actual runtime tbh
Can you share some code?
Also what does your algorithm say about the number of distinct elements in the second(and half) 16bit field in the 64 bit integer? (B pattern in my comments)



Should be around this: 39169



I consider this solved in any case since this function hashes all permutation of pawns attacks and moves into 3 nice 64k arrays. (even the very few unreachable onces)

Code: Select all

//Hashes a BB of 0..8 set bits into a number 0..(1 << 16)
//Is useful for the 3x 48bits of pawns
int Hash64k_16(uint16_t Max8Bits)
{
	return (Max8Bits * 11359312312521135389ull) >> 48;
}

And makes is possible to have branchless runtime free pawn promotion (since the movelist is preprepared and no conditions for rank are needed etc)

[petero2]

There are 444957311 (443702487 with 15 captures max) unique positions with 8 downto 0 pawns.

I can confirm this. Using a dynamic programming algorithm, I get:

Can you share some code?

See below. This was just a quick hack though. Some comments are probably needed to understand the algorithm.

For the dynamic programming algorithm, a mapping between index and pawn pattern is needed. For this mapping I assume bits 0, 1, ..., 47 in a 64-bit integer are used to represent possible pawn patterns.

Let n(a,b) = the number of ways that between 0 and b pawns can be placed on the squares (a+1), (a+2), ..., 47. The following holds:

Code: Select all

n(a,0) = 1
n(47,b) = 1
n(a,b) = n(a+1,b) + n(a+1,b-1)

The first equation holds because there is one way to place 0 pawns on any number of squares.

The second equation holds because there is one way to place between 0 and b pawns on zero squares, namely to place 0 pawns.

The third equation holds because to place 0 .. b pawns on squares a+1 .. 47, you can either leave square a+1 empty and place 0 .. b pawns on squares a+2 .. 47, or place a pawn on square a+1 and place 0 .. (b-1) pawns on squares a+2 .. 47.

Given these equations the int n[48][9] array can be computed.

Given the n function, the toIdx function can quickly convert a pawn pattern to an index.

The mapping from index to pawn pattern is handled by the toMask lookup table.

Captures of white pawns can be assumed to happen before any other moves. This means there are 2^8 = 256 possible initial pawn patterns.

Another observation is that all non-capture moves can be played before all moves that capture black pieces. After playing all non-capture moves, a pawn can therefore be on one of 6 possible rows. The number of patterns without any captures is therefore sum([comb(8,i)*6**i for i in range(9)]) = 5764801.

The v array keeps track of reachable patterns. v[idx] = c if the pattern having index "idx" can be reached using c captures but not using c-1 captures. Initially v[idx] = -1 for all idx, indicating the the result has not yet been computed.

v[idx] is then set to 0 for the 5764801 patterns reachable without capturing black pieces.

Finally a loop over number of captures is used to extend the number of reachable patterns by performing left/right capture moves for all patterns that were determined to be reachable in the previous iteration.

Code: Select all

// g++-10 --std=c++20 -O3 -march=native -Wall -o pawnstruct pawnstruct.cpp

#include <cstdint>
#include <bit>
#include <vector>
#include <iostream>
#include <iomanip>
#include <cassert>

using U64 = uint64_t;
using U32 = uint32_t;
using S8 = int8_t;

int main() {
    int n[48][9];
    for (int a = 0; a < 48; a++)
        n[a][0] = 1;
    for (int b = 1; b < 9; b++)
        n[47][b] = 1;
    for (int b = 1; b < 9; b++)
        for (int a = 46; a >= 0; a--)
            n[a][b] = n[a+1][b] + n[a+1][b-1];

    auto toIdx = [&n](U64 m) -> int {
        m >>= 8;
        int idx = 0;
        for (int i = 8; m != 0; i--, m &= m-1)
            idx += n[std::countr_zero(m)][i];
        return idx;
    };

    int N = n[0][8] + n[0][7];
    std::vector<S8> v(N, -1);
    std::vector<U64> toMask(N, 0);

    int sum = 0;
    int nNew = 0;
    for (U32 b = 0; b < 256; b++) {
        int c = 1;
        for (int i = std::popcount(b); i > 0; i--)
            c *= 6;
        for (int i = 0; i < c; i++) {
            int cTmp = i;
            U64 m = 0;
            for (int x = 0; x < 8; x++) {
                if (b & (1 << x)) {
                    int y = 1 + (cTmp % 6);
                    cTmp /= 6;
                    m |= 1ULL << (y * 8 + x);
                }
            }
            int idx = toIdx(m);
            v[idx] = 0;
            toMask[idx] = m;
            nNew++;
        }
    }
    sum += nNew;
    std::cout << std::setw(2) << 0 << " " << std::setw(9) << nNew << ' ' << std::setw(9) << sum << std::endl;

    U64 left  = 0x0000fefefefefefeULL;
    U64 right = 0x00007f7f7f7f7f7fULL;

    for (int c = 1; c < 32; c++) {
        nNew = 0;
        for (int idx0 = 0; idx0 < N; idx0++) {
            if (v[idx0] == c - 1) {
                U64 m0 = toMask[idx0];

                U64 tgt = ((m0 & left) << 7) & ~m0;
                while (tgt) {
                    int sq = std::countr_zero(tgt); tgt &= tgt - 1;
                    U64 m = (m0 & ~(1ULL << (sq - 7))) | (1ULL << sq);
                    int idx = toIdx(m);
                    if (v[idx] == -1) {
                        v[idx] = c;
                        toMask[idx] = m;
                        nNew++;
                    }
                }

                tgt = ((m0 & right) << 9) & ~m0;
                while (tgt) {
                    int sq = std::countr_zero(tgt); tgt &= tgt - 1;
                    U64 m = (m0 & ~(1ULL << (sq - 9))) | (1ULL << sq);
                    int idx = toIdx(m);
                    if (v[idx] == -1) {
                        v[idx] = c;
                        toMask[idx] = m;
                        nNew++;
                    }
                }
            }
        }
        sum += nNew;
        std::cout << std::setw(2) << c << " " << std::setw(9) << nNew << ' ' << std::setw(9) << sum << std::endl;
    }
}

[Uri Blass]

The question is if you can get all pawn structures of white pawns by a legal way.

I found one pawn structure that you can get in a legal way but need 14 captures in black squares.
If you need 15 captures in black squares then it is impossible to get it because you have no way to capture both bishops.

[fen]k7/P1P5/8/P7/8/P7/P1P1P1P1/K7 w - - 1 1 [/fen]

The fact that I did not prove illegal pawn structures does not prove that there are not illegal pawn structure that you counted.

[Harald]

The question is if you can get all pawn structures of white pawns by a legal way.

I found one pawn structure that you can get in a legal way but need 14 captures in black squares.
If you need 15 captures in black squares then it is impossible to get it because you have no way to capture both bishops.

[fen]k7/P1P5/8/P7/8/P7/P1P1P1P1/K7 w - - 1 1 [/fen]

The fact that I did not prove illegal pawn structures does not prove that there are not illegal pawn structure that you counted.

I did not follow this thread and therefore may be wrong in my assumptions.
A pawn can capture a white/black square bishop then go up one rank and capture a black/white square bishop.
Also White can capture two black squared bishops from Black if Black promoted a pawn to a bishop on a black square.
Black would rather promote to a queen but that also gives you another possible queen capture.
If there were no other restrictions the White pawns could capture all 7 Black pieces and all 8 (promoted) Black pawns.
Sorry, I could not resist.

[hgm]

Try to create the given position from an initially filled 2nd rank, and you will see that it can only be done by making nothing but diagonal moves. The pawn at a3 must come from b2. Then a5 must come from d2, (as a2, b2 and c2 are already committed), and can only do that via c3 and b4. Etc.

Unfortunately the program I made for this is on my old laptop, which is almost impossible to run (dead battery and broken power plug). But I recal that it did account for the limitation to the number of captures. That was essential, since the goal was to calculate the number of Pawn structures reachable from a position with 2 or 3 other pieces (in addition to Kings and Pawns), so the number of captures was very limited indeed.

I think I did it as follows:

The game state was not only given by stm and Pawn constellation, but also by the remaining number of other pieces on each side. The latter did not contribute to the hash key, but was stored in the hash entry. Each diagonal Pawn move to an empty square would decrease the opponent piece count. When a position in the search tree had a hash hit, the search was aborted only when both piece counts were equal or less than than the stored ones. Otherwise the search was continued after updating the hash table to the larger piece counts. Positions were only counted when they did not give a hash hit. (Of course there was never any overwriting of positions; it has to be a lossless hash table.)

In fact I think I counted all combinations of piece counts separately. This was of interest for estimating how much work it would be to generate the EGT for the root position; Pawn-slices with one less piece are 64 times as easy. I am not sure how I handled the case where one count was higher and the other lower. E.g. a start position with white on e2 and black on e7 can convert to white e5 and black e4 by two white captures or two black captures. I am not sure this can happen with fewer than 4 pieces, however, and that was outside my scope. (Because then even a P-slice would be a 6-men EGT.)

[dangi12012]

Code: Select all

n(a,0) = 1
n(47,b) = 1
n(a,b) = n(a+1,b) + n(a+1,b-1)

The first equation holds because there is one way to place 0 pawns on any number of squares.
The second equation holds because there is one way to place between 0 and b pawns on zero squares, namely to place 0 pawns.
The third equation holds because to place 0 .. b pawns on squares a+1 .. 47, you can either leave square a+1 empty and place 0 .. b pawns on squares a+2 .. 47, or place a pawn on square a+1 and place 0 .. (b-1) pawns on squares a+2 .. 47.

Given these equations the int n[48][9] array can be computed.

A little bit more optimized (but not as concise):

Code: Select all

#include <cstdint>
#include <bit>
#include <vector>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <array>
#include <algorithm>

using U64 = uint64_t;
using U32 = uint32_t;
using S8 = int8_t;

static constexpr uint64_t PopBit(uint64_t & val)
{
    uint64_t lsb = val & -val;
    val ^= lsb;
    return lsb;
}

static constexpr auto n = [] {
    std::array<std::array<int, 9>, 48> n{};
    for (int a = 0; a < 48; a++)
        n[a][0] = 1;
    for (int b = 1; b < 9; b++)
        n[47][b] = 1;
    for (int b = 1; b < 9; b++)
        for (int a = 46; a >= 0; a--)
            n[a][b] = n[a + 1][b] + n[a + 1][b - 1];
    return n;
}();

static constexpr int toIdx(U64 m)
{
    int idx = 0;
    idx += n[std::countr_zero(m)][8]; if ((m &= m - 1) == 0) return idx;
    idx += n[std::countr_zero(m)][7]; if ((m &= m - 1) == 0) return idx;
    idx += n[std::countr_zero(m)][6]; if ((m &= m - 1) == 0) return idx;
    idx += n[std::countr_zero(m)][5]; if ((m &= m - 1) == 0) return idx;
    idx += n[std::countr_zero(m)][4]; if ((m &= m - 1) == 0) return idx;
    idx += n[std::countr_zero(m)][3]; if ((m &= m - 1) == 0) return idx;
    idx += n[std::countr_zero(m)][2]; if ((m &= m - 1) == 0) return idx;
    idx += n[std::countr_zero(m)][1]; if ((m &= m - 1) == 0) return idx;
    return idx + n[std::countr_zero(m)][0];
}

int main() {
    constexpr int N = n[0][8] + n[0][7];
    std::vector<S8> v(N, -1);
    std::vector<U64> toMask(N, 0);

    for (U32 b = 0; b < 256; b++) {
        int c = 1;
        for (int i = std::popcount(b); i > 0; i--)
            c *= 6;
        for (int i = 0; i < c; i++) {
            int cTmp = i;
            U64 m = 0;
            for (int x = 0; x < 8; x++) {
                if (b & (1 << x)) {
                    int y = 1 + (cTmp % 6);
                    cTmp /= 6;
                    m |= 1ULL << (y * 8 + x);
                }
            }
            int idx = toIdx(m);
            v[idx] = 0;
            toMask[idx] = m;
        }
    }
    int current = std::count_if(v.begin(), v.end(), [](int i) {return i != -1; });
    std::cout << std::setw(2) << 0 << " " << std::setw(9) << 5764801 << ' ' << std::setw(9) << 5764801 << std::endl;

    constexpr U64 left  = 0x0000fefefefefefeULL;
    constexpr U64 right = 0x00007f7f7f7f7f7fULL;
    for (int c = 1; c < 32; c++) {
        for (int idx0 = 0; idx0 < N; idx0++) {
            if (v[idx0] != c - 1) continue;
            const U64 m0 = toMask[idx0];

            U64 tgt = ((m0 & left) << 7) & ~m0;
            while(tgt)
            {
                const uint64_t pawn = PopBit(tgt);
                U64 m = m0 ^ ((pawn >> 7) | pawn);
                int idx = toIdx(m);
                if (v[idx] == -1) {
                    v[idx] = c;
                    toMask[idx] = m;
                }
            }
            tgt = ((m0 & right) << 9) & ~m0;
            while(tgt){
                const uint64_t pawn = PopBit(tgt);
                U64 m = m0 ^ ((pawn >> 9) | pawn);
                int idx = toIdx(m);
                if (v[idx] == -1) {
                    v[idx] = c;
                    toMask[idx] = m;
                }
            }
        }
        int end = std::count_if(v.begin(), v.end(), [](int i) {return i != -1; });
        std::cout << std::setw(2) << c << " " << std::setw(9) << (end - current) << ' ' << std::setw(9) << end << std::endl;
        current = end;
    }
}

But I cannot wrap my head around the math here. This is not using the combinatorics number system (base n! per digit or maybe it is?) but still it looks very similar. The toIdx function clearly transforms the 8 bit binary representation into antother base number but what is that number system called? (for googling this stuff)

This would be super useful for indexing into the king patterns from and index and vice versa.
Kings and all 4 bits for Castling rights can be stored in 11 bits - as opposed to the usual 12+4.
Enumerating all legal king positions (they cannot touch) - and for the legal castling square you add two extra states gives a number which is below 2048. So that would help here.

The code you posted can store one pawn bitboard in log2(465174935) = 29bits. And pack/unpack with the cost of toIdx.

[petero2]

Code: Select all

n(a,0) = 1
n(47,b) = 1
n(a,b) = n(a+1,b) + n(a+1,b-1)

...
Given these equations the int n[48][9] array can be computed.

The toIdx function clearly transforms the 8 bit binary representation into another base number but what is that number system called? (for googling this stuff)

I just made this up to solve this particular problem, so I don't know if it has a name. It would not surprise me though if someone else has already derived the same formula and given it a name.

First consider a slightly different function n0(a,b) = number of ways to place between 0 and "b" pawns on "a" squares. Like before, we have:

Code: Select all

n0(a,0) = 1                        (one way to place 0 pawns)
n0(0,b) = 1                        (one way to place pawns on 0 squares)
n0(a,b) = n0(a-1,b) + n0(a-1,b-1)  (either you leave the first square empty or you put a pawn on it)

This function has the following values for a<=4, b<=2:

Code: Select all

b\a | 0   1   2   3   4
----+------------------
0   | 1   1   1   1   1
1   | 1   2   3   4   5
2   | 1   2   4   7  11

Now suppose you want to compute an index for the bit patterns when placing between 0 and 2 pawns on 4 squares. From the table we can see that there are 11 ways to do that. We can systematically list those patterns by counting in binary but skipping all patterns having more than two "1" bits, like this:

Code: Select all

     s0 s1 s2 s3
 0 :  0  0  0  0
 1 :  0  0  0  1
 2 :  0  0  1  0
 3 :  0  0  1  1
 4 :  0  1  0  0
 5 :  0  1  0  1
 6 :  0  1  1  0
 7 :  1  0  0  0
 8 :  1  0  0  1
 9 :  1  0  1  0
10 :  1  1  0  0

Lets first consider bit pattern 1000. We can see that all patterns before this pattern have s0=0, so the number of such patterns are the number of ways to place 0-2 pawns on 3 squares (s1, s2, s3), which by definition is n0(3, 2) = 7, so the index of pattern 1000 is 7. Similarly consider pattern 0100, which has index n0(2, 2). In general the pattern with a one bit on only square s_i has index n0(3-i, 2).

Next, consider the pattern 1100. We know that this pattern comes after pattern 1000 (which has index n0(3,2)), and we can see that all patterns from 1000 to the pattern before 1100 are characterized by having s0=1, s1=0. The number of such patterns are n0(2,1), because there are two remaining squares (s2,s3) and one remaining 1 bit. Therefore the index of pattern 1100 is n0(3,2) + n0(2,1).

The same reasoning can be used for a=48, b=8 to derive the formula:

Code: Select all

int idx = 0;
for (int i = 8; m != 0; i--)
    idx += n0[47-std::countr_zero(m)][i];
return idx;

To get rid of the "47-" in that formula I defined n(a,b)=n0(47-a,b), which leads to the formula in my program.

The code you posted can store one pawn bitboard in log2(465174935) = 29bits. And pack/unpack with the cost of toIdx.

My current code uses a big lookup table for the "unpack" case, which I think is the fastest way to do that, but the size of that table is around 4GB, which might be a problem, depending on the application.