Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If you play a standard chess game on a normal $8 \cdot 8$ chess board with the usual rules: How many different "board representations" can exist?

Upper bound: Well, you have 16+16 = 32 chess pieces and 64 fields, so $\frac{64!}{32!} \approx 4.8 \cdot 10^{53}$ is an upper bound. This would mean that all chess pieces are distinguishable (e.g. white knights are not distinguishable) and you can distribut them freely accross the field (white pawns can never be in the first row).

Lower bound: If you look only at the pawns, you can imagine them as a number in base 3 (they can not move, move one in front or move two in front). You have 16 pawns, so $3^{17} \approx 1.3 \cdot 10^8$ is a lower bound.

I would also be happy with the number of different game situations (which is higher, as you might care of the possibility of castling, promotion or capture).

I guess the explanation will not be easy, so please provide a source.

share|cite|improve this question
7  
We will probably never know the exact number, even by computer search - I think the only fully reliable way to demonstrate that a position is legal is by proof game. There are positions in which it is tricky enough to determine legality that there is a type of puzzle based on this idea, frequently called a retrograde analysis study. janko.at/Retros/index.htm has some examples. en.wikipedia.org/wiki/Shannon_number provides some estimates. – David Spencer Jul 12 '12 at 11:31
5  
Oh, and although your upper bound is probably above the actual number, it doesn't seem to take into account promotions or captures. – David Spencer Jul 12 '12 at 11:43
    
Game situations are not only governed by the moves possible by the pieces(e.g. castling or en passant capture)but also by the the 3-fold repetition rule, the 50-move rule, and the insufficient-material rule. See FIDE.com – user254665 Feb 19 at 20:50

$\left(56^{16}\times2\right)^2 =$ number of possible outcomes, right?

Each row of pawns can be in every place except the first row, so I thought of it as $4$ separate superimposed boards where the first two rows of two of the boards were removed [because pawns can't travel backward] then I multiplied the number of board-spaces to the 16th power because that's the number of states that a given board-square can be in at any given time, then I squared the answer to account for the fact that pieces can go missing overtime [because that's how you play].

These are my first thoughts however, it may also be the sum of $\left(56^8\times2\right)^2$ and/plus $\left(64^8\times2\right)^2$. I'm trying to approach it as an information theory problem (like an integrated circuit) but instead of bits-per-chip I'm trying (and probably failing miserably) to read it as board-square/board-space_states_per_board, it's particularly challenging because half of the pieces [plus horses and bishops (Bishops or, maybe castles? The "diagonal moving dudes")] are restricted to never being able to reach certain spaces, so if we could: subtract those from that piece's version of the board; think of the board as a binary data equation where each valid board-square was considered as being able to be in one of 3 states (yours the enemy's, or empty); add that data to equations that had those piece-states removed from them, and then subtract one from the total [because there will always be one piece left: therefore: meaning that the outcome where all spaces are empty is invalid]

-Hope this helps. I for one: would also like to solve this mystery.

share|cite|improve this answer
    
I have a bad memory, so sorry if I offended any chess experts, up there. Also: I was hoping to Jog new ways of thinking. If someone could correct my reason to make it more accurate/rational/correct then I will shorten my answer, so as to make it more helpful. It may not seem like a complete answer, but it is, it's just an answer that could use improvement. – Ian Dec 20 '15 at 1:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.