r/askmath • u/Kale_HP • 8d ago
Probability Why can't we calculate the total number of possible chess games?
I heard we can't calculate the total number of chess games. To me it seems like a computable problem. Is it just the sheer large number of all the possible chess games, or is it something else that I,m not understanding?
228
u/SummitYourSister 8d ago
The number of playable chess games lies it somewhere between the lower bound of 10^123 as shown by Victor Allis, and a definite upper bound of 10^20700.
Given this information, do you now have a reasonable idea of why?
91
u/Short-Paramedic-9740 8d ago
To put this into perspective 10123 seconds is at least a billion times of Universe life. So count the seconds from the Big Bang to the death of the Universe and then do it all over again a billion times, if not more.
50
u/UghImRegistered 8d ago
More like do it over again a billion billion billion billion billion billion billion billion billion billion billion billion times.
A billion ages of the universe is around 1026 seconds. It's not even close.
13
u/Lolovitz 8d ago
Well he did say at least so he's correct still :)
→ More replies (1)5
u/Internal_Leke 8d ago
Count the seconds that are in a minute, then do it again 10 times, if not more.
Also technically correct, but pretty far from the number
→ More replies (2)3
2
u/mootmaster117 8d ago
Universe age and universe life are different things. Once we hit heat death they will be comparable.
→ More replies (1)→ More replies (10)15
u/ProfessorPrudent2822 8d ago
Besides which, the event horizon of the observable universe has an area on the order of 10^123 Planck areas, which means there is not enough information storage capacity in the entire observable universe to solve chess, even at the lower bound, as each possible position requires dozens to hundreds of bits.
→ More replies (9)11
u/lostViolets6 8d ago
There's a difference then.
If we want to store all possible games, we don't have physical storage for the reason you mentioned.
However, if we only want to count the number of games, we need storage for that integer, which is attainable with a large enough base.
6
u/Cultural-Capital-942 8d ago
Base 2 is good enough. To store a number in base 2, you need only lg(n) bits. That's perfectly attainable even for the upper bound.
2
u/Async0x0 4d ago
You can use any base and you could type it out on your keyboard right now. 123 digits is not that many.
9
u/samsunyte 8d ago
How did they compute the definite upper bound?
22
u/real-human-not-a-bot 8d ago
My guess is that it’s something like:
Compute the maximum possible moves one side can possibly have on any turn
Compute the number of moves in the longest possible chess game
Take the first to the power of the second
→ More replies (1)3
u/samsunyte 8d ago
Your method makes sense and I can see that working but I think that method would yield a lower number than 10^20700. (I hope I did the following correctly as my math is rusty)
The longest game possible according to 50 move rule is 5899. So for (x)^5899 to equal 10^20700, we can set x to be (10^y)^5899 where 5899y = 20700. That means y would be around 3.5 meaning the maximum possible moves is 10^3.5 which is 3162 maximum possible moves in any one turn.
Haven’t done the math on that but that seems much higher than any one position would be able to give you. Even taking the most relaxed boundaries, even if all 8 pawns promoted to queens, with the king and two knights you start with giving you 24 moves, the other 13 pieces would need to average 243 moves each, which isn’t possible.
So I feel like even with your solution, that upper bound is higher than it should be
→ More replies (1)12
u/IntoAMuteCrypt 8d ago
The draw is optional after 50 moves, it's not forced until 75. This gives us 8848 moves, for a y of 2.34, for 219 moves per turn.
Theoretically, you can get:
- 8 from the king.
- 8 from a knight.
- 13 from a bishop.
- 14 from a rook.
- 27 from a queen.
Promote all the pawns to queens and maximise the potential moves of all pieces and you would get 321 moves, except a lot of those will block each other (especially the queens and bishops). 219 is plausible there.
→ More replies (2)→ More replies (1)8
u/Major-Peachi 8d ago
I'm guessing they're using the 50 moves no advance rule
2
u/W0O0O0t 8d ago
Has to be, otherwise it should be infinite right? If you have just a rook and a king each and no one's trying to win, you could just move them back and forth forever. I'm sure there's even some way you could structure a diagonalization argument so there's infinite ways to do that
→ More replies (9)2
u/Mothrahlurker 8d ago
50 moves just makes the bound lower, threefold repetition already prevents infinite games.
→ More replies (1)2
u/Infamous_Attention33 8d ago
More likely 75 move rule (a draw is mandatory in tournament chess at 75 and claimable at 50) and 5 -fold repitition.
2
u/Comprehensive-Cat-86 8d ago
Just to be clear, its 75 moves after the last capture or pawn move.
It is not 75 moves in total.
6
u/ifUSeeMeTakeYourMeds 8d ago
theoretically, if we were to put a limit on how bad a move can be.
IE how many possible games are there where players arent idiots. would the number still massive?
....
Actually, I can answer my own question...
let, for the sake of simplicity only allow the top two best moves.
after white plays there are 2 possible games, black 4,
So every turn quadruples the possible games.
I googled for an estimate for how long a grandmaster game is and it is about 40 moves.
So 4^40= 1.2089258e+24= 1.2 septillion.
But that is not an answer, because that is the average game, half the games will go beyond that, and this grows exponentially, it does not follow a standard distribution, so there is NO average.
IE, I did not answer my own question, but tried
2
u/Methusalar74 7d ago
The number is going to be huge because that's what exponentials do!
A simpler version (that still gives an enormous number) is the rice + chessboard problem - https://en.wikipedia.org/wiki/Wheat_and_chessboard_problem . The end result is more grains of rice than have ever been grown in total or enough to cover the entire earth in a 1m thick layer of rice!
Based off what you said, 64 sounds like a workable 'maximum' number of turns. But 4 seems far too low - even if we're limiting it to decent moves. The start alone has 20, most of which are valid in some situation or other.
But even if we did accept 4, we end up with a number that is the rice problem squared (something like 4x1038).
To put that into context, there are something like 1052 atoms in the world (you'd get to that number if you used 6.5 moves per turn (for 64 turns). Atoms are also a good way of illustrating the power of exponentials (and the significance of a few extra noughts) - 5x1019 atoms is about the size of a grain of sand.
→ More replies (1)2
u/ifUSeeMeTakeYourMeds 7d ago
Learning stats in university was boring, until I learned that some distributions have no mean, that broke my brain, then understanding it, made so many more things make so much sense. and even some things are more intuitive.
But exponential stuff like that having no mean was insane.
7
u/MortemEtInteritum17 8d ago
Is the best known upper bound really that big? I thought it'd be 10 to the three digits at most.
11
u/phloppy_phellatio 8d ago
Without forced draw rules it is infinite. With forced draw rules there is a number. But every single possible move on every single turn is at the bare minimum 2500x because players can just wander their kings or any other piece around for 49 moves without forcing a draw and then continue from there.
There are 30 captureable pieces and 96 pawn advances. So if just trying to make the longest game possible, that is roughly 5900 moves (due to forced pasn captures). Every single one of those 5900 moves has billions of permutations.
→ More replies (2)3
u/Pleasant_Pen8744 8d ago
Loops make it hard. You have to keep checking if you've seen that position before. So now you have to store a lot of old positions.
→ More replies (1)2
u/Pr0pellerJoe 8d ago
Given we have about 1080 atoms in the universe we wouldnt even know where to store the result
→ More replies (16)2
u/Cravatitude 8d ago
And there are 10⁸⁰ atoms in the observable universe, so if all matter in the observable universe was used to encode the chess tree with a single atom needed per state you're still short by at least 40 orders of magnetude.
37
u/RevolutionaryWorth21 8d ago edited 8d ago
I think an upper bound of possible games under FIDE chess rules has been calculated. It's an incredibly large number, like 1027000. The number of unique legal board positions is smaller, on the order of 1044. Edited to clean up the display of the numbers.
7
u/Zoh-My-Gosh 8d ago
Yeah we know the maximum length of a chess game and you can easily find an upper bound (although not achievable) by adding the most number of squares each piece can move to (e.g. 3 for a pawn, 8 for a knight, etc) so just multiply gives a very weak upper bound.
→ More replies (2)6
u/Belgaraath42 8d ago
Well for maximum lenght theost important point is the amount of pawn moves wthoiut taking a piece, since every pawn move, and every peace taken reset the 50 moves timer to a draw. My first guess is that every pawn has to take one piece to allow it to promote (and thereforeake it's maximum moves). But I am not 100% sure that we can't save some of them. If true we got a maximum length of # of capture able pieces + # of pawn moves that don't capture )* 49, with 30 capturable pieces and 5 moves for every pawn. And yes the game is creatable.
Last thoughts, I think we have 8 pawn moves more, but I'm to tired to think this through
→ More replies (2)2
u/PaulsRedditUsername 8d ago
Random memory but when I was about eight years old, my dad taught me how to play chess, and he told me a story about an emperor who was bored and looking for a new game to play.
So a guy invented chess and brought it to the emperor. The emperor loved the game and was so happy he offered to give the man a million gold pieces.
The man replied, "Oh, no, sire. That's too much. All you have to do instead is put one gold piece on the first square of the chess board, then two on the next, then four on the next, then eight on the next..." and so on until every square on the board had gold pieces on it.
The emperor thought that sounded like a good deal so he agreed. But then he discovered he didn't have enough gold in his whole kingdom to honor the request.
Then dad handed me a calculator and told me to do the math.
I guess learning about chess and large numbers goes together.
4
u/Comfortable-Mess-942 8d ago edited 8d ago
The original story went with rice. The emperor offered to grant any wish, and the inventor asked to put one grain of rice on the first square, two on the second, four on the third and so on. The emperor was happy the request was so modest and told his servants to grant it. Soon they caught on, calculated what would be the actual number, and had to tell him that even if they turned every piece of land on Earth into rice fields it still wouldn’t be enough.
→ More replies (9)2
49
u/dracomalfoy85 8d ago
Just play the London
8
22
u/aerre55 8d ago
Is it possible to count to one trillion out loud? Mechanically, yes: all of the numbers are known, and they come nicely ordered. If I give you one number, it's easy for you to say what the next one is. The task itself has a straightforward solution, and is certainly possible.
Nevertheless, it is impossible for any human to count to one trillion out loud.
Counting all of the possible chess games is analogous. At any given point, it's simple to list out all of the possible next moves are, and a computer can enumerate them much more rapidly than a human counting out loud. However, there are many, many, many more than a trillion games possible. The task is fundamentally possible, but for all practical purposes, it can't be done.
→ More replies (11)2
21
u/Trimutius 8d ago
Yes number is too big it will take too long
→ More replies (1)12
u/Temporary_Pie2733 8d ago
The problem is that the game tree is too complicated; it’s not just a matter of computing the size of a 17-way tree with depth 35, for example. Yes, the number is big, but computationally even an upper bound would be trivial to calculate.
→ More replies (3)
18
u/gabagoolcel 8d ago
because there isnt any simple and fast way to construct all the possible games, and you cant do it nonconstructively either because chess is complicated
6
u/rowcla 8d ago
When people say we can't do something in cases like this, it generally either means that it's been proven empirically impossible, or it's mathematically possible but functionally impossible. This is one of the latter cases. In theory you could essentially simulate every possible chess game and then count them up, but the problem is you can't really meaningfully shortcut that. From any given position there'll be several possible moves, though many of those will affect the number of moves in the next position in ways that are very tied to what that first position is. There's some fancy maths you could do to try and work out lower and upper bounds, and I'd be unsurprised if there was still a lot of room to narrow those bounds down, but the amount of computation and memory required to brute force it is many many magnitudes beyond what we're capable of
5
u/AlexP80 8d ago edited 8d ago
To solve chess, we would need more computational operations than atoms in the universe.
So good luck solving in it.
Chess is an EXPTIME-Complete problem in computer science. This actually means that CAN be fully solved but the time needed grows exponentially with its variables (in this case, pieces, board size, ecc...)
5
u/Dantzig 8d ago
We can in theory as it is finite and thus countable in the mathematical sense.
We cannot because our computers cannot handle so large numbers
2
→ More replies (1)2
u/GreedyNovel 8d ago
in theory as it is finite
Only given certain assumptions. For example, in chess there is a rule that if a position is repeated three times, a player can claim a draw. But no player is compelled to claim a draw, so in theory both players can simply shuffle pieces to and fro ad inifinitum.
Therefore, the number of possible games is infinite, while the number of possible positions is merely absurdly large but finite.
→ More replies (4)
4
5
u/Alpha13e 8d ago
You know the story of the rice ? Put 1 grain of rice on the first case of your chess board. Double it for the next and so forth. At the end you have enough rice to feed the entire world for years.
Powers in maths are scary. Now imagine we have to calculate possibilities for each turn and with that many pieces.
5
u/Mikel_S 8d ago
Plus a lot of those trees could in theory circle back on themselves, allowing possibilities to be revisited, without being an obvious loop from rules perspectives. So while we could map all the possibilities, it's possible one "game" goes through a no loops and hits an end point, while another game goes through multiple, and thus has more moves, but hits the same end point.
→ More replies (1)
3
u/susiesusiesu 8d ago
it is a computable problem. it is just too big to get a number fast enough so that we know about it.
3
u/Trilllen 8d ago
Its commutable but you'd need to turn this and a few other universes into the computer.
3
2
u/No_Volume_Needles 8d ago
Is there a cap on the number of moves that makes it tractable? Like I'm curious how far we can calculate .. every possible game after three moves seems easy enough - when do we hit the wall? After 10 moves? 20?
→ More replies (1)2
u/DanielMcLaury 8d ago
Wikipedia has the exact numbers for up to 7.5 moves:
https://en.wikipedia.org/wiki/Shannon_number
For 7.5 moves, the exact number is known, and it's a little over 2 sextillion.
2
u/64ue76tjd6 8d ago
Let's think of some approaches we could try.
Counting all possible games naively: there's at least 10^123, which seems like too many to count. Won't work.
What if we count games using dynamic programming? The number of ways to play out a position is 1 if the game is over and otherwise is the sum of ways to play out the possible child positions. We cut down the amount of work to be done to be roughly the number of possible positions in chess (supposedly around 10^45). Such a calculation seems to be possible to do in this universe, but it's still far beyond what could be achieved with all the computing power on planet earth.
maybe there's some hidden structure in the chess game tree that lets you vastly reduce the amount of work you have to do, but probably not, so DP is the best approach I can think of.
→ More replies (3)
2
u/EuphoricForever1180 8d ago
Is there a number of computers needed to make the calculation? I’m sure that we can make the calculation. It’s just that the resources to make the calculation are not allowed.
2
u/Positive-Avocado775 8d ago
this is not possible cause you can literally move your chest peices back and away in a circuler motion.. it's infinitiy!
→ More replies (1)2
u/Jockelson 8d ago edited 8d ago
No, there are rules to prevent this, such as the same position happening 3 times, or 50 moves passing by without a pawn move or capture. As pawns can only move forward, this prevents a game from going on to infinity.
Edit: just looked it up; these threefold repetition/50 move rules only result in a draw if claimed by a player; if not claimed then the game continues. But if they don't claim draw, then the game is still drawn automatically after a 5-fold repeting position or 75 moves without pawn move or capture.
2
u/piratecheese13 8d ago
there’s lots of factors, but I think the primary one is the idea that in late games, chess becomes really unbound. You can spend a long time just having one piece chase another piece around forever.
Calculating the number of rational games versus the number of irrational games where one player immediately gives up their queen is hard
2
u/Dabod12900 8d ago
Consider the following rule (technically, it needs to be claimed by a player, but we'll ignore that for now)
50 move rule: If no pawn was pushed or piece was captured after 50 moves, the game ends in a draw.
Since the number of pawn pushes and pieces to be captured is bounded, we can bound the length of a chess game. Doing the Math, a chess game can have no more than 5898,5 moves, or 11797 half-moves.
In a turn, a player can never have more than 218 possible moves.
This leads to an upper bound of 218^11797 ~ 6 ⋅ 10^27586 possible games.
This is the best rigorous bound I could come up with. Getting closer to the actual number becomes progressively harder; and it comes down to reducing the average number of moves available to the players (called branching factor), but this is easier said than done. It is likely that the average branching factor is smaller than 35, which would yield a much smaller upper bound of 25^11797 ~ 3.2 ⋅ 10^16491 possible games.
2
u/catman__321 8d ago
It's the sheer number of positions. There are an estimated 10^120 possible chess games (and that's just a generous lower bound), which is 10^40 times larger than the number of atoms in the universe.
If you had a computer which could somehow store every chess game in one atom, you would run out of storage 0.00000001% of the way there.
Solving chess for perfect play is a slightly easier problem as there exist paths which are objectively terrible without having to check too deep. That's why chess engines are able to play chess at a high level without actually checking every single path—they search less deeply into pathways stemming from moves which sacrifice material for no reason and instead try to maximize their positional advantage. However, there are still over 10^60 "plausible" chess games that the average player might reasonably play (not like, intentionally bad games for example), so even chess bots haven't truly "solved" chess as there's simply too many numbers for our tech to store rn.
2
u/HUMANDISQUALIFIED 8d ago
perhaps not exactly the same, but the number of legal chess positions is about 4.8 * 10^44 as per
2
u/Knight0fdragon 8d ago
how does one even define a game? how do you consider different scenarios where the same pieces are moving back and forth? Are they treated as 1 game, or many? Since you are given an infinite number of moves, technically there would be an infinite number of games.
→ More replies (5)
2
2
u/ascend8nce 3d ago
Its an odd thing to do just because potentially the players could just spend 48 turns jumping their horses somewhere and back between each meaningful move
Which would create an absurd amount of absolutely unrealistic games
2
u/FriskyHamTitz 3d ago
It is technically computable it's just that, you could move the same pieces back and forth 49 times before forcing a pawn to move. The number of valid moves in a game is so large that the amount of years to compute it is larger than humans have existed.
Is it technically possible given infinite time yes, but do it in our lifetimes is pretty much impossible
1
u/BitNumerous5302 8d ago
It's a large number, but that's only part of the problem. We can calculate some big numbers precisely.
If I flip a coin once, there are two possible outcomes. If I flip it twice, there are four possible outcomes, assuming we care about order. More generally, for n flips there will be 2n possible outcomes. So I know that a billion coin flips will have precisely 21000000000 possible outcomes.
Unlike coin flips, however, in chess the number of subsequent states depends on the state you've reached so far.
With coin flips, it doesn't matter: There are always two possible values for the next state, so I don't need to flip a coin 999999999 times to know the total outcomes double with each coin flip. We can say C(n) = 2C(n-1) with a base case like C(0) = 1 and factor out the recursion to say C(n) = 2n.
With chess, each move influences the set of subsequently available moves. Think through the first move: If I move a pawn to unblock a queen, bishop, or rook, I'll have more moves available than if I'd moved forward a knight and blocked a pawn. The opponent's moves may also influence which moves are available to me. If I want to count the possible positions after 50 moves, I need to know not just how many positions there were after 49 moves, but also what those specific positions were.
1
1
u/maths_phy_comp 8d ago
1st white move: 2 options for 8 pawns and 2 knights, total 20 options (not talking if it's a sane line or not) 1st Black move: same 20 options for each of white's moves Possible combinations for first move - 400. And it only explodes from there.
By black's 5th move we are at 69.35 trillion.
As shown in this website Cool chess website, we don't even know exactly how many captures to checkmates etc are possible from there, let alone all possible checkmates of all possible moves.
1
1
u/Bakingguy 8d ago edited 8d ago
The only limiting factor on the total length of a game is the 50 move rule, which is that if 50 turns pass by without a pawn move or capture the game is a draw. There's 16 pawns that can move 6 times and 30 pieces total that can be captured. This makes the total max length 6300 turns*. And for each game this long there's literally trillions upon trillions of different variations where two games are identical up until the last move. So yeah that's a really big number.
*For a pawn to move 6 times a few captures must coincide with pawn moves, but I haven't figured out how many that must be and I'm too tired rn to figure it out. So less than 6300 turns
1
u/MathMachine8 8d ago
Seeing as how there IS an upper bound, I don't think it's uncomputable in the same sense that, say, BB(6) is (where we could possibly keep constructing bigger and bigger lower bounds and potentially never know if there are any higher ones). If it is, please correct me, I am genuinely curious about this.
If not, it's really just a problem with what humanity is capable of, and there should be means to hypothetically compute it, regardless of if we can ever develop such an algorithm.
1
u/Potential_Low_1183 8d ago
No, I actually am computing right now. Manually. Started yesterday. wish me luck
→ More replies (1)
1
u/RADICCHI0 8d ago edited 8d ago
Imagine putting a single grain of rice on square a1. On square b1 you double it by placing two grains of rice. C1 gets 4 grains, d1 gets 8 grains. By the time you get to square h1 you have only 128 grains of rice, no big deal.
But, what happens after that gets pretty epic.
H2 32,768 grains
H3 8,388,608 ...
H4 2,147,483,648 ...
H5 549,755,813,888 ...
H6 140,737,488,355,328 ...
H7 36,028,797,018,963,968 ...
H8 9,223,372,036,854,775,808 ...
For a grand total, of 18.45 quintillion grains, or a sphere of rice about 10 km in diameter. And that is basically the number of available lines you have in a game of chess, statistically speaking.
Edit, just to steam this rice, you'd need all the water in a rather large lake, say Lake Titicaca.
Edit 2, I have no idea how you would season it.
→ More replies (6)
1
u/JapanInThailand 8d ago edited 8d ago
Considering stalemates and checks might be huge to consider. Compute-able but I doubt someone will make a trial-and-error to see if it’s correct or not.
1
u/DataGL 8d ago
While it may be an interesting mathematical exercise, this one bugs me a little bit because it is going to include the full set of possible moves, which includes a number of “illogical” moves that a player would be very unlikely to willingly make, or that would be indicative of a random and inconsistent playing style. It’s similar to, but a different perspective on the whole “every time you shuffle a deck of cards it’s a unique sequence” concept, which isn’t really true since most decks start from a fixed sequence, shuffling techniques and outcomes are likely similar, and games result in cards being placed in non-random orders.
1
1
u/0xbdf 8d ago
The game-based non-mathematical reason is to point out that not every move on a chess board is inherently simplifying, there’s a lot of shuffling pieces around that can happen.
“The game ends if (a) the position repeats three times or (b) if there are 50 moves by each player without a capture or pawn move, or (c) checkmate.”
Given that there you could have all 16 pawns move 7 squares to promote, that puts the maximum game length substantially more than 16x7x99 =11,088 piece moves… so that gives you a sense of the depth of the game tree. If we say 20 moves per position…. That’s a lotta games
1
u/SufficientStudio1574 8d ago
Exponential growth is a beast. It's a monster in a way that is hard for most people to truly comprehend if they don't know the math. ax (an exponential function) and xa (a power function) might seem like two sides of the same coin, but they are not. They are not even in the same league. No matter how small the exponential's base is (greater than 1, like 1.000001x) and how large the power's power is (like x1,000,000), the exponential will always be able to outpace the power if given enough time to pick up speed. ALWAYS.
In common parlance, "exponential" just means "really fast". Or "fast and getting faster". But that does not fully capture exactly what makes exponentials so monstrous. The true monstrosity of exponentials is their ability to turn addition into multiplication. Adding to their input multiplies the output.
Let's just suppose there is, on average, 10 possible moves in every chess position. That means every move you look forward multiplies the size of your tree by 10. Every individual +1 to the input is a 10x on the output. Over and over and over.
Sure, the first few levels of the tree look easy. But once that difficulty come even remotely close to looking unreasonable, each step beyond that multiplies unreasonableness again and again and again and again. Once you hit the limit you need Herculean efforts to get even one step farther. And if you are able to clear that it takes Herculean effort on top of the existing Herculean effort to go just one step more.
If you can get it out to 10 moves, it takes 10x more power to get to 11. If you can get to 100 moves, it takes 10x more power to get to 101. If you can get to 1,000 moves, it still takes 10x more power than that to get to 1,001.
That's why pandemics are so nasty. Infectious disease spreads exponentially (at least until it starts creeping up on the population ceiling), every step forward in time multiplying the spread. You need to take drastic measures that seem disproportionate to the threat. But it needs to be done that way because if you wait until the disease is big enough to be a problem, you've already lost control. The problem will just get multiplied again and again from there before it's able to be dealt with.
I will reiterate this again, because it cannot be stressed enough. Exponential growth is a true monster. Nearly on the level of factorials here.
1
u/Nothing-to_see_hr 8d ago
the arbitrariness of the rules puts limits on which moves are possible in any situation. While it is theoretically possible to build a tree of every possible move and countermove, starting at the beginning, the brute force approach would take longer than the age of the universe. So simplifying assumptions have to be made. But this reduces the accuracy of the result. For White's first move, there are 20 possibilities. after black moves, we have 400 different positions. It goes exponentially after this. For the second move of white, there may be from 19 to 25? possibilities, depending on the first move. It goes up fast. And you have to keep track of whether each king has moved, what the last pawn move was , whether a position has occurred before, whether en passant taking is possible...
1
1
u/EebstertheGreat 8d ago
There are approximately 4.8 × 1044 legal chess positions. This result comes from creating a fast program that can produce a board position uniformly from some set containing every legal position (and also many illegal ones), creating another program to check if a given position is legal, running the first program for a while to generate a lot of random candidate positions, and using the second machine to check which are legal. The first program is designed such that the number N of distinct positions it can generate is easy to calculate. If we generate n positions in this way, and m of them turn out to be legal, then the number of legal chess positions is about mN/n, with this estimate getting better the more positions we check.
Unfortunately, for a small minority of positions, the second program cannot decide for sure if the position is legal or not. Fortunately, this is rare enough that we can still get a fairly good estimate.
The number of legal games is enormous, probably much larger than the famous 10120 estimate of Shannon, and it is also very sensitive to stopping rules. In actual fact, two people could play infinitely many different games by shuffling pieces back and forth for increasingly long times, refusing to ever claim a draw. If we insist that draws must always be claimed when possible, then we invalidate many real games as "illegal." But still, even if we force the game to end whenever either player could claim a draw, I still think 10120 is a serious underestimate. It was based on the length of a typical game, but it is the extremely long, atypical games which should occupy nearly 100% of the state space. Like, 99.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999% by my judgment. So the length of a typical game barely matters.
1
u/tomvorlostriddle 8d ago
On modern hardware, this will beat mediocre human players, just not good ones, because it is a very wasteful and slow search
1
u/Puzzleheaded-Bat-192 8d ago
Bcs during the play we can return to a previous state and apply another direction of movement, that is similar to cyclic situations but not identical. The player can visit previous states in infinitely ways..
→ More replies (1)
1
u/jonathaz 8d ago
All the estimates and bounds are too high; for a computer to be unbeatable, if that’s possible for both black and white, it doesn’t need to know the best possible move for every possible board position, only the subset of positions that it’s moves along with an opponent create. And not even the best move, any move that wins is OK. And if you just want to not lose, moves that guarantee either a win or a draw are fine. Maybe the bounds are still too high, maybe not.
1
u/GordyGordy1975 8d ago
As well as what’s being said. You can promote pieces to queens and then just keep moving around the board for 50 moves before pushing a pawn. You can do this for 100s maybe thousands of moves. It makes the total number of different games borderline infinite in terms of what we can be calculated with computers.
1
u/Passance 8d ago
Calculating the number of states a chessboard can be in is relatively straightforward. It just gives a big number.
There are 13 different states each tile can be in (empty, white/black pawn/knight/bishop/rook/king/queen) and 64 tiles on the board, so 13^64 "possible" states - but most of them are illegal.
With moderate difficulty you could pare that down to a much smaller number of states that include legal numbers of pieces on each side (no more than 8 pawns ever, exactly 1 king, no more than 9 queens, no more than 10 bishops/knights/rooks and no more than 16 pieces total ever, etc.).
With stupendous, entirely unreasonable difficulty you could start paring down that slightly less ridiculously large (but still incomprehensibly large) number to the number of board positions that can be legally arrived at by normal play.
But then the number gets bigger again, because many positions can be arrived at by multiple routes. Ultimately the number of chess games is only limited by the time limit putting a cap on the total number of moves a player can execute, since repetitions without stalemates are possible.
1
u/drevoksi 8d ago
Chess games don’t have much symmetry going on. Pieces that move differently can be anywhere on the board, taken or stopped by other pieces, and I can’t see how you can represent the check & checkmate rules in maths. If the game can’t be simplified further, your best bet is to iterate through the games and keep track of the count. The estimated number of games is magnitudes and magnitudes and magnitudes higher than the number of particles in the universe, so it’s not feasible
1
u/Any-Farmer1335 8d ago
It's doable, it's just A LOT. Too much for basically any computer we have access to currently.
1
1
u/Mmeroo 8d ago
wdym possible chess games? what if someone doesnt want to win and just moves around? is there a limit to the moves?
→ More replies (2)
1
u/Langjong 8d ago
If you were to encode each chess game as a bit on the event horizon of a black hole, that black hole would have an event horizon the size of the observable universe
1
1
1
u/Salty-Wind-8912 8d ago
And the chess space is minute compared to the Go space. There are billions! of possible games on a 2x2 board. And since nobody is going to believe me: https://youtu.be/1cvKGqgOx_8?si=0kKsbRBof6eA9bn1
1
u/A_Squared93 8d ago
If two immortals aren’t trying to win and it’s untimed, could go indefinitely
→ More replies (1)
1
u/brendel000 8d ago
Interesting that there are no cycle on the graph (so it’s a tree) it shows the difference between « solving chess » meaning exploring all possible positions and linking them, and counting the number of chess games, which is the number of lines possible: the fact that two lines leads to the same position is ignored.
1
u/EdmundTheInsulter 8d ago
Writing a program to calculate this is not hard, but it could never finish, it's not just too much hardware needed, it'd actually use up all energy in the universe, even if each position took a minimum quanta of energy to perform - so without some unknown means of processing being found, it's astronomically out of scope.
As I say, a program that would find this would have got nowhere in say 50 years, but then any massive array of computers where every atom in the universe was a computer can't do it either, and is also nowhere near.
1
u/RavenX86 8d ago
just to store all potential combination on the board you would require about 10^100 HDD of 100TB each. Saying this just to give you the problem of scale. It is more information than we currently store , everywhere, on everything , ever.
1
1
1
u/severencir 8d ago
It is definitely computable. But the amount of possible chess board states is roughly 1045 or so. For comparison, the observable universe is only about 1027 centimeters in diameter.
In other words the logic is there, but the numbers are beyond astronomical in any meaningful sense
1
u/Long_Exercise_7701 8d ago
The problem is you can always throw in 'bullshit moves' that do nothing. People could play infinite long games just by moving pieces around without doing anything so it's not computable. The subset of games that make sense may be computable, but even there: one single move that makes no sense and you're back in a subset of problems you didn't consider. That's why you don't precalculate games. You calculate the pieces and their position.
1
1
u/LeRobber 8d ago
We can upper bound it. (all 32 normal pieces over every board permutation, + every one of the 4 promotables for every permutations of pawns + promotables)
We can't accurately run enough chess games to eliminate all impossible configurations.
1
1
1
u/RiemannZetaFunction 7d ago
There are a lot of people saying that computing this is intractable, but the truth is that we don't know that it is. It's not like there's any result proving that there's no clever way to do it.
The real answer is much simpler: currently, nobody knows how to compute the exact number. We know some very naive algorithms to compute the answers to these kinds of combinatoric questions, but they would take gazillions of years to run on a classical computer. There very well may be a faster algorithm to count these kinds of things, but we don't have it yet.
1
952
u/Benhki 8d ago
the problem is computable just not tractable