How many different positions are there in the game tree of chess?

Additional material

Full references, as given by Prof. Nievergelt:

J. Nievergelt: Information content of chess positions,
ACM SIGART Newsletter 62, 13-14, April 1977.

reprinted in:
J. Nievergelt: Information content of chess positions:
Implications for game-specific knowledge of chess players,
283-289 in Machine Intelligence 12, (eds. J. E. Hayes,
D. Michie, E. Tyugu), Clarendon Press, Oxford, 1991.

-- J. Nievergelt <jn@inf.ethz.ch>

[ Editor: from "How many chess positions are there?", an archive of
  mail and Usenet postings (August 1996) compiled by Joe Snyder
  <zp4@semaphorecorp.com> at http://www.semaphorecorp.com/chess/chron.html.
  Arrangements among the correspondents, program listings and a side
  discussion of a "theory of chess" are omitted. ]

I was wondering how many different legal board positions there are.  In
other words, if a database listed every legal board, how many database
records would there have to be?

The only value I found on the net was at
http://www.inwap.com/pdp10/hbaker/hakmem/proposed.html, which claims
there are 10^40 positions.

Does anyone know a good way to calculate that estimate?

In any board position, each player will have a king and from zero to 15
other pieces:  zero or one queen, zero to 2 bishops, zero to 2 knights,
zero to 2 rooks, and zero to 8 pawns (promoted or not).  That means in
any board position, each player will have one of 2 x 3 x 3 x 3 x 9 or
162 possible collections of White or Black pieces.

If on any board White can have 162 possible different collections of
pieces, and Black the same, then there are 162 x 162 = 26,244 possible
different collections of the total pieces on any board.

For each of the 26,244 possible collections, we need to calculate how
many different ways the pieces can actually be placed on the board.  If
we ignore illegal placements (such as kings on adjacent squares), the
combinations for a full board of 32 pieces would be computed as 64
squares taken 32 at a time or

  64!
------
32!32!

but I approximate that to be only 4.8223 x 10^18 (watch out, my math is
very rusty).

[ Editor: 64!/(32!32!) = 1.83 x 10^18; 4.82 x 10^53 is the value of
  64!/32!, which comes up later in the discussion. ]

There are still 26,243 other placement combinations (of fewer pieces) to
add up, but it doesn't look like it's possible to reach 10^40.  Ignoring
illegal boards would drop the total even more, though I have no idea how
to estimate that.  The total also almost doubles by having to indicate
if it's White or Black's turn ("almost" because some boards will be
illegal depending on the turn).  There also have to be state indicators
for whether castling is allowed, en passant captures, etc.

Can anyone improve on this?  What are the flaws in the above?

-- Joe Snyder <joe@semaphorecorp.com>

One other thing to consider is pawn promotion.  With pawn promotion
there can be up to nine queens of a single color on the board (of
course, in this scenario the other side must have lost some of its
pawns).

There is also one mathematical point that I think you may have
overlooked.  You show that each side has 162 possible collections of
pieces, and that between the two sides there are 26244 possible
collections.  However, you seem to have done this without considering
the number of ways these pieces can be arranged amongst the 32 available
squares.  (For example, if you had four marbles, 2 white and 2 blue,
you could have only 3x3=9 collections while you could arrange them in
many more ways:  6 using all chips, plus 12 using both white and only
one blue, plus 6 using the white ones only, etc.)

Thus, 10^40 might be reasonable after all.  So, instead of 26244, you
would have to multiply 64!/(32!32!) by a much larger number.  The new
number is obtainable but it requires doing more arithmetic than I care
to do "by hand." ...

Of course, after making these computations and multiplying the result
by suitable numbers to take care of the "switches", and after taking
care of pawn promotion, we shall have a rather large upper bound, due to
the fact that many of the positions described are illegal or
unattainable (for example, pawns moving over more files than there are
captured men).

A computer program, although it might not finish in our lifetime, could
get a much smaller upper bound, although it would be difficult to rule
out all of the unattainable positions.

-- John Thompson <thompson@uffenham.isu.edu>

Two errors need to be fixed.

)board position, each player will have one of 2 x 3 x 3 x 3 x 9 or 162

not 162, but 486.  2x3 = 6, x3 = 18, x3 = 54, x9 [Editor: "x3" in the
original] = 486.  2 from Q, 3 each from R,N,B, 9 from P.

More seriously, however:

)  64!
)------
)32!32!

is the correct number telling how many ways there are to mingle 32
occupied squares with 32 unoccupied squares.

But you've ignored the order of placing the pieces into those occupied
squares:  That's another factor of 32!.  (Example: suppose there are 3
pieces, WK, WP, BK.  #of ways of placing 3 occupied squares and 61
blanks is 64!/3!61!.  But the three pieces can be placed on the occupied
squares in 3! ways.)

