8

There have been several questions regarding the possible number of chess games. for example; Database of every possible move in chess. However,can there be an estimate on the number of "allowable" chess positions?

For another example, White pawns cannot occupy the first row and Black pawns cannot occupy the eighth row. If a given chess piece is occupying a square, then another chess piece cannot occupy that. Using simple elimination rules coded, can we have an estimate on the number of unique positions that chess pieces can have since they would be reducing in number? An upper bound on positions before applying any elimination rules would be the sum of (64 C 32 + 64 C 32 ... + 64 C 2). This is less than 10^20. With elimination rules, they should be significantly lower.

Any ideas on how elimination rules are written for chess pieces?

Improve this question
5
  • 1
    Your estimate is too low. You shouldn't just compute combinations, it matters which pieces are on which squares.
    – Dag Oskar Madsen
    Commented Jun 16, 2014 at 10:36
  • The maths goes like you choose the 32 squares possible, and find number of pieces you can place on each square. Then multiply 64 C 32
    – QuIcKmAtHs
    Commented Dec 27, 2017 at 12:25
  • 1
    The number of legal chess positions is roughly 4x10^44: github.com/tromp/ChessPositionRanking
    – John Tromp
    Commented Aug 8, 2021 at 15:39
  • 1
    Does this answer your question? Is the number of possible chess games infinite?
    – BCLC
    Commented Nov 6, 2021 at 18:02
  • A serious answer should, I think, at least give a nod to the restrictions that the positions should be those 'in a chess game'. Thus it is not just legal positions, but also that they have to follow each other like pearls on a string: when one pawn is moved, or a piece captured, this immediately puts additional restrictions on the positions that can follow. It's fairly easy to estimate an upper limit -- but getting at any correction terms appears to be close to imponderable
    – user30536
    Commented Mar 7, 2023 at 17:49

4 Answers 4

Reset to default
9

Upper bounds on the number of allowable positions are discussed on the Shannon number Wikipedia page.

There is an accepted upper bound of 1.8x10^46 by Shirish Chinchalkar, and an accurate estimate of 4.8x10^44 by John Tromp.

By comparison, the number of atoms on earth is about 10^50.

Improve this answer
8
  • The article fairly estimates the positions to be close to 10^50. Link is nwchess.com/articles/misc/Chess_Board_Positions_article.pdf
    – shoonya
    Commented Jun 16, 2014 at 9:34
  • However this can be computed to a far better estimate, especially the cases when Kings are already in checks, Kings are simultaneously in check. The key thing being estimating this can allow us to typically find the optimal moves for a given position.
    – shoonya
    Commented Jun 16, 2014 at 10:11
  • 1
    @JohnTromp Do you have a new reference?
    – Dag Oskar Madsen
    Commented Mar 7, 2023 at 11:50
  • 1
    @JohnTromp and 'accurate' is subjective - you might want to add the uncertainty.
    – Glorfindel ♦
    Commented Mar 7, 2023 at 13:11
  • Is the editor hijacking the answer here? Is that really allowed?
    – user30536
    Commented Mar 7, 2023 at 17:53
2

Old question, but for people who just want a quick estimate they can do with basic math this is an easy way to go about it

If we consider all 32 pieces, we can rearrange them P(64,32) or 64 permute 32 ways. If we then consider 31 pieces, we do the same as above with P(64,31) but this time we must factor in the choice of 31 out of the 32 pieces so we multiply P(64,31) by C(32,31) or 32 choose 31. If we continue along this manner we have the sum from n =2 to 32 of P(64,n)C(32,n) which gives 1.24e54 which is only a few orders of magnitude larger than the number given by Vicor Allis.

Note that in the assumptions, we allowed illegal positions, and double or triple counted certain positions by treating each piece as distinct. But the number is reasonable compared to that above and more importantly is easily attainable with pretty basic math.

