How many pawn structures are there in total?

[Pio]

4x faster version. Mostly thanks to https://martin.ankerl.com/2019/04/01/ha ... -overview/

The default std::unorderes set is very slow.

New version:
https://1drv.ms/u/s!AoDIyNlDG2QTg8tMe1B ... Q?e=08Aw0h

Results of all possible pawn structures:
Total Patterns: 444957311
Total Upper 32 Bit Patterns: 1271608
Total Lower 32 Bit Patterns: 881518

Gut feeling:
Two completely different implementations - same result.
Is it possible that the upper board will have more patterns?
Absolutely! Since pawns need to move diagonally a bit to start forming a line which cannot happen on the first few squares.

I am now looking for independent verification.

Have you taken into account that each side can do a maximum of 15 captures?

[dangi12012]

Update:
Now with 4x 16 bits over the board - and taking maximum 15 captures into account (yes it makes a very small difference).
There are two positions not reachable in the upper 16 bits - permutated over all positions it makes a small adjustment:

//Treating the board as 1x uint64
Total Patterns: 443702487

//Treating the board as 2x uint32
Total Upper 32 Bit Patterns: 1269754
Total Lower 32 Bit Patterns: 881518

//Treating the board as 3x uint16 for the pawn squares
Total A 16 Bit Patterns: 39201
Total B 16 Bit Patterns: 39169
Total C 16 Bit Patterns: 24875

//Treating the board as 4x uint16
Total a 16 Bit Patterns: 256
Total b 16 Bit Patterns: 39201
Total c 16 Bit Patterns: 37809
Total d 16 Bit Patterns: 256


What is the meaning of this?
There are 444957311 (443702487 with 15 captures max) unique positions with 8 downto 0 pawns. So the answer to my original question is 444957311.
When generating the possible pawn moves normally a Bitpop loop is used.
Hashing 16bits into 3x 64k slots allows one to branchlessy resolve all up to 8 bits in parallel without any loops.
Resolve means getting a single set bit per pawn in from a uint64_t with 8 bit set.

[dangi12012]

Both sides need to be hashed.
The NCR SUM = 39203

Code: Select all

0	1
1	16
2	120
3	560
4	1820
5	4368
6	8008
7	11440
8	12870
SUM:	39203

So all possible permutations of 8 to 0 can be reached by pawns starting on the opposite side.
Taking this into account means that its easiest to just hash all 39203 values into 6 buffers (3 per side) and use that instead of loops.

[dangi12012]

This function can hash all 39203 pawn configuration in each of the three 16 bit fields into 64k slots:

Code: Select all

int index = (pawns * 11359312312521135389ull) >> (64-16);

Meaning that it can resolve 8 square offsets at once and is equivalent to this loop:

Code: Select all

int* squares;
for(;pawns; pawns &= pawns-1)
{
   *squares++ = std::countr_zero(pawns);
}

But many times faster - and it could directly index into a movelist when the hashed value is not the 8 pawns bitboard - but the 8 target squares per direction.
Nice findings for the day.

[phhnguyen]

Time to verify the result.

We have two programs here. One by @dangi12012, looks very elegant and compact. The other is mine, much longer and in the more traditional way. It will be good if we can make both produce the same result, then all are verified.


About my code:
- Using a simple mailbox for board representation. It uses a vector pawnVec to track the locations of Pawns on the board
- It considers the horizontal symmetry
- Each board has a unique key (64-bit), it is not a hash key but actually a simple bitmap of all Pawns. From a given key we can extract the board
- When starting up, it creates all 240 initial boards by placing the first Pawn in a2, then b2 - d2. For each first Pawn, add the second Pawn next to it, and so on
- For each initial board, I use a sort of Perft function (named “calculate” in my code) to compute all possible moves/positions, considering the limit of 15 captures. It used a set to store visited keys (pawnSet). The result is the size of that set.

The first initial board:

Code: Select all

 . . . . . . . . 8
 . . . . . . . . 7
 . . . . . . . . 6
 . . . . . . . . 5
 . . . . . . . . 4
 . . . . . . . . 3
 P . . . . . . . 2
 . . . . . . . . 1
 a b c d e f g h

