Total possible chess positions?

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
AlvaroBegue
Posts: 920
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: Total possible chess positions?

Post by AlvaroBegue » Wed Mar 26, 2014 1:36 pm

John Tromp claims to have a tighter bound of around 10^45.888 : http://homepages.cwi.nl/~tromp/chess/chess.html

Gerd Isenberg
Posts: 2127
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Total possible chess positions?

Post by Gerd Isenberg » Wed Mar 26, 2014 2:02 pm

Ahh, thanks Álvaro - will soon update it.

User avatar
SMIRF
Posts: 91
Joined: Wed Mar 26, 2014 3:29 pm
Location: Buettelborn/Hessen/Germany
Contact:

Re: Total possible chess positions?

Post by SMIRF » Thu Mar 27, 2014 5:40 am

There also has been a simplified estimation, based on a Huffman coding approach: http://www.10x8.net/chess/Zahlen.html

Image

Angrim
Posts: 69
Joined: Mon Jun 25, 2012 8:16 pm
Location: Forks, WA
Full name: Ben Nye

Re: Total possible chess positions?

Post by Angrim » Sat Mar 29, 2014 3:56 pm

ZirconiumX 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
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 the
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 non-empty 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.

Post Reply