Skip to main content
added 1158 characters in body
Source Link

EDIT 3

These things always come to me after I post.

Let's build one cage for both kings. Allocate a corner and a 2-rank by 4-file space for the cage. (One can do a vertical 4 by 2 cage also, but the analysis with pawns is harder. Let's stick to horizontal for now.) Allocate 5 pieces to form the walls of the cage. The nice thing here is that pawns of both colors can be involved, and you can put either king in the corner office. There will be three forbidden squares for one color knight and only one for the other color in the remaining 56 squares. We only need at most two promotions to build a cage, but there are 7x5x7x7x6=10290 different cages to build. Swapping kings or using a different corner gives another factor of 2x4. Without even considering differing multisets beyond what is needed to build a cage, we can use much of the analysis below to get over 10000P many legal games. With more work, we can push the provable lower bound for the ratio to above 10^-12, and that is assuming the weak upper bound for all positions of roughly Qx10^5. I now expect the actual ratio to be between 10^-4 and 10^-7.

3 TIDE

EDIT 2

EDIT 2

EDIT 3

These things always come to me after I post.

Let's build one cage for both kings. Allocate a corner and a 2-rank by 4-file space for the cage. (One can do a vertical 4 by 2 cage also, but the analysis with pawns is harder. Let's stick to horizontal for now.) Allocate 5 pieces to form the walls of the cage. The nice thing here is that pawns of both colors can be involved, and you can put either king in the corner office. There will be three forbidden squares for one color knight and only one for the other color in the remaining 56 squares. We only need at most two promotions to build a cage, but there are 7x5x7x7x6=10290 different cages to build. Swapping kings or using a different corner gives another factor of 2x4. Without even considering differing multisets beyond what is needed to build a cage, we can use much of the analysis below to get over 10000P many legal games. With more work, we can push the provable lower bound for the ratio to above 10^-12, and that is assuming the weak upper bound for all positions of roughly Qx10^5. I now expect the actual ratio to be between 10^-4 and 10^-7.

3 TIDE

EDIT 2

added 5957 characters in body
Source Link

EDIT 2

Here is a lower bound which hinges on several parts.  We will build two cages to isolate the kings, promote 9 pawns, scattershoot the remaining pieces, and remove the illegal and some legal combinations, and then indicate some variations to pump up the lower bound.

The basic setup involves castling both kings on King side, and moving them to the corners and using two stationary pawns and a preselected piece to guard the king.  To simplify things, we will choose one of twenty combinations for guarding: each king gets a nonpawn of their color, or each gets an opposing knight or bishop.  Both kings are on the h file corners and the guard pieces are adjacent to them on the g file.

Once guard pieces are chosen, advance King and Queen pawns, advance material to castle, and then maneuver the guard pieces into position, moving a king out of check if needed (although it should not be necessary).  Now that the kings are caged, advance pawns and move nonpawns in a nonthreatening manner to the g and h files.

Now plan for three pawn captures, especially if bishop color matters.  Place the remaining nonpawns (two of each color) in the file behind pawns of the same color that will promote on that file. To make the analysis simpler, promote no more than four pawns to queens of the same color, and no more than three of any other type.

Once all of the promotions have been made, there will be 56 squares for 21 pieces, and I assert that all the illegal placements are covered by monochromatic bishop placement and by knights putting opposing kings in check.  Before dealing with that assertion, let's count how many potentially legal positions that could be.  As a starter calculation, assume among the 21 pieces outside the cages that there are three or two of each of the 8 allowed types of nonpawns, and call this multiset R  There are P=(56_R)=$(56!)/((35!)(3!)^5(2!)^3)$ such positions.  When we compare this to the standard Q defined below, we get P=Q[((8!)^2(2!)^3 (56!)(32!))/((3!)^5(64!)(35!)) ] This means P/Q is roughly about 1/2x10^-12 . But wait! There's more!