The 2nd board

Code: Select all

 . . . . . . . . 8
 . . . . . . . . 7
 . . . . . . . . 6
 . . . . . . . . 5
 . . . . . . . . 4
 . . . . . . . . 3
 P P . . . . . . 2
 . . . . . . . . 1
 a b c d e f g h

The board with full 8 Pawns

Code: Select all

 . . . . . . . . 8
 . . . . . . . . 7
 . . . . . . . . 6
 . . . . . . . . 5
 . . . . . . . . 4
 . . . . . . . . 3
 P P P P P P P P 2
 . . . . . . . . 1
 a b c d e f g h

The last one 240th. The first Pawn stopped at d2 for the horizontal symmetry:

Code: Select all

 . . . . . . . . 8
 . . . . . . . . 7
 . . . . . . . . 6
 . . . . . . . . 5
 . . . . . . . . 4
 . . . . . . . . 3
 . . . P . . . P 2
 . . . . . . . . 1
 a b c d e f g h

My code:

Code: Select all

//
//  By Nguyen Pham
//

#include <iostream>
#include <vector>
#include <unordered_set>


std::unordered_set<uint64_t> pawnSet;
std::chrono::steady_clock::time_point startTime;

class Move
{
public:
    int idx, from, dest;
    bool cap;
    
    Move() {}
    Move(int idx, int from, int dest, bool cap) : idx(idx), from(from), dest(dest), cap(cap) {}
};

const char PAWN = 'P';
const char EMPTY = '.';

std::chrono::steady_clock::time_point getNow()
{
    return std::chrono::steady_clock::now();
}

std::string elapsedString()
{
    int64_t elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(getNow() - startTime).count() + 1;
    
    std::string s = std::to_string(elapsed / 1000) + "s";
    return s;
}

class Board
{
public:
    char pieces[64];
    uint64_t key = 0, cnt = 0;
    int capCnt = 0;
    
    std::vector<int> pawnVec;

public:
    Board() { reset(); }
    
    void reset() {
        for(int i = 0; i < 64; ++i) pieces[i] = EMPTY;
    }
    
    void make(const Move& move) {
        assert(pieces[move.from] == PAWN && pieces[move.dest] == EMPTY && move.idx < pawnVec.size());
        pieces[move.from] = EMPTY;
        pieces[move.dest] = PAWN;
        pawnVec[move.idx] = move.dest;
        
        if (move.cap) capCnt++;
        
        assert(key & (1ULL << move.from));
        key |= (1ULL << move.dest);
        key &= ~(1ULL << move.from);
        
//        assert(board2String() == key2String(key));
    }

    void takeback(const Move& move) {
        assert(pieces[move.from] == EMPTY && pieces[move.dest] == PAWN && move.idx < pawnVec.size());
        pieces[move.dest] = EMPTY;
        pieces[move.from] = PAWN;
        pawnVec[move.idx] = move.from;

        if (move.cap) capCnt--;

        key |= (1ULL << move.from);
        key &= ~(1ULL << move.dest);
    }
    
    void printOut() const {
        std::cout << board2String() << std::endl;
    }
    
    std::string board2String() const {
        std::string s;
        char buf[3];
        buf[1] = 0;
        for(int i = 0; i < 64; i++) {
            buf[0] = pieces[i];
            s += " " + std::string(buf);
            if (i && i % 8 == 7) {
                s += " " + std::to_string(8 - i / 8) + "\n";
            }
        }
        
        s += " a b c d e f g h\n";
        return s;
    }
    
    std::string key2String(uint64_t key) const {
        std::string s;
        for(int i = 0; i < 64; i++) {
            s += (key & (1ULL << i)) ? " P" : " .";
            if (i && i % 8 == 7) {
                s += " " + std::to_string(8 - i / 8) + "\n";
            }
        }
        
        s += " a b c d e f g h\n";
        return s;
    }
    
