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?

2

3 Answers 3

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!

4
  • "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 Commented Jul 14, 2020 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
    Commented Jul 14, 2020 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.
    Commented Jul 14, 2020 at 6:59
  • 1
    @StanleyF.: Gah you're right. Let me just use the simpler obvious upper bound of 63...
    – user21820
    Commented Jul 14, 2020 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.

1

Assume that only checkmate or stalemate ends the chess game. It implies that every legal position in the classical chess remains legal. Then, the number of legal positions in chess does not exceed 53005918951815626260641171706639462843262017900515420, please see Lemma 16 in

http://ssrn.com/abstract=3978669

The upper bound in Lemma 16 is not minimal because takes into account many positions which are impossible to achieve in a game.

For every p \in {0,...,8}, any position with p white pawns cannot contain 2+8-p white bishops on the squares of the same colour.

For every p \in {0,...,8}, any position with p black pawns cannot contain 2+8-p black bishops on the squares of the same colour.

If the white king is in check then Black cannot have a move.

If the black king is in check then White cannot have a move.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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