Improve this answer
4
  • @DagOskarMadsen I did notice you have a PhD in math, so does this upper bound seem reasonable or is there a way to improve it?
    – Colin Hicks
    Commented Jul 21, 2020 at 4:58
  • 1
    It's a start. You also have to take promotions into account which will make this bound much larger.
    – Dag Oskar Madsen
    Commented Jul 21, 2020 at 12:32
  • @DagOskarMadsen ah yes. I changed C(32,n) to C(96,n) to allow for all 16 pawns to assume the identity of the 4 other piece types other than king but now the value is 1.454e79 which is fairly off the mark haha
    – Colin Hicks
    Commented Jul 21, 2020 at 17:24
  • Wikipedia mentions 2x10^40 as the best known upper bound without promotions.
    – Dag Oskar Madsen
    Commented Jul 21, 2020 at 18:18
1

It is really difficult to find out legal positions but total positions possible is 13^64 , assuming each piece can be positioned in every available square

Improve this answer
1

Here is a Python script that gives an upper bound of ~10^51.431 positions (legal and illegal). Moreover, the script doesn't check for legality of positions or if a position is reachable, so the proportion of legal positions should be a few orders of magnitude lower. A bootstrap approach can be used to approximate this proportion.

Note the following variables are updated:

squaresAvailable = Number of squares available to use
whiteProm = Maximum number in promotions available on the position for white pieces
blackProm = Maximum number in promotions available on the position for black pieces

