Possible pawn combinations

Question

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 1

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.

Answer 2

My chess terminology isn't the greatest, but I hope the following is at least understandable. I don't fully understand the conditions laid out in the original problem, so I want to assert that the following assumptions are made:

1. Pawns are not unique. For example, if the only pawn on the board is at h4, it doesn't matter if that pawn came from h2, f2, or e2.
2. We seek to find the total number of unique pawn configurations, as described above. The positions of any piece other than a pawn of the specified color does not matter.

With the above conditions laid out for this attempted solution, I'd like to make some more assumptions:

3. Because the King cannot be captured (for either side), it will be assumed that the players are allowed to make an infinite number of 'trivial' moves.
4. Because of assumption 3, we will assume that the 8 enemy pawns will be able to be 'queened'
5. Because of assumptions 3 and 4, we will assume that this allows us to take the time required to position/remove the remaining 15 enemy pieces and 7 allied pieces wherever we want.
6. Because of assumption 5, we will assume that 15 'column changes' (file changes?) are permitted by the allied pawns.

Now, I'll borrow John Kossa's bounding system to see if I can get narrower bounds.

Let's establish first a lower bound. If each pawn is restricted to its own column, we have 7 states for each pawn. This gives us our first lower bound of 7^8 = 5,764,801.

Let's establish an upper bound. We have 6*8=48 positions for a pawn, 8 pawns, and the possibility of as few as 0 pawns. So we can add up the total number of organizations of these pawns if we assume absolute free movement. We will use the formula 48!/((48-#pawns)((#pawns)!)) and sum for #pawns=0->8 to get our upper bound of 465,174,935.

I may return later with a python program to attempt to calculate this. I have a program running which accurately calculates valid states. It has calculated 1 for 0 pawns, 48 for 1 pawn, 1,128 for 2 pawns, 17,294 for 3 pawns, 194,462 for 4 pawns, 1,708,715 for 5 pawns, and 12,179,855 for 6 pawns. I will report back in approximately 14 days with more information.I've had to terminate the program early. The below is my final update.

Using this information, I predict that the final number will be somewhere in the neighborhood of 415,354,443.

Answer 3

Not a solution, just some ideas that are too extensive for the comments.

Let's say a configuration (a set of up to 8 possible positions for white pawns) is "permissible" if it's possible get to that position as follows: start with all the pawns on the second rank, throw some of them out, and then apply a series of moves, where each move moves a pawn either one step forward, one step diagonally forward-right, or one step diagonally forward-left, to a square not already occupied by a pawn. (For example, the configuration (a2, b2, a3) is not permissible.)

Being "permissible" might not be the same as being "valid" (meaning you can get there by the standard rules of chess). For example, (a2, a3, a4, a5, a6, a7, h2, h3) is permissible but not valid (because it would require white to play 16 captures, while black only has 15 pieces which may be captured).

I have a possible combinatorial condition for a configuration to be "permissible."

For motivation, look at the example (a2, a3, b2) of a configuration which is not permissible. Here's why it's not permissible: all three of the pawns would have had to start on the starting "base" (a2, b2), because you can't get to a3 from any other square. But of course you can't have three starting pawns on only two squares.

In general, call a "base" a subinterval of (a2, b2, ..., h2) -- in other words, a "base" is just a row of consecutive squares. The "length of the base" is the number of squares in the row. The "pyramid on the base" is the set of squares which can only be reached starting on the base. For example, the pyramid on (a2, b2) is (a2 a3 b2); while the pyramid on (b2, c2, d2) is (b2 c2 c3 d2).

Claim: A configuration is permissible if and only if it satisfies the following condition: For every base B, the number of pawns in the pyramid on B is at most the length of B.

The condition is clearly necessary, since every pawn in the pyramid on B must start out within B.

The other direction is more complicated: My idea is to argue that, if you start with a position satisfying the condition, then you can move a pawn backward in such a way that the condition remains satisfied... then repeating the process you eventually get back to a starting position. But the details will be annoying to write.

--

tl;dr

I simplify the problem to consider "permissible" configurations, which isn't the same as the question asked, but is more amenable to analysis.

I give a combinatorial characterization of "permissible" configurations, but without a complete proof.

I don't offer any ideas about how to count them.