This correction should get you into the ballpark of my estimate.

I estimated the number of pawn positions (in the no-captures situation,
this is 15^8), times all pieces in all positions, dividing by 2 for each
of the R,N which are interchangeable, dividing by 2 for each pair of Bs
(since half the posns will have the Bs on same color squares).

There are more positions with one or two captures, since the Ps can
switch columns then.  Someone has told me that adding underpromotion
brings the count up to ~10^43.  I think that's a tad high, but haven't
done the arithmetic.

-- Richard Schroeppel <rcs@cs.arizona.edu>

It seems to me that every board has inherent state information
(promoted pawns, castling state, en passant state, and whose turn), and
some of those states are often completely independent of actual piece
positions.  For example, whether a board allows castling or not, or
whether a pawn can be captured en passant, can not be determined only by
examining the piece positions.

This means that by simply counting pieces and counting every possible
state for each piece, we can compute a provable, guaranteed upper limit
to the number of board positions, but that would include a tremendous
number of illegal boards, and the actual number of legal boards can only
be determined by the brute force computation of each board.

[ Editor: a program outline follows in the original: nested loops over
  the numbers of each kind of piece, of moved rooks and king, of
  promoted pawns and of en passant flags for each side, calling an
  "arrange" routine for each combination. ]

The duplicate loops for the white and black pieces and states each cause
555,985 iterations, so the above code calls the arrange routine
555,985 * 555,985 * 2 times. ...  If the for-loops for the castling and
en passant states are removed from the code above (so we can assume
arrange is accounting for those states), the remaining loops each cause
only 69,498 iterations, so the arrange routine is called 69,498 * 69,498
* 2 times.

-- Joe Snyder

An amazing number since the universe is only 10^18 seconds old
according to the latest scientific estimates.  (Using simple
arithmetic), it is possible to play a million complete chess games per
second since the beginning of the universe and still not exhaust all
possible games.  Amazing.

-- Dave B. <yorkshire@sympatico.ca>

Here, I believe, is the math involved to compute the (very generous)
limit:

64!/(wp! wr! wk! wb! wq! bp! br! bk! bb! bq! (64 - total_men)! * 1 * 1)

The two ones at the end, of course, don't affect the result; I only
placed them there so as to show that the kings are not forgotten.
total_men is the sum of the current wp, wr, wk, wb, wq, bp, br, bk, bb,
and bq, plus two for the kings.  (64 - total_men) is the number of blank
squares.  Of course, the above expression doesn't take any switches into
account.

-- John Thompson

That is correct - or rather approximately correct.  Consider this: The
opening position has 20 moves for white (4 knight moves, 8 pawn moves to
the third rank, and 8 pawn moves to the fourth rank).  Now look at the
ending.  Even a lone queen can produce 28 moves (7 each: rank, file, and
2 diagonals).  It's a safe assumption that in general, the possible
number of LEGAL moves in any given position is greater, so assuming a
worst case, let's say 20 moves in any given position.  For the first 2
whole moves you get:

white moves       20
black moves     x 20
white moves     x 20
black moves     x 20
                -----
                20 ^ 4, or 160,000 moves!

For an average?! game of 40 moves, it's (20*2)^40!

-- Sheldon Mandel

[ Editor: corrected later in the thread by Adam Whiteson, below. ]

I think your program has a small bug -- the static position might allow
a few EP captures, and your flag doesn't say which is *the* one.

My approach would be different:  Since castling flags are only relevant
when the K and one R are on the starting square, I'd count those cases
separately.  The addon is miniscule.  Same general idea for EP, although
I think the addon fraction is in the 10-20% range.

If you are trying to get a good estimate of the actual number of legal
positions, the toughest problem will be accounting for king-in-check-
but-not-his-move.  I'd go for Monte Carlo to estimate this.

-- Richard Schroeppel

> the toughest problem will be accounting for king-in-check-
> but-not-his-move.  I'd go for Monte Carlo to estimate this.

Might it be 50% of king-in-check?

Besides pawns on their own first rank, and both bishops on the same
color, what other guaranteed illegal (or impossible) placements are
there?

Another thought:  depending on how it's coded, a truly minimal board
generator might have lots of special cases to consider.  For example,
"just-moved pawn on own 4th rank with adjacent attacking pawn, attacker
to move" might still not be an EP board if some other piece occupies the
2nd or 3rd rank squares, since that indicates the pawn couldn't possibly
have just moved.

-- Joe Snyder

My estimate of the number of positions to examine to prove a draw or win
is 10^20.  This is based on the heuristic that in a random game you only
need to evaluate moves for one side (the opponent) to prove a strategy.
Note that the world already has this much computing power, although it
isn't yet well connected together.

