Skip to main content
Added filtered counts.
Source Link
Douglas Zare
  • 28k
  • 6
  • 90
  • 130

I count $173558929221226891302430767615551561533417485504 = 1.7356 \times 10^{47}$ ways to place a legal collection of chessmen on the board. Of these, $24639467089379915386890365075260915223928803040 = 2.4639 \times 10^{46}$ have no pawns on the first or last ranks, so at most $14.2\%$ of ways to place a legal collection of chessmen on the board produce a legal position. It is likely that improvements would find more significant restrictions on the set of legal positions.

It takes some effort to determine the possible collections of legal chessmen. ("Chessmen" includes pawns. "Piece" technically refers to a non-pawn.) For example, if White has 8 pawns, 2 bishops, 2 knights, and a king, then it is not possible for Black to have 4 pawns, 3 queens, 4 rooks, 2 bishops, 2 knights, and a king. However, Black could have 4 pawns, 3 queens, 4 rooks, 2 bishops, 1 knight, and a king. If White still has 8 pawns, then each promotion of a Black pawn can be paired with a capture for one side or the other, and in the first collection there were at least 4 promotions and at most 3 captures.

I started by finding the possible vectors of opposed pawns, unopposed pawns, and original pieces not counting kings for each side. Call a pawn opposed if it has not moved from its original column, and neither has the opponent's pawn in that column. Each side starts with $8$ opposed pawns, $0$ unopposed pawns, and $7$ original pieces. Moves include $(-2,+2,0,-2,+1,0)$, which occurs when a White opposed pawn captures a Black opposed pawn, which converts $2$ White opposed pawns into unopposed pawns, and converts $1$ Black pawn into an unopposed pawn. There are $17932$ possible vectors of opposed pawns, unopposed pawns, and original pieces.

Next, convert each vector into the possible vectors of pawns, promotions, and captures. Each unopposed pawn can promote or stay a pawn. Convert each vector of pawns, promotions, and captures into the possible vectors of pawns, knights, bishops, rooks, queens, and king for each side. I used a hash table to avoid duplicates, since the same vector of counts may occur from different numbers of promoted pawns. Count how many ways there were to place these chessmen on the board, and how many ways there were under the restriction that the pawns have to be placed within the $48$ squares in the second through seventh ranks. I used C# with a big integer package. The computation took $2$ hours $34$ minutes on a $2$ GHz processor. Here are the counts filtered by the total number of pieces other than kings:

$$\begin{matrix} 4032 & 4032\newline 2499840 & 2374848\newline 762451200 & 688021440\newline 152490240000 & 130689523200\newline 22492310400000 & 18305596012800\newline 2609108006400000 & 2016206442390528\newline 247865260608000000 & 181841738563525632\newline 19829220848640000000 & 13808933884008775680\newline 1363258933344000000000 & 901054038699836313600\newline 81795535837048927998720 & 51305183887862557540800\newline 4335162450829839506110464 & 2580103899370081990144800\newline 204934580948509440712459776 & 115714657023418620663724800\newline 8709625161842041324664929152 & 4665050555573374751447039520\newline 334969016041319033638193529600 & 170173825673382454767520248000\newline 11721777898941512268159714220800 & 5647729008729626602595924112000\newline 374885578524998042949781990656000 & 171301515200792754380618149854720\newline 10995798990911566467975707768400000 & 4765529886571048034261032746780960\newline 296499744424712483942201077363200000 & 121910613390103852405088592091960320\newline 7359259246674152754334338180912672000 & 2871962662751699192209092269498673600\newline 168140268992852540807133006561199334400 & 62319197518162641915225476408569670400\newline 3532159391229553383833527063326170154240 & 1244357903407170974320709795637765066240\newline 68072251892766786279733898221633351480320 & 22815946937203267917191715682760288217600\newline 1199612470722563512991607127423133252405760 & 382949338893972841238132883627848055957120\newline 19244922194683190664837287286758917707571200 & 5858794635470333659860790877285971462732800\newline 278995789496829967243384718498911484120064000 & 81113217425471696961324265298226557473881600\newline 3512763516196652188175623254752242110008524800 & 967860625456447714742338884049918383560140800\newline 30032513167097689765684275178492499448148377600 & 7180859208049984902733460962414426023904281600\newline 90835621190174574287987518323083620781868441600 & 13544187413659480412286575232707703090739353600\newline 46469725378042907543299835558295158351228160000 & 2814661208855794476422354880818644910233920000\newline 2404159138638549255694710397739697094118400000 & 44498154253195662774573947559960251923200000\newline 4634726695587809641192045982323285670400000 & 21392082322155637297725861387221535360000\newline \end{matrix}$$

