Number of Possible Chess Configurations

rickyk586

I'm not sure if this is the right place to post the question.

How many ACTUAL chess board configurations are their?  I HAVE been able to find sites with answers to this question that include boards with extra pieces (like a board full of white Kings) (http://ioannis.virtualcomposer2000.com/math/EveryChess.html), but this is not what I am asking.  There can not be extra pieces.

It is OK, however, if one or more of the board configurations in the answer would be impossible to get to in a normal chess game.

So, to sum up:
- Total number of possible chess board configurations.
- Using at most 1 King, 1 Queen, 2 Rooks, 2 Knights, 2 Bishops, and 8 Pawns. (black and white).
- Some Impossible boards are OK (such as a board with no black king, or any board that could never happen in a normal game.  Even boards with overlapping pieces would be OK I guess, although not preferred).

BONUS: If you can exclude impossible boards in the answer, more power to you!

artfizz

Various numbers get bandied about. 10120 seems to crop up a lot.

As far as I can see, 1364 (Fermat's Last Pizza) ought to be the upper bound (that's about  1071  ) - and that includes boards with way too many pieces.

This thread - http://www.chess.com/forum/view/general/how-many-different-chess-positions-are-there - discussed an approach for calculation based on enumerating sets of valid pieces (e.g. 2 pieces: 2 kings; 3 pieces: 2 kings + white pawn; 2 kings + black pawn; 2 kings + white bishop, etc.) all the way up to 32 pieces.

Ziryab wrote: If you google "chess position statistics," you should find the website of François Labelle at UC Berkeley who is working on computer modeling and mathematics and has an interest in chess. You'll see that he is carrying Claude Shannon's research much further.

According to Labelle, there are no more than 1050 distinct board positions.

artfizz
elcabesa wrote:

give each piece a name or a numver, you'll have 32 different pieces on the board.

you can put the first piece on  one of the 64 squares, the second in one of the remainng 63 squares etc

the result is

64*63*62*...33*32

=64!/31!

1.27e89/8e33= 1.58e55

 

but i'm not considering pawn promotion and as already told i'm counsidering each pawn different from another.


You're also only considering using ALL 32 pieces. What about positions with fewer than 32 pieces?

rickyk586
elcabesa wrote:

you are right

so a better solution is sum of all combination with 32 pieces + 32 *sum of all combination with 31 pieces + 32^2 *sum of allcombination with 30 pieces etc.. +32^31 sumof all combination with 1 pieces

wow

64!/32! +32 *64!/33!+ 32^2*64/34!+.. +32^31*64!

= 64!/32!* (1+32/33+32^2/(33*34) + 32^3/(33*34*35)+....+ 32^31/(33*34*35*...*64))

=4.8e53*(1+0.97+0.91+0,83+0.74+0.65+0,57+...)

=(circa) 5e54

I hope

the number is far from perfect.. but it's near other approximation


I think I understand... but could you figure it out without considering each pawn different from each other (and the other pieces)?

shleena

i've seen it written in some chess books, and some chess blogs (the questions arise thus - "with all of the top players, isnt it just now a matter of memory?") ...that after about move 8, the positions grow so rapidly that by the middle game the possibilities outnumber the atoms in the universe

Eniamar

Zug's article is a very fun read, however some quick research shows 10^50 as a lower bound on the state-space complexity of chess, aka the number of legal positions.

The game tree complexity is indeed Shannon's number, 10^120 which is all possible positons.

Note that Go's game tree complexity is somewhere in the neighborhood of 10^360, which is fantastically larger, though this could possibly be due to the average Go game length being nearly twice that of a chess game. (80 vs. 150)

bart225

Way over my head .

thegab03

You are on about permutations?

If so, one can not calculate untill a given place of stay!

rickyk586
Eniamar wrote:

Zug's article is a very fun read, however some quick research shows 10^50 as a lower bound on the state-space complexity of chess, aka the number of legal positions.

The game tree complexity is indeed Shannon's number, 10^120 which is all possible positons.

Note that Go's game tree complexity is somewhere in the neighborhood of 10^360, which is fantastically larger, though this could possibly be due to the average Go game length being nearly twice that of a chess game. (80 vs. 150)


But these numbers include boards with more pieces then there really are (like 64 Black Kings).

joetheplumber
elcabesa wrote:

you are right

so a better solution is sum of all combination with 32 pieces + 32 *sum of all combination with 31 pieces + 32^2 *sum of allcombination with 30 pieces etc.. +32^31 sumof all combination with 1 pieces

wow

64!/32! +32 *64!/33!+ 32^2*64/34!+.. +32^31*64!

= 64!/32!* (1+32/33+32^2/(33*34) + 32^3/(33*34*35)+....+ 32^31/(33*34*35*...*64))

=4.8e53*(1+0.97+0.91+0,83+0.74+0.65+0,57+...)

=(circa) 5e54

I hope

the number is far from perfect.. but it's near other approximation


yes, but in all fairness there really are only 12 pieces, since all but king and queen have another.

artfizz
joetheplumber wrote:
yes, but in all fairness there really are only 12 pieces, since all but king and queen have another.

Only 12 distinct pieces - but it's better to use the number 13 in calculations, so that empty squares are included.

RosarioVampire

but why? if the pawns could promote..

artfizz
RosarioVampire wrote: but why? if the pawns could promote..

There are a maximum of 32 pieces on a chessboard, and a minimum of two pieces. When counting board positions, you also have to take into account that a square may be unoccupied.

Many board positions are duplicates, since the pieces are duplicated. In order to count DISTINCT positions, one uses the count of distinct pieces (i.e. 12 + empty). Promotions don't alter the number of distinct pieces. In mathematical terms, we would be counting combinations.

To count all board positions, including duplicates, one counts the pieces including duplicates (i.e. 32 + empty). In mathematical terms, we would be counting permutations.

Tompump

I took out my wooden set and board and have started on the problem. will post the answer as soon as I finish.

PS. Admin- can u pls. extend my vacation time for me to complete this, thanks.

RetGuvvie98

there must be a lot of folks with 'not enough work to do' that they have time to peruse this post, ponder it, and speculate (some actually based on sound reasoning), on the total number of possibilities in chess.

    I'm not enough of a mathematician to comprehend entirely, but this does make a fun read.

 

I am curious though, as Eniamar wrote that the average length of a chess game is 80 moves and average length of a GO game is 150 moves.

What is the source of those two numbers??  

 

not to change the subject of this forum, but simply to ask:  what is the source of those numbers, and if the chess 'average # of moves' is wrong, then is the average listed for GO also wrong??

artfizz
cuendillar wrote:

Under those stipulations the problem isn't all that hard. For all 32 pieces it is 63!/(32!*8!*8!)=4.63*10^42 unless I've made a mistake in the calculations. The rest will take a little longer to work out but I'm working on it. My number is lower than the others as I've took into account that all pieces aren't different.

PS: 63 is not a typo.

It's a lot harder than you might think to count LEGAL positions. With 32 pieces, your calculations can make sure the right set of pieces is on the board i.e. 2 kings, 16 pawns, etc. However, there are a number of additional constraints such as: two kings must not occupy adjacent squares; white pawns cannot occupy the 'a' rank.


RetGuvvie98
artfizz wrote:
cuendillar wrote:

Under those stipulations the problem isn't all that hard. For all 32 pieces it is 63!/(32!*8!*8!)=4.63*10^42 unless I've made a mistake in the calculations. The rest will take a little longer to work out but I'm working on it. My number is lower than the others as I've took into account that all pieces aren't different.

PS: 63 is not a typo.

It's a lot harder than you might think to count LEGAL positions. With 32 pieces, your calculations can make sure the right set of pieces is on the board i.e. 2 kings, 16 pawns, etc. However, there are a number of additional constraints such as: two kings must not occupy adjacent squares; white pawns cannot occupy the 'a' rank.



good point, Artfizz,  but also, don't forget, while you cannot place two kings on adjacent squares; since you cannot place a king where it can be captured by any other piece, that will significantly reduce the remaining possible positions as well.

  I suspect that those who establish calculations for 'maximum' number of positions ignore those stipulations and just look at physically possible positions, not the number of possible "legal chess" positions.

also, you would have to reduce the positions by those that - for instance - have all of one side's 8 pawns lined up on two adjacent files as that isn't "legal chess" possible if the opponent's other pieces and pawns are on the board as well.  For every pawn that changes to a different file, you would have to remove something from the opponent's side.

artfizz
RetGuvvie98 wrote:
 ...  but also, don't forget, while you cannot place two kings on adjacent squares; since you cannot place a king where it can be captured by any other piece, that will significantly reduce the remaining possible positions as well.

  I suspect that those who establish calculations for 'maximum' number of positions ignore those stipulations and just look at physically possible positions, not the number of possible "legal chess" positions.

also, you would have to reduce the positions by those that - for instance - have all of one side's 8 pawns lined up on two adjacent files as that isn't "legal chess" possible if the opponent's other pieces and pawns are on the board as well.  For every pawn that changes to a different file, you would have to remove something from the opponent's side.


Calculating the number of legal positions with JUST 2 KINGS on the board is instructive. One approach to counting TOTAL legal positions is to start by counting physically possible positions (say 1050 ) and then subtract positions which are invalid, for the types of reasons you mention.

The 2 kings case illustrates many of the difficulties of the overall problem: duplicated positions; the chessboard lacks rotational symmetry; context information (in this case: just checks - but in the general case: pawn position invariance, en passant, castling, promotion, captures, white moving first).

RetGuvvie98

cuendillar,

 

you cannot have pawns promoted unless there are fewer than 16 remaining opponent piece/pawns total.  because all pawns are opposed by a pawn - none can 'queen' unless something is captured, and that will drastically change the number of possible positions

 

(or will it?  heck, I don't know, this is straining my neurons.  I need to find a kid who needs an old guy to take him fishing - now there is an enterprise worth my time - matching wits with a fish while getting outdoors with a kid whose parents are both working and the kid needs someone to sit with and observe how to match wits with a fish.  and while waiting for the fish to bite, we might just play a game of chess.)

 

I am not a statistician.  probably that is why I'm thinking of going fishing.

 

maybe GM Larry Kaufman will weigh in on this topic. (the statistical part, not the fishing part).   He is a statistician.

RetGuvvie98

my head hurts.  I'm going fishing.