Let us get some hand-waving out of the way. I assert that any legal arrangement of 21 pieces on the reduced board can be reached from any other legal arrangement. Here legal is more strict and includes no knights placing kings in check. The basic idea is to move all 21 pieces into files a-e, and then argue that you can move enough pieces into a restricted portion of files f-h so that you can swap any two pieces, sort of like a complex 14-15 puzzle with the only parity issue involving bishops. I handwave that from any arrangement of 21 pieces in files a-e, you can legally place 8 or more pieces in files f-h without checking either king, leaving 13 or fewer pieces in files a-e. If it helps, I invoke the fact that we can promote so that all of the 8 types of pieces have at least 2 representatives in the 21. (One may need to prove that there is room enough to permute arbitrary piece types, but there are 12 squares to work with in files f-h, so I am asserting with confidence. One also needs to show that there is no locked configuration of 13 pieces on a 5 by 8 board, but by tiling the board by p pentominoes, you can likely show that there will be more than one piece that can move usefully.)

Now let us handle the illegal combinations. They are monochromatic bishops and checking knights. In case there is only one white bishop among the 21, it needs to be on a color square that is different from the square that the guarding white bishop is on. Potentially half of those P many positions may thus be illegal, and less than half if there are two or more bishops among the 21. Similarly the black knights are forbidden from simultaneously occupying f2 and g3, so let them occupy the other 54 squares instead. With at most five knights of one color, this reduces the number of positions by a factor of at most (51x50)/(56x55), so by a factor of more than 80%. So I claim that at least 64/4=16% of the P many combinations are legal, by factoring in contributions from both colors of bishops and knights.

Now to pump up the numbers. First note that we can use a queen side arrangement to double the number of legal positions, counteracting the white bishops complication. Also, we can move the pawns in the h file (or a file for Queen side) and reduce the number of squares from 56 to 53 or 52, depending on if you want a piece between black and white pawns. This (more handwaving using 10353433/5655*54) restores another factor of close to 2. Also, by considering capturing one or two pieces of the 21 gives us a factor of about (1 + 21/35(1 + something positive)), so we build back up to P many positions which are legal, using queen side and using slightly fewer pieces.

Now to bump things up. The above was based on a fixed multiset R, and using just that multiset we got at least 0.64P legal positions, building up to P by capturing one or two of the 21 pieces not involved in the cages. However, there are 56 different multisets allowed for the 21 pieces, if there are only two or three of each type. If we allow one color to have a 4 3 3 2 distribution and the other a 3 2 2 2 among the types, we get 2x12x4 additional multisets at a cost of reducing P by 3/4. So we actually have at least a factor of (56 + 96x3/4)=128 to use in our lower bound. Finally, we have the factor of 20 different guard combinations. Even if we don't consider multisets of size smaller than 29, we get a lower bound of 1600P many legal combinations, which puts us within striking distance of Qx10^-9.

Although there is much work left, I now expect the ratio lies between 10^-15 and 10^-7. The feeling I get is that games involving 26 pieces or less will make no significant contribution to the ratio, and even 28 piece games will not shift the order of magnitude of approximations.

2 TIDE

EDIT

EDIT

EDIT 2

Here is a lower bound which hinges on several parts.  We will build two cages to isolate the kings, promote 9 pawns, scattershoot the remaining pieces, and remove the illegal and some legal combinations, and then indicate some variations to pump up the lower bound.

The basic setup involves castling both kings on King side, and moving them to the corners and using two stationary pawns and a preselected piece to guard the king.  To simplify things, we will choose one of twenty combinations for guarding: each king gets a nonpawn of their color, or each gets an opposing knight or bishop.  Both kings are on the h file corners and the guard pieces are adjacent to them on the g file.

Once guard pieces are chosen, advance King and Queen pawns, advance material to castle, and then maneuver the guard pieces into position, moving a king out of check if needed (although it should not be necessary).  Now that the kings are caged, advance pawns and move nonpawns in a nonthreatening manner to the g and h files.

Now plan for three pawn captures, especially if bishop color matters.  Place the remaining nonpawns (two of each color) in the file behind pawns of the same color that will promote on that file. To make the analysis simpler, promote no more than four pawns to queens of the same color, and no more than three of any other type.

Once all of the promotions have been made, there will be 56 squares for 21 pieces, and I assert that all the illegal placements are covered by monochromatic bishop placement and by knights putting opposing kings in check.  Before dealing with that assertion, let's count how many potentially legal positions that could be.  As a starter calculation, assume among the 21 pieces outside the cages that there are three or two of each of the 8 allowed types of nonpawns, and call this multiset R  There are P=(56_R)=$(56!)/((35!)(3!)^5(2!)^3)$ such positions.  When we compare this to the standard Q defined below, we get P=Q[((8!)^2(2!)^3 (56!)(32!))/((3!)^5(64!)(35!)) ] This means P/Q is roughly about 1/2x10^-12 . But wait! There's more!