The $14.2\%$ value from restricting pawns to $3/4$ of the board indicates that typical positions of legal sets of chessmen have many pawns, about $\log .142/\log .75 \sim 7$, which is not obvious because there are many ways a pawn could underpromote or could be captured. Perhaps one could get a better restriction by keeping track of pairs of opposed pawns, which have to be in their original columns in order. This would add a lot of complexity to the bookkeeping, but it would produce a severe restriction for collections of chessmen which can only occur with a pair of opposed pawns still in their original column, perhaps trimming a few percent off of the $14.2\%$.

I count $173558929221226891302430767615551561533417485504 = 1.7356 \times 10^{47}$ ways to place a legal collection of chessmen on the board. Of these, $24639467089379915386890365075260915223928803040 = 2.4639 \times 10^{46}$ have no pawns on the first or last ranks, so at most $14.2\%$ of ways to place a legal collection of chessmen on the board produce a legal position. It is likely that improvements would find more significant restrictions on the set of legal positions.

It takes some effort to determine the possible collections of legal chessmen. ("Chessmen" includes pawns. "Piece" technically refers to a non-pawn.) For example, if White has 8 pawns, 2 bishops, 2 knights, and a king, then it is not possible for Black to have 4 pawns, 3 queens, 4 rooks, 2 bishops, 2 knights, and a king. However, Black could have 4 pawns, 3 queens, 4 rooks, 2 bishops, 1 knight, and a king. If White still has 8 pawns, then each promotion of a Black pawn can be paired with a capture for one side or the other, and in the first collection there were at least 4 promotions and at most 3 captures.

I started by finding the possible vectors of opposed pawns, unopposed pawns, and original pieces not counting kings for each side. Call a pawn opposed if it has not moved from its original column, and neither has the opponent's pawn in that column. Each side starts with $8$ opposed pawns, $0$ unopposed pawns, and $7$ original pieces. Moves include $(-2,+2,0,-2,+1,0)$, which occurs when a White opposed pawn captures a Black opposed pawn, which converts $2$ White opposed pawns into unopposed pawns, and converts $1$ Black pawn into an unopposed pawn. There are $17932$ possible vectors of opposed pawns, unopposed pawns, and original pieces.

Next, convert each vector into the possible vectors of pawns, promotions, and captures. Each unopposed pawn can promote or stay a pawn. Convert each vector of pawns, promotions, and captures into the possible vectors of pawns, knights, bishops, rooks, queens, and king for each side. I used a hash table to avoid duplicates, since the same vector of counts may occur from different numbers of promoted pawns. Count how many ways there were to place these chessmen on the board, and how many ways there were under the restriction that the pawns have to be placed within the $48$ squares in the second through seventh ranks. I used C# with a big integer package. The computation took $2$ hours $34$ minutes on a $2$ GHz processor.

The $14.2\%$ value from restricting pawns to $3/4$ of the board indicates that typical positions of legal sets of chessmen have many pawns, about $\log .142/\log .75 \sim 7$, which is not obvious because there are many ways a pawn could underpromote or could be captured. Perhaps one could get a better restriction by keeping track of pairs of opposed pawns, which have to be in their original columns in order. This would add a lot of complexity to the bookkeeping, but it would produce a severe restriction for collections of chessmen which can only occur with a pair of opposed pawns still in their original column, perhaps trimming a few percent off of the $14.2\%$.