The other constraint is that the pawn position must be proper.  Besides
no pawns on first rank, there's no pawns on eighth rank.  In addition,
the number of pawn-displaced-files must be less than the number of
captured pieces of each color; and if the capturing involved pawns, they
must either be on possible files, or have promoted.  There are some
corollaries about when a file can have pawns in unusual order - if
nothing's captured, then on every file, the white pawns must be in front
of the black pawn.

This makes me think that the most numerous class of boards are those
with one or two captures and one or two promotions.

There are a couple of other miscellaneous constraints:  If no pawns are
moved, only the Ns can be loose; the total number of elapsed moves must
have the correct parity (only a constraint if no BQKR has escaped).
These only matter in the initial position.

) Might it be 50% of king-in-check?

I don't think it's this high:  You need an enemy N on one of ~7 squares,
or an enemy QRB reasonably close.  Maybe 25%.

Oh, that provides another constraint:  Double check must have a suitable
prior position.  No triple checks.

I guess there's an ambiguity:  Do you want to bother excluding posns
that are not facially illegal/impossible, but couldn't have arisen in a
legal game?

-- Richard Schroeppel

Such as "Garden of Eden" boards, with no possible predecessor?  ...
Yes, I would prefer not including "legal" boards that can't be reached
in play, since they wouldn't be of use in an actual game.  But it seems
like lots of them couldn't just be proven impossible by rules, and could
only be weeded out by exhaustively checking the previous line of play to
see if the board was reachable.

So, here's another attempt at a simple GOE board WITH pieces in "legal"
positions BUT unreachable in a game and WITH no previous moves:  all
pawns and bishops in their original positions, all knights and rooks
gone, white king on white queen's square, white queen on white king's
square, and black's king and queen on their original squares (or
swapped with each other like white).  Can't be reached, and no previous
move.

Take away the bishops and queens, swap the kings to put them behind
enemy lines, and now you have a still-unreachable board but with
possible previous moves by the kings.

-- Joe Snyder

) faster (but larger) first cut at computing a limit, how about treating
) each piece as unique and just using 64!/(64-total_men)! ?

That can be done, of course, but for the single case where there are 32
men alone you would have (64!/32!) arrangements, which is about 4.8 x
10^53.  So your result will be greater.  On the high side, your result
will be less than 555985 * 555985 * 2 * (64!/32!) approx= 2.98 x 10^65.

