Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. Donation legionnaire
    Free Thinker
    10 Dec '02 21:32
    Just for my own curiousity (and because this sort of came up in
    another thread,) I was wondering if we could figure out a formula to
    calculate the total number of possible legal positions on a
    chessboard. There are a bunch of criteria to consider, so here are the
    ones that I was able to come up with:

    A chessboard has 64 squares, 32 black and 32 white.
    Both sides must have a king.
    Neither side can have more than 8 pawns.
    The sum of the number of queens, knights, rooks, bishops and pawns
    cannot exceed 15 for either side (think pawn promotion.)
    White cannot have any pawns on rank 1, black cannot have any on
    rank 8.

    Other criteria are more complex: I can't imagine any possible play
    resulting in, for example, eight white pawns on rank 5 and eight black
    pawns on rank 4.

    Can anyone think of more that I've missed? Or derive a general
    formula including these (and any additional) criteria that can calculate
    the total number of positions?

    -mike
  2. Donation Jacko
    Knock, Knock...?
    10 Dec '02 22:43
    would casteling be 2 moves (king and rook moving) or as one move??

    David
  3. Donation Acolyte
    Now With Added BA
    11 Dec '02 01:23
    More conditions: at most one king is in check; the 'bias' of the pawn structure (ie number of
    double pawns etc) can be no more than the number of pieces the opposing player has lost.
  4. Donation legionnaire
    Free Thinker
    11 Dec '02 04:06
    Originally posted by Acolyte
    More conditions: at most one king is in check; the 'bias' of the
    pawn structure (ie number of
    double pawns etc) can be no more than the number of pieces the
    opposing player has lost.
    Those are good ones. I suppose another case would be in the event
    that all 8 pawns are present with two bishops that they would have to
    be on different colored squares.

    The idea for posting this in the first place is my assumption that there
    exists a finite number of legal positions on a chessboard. Maybe I'm
    asking the question in the wrong way. Can any prove that there exists
    an infinite number of legal positions?

    -mike
  5. 11 Dec '02 15:34
    I'm sure there must be a finite number of legal positions on a chess board. At first I thought
    otherwise in a parallel to language: i.e., there are an infinite number of recombinations of
    words to form new utterances. However, language is constrained only by a generative
    grammar, and chess is much more constrained than this. If you think that each piece can only
    be on one of 64 squares (notwithstanding the constraints already raised in this thread) then
    the total no. of legal positions is bound to be constrained to a finite number by this
    consideration alone... again, with the language analogy, the possible number of sentences is
    not at all constrained by length, you don't have to shoehorn all of the words into 64 possible
    slots, and I think this helps greatly in making language infinitely possible....

    sorry for the rambling, and I'm aware that this in no way comes even anywhere near a proof
    of anything, but it seems intuitively correct somehow

    Joe
  6. Donation Acolyte
    Now With Added BA
    12 Dec '02 00:13
    This problem sounds like it'll take a while. I think I'll start by finding an upper bound (ie
    something guaranteed to be an overestimate.) I'll round up the numbers and give the
    estimate in brackets.

    Suppose we have 32 pieces on the chessboard. Then there are 64 choose 32 ways of covering
    squares with them (2*10^18) . Two of these are the kings, so we have 32x31 (700) ways of
    putting these on the covered squares. Then we have 8 pawns for each player, so we have 30
    choose 8 for White and 22 choose 8 for Black (6*10^7, 320000). But these pawns could each
    be in one of 6 states (promoted to one of 4 things, unpromoted, captured), so that gives a
    further 6^16 (3*10^12) possibilities. Now among the remaining 14 pieces, we have three
    kinds of piece occurring twice, so we get 14!/8 (1.1*10^10) ways of arranging them
    (eliminating ones where two alike pieces are swapped around.) But any of these could have
    been captured, so we have to multiply by 2^14 (17000).

    Multiplying all these rounded up numbers together, you get around 10^57. So at least we
    know the real answer isn't THAT big.
  7. 12 Dec '02 13:05
    there are probably ways to reduce this maximum drastically (bishops can only be on half the squares etc....). But first there are a
    few things that make the maximum greater:

    - it makes a difference in position if a fysical configuration has reoccured 0, 1 ot 2 times before
    - the number of moves before without capturing or moveing pawns also affects the 'position'
    - castling still possible or not

    just to name a few.

    Gilbert
  8. Donation legionnaire
    Free Thinker
    12 Dec '02 16:32
    Originally posted by Acolyte
    This problem sounds like it'll take a while. I think I'll start by
    finding an upper bound (ie
    something guaranteed to be an overestimate.) I'll round up the
    numbers and give the
    estimate in brackets.

    Suppose we have 32 pieces on the chessboard. Then there are 64
    choose 32 ways of covering
    squares with them (2*10^18) . Two of these are t ...[text shortened]... ers together, you get around
    10^57. So at least we
    know the real answer isn't THAT big.
    Ouch!! That's a huge number of positions, enough to trouble even a
    massive supercomputer. I wonder if it would help to start with the
    absolute simplest case: each side has one king only. In that case,
    the two pieces could be anywhere on the board except adjacent to
    each other. So starting with the first king, it could have 64 possible
    positions. If that king is in a corner, then there are 60 possible
    positions for the other king. If the first king is along an edge but not
    in a corner, then there are 58 possible positions for the second king.
    If the first king is not on an edge, then there are 55 possible
    positions for the second king. Giving a total of either 124, 122 or 119
    possible positions.

    -mike
  9. Donation Acolyte
    Now With Added BA
    12 Dec '02 19:18
    Originally posted by sintubin
    there are probably ways to reduce this maximum drastically (bishops can only be on half
    the squares etc....). But first there are a
    few things that make the maximum greater:

    - it makes a difference in position if a fysical configuration has reoccured 0, 1 ot 2 times
    before
    - the number of moves before without capturing or moveing pawns also affects the 'position'
    - castling still possible or not

    just to name a few.

    Gilbert
    I didn't think of those... make that 10^60 then.
  10. 12 Dec '02 19:28
    Originally posted by Acolyte
    I didn't think of those... make that 10^60 then.
    so now we could perhaps try to get the number down:
    - two white rooks , when both on the board can be interchanged
    without changing the position; same with black ones, same with
    knights
    - promotion to knights and rooks will give the same "duplication"
    - a big one, bbt a problem on its own: no position is allowed where
    both kings are in chess
    - a king can not be 3 or more times in check in one position (is that
    certain?)

    etc... this is getting out of hand.

  11. Donation Acolyte
    Now With Added BA
    13 Dec '02 00:01 / 1 edit
    Lower bound (rounding down this time)

    Assume no promotions.

    Pieces that have been captured are seen as being on 'dead' squares off-board

    Pawns: each file 8 choose 2 = 28 -> 28^8 (allowing for 'dead' squares)
    I'm assuming that each player has at most one pawn on any file, and that they're standing
    facing each other, so no choice of order.

    Say White King is not in check, so could be in one of 34 places (64 -(16 + 14))

    Black King is not next to White King, so 64 - 16 - 9 = 39.

    So far we have about 5*10^14.

    Say Black King is not being attacked by non-pawns: this rules out up to 14 squares for
    orthogonally and 13 for diagonally movable pieces. So:

    White Queen has 65 - 18 -14 - 13 = 20
    White Rooks have 66 - 19 - 14 = 33, that choose 2 = 528, -1 for alternate use of 'dead'
    squares
    White Knights have 66 - 21 - 8 = 37, that choose 2 = 666, -1 for same reason

    Similarly

    Black Queen has 65 - 23 - 14 - 13 = 15
    Black Rooks have 66 - 24 - 14 = 28, that choose 2 = 378, -1 = 377
    Black Knights have 66 - 26 - 8 = 32, that choose 2 = 496, -1 = 495

    Total for this section: about 1.9*10^13

    Some positions counted might be impossible due to strange circumstances involving check and
    stalemate, but I don't think there are very many of these.

    So my second crudely calculated estimate is 9.5*10^27, and this time I'm pretty sure it's an
    underestimate.

    PS I've ignored Bishops because they get a bit complicated.
  12. Donation Rhymester
    and RedHotTed
    19 Dec '02 13:15
    Originally posted by Acolyte

    I've ignored Bishops because they get a bit complicated.

    LOL!
    LOL!!!!
  13. Standard member genius
    Wayward Soul
    26 Dec '02 10:33 / 1 edit
    for the first 4 moves there are (((20^20)^20)^20)-1 possibilities. i think (well, it is boxing day......) anyway, that's approximatly 1.737*10^10408...wow...were into big numbers here...

    G
  14. 26 Dec '02 11:17
    Originally posted by genius
    for the first 4 moves there are (((20^20)^20)^20)-1 possibilities. i think (well, it is boxing day......) anyway, that's approximatly 1.737*10^10408...wow...were into big numbers here...

    G
    didn't you mix powers and multiplication?
  15. Standard member thire
    Xebite
    22 Jan '03 09:50
    interesting thread...
    I wonder if this question hasn't already discussed out there in the net. anyone knows?