I count $173558929221226891302430767615551561533417485504 = 1.7356 \times 10^{47}$ ways to place a legal collection of chessmen on the board. Of these, $24639467089379915386890365075260915223928803040 = 2.4639 \times 10^{46}$ have no pawns on the first or last ranks, so at most $14.2\%$ of ways to place a legal collection of chessmen on the board produce a legal position. It is likely that improvements would find more significant restrictions on the set of legal positions.

It takes some effort to determine the possible collections of legal chessmen. ("Chessmen" includes pawns. "Piece" technically refers to a non-pawn.) For example, if White has 8 pawns, 2 bishops, 2 knights, and a king, then it is not possible for Black to have 4 pawns, 3 queens, 4 rooks, 2 bishops, 2 knights, and a king. However, Black could have 4 pawns, 3 queens, 4 rooks, 2 bishops, 1 knight, and a king. If White still has 8 pawns, then each promotion of a Black pawn can be paired with a capture for one side or the other, and in the first collection there were at least 4 promotions and at most 3 captures.

I started by finding the possible vectors of opposed pawns, unopposed pawns, and original pieces not counting kings for each side. Call a pawn opposed if it has not moved from its original column, and neither has the opponent's pawn in that column. Each side starts with $8$ opposed pawns, $0$ unopposed pawns, and $7$ original pieces. Moves include $(-2,+2,0,-2,+1,0)$, which occurs when a White opposed pawn captures a Black opposed pawn, which converts $2$ White opposed pawns into unopposed pawns, and converts $1$ Black pawn into an unopposed pawn. There are $17932$ possible vectors of opposed pawns, unopposed pawns, and original pieces.

Next, convert each vector into the possible vectors of pawns, promotions, and captures. Each unopposed pawn can promote or stay a pawn. Convert each vector of pawns, promotions, and captures into the possible vectors of pawns, knights, bishops, rooks, queens, and king for each side. I used a hash table to avoid duplicates, since the same vector of counts may occur from different numbers of promoted pawns. Count how many ways there were to place these chessmen on the board, and how many ways there were under the restriction that the pawns have to be placed within the $48$ squares in the second through seventh ranks. I used C# with a big integer package. The computation took $2$ hours $34$ minutes on a $2$ GHz processor. Here are the counts filtered by the total number of pieces other than kings:

$$\begin{matrix} 4032 & 4032\newline 2499840 & 2374848\newline 762451200 & 688021440\newline 152490240000 & 130689523200\newline 22492310400000 & 18305596012800\newline 2609108006400000 & 2016206442390528\newline 247865260608000000 & 181841738563525632\newline 19829220848640000000 & 13808933884008775680\newline 1363258933344000000000 & 901054038699836313600\newline 81795535837048927998720 & 51305183887862557540800\newline 4335162450829839506110464 & 2580103899370081990144800\newline 204934580948509440712459776 & 115714657023418620663724800\newline 8709625161842041324664929152 & 4665050555573374751447039520\newline 334969016041319033638193529600 & 170173825673382454767520248000\newline 11721777898941512268159714220800 & 5647729008729626602595924112000\newline 374885578524998042949781990656000 & 171301515200792754380618149854720\newline 10995798990911566467975707768400000 & 4765529886571048034261032746780960\newline 296499744424712483942201077363200000 & 121910613390103852405088592091960320\newline 7359259246674152754334338180912672000 & 2871962662751699192209092269498673600\newline 168140268992852540807133006561199334400 & 62319197518162641915225476408569670400\newline 3532159391229553383833527063326170154240 & 1244357903407170974320709795637765066240\newline 68072251892766786279733898221633351480320 & 22815946937203267917191715682760288217600\newline 1199612470722563512991607127423133252405760 & 382949338893972841238132883627848055957120\newline 19244922194683190664837287286758917707571200 & 5858794635470333659860790877285971462732800\newline 278995789496829967243384718498911484120064000 & 81113217425471696961324265298226557473881600\newline 3512763516196652188175623254752242110008524800 & 967860625456447714742338884049918383560140800\newline 30032513167097689765684275178492499448148377600 & 7180859208049984902733460962414426023904281600\newline 90835621190174574287987518323083620781868441600 & 13544187413659480412286575232707703090739353600\newline 46469725378042907543299835558295158351228160000 & 2814661208855794476422354880818644910233920000\newline 2404159138638549255694710397739697094118400000 & 44498154253195662774573947559960251923200000\newline 4634726695587809641192045982323285670400000 & 21392082322155637297725861387221535360000\newline \end{matrix}$$

