Computer memory is not just “energy”, you need atoms to store information, and 1 bit requires much more than 1 atom.
4 Likes
Atoms are small units of matter, but they are made up of smaller particles: electrons, neutrons, and protons. The protons and neutrons are actually made up of even smaller particles, quarks. In our current understanding of physics, electrons, quarks, and other elementary particles are the smallest known units of matter/energy. It is possible that there might be even smaller units that are compose these elementary particles, which might help to explain and understand certain patterns observed in their properties, but these have yet to be discovered. Even some potential elementary particles (such as the graviton) remain hypothetical.
In an earlier post, I discuss how hopelessly large these numbers are, even if we could manage to store information at a subatomic scale:
As @jlt noted, the storage of information in a computer requires more than just energy, but also the physical structure of the circuits. The densest electronic storage of information comes from flash memory, which stores information by essentially charging energy into tiny electronic devices. However, storing each bit requires a separate device that is roughly on the scale of nanometers, and a cubic nanometer of material contains, roughly, quadrillions of atoms. Then, any practical use and manipulation of the stored information requires surrounding circuity and packaging, along with the rest of the computer system, which is many orders of magnitudes larger.
Beyond electronics, the highest density information storage seems to be an experimental DNA-based system, which seems to uses dozens of atoms per bit of information stored. From Density (computer storage) - Wikipedia
In 2012, DNA was successfully used as an experimental data storage medium, but required a DNA synthesizer and DNA microchips for the transcoding. As of 2012, DNA holds the record for highest-density storage medium.[12] In March 2017, scientists at Columbia University and the New York Genome Center published a method known as DNA Fountain which allows perfect retrieval of information from a density of 215 petabytes per gram of DNA, 85% of the theoretical limit.[13][14]
3 Likes
It’s better for me to stick to my history research then…
Although I am always curious about the possible legal positions of the board. After the scoring, say we stick with Chinese rule for simplicity, Each intersection should be either black or white (no idea how many seki would there be, but I feel they would be relatively few in portion), so wouldn’t that be close to 2361 than 3361? So realistically, if the game has to end, then the finished game positions should be more manageable in numbers?
And we don’t account for the time. Going from a starting fuseki which are totally manageable, at which point do them explode to unmanageable positions that required more “basic things” to represent them?
3 Likes
For 19x19 boards (and smaller), the exact number of legal positions (where all stones have liberties) has been calculated. See Counting Legal Positions in Go
It is this 171 digit number
208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935
The number of finished game positions should be fewer, but it could be a bit tricky to define what is exactly a finished game. For example, under Chinese rules, two players might both pass when there are only an even number of unimportant dame. Would that count as a finished game position?
Are you proposing that empty points be counted as either black or white, for the sake of enumerating board positions?
1 Like
No, stay interested! There’s nothing nicer than learning about a new subject 
…or empty, that’s why it’s 3361.
But are they? The first 10 stones can already be placed in approximately 361×360×359×…×351 ≈ 1028 different ways. If the earth was completely made out of sand, that would be comparable to the number of grains of sand it would have.
Fuseki seems totally manageable because we always play the same thing, but if we truly try to find every possible game, we’d already have serious trouble describing all possible first 10 moves.
5 Likes
In Chinese rule, a “finished” game has to fill all the dame, and all the intersections has to be white or black, with only seki situation and odd amount of shared intersections would there be one split shared intersection of half-and-half black/white. So it would be like changing one 2 to a 3 (360 will have to be black or white, and the final black or white or half-and-half). Unless we are counting positional super-ko, and theoretically it should be resolved in the end to finish a game.
2 Likes
Then the question would be if two games are considered different if one of the players had played an extra stone inside their territory at the end, before passing. In a sense it doesn’t really matter, of course, but how would you rigorously describe whether a move was useful or not?
1 Like
In Chinese rule, the answer for any settlement issue is simple (and complicated), determined by resuming actual play. So although the rule doesn’t specify players have to actually capture all the dead stones, in theory, a game in Chinese rule is truly only finished when each group only has two eyes left (or seki, or in weird super-ko cycles that can be truly complicated)
2 Likes
It sounds like a way of counting games that is a lot harder than simply counting legal board positions. I wouldn’t really know how to estimate the number of finished board positions like that, but I’m willing to bet that it’s still larger than the number of particles in the observable universe.
2 Likes
I read somewhere that currently storage capacity is passing 10 zettabytes in total, so I assume at cosmic scale, it is totally manageable to a degree (we can already store all possible first 8 moves, possibly 9 if rotation and mirror are deduced if we really want).
And my question is at which point is a super-being that can observe and catalog all variations as a game progressing will start to not able to comprehend the next move?
2 Likes
It’s a hard question to answer, what exactly do you count as a “super-being”?
If earth was replaced by memory storage, and 10TB of SSD storage takes up, with future technology, say, 10 grams, we’d reach somewhere around 1040 bits of data, which wouldn’t be enough for the first 15 moves.
2 Likes
Well, a super-being that can search all the cataloged positions it has seen using media (even every particle except itself is storage) to help find more variations for next moves that are legal. I suspect it would be still quite impossible all the way, but at which move would that be truly impossible?
1 Like
Doesn’t 1040 already sound truly impossible?
If we go a bit further, and only look at the first 30 moves, that would be comparable to the number of particles in the observable universe.
On a cosmic style, it’s very small I’d think. Nowhere near impossible, I’d say. That’s why I use super-being, that can search and process in an instant.
1 Like
Yes, but that’s too vague to really give an answer to. You’re basically not putting any physical constraints on this super-being, so how could I attach numbers to it? 
Well, I’d say first 30 to 40 moves solved would be interesting, since that would verify some fuseki theory right or not.
Does this mean AI no matter how powerful is still no-where near any possible super-being that theoretically exist to comprehend all games to find the divine move?
1 Like
How? We just catalogue the moves, but there’s no way to know if they’d actually be good or not.
There are waaaaaay too much possible games for any AI ever to verify a winning strategy by just searching through all possibilities. Some extremely clever mathematics needs to be discovered to actually verify a perfect strategy in an efficient way.
Moreover, computationally, this is already proven to be a very inefficient problem to solve: the amount of time and storage one needs to solve a game of go on a given board size increases at least exponentially (it’s an EXPSPACE-complete problem). According to this paper, 4x4 was solved in about 3.3 seconds, and 5x5 was solved in about 2.7 hours, so that’s an increase by a factor of 3000. So, continuing exponential growth with this factor means that solving 19x19 with this algorithm on our hardware would take 1048 hours. Note that the universe is currently about 1010 years old…
That is not to say that it is impossible to solve, since certain hard games can be solved without formulating an actual strategy. For example, in the game of Hex, under perfect play, the first player will win, since Hex has the nice property than any move you make can only be beneficial to you. If the second player had a winning strategy, then all the first player would have to do, is play an arbitrary first move, and then use the same winning strategy as the second player to win (which of course means the original strategy of the second player wasn’t in fact a winning strategy, thus such a strategy does not exist).
We have no clue whatsoever what this strategy of the first player is supposed to be, though.
2 Likes
I have a calculable related question (I think)
Assume every particle in the universe is a tiny little robot, that can randomly play a legal move using the simplest rule (like Tromp-Taylor rule). They play with each other simultaneously, and magically knew whether a game position has being tried or not (preventing positional super-ko issues), and would start an unfound new game when finishing one. If every game is finished in 1 seconds, how long would it take to search all possible games if using all particle as these tiny robots?
1 Like
Right, I was assuming a super-being would know the answer if a position it tried that position, but forgot a game has to be finished first.
1 Like
So, there’s 1080 little robots, each taking 1 second per game, and by:
there are at least 1010¹⁰⁰ many possible games.
So, it barely matters that you have this many little robots and that they’re working at a speed of 1 second per game, it will still take roughly 1010¹⁰⁰ many seconds, or million years, the order of magnitude is so large that it doesn’t really matter.
1 Like