4 ms·
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 o
by sametmax 11y ago
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.
- deepnet 11y agoCompared 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]
- tromp 11y agoMatthieu 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 http://matthieuw.github.io/go-games-number/GoGamesNumber.pdf Does that count:-?
- deepnet 11y agoThat 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 11y agoThe 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 11y agoIn 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 11y agoActually, 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.
- lern_too_spel 11y agoGraham'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.html http://iteror.org/big/Source/Graham-Gardner/GrahamsNumber.ht...
- skissane 11y agoRayo'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 https://en.wikipedia.org/wiki/Rayo%27s_number
- tomrod 11y agoI _love_ the way you stated this. Thank you!
- harryjo 11y agoI 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.
- vacri 11y agoSametmax'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.
- tromp 11y agoIndeed, enumerating all 208168199381979984699478633344862770286522453884530548425 639456820927419612738015378525648451698519643907259916015 628128546089888314427129715319317557736620397247064840935 positions in Go is impossible.
- dogecoinbase 11y agoIn your enumeration, what's the board look like at position 348277381979984699478633344862652779770286522453884530548425639456820927419612?
- Jyaif 11y ago1/ 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 11y agoThat 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.
- 11y ago