My friend, who was in chess club in HS and is an avid player still, beats me every time we play. I told him I was going memorise all trillion or so possible games and he'd never beat me again. He told me the number was way higher than trillions and that even super computers can't win by brute force.
When I got home this afternoon, I was curious. Wikipedia states that the number of possible moves is something like 10^47. Holy shit.
But I can't help but wonder why the exact number of legal moves hasn't been calculated.
Is it just extremely impractical or is it somehow logically impossible to make the calculation?
>But I can't help but wonder why the exact number of legal moves hasn't been calculated. Because it would LITERALLY take Millions of years for your current computers to do that.
Suppose the actual number is somewhere around 10^40 moves and we had a million CPU cores running at 10 GHz and that with every clock cycle we would find a new move on every core. These are VERY generous over simplifications
That gives 10*10^9 * 10^6 = 10^16 calculated moves per second and then 3,6*10^19 moves per hour then 8,64*10^20 moves per day then 3,1536*10^23 moves per year.
So if we do that for 3,17*10^16 years, then we will have calculated all moves. (If I made a mistake I am sorry.)
In other words the sun will have stopped shining before you calculated all moves.
Justin Brooks
next time try playing connect 4 with him, it's a much simpler game with a guaranteed win strategy for the first player.
Lincoln Roberts
>64 positions on the board. >32 starting pieces >Each piece has up to several possible moves, depending on the positions of the other pieces.
The number of moves you can make for a given board state is easy enough to calculate, just check which moves are legal. But, for every board state with N legal moves, the game proceeds to a new board state that has anywhere from no legal moves to the maximum amount of legal moves. Each of these states, in turn, leads into even more board states.
Let's say you play a game of chess where every turn, a legal move is picked at random. Is there any formula for the distribution of the number of legal moves at, say, turn 10? Not really. All we can do is try to find some numeric estimate by simulation. Using estimates like this, we're able to get some kind of grip on the number of legal games of chess.
Oliver Reyes
Computers can and have won literally by using brute force.
Joshua Brown
Autism, you clearly don't know math. Theorem: If things work kinda like this with small n then absolutely it also works like that for all n
Now apply the theorem: first construct and 2 by 2 chess board and calculate all thd possible moves. Then 3 by 3, 4 by 4 and so on until it becomes impractical.
If you notice a pattern of this as a function of the dimensions of the board then simply generalize by applying the previous theorem and then plug in n=8. Any pattern works, even Lagrange polynomials. It works
t. physicist
Andrew Walker
>But I can't help but wonder why the exact number of legal moves hasn't been calculated. because its infinite? i mean i can just move my knight around without doing anything
Christian Robinson
Are you saying the number of moves is infinite and therefore equal to -1/12? How can that be. How can there be a negative amount of moves?
Evan Campbell
>Is it just extremely impractical or is it somehow logically impossible to make the calculation? impossible.
you're asking for the number of nodes of the total gametree of chess. this is not something we can say anything about with certainty, it's just too huge
That's false, all chess computers start with heuristics since they cannot brute force from the first move. Then once the board is paired down they will brute force. Some programs even prefer to trade pieces in order to get to the brute force stage faster since they will have perfect strategy then.
Blake Cruz
nope, 3 move repetition and 50 move rule make the game tree of chess finite
Nathaniel Ross
>t. retard ftfy
Angel Sanchez
>3 move repetition *3 fold repetition
Connor Nelson
>Chess is infinite: There are 400 different positions after each player makes one move apiece. There are 72,084 positions after two moves apiece. There are 9+ million positions after three moves apiece. There are 288+ billion different possible positions after four moves apiece. There are more 40-move games on Level-1 than the number of electrons in our universe. There are more game-trees of Chess than the number of galaxies (100+ billion), and more openings, defences, gambits, etc. than the number of quarks in our universe!
Thomas Stewart
There are tons of chess moves, but the number of plausible high-level games is relatively small. It's a big number, but small enough that they repeat entire games all the time.
It's just like go. Once symmetry is broken, there are an incredible number of moves that can be made, but in any given board position there are only a handful of "correct" highest level moves.
Aiden Russell
>small enough that they repeat entire games all the time name a single example of two games that are exactly identical. games agreed to draw very early in the game (around move 30) dont count obviously
>It's just like go. Once symmetry is broken, there are an incredible number of moves that can be made, but in any given board position there are only a handful of "correct" highest level moves. thats a rather shallow analysis. in game theory there is a concept of heat. some moves are very "hot" and dont allow many alternative responses (think of a check in chess, it's very forcing). otoh there are loads of "quite" or "cool" positions where the number of sensible moves is still very high, and these positions continue throughout the middlegame
Brandon Parker
This upscaling n only works for checkers. I mean, which pieces are and aren't on the n=5 board?
Brayden Butler
Chess can't be represented with a DAG so counting possible moves is difficult
Elijah Anderson
We will have to wait for quantum computers to figure it out.
Matthew Smith
Can quantum computers count how many possible arrangements of quantum computers can count all the possible moves in chess?
Hudson Smith
>in HS reported
John Barnes
My primary question hasn't really been addressed though. You're all nothing on the impracticality of calculating it, and how modern computers could not do it. But what I found a genie and wished for a computer capable of performing an infinite amount of calculations instantly.
Would it be possible to program the logic for the calculation?