It seems that even using the long expression above, our estimates will
be quite high.  For example, using the long expression for the case
where we have 3 pawns, 3 rooks, 3 knights, 3 bishops, 3 queens, and 1
king for each side (which of course can't happen in a real game), we
have 64!/(32! 6^10) =~ 7.98 x 10^45 positions.  On the high side again,
we should get fewer than 64!/(32! 6^10) x 555985^2 * 2, which is
approximately 4.93 x 10^57.

-- John Thompson

I estimate that more than 99% of the positions will have more than four
pawns promoted to non-queens.  I'm interested in refining this estimate
so it's only a few orders of magnitude loose.  It's somewhat amusing
that most of the positions are not only not achieved in practice, but
are not even approached.

-- Dan Hoey <hoey@AIC.NRL.Navy.Mil>

Of course you know about this sequence from the Encyclopedia of Integer
Sequences, that ken thompson computed for me:

%I A007545 M5100
%S A007545 1,20,400,8902,197742,4897256,120921506,3284294545,88867026005
%N A007545 Number of chess games with $n$ moves.
%R A007545 ken.
%K A007545 fini
%O A007545 0,2
%A A007545 njas

-- Neil Sloane <njas@research.att.com>

The following game position estimates are well-known:

Chess:    10^43
The estimate 64!/(32!*8!^2*2!^6) ~= 10^43 is given by Shannon in his
seminal paper "Programming a Computer for Playing Chess", Phil. Mag. 41
(1950) 256-275 (also in D. Levy's "Computer Chess Compendium").  As most
everyone knows, we are far from solving the game of chess.

Checkers: 10^18
For checkers, Jon Schaeffer estimates 5*10^20 plausible positions with
10^18 reachable under the rules of the game.  But solving may require
only the square root of the number of positions in the search space
i.e. 10^9.  The trick is finding which 10^9 positions to use.  His World
champion program Chinook has access to all 8 piece databases (444
billion positions).  [source: rec.games.chess.computer 7/17/95].  Thus
there is hope that some day checkers may be solved.

Merrils:  10^10
Merrils (Nine Men's Morris) has been solved.

As might be expected, the number of positions (size of the state space)
is thought to be a good measure of the complexity of these games.  For
further details see the following excellent survey on exhaustive
search:

    ALL THE NEEDLES IN A HAYSTACK:
    CAN EXHAUSTIVE SEARCH OVERCOME COMBINATORIAL CHAOS?
    http://nobi.ethz.ch/febi/ex_search_paper/paper.html

Here's a relevant excerpt:

 Although a direct comparison of different enumeration problems is not
 easy, due to their state spaces of different structure and varying
 connectivity, it is striking that at present, the size of state spaces
 of various solved problems, including Merrils, is of the order of 10^10
 positions.  The empirical fact that the raw size of the state space is
 the dominant parameter that affects complexity might be explained by
 the observation that the structure of all these spaces shows no
 regularity - they appear to be random graphs.  Without predictable
 regularity to exploit, all exhaustive searches look like random walks
 in a random graph.  Thus, the most telling indicator of complexity is
 the size of the space, and its connectivity is second.

Finally I'll leave you with this excerpt:

 Exhaustive search is truly a creation of the computer era.  Although
 the history of mathematics records amazing feats of paper-and-pencil
 computation, as a human activity, exhaustive search is boring,
 error-prone, exhausting, and never gets very far anyway.  As a
 cautionary note, if any is needed, Ludolph van Ceulen died of
 exhaustion in 1610 after using regular polygons of 2^62 sides to obtain
 35 decimal digits of Pi - they are engraved on his tombstone.

-- Bill Dubuque <wgd@martigny.ai.mit.edu>

A related problem to estimating the number of chess positions is to
develop a "legal position recognizer".  Given a board with an arbitrary
population of pieces, (1) determine whether this position could arise
via legal chess moves, and (2) exhibit a sequence of play which will
produce that position.

I once saw an interesting puzzle of type (2), whose pawn structure was
such that it required certain captures, which in turn led (as I recall)
to a unique game score.  In general positions can arise from more than
one score (even excluding single repetitions or three-times repetitions
- not legal).  It might be interesting to estimate the average number of
ways a random position can be attained.  (Then, of course, simply
multiply by the number legal positions to estimate the number of legal
games.)

Enumerating chess positions should also specify the "off board"
information - can either side castle, who moved last, and (sometimes)
was the last move a pawn double move allowing en passant capture.

-- Ken Roberts <ken@mirror.org>

) For an average game of 40 moves, by this approach, the number is
) 20^(40*2) not (20*2)^40.  Now 20^80 = 1.21*10^104 (approx) !!
)
) This counts the number of GAMES but not the number of distinct
) POSITIONS.  We could sum the sequence:
)   20 + 20^2 + 20^3 + ... + 20^80 = 1.27*10^104 (approx)
)
) But many of these positons are the same since different games can
) share the same positions and also the same position can repeat up to
) three

-- Adam Whiteson, as quoted by Sheldon Mandel, who replied "WHOOPS - I
   stand corrected."

My first program that finishes in a reasonable time (essentially
immediately) AND calculates an actual (and admittedly very generous)
limit to the number of possible boards.  The output is 4.54 x 10^54.

If this code is correct, it can be called a proof (not just an
estimate) that the real number of boards is less than 4.54 x 10^54, and
also serve as the starting point for additional code to whittle down
that limit as discussed in previous messages.

Since 64!/(64-i)! is used for placing i pieces, the code ignores
promotions and lets each pawn act as a unique piece, promoted or not.

If at least two opposing pawns are present, ALL arrangements for those
pieces are counted twice:  once for no en passant and once for.

Similarly, if the side to move has rooks, ALL arrangements for those
pieces are counted again once for each rook to assume castling is
possible.

[ Editor: program listing omitted.  An earlier version that left out
  the pawn promotion loops had returned 9.22 x 10^55 boards, "which has
  to be doubled to consider placements by both black and white". ]

-- Joe Snyder

:   64!
: ------
: 32!32!

This is too low as it does not distinguish between differing
arrangements of pieces on those 32 squares.  The correct formula is

           64!
 ---------------------------  =  ~ 2.317 x 10^42
 32!8!8!2!2!2!2!2!2!1!1!1!1!

[ Editor: this quotient is 4.63 x 10^42 (64!/32! = 4.822 x 10^53,
  divided by 8!^2 x 2^6 = 1.0405 x 10^11), as in Komputer Korner's table
  below. ]

Now LEGAL positions excludes all kinds of things like more than one pawn
of the same color on a file when no captures have been made, both
Bishops on the same color with no pawns missing etc.  After pruning
those out and adding in the other 26,243 cases it could possibly be
somewhere in the vicinity of 10^40.

-- Loren Pomeroy <l.pomeroy@m.cc.utah.edu>

Komputer Korner (korner@netcom.ca) wrote:

)  a programme to count all possible distributions. Here are the
)  results: (the first number in each line specifies the number of
)  chessmen which are on the board)
)
)  0  1.00000000000000E+0000
)  1  7.68000000000000E+0002
)  2  2.82240000000000E+0005
)  3  6.60791040000000E+0007
)  4  1.10669791680000E+0010
etc. to
) 32  4.63472669558781E+0042

