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.