import math
sum = 0
tosum = 43
for whitepawn in range(9): #whitepawn is the number of white pawns on the board (0 to 8)
    #wp represents the number of ways to arrange a given number of white pawns
    wp = math.comb(48, whitepawn)
    whiteProm = 8 - whitepawn
    blackProm = 8
    
    for blackpawn in range(9):
        bp = math.comb(48 - whitepawn, blackpawn)
        whiteProm = 8 - whitepawn
        blackProm = 8 - blackpawn
        squaresAvailable = 62 - whitepawn - blackpawn
        
        for whitelsbishop in range(2 + max(whiteProm, 0)):
            squaresAvailable =  62 - whitepawn - blackpawn - whitelsbishop
            wbls = math.comb(math.ceil(squaresAvailable/2), whitelsbishop)
            whiteProm = 8 - whitepawn - max(0, whitelsbishop - 1)
            blackProm = 8 - blackpawn
            
            for blacklsbishop in range(2 + max(blackProm, 0)):
                squaresAvailable = 62 - whitepawn - blackpawn - whitelsbishop - blacklsbishop
                bbls = math.comb(math.ceil(squaresAvailable/2), blackbishop)
                whiteProm = 8 - whitepawn - max(0, whitelsbishop - 1)
                blackProm = 8 - blackpawn - max(0, blacklsbishop - 1)

                for whitedsbishop in range(2 + max(whiteProm, 0)):
                    squaresAvailable =  62 - whitepawn - blackpawn - whitelsbishop - blacklsbishop - whitedsbishop
                    wbds = math.comb(math.ceil(squaresAvailable/2), whitedsbishop)
                    whiteProm = 8 - whitepawn - max(0, whitelsbishop - 1) - max(0, whitedsbishop - 1)
                    blackProm = 8 - blackpawn - max(0, blacklsbishop - 1)

                    for blackdsbishop in range(2 + max(whiteProm, 0)):
                        squaresAvailable =  62 - whitepawn - blackpawn - whitelsbishop - blacklsbishop - whitedsbishop - blackdsbishop
                        bbds = math.comb(math.ceil(squaresAvailable/2), whitedsbishop)
                        whiteProm = 8 - whitepawn - max(0, whitelsbishop - 1) - max(0, whitedsbishop - 1)
                        blackProm = 8 - blackpawn - max(0, blacklsbishop - 1) - max(0, blackdsbishop - 1)
                    
                        for whitenight in range(3 + max(whiteProm, 0)):
                            squaresAvailable = 62 - whitepawn - blackpawn - whitelsbishop - blacklsbishop - whitedsbishop - blackdsbishop - whitenight
                            wn = math.comb(squaresAvailable, whitenight)
                            whiteProm = 8 - whitepawn - max(0, whitelsbishop - 1) - max(0, whitedsbishop - 1) - max(0, whitenight - 2)
                            blackProm = 8 - blackpawn - max(0, blacklsbishop - 1) - max(0, blackdsbishop - 1)
                            
                            for blacknight in range(3 + max(blackProm, 0)):
                                squaresAvailable = 62 - whitepawn - blackpawn - whitelsbishop - blacklsbishop - whitedsbishop - blackdsbishop - whitenight - blacknight
                                bn = math.comb(squaresAvailable, blacknight)
                                whiteProm = 8 - whitepawn - max(0, whitelsbishop - 1) - max(0, whitedsbishop - 1) - max(0, whitenight - 2)
                                blackProm = 8 - blackpawn - max(0, blacklsbishop - 1) - max(0, blackdsbishop - 1) - max(0, blacknight - 2)   
        
                                for whiterook in range(3 + max(whiteProm, 0)):
                                    squaresAvailable = 62 - whitepawn - blackpawn - whitelsbishop - blacklsbishop - whitedsbishop - blackdsbishop - whitenight - blacknight - whiterook
                                    wr = math.comb(squaresAvailable, whiterook)
                                    whiteProm = 8 - whitepawn - max(0, whitelsbishop - 1) - max(0, whitedsbishop - 1) - max(0, whitenight - 2) - max(0, whiterook - 2)
                                    blackProm = 8 - blackpawn - max(0, blacklsbishop - 1) - max(0, blackdsbishop - 1) - max(0, blacknight - 2)
                                    
                                    for blackrook in range(3 + max(blackProm, 0)):
                                        squaresAvailable = 62 - whitepawn - blackpawn - whitelsbishop - blacklsbishop - whitedsbishop - blackdsbishop - whitenight - blacknight - whiterook - blackrook
                                        br = math.comb(squaresAvailable, blackrook)
                                        whiteProm = 8 - whitepawn - max(0, whitelsbishop - 1) - max(0, whitedsbishop - 1) - max(0, whitenight - 2) - max(0, whiterook - 2)
                                        blackProm = 8 - blackpawn - max(0, blacklsbishop - 1) - max(0, blackdsbishop - 1) - max(0, blacknight - 2) - max(0, blackrook - 2)
                                        
                                        for whitequeen in range(2 + max(whiteProm, 0)):
                                            squaresAvailable = 62 - whitepawn - blackpawn - whitelsbishop - blacklsbishop - whitedsbishop - blackdsbishop - whitenight - blacknight - whiterook - blackrook - whitequeen
                                            wq = math.comb(squaresAvailable, whitequeen)
                                            whiteProm = 8 - whitepawn - max(0, whitelsbishop - 1) - max(0, whitedsbishop - 1) - max(0, whitenight - 2) - max(0, whiterook - 2) - max(0, whitequeen -1)
                                            blackProm = 8 - blackpawn - max(0, blacklsbishop - 1) - max(0, blackdsbishop - 1) - max(0, blacknight - 2) - max(0, blackrook - 2)
        
                                            for blackqueen in range(2 + max(blackProm, 0)):
                                                squaresAvailable = 62 - whitepawn - blackpawn - whitelsbishop - blacklsbishop - whitedsbishop - blackdsbishop - whitenight - blacknight - whiterook - blackrook - whitequeen - blackqueen
                                                bq = math.comb(squaresAvailable, blackqueen)
                                                blackProm = 8 - blackpawn - max(0, blacklsbishop - 1) - max(0, blackdsbishop - 1) - max(0, blacknight - 2) - max(0, blackrook - 2) - max(0, blackqueen -1 )
                                                sum = sum + wp * bp * wbls * bbls * bbds * wbds * wn * bn * wr * br * wq * bq
                                                    
                                    
#64 squares available for white king and 63 for black king as an upper bound
print(math.log10(sum * 64 * 63))

OUTPUT: 51.43108306627925
Improve this answer
2
  • Symmetrical positions? Positions that are not feasible? legal positions - we are hoping this shall be a big number
    – shoonya
    Commented Mar 19 at 14:36
  • All symmetrical positions are considered. The script doesn't check for legal positions is not implemented, although I have a few ideas to minimize the number of illegal positions. The result (10^51.431) is absolutely a huge number.
    – Yash Jain
    Commented Mar 19 at 15:40

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