Komputer Korner points out that the numbers *are* upper bound with no
attempt to distinguish legality.  Legal chess positions become
progressively more difficult to discern as the number of pieces on the
board increase, but this should not constrain us from calculating
*actual* numbers for a small number of pieces.

There are, of course, no positions for zero or one piece.  Assuming that
Black/White and Left/Right are *not* interchangeable (symmetry will only
complicate calculations when more pieces are introduced), for two pieces
(both necessarily Kings), I believe there are 3612 board positions.
Three pieces yield 2127600; and four pieces, 1205537008 *minus* the
number of boards that have both Kings in check.

These calculations were done by hand a number of years ago and I would
not be overly surprised if they were wrong.  I would expect the number
of legal board positions for 32 pieces to be relatively small (nowhere
near 10^42) because of the impossibility of pawns passing each other,
etc., but the actual number might be fiendishly difficult to calculate.

-- Hans Havermann <haha@astral.magic.ca>

Hauke Reddmann wrote:
)
) Let's see: On every rank, there are 15 legal pawn positions.
) 15^8*50^16 (the latter an upper estimate for the rest of the figures)
) less than 10^37 indeed.

Hmmm... pawns don't move linearly when they capture.  There are a lot
more than 15 legal pawn positions per rank.  I'm not sure what you mean
by pawns can't pass each other, but nothing precludes an indirect pass
through a capture...

I think there are 1*3*3*3*3*3*3*1=6561 legal positions per rank,
corresponding to empty/white pawn/black pawn possibilities.  plus you'd
have to take into account promotion of pawns...  dividing it up this way
does not help simplify the problem.

-- Tim Firman <firman@lombardi.chem.wisc.edu>

Hauke Reddmann was calculating an (upper bound) number of legal board
positions when *all* 32 pieces are (still) on the board.  Thus nothing
has been captured.

-- Hans Havermann

Title: Schach und Zahl : Unterhaltsame Schachmathematik
(Chess and Numbers : Entertaining chess mathematics)
Authors: Eero Bonsdorff, Karl Fabel, Olavi Riihimaa
Edition: 3
Year: 1978
Publisher: Rau

-- Robert M. Muth <muth@cs.arizona.edu>, suggesting a book on chess
   enumeration problems

In HAKMEM Problem 95, I gave an estimate of the number of chess
positions, "about 10^40".

