Just for my own curiousity (and because this sort of came up in
another thread,) I was wondering if we could figure out a formula to
calculate the total number of possible legal positions on a
chessboard. There are a bunch of criteria to consider, so here are the
ones that I was able to come up with:
A chessboard has 64 squares, 32 black and 32 white.
Both sides must have a king.
Neither side can have more than 8 pawns.
The sum of the number of queens, knights, rooks, bishops and pawns
cannot exceed 15 for either side (think pawn promotion.)
White cannot have any pawns on rank 1, black cannot have any on
rank 8.
Other criteria are more complex: I can't imagine any possible play
resulting in, for example, eight white pawns on rank 5 and eight black
pawns on rank 4.
Can anyone think of more that I've missed? Or derive a general
formula including these (and any additional) criteria that can calculate
the total number of positions?
-mike
Originally posted by AcolyteThose are good ones. I suppose another case would be in the event
More conditions: at most one king is in check; the 'bias' of the
pawn structure (ie number of
double pawns etc) can be no more than the number of pieces the
opposing player has lost.
that all 8 pawns are present with two bishops that they would have to
be on different colored squares.
The idea for posting this in the first place is my assumption that there
exists a finite number of legal positions on a chessboard. Maybe I'm
asking the question in the wrong way. Can any prove that there exists
an infinite number of legal positions?
-mike
I'm sure there must be a finite number of legal positions on a chess board. At first I thought
otherwise in a parallel to language: i.e., there are an infinite number of recombinations of
words to form new utterances. However, language is constrained only by a generative
grammar, and chess is much more constrained than this. If you think that each piece can only
be on one of 64 squares (notwithstanding the constraints already raised in this thread) then
the total no. of legal positions is bound to be constrained to a finite number by this
consideration alone... again, with the language analogy, the possible number of sentences is
not at all constrained by length, you don't have to shoehorn all of the words into 64 possible
slots, and I think this helps greatly in making language infinitely possible....
sorry for the rambling, and I'm aware that this in no way comes even anywhere near a proof
of anything, but it seems intuitively correct somehow 😉
Joe
This problem sounds like it'll take a while. I think I'll start by finding an upper bound (ie
something guaranteed to be an overestimate.) I'll round up the numbers and give the
estimate in brackets.
Suppose we have 32 pieces on the chessboard. Then there are 64 choose 32 ways of covering
squares with them (2*10^18) . Two of these are the kings, so we have 32x31 (700) ways of
putting these on the covered squares. Then we have 8 pawns for each player, so we have 30
choose 8 for White and 22 choose 8 for Black (6*10^7, 320000). But these pawns could each
be in one of 6 states (promoted to one of 4 things, unpromoted, captured), so that gives a
further 6^16 (3*10^12) possibilities. Now among the remaining 14 pieces, we have three
kinds of piece occurring twice, so we get 14!/8 (1.1*10^10) ways of arranging them
(eliminating ones where two alike pieces are swapped around.) But any of these could have
been captured, so we have to multiply by 2^14 (17000).
Multiplying all these rounded up numbers together, you get around 10^57. So at least we
know the real answer isn't THAT big. 😉
there are probably ways to reduce this maximum drastically (bishops can only be on half the squares etc....). But first there are a
few things that make the maximum greater:
- it makes a difference in position if a fysical configuration has reoccured 0, 1 ot 2 times before
- the number of moves before without capturing or moveing pawns also affects the 'position'
- castling still possible or not
just to name a few.
Gilbert
Originally posted by AcolyteOuch!! That's a huge number of positions, enough to trouble even a
This problem sounds like it'll take a while. I think I'll start by
finding an upper bound (ie
something guaranteed to be an overestimate.) I'll round up the
numbers and give the
estimate in brackets.
Suppose we have 32 pieces on the chessboard. Then there are 64
choose 32 ways of covering
squares with them (2*10^18) . Two of these are t ...[text shortened]... ers together, you get around
10^57. So at least we
know the real answer isn't THAT big. 😉
massive supercomputer. I wonder if it would help to start with the
absolute simplest case: each side has one king only. In that case,
the two pieces could be anywhere on the board except adjacent to
each other. So starting with the first king, it could have 64 possible
positions. If that king is in a corner, then there are 60 possible
positions for the other king. If the first king is along an edge but not
in a corner, then there are 58 possible positions for the second king.
If the first king is not on an edge, then there are 55 possible
positions for the second king. Giving a total of either 124, 122 or 119
possible positions.
-mike
Originally posted by sintubinI didn't think of those... make that 10^60 then.
there are probably ways to reduce this maximum drastically (bishops can only be on half
the squares etc....). But first there are a
few things that make the maximum greater:
- it makes a difference in position if a fysical configuration has reoccured 0, 1 ot 2 times
before
- the number of moves before without capturing or moveing pawns also affects the 'position'
- castling still possible or not
just to name a few.
Gilbert
Originally posted by Acolyteso now we could perhaps try to get the number down:
I didn't think of those... make that 10^60 then.
- two white rooks , when both on the board can be interchanged
without changing the position; same with black ones, same with
knights
- promotion to knights and rooks will give the same "duplication"
- a big one, bbt a problem on its own: no position is allowed where
both kings are in chess
- a king can not be 3 or more times in check in one position (is that
certain?)
etc... this is getting out of hand.
Lower bound (rounding down this time)
Assume no promotions.
Pieces that have been captured are seen as being on 'dead' squares off-board
Pawns: each file 8 choose 2 = 28 -> 28^8 (allowing for 'dead' squares)
I'm assuming that each player has at most one pawn on any file, and that they're standing
facing each other, so no choice of order.
Say White King is not in check, so could be in one of 34 places (64 -(16 + 14))
Black King is not next to White King, so 64 - 16 - 9 = 39.
So far we have about 5*10^14.
Say Black King is not being attacked by non-pawns: this rules out up to 14 squares for
orthogonally and 13 for diagonally movable pieces. So:
White Queen has 65 - 18 -14 - 13 = 20
White Rooks have 66 - 19 - 14 = 33, that choose 2 = 528, -1 for alternate use of 'dead'
squares
White Knights have 66 - 21 - 8 = 37, that choose 2 = 666, -1 for same reason
Similarly
Black Queen has 65 - 23 - 14 - 13 = 15
Black Rooks have 66 - 24 - 14 = 28, that choose 2 = 378, -1 = 377
Black Knights have 66 - 26 - 8 = 32, that choose 2 = 496, -1 = 495
Total for this section: about 1.9*10^13
Some positions counted might be impossible due to strange circumstances involving check and
stalemate, but I don't think there are very many of these.
So my second crudely calculated estimate is 9.5*10^27, and this time I'm pretty sure it's an
underestimate.
PS I've ignored Bishops because they get a bit complicated.
