5

For layman, can someone explain how you calculate the number of available positions in a chess game, and how do you get the huge number of 10^120 or 10^46?

9

We can easily get a reasonably good upper bound on the number of positions. At any point in time, each player has 16 pieces of which the 8 pawns can perhaps be promoted to a knight / bishop / rook / queen. Consider all captured pieces to be off the board but part of the position (this would increase the number of positions but that is fine because we only want an upper bound). Thus in each position the number of combinations of pieces each player has is less than 58. Place the kings on the board first. There are less than 642 ways to do that. Line up the 30 other pieces in any order and place them one by one on the board or off the board (captured). There are at most 6330 ways to do that. This gives a total of less than (58)2×64^2×63^30 < 6×1068 positions. Double that to include whose turn it is. I had ignored castling rights; you can check that it is negligible by similar calculations.

This bound is very much smaller than what you gave in your question, even though it is an extremely loose upper bound, because you had a misconception. The number of possible positions is not at all the same as the number of possible games. For example, there are less than 642 positions with just the 2 kings, but at least 2100 possible games starting from any such position (under the 50-move rule but ignoring 3-fold repetition rule for easy estimation). Moreover, the 10120 estimate is assuming the game lasts 40 moves (2 plies) and each move has about 1000 possibilities. The real total number of possible games (including stupid ones) is obviously way more than that, since we already have 2100 possible KK games alone!

  • "The number of possible positions is not at all the same as the number of possible games." that's something knew. i didn't know that. It would be a good idea to give the number of possible positions from any particular opening such as the sicilian or grunfeld. then there won't be a problem of calculating the number of games and it would be a good example if anybody seeks to calculate some other opening. thanx – shashank shekhar singh Jul 14 '20 at 6:53
  • 1
    @shashankshekharsingh: To get your intuition working better, consider a simple 'game' in which you have three cells in a line and one piece in one of the cells, and you just move the piece to an adjacent cell on each move. Then there are only 3 possible positions, but 2^k possible games that last 2k moves. – user21820 Jul 14 '20 at 6:56
  • 2
    "Line up the 30 other pieces in any order and place them one by one on the board or off the board (captured)." With this, the calculation 63x62x...x34 gives a number that is too small (and thus it is not an upper bound), because the "captured" position can be chosen multiple times and thus does not reduce the number of possibilities for the next piece to select from. – Stanley F. Jul 14 '20 at 6:59
  • 1
    @StanleyF.: Gah you're right. Let me just use the simpler obvious upper bound of 63... – user21820 Jul 14 '20 at 7:01
1

One way to do it is think about what the smallest computer encoding of a chess position (in bits). The maximum size for a given encoding provides an upper-bound on the number of chess positions. For some really tight upper bounds check out https://codegolf.stackexchange.com/questions/19397/smallest-chess-board-compression/19446#19446. This gives an upper bound of 2^160 (10^48) positions, which is a bit high, but not that much higher than the true value.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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