(This was a reaction to people who wanted to emphasize how hard it is to
completely search the chess game tree, and quote an old estimate of
10^120 possible games.  Of course you don't have to follow every branch
to evaluate chess:  Even without using Alpha-Beta, you need merely to
assign values to all positions, which can be done with effort (roughly)
#positions * #moves.)

There's an old heuristic estimate of the effort to *verify* a game
value: roughly the square-root of the number of positions.  The
justification is that to check a claimed strategy for, say, forcing a
Black draw-or-better, you only have to examine all possible White moves;
the strategy supplies a single Black move for each position.

The computing power to touch 10^20 positions exists in today's world:
Assume 3 million PCs, one touch/microsecond, one year (10^13.5
microseconds).

If this heuristic is true for chess, then we may expect the game to be
solved in some not-too-distant future -- perhaps within the next
century.

-- Richard Schroeppel

First, worrying about counting en passantability and castling is
niggling. ...  Most position reachability considerations are also down
in the noise, except for check (see below).  Even counting who has the
move is at most a factor of two, which is eventually going to be below
our threshold of estimation.

One thing they did was estimate the number of positions with 32 men on
the board.  My estimate is that placement gets you about
15^8 48! / (32! 2^8), or 10^32.6 positions.  They proposed to rule out
positions with both kings in check.  I think we should also rule out
positions with either king in double check, since almost all such
positions are impossible.  I haven't got a good handle on that
probability; I'm thinking of a computerized case-analysis: Each king
position is attackable on so many diagonals, ranks, files, knights, etc,
and to a first approximation every position is equally likely for
anything except pawns.

For 31-man boards the situation is tougher, but I think most positions
(by far) consist of twelve pawns and nineteen pieces.  Yes, that's
pawn-takes-pawn followed by three promotions.  I make it 10^37.1
positions before check is taken into account.  Lower-order cases like
pawn-takes-piece and two promotions also swamp the positions not
involving promotion.

My guess at the most populous combination over all chess positions is
for each side to have one pawn, three rooks, three knights, three
bishops, and three queens, after losing two pawns each to pawn captures
to make the remaining pawns promotable.  I wouldn't be surprised to find
that Shannon underestimated--his formula doesn't really get serious
about counting promotion.  I suspect making an estimate within a few
orders of magnitude is possible with a computerized case-analysis of
piece population and check-probability.

As I mentioned in the message to Rich last week, the possible positions
are composed of a near-unanimity of wildly implausible positions.  I
think this knocks the square-root-of-the-number-of-positions heuristic
into a much more cocked hat than it started in.

-- Dan Hoey

[ Editor: in a follow-up Hoey withdrew a remark (omitted here) that
  Snyder's program counted castling history as three bits of state. ]

There is another way in which the promotion-counting program is
inevitably flawed, in that it counts positions that contain two original
knights as different from positions with two promoted knights, or one of
each.  I think this ends up overcounting many common implausible
positions by a factor of over 1000.

The final version of the program--which "lets each pawn act as a unique
piece, promoted or not" would produce a better lower bound if each
player were considered to have one king and at most fifteen other men of
five different types (P, R, N, B, Q).  If there are W white pieces and B
black pieces, there would be

    64 Binomial[63,W-1] 5^(W-1) (64-W) Binomial[63-W,B-1] 5^(B-1)

positions, which sums to 6.34x10^50 before castling and en passant is
considered.

There is a sense in which this last program is conceptually incorrect,
in that it undercounts some of the hidden state in three ways:

  1. If a player has two rooks, there are four possible states of that
     player's castling possibilities (queenside, kingside, both, or
     neither), not two.

  2. A player's castling possibilities can affect the future course of
     the game whether or not that player has the move.  Therefore both
     players' castling state is part of the hidden state, not just
     one's.

  3. If there are more than one of the opponent's pawns adjacent to the
     player's sixth rank pawns, then there are more than two possible
     en-passant states.

So the particular board

    BR == .. == BK == .. BR
    == .. == .. == .. == ..
    .. == .. == .. == .. ==
    BP WP BP BP WP BP BP WP
    .. == .. == .. == .. ==
    == .. == .. == .. == ..
    .. == .. == .. == .. ==
    WR .. == .. WK .. == WR

should be counted 112 times, depending on the hidden state (including
whose move it is).

However, I think with a little more effort to count positions of these
types only when the positions of rooks and kings or pawns make them
possible, I believe their total contribution will be reduced to under
40%, instead of about 230% as it is coded now.

-- Dan Hoey

[ Editor: the board is given here as corrected in Hoey's next message;
  his first version was missing a rank. ]

It may be useful to deal with pawn promotions by recording each piece in
terms of its possible locations on the board, with suitable additional
"locations" to allow for capture or promotion or special moves.

For instance, a knight, bishop, or queen can be in one of 63 possible
locations, including "captured", but excluding the two squares with
white and black kings.

White's king can be in 65 possible locations, wherein the king's
original square is counted twice, once for king-has-never-moved and once
for king-moved-away-and-moved-back.  Black's king can be in one of up to
61 locations, excluding the squares adjacent to the white king.

Similarly a rook can be in one of 64 possible locations, counting
original square twice, and also allowing captured, but excluding king
squares.

An unpromoted pawn can be in one of 48 locations on ranks 2 thru 7.  The
8 rank 4 locations can be duplicated again to allow for the situation
"pawn moved there on last move", which is the only situation in which
the pawn might be captured en passant.  Allowing for capture, there are
thus 57 possible locations for an unpromoted pawn.

After the pawn has been promoted to one of 4 possible pieces, it can
move to any of 62 locations.  We can exclude capture since after capture
it does not matter whether the pawn was or was not promoted.  Hence a
promoted pawn has 248 possible locations.

Thus we obtain an upper bound for locating all white's pieces on/off
board of

64*63*63*63*65*63*63*64 * (57+248)^8  locations.

Black's pieces have somewhat fewer king locations, and have an upper
bound of

64*63*63*63*61*63*63*64 * (57+248)^8  locations.

Take the product, and double to include the player to move.

Refinement:  It would be nice symmetry, and a lower value of the upper
bound, to replace 65*61 as the estimate of the number of white and black
king locations, with an actual count of the number of possible locations
of two kings (including counting each king's original square twice).

Apropos of my earlier note, I forgot to count position repetitions.  One
must multiply by 3 to record whether the position has been reached the
first, second, or third times.

-- Ken Roberts

Incidentally, Appendix A of Botvinnik's book Computers, Chess and Long
Range Planning, the preface to the Russian edition, written by N.A.
Krinitskii, discusses an upper bound of the number of chess positions,
covering some of the ground which has been covered in this list.

-- Ken Roberts

> the promotion-counting program
> is inevitably flawed, in that it counts positions that contain two
> original knights as different from positions with two promoted
> knights, or one of each.

I'm taking the position that overcounting is just an indication the
program needs more code or better algorithms for lowering the
calculated limit, while undercounting is a bug.

>   1. If a player has two rooks, there are four possible states of
>      that player's castling possibilities (queenside, kingside, both,
>      or neither), not two.

Isn't it true you can't count "both", because the player can't move
both rooks?  Ie, the tree of subsequent moves has 3 castling branches,
not four:  queenside, kingside, or neither.  A board with two rooks
can't lead to a "next" board with both rooks moved.

>   2. A player's castling possibilities can affect the future course of
>      the game whether or not that player has the move.

I don't think that affects a count of the number of possible positions.
Eg, when looking at a white-to-move board, the number of possible boards
(moves) white can make is unchanged by black's castling state before
white's move.

In any case, I don't think the program is undercounting, since it's
making an extra addition of every possible arrangement for every piece
(even treating all pieces as unique) when en passant is even remotely
possible.  In effect, the en passant logic is treating EACH piece in the
extra arrangement count as a piece making an en passant capture (very
wasteful, but easy to code).

I think it's important a counting program (as opposed to an estimating
program) is modified to lower its calculated limit one "improvement" at
a time, otherwise the logic gets real complicated real fast, bugs creep
in, and the result is no longer provable/guaranteeable.