    void gen(int idx, std::vector<Move>& vec) const {
        auto from = pawnVec.at(idx); assert(pieces[from] == PAWN);
        if (from >= 16) {
            auto dest = from - 8;
            if (pieces[dest] == EMPTY) {
                vec.push_back(Move(idx, from, dest, false));
            }
            
            // We can't capture more than 15
            if (capCnt >= 15) return;

            auto col = from % 8;
            if (col > 1) {
                auto dest = from - 9;
                if (pieces[dest] == EMPTY) {
                    vec.push_back(Move(idx, from, dest, true));
                }
            }
            if (col < 7) {
                auto dest = from - 7;
                if (pieces[dest] == EMPTY) {
                    vec.push_back(Move(idx, from, dest, true));
                }
            }
        }
    }
    
    std::vector<Move> gen() const
    {
        std::vector<Move> vec;
        for(int i = 0; i < pawnVec.size(); i++) {
            gen(i, vec);
        }
        return vec;
    }
    
    void calculate() {
        if (pawnSet.find(key) != pawnSet.end()) {
            return;
        }
        pawnSet.insert(key);

        cnt++;
        if ((cnt & 0x1fffff) == 0) {
            std::cout << "cnt: " << cnt << ", theSet sz: " << pawnSet.size() << std::endl;
        }
        
        std::vector<Move> vec = gen();

        for(auto && m : vec) {
            assert(!m.cap || capCnt < 15);
            make(m);
            calculate();
            takeback(m);
        }
    }

    void setPawn(int idx) {
        auto k = 48 + idx;
        pieces[k] = PAWN;
        pawnVec.push_back(k);
        key |= 1ULL << k;
    }

    void removeLastPawn() {
        if (pawnVec.empty()) return;
        auto k = pawnVec.back();
        pawnVec.pop_back();
        pieces[k] = EMPTY;
        key &= ~(1ULL << k);
    }
};


std::vector<Board> boards;

void startBoard(int i, Board& board)
{
    board.setPawn(i);
    boards.push_back(board);
    
    for(int j = i + 1; j < 8; j++) {
        startBoard(j, board);
    }
    board.removeLastPawn();
}


int main(int argc, const char * argv[]) {
    std::cout << "Count all pawn structures!\n" << std::endl;
    
    startTime = getNow();

    Board board;
    for(int i = 0; i < 4; i++) {
        startBoard(i, board);
    }
    
    std::cout << "Starting #boards: " << boards.size() << std::endl;
    
    for(auto && board : boards) {
        board.printOut();
        board.calculate();
    }
    
    std::cout << "All done. pawnSet sz: " << pawnSet.size() << ", elapsed: " << elapsedString() << std::endl;
    return 0;
}

[dangi12012]

- Each board has a unique key (64-bit), it is not a hash key but actually a simple bitmap of all Pawns. From a given key we can extract the board
- When starting up, it creates all 240 initial boards by placing the first Pawn in a2, then b2 - d2. For each first Pawn, add the second Pawn next to it, and so on
- For each initial board, I use a sort of Perft function (named “calculate” in my code) to compute all possible moves/positions,

What was the result for you?

Also I really doubt the 240 number it should be 256 imo. The starting position should be one: namely all 8 pawns on the first rank.
A pawn can be removed recursively or move etc. making permutations on the first rank 256 by the perft automatically. With your plan of 240 position I dont see the possibility of a pawn dying later on.

Also now that I know that every permutation of 8 in 16 can be reached by pawns in the upper third of the board - and I can hash these into 64k any other result would not change the end result anyways.

The number posted above can resolve 8 positions in 3mults + 3 branchless shifts + 3lookups into 64k.
A loop needs 8 conditions, 8 bsr, 8bsf instructions and is conditionally jumping. But with 0 pawns it needs only 1 conditional jump.

Which is faster depends on the platform.

But thanks for the interest in any case

[phhnguyen]

What was the result for you?

I have posted already on the previous page:

336764843

Also I really doubt the 240 number it should be 256 imo. The starting position should be one: namely all 8 pawns on the first rank.
A pawn can be removed recursively or move etc. making permutations on the first rank 256 by the perft automatically. With your plan of 240 position I dont see the possibility of a pawn dying later on.

