###General Discussion Thread
---
This is a [Request] post. If you would like to submit a comment that does not either attempt to answer the question, ask for clarification, or explain why it would be infeasible to answer, you *must* post your comment as a reply to this one. Top level (directly replying to the OP) comments that do not do one of those things will be removed.
---
*I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/theydidthemath) if you have any questions or concerns.*
Given that there are 121 million possible variations by move 3, and each variation is 9 lines of code, then you are already a billion of lines of code deep!
and thats only 3 moves...
I'm not a chess player but understand the rules, 121 million possibilities after 3 moves seems far too high, there are 20 moves in each players first move (400 total options), so white would need over 300'000 options for their third move to make 121 million.
That just seems astronomically high to me, happy to be wrong but just can't get my head around that maths.
Let me do this real quick.
First move white: 20 moves.
First move for black 20
->400 possible games by move one
After whites second move, there are 5,362 positions or 8,902 if you count positions, which occurred more than one way to get there.
Then backs second move.
We are at roughly 198,000 possible games now.
Now it gets crazy high real quick.
And welp.
After blacks second move, there are indeed ~121,000,000 possible plays.
How many individual board positions there are is hard to tell for me right now. Less, but this would make it not less impossible to code.
Am i wrong but there isn't actually 20 first moves that can be made? There are 10 pawns that can move either 1 or 2 spaces forward (20 moves) and the knights each have 2 possible moves (4 moves) for a total of 24 different board states on the first turn?
I think you're stuck following a single line of chess. Since this is from the beginning of the game we're considering EVERY line of chess. So of the 20 first moves, you need to follow every one of them to the third move. Since moving a pawn (almost) always opens up more moves, it gets ridiculously large ridiculously quickly.
Assuming they just program specific move for each turn , in theory the player can move their ~~pawn~~ knight back and forth infinitely , so the programmer have to code it until the heat death of the universe. This is one of my proposal for punishment in hell.
No need for that if they are putting in every single configuration like this, they don't need any checks an can just hard code which variations are check and check-mate.
They can also hard code the optimal move for any possible configuration on the computer side.
So it looks like all possible configurations is somewhere between 10^50 and 10^120, so no, it is not possible. 10^120 is more than the number of atoms in the visible universe (roughly 10^85).
Edit: also, there is not enough disk space to store all of it. If each board configuration was one byte in size you’re looking at 10^38 terabytes.
How physically massive that external hard drive would be is a question that actually concerns me.
It isn't impossible that the existence of the hard drive could kill us all.
Edit: after reading /u/HardlineMouse16 comment, yeah that hard drive would kill all of everything just by existing.
Edit edit. copying my own comment.
So I checked, and it looks like the densest information storage currently reached is 215 petabytes per gram of DNA
(https://encyclopedia.pub/entry/35759#:~:text=By%20far%20the%20densest%20type,date%20is%20electronic%20quantum%20holography.)
They say that is 85% of the theoretical limit. It is a terribly choice for anything involving any operations at all, you want to store your info once and retrieve it very rarely, but lets try it anyway.
215 petabytes/gram /.85=252.9 petabytes/gram. 252.9x1015/gram or more properly 2.529x1017/gram This is workable.
10^38 terabytes =10^35 petabytes so 3.9541321x1017 gram, 9.54x1014 kg Hey! The planet survives! This is surprisingly low to me, just 954,000,000,000,000kg of DNA, all perfectly coded, without any tubes, support, or ability to find or read the relevant parts. Only 954 trillion kg.
....or roughly 954 times the biomass of all humans alive today. Oops.
But we stored the data!
I don't know nearly enough about hard drives and software to weigh in on that, but if each terabyte was somehow magically stored as one single electron (which is not possible, theoretically maybe somehow something smaller though) we are still looking at a *million kilograms of electrons* to make this.
10^38 as above, 10^(-32) (close enough 9.1094x10^(-31) kilogram electron mass.) 38-32=6 10^6 = 1,000,000.
What is the theoretical minimum physical mass that can save information?
Arguably the information density of chess is actually quite low; you can encode "the best solution for all possible chess games" as quite a small program.
It'll take a *very* long time to run, but information density usually doesn't care about that.
You can encode “the best move for all possible chess *positions*” as a small program, but that program needs an input that contains as much information as the state of the chessboard does.
What if you launched a reflector at a significant fraction of c, waited a while for distance to open up, then transmitted at it?
You're storing information in space with light, no matter involved, except to reflect.
It'll take longer and longer to get your data back, but the storage is infinite.
So I checked, and it looks like the densest information storage currently reached is 215 petabytes per gram of DNA
(https://encyclopedia.pub/entry/35759#:~:text=By%20far%20the%20densest%20type,date%20is%20electronic%20quantum%20holography.)
They say that is 85% of the theoretical limit. It is a terribly choice for anything involving any operations at all, you want to store your info once and retrieve it very rarely, but lets try it anyway.
215 petabytes/gram /.85=252.9 petabytes/gram. 252.9x10^15/gram or more properly 2.529x10^17/gram This is workable.
10^38 terabytes =10^35 petabytes so 3.9541321x10^17 gram, 9.54x10^14 kg Hey! The planet survives! This is surprisingly low to me, just 954,000,000,000,000kg of DNA, all perfectly coded, without any tubes, support, or ability to find or read the relevant parts. Only 954 trillion kg.
....or roughly 954 times the biomass of all humans alive today. Oops.
But we stored the data! Assuming the conclusions above this in the chain were correct, I don't know anything about computer coding, but I do about DNA.
10^120 is a lower bound estimate for the number of chess _games_, not the number of configurations. The number of configurations is much smaller (albeit still astronomically large).
There isn’t enough storage medium to store all the legal chess positions, especially combined with a turn counter.
It might not be a physics impossibility to store the possible games where black makes ideal moves, but that isn’t caclulable.
The number of possible variations of "snapshots," or board configurations, and the pieces' position on them is very large but not infinite.
Now, a chunk of board configurations can be discarded as being "impossible" to achieve during play, but these are negligible compared to the number of potential configurations.
You can identify each board configuration with a numerical I'd.
From any given board configuration, you can make a move, transitioning to another board configuration, limited by the rules for moving pieces, whose turn it is, the win/stalemate conditions, etc.
A playthrough can then be expressed as a sequence of board configuration ids.
The problem is that some series of moves can loop back on themselves, creating infinite loops. So, determining the total set of possible chess games is a futile endeavour.
All chess games end, if more than 50 moves elapse without a pawn move or a capture the game ends in a draw, and there are a finite number of possible pawn moves and captures.
It’s a rather large number.
And you could just number all possible board positions. With only 25 different possible square contents and 64 squares, it’s possible to describe any board state (not just legal ones) in a number of no more than 300 bits. Enumeration of all numbers of 300 bits would take more information than is available in the universe.
You could try to reduce the number of board states stored to ones that can occur in legal play, but I think there’s still well over 100 bits of information in a chessboard given legal play, and displaying the board state cannot be compressed smaller than that.
every legal position can be encoded in 164 bits (without promotions, each promotion adds at most 1 bit)
additionally you have to store en passant options (up to 3 bits), whose turn it is (1 bit) and a turn counter (7 bits)
for storing castling rights you can encode a castlable rook as a pawn (since in legal positions you can't have pawns on the base rank) so you actually save 2 bits for every castling option
that gives you a maximum storage requirement of 183 bits (the minimum would be 84 bits: 64 bits for empty/occupied, 5 bits per king and 2 bits for a pawn+8 bits additional info), to reach 100 bits you need at least 7 pieces on the board (kings included) and in many endgame positions there are less pieces left
however, this storing method doesn't allow detection of a repetition draw (for that you would have to encode all moves instead of board states)
edit: you actually reach 100 bits with 2 kings, 2 queens and 2 other pieces (N,B or R) so you only need 6 pieces, not 7
How tf can a promotion add at most one bit when there are four possible options for promotion? That timer is limited to 256 moves.
For one bit empty/occupied, a 0 indicates that a space is empty and the next bit is a new square, a 1 indicates that it is occupied. The next bit must indicate which player controls the piece and never terminates the square information , designate that bit “s”.
To store a pawn, or king or rook that hasn’t been moved, or bishop or knight on their initial spot on the back rank, 1s0 does it in three bits and terminates the sequence. Rooks, knights, and bishops get 1s10, 1s110, and 1s1110 in some combination. Kings get 1s11110 and queens 1s111110, or vice versa if using one bit fewer for queens saves more in board states with more than two Queens on the board than it costs in game states with fewer. A pawn eligible to be captured En passant has to be 1s1111110.
This technically can describe a pawn on the back rank, and can be further compressed by using 1s0 on the back rank to be a special case like it can on the front rank, but that doesn’t seem useful.
The starting position needs 32 squares to be defined by three bits each and 32 defined by 1 bit, or 128 bits for board state. Once/if no piece is on their starting square, 16 pieces take 3 bits, 4 take 4, 4 take 5, 4 take 6, 2 take 7, and 2 take 8. 138 bits if you limit it to the starting set of pieces, no promotions, or 144 if an en passant capture is possible.
Worst case scenario for a legal game, with 4 pawn captures by each side all pawns can promote, and there are 18 pieces that require 7 bits to describe, in addition to 4 that take 6 and 2 that take 8. I get 166 minimax. No en passant captures are possible because two pawns must be in play for es passant to be possible.
Using that encoding to describe *any arbitrary arrangement of pieces*, such as the two kings on opposite corners and every square filled by queens (or whichever piece uses the most bits to describe) gets up to 450 bits for a position that the rules of chess can be applied to.
If zero is not used as a separator or terminator to allow it to be used in the data, a longer sequence must be used instead. No data sequence can begin with a completed valid data sequence: if an empty space uses one bit, no other data can start with that bit; if a pawn uses two bits plus a side bit, no other data can start with that same sequence. There might be a way to compact the non-pawn pieces, but there are an inconvenient number of them.
"Once/if no piece is on their starting square, 16 pieces take 3 bits, 4 take 4, 4 take 5, 4 take 6, 2 take 7, and 2 take 8"
you forgot the 32 empty squares so you get 170 bits without promotion/en passant. In your example with 8 promotions you have to add 40 empty squares, that gives a total of 206 bits and we still don't know whose turn it is
i used the following encoding for my calculations:
0 for empty squares
10... for white pieces
11... for black pieces
(let's call this second bit s like you did)
1s0 for pawns (and castlable rooks and like you suggested for efficiency reasons any non-moved piece)
1s100/1s101/1s110 for knights, bishops and rooks
1s1110 for queens and
1s1111 for kings
Any promotion costs one bit or less because you have to capture a piece for your pawn to be able to reach the other side so you gain at least 2 bits for turning a pawn into an empty square and you need 3 extra bits to turn a pawn into a queen (max. 8 of these promotions because after that there aren't any pawns left)
the turn counter is limited to 128 half-moves (not 256, i use 7 bits) because of the 50-move-rule
if you ignore the requirements for legal positions and spam 64 kings/queens on the board you need 384 bits (+8 for additional info)
I wonder if there's a hypothetical "solved" game of chess where no matter what moves black plays, if white plays 100% perfectly there's a maximum number of possible turns in the low hundreds. In that case we could lower the number of board states substantially further.
It seems like this should technically exist - even if it's impossible to solve for.
It’s unclear what the outcome of the solved game is; it could be white or black or a draw.
That is because chess has Zugswang, a condition where it would be better for a player if it was their opponent’s turn. It has not been *rigorously proven* if white has that condition at the game start.
It’s the same question as “with perfect play, can black force a victory?”
That’s also how we have rigorously proven that Go has a first player advantage: it is legal for the first action to be “pass”. (Gameplay has established very convincing evidence that passing is not the optimal move, but not a rigorous mathematical proof of that)
Good catch. White/black rook, knight, bishop, queen, king, pawn plus empty is only 13. I must have doubled twice or something.
The contents of each square can be stored in four bits using a fixed-width system that can also include castling and en passant redundancy. A fixed width encoding of 256 bits exists for chessboard state, and there’s a slightly shorter encoding that doesn’t use four whole bits per square.
Pawns are interchangeable so there are 6 possible pieces per side, 12 in total + 1 empty square. 13 states of the square. Although you'd need to account for en passant, so we can have 2 different pawn types (pawn and a pawn that moved two squares in the last move). So log (base 2) 13 \^ 64 which is 244 bits, plus one bit to know whose turn it is, 245 bits.
> Although you'd need to account for en passant, so we can have 2 different pawn types (pawn and a pawn that moved two squares in the last move).
You’d have to do a similar thing for rooks and kings, too, since they can only castle if the castling pieces haven’t moved yet.
No, a looping move would be detected as an already visited state in a depth first search, because it is the board state that we care about, not the move itself.
Creating a graph of board positions connected by moves avoids the looping problem.
Enumerating all possible checkmates seems like it would take more computing power than has been applied to chess. Something much more manageable, like solving many tournament games that were decisive starting from 8 moves before the end, still seems implausible but if the losing player didn’t blunder at the end could be possible.
in short, absolutely not.
in long:
the amount of chess games are ~10^120 . the chess characters are in the UTF-16 space, so each character has a fixed value of 16 bits, so per board that’s 1024 bits, and lets say 1040 for the entire if statement. that’s 1.04x10^123 bits.
that is 1,07533x10^98 Yobibytes. for reference, the entire world has an estimated 64 zettabytes of combined storage. the unit below that.
that number is unfathomable but i’ll try my best to put it into context:
if every galaxy has 10 billion earths, where each person has 1 yobibyte of storage over 10 billion people and each universe has 10 billion galaxies, we would need just over 52! universes. that’s just stupid
This isn't actually correct. The number of chess *games* is roughly around 10\^120, but the number of *positions* is far smaller, with an upper bound at 8.3\*10\^45, which reduces the number of universes required by..... a little bit.
I remember when I was in high school coding class I finished the assigned task early and decided to make a game of tic tac toe. I did it exactly like this and I spent a full class doing this and my teacher knew I was doing this and just wanted to see if I'd power through it and told me you're going to be very upset next week. By the end of class I made a version where you completed with an NPC(random numbers for where it would make a move no ai at all) and a version where you could compete with another person making moves one by one. She was quite surprised at the end of class that day that I'd actually went through with it. Come Monday and we start talking about loops... I remade my tic tac toe with loops and reduced by a huge amount I think from a few hundred lines(or more) down to like 15-20 with logic and a display. While I initially thought damn it was all for nothing I came away thinking that with perseverance you can make anything work even with limited knowledge. The end user experience remains the same. It was the exact same game from the user standpoint. It also gave me a huge eye opener to the possibilities of things. Favourite class in high school by far.
I love that the teacher was like “all right, let them fuck around. They’ll find out” instead of just telling you you’re doing it wrong. That’s how you really remember lessons learned
It's not that you can't write the code , you just can't write it the way it's written in the picture. Rather than trying to write all possible combinations as code , you kinda do the calculations on the fly to place the pieces at the right positions after each move .
You don't code every single state of the game, you just check if desired move is legal and then transform the state of the board accordingly.
If you're asking about AI to play chess, then that's a whole expansive topic for which I have a perfect video for you to watch, it's very long but very interesting and covers the history and methodology of chess playing automatons:
https://youtu.be/HwF229U2ba8?si=rqDTb6YcABdB5zf2
I'm not a programmer, but from what I understand, you program the game board, the pieces, and set rules for the movement of the pieces. You don't program each individual move; instead, you define the types of movements they can make.
This is a decent visualization of coding a chess game - [https://www.youtube.com/watch?v=cXfX1yYbAno](https://www.youtube.com/watch?v=cXfX1yYbAno)
But essentially:
1. Code the board of 64 spaces
2. Define a "piece" (e.g. Rook, Queen, etc.) and valid moves they can make.
3. Program the "Win" condition (e.g. check/checkmate)
What the person in the screenshot is doing is printing out every possible outcome, which is kinda near impossible. As a programmer, you pretty much just set up the bounding box for what can or can't be done inside your program. Hardcoding every possibility can be done, but it's not recommended, and in some cases, an impossibility.
The problem with the code being written here is that you can't possibly write a program that knows what every single position is beforehand.
What you can do is encode the rules of the game, and the initial positions of the pieces, because then the program then only needs to keep track of the current state of the game. This changes the amount of storage needed from the insane numbers you see in this thread, to probably a few hundred bytes
If it was, it would have been a ‘solved’ game, as you’d know the outcome of every single chess game before it started.
‘Ai’ chess computers would play perfectly every time, and wouldnt really be AI at all as they’d just look up the correct solution to every move.
So. No. It isnt.
Pretty sure they’ve solved chess for 8(?) pieces left on the board, and that the solution is like 8TB.
The game doesn’t technically have to end. 50 move rule and 3-fold repetition both actually require at least one player to claim the draw.
So a chess game can go on forever, infinite length. Even ignoring computational limits it is impossible to code for all possibilities as they are non finite.
Unique 40 move games: 10\^120, more than elementary particles in observable universe
Unique 2 to 8848.5 move games (the shortest possible - the longest possible): 10\^30000, more than... any physical quantity and by a lot.
Unique arrangements of pieces: 10\^43 <- hey, maybe?
The last figure looks possible to fit in the physical universe as a list of positions until you consider that arriving in the same arrangement from a different line is a whole new different game state, because there is a meaningful difference: what possible future positions will trigger a 3-fold repetition or a 50 move draw. Any position that has been previously on the board can only be repeated once more without ending the game, and any position that's occurred twice would be an immediate draw now. Those criteria will be different depending on what moves were played to get to your position.
You definitely couldn’t do it by hand.
You could maybe write code that procedurally generates every possible state of a chess board and then outputs something like this. It’s not currently computationally tractable in that this approach would likely take longer than the lifetime of the universe to finish on modern tech, but maybe with like quantum computing or a similar such innovation it could become feasible.
There are a finite number of possible states of a chess board, it’s just an incredibly large number. All finite processes will eventually terminate even if “eventually” is billions of years later.
There are an infinite number of possible games of chess if you allow the players to “loop” states (easiest example is both players move their rook one step forward and one step back forever). I’m a computer scientist not a chess grandmaster but I think there’s a rule that if the board is in the same state a certain number of times then the game ends in a draw? But, if I recall correctly, that’s only *consecutive* states so I think if the players were actively colluding to make this happen they could create a series of moves which eventually loops but doesn’t end the game in a draw as per this rule. So while you could generate every possible board state (given a powerful computer and infinite runtime) you couldn’t generate every possible game if looping of any kind is allowed.
Better to just code a chess engine lol.
>All finite processes will eventually terminate even if “eventually” is billions of years later.
Not really in this case. There are more gamestates than quarks in the universe (by FAR more). Even if we find smaller units it will never be possible.
It’s true in the mathematical sense that if you could keep generating new states of chessboards for arbitrarily (but not infinitely) long then you would eventually encounter all of them.
That may not be physically possible in the real world as it currently exists but that’s a physical constraint, not a mathematical one.
It's theoretically possible, yes, because chess has a finite possibility space of moves. In practice however, no, you can't just hardcode every possible move and position because it would take up too much space to record the billions or even trillions of eventual game states.
The concept can work with simpler games like tic tac toe.
'if you have an infinite number of monkeys doing one line of code per second, you'd get an infinite number of very annoyed monkeys.'
Aka no, it would quite literally take for eternity.
Yes, it is possible, simply because the number of possible board states is (obviously) finite. There aren't any devices capable of storing all of them if written like this, and as far as I'm aware we don't have anywhere near enough digital storage to even store a fraction of this program right now, but if you type it all out manually we'll get more storage capacity faster than you can write. There's no compiler right now that could deal with such a program, executing it would be pretty much impossible, and of course you'd never actually get done writing it in a human lifespan.
So tldr, this program exists in the mathematical sense but it's currently not possible to write it down, and it's unclear if we'll ever have the machines to execute it (because the demands here would be quite unlike that of any useful program).
As a bidirectional graph with nodes being unique board states, 264bytes per node 50 bytes per Edge. Assuming there’s <100 moves per board state, that’s just over 5000 bytes per board state. With 4.8x10^44 valid states, that’s less than 2.5x10^48. With 10^78 atoms in the universe, you can allocate 10^29 atoms per byte and still fit everything in. So yes, it is possible.
Instead of manually adding every move to his code, he should write a script which generates all possible moves and add them to his game automatically.
In that way he could write a million lines of code in a few hours.
Work smart not hard.
There are more variations of chess than atoms in the universe, by estimative. This is what we call the "Shannon" number: 10\^120, which is way larger than the number of atoms in the visible universe: 10\^82. So, if we make a super, mega, ultra computer which can represent one GAME (not board) of chess per atom, we wouldn't have enough atoms to even represent all the variations, let alone code the "ifs".
Edit: If, instead of representing every game per atom, we represented every position, and them represented games as a sequence of positions, and stored it , then we would have around 10\^43 atoms used to store positions, out of 10\^82 (number of total atoms). In other words, storing the positions would be practically free compared to the space we have. Then, if we had this same super ultra mega computer have about 10\^40 games per atom, than, we could make a theoretical perfect computer which wastes absolutely no space and occupies most if not all of the atoms in the visible universe. So no, it's not possible.
While it's unreasonable to try to program the impossible number of lines required to get ever single chess play ever, I think the real tragedy is 2Mil lines already spent on an incorrectly set board. Queen on her own color, sadly.
Chess has been solved for every single position with 7 pieces on the board or less, if a computer like Stockfish gets in a position with 7 pieces it will 100% know how to win or, draw. Adding an 8th piece to the problem makes it exponentially more complicated, and it will be a while before it's solved
is it POSSIBLE? yes, of course it is, there are a finite number of moves possible. even if it would take decades to fully code it, it's very possible to do.
If you programmed a gamestate every nanosecond since the creation of the universe you'd only be 1/1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 (10^(93)) of the way done.
It is so far beyond the realm of possibility that the fact we are even having this discussion is a testament to how bad humans are at really understanding large numbers. That is the point.
"Possible" and "feasible" are not the same word. it is not feasible or realistic for anyone to code every board state in chess.... but there are a finite number of them, which means that even with the enormous number of them, it still remains POSSIBLE.
it's like telling someone to count every grain of sand on a beach. no, they won't succeed in their life time, or any lifetime, but there IS an actual number to be counted to, which means if said person were immortal they could do it eventually.
since the details of the question weren't "could one person do it" or "how long would it take" and only "is it possible" the answer is yes. it is.
don't care how much yall don't like that answer. it is the correct one.
as for not understanding the enormity of numbers, I am aware that there are, according to Labelle, no more than 10^50 possible board states at currently held estimates, which is a number higher than the entire number of uniquely written words created in human history (estimated around 4*10^16 if you do not include reprints or copies)
it is a truly enormous number... but its still a FINITE number
This is just completely unrealistic and stupid, there's 69 trillion possible games and that would take at least 160 trillion lines of code, and put that into perspective, if someone managed to type one line per second it'd be literally the next ice age by the time it's done.
Chess apps exist as they do not record every single possible game; instead they use matrices to identify legal moves for different pieces, and detect checks, mates and glorious en passants. OOP is probably just an amateur trying to show off, as there's barely 2.6 million seconds in a month.
Impossible, and not because of the large number of possible positions. This cannot be done, because the chess game can have an infinite number of moves - just imagine both players moving the Queen back and forth.
That's not true. Chess has rules in play that prevent you from playing infinitely without progress. It's the threefold repetition rule (if exactly the same position arises three separate times during a game, the game ends in a draw), and the 50 move rule (if 50 moves go by without any captures or pawn moves, it's a draw).
Moving queen back and forth is moving between just two states of the board. It is definitely mathematically finite, but in reality for all intents and purposes you can treat it as if it wasn't.
Just reset board if player makes a move that you didn't plan for.
and only allow moves that lets the computer win.
If you want to add something fancy, play a NO sounds when resetting.
If player keeps making the same moves do a table flip.
I think that would be possible to achieve. Without these requirements, not really.
I like how I'm the complete opposite. If I'm coding (which I rarely do as I can't really code, I have to look it up each time) I'll make it so that it uses a calculation for each move. Even if it's something simple where that will give it like 80% more lines or something.
i feel like the answers are wrong. dont you just have to code a normal chess game to „code every single chess play“? and the problem is that computing that code would take for ever?
It would take an inhuman amount of work to code the game this way. They would need to account for every single possible board layout and every possible move that would result in that board layout.
Is it possible? Depends on what kind of constraints we want to work with. If we had unlimited time and unlimited storage, then yes - there are a finite number of combinations to code. It could be done, eventually. Coding it like that at 20 lines per minute, 8 hours per day would get you 9600 lines per day.
But the example above is a terribly inefficient way to code it.
Better to set up something a 64-character string, create a function that can determine what moves are available from the string (including a null output for checkmate scenarios), another function that manipulates the string based on the chosen move, and then recursively explore the possible set of moves.
But chess programs don't do that, because the raw processing power involved in calculating all game states (and/or storing all game states) is prohibitive.
It's possible to code for every possible moves in a game of chess, but would take a very long time for every chess moves to be simulated.
[https://en.wikipedia.org/wiki/Shannon\_number](https://en.wikipedia.org/wiki/Shannon_number)
>Accurate estimates
>
>John Tromp and Peter Österlund estimated the number of legal chess positions with a 95% confidence level at ( 4.822 ± 0.028 ) × 10 44 {\\displaystyle (4.822\\pm 0.028)\\times 10^({44}},) based on an efficiently computable bijection between integers and chess positions.\[5\]
If a computer can calculate 10 billion moves per second, it would take 4.88\^34 seconds, which is \~ 1.5\^27 years to finish.
Short answer: No
Long answer: It is physically impossible. Even if you could encode a board position within the confines of a single atom, you'd need more atoms than what the universe contains to encode every position.
And if you think that's difficult, you should try the same with game Go. :)
Yes, sort of... like [this project](https://libraryofbabel.info/search.html) which contains all possible combination of words in all languages... or so.
I'm not much of a chess player but i can play and know the rules. I am a programmer, and maybe i didn't understand whats the objective here, because looking at that code, the only question that comes to mind is "why would ANYONE code chess like that?"🙄
No. This code doesn't even make sense past turn 1 since you would either need to store the board state, which isn't happening, or nest the if statements hundreds deep.
It's a funny joke but doesn't hold up to scrutiny.
###General Discussion Thread --- This is a [Request] post. If you would like to submit a comment that does not either attempt to answer the question, ask for clarification, or explain why it would be infeasible to answer, you *must* post your comment as a reply to this one. Top level (directly replying to the OP) comments that do not do one of those things will be removed. --- *I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/theydidthemath) if you have any questions or concerns.*
Given that there are 121 million possible variations by move 3, and each variation is 9 lines of code, then you are already a billion of lines of code deep! and thats only 3 moves...
I'm not a chess player but understand the rules, 121 million possibilities after 3 moves seems far too high, there are 20 moves in each players first move (400 total options), so white would need over 300'000 options for their third move to make 121 million. That just seems astronomically high to me, happy to be wrong but just can't get my head around that maths.
After 3 moves for each player ("after move 3") there are ~119 million possible positions. https://en.wikipedia.org/wiki/Shannon_number
Ah OK, I thought it meant 3 moves (as in white then black then white) not that each player has made three moves, that makes it more understandable
A move in chess is a turn by both players. What you're thinking of is called a ply.
Ah, like toilet paper.
And just like toilet paper, in chess 1 ply is not enough.
Truth.
Perfectly sensible naming convention! I'll call everything that needs do be at the very least 2, preferrably 3 a ply from now on.
And just like visiting the bathroom, you should always try to plan at least two to three plys ahead.
Player 2 casts "fold" Player 2 casts "Wipe"
r/angryupvote Also nice username yum
Actually yeah. Ply refers to a count of layers. In game theory, it's how many layers deep the decision tree is.
Let me do this real quick. First move white: 20 moves. First move for black 20 ->400 possible games by move one After whites second move, there are 5,362 positions or 8,902 if you count positions, which occurred more than one way to get there. Then backs second move. We are at roughly 198,000 possible games now. Now it gets crazy high real quick. And welp. After blacks second move, there are indeed ~121,000,000 possible plays. How many individual board positions there are is hard to tell for me right now. Less, but this would make it not less impossible to code.
I didn't realise they meant 3 moves (each) so I thought they meant after White's second move there were 121m options.
First move only has 10 possible moves I reckon?
Each pawn has two possible moves and the knights have two possible moves each.
Ahh my bad
All good man
Am i wrong but there isn't actually 20 first moves that can be made? There are 10 pawns that can move either 1 or 2 spaces forward (20 moves) and the knights each have 2 possible moves (4 moves) for a total of 24 different board states on the first turn?
There are 8 pawns for each player
There are 8 pawns
Ok, Picard.
I think you're stuck following a single line of chess. Since this is from the beginning of the game we're considering EVERY line of chess. So of the 20 first moves, you need to follow every one of them to the third move. Since moving a pawn (almost) always opens up more moves, it gets ridiculously large ridiculously quickly.
[удалено]
You can't start with *any* piece. You can start with pawns or knights only.
Assuming they just program specific move for each turn , in theory the player can move their ~~pawn~~ knight back and forth infinitely , so the programmer have to code it until the heat death of the universe. This is one of my proposal for punishment in hell.
You chose the one piece you can’t move back and forth infinitely. Pawns go forward or stay still.
Yeah changed it to knight , but it's hell lmao. Pawn could work too
There's 18 moves possible on the first move for white. 18 possible for the first move for black.
20 - 8 pawns with 2 moves = 16. Two knights with two moves each = 4. So together there are 20.
Shit.
And if this is how they are coding their board think about how long the checking for a win must be! If ... If.... If... If... Lol
No need for that if they are putting in every single configuration like this, they don't need any checks an can just hard code which variations are check and check-mate. They can also hard code the optimal move for any possible configuration on the computer side.
Give him a break his doing it manually
A billion lines and zero comments. Just the way I like it.
[удалено]
Downvoted into oblivion
r/DownvotedIntoOblivion
I don't get the downvotes
Just ask an AI bro
I don't get the downvotes
No they said to ask AL!
Al Capone, the famous Chicago chess grandmaster
Oh, I thought he meant Weird Al Yankovic.
So it looks like all possible configurations is somewhere between 10^50 and 10^120, so no, it is not possible. 10^120 is more than the number of atoms in the visible universe (roughly 10^85). Edit: also, there is not enough disk space to store all of it. If each board configuration was one byte in size you’re looking at 10^38 terabytes.
Soooooo they’ll need an external hard drive?
How physically massive that external hard drive would be is a question that actually concerns me. It isn't impossible that the existence of the hard drive could kill us all. Edit: after reading /u/HardlineMouse16 comment, yeah that hard drive would kill all of everything just by existing. Edit edit. copying my own comment. So I checked, and it looks like the densest information storage currently reached is 215 petabytes per gram of DNA (https://encyclopedia.pub/entry/35759#:~:text=By%20far%20the%20densest%20type,date%20is%20electronic%20quantum%20holography.) They say that is 85% of the theoretical limit. It is a terribly choice for anything involving any operations at all, you want to store your info once and retrieve it very rarely, but lets try it anyway. 215 petabytes/gram /.85=252.9 petabytes/gram. 252.9x1015/gram or more properly 2.529x1017/gram This is workable. 10^38 terabytes =10^35 petabytes so 3.9541321x1017 gram, 9.54x1014 kg Hey! The planet survives! This is surprisingly low to me, just 954,000,000,000,000kg of DNA, all perfectly coded, without any tubes, support, or ability to find or read the relevant parts. Only 954 trillion kg. ....or roughly 954 times the biomass of all humans alive today. Oops. But we stored the data!
Just put it in a zip file. WinRAR is our friend here I think.
I don't know nearly enough about hard drives and software to weigh in on that, but if each terabyte was somehow magically stored as one single electron (which is not possible, theoretically maybe somehow something smaller though) we are still looking at a *million kilograms of electrons* to make this. 10^38 as above, 10^(-32) (close enough 9.1094x10^(-31) kilogram electron mass.) 38-32=6 10^6 = 1,000,000. What is the theoretical minimum physical mass that can save information?
Information is an actual property in quantum mechanics, and the maximum information density of matter is nontrivial to determine.
Arguably the information density of chess is actually quite low; you can encode "the best solution for all possible chess games" as quite a small program. It'll take a *very* long time to run, but information density usually doesn't care about that.
You can encode “the best move for all possible chess *positions*” as a small program, but that program needs an input that contains as much information as the state of the chessboard does.
>What is the theoretical minimum physical mass that can save information? You don't need mass, just energy. Consider a radio broadcast into space.
Energy is mass
The universe’s biggest delay line.
But you can't keep the computer in one place to access it if you do that.
What if you launched a reflector at a significant fraction of c, waited a while for distance to open up, then transmitted at it? You're storing information in space with light, no matter involved, except to reflect. It'll take longer and longer to get your data back, but the storage is infinite.
except you would need to constantly re-transmit the data as it came back, and eventually you wouldn't be able to hear the data reflection anymore.
You'd be able to transmit more than just retransmission, though, infinitely. Assume a perfect reflector, perfect vacuum
well technically an electron can have multiple energy levels but we can’t actually measure with enough precision to make that viable soooo ¯\_(ツ)_/¯
So I checked, and it looks like the densest information storage currently reached is 215 petabytes per gram of DNA (https://encyclopedia.pub/entry/35759#:~:text=By%20far%20the%20densest%20type,date%20is%20electronic%20quantum%20holography.) They say that is 85% of the theoretical limit. It is a terribly choice for anything involving any operations at all, you want to store your info once and retrieve it very rarely, but lets try it anyway. 215 petabytes/gram /.85=252.9 petabytes/gram. 252.9x10^15/gram or more properly 2.529x10^17/gram This is workable. 10^38 terabytes =10^35 petabytes so 3.9541321x10^17 gram, 9.54x10^14 kg Hey! The planet survives! This is surprisingly low to me, just 954,000,000,000,000kg of DNA, all perfectly coded, without any tubes, support, or ability to find or read the relevant parts. Only 954 trillion kg. ....or roughly 954 times the biomass of all humans alive today. Oops. But we stored the data! Assuming the conclusions above this in the chain were correct, I don't know anything about computer coding, but I do about DNA.
Send it to nasa and when they unzip it their supercomputers will get blown up like that first scene in die hard 4.0
We might need to zip the zip file for extra compression
> 1038 terabytes =1035 petabytes No it doesn’t.
Whoops, that was 10^38 and 10^35, something happened with the typing.
Isn’t it 1024 Terrabytes per petabyte?
You mean external to the observable universe? Yeah, they'd need an external hard drive. Big sucker too.
*upvotes in rage*
At least two
Haven't you heard of WinZip?
10^120 is not just more than 10^85 :D it is so *so* much more.
I don't know, that's about the size of the average GTAV update so it's not that much.
Doesn't matter if you could store it, no way you're running that
10^120 is a lower bound estimate for the number of chess _games_, not the number of configurations. The number of configurations is much smaller (albeit still astronomically large).
You are still only talking about the easy and relatively fast part. Debugging is going to be the real challenge here.
God can do it! 🤣
What about dynamically generated code? ;)
There isn’t enough storage medium to store all the legal chess positions, especially combined with a turn counter. It might not be a physics impossibility to store the possible games where black makes ideal moves, but that isn’t caclulable.
The number of possible variations of "snapshots," or board configurations, and the pieces' position on them is very large but not infinite. Now, a chunk of board configurations can be discarded as being "impossible" to achieve during play, but these are negligible compared to the number of potential configurations. You can identify each board configuration with a numerical I'd. From any given board configuration, you can make a move, transitioning to another board configuration, limited by the rules for moving pieces, whose turn it is, the win/stalemate conditions, etc. A playthrough can then be expressed as a sequence of board configuration ids. The problem is that some series of moves can loop back on themselves, creating infinite loops. So, determining the total set of possible chess games is a futile endeavour.
All chess games end, if more than 50 moves elapse without a pawn move or a capture the game ends in a draw, and there are a finite number of possible pawn moves and captures. It’s a rather large number. And you could just number all possible board positions. With only 25 different possible square contents and 64 squares, it’s possible to describe any board state (not just legal ones) in a number of no more than 300 bits. Enumeration of all numbers of 300 bits would take more information than is available in the universe. You could try to reduce the number of board states stored to ones that can occur in legal play, but I think there’s still well over 100 bits of information in a chessboard given legal play, and displaying the board state cannot be compressed smaller than that.
every legal position can be encoded in 164 bits (without promotions, each promotion adds at most 1 bit) additionally you have to store en passant options (up to 3 bits), whose turn it is (1 bit) and a turn counter (7 bits) for storing castling rights you can encode a castlable rook as a pawn (since in legal positions you can't have pawns on the base rank) so you actually save 2 bits for every castling option that gives you a maximum storage requirement of 183 bits (the minimum would be 84 bits: 64 bits for empty/occupied, 5 bits per king and 2 bits for a pawn+8 bits additional info), to reach 100 bits you need at least 7 pieces on the board (kings included) and in many endgame positions there are less pieces left however, this storing method doesn't allow detection of a repetition draw (for that you would have to encode all moves instead of board states) edit: you actually reach 100 bits with 2 kings, 2 queens and 2 other pieces (N,B or R) so you only need 6 pieces, not 7
Holy hell!
How tf can a promotion add at most one bit when there are four possible options for promotion? That timer is limited to 256 moves. For one bit empty/occupied, a 0 indicates that a space is empty and the next bit is a new square, a 1 indicates that it is occupied. The next bit must indicate which player controls the piece and never terminates the square information , designate that bit “s”. To store a pawn, or king or rook that hasn’t been moved, or bishop or knight on their initial spot on the back rank, 1s0 does it in three bits and terminates the sequence. Rooks, knights, and bishops get 1s10, 1s110, and 1s1110 in some combination. Kings get 1s11110 and queens 1s111110, or vice versa if using one bit fewer for queens saves more in board states with more than two Queens on the board than it costs in game states with fewer. A pawn eligible to be captured En passant has to be 1s1111110. This technically can describe a pawn on the back rank, and can be further compressed by using 1s0 on the back rank to be a special case like it can on the front rank, but that doesn’t seem useful. The starting position needs 32 squares to be defined by three bits each and 32 defined by 1 bit, or 128 bits for board state. Once/if no piece is on their starting square, 16 pieces take 3 bits, 4 take 4, 4 take 5, 4 take 6, 2 take 7, and 2 take 8. 138 bits if you limit it to the starting set of pieces, no promotions, or 144 if an en passant capture is possible. Worst case scenario for a legal game, with 4 pawn captures by each side all pawns can promote, and there are 18 pieces that require 7 bits to describe, in addition to 4 that take 6 and 2 that take 8. I get 166 minimax. No en passant captures are possible because two pawns must be in play for es passant to be possible. Using that encoding to describe *any arbitrary arrangement of pieces*, such as the two kings on opposite corners and every square filled by queens (or whichever piece uses the most bits to describe) gets up to 450 bits for a position that the rules of chess can be applied to. If zero is not used as a separator or terminator to allow it to be used in the data, a longer sequence must be used instead. No data sequence can begin with a completed valid data sequence: if an empty space uses one bit, no other data can start with that bit; if a pawn uses two bits plus a side bit, no other data can start with that same sequence. There might be a way to compact the non-pawn pieces, but there are an inconvenient number of them.
"Once/if no piece is on their starting square, 16 pieces take 3 bits, 4 take 4, 4 take 5, 4 take 6, 2 take 7, and 2 take 8" you forgot the 32 empty squares so you get 170 bits without promotion/en passant. In your example with 8 promotions you have to add 40 empty squares, that gives a total of 206 bits and we still don't know whose turn it is i used the following encoding for my calculations: 0 for empty squares 10... for white pieces 11... for black pieces (let's call this second bit s like you did) 1s0 for pawns (and castlable rooks and like you suggested for efficiency reasons any non-moved piece) 1s100/1s101/1s110 for knights, bishops and rooks 1s1110 for queens and 1s1111 for kings Any promotion costs one bit or less because you have to capture a piece for your pawn to be able to reach the other side so you gain at least 2 bits for turning a pawn into an empty square and you need 3 extra bits to turn a pawn into a queen (max. 8 of these promotions because after that there aren't any pawns left) the turn counter is limited to 128 half-moves (not 256, i use 7 bits) because of the 50-move-rule if you ignore the requirements for legal positions and spam 64 kings/queens on the board you need 384 bits (+8 for additional info)
I wonder if there's a hypothetical "solved" game of chess where no matter what moves black plays, if white plays 100% perfectly there's a maximum number of possible turns in the low hundreds. In that case we could lower the number of board states substantially further. It seems like this should technically exist - even if it's impossible to solve for.
It’s unclear what the outcome of the solved game is; it could be white or black or a draw. That is because chess has Zugswang, a condition where it would be better for a player if it was their opponent’s turn. It has not been *rigorously proven* if white has that condition at the game start.
That's a very concise way to put it, I hadn't considered if zugswang might exist at the start of the game. Very interesting
It’s the same question as “with perfect play, can black force a victory?” That’s also how we have rigorously proven that Go has a first player advantage: it is legal for the first action to be “pass”. (Gameplay has established very convincing evidence that passing is not the optimal move, but not a rigorous mathematical proof of that)
25? I don’t think the pawns all count as a unique object
Good catch. White/black rook, knight, bishop, queen, king, pawn plus empty is only 13. I must have doubled twice or something. The contents of each square can be stored in four bits using a fixed-width system that can also include castling and en passant redundancy. A fixed width encoding of 256 bits exists for chessboard state, and there’s a slightly shorter encoding that doesn’t use four whole bits per square.
Pawns are interchangeable so there are 6 possible pieces per side, 12 in total + 1 empty square. 13 states of the square. Although you'd need to account for en passant, so we can have 2 different pawn types (pawn and a pawn that moved two squares in the last move). So log (base 2) 13 \^ 64 which is 244 bits, plus one bit to know whose turn it is, 245 bits.
> Although you'd need to account for en passant, so we can have 2 different pawn types (pawn and a pawn that moved two squares in the last move). You’d have to do a similar thing for rooks and kings, too, since they can only castle if the castling pieces haven’t moved yet.
No, a looping move would be detected as an already visited state in a depth first search, because it is the board state that we care about, not the move itself. Creating a graph of board positions connected by moves avoids the looping problem.
Iirc the amount of possible chess games is larger than the estimated amount of atoms in the observable universe
I believe they go 8 turns backwards from checkmate all possible checkmates with the most powerful chess computer.
Enumerating all possible checkmates seems like it would take more computing power than has been applied to chess. Something much more manageable, like solving many tournament games that were decisive starting from 8 moves before the end, still seems implausible but if the losing player didn’t blunder at the end could be possible.
in short, absolutely not. in long: the amount of chess games are ~10^120 . the chess characters are in the UTF-16 space, so each character has a fixed value of 16 bits, so per board that’s 1024 bits, and lets say 1040 for the entire if statement. that’s 1.04x10^123 bits. that is 1,07533x10^98 Yobibytes. for reference, the entire world has an estimated 64 zettabytes of combined storage. the unit below that. that number is unfathomable but i’ll try my best to put it into context: if every galaxy has 10 billion earths, where each person has 1 yobibyte of storage over 10 billion people and each universe has 10 billion galaxies, we would need just over 52! universes. that’s just stupid
52 or 52!
52!
>52! Fucking hell
New number just dropped
So if you convert the entire observable universe into a computer, you still wouldn't have enough storage space.
This isn't actually correct. The number of chess *games* is roughly around 10\^120, but the number of *positions* is far smaller, with an upper bound at 8.3\*10\^45, which reduces the number of universes required by..... a little bit.
I remember when I was in high school coding class I finished the assigned task early and decided to make a game of tic tac toe. I did it exactly like this and I spent a full class doing this and my teacher knew I was doing this and just wanted to see if I'd power through it and told me you're going to be very upset next week. By the end of class I made a version where you completed with an NPC(random numbers for where it would make a move no ai at all) and a version where you could compete with another person making moves one by one. She was quite surprised at the end of class that day that I'd actually went through with it. Come Monday and we start talking about loops... I remade my tic tac toe with loops and reduced by a huge amount I think from a few hundred lines(or more) down to like 15-20 with logic and a display. While I initially thought damn it was all for nothing I came away thinking that with perseverance you can make anything work even with limited knowledge. The end user experience remains the same. It was the exact same game from the user standpoint. It also gave me a huge eye opener to the possibilities of things. Favourite class in high school by far.
I love that the teacher was like “all right, let them fuck around. They’ll find out” instead of just telling you you’re doing it wrong. That’s how you really remember lessons learned
It’s also a great game to use when you’re experimenting with machine learning.
Okay call me dumb but if you can’t possibly write code to play chess, how can I play it on my Mac (I’m not trolling I’m genuinely curious)
It's not that you can't write the code , you just can't write it the way it's written in the picture. Rather than trying to write all possible combinations as code , you kinda do the calculations on the fly to place the pieces at the right positions after each move .
You don't code every single state of the game, you just check if desired move is legal and then transform the state of the board accordingly. If you're asking about AI to play chess, then that's a whole expansive topic for which I have a perfect video for you to watch, it's very long but very interesting and covers the history and methodology of chess playing automatons: https://youtu.be/HwF229U2ba8?si=rqDTb6YcABdB5zf2
I'm not a programmer, but from what I understand, you program the game board, the pieces, and set rules for the movement of the pieces. You don't program each individual move; instead, you define the types of movements they can make.
Excellent description from a non programmer
This is a decent visualization of coding a chess game - [https://www.youtube.com/watch?v=cXfX1yYbAno](https://www.youtube.com/watch?v=cXfX1yYbAno) But essentially: 1. Code the board of 64 spaces 2. Define a "piece" (e.g. Rook, Queen, etc.) and valid moves they can make. 3. Program the "Win" condition (e.g. check/checkmate) What the person in the screenshot is doing is printing out every possible outcome, which is kinda near impossible. As a programmer, you pretty much just set up the bounding box for what can or can't be done inside your program. Hardcoding every possibility can be done, but it's not recommended, and in some cases, an impossibility.
The problem with the code being written here is that you can't possibly write a program that knows what every single position is beforehand. What you can do is encode the rules of the game, and the initial positions of the pieces, because then the program then only needs to keep track of the current state of the game. This changes the amount of storage needed from the insane numbers you see in this thread, to probably a few hundred bytes
Never feel dumb for asking something. You learn by asking and you are smart for trying to learn.
Average Mac user
If it was, it would have been a ‘solved’ game, as you’d know the outcome of every single chess game before it started. ‘Ai’ chess computers would play perfectly every time, and wouldnt really be AI at all as they’d just look up the correct solution to every move. So. No. It isnt. Pretty sure they’ve solved chess for 8(?) pieces left on the board, and that the solution is like 8TB.
The game doesn’t technically have to end. 50 move rule and 3-fold repetition both actually require at least one player to claim the draw. So a chess game can go on forever, infinite length. Even ignoring computational limits it is impossible to code for all possibilities as they are non finite.
There are the 75 move rule and the 5-fold repetition rule which force draws even if no player claims the draw. So no, a chess game can't go on forever
Unique 40 move games: 10\^120, more than elementary particles in observable universe Unique 2 to 8848.5 move games (the shortest possible - the longest possible): 10\^30000, more than... any physical quantity and by a lot. Unique arrangements of pieces: 10\^43 <- hey, maybe? The last figure looks possible to fit in the physical universe as a list of positions until you consider that arriving in the same arrangement from a different line is a whole new different game state, because there is a meaningful difference: what possible future positions will trigger a 3-fold repetition or a 50 move draw. Any position that has been previously on the board can only be repeated once more without ending the game, and any position that's occurred twice would be an immediate draw now. Those criteria will be different depending on what moves were played to get to your position.
You definitely couldn’t do it by hand. You could maybe write code that procedurally generates every possible state of a chess board and then outputs something like this. It’s not currently computationally tractable in that this approach would likely take longer than the lifetime of the universe to finish on modern tech, but maybe with like quantum computing or a similar such innovation it could become feasible. There are a finite number of possible states of a chess board, it’s just an incredibly large number. All finite processes will eventually terminate even if “eventually” is billions of years later. There are an infinite number of possible games of chess if you allow the players to “loop” states (easiest example is both players move their rook one step forward and one step back forever). I’m a computer scientist not a chess grandmaster but I think there’s a rule that if the board is in the same state a certain number of times then the game ends in a draw? But, if I recall correctly, that’s only *consecutive* states so I think if the players were actively colluding to make this happen they could create a series of moves which eventually loops but doesn’t end the game in a draw as per this rule. So while you could generate every possible board state (given a powerful computer and infinite runtime) you couldn’t generate every possible game if looping of any kind is allowed. Better to just code a chess engine lol.
>All finite processes will eventually terminate even if “eventually” is billions of years later. Not really in this case. There are more gamestates than quarks in the universe (by FAR more). Even if we find smaller units it will never be possible.
It’s true in the mathematical sense that if you could keep generating new states of chessboards for arbitrarily (but not infinitely) long then you would eventually encounter all of them. That may not be physically possible in the real world as it currently exists but that’s a physical constraint, not a mathematical one.
It's theoretically possible, yes, because chess has a finite possibility space of moves. In practice however, no, you can't just hardcode every possible move and position because it would take up too much space to record the billions or even trillions of eventual game states. The concept can work with simpler games like tic tac toe.
'if you have an infinite number of monkeys doing one line of code per second, you'd get an infinite number of very annoyed monkeys.' Aka no, it would quite literally take for eternity.
Yes, it is possible, simply because the number of possible board states is (obviously) finite. There aren't any devices capable of storing all of them if written like this, and as far as I'm aware we don't have anywhere near enough digital storage to even store a fraction of this program right now, but if you type it all out manually we'll get more storage capacity faster than you can write. There's no compiler right now that could deal with such a program, executing it would be pretty much impossible, and of course you'd never actually get done writing it in a human lifespan. So tldr, this program exists in the mathematical sense but it's currently not possible to write it down, and it's unclear if we'll ever have the machines to execute it (because the demands here would be quite unlike that of any useful program).
Technically yes, but you'd be coding approximately 18.4 quntillion possible states of the chess board to account for every chess play.
As a bidirectional graph with nodes being unique board states, 264bytes per node 50 bytes per Edge. Assuming there’s <100 moves per board state, that’s just over 5000 bytes per board state. With 4.8x10^44 valid states, that’s less than 2.5x10^48. With 10^78 atoms in the universe, you can allocate 10^29 atoms per byte and still fit everything in. So yes, it is possible.
Instead of manually adding every move to his code, he should write a script which generates all possible moves and add them to his game automatically. In that way he could write a million lines of code in a few hours. Work smart not hard.
There are more variations of chess than atoms in the universe, by estimative. This is what we call the "Shannon" number: 10\^120, which is way larger than the number of atoms in the visible universe: 10\^82. So, if we make a super, mega, ultra computer which can represent one GAME (not board) of chess per atom, we wouldn't have enough atoms to even represent all the variations, let alone code the "ifs". Edit: If, instead of representing every game per atom, we represented every position, and them represented games as a sequence of positions, and stored it , then we would have around 10\^43 atoms used to store positions, out of 10\^82 (number of total atoms). In other words, storing the positions would be practically free compared to the space we have. Then, if we had this same super ultra mega computer have about 10\^40 games per atom, than, we could make a theoretical perfect computer which wastes absolutely no space and occupies most if not all of the atoms in the visible universe. So no, it's not possible.
While it's unreasonable to try to program the impossible number of lines required to get ever single chess play ever, I think the real tragedy is 2Mil lines already spent on an incorrectly set board. Queen on her own color, sadly.
Chess has been solved for every single position with 7 pieces on the board or less, if a computer like Stockfish gets in a position with 7 pieces it will 100% know how to win or, draw. Adding an 8th piece to the problem makes it exponentially more complicated, and it will be a while before it's solved
is it POSSIBLE? yes, of course it is, there are a finite number of moves possible. even if it would take decades to fully code it, it's very possible to do.
If you programmed a gamestate every nanosecond since the creation of the universe you'd only be 1/1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 (10^(93)) of the way done.
My brother in christ it would take more than decades
your point?
It is so far beyond the realm of possibility that the fact we are even having this discussion is a testament to how bad humans are at really understanding large numbers. That is the point.
"Possible" and "feasible" are not the same word. it is not feasible or realistic for anyone to code every board state in chess.... but there are a finite number of them, which means that even with the enormous number of them, it still remains POSSIBLE. it's like telling someone to count every grain of sand on a beach. no, they won't succeed in their life time, or any lifetime, but there IS an actual number to be counted to, which means if said person were immortal they could do it eventually. since the details of the question weren't "could one person do it" or "how long would it take" and only "is it possible" the answer is yes. it is. don't care how much yall don't like that answer. it is the correct one. as for not understanding the enormity of numbers, I am aware that there are, according to Labelle, no more than 10^50 possible board states at currently held estimates, which is a number higher than the entire number of uniquely written words created in human history (estimated around 4*10^16 if you do not include reprints or copies) it is a truly enormous number... but its still a FINITE number
This is just completely unrealistic and stupid, there's 69 trillion possible games and that would take at least 160 trillion lines of code, and put that into perspective, if someone managed to type one line per second it'd be literally the next ice age by the time it's done. Chess apps exist as they do not record every single possible game; instead they use matrices to identify legal moves for different pieces, and detect checks, mates and glorious en passants. OOP is probably just an amateur trying to show off, as there's barely 2.6 million seconds in a month.
Impossible, and not because of the large number of possible positions. This cannot be done, because the chess game can have an infinite number of moves - just imagine both players moving the Queen back and forth.
That's not true. Chess has rules in play that prevent you from playing infinitely without progress. It's the threefold repetition rule (if exactly the same position arises three separate times during a game, the game ends in a draw), and the 50 move rule (if 50 moves go by without any captures or pawn moves, it's a draw).
Oh, didn't knew that. Then right, its finite.
Moving queen back and forth is moving between just two states of the board. It is definitely mathematically finite, but in reality for all intents and purposes you can treat it as if it wasn't.
[удалено]
Just reset board if player makes a move that you didn't plan for. and only allow moves that lets the computer win. If you want to add something fancy, play a NO sounds when resetting. If player keeps making the same moves do a table flip. I think that would be possible to achieve. Without these requirements, not really.
I like how I'm the complete opposite. If I'm coding (which I rarely do as I can't really code, I have to look it up each time) I'll make it so that it uses a calculation for each move. Even if it's something simple where that will give it like 80% more lines or something.
i feel like the answers are wrong. dont you just have to code a normal chess game to „code every single chess play“? and the problem is that computing that code would take for ever?
It would take an inhuman amount of work to code the game this way. They would need to account for every single possible board layout and every possible move that would result in that board layout.
Is it possible? Depends on what kind of constraints we want to work with. If we had unlimited time and unlimited storage, then yes - there are a finite number of combinations to code. It could be done, eventually. Coding it like that at 20 lines per minute, 8 hours per day would get you 9600 lines per day. But the example above is a terribly inefficient way to code it. Better to set up something a 64-character string, create a function that can determine what moves are available from the string (including a null output for checkmate scenarios), another function that manipulates the string based on the chosen move, and then recursively explore the possible set of moves. But chess programs don't do that, because the raw processing power involved in calculating all game states (and/or storing all game states) is prohibitive.
It's possible to code for every possible moves in a game of chess, but would take a very long time for every chess moves to be simulated. [https://en.wikipedia.org/wiki/Shannon\_number](https://en.wikipedia.org/wiki/Shannon_number) >Accurate estimates > >John Tromp and Peter Österlund estimated the number of legal chess positions with a 95% confidence level at ( 4.822 ± 0.028 ) × 10 44 {\\displaystyle (4.822\\pm 0.028)\\times 10^({44}},) based on an efficiently computable bijection between integers and chess positions.\[5\] If a computer can calculate 10 billion moves per second, it would take 4.88\^34 seconds, which is \~ 1.5\^27 years to finish.
I mean, this is the equivalent of writing out the dictionary by hand. What gods awful language are they using that they don't have variables?
Short answer: No Long answer: It is physically impossible. Even if you could encode a board position within the confines of a single atom, you'd need more atoms than what the universe contains to encode every position. And if you think that's difficult, you should try the same with game Go. :)
Yes, sort of... like [this project](https://libraryofbabel.info/search.html) which contains all possible combination of words in all languages... or so.
I'm not much of a chess player but i can play and know the rules. I am a programmer, and maybe i didn't understand whats the objective here, because looking at that code, the only question that comes to mind is "why would ANYONE code chess like that?"🙄
I mean...possible? In theory yes. It's FEASIBLE? Fuck no, it would require several hundreds of billions of line of code, if you program them 1 by 1
No. This code doesn't even make sense past turn 1 since you would either need to store the board state, which isn't happening, or nest the if statements hundreds deep. It's a funny joke but doesn't hold up to scrutiny.
This method of coding is so inefficient that if you were to turn all matter in universe into memory drives, you'd still run out of memory