In the solving chess kickstarter topic I posted a rough figure for the total possible (not necessarily legal) chess positions, that of 3.837824955509396e+78 possible positions.
A friend of mine got the figure of 1.9605347643076107e+71 by doing 13^64 (each square of the board can be in one of 13 different states  6 white pieces, 6 black pieces and being empty).
Since my maths are evidently off, what is the actual figure?
Matthew:out
Total possible chess positions?
Moderators: hgm, Harvey Williamson, bob
Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.

 Posts: 1327
 Joined: Sun Jul 17, 2011 9:14 am
Total possible chess positions?
Some believe in the almighty dollar.
I believe in the almighty printf statement.
I believe in the almighty printf statement.
 hgm
 Posts: 23004
 Joined: Fri Mar 10, 2006 9:06 am
 Location: Amsterdam
 Full name: H G Muller
 Contact:
Re: Total possible chess positions?
Your math was off because of several reasons. One was that you did not take account of permutation of the pieces. With one piece you have 6 types, but with two pieces you don't have 6*6 combinations, but only 21, since BN would be the same as NB, etc.
13^54 obviously also is a huge overestimate, as you don't have 64 pieces.
For an accurate estimate you would have to take account of the fact that Pawns cannot be on 1st or 8th rank, and that many Pawn structures are unreachable. (E.g. eight white Pawns on a7h7, eight black Pawns on a2h2.) Without worrying about the reachability, the number of Pawn structures (with all Pawns) would be 48*47*46*...*33/(2*3*4*5*6*7*8 * 2*3*4*5*6*7*8), where the denominators take care of the fact that when you exchange Pawns of the same color, you won't get a different position.
13^54 obviously also is a huge overestimate, as you don't have 64 pieces.
For an accurate estimate you would have to take account of the fact that Pawns cannot be on 1st or 8th rank, and that many Pawn structures are unreachable. (E.g. eight white Pawns on a7h7, eight black Pawns on a2h2.) Without worrying about the reachability, the number of Pawn structures (with all Pawns) would be 48*47*46*...*33/(2*3*4*5*6*7*8 * 2*3*4*5*6*7*8), where the denominators take care of the fact that when you exchange Pawns of the same color, you won't get a different position.

 Posts: 2113
 Joined: Wed Mar 08, 2006 7:47 pm
 Location: Hattingen, Germany
Re: Total possible chess positions?
Shirish Chinchalkar has determined a statespace complexity of 10^46 as upper bound for the number of reachable chess positions
Shirish Chinchalkar (1996). An Upper Bound for the Number of Reachable Positions. ICCA Journal, Vol. 19, No. 3, pp. 181183
https://chessprogramming.wikispaces.com ... s%20Maxima
Shirish Chinchalkar (1996). An Upper Bound for the Number of Reachable Positions. ICCA Journal, Vol. 19, No. 3, pp. 181183
https://chessprogramming.wikispaces.com ... s%20Maxima

 Posts: 913
 Joined: Tue Mar 09, 2010 2:46 pm
 Location: New York
 Full name: Álvaro Begué (RuyDos)
Re: Total possible chess positions?
John Tromp claims to have a tighter bound of around 10^45.888 : http://homepages.cwi.nl/~tromp/chess/chess.html

 Posts: 2113
 Joined: Wed Mar 08, 2006 7:47 pm
 Location: Hattingen, Germany
Re: Total possible chess positions?
Ahh, thanks Álvaro  will soon update it.
Re: Total possible chess positions?
There also has been a simplified estimation, based on a Huffman coding approach: http://www.10x8.net/chess/Zahlen.html
Re: Total possible chess positions?
I don't have a complete answer, but some additional considerations. If you are just looking at the positions of the pieces we can reduce theZirconiumX wrote:In the solving chess kickstarter topic I posted a rough figure for the total possible (not necessarily legal) chess positions, that of 3.837824955509396e+78 possible positions.
A friend of mine got the figure of 1.9605347643076107e+71 by doing 13^64 (each square of the board can be in one of 13 different states  6 white pieces, 6 black pieces and being empty).
Since my maths are evidently off, what is the actual figure?
Matthew:out
number greatly from your friend's estimate, since most of the squares are empty. Start with a bitmap of which squares are empty(64 bits, no more than 2^64 possible values)
then for the nonempty squares you have at most 48 squares that have something on them for 12^48 possible values. so 2^64 * 12^48 possible positions.
You can reduce it a lot further using facts such as there are no more than 16 pieces of each color, and only 1 king on each side.
But then there is the fact that a chess position is more than just the position of the pieces, the history also matters. 50 move rule and
triple repetition both depend on it. When you take those into account, the number of unique positions gets a whole lot larger.