[boredguy8]

I like how Ken Jennings dealt with the 'Go complexity' analogy:

"Go is famously a more complex game than chess, with its larger board, longer games, and many more pieces. Google’s DeepMind artificial intelligence team likes to say that there are more possible Go boards than atoms in the known universe, but that vastly understates the computational problem. There are about 10^170 board positions in Go, and only 10^80 atoms in the universe. That means that if there were as many parallel universes as there are atoms in our universe (!), then the total number of atoms in all those universes combined would be close to the possibilities on a single Go board."

http://www.slate.com/articles/technology/technology/2016/03/...

[sametmax]

Comparing combinations with numbers of items is unfair.

In Go, the number of items is the number of pieces, and it's very small.

In the universe, the number of combinations of positions of all the atoms is, well, wonderful.

[harryjo]

I don't think anyone believes that Go is somehow more complex than the universe it is a subset of. The point is that enumerating all cases of Go is impossible and always will be, so more sophisticated analysis is required.

[tromp]

Indeed, enumerating all

208168199381979984699478633344862770286522453884530548425 639456820927419612738015378525648451698519643907259916015 628128546089888314427129715319317557736620397247064840935

positions in Go is impossible.

[ChristianBundy]

That's called "counting". Enumeration is iterative.

[dogecoinbase]

In your enumeration, what's the board look like at position 348277381979984699478633344862652779770286522453884530548425639456820927419612?

[tromp]

I can't say, because I didn't enumerate them. I only counted them. See

http://tromp.github.io/go/legal.html

for the method used, which is a form of dynamic programming.

[nhaehnle]

Though if it is dynamic programming, then it should be possible for you to answer dogecoinbase's question using not much more computational power than you used to count them in the first place, right?

If you think of dynamic programming as counting the number of paths in a directed graph (in this case, from skimming the paper, the nodes correspond to border states), then given a path number, you can trace the path backwards through the graph, as long as you remember the number of paths ending in every vertex.

[Jyaif]

1/ Convert the number to base 3.

2/ Each digit represents an intersection on the goban, assuming the following mapping: 0 = no stone, 1 = black stone, 2 = white stone.

[tromp]

That would work for all positions regardless of legality, which are in 1-1 correspondence to {0,1,2}^(19*19).

The count above is for legal positions only, i.e. those where every connected group of stones is adjacent to an empty point.

[vacri]

Sametmax's point is that you're comparing a simple count (atoms) to a factorial (combinations of pieces). For example, it's hardly surprising that 6! is larger than 6 - factorials grow much faster than simple counts.

[tomrod]

I _love_ the way you stated this. Thank you!

[deepnet]

Compared with a googol our Universe has negligible atoms , 10^100 - 10^80 = ~10^100

