Hacker News Reader

Comment by sametmax | Hacker News Reader

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.

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.

Indeed, enumerating all

208168199381979984699478633344862770286522453884530548425 639456820927419612738015378525648451698519643907259916015 628128546089888314427129715319317557736620397247064840935

positions in Go is impossible.

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

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

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.

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.

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.

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.

Yes, you could if you preserved all intermediate counts. But the graph I used has 362 layers each of which can have up to 363 billion nodes, so I had to recycle the space used for the counts (4TB per layer). Also, I didn't even compute with full counts. I reconstructed them using the Chinese Remaineder theorem from 9 separate modular counts. So, yes it's possible, but highly impractical...

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.

I _love_ the way you stated this. Thank you!

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]

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:-?

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.

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.

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.

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.

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...

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

Reply on news.ycombinator.com