The $14.2\%$ value from restricting pawns to $3/4$ of the board indicates that typical positions of legal sets of chessmen have many pawns, about $\log .142/\log .75 \sim 7$, which is not obvious because there are many ways a pawn could underpromote or could be captured. Perhaps one could get a better restriction by keeping track of pairs of opposed pawns, which have to be in their original columns in order. This would add a lot of complexity to the bookkeeping, but it would produce a severe restriction for collections of chessmen which can only occur with a pair of opposed pawns still in their original column, perhaps trimming a few percent off of the $14.2\%$.

Source Link
Douglas Zare
  • 28k
  • 6
  • 90
  • 130

I count $173558929221226891302430767615551561533417485504 = 1.7356 \times 10^{47}$ ways to place a legal collection of chessmen on the board. Of these, $24639467089379915386890365075260915223928803040 = 2.4639 \times 10^{46}$ have no pawns on the first or last ranks, so at most $14.2\%$ of ways to place a legal collection of chessmen on the board produce a legal position. It is likely that improvements would find more significant restrictions on the set of legal positions.

It takes some effort to determine the possible collections of legal chessmen. ("Chessmen" includes pawns. "Piece" technically refers to a non-pawn.) For example, if White has 8 pawns, 2 bishops, 2 knights, and a king, then it is not possible for Black to have 4 pawns, 3 queens, 4 rooks, 2 bishops, 2 knights, and a king. However, Black could have 4 pawns, 3 queens, 4 rooks, 2 bishops, 1 knight, and a king. If White still has 8 pawns, then each promotion of a Black pawn can be paired with a capture for one side or the other, and in the first collection there were at least 4 promotions and at most 3 captures.

I started by finding the possible vectors of opposed pawns, unopposed pawns, and original pieces not counting kings for each side. Call a pawn opposed if it has not moved from its original column, and neither has the opponent's pawn in that column. Each side starts with $8$ opposed pawns, $0$ unopposed pawns, and $7$ original pieces. Moves include $(-2,+2,0,-2,+1,0)$, which occurs when a White opposed pawn captures a Black opposed pawn, which converts $2$ White opposed pawns into unopposed pawns, and converts $1$ Black pawn into an unopposed pawn. There are $17932$ possible vectors of opposed pawns, unopposed pawns, and original pieces.

Next, convert each vector into the possible vectors of pawns, promotions, and captures. Each unopposed pawn can promote or stay a pawn. Convert each vector of pawns, promotions, and captures into the possible vectors of pawns, knights, bishops, rooks, queens, and king for each side. I used a hash table to avoid duplicates, since the same vector of counts may occur from different numbers of promoted pawns. Count how many ways there were to place these chessmen on the board, and how many ways there were under the restriction that the pawns have to be placed within the $48$ squares in the second through seventh ranks. I used C# with a big integer package. The computation took $2$ hours $34$ minutes on a $2$ GHz processor.

The $14.2\%$ value from restricting pawns to $3/4$ of the board indicates that typical positions of legal sets of chessmen have many pawns, about $\log .142/\log .75 \sim 7$, which is not obvious because there are many ways a pawn could underpromote or could be captured. Perhaps one could get a better restriction by keeping track of pairs of opposed pawns, which have to be in their original columns in order. This would add a lot of complexity to the bookkeeping, but it would produce a severe restriction for collections of chessmen which can only occur with a pair of opposed pawns still in their original column, perhaps trimming a few percent off of the $14.2\%$.