Compared with a googolplex (10^(10^100)) the entire Evrettian metaverse is negligible as (10^(10^100) - 10^80^2 * (average quarks in atom) * leptons(10^200) * dark multiplier(10^2) = ~1 googolplex

Has anyone ever used a googolplex for anything ?

[For ~ read approximately]

[lern_too_spel]

Graham's number - one googolplex raised to the googolplexed power =~ Graham's number, which has been used in a proof. There have been larger numbers used in proofs but none yet as famous as Graham's number, about which Martin Gardner wrote a popular mathematics article. http://iteror.org/big/Source/Graham-Gardner/GrahamsNumber.ht...

[skissane]

Rayo's number is so big it is almost impossible to convey how big it is. It is certainly much much much bigger than Graham's number. (Unlike Graham's number, it appears not to serve any useful purpose beyond winning "who can name the biggest number?" games.)

https://en.wikipedia.org/wiki/Rayo%27s_number

[tromp]

Matthieu Walraet "used" a googolplex as a lower bound on the number of possible Go games, in http://matthieuw.github.io/go-games-number/GoGamesNumber.pdf

Does that count:-?

[deepnet]

That is a staggering amount of possible Go games, no wonder tree search failed to improve without the Convnet pruning.

Makes me wonder if Deepmind could learn Go without first learning from the big dataset of expert games to train the convnet to prune the tree.

Which implies that Deepmind couldn't learn to play Go without first being taught by us (the expert games).

So AlphaGo learnt Go from us. It took a human brain to crack the problem of Go and the AI learned from our solutions it did not discover them itself - still a very great breakthrough.

Would Lee Sedol have won if he could use MCTS to assist his evaluation ?

( Arguably the MCTS is a non-AI component of deepmind & does not learn ).

MCTS = Monte Carlo Tree Search, where repeated random playouts evaluate moves by randomly sampling the tree of following (googolplex) possible moves.

[tromp]

The tree searched by MCTS is WAY smaller than a googolplex, since it excludes the eye-filling moves that allow games to go on past 400 or so moves.

[deepnet]

In the OP article Norvig suggests 10^172 possible games and games average 200 moves.

Walraet paper has 10^10^103, so 1000 googolplexes - this is very large.

Monte Carlo methods are specifically for guess-timating intractably big searches.

MCTS is close to the human heuristic for evaluating Go positions - counting who currently controls what, multiplied by the strength of each position (in Go 2 'eyes' make a block impervious to harm). Early on this is very subtle to discern - which makes Go a subtle art.

The human heuristic is complex, the MCTS random playout is overly simple but uses gigaflops of random sampling. MCTS was the basis of the best computer (the new innovation is the convnets that prunes the tree before MCTS).

The convnets are trained on a big database of expert games which is why I wonder if the MCTS is the differenting factor & Lee Sedol with an MCTS would beat the Convnet & MCTS.

This is important because: does AlphaGo plan ?

If not, the implication is planning is a poorer heuristic compared with whatever AlphaGo actually does.

The convnet provably doesn't plan, it estimates what a human expert would do and performs tne same whether playing game or just predicting next move from random configurations.

AI research has always held planning in high regard.

[iopq]

Actually, MCTS usually doesn't allow eye-filling. That's how it determines a game is over - all of the territory is "eyes". Otherwise, the playout would go on forever, or would stop at an arbitrary stopping point (board width * board length * 3 or something) which is not as accurate.

[Retric]

Don't conflate the "Observable Universe" with the actual Universe. We flat out don't know how big the actual Universe is. So, it could be 10^80, 10^800, or even A(10, 80)* Atoms.

*https://en.wikipedia.org/wiki/Ackermann_function

[dsfuoi]

It could be infinite.

[levemi]

If that is the case was the universe once finite and then went infinite during the early (big bang) expansion? I don't understand how something could have expanded if it was always infinite in size. I'm not even sure the concept of expansion even makes sense. What is infinite + 1? It's just infinite. It seems more like the expansion is a distribution of internal things.

[DonaldFisk]

You can see back as far as the Big Bang, approximately 14 billion years ago, so all matter in the visible Universe is within 14 billion light years of the Earth. However, the space the Universe occupies is only really finite if it's positively curved. If it's flat or negatively curved, the space it occupies is infinite, and if its density is constant, it must contain an infinite amount of matter even though we only see part of it. The Big Bang is a singularity - a point with infinite density. It's hard to get your head around intuitively, but it all makes sense mathematically. (The maths is pretty hard, and rarely covered at undergraduate level.)

The simplest model in rough agreement with observations is called the Einstein-de Sitter Model, and it's flat with a zero cosmological constant. See http://www.britannica.com/science/cosmology-astronomy/Relati...

More general models are covered here: https://en.wikipedia.org/wiki/Friedmann%E2%80%93Lema%C3%AEtr...

[dsfuoi]

Radius of the visible universe is actually 45.7 billion ly.

[DonaldFisk]

Thanks for the correction: https://en.wikipedia.org/wiki/Observable_universe

[DougWebb]

Off the cuff thought: the overall universe is infinite and not expanding, and it's only the visible universe that's expanding into that infinite space.

Now try to wrap your mind around this: someone that's one light year to the left is going to see a slightly different visible universe, also expanding, into the same infinite space. But if we look in their direction, we see the edge of our visible universe expanding into the void, but from their point of view looking in the same direction our edge is one light year short of their edge. So what's our edge expanding into?

[Razengan]

I've always wondered; is there a "last" galaxy in any direction, such that for an observer in that galaxy, no further light or radiation can be detected from that direction? (outside that galaxy)

That, must be a terrifying place to live in......

[zuminator]

The typical way to picture the universe is like the surface of an expanding balloon, a 2-manifold which happens to be embedded in 3-space. If you picture galaxies as spots on the balloon, there's no "last" galaxy, they're all roughly equidistant from their neighbors. Analogously, our Euclidean universe is thought of (in terms of noncompact spatial dimensions) as an expanding 3-manifold. There's no last galaxy there either. However, if you include time, then at some point in the distant future there will be a last galaxy because old stars will all burn out or be sucked into black holes. And further in the future protons will decay, so there will be no baryonic matter left, plus black holes will eventually evaporate. Much sooner than that though, the continued expansion of spacetime means that galaxies will in time disappear over the expanding cosmological horizon, and future lifeforms will know nothing of the universe outside their own aging galaxies. See: https://en.wikipedia.org/wiki/Future_of_an_expanding_univers...

[eru]

The last thing we can see with light in any direction is the background radiation. That's when light and matter separated.

That's why gravitational waves are such a big deal: they allow us to look further. (Not further than the limit imposed by the speed of light, though.)

[hasenj]

I think they would have to be at the edge of their galaxy for this effect to take place ..

[spydum]

Obviously I have no evidence, but my suspicions are that its like the pac-man world, it just continuously loops on itself. Its just really big...

[Razengan]

Too late to edit, but I must add that I'm not necessarily asking if there's an "edge" of the Universe.

[hellameta]

I don't see how our situation is any less terrifying haha

[Retric]

Math includes the idea of orders of infinity. There are infinite prime numbers, there are more positive integers, even more integers (positive and negative), even more rational numbers (A/B), and even more numbers (rational + irrational {e, Pi} etc)...

[pcmonk]

In what sense are there more rational numbers than prime numbers? They can be put into bijection with each other, so we generally think of them as being same infinity. There are more real nubmers, of course, by Cantor's diagonalization, so your basic point is true.

[Retric]

The set of all prime numbers is contained within the set of rational numbers, but they are rational numbers that are not within the set of prime numbers.

Cantor's diagonalization is simply demonstrating that same inequality by showing a number in set A is not in set B.

Just because you can map two infinity's to each other does not mean they are of the same size consider: Limit(0->inifinity) of (x - (x/2)) algebraically that's clearly Limit(0->inifinity) of X/2 which is infinity.

PS: What makes Cantor's diagonalization interesting is you can repeat it recursively an infinite number of times. This is more obvious in base 2.

[levemi]

Within a segment of numbers I understand how there are more rational numbers than integers, but I don't understand it in the context of infinity. How can there be more rational numbers than integers when in both cases there are infinite amounts? Are there mathematical operations or concepts that depend on this (in the context of infinity, not subsets)?

[jimm]

There are different kinds of infinity. The integers are countable, the real numbers aren't. You can prove that if you try to map each integer to some rational number, there will be some rational numbers that are not on that list --- there are more of them. See https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument.

[ambulancechaser]

in mathematics, we lose concept of how many and fall back to cardinality, which has a lose correlation with how many. So asking "are there the same number" of integers as rational numbers gets a little iffy until we make some definitions. We just say that we can create a bijection from integers to rationals. They each index the other, and for each thing in one, there is one and only one thing in the other. Does this mean there are the same "many"? Well loosely, and in the context of cardinality, yes. But things get weird because there are the same "many" of the whole as a subset (ie, there are as "many" even numbers as integers, as "many" positive numbers as positive and negative integers, etc).

But most people would disagree with you when you say "how can there be more rational numbers than integers..." because while we don't have a firm grasp of how many, we definitely would say that having the same cardinality means that there isn't some notion of "more".

I'm not sure what you mean by mathematical operations or concepts that depend on this.

[gnodar]

I don't know the answer to your question, but I can imagine how something can expand if it's infinite. Imagine an infinitelylong rubber band in front of you. Now imagine grabbing it with two hands and pulling them away from each other, causing the rubber band to stretch. If you take a sharpie, and paint dots on a spot representing planets or whatever else, they will pull away from eachother as you stretch the rubber band.

[stouset]

Take the set of positive integers (0, 1, 2…). Double them, so you have (0, 2, 4…). You had an infinite list of numbers, all "compact" (no room for more positive integers inbetween them), and with a simple mathematical transform, you've given yourself space for a second equally-sized infinity of integers to fit neatly inside of them.

[chinathrow]

It could be a simulation.

http://www.scientificamerican.com/article/are-we-living-in-a...

[randommodnar]

While this comparison highlights that yes, there are very many possible Go games, it's really apples to oranges.

The real comparison would be the number of pieces on a Go board (19x19 = 361) compared to the number of atoms in the universe. And then to compare the number of possible board positions in Go, with the number of possible atom positions in the universe, and in this case I think the universe wins.....

[dack]

especially considering all go boards exist _within_ the universe!

[IsaacL]

Go is very complex, and the fact that DeepMind could tackle this complexity is a huge technical achievement. No minimax-based AI could have tackled such a large state space.

However, other problems have even larger state spaces. Imagine writing an AI which read project Euler problem descriptions (in English) and output working code (in some given programming language). Keep outputs limited to 100-line scripts, max 80 characters per line.

There's roughly 100 usable characters in ASCII, so the possible space of 100-line programs is roughly:

(10^2)^(80 * 100) = 10^16000.

You could simplify this by having the AI work with predefined tokens rather than individual characters, but it's still a vast amount of combinations. Then consider 1000-line or 10000-line programs, and you see how high a mountain AI still has to climb. Humans are able to "compress" this state space via conceptual reasoning, which is much more complex than the "pattern recognition" many deep learning researchers are chasing.

(See "Introduction to Objectivist Epistemology" for more on how humans think in concepts - I'm planning to write more at some point on how this book shows where the practical limits of AI lie).

[tossaway1]

> the total number of atoms in all those universes combined would be close

Close?? Wouldn't it still be roughly 10 billion times smaller...?

[vidarh]

When you're dealing with numbers on the order of 10^80 to 10^170, I think you're entitled to calling that "close".

[Nevermark]

The ratio is 10^90 which is not small. The subtractive difference rounds to 10^170. In either case, I think its fair to say that 10^170 is unimaginably larger than 10^80.

But if differences become so large we cannot imagine the differences, then we could imagine there are no differences at all, so ... psychologically/subjectively there would be no difference?

[bmm6o]

The comparison in question is between 10^170 and 10^160 (= 10^80 * 10^80). So "just" a factor of 10^10.