8

Call a collection of (white and black) chess pieces legal if it occurs in the position of a legal chess game. For example, KQRRBBNNPPPPPPPPkqrrbbnnpppppppp is the collection at the beginning of the game. It seems any subset of this (still containing the two kings) is possible as well. But sometimes you can have lots of promotions, so for example Kkqqqqqqqq is possible if black promotes all eight pawns to queens while all other pieces are captured.

Which collections of pieces are legal?

This answer on MathOverflow conjectures/states without proof that the legal collections are those that can be obtained from the starting collection using the following two operations:

  1. Delete any (non-king) piece and promote at most one white and at most one black pawn.

  2. Delete a pawn and promote at most one pawn of the same color and at most two pawns of the opposite color.

Is this characterization correct?

14
  • 2
    Certainly any legal collection can be generated by those two operations: in order to promote a white pawn, that pawn must somehow "overtake" its opposing black pawn. So either 1) the pawn must move to a different rank by taking a piece. Doing so also allows the opposing black pawn to promote. Or 2) The opposing black pawn must be taken. If it is pawn that takes this opposing black pawn, then the two white pawns can promote, as can the black pawn whose rank is cleared by the capturing pawn. What's not obvious, however, is that all such collections are actually possible!
    – Mathmo123
    Dec 14 '20 at 17:46
  • 1
    For example, KQQQQQQQQQRRBBNNk can be generated from those operations... Is there any way that many promotions can actually happen without the black king already being in checkmate? It seems hard to answer such a question for all possible collections!
    – Mathmo123
    Dec 14 '20 at 17:49
  • 2
    Indeed. Perhaps a program could achieve the task given a desired collection? Your particular configuration is a popular one to attempt: chess.stackexchange.com/q/19936/25684
    – A. Rex
    Dec 14 '20 at 18:19
  • 1
    @Mathmo123 Or 3) the opposing pawn moves out of the way by capturing. Dec 14 '20 at 22:46
  • 2
    @Acccumulation Your point 2 is not necessarily true; it could have already passed the black pawn on the adjacent rank.
    – D M
    Jan 18 at 21:34
6
+50

Yes the characterization is correct, and there are 58,084,310 legal collections in total.

To make headway, we need the right level of discourse, avoiding loss of accuracy while avoiding diving into trivialities.

Necessity & sufficiency of the deletion moves

Two kinds of operation were suggested to be necessary & sufficient to reach all legal collections:

(1) Delete a (non-K) officer & promote at most 1 wP and 1bP
(2) Delete a P & promote at most 1P of that color and at most 2Ps of the other color.

Firstly, the two criteria are necessary. To unblock a file a capture must take place. Capturing an officer will allow both pawns from a file to promote. A pawn capturing a pawn from a neighbouring file is more efficient, as it allows three pawns to promote.

The condition is also sufficient, as can be seen by dividing up the board into 4 pairs of files. We have to make assumptions that the kings can keep out of the way of the action. See later for an example which explores the validity of this assumption.

"Supply & demand"

Maybe worth moving on to the question of which collections are achievable in this way:

  1. Count the number of visible "non-starting officers" for each side (queens beyond the first; other officers beyond the second of that type): N_w & N_b
  2. Count the number of "awol pawns" on each side: (pawns morphed into NSOs aren't counted): A_w & A_b
  3. Count the number of "missing officers" for each sides (missing queen, or other officers less than the second of that type): M_w & M_b

Then the following elegant "supply & demand" inequalities are necessary and sufficient criteria for a legal collection:

M_b + 2*A_b >= N_w - M_w - A_w
M_w + 2*A_w >= N_b - M_b - A_b

Grouping the terms by White & Black, the left hand side is the "supply", the right hand side is the "demand". The supply is always non-negative, so if the demand is zero or less, it's always satisfied. Similarly, a supply of 8+ will meet any demand that can occur.

Here's an example. Can we have 18 queens on the board? Yes!

N_w = N_b = 8
(because 8 promoted pawns on each side)

A_w = A_b = 0
(every missing pawn was promoted)

M_w = M_b = 6
(all Rs, Bs & Ns were captured)

M_b + 2*A_b >= N_w - M_w - A_w
translates to:
6 + 2*0 >= 8 - 6 - 0
6 >= 2

So this is legal. Similarly for White supply for Black demand. Even if we had the knights still on the board, so M_b = M_w = 4, the inequality would be 4 >= 4, so still legal.

Aside on mate/stalemate

Some wonder if such a position can be achieved without mate or stalemate, which is a fair question. The answer is yes. It's like asking to prove that 450g of cornflakes will all fit in a box. It's a matter of common experience that one can just shake the pack and the cornflakes settle down. There are not too many cornflakes in the box. Although it's obviously illegal, it's possible to arrange the kings and up to 34(!) white queens on the board without mate or stalemate looming. At this density, it getting a bit tight, but this thought experiment shows that when we are dealing with merely 18 queens, where moreover friendly queens can shield against enemy ones, there a vast amount of slack, and no need to worry about forced mates or stalemates. Even with 18 queens, the chessboard is a very empty box of cornflakes :-)

