Number of Possible Chess Configurations

Jump to forum:
« Previous | 1 2 3 4 5 | Next » | Last Post
3rd February 2009, 08:49pm
#1
by rickyk586
Rochester United States
Member Since: Feb 2009
Member Points: 5

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!

3rd February 2009, 08:51pm
#2
by HotFlow
KL, Malaysia Malaysia
Member Since: Sep 2007
Member Points: 1840

12

4th February 2009, 04:35am
#3
by artfizz
South (GMT) +rT United Kingdom
Member Since: May 2008
Member Points: 3108

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.

4th February 2009, 04:53am
#4
by elcabesa
Firenze Italy
Member Since: May 2008
Member Points: 458

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.

4th February 2009, 05:01am
#5
by NM Zug
Central Florida United States
Member Since: Feb 2008
Member Points: 746

I had some fun with this on Chess.com:

"Is Chess Infinite?"

- Zug

4th February 2009, 05:19am
#6
by artfizz
South (GMT) +rT United Kingdom
Member Since: May 2008
Member Points: 3108
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?

4th February 2009, 05:44am
#7
by elcabesa
Firenze Italy
Member Since: May 2008
Member Points: 458

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

4th February 2009, 06:35pm
#8
by rickyk586
Rochester United States
Member Since: Feb 2009
Member Points: 5
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)?

4th February 2009, 06:48pm
#9
by shleena
Sheffield United Kingdom
Member Since: Feb 2008
Member Points: 50

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

4th February 2009, 06:53pm
#10
by Eniamar
Ohio United States
Member Since: Mar 2008
Member Points: 328

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)

4th February 2009, 07:03pm
#11
by bart225
kelowna bc Canada
Member Since: Dec 2007
Member Points: 221

Way over my head .

4th February 2009, 07:10pm
#12
by thegab03
on the road to nowhere! Ireland
Member Since: Nov 2007
Member Points: 16969

You are on about permutations?

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

4th February 2009, 08:17pm
#13
by rickyk586
Rochester United States
Member Since: Feb 2009
Member Points: 5
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).

4th February 2009, 11:24pm
#14
by elcabesa
Firenze Italy
Member Since: May 2008
Member Points: 458

my math skills are good, but I'm not the best with combinatoric math.  :)

4th February 2009, 11:48pm
#15
by joetheplumber
The White House United States
Member Since: Nov 2008
Member Points: 305
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.

5th February 2009, 12:32am
#16
by artfizz
South (GMT) +rT United Kingdom
Member Since: May 2008
Member Points: 3108
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.

5th February 2009, 02:02am
#17
by RosarioVampire
Singapore
Member Since: Jan 2009
Member Points: 227

but why? if the pawns could promote..

5th February 2009, 02:17am
#18
by artfizz
South (GMT) +rT United Kingdom
Member Since: May 2008
Member Points: 3108
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.

5th February 2009, 02:32am
#19
by Tompump
London International
Member Since: Apr 2008
Member Points: 18

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.

5th February 2009, 02:54am
#20
by cuendillar
Stockholm Sweden
Member Since: Jan 2008
Member Points: 811

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.

« Previous | 1 2 3 4 5 | Next » | Last Post

Add your comment:

Join Chess.com for free to add your comment! Already a member? Then login now to comment.