How many pawn structures are there in total?

[dangi12012]

When looking at the 8 white pawns only:
Pawns can exist in only 48/64 squares. So the upper limit is NCR(48,8) summed to NCR(48, 1) which is around 4E8.


From an older post:

I tried a Lichess download of 16 million games, unique pawn structures 132 million. Can't measure the hit-rate because I currently can't create a bigger pawn hash table than 32 million.

Looking at this image of course there cannot be a pawn on b2 - even when we have 2/8 pawns to spare. So the limit is above 132million and below 400Million.

Related CPW page: https://www.chessprogramming.org/Pawn_Hash_Table

The question:
Does anyone have the exact figure of possible pawn sturctures? - and optimally code to produce all patterns? With a solution a precomputed TT of the board might also be split into 2 or 4 to get a hashing function into a table that is small enough putting the size down to NCR(12, 8->0)

[shadyantra]

How is your c++ helpful to integrate with http calls. 2 billion instructions per second claim is too much..

[Uri Blass]

It is possible to get a good estimate by generating random pawn structures and see the percentage of legal pawn structures, but when the number is smaller than the sum of NCR(48,8) and smaller numbers it is possible to do better than it and get an exact number by simply count the number of pawn structure that you can get in 1 move,in 2 moves,in 3 moves until no more pawn structures.

move can be
1)White pawn capture something.
2)White pawn being captured.
3)White pawn move forward.

You can also try to find the number of pawn structures of both sides(pawn structure is a combination of white and black) in a similiar way when you add black move forward and black capture but
there is a memory problem and it is probably better to get an estimate in this case.

[hgm]

Structure of pawns of a single color tend to be utterly useless in engines; what matters most is how your pawns are positioned wrt enemy pawns. E.g. which pawns are passers.

I once wrote a routine for determining the number of Pawn structures reachable from a given one, along the lines Uri mentioned. (Basically perfting with only Pawns, but counting reachable positions rather than paths.) This is the first step for on-the-fly EGT generation of 8-10-men EGTs with several Pawns: each Pawn structure defines a P-slice, and the P-slices can be solved one by one in the order defined the irreversible moves between them. The number of pawn structures reachable from the initial position with 2x8 pawns is of course huge; I think I did not get any further than 5 against 5 (on a to e-file) on their initial rank.

[dangi12012]

Thanks for the comments so far! - Do you have the code around that still?
Thought so too that perft for pawns while removing duplicates seems to be the (only?) option. I was hoping that someone already did that once and can share the code.

I once wrote a routine for determining the number of Pawn structures reachable from a given one, along the lines Uri mentioned. (Basically perfting with only Pawns, but counting reachable positions rather than paths.)

Once that is done this would be super helpful - not for an engine but for just pointing to the 3 movelists for all 0-8 pawns at once. If memory becomes an issue this can be done twice for 2x24 relevant bits of the board - but there I need to know exactly how many patterns there are in total and more importantly enumerate them all.

Code: Select all

uint64_t forward = (pawns << 8) & Empty & CheckEvasion
//Hash forward into the index for the movlist:
int MoveIdx = (forward * seed) >h> (64 - bits)

[dangi12012]

For perft there are 5? moves:
- Forward
- Forward twice (first rank only)
- Take left
- Take right
- Get Taken (remove from board)

For a Perft:
Instant return of the current recursion if the current pattern was already discovered.
En Passant does not change the total number of patterns for (white only) since the pawn just moves diagonally.

End result: Less than 4E8 garuanteed
How many are there exactly? - lets find out!

[dangi12012]

Ok that was not too bad! Here is PerfT pawn:
(I verified that double move forward and EnPassant does not change the result so you dont see it in the code)

Code: Select all

#include <iostream>
#include <bit>
#include <unordered_set>

#define Bitloop(X) for(;X; X &= X - 1)

static constexpr uint64_t File1 = 0b1000000010000000100000001000000010000000100000001000000010000000ul;
static constexpr uint64_t File8 = 0b0000000100000001000000010000000100000001000000010000000100000001ul;
static constexpr uint64_t Rank7 = 0b0000000011111111000000000000000000000000000000000000000000000000ul;
static constexpr uint64_t Rank2 = 0b0000000000000000000000000000000000000000000000001111111100000000ul;

std::unordered_set<uint64_t> patterns;

bool doPrint = false;

static std::string _map(uint64_t value)
{
	static std::string str(64 + 8, 'o');
	for (uint64_t i = 0, c = 0; i < 64; i++)
	{
		uint64_t bitmask = (1ull << 63) >> i;

		if ((bitmask & value) != 0) str[c++] = 'X';
		else str[c++] = '.';

		if ((i + 1) % 8 == 0) str[c++] = '\n';
	}
	return str;
}

static void perftPawns(uint64_t currentPattern)
{
	if (!patterns.insert(currentPattern).second)
		return;

	if (doPrint)
	{
		if (patterns.size() % (1ull << 16) == 0)
		{
			std::cout << _map(currentPattern) << "\n";
			std::cout << patterns.size() << "\n";
		}
	}

	uint64_t bitloop = currentPattern & ~Rank7;
	Bitloop(bitloop)
	{
		uint64_t pawn = 1ull << std::countr_zero(bitloop);

		uint64_t forward = currentPattern ^ (pawn | (pawn << 8));
		perftPawns(forward);
		if (pawn & ~File8) 
		{
			uint64_t right = currentPattern ^ (pawn | (pawn << 7)); 
			if (right & ~currentPattern)
			{
				perftPawns(right);
			}
		}
		if (pawn & ~File1)
		{
			uint64_t left = currentPattern ^ (pawn | (pawn << 9));
			if (left & ~currentPattern)
			{
				perftPawns(left);
			}
		}
		uint64_t taken = currentPattern & ~pawn;
		perftPawns(taken);
	}
}


int main()
{
	doPrint = true;
	perftPawns(0b11111111ull << 8);
	std::cout << "Total Patterns: " << patterns.size();
}

Result calculating...

[dangi12012]

444957311

[phhnguyen]

336764843

[dangi12012]

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.