combinatorics - Possible pawn combinations

This may seem simple, but I have a problem calculating it. It may be because it's Monday morning.
How may possible valid combinations of one color pawn (white or black, your choice) positions are there on a regular chess board?
To explain it better....
Start a normal chess game.

1. So we have the first pawn combination: All white on row 2 and/or all black on row 7.


2. (Almost) Every pawn (of the color you choose) move means a new combination .


3. Every other piece move does not increase the number of pawn combinations.


4. Pawns on the last row (8 for white, 1 for black are not pawns anymore, they are considered as promoted)


5. (exception for 2.) In the example below, capturing the white pawn on c4 results in the same combination, not 2 different ones. Example is provided for black pawns, but it applies if you choose white also.

I will settle for partial responses, strategies or anything.

Answer

I'm going to be working from the assumption that you still want pawns from both sides for this answer. If you only care about 1 side, the numbers get much more manageable (but slightly less interesting).

First let's establish a massive upper bound and see if we can work it down from there:

Each of the 48 positions is either black, white, or unoccupied.

3^48 = 7.97666e+22

Working down from that, you can assume that at most 16 spaces from the 48 can be occupied.

The sum of all n from 0 to 16 for 48 choose n gives us 4.1243046e+12 possible choices for pawn locations.

To account for pawn color, you multiply each term from the above equation by 2^n before adding it together. After accounting for piece color, that gives us 1.9341983e+17 states.

We can possibly reduce this down a bit further as the above number allows for anywhere from 0 through 16 pawns of each color, but we can limit it to 8 of each color.

To do that, we can choose 0 through 8 pieces for one color and then for each have 48 minus that number choose the second number for all combinations of 0 to 8 pieces on each side.

This gives us 4.90955e+13 possibilities. This number does still encompass a few impossible arrangements, but it should be a pretty close upper bound.

Now let's work up from what the pawns can do.

To establish a strong lower bound for this number, we assume that all pawns may only move forward and do not capture other pieces. The white pawn can move from 0 to 5 spaces and then the black pawn can move from 0 to 5-i spaces. This is the set of possible configuration states for the column as a whole. The configuration of the whole board can then be expressed as:

or 2.56289e+9. This is a strict lower bound of the answer.

If we assume that any pawns can be safely removed from the board by a combination of player cooperation and a knight being able to reach any square on the board, we can add in the empty state for no pawns, six states for the white pawn and six states for the black pawn giving:

or 3.77801e+11. Again, assuming any pawn can be surgically extracted by a knight, we have an even better strict lower bound

So far we have 3.77801e+11 < states < 4.90955e+13

It might be possible to extend this line of thinking to include cases with 2 pawns of one color and 1 of another where a pawn joined his buddy's file. And 3 and so on. In order to still keep this as a lower bound, we just have to prove that all the positions covered by the equation are reachable but don't necessarily cover all the possible behaviors of the pawns. This is where things start to get sticky. The ability to move sideways on a board is a limited resource, so if we have a state that involves more than 7 file displacements, it's unreachable without causing side effects to the opposing pawns. More on that in the next section.

Now on to capturing

Pawns can only change their file by capturing and no pawn may capture more than 5 times (since it puts you forward a space). Each type of pawn also opens up different amounts of possible positions for itself with some number of captures. A single capture let's a rook's pawn open up all but 1 of the positions in the adjacent knight's file, adding 5 potential position whereas a knight's pawn with a single capture gains access to the rook's file or the bishop's file, adding 10 possible positions. For 2, 3, 4, and 5 captures, each piece gains a different number of possible positions.

I'll be naming the pawns for their file name.

Positions with 1 capture:

• Rook 12


• Knight 17


• Bishop 17


• King 17

Positions with 2 captures:

• Rook 16


• Knight 21


• Bishop 25



• King 25

Positions with 3 captures

• Rook 19


• Knight 24


• Bishop 28


• King 31

Positions with 4 captures

• Rook 21


• Knight 26


• Bishop 30


• King 33

Positions with 5 captures

• Rook 22


• Knight 27



• Bishop 31


• King 33

So let's make another upper bound, this time based on per-piece positions and assuming as many captures as we want:

Since we have 4 of each type of pawn on the board, we get:

33^4 * 31^4 * 27^4 * 22^4 = 1.3634786e+23 possible configurations.

This bound is way higher than the previous one as this method produces a lot of "duplicate" board states such as a knight and rook pawn trading files as well as not handling co-occupied spaces between our same color pieces or opposite ones, so this is a looser upper bound.

There are 7 "free" captures per side on the board that don't affect other pawns. These include capturing Rooks, Knights, Bishops, and the Queen. Since they are irrelevant to our pawn configurations, they're "free" ways to capture.

When you add in opposing pawns, there are 15 captures per side in total, so the total pawn file displacement must be less than or equal to 15. Each displacement beyond the 7th, however, produces side effects. Since we removed an opposing pawn to shift over, this restricts one of the other side's pawns to one option (non-existence).

Working from just the 7 "free" captures per side, let's assume each pawn captures strategically to add the most possible moves to its move pool.

The highest utility each piece gets from a move is +10 for knight/bishop/king pawns on the first capture, so lets' use 6 of them for that. The next hightest is +8 on a bishop/king pawn on its second capture, so let's use the final one on one of them.

4x 0 cap Rook(7 moves) + 10x 1 cap Knight/Bishop/King (17 moves) + 2x 2 cap Bishop/King (25 moves)

7^4 * 17^10 * 25^2 = 3.0252508e+18

So our 3.0252508e+18 number is the maximum number of non-destructive board states that can be made in a single game before removing co-occupying pieces. We still aren't accounting for co-occupancy, so this can't be a strict lower bound. We also aren't accounting for all the possible destructive captures either, so this isn't an upper bound either.

If we want to refine our non-destructive capture number to include all possible games, we'll need to distribute those 7 "free" captures to each of 2 rook pawns, 2 knight pawns, 2 bishop pawns, and 2 king pawns. For each side, we have to use a partition operator on 7 and square the result.

There are 15 ways to partition 7 into addition, but some of those (7+0 and 6+1) involve more than 5 captures for a single pawn, so they can be discarded, leaving 13. Each unique partition generates its own choose function that gets added on to deal with the distribution of 0s, 1s, 2s, etc across the 8 possible slots.

Theoretically, each of those distributions would create a set of states for a single game, each depending on how the captures were distributed. The number will be massive but there should be a lot of collision, which means we can theoretically drop a fair number of them.

Captures beyond the 7 "free" ones should always yield fewer moves that the non-destructive game. For instance, sacrificing the Rook pawns to give the Bishop/King pawns more moves gives:

4x dead Rook(1 option) + 10x 1 cap Knight/Bishop/King (17 options) + 4x 2 cap Bishop/King (25 options) for 18 captures, taking all 4 Rook pawns off the table

1^4 * 17^10 * 25^4 = 7.8749762e+17

Thus, the additional states provided by each of these should be less than each of the non-destructive games.

Note, we still haven't taken out doubly occupied positions.

Self-overlapping can be reduced out by determining the amount of overlap each pawn has with another per amount of captures it makes. For instance, a 1 cap Rook's pawn has a range that covers 5 of the 7 locations of the adjacent 0 cap Knight's pawn, meaning we should treat the move contributions of the 0 cap Knight's pawn as 2 moves instead of the usual 7. We would need to create a mapping table for each type of piece's interference against each other type and use it for each of the partition calculations mentioned earlier. This will remove a lot of duplicate or erroneous board states.

Note: We still havn't dealt with pawns being blocked by others and all sorts of other things.

I'll add more later if I get some more time.