-- Joe Snyder

I say that from the complete description of a position in any game, you
should be able to verify the set of possible successor positions--
that's what this hidden state is all about.  So from one position the
game tree has branches {o-o,o-o-o,neither}, from another the game tree
has branches {o-o,neither}, from another {o-o-o,neither}, and from
another only {neither}.  They have different sets of legal continuations
so they must be different positions.

I'm sure a puzzle constructor could demonstrate a position in which a
player who can choose which way to castle will win, but being able to
castle only one way is drawn (the opponent can counter either threat but
not both) and not being able to castle is a loss (not needing to counter
either threat, the opponent attacks).

: I don't think that affects a count of the number of possible
: positions.

False.  If black can castle, white may be forced (on this move) to
counter the threat of castling, as above.  They are different positions
because they can force different responses. ...  If we get back to
basics, the possible successor positions (in which you apparently agree
must reflect black's castling ability) are different, so the positions
with white to move must also be different.

Okay, it's true that whenever N en passant captures may be possible, you
count at least 2 N! positions (when there are actually N+1), so you've
got the en passant covered.  But don't forget to multiply the number of
positions you find by each method together.

A more interesting note from Ken Roberts (ken@mirror.org)

] Apropos of my earlier note, I forgot to count position
] repetitions.  One must multiply by 3 to record whether
] the position has been reached the first, second, or
] third times.

leads to a huge increase in the number of positions.  If you want to
represent under what circumstances a draw by repetition is possible, you
need to be able not only to tell if this position is drawn by
repetition, but which of its successors is drawn by repetition, and
their successors, etc.  In fact, you may have to represent which subset
of the ancestors of this position may appear again, and which subset
have appeared twice.

You need to represent ancestors back to the most recent pawn move or
capture.  If we accept a mandatory fifty-move draw (with the usual
exceptional endgames), you need to represent up to the last 100 tempos
in most cases.  With a branching factor of twenty, the number of
positions would be multiplied by 10^130.

If (as I understand the tournament standard) the fifty-move draw is
optional and the repetition draw is mandatory, we have a much harder
problem.  Each set of N mutually ancestral overt positions would have to
be multiplied by 3^(Log[N]/Log[2]).  I believe that would more than
square the total number of positions.

My advice is to give up trying to represent repetitive draw (and
fifty-move draw) possibilities.  They cause an immense blowup of the
number of positions to very little effect.  Personally, I'm much more
interested in counting the number of overt positions, which is even
less relevant to the conduct of the game than this hidden state stuff.

-- Dan Hoey

We need some standardization of terminology for efficiency.  What about
the following:

Board = chessboard with a distribution of pieces on it.  Only what is
visible.  No "state" information.  Does not matter who is to move,
whether could arise in game, etc.

Score = sequence of legal chess moves.

Legal board = board which can arise from following a score.

Position = board, plus state information to say which of the various
hidden attributes pertain: whose move is it, was some pawn on 4th rank
just moved and hence subject to possible en passant capture, which kings
or rooks have never moved.  Also "simple position".

Legal position = position which can arise from following some score or
scores.

Scored position = position which arises from following a particular
score to a particular ply.

Partly scored position = position which arises from following a partial
score, starting from a predecessor position.

