Author: Ratko V Tomic

Date: 19:47:25 11/11/99

Go up one level in this thread

> One of the gentlemen is interested in max of promoted pieces. ie I > remembered seeing the thread that you can have 8 queens of one color > and 4 of the other. Can someone tell me what the max #'s are for > rooks, knights and bishops. You can have 9 white Queens and 9 black Queens in a legal sequence of moves (with cooperating "opponents"). To see such sequnce of moves, you note first that a white pawn can bypass a black pawn blocking its way by capturing a black piece behind a black pawn on an adjacent line (e.g. WP on a5, BP blocking it on a6, BP on b5, BN on b6; white pawn captures knight on b6 and gets thus behind the BP on b5, so it can now promote; and, of course, once WP is gone from the a-line, the black pawn on a6 can promote as well). Using this maneuver 4 times with white pawns capturing black non-pawns and 4 times with black pawns capturing white non-pawns, you get 8 promotions on each side, and as a side effect, you have also removed 8 non-pawns (4 white and 4 black) off the board. Thus you end up with at most 32-8=24 pieces (and 0 pawns left) on the board, and as many as 18 Queens (or 20 Rooks, or 20 Bishops, or 20 Knights). For example, each side could legally have 10 Knights, King and 1 more piece (one of Q, R, N; which means that there are only 9 distinct material content states which contain 10 Knights on each side). The maneuver described above is one of the only two (what I call) the "optimal promotion maneuvers," optimal in the sense of generating either the most promotions overall (which is the maneuver above) or the most promotions per capture which is the maneuver of the following type: White pawns on a5, b5, Black pawns on a6 and b6 -- White pawn captures a5xb6, allowing 2 white pawns on the b6 abd b5 and 1 black pawn on a6 to promote, i.e. a single capture (of a pawn by a pawn) allows as many as 3 promotions (2+1, 2 for the capturing side). The whole meneuver consumes 4 pawns and creates 3 (2+1 or 1+2) non-pawns. The example you were mentioning belongs to this 2nd type of maneuver, repeated 4 times (with capturing by one side all 4 times). The result is at most 12 extra non-pawns (like 8+4 extra Queens), and at least 4 captures, leaving at most 32-4=28 non-pawns on the board (and 0 pawns). If we call these two maneuvers P type ("pawn type" i.e. the second one, where a pawn is captured), and N type ("non-pawn type" i.e. the first one where a non-pawn is captured), then one can have at most 4 P or at most 8 N maneuvers, or any combination of the two, i.e. there are 5 maximal promotion cases: {0P+8N, 1P+6N, 2P+4N, 3P+2N, 4P+0N} which result in maximum promotions rising as {12, 13, 14, 15, 16} and the remaining material count dropping as {28, 27, 26, 25, 24}. The P type costs 1/3rd of a pawn captured per promotion (black+white), while the N type costs 1/2 of a non-pawn captured per promotion (black+white), and the full payment must be made in the whole numbers _in advance_ of getting any of the promotions (i.e. a whole captured pawn is paid before the 2+1 or 1+2 promotions are received, or a whole captured non-pawn is paid before 1+1 promotions are received). Or, looking at promotions for one side only, the restriction of black & white promotions breakdowns to 2+1, 1+2 and 1+1 combinations (but not to 3+0, 0+3, 2+0, 0+2), we can say that the P type maneuvers with white capturing cost 1/2 of a black pawn capture per 1 white promotion (i.e. for one black pawn white can "buy" up to two promotions), and with black capturing white pawn, they cost 1 white pawn capture per 1 white promotion, while the N type promotions cost 1 white or one black non-pawn capture per 1 white promotion. We can write these relations in a more usable (by the program) form as an upper bound on number of white promotions in terms of various captures: wPr <= 2*bpc + bnc + wpc + wnc (1) where wPr is the # of white promotions, <= means less or equal, bpc and bnc are numbers of captured black pawns and nonpawns, and wpc, wnc are numbers of captured white pawns, nonpawns. The earlier program by Uri had used a weaker constraint which had a factor 2 for bpc and bnc, giving thus the larger upper bound (my enumeration program reproduces Uri's 3.701*10^46 figure chess position upper bound, to 11 significant digits, when I replace bnc with 2*bnc above), This can be simplified if we denote total captured white (or black) units as wc (or bc), since: wc = wnc + wpc (2w) bc = bnc + bpc (2b) we can rewrite (1) as: wPr <= bpc + bc + wc (3) The obvious problem in applying (3) to check whether given material content (MC) state is legal, is that that an MC state consists only of counts of pieces of each type (i.e. an MC state is specified as a list of 10 numbers, each being 0 to max for a given piece type). It doesn't contain capatures and promotions, but only the final counts. For example, the same MC state may represent a black pawn which had been promoted to non-pawn, then captured as a black non-pawn (adding thus 1 only to the bc term in (3)) or it had never promoted and was captured as a pawn (adding 1 to bpc and bc terms in (3)). To resolve this mismatch of what constraint (3) needs and what we have work with in an MC, we'll define first some numbers obtainable easily from an MC state (i.e. from the list of 10 counts for 10 piece types which can change tier counts; kings have fixed counts). Piece Excess = excess in piece count above the initial position count value i.e. white Queens above 1, W.Rooks above 2, etc; defined as 0 if the piece count is equal or below the initial position count. White Excess = wx = sum of piece excesses for all white pieces bx = sum of piece excesses for all black pieces Since only non-pawns can have nonzero excess, we omit 'p' /'n' symbols. Clearly wx is always lower or at most equal to the number of white promotions (i.e. it is equal only if no promoted piece type suffered captures, otherwise it is lower). Nonpawn Defect = defect in nonpawn piece count below its initial position count (e.g. if MC state has no White Rooks, the W.Rook has defect 2; etc; defect is defined as 0 if piece count is greater or equal its initial count). We denote defects as wnd, bnd (for white & black nonpawns). For a given nonpawn, its defect is at most equal to the number of captures of that nonpawn (it is equal if no promotions into that nonpawn occured, otherwise it is smaller than the # of captures). Pawn Defect = defect in pawn counts, beyond what the excess (wx or bx) implies for promotions (of white or black). If the MC has wnp white pawns, then white pawn defect is wpd = (8-wnp)-wx, and black pawn defect is bpd = (8-bnp)-bx. The pawn defect is at least equal to the captured pawns (for each color), but it is greater if promoted-into piece types are captured (the net outcome being as if the pawn which was promoted was actually captured). White Defect = wd = wnd + wpd (these are merely definitions of total one side defect) bd = bnd + bpd We see therefore that neither the excesses are equal the promotions, nor the defects are equal the captures, even though they do seem close. So the constraint (3) doesn't seem to apply to the numbers available from a given MC but to some fictitious numbers we can't know from knowing only the MC. But we can quantify the difference between the two sets of quantities. The common elemental cause behind all these differences is a pawn which promotes to some piece type and there is/was also a capture of that same piece type (before or after promotion). The net outcome of this sequence is that this piece type count remains unchanged, thus its excess and its defect are 0, while there was 1 promotion (not reflected in the piece excess) and 1 non-pawn capture which isn't reflected in this piece defect, and a there apears one pawn defect (from (8-7)-0=1), even though no pawns were captured. If this two step (the cancelled-out promotion) transaction is repeated again, the pawn defect will rise to 2, there will be 2 promotions and 2 non-pawn captures, while the excess & the defect for this piece will remain unchanged. If we denote the count of this transactions on white (black) as wa (ba), i.e. the white (black) "adjust value," we'll have the following relations: wPr - wa = wx (4w) bPr - ba = bx (4b) wnd = wnc - wa (5w) bnd = bnc - ba (5b) wpd = wpc + wa (6w) bpd = bpc + ba (6b) Equation (4) tells us that each repeat of this transaction cancels out 1 promotion from reflecting in the excess value (in the earlier wa=2 example, there were 2 white promotions and 0 white excess, i.e. by eq. (4): 2 - 2 = 0). Equation (5) tells us that nonpawn captures (wnc) were reduced by each transaction by 1, to produce smaller wnd value (in the wa=2 example wnd=0, wnc=2, hence by eq. (5) we have 0=2-2). Finally, eq (6) tells us that the pawn defect, which in the absence of this transaction is equal to the number of pawn captures, is increased by these transactions, 1 per transaction (in the wa=2 example, we have wpd=2, wpc=0 and eq. (6) gives 2=0+2). So these 3 pairs of relations connect the numbers we can get out of piece counts (wx, wpd, wnd,...) with the numbers we can't know from the piece counts (wPr, wpc, wnc,...) via a pair of quantities (wa and ba) we can't know from the piece counts. But by adding equations: (5w)+(6w) and (5b)+(6b), the wa cancels out from the right hand sides, giving: wnd + wpd = wnc + wpc bnd + bpd = bnc + bpc and using the definitions for wd, bd, wc and bc, we get: wd = wc (7w) bd = bc (7b) i.e. the total defects (for pawns and nonpawns) are always equal total captures, for each side. Using (7w) and (7b) in our basic inequality (3) we get: wPr <= bpc + bd + wd (3.1) applying to this (4w) as: wPr=wx+wa and (6b) as: bpc=bpd-ba we get: wx+wa <= bpd-ba + bd + wd or: wx <= bpd + bd + wd - (wa+ba) (3.2) Since (wa+ba) is always a positive quantity or zero, (3.2) implies that: wx <= bpd + bd + wd (3.3) (i.e. using the logic: if x <= 10-3 then x <= 10 as well). So the final result (3.3) looks exactly as our inequality (3), except that the promotions are replaced with the corresponding excesses and the captures with the corresponding defects, as someone might have guessed to start with by incorrectly assuming that defects are the same thing as captures and excesses the same thing as promotions (reaching thus the right conclusion for the wrong reason). The (3.3) now has onkly the numbers easily obtainable from the piece counts (i.e. the MC state), and that's what I used in my program to count 2.46*10^46 chess positions and the 155/157 bit encoding.

This page took 0 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.