Combinatorics in chess.

2 #1
I think you are wrong. Some positions are not possible under the rules of the game. Other positions can not be obtained during the game :)

TBH, there only 1-2 moves per position. It would be cool to figure out the total number of moves but I'd rather focus my attention now to finding the best move in each position. I think I personally have more to gain doing that. I guess you could figure out how many positions are on a 3x3 with only 6 or 12 total pieces and once you cracked that then take that equation and translate it to a 8x8 matrix with 32 pieces. Figure out how many positions can come from a tic tac toe game and go from there... shannon's number may not be valid and take it upon yourself to figure it out. When I posted my opinion I was just think about pictures of chess position in my head. Prolly wrong idea of thinking but it's up to you all to prove it!

#10: @OneOfTheQ
Your second example is wrong, position is legal. You forget uncaptures. White's last move could have been a knight capture, or upon retracting -1. Nc4 Kb8 -2. Bd6x*c7, the position is clearly legal.

A simple working illegal position would be:
k7/1Rp5/pp6/1K6/8/8/8/8 w - -

Of course you have more complicated illegal positions like this (which is still very, very easy to figure out):
6Bk/4pP1N/6KN/6p1/8/8/8/B7 b - -

More difficult ones would be into the realm of retros proper (Smullyan's Sherlock Holmes book is only the tip of the iceberg... there be dragons down the rabbit hole.)

@Illion: Fair. That's what I get for trying to quickly throw together an example on my own instead of just using a known position. :)

At any rate, the point stands. There are positions that could not arise from any legal sequence of moves, and accounting for them is basically impossible in any purely mathematical attempt to estimate the number of possible positions in chess.

Cheers!

And the kings can never be on a square next to each other as well. all your pawns can not be on a single row. or could they?

I still think the "easiest" way to find the number of legal positions is the game-tree method eg 20 first moves for both sides = 400 possibilites... and then things get a bit out of hand. I have often wondered how big a 32-piece tablebase would be, and how long it would take to generate - I think I read somewhere that even with the current best supercomputers working together it would take longer than the estimated lifespan of the universe thus far (13+ billion years). So - not easy at all, but easier to understand (for me at least) than the "Shannon number minus loads of illegal cases" method.

@mCoombes314: It's easier to understand conceptually, certainly.

The impossibility of currently implementing it is a slight mark against it, however :)

Of course, that's not a huge issue, since computing an upper bound and removing illegal positions is also not possible to implement right now.

It's just that at least there you get the upper bound as reward for your work :)

Another interesting empirical method of estimating would be to have a legal move generator play out random games constantly, recording all the unique positions.

At first, nearly every position would be unique. Over time, though, the rate of addition of new positions would slow. After letting the process run for a decent amount of time, you could then plot the count of unique positions vs time, and compute the limit for the function(s) that best fit, which would probably be a decent estimate.

It would also require substantial storage, but nothing like effectively computing all of the 8-32 piece tablebases.

The practical concern there is that you might not see much slowing until you outpaced current storage limitations (to guarantee no collisions, you'll need about 160 bits per position, which "only" gives you about 50 billion positions per TB, which is a much, much smaller number than any currently computed upper bound), and once a gargantuan amount of data had been stored, the check to see whether a position had already been reached would be very expensive.

The upshot is that chess is pretty complicated :)

Just a note: it is not illegal to have two bishops on the same colored square, as someone up-thread mentioned. Promoting to a bishop allows this.

Agreed, my method is very flawed :p. I like your estimation method at #17, but again this mainly shows the limitations of current technology. We'll just have to see how long Moore's Law can stay true for...

Also, a lot of the chess positions computed would be positions that would be almost impossible to reach in an actual game. eg 18 Queens on the board, in all of their respective positions. Same for 20 knights or bishops etc