Now, this raises the issue of how to talk about repetition.  Encoding of
the repetition-draw-state of a position and its predecessors is really
only meaningful for a partly scored position, where we have the partial
score from a predecessor which goes back to the last pawn move.

What is the objective of the counting exercise?  To determine how
difficult it would be to completely enumerate all chess move-plans,
extending the work done on positions with up to five pieces on the
board?  In that case, especially since one is dealing with endgames, it
is necessary to consider possible draws and "positions" should be partly
scored positions.

Again, for efficiency of investigation, perhaps it would be worthwhile
first to attempt to estimate or bound the number of boards, and the
number of legal boards.

-- Ken Roberts

Joe Snyder wrote:

  With machines now evaluating billions of boards per minute, who
  knows, we might find we're only a few magnitudes from computing
  every board we really ever expect to care about.

Suddenly, we're talking about boards we expect to care about in play.
You know, that's a long, long way from all the legal boards.

Let us consider a variant game, called Chess-B, that acts exactly like
chess, except that Black wins if either he gets three queens at once, or
White gets more than two rooks or knights or gets two bishops on the
same color.  The usual conditions (checkmate, stalemate, etc.) will also
terminate the game with the outcome as in Chess.  It's plain that White
can't do any better playing Chess-B than he can playing Chess.  There's
also Chess-W in which White wins if he gets three queens or Black gets
too many minor pieces, as before.  White can do at least as well playing
Chess-W as playing Chess.  If we score -1 for a black win, 0 for a draw,
or 1 for a white win,

        Chess-B <= Chess <= Chess-W.

Now consider Chess-0, in which any player to get three queens wins, any
player who gets too many minor pieces loses, and is otherwise like
chess.  This is also no worse for White than Chess-B and no better than
Chess-W:

        Chess-B <= Chess-0 <= Chess-W.

Now, I think it's very likely that with optimum play, Chess-B and
Chess-W have the same outcome.  The reason is that in order for the odd
promotion rules to make a difference, either someone is way ahead of the
other (forcing a lot of promotion), or someone is playing to lose
(underpromoting or intentionally letting the opponent's pawns through),
or play reaches one of the very few cases where underpromoting wins, or
multiple promotion can be forced.  And most of those cases will have a
sibling of an ancestor with the same game value, that the losing player
could have chosen instead if he was trying to avoid these problematic
cases.

Now on the hypothesis that Chess-W = Chess-B, we can prove that Chess =
Chess-0 !  So we can consider the Chess-0 positions as the ones we care
about, in which no one ever gets more pieces he never started with,
except possibly a second queen.  Counting these positions is much
easier, and there are many orders of magnitude fewer of them.  Computing
billions of boards a minute, it might take us only quintillions of years
instead of decillions of years.

But I think counting all the legal boards is fun, so I'm sticking with
that.

-- Dan Hoey

I think there's some confusion between what board positions are being
generated for consideration versus what boards to ultimately count.

My first posting said "if a database listed every legal board, how many
database records would there have to be?".

How about if we keep it simple and define the problem like this:

board record =
  squares:  array[1..64] containing one of (0, wp, wr, wn, wb, wq, wk,
            bp, br, bn, bb, bq, bk)
  end record

Solve:  "Starting with pieces in their initial game position, how many
different board records can be generated by making legal moves?"

For the more adventuresome, and to create a more "practical" database,
let's add a score to each record for all possible immediate moves the
board can generate.  With a minimal record like the above, we have to
assume just about any move on the board is possible.  So instead, let's
use a record like:

board record =
  squares:  array[1..64] containing one of (0, wp, wr, wn, wb, wq, wk,
            bp, br, bn, bb, bq, bk)
  playertomove: black or white
  scores:  array[1..possible moves] containing one of (white wins, black
           wins, draw)
  end record

Solve (same problem):  "Starting with pieces in their initial game
position, how many different board records can be generated by making
legal moves?"

Now there are more records in the database to count, but fewer move
possibilities to consider within each record.  (The "scores" are just to
imply a more pragmatic database, and don't have anything to do with the
counting problem.)

We can continue that trend of more-records-with-fewer-choices by
including more state info:

board record =
  squares:  array[1..64] containing one of (0, wp, wr, wn, wb, wq, wk,
            bp, br, bn, bb, bq, bk)
  playertomove: black or white
  scores:  array[1..possible moves] containing one of (white wins, black
           wins, draw)
  square number containing opposing pawn capturable by ep, or 0 if none:
           integer
  movercancastle: set of [kingside, queenside]
  end record

That's about as detailed a record as we'd probably want to try and
count.  Whichever record type anyone cares to choose, if any, is fine
with me.

-- Joe Snyder