Counting the collections

Let's focus on just the White units first. How many legal White collections are there? 8,694. Here's a quick proof.

Let k be the number of visible promotions to rook, knight or bishop (i.e. officers beyond the original complement of 2 for any of these types). (For symmetry reasons, queens are dealt with in a couple of paragraphs instead.)

Let v(k) be the number of different combinations of R,N,B which achieve this.

v(0) = 27:
because there may be 0-2 remaining of each of R,N,B. 

For k>0, v(k) = (k^2 + 15*k + 38)/2
e.g.:

v(1) = again 27:
3 ways to pick one of R,N,B to be 3; 
& 0-2 possible for each of the other two types.

v(2) = 36:
27 ways to have 4,0-2,0-2; 
& 9 ways to have 3,3,0-2.

Then the other 8-k pawns may still be Ps, or turned into Qs, or captured.

Let q be the number of visible queen promotions (i.e. queens beyond the original complement of 1).

Let u_k(q) be the number of different combinatorial ways we can achieve this (in terms of surviving pawns, queens and captured pawns)

u_k(0) = 2*(9-k)
because we can have 0 to 8-k pawns, and the rest are captured,
independently we have 0 or 1 queen.

For q>0, u_k(q) = (9-k-q)

s(k) = sum(q=0,...,8-k) [u_k(q)]
= 2*(9-k) + (8-k) + (7-k) + ... 1
= (9-k)(12-k)/2.

Check:
s(8) = 2: 0-1Q
s(7) = 5: 0P,0-2Q; 1P;0-1Q
...
s(0) = 54: = 55-1

So the total number of of legal White collections is:
sum(k=0...8) [s(k)*v(k)]
= 8,694

All of these white collections are indeed achievable, e.g. if Black has only bare king remaining, but in fact in many other situations too: the supply/demand inequalities are not very demanding.

The next exercise involves counting for each combination of N_w, M_w ,A_w how many White collections exist.

I computed the following table of numbers of collections, sorted according to the total number of pieces on the board, as shown in this table:

enter image description here

For each number of units from 2-32, this shows

  • v_0: the number of basic candidates without worrying about supply-demand,
  • v_1: the number who have a single fail against supply-demand,
  • v_2: the number who have a double fail against supply-demand.

To avoid double counting, the number of legal positions is computed as v_1 - 2*v_2 + v_3. My calculations match Kryukov's prior results exactly.

Note that there are no fails until one reaches 25 units. That's because with 8 captures, all candidate promotion collections can be achieved.

An "extra credit" open question (work in progress)

Retro enthusiasts further distinguish between the colour of squares the bishops are on, since that is an invariant. This has a major, visible impact on potential legality, is part of the essential classification for chess tablebases, and is also an aesthetic concern in composition. The corresponding term then is "non-standard officers" (queens or "tinted" bishops beyond the first; rooks or knights beyond the second). The count of missing officers is based on the same 5 types. The determination of which additional inequalities are necessary and sufficient to characterize legal collections is now substantially more complicated.

The best approach may be to first apply the adapted supply/demand inequalities. Then can ask how many extra pawn captures are required to "nudge" certain bishops to the correct tint?

A pawn capture of an officer/pawn will result in a batch of respectively 2/3 pawns all promoted on same tint squares, but it seems that for each such batch, we are free to choose the tint independently.

5
  • 2
    Yes, you are right, the tint of the bishops is a brilliant observation! If no pieces are missing, except for $x$ black and $2x$ white pawns, and there are $2x$ additional white bishops, then an even number of them must be on white-squares (so with the original white-squared white bishop, an odd number of them).
    – domotorp
    Jan 20 at 8:13
  • @domotorp: yes! There's all kinds of random constraints: e.g. if 20 bishops are on the board, then the number of white & black light-tint bishops differs by at most 2. Need some systematic way to simplify the possibilities in order to be able to focus on real limiting factors
    – Laska
    Jan 21 at 12:33
  • 3
    Cool write-up of a lot of things, especially the bishop tint. I agree there are 8694 legal collections considering only pieces of a single color. However, I think there are 58084310 legal collections total. This write-up by someone else agrees: stmintz.com/ccc/index.php?id=77068 (see section 2.2 and especially the inequality constraint (1))
    – A. Rex
    Jan 21 at 14:35
  • @A.Rex ok I found the bug which was just in the totting up. The main spreadsheets were ok, phew! Answer updated, thanks for support
    – Laska
    Jan 25 at 14:56
  • @2080: thanks much appreciated
    – Laska
    Jan 25 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.