Hello to everybody, I would like someone who knows maths or is fond of maths (specially combinatorics) to tell me whether this calculation of how many chess positions are possible on the board is correct.
The board has 64 squares and there are 32 pieces. All of the possible combinations among the pieces is 32! and we only need 32 squares, therefore, the total number must be given by this formula: 64!*32!/(64-32)!=Total possible positions
By the way, there hare thousands of positions that are basically the same, so my formula doesn't consider each piece completely different from its equivalents. The "real" number is lower.
Your comments and corrections will be very much appreciated.
I was thinking about this too, and while that formula works well, it doesn't exclude illegal cases of for example the two kings being on adjacent squares or one player having 2 bishops on the same coloured squares or pawns on the first and eighth ranks. Any idea on how many positions these conditions would eliminate?
en.wikipedia.org/wiki/Shannon_numberSee the second paragraph. You can probably find his working somewhere
Edit: There's an edit feature now? Awesome
Thanks for that... I thought somebody might have got there before us.
Mmm that's a good point mCoomber314. And Shannon's formula makes a lot of sense. 64!/32!*8!^2*2!^6. 8!^2 stands for the pawns and 2!^6 stands for the the pair of rooks, bishops and knights I guess. But I don't know why 64! is being divided by (8!^2*2!^6).
(32!(64!)) + (31!(64!)) + (30!(64!)).....+ (2!(64!))
Just add them all up after you've done it for every number between 2-32.
After a quick Google I found that people at
Chess.com have asked the same question, but nobody explains how Shannon's number was calculated... it's quite a long thread.
www.chess.com/forum/view/general/how-many-different-chess-positions-are-thereWe also have to consider the positions that can arise after a pawn or multiple pawns got promoted. Just imagine 18 queens on the board!
There are a few things you have to include in addition to what's been mentioned so far, namely castling rights and whether/where en passant is possible.
Most attempts at specifying an upper bound on the number of chess positions approach the problem from a different angle. Particularly, they try to figure out what the most efficient encoding scheme is for the state of the board, and the number of bits used in the worst case provides an upper bound.
The most efficient attempts are usually around 160 bits in the worst case, which works out to a bit bigger than Shannon's estimate for number of positions (around 10^46 instead of 10^43).
As a side note "Shannon's number" is usually used to refer to his estimate for the complexity of the game tree, not the number of positions.
Accounting for things like illegal positions would definitely cut down on those estimates, but it's difficult to say how much (although one could obtain a rough estimate by picking an encoding scheme and randomly generating thousands of positions, and seeing what percentage were legal).
That difficulty is one of the reasons true estimates are difficult to find; more commonly you'll see upper bounds offered, since those are safer to compute.
It's complicated further by the presence of some positions that aren't blatantly illegal, but on reflection could not arise from any sequence of legal moves.
There are devilishly complicated examples (often examined along with things like retrograde puzzles, or other "Chess Puzzles of Sherlock Holmes" type things), but a simple example would be this:
k7/1P6/KN6/8/8/8/8/8 b - - 2 1
This position could never actually arise, because whatever white's previous move was, black would have to have already been in check.
We could conceivably put in a rule that disallows positions with check being given by both a knight and pawn, since those can't happen.
Some aren't so easy for an automated computation, though, like this:
k7/2B5/KN6/4Q3/8/8/8/8 b - - 2 1
It's mate, so obviously white's last move must have been Nb6. Equally clearly, black's last move must have been Ka8.
But where was the black king before it moved to a8? It couldn't have been a7 or b7, since the white king is there.
However, it equally well couldn't be b8, as a quick reductio shows. Assume it had been on b8. Then what was white's previous move?
Since both the queen and bishop control b8, whatever white's move was, the black king on b8 would have been in check with white to move. That is illegal, so it couldn't have been on b8.
However, a7,b7,and b8 are the only squares from which it could get to a8, so if none of them are possible, the position cannot be legally obtained.
Accounting for those sorts of positions is nearly impossible in a purely mathematical calculation of the number of positions, so again, most people fall back on calculating upper bounds instead of estimates.
As to the actual calculation in the original post, there is a trick you haven't accounted for, which wargzel alluded to.
You have pawns that can become a different piece, and that matters. A black pawn on f5 is very different than a queen on f5, even when that queen is the same pawn after promotion.
That pawn can't just be treated as the "nth" piece of 32, then.
As you can imagine, there are lot of other caveats in these calculations, and they're a lot of fun to work through (well, for some people). :)
Cheers!