TransWikia.com

How to calculate the number of positions in chess?

Chess Asked on October 5, 2021

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 Answers

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.

Answered by Oscar Smith on October 5, 2021

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!

Answered by user21820 on October 5, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP