- 10 Dec '02 21:32Just 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 - 11 Dec '02 04:06

Those are good ones. I suppose another case would be in the event*Originally posted by Acolyte***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 - 11 Dec '02 15:34I'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 - 12 Dec '02 00:13This 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. - 12 Dec '02 13:05there 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 - 12 Dec '02 16:32

Ouch!! That's a huge number of positions, enough to trouble even a*Originally posted by Acolyte***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 - 12 Dec '02 19:18

I didn't think of those... make that 10^60 then.*Originally posted by sintubin***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 - 12 Dec '02 19:28

so now we could perhaps try to get the number down:*Originally posted by Acolyte***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.

- 13 Dec '02 00:01 / 1 editLower 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.