Let us get some hand-waving out of the way. I assert that any legal arrangement of 21 pieces on the reduced board can be reached from any other legal arrangement. Here legal is more strict and includes no knights placing kings in check. The basic idea is to move all 21 pieces into files a-e, and then argue that you can move enough pieces into a restricted portion of files f-h so that you can swap any two pieces, sort of like a complex 14-15 puzzle with the only parity issue involving bishops. I handwave that from any arrangement of 21 pieces in files a-e, you can legally place 8 or more pieces in files f-h without checking either king, leaving 13 or fewer pieces in files a-e. If it helps, I invoke the fact that we can promote so that all of the 8 types of pieces have at least 2 representatives in the 21. (One may need to prove that there is room enough to permute arbitrary piece types, but there are 12 squares to work with in files f-h, so I am asserting with confidence. One also needs to show that there is no locked configuration of 13 pieces on a 5 by 8 board, but by tiling the board by p pentominoes, you can likely show that there will be more than one piece that can move usefully.)

Now let us handle the illegal combinations. They are monochromatic bishops and checking knights. In case there is only one white bishop among the 21, it needs to be on a color square that is different from the square that the guarding white bishop is on. Potentially half of those P many positions may thus be illegal, and less than half if there are two or more bishops among the 21. Similarly the black knights are forbidden from simultaneously occupying f2 and g3, so let them occupy the other 54 squares instead. With at most five knights of one color, this reduces the number of positions by a factor of at most (51x50)/(56x55), so by a factor of more than 80%. So I claim that at least 64/4=16% of the P many combinations are legal, by factoring in contributions from both colors of bishops and knights.

Now to pump up the numbers. First note that we can use a queen side arrangement to double the number of legal positions, counteracting the white bishops complication. Also, we can move the pawns in the h file (or a file for Queen side) and reduce the number of squares from 56 to 53 or 52, depending on if you want a piece between black and white pawns. This (more handwaving using 10353433/5655*54) restores another factor of close to 2. Also, by considering capturing one or two pieces of the 21 gives us a factor of about (1 + 21/35(1 + something positive)), so we build back up to P many positions which are legal, using queen side and using slightly fewer pieces.

Now to bump things up. The above was based on a fixed multiset R, and using just that multiset we got at least 0.64P legal positions, building up to P by capturing one or two of the 21 pieces not involved in the cages. However, there are 56 different multisets allowed for the 21 pieces, if there are only two or three of each type. If we allow one color to have a 4 3 3 2 distribution and the other a 3 2 2 2 among the types, we get 2x12x4 additional multisets at a cost of reducing P by 3/4. So we actually have at least a factor of (56 + 96x3/4)=128 to use in our lower bound. Finally, we have the factor of 20 different guard combinations. Even if we don't consider multisets of size smaller than 29, we get a lower bound of 1600P many legal combinations, which puts us within striking distance of Qx10^-9.

Although there is much work left, I now expect the ratio lies between 10^-15 and 10^-7. The feeling I get is that games involving 26 pieces or less will make no significant contribution to the ratio, and even 28 piece games will not shift the order of magnitude of approximations.

2 TIDE

EDIT

Bounty Ended with 100 reputation awarded by Joel David Hamkins
added 1857 characters in body
Source Link

There are 165 possible multisets arising from promoting 8 pawns of one color. I suspect an upper bound for the number of maximal legal multisets is 165165, given that 2k promotions usually require k captures. This suggests an upper bound of 272255Q8Q for the number of all possible positions, or about 136125Q217800Q.

There are 165 possible multisets arising from promoting 8 pawns of one color. I suspect an upper bound for the number of maximal legal multisets is 165165, given that 2k promotions usually require k captures. This suggests an upper bound of 272255Q for the number of all possible positions, or about 136125Q.

There are 165 possible multisets arising from promoting 8 pawns of one color. I suspect an upper bound for the number of maximal legal multisets is 165165, given that 2k promotions usually require k captures. This suggests an upper bound of 272258Q for the number of all possible positions, or about 217800Q.

added 1857 characters in body
Source Link
Loading
added 268 characters in body
Source Link
Loading
added 301 characters in body
Source Link
Loading
Source Link
Loading