Your method starts with 8 Pawns and then captures them one by one to 1. My method starts with 1, 2,... 8 Pawns, then move them around without being captured. You don't need to create many starting positions but your a-like-perft function should be a bit more complicated than mine (because of capturing).

Two methods should have the same result since we count only Pawn-patterns. What wrong? Or are both of us wrong?

Also now that I know that every permutation of 8 in 16 can be reached by pawns in the upper third of the board - and I can hash these into 64k any other result would not change the end result anyways.

The number posted above can resolve 8 positions in 3mults + 3 branchless shifts + 3lookups into 64k.
A loop needs 8 conditions, 8 bsr, 8bsf instructions and is conditionally jumping. But with 0 pawns it needs only 1 conditional jump.

Which is faster depends on the platform.

But thanks for the interest in any case

My code can complete within 30 minutes on my 5-year-old computer. It is fine for a program for only one use.

Feel free to use/change my code or jump to help us (verify, find out why our results are different).

[Pio]

What was the result for you?

I have posted already on the previous page:

336764843

Also I really doubt the 240 number it should be 256 imo. The starting position should be one: namely all 8 pawns on the first rank.
A pawn can be removed recursively or move etc. making permutations on the first rank 256 by the perft automatically. With your plan of 240 position I dont see the possibility of a pawn dying later on.

Your method starts with 8 Pawns and then captures them one by one to 1. My method starts with 1, 2,... 8 Pawns, then move them around without being captured. You don't need to create many starting positions but your a-like-perft function should be a bit more complicated than mine (because of capturing).

Two methods should have the same result since we count only Pawn-patterns. What wrong? Or are both of us wrong?

Also now that I know that every permutation of 8 in 16 can be reached by pawns in the upper third of the board - and I can hash these into 64k any other result would not change the end result anyways.

The number posted above can resolve 8 positions in 3mults + 3 branchless shifts + 3lookups into 64k.
A loop needs 8 conditions, 8 bsr, 8bsf instructions and is conditionally jumping. But with 0 pawns it needs only 1 conditional jump.

Which is faster depends on the platform.

But thanks for the interest in any case

My code can complete within 30 minutes on my 5-year-old computer. It is fine for a program for only one use.

Feel free to use/change my code or jump to help us (verify, find out why our results are different).

377349043

[Pio]

What was the result for you?

I have posted already on the previous page:

336764843

Also I really doubt the 240 number it should be 256 imo. The starting position should be one: namely all 8 pawns on the first rank.
A pawn can be removed recursively or move etc. making permutations on the first rank 256 by the perft automatically. With your plan of 240 position I dont see the possibility of a pawn dying later on.

Your method starts with 8 Pawns and then captures them one by one to 1. My method starts with 1, 2,... 8 Pawns, then move them around without being captured. You don't need to create many starting positions but your a-like-perft function should be a bit more complicated than mine (because of capturing).

Two methods should have the same result since we count only Pawn-patterns. What wrong? Or are both of us wrong?

Also now that I know that every permutation of 8 in 16 can be reached by pawns in the upper third of the board - and I can hash these into 64k any other result would not change the end result anyways.

The number posted above can resolve 8 positions in 3mults + 3 branchless shifts + 3lookups into 64k.
A loop needs 8 conditions, 8 bsr, 8bsf instructions and is conditionally jumping. But with 0 pawns it needs only 1 conditional jump.

Which is faster depends on the platform.

But thanks for the interest in any case

My code can complete within 30 minutes on my 5-year-old computer. It is fine for a program for only one use.

Feel free to use/change my code or jump to help us (verify, find out why our results are different).

377349043

You can calculate it as 1 for empty board + 48 for 1 pawn + 48*47/2 for two pawns + 48*47*46/(3!) for three pawns + …

[hgm]

That is an upper limit. Not every pawn structure in the 48-square area is reachable. E.g. with 3 Pawns you cannot have a2+a3+b2 and h2+h3+g2.