News for hackers. Stuff that matters.
Re:AlphaGo beats Lee Sedol again in match 2 of 5 by davelondon on Thursday March 10, 2016 @04:51AM (#11258215)
Let's compare Go and Chess. We all know that Go is more complex that Chess, but how much more?

There's 10^50 atoms in the planet Earth. That's a lot.

Let's put a chess board in each of them. We'll count each possible permutation of each of the chess boards as a separate position. That's a lot, right? There's 10^50 atoms, and 10^40 positions in each chess board so that gives us 10^90 total positions.

That's a lot of positions, but we're not quite there yet.

What we do now is we shrink this planet Earth full of chess board atoms down to the size of an atom itself, and make a whole universe out of these atoms.

So each atom in the universe is a planet Earth, and each atom in this planet Earth is a separate chess board. There's 10^80 atoms in the universe, and 10^90 positions in each of these atoms.

That makes 10^170 positions in total, which is the same as a single Go board.

Chess positions: 10^40 (https://en.wikipedia.org/wiki/Shannon_number) Go positions: 10^170 (https://en.wikipedia.org/wiki/Go_and_mathematics) Atoms in the universe: 10^80 (https://en.wikipedia.org/wiki/Observable_universe#Matter_con...) Atoms in the world: 10^50 (http://education.jlab.org/qa/mathatom_05.html)

Re:AlphaGo beats Lee Sedol again in match 2 of 5 by ekianjo on Thursday March 10, 2016 @05:41AM (#11258380)
I am not sure that calculating the raw number of positions is a good indication of complexity at a given point. What if most positions are obviously junk in go while they are more difficult to assess in chess? Not saying this is the case in this particular example but thats a possibility in theory.
Re:AlphaGo beats Lee Sedol again in match 2 of 5 by eru on Thursday March 10, 2016 @06:06AM (#11258466)
To illustrate your point: you can just add rows to a game of Nim (https://en.wikipedia.org/wiki/Nim) to get a truly enormous state space, without changing the simple winning strategy.
Re:AlphaGo beats Lee Sedol again in match 2 of 5 by masklinn on Thursday March 10, 2016 @05:56AM (#11258433)
> What if most positions are obviously junk in go while they are more difficult to assess in chess?

I wouldn't go with most (because I don't know about that), but many of these boards would also be either impossible to achieve (in a normal game) or illegal.

Re:AlphaGo beats Lee Sedol again in match 2 of 5 by aardvark179 on Thursday March 10, 2016 @06:07AM (#11258472)
The 10^170 figure is legal positions. It's about 1% of possible board positions. How many of those are sensible is another matter.
Re:AlphaGo beats Lee Sedol again in match 2 of 5 by pavelrub on Thursday March 10, 2016 @06:07AM (#11258476)
This doesn't seem to be the main reason why Go is harder than chess for computers. It was noted that even in 9x9 Go, with a comparable branching factor to Chess, traditional Go programs are still no stronger than on big boards. The main difficulty for Go is that it is much harder to evaluate board positions. So in Chess the depth of the search can be significantly reduced by using a reasonable evaluation function, whereas in Go no such function seems to exist.
Re:AlphaGo beats Lee Sedol again in match 2 of 5 by liviu- on Thursday March 10, 2016 @07:21AM (#11258748)
>It was noted that even in 9x9 Go, with a comparable branching factor to Chess, traditional Go programs are still no stronger than on big boards.

Are they not? MoGo beat pros of 9 Dan on 9x9 in 2011: https://www.lri.fr/~teytaud/mogo.html

Re:AlphaGo beats Lee Sedol again in match 2 of 5 by pavelrub on Thursday March 10, 2016 @08:41AM (#11259095)
Well, I guess it was more true before the advent of Monte Carlo Tree Search. Even so, note that even in the case of MoGoTW in 2011, it played blind Go (this helps the computer), and out of 4 games, won two games against a 9p player, and lost 1 game to a 5p player. Though it is perhaps better than MoGo's performance on 19x19, it still isn't very good, doesn't seem much better than MoGo on 13x13, and performs much worse than computer Chess, despite a similar branching factor.
Re:AlphaGo beats Lee Sedol again in match 2 of 5 by iopq on Thursday March 10, 2016 @11:50AM (#11260304)
The branching factor is much larger, around 75 legal moves after the opening, while chess has at most like 30.

Fuego beat a pro in 2008 using MCTS actually.

Re:AlphaGo beats Lee Sedol again in match 2 of 5 by pavelrub on Friday March 11, 2016 @05:26AM (#11265762)
The branching factor of 9x9 Go isn't 75. 75 could be the factor in early game, but the average factor is somewhere between 40 and 50, versus 35 in chess. State-space complexity is also considerably higher in Chess than in 9x9 Go.

Not sure what you meant regarding MCTS, I never said anything about MCTS not being able to beat pros.

Re:AlphaGo beats Lee Sedol again in match 2 of 5 by rurban on Thursday March 10, 2016 @09:06AM (#11259225)
This evaluation function does exist, and it's better than the super-simple chess evaluation function.

See, a chess program needs to find a lot of valid moves (see Deep Blue which won because it had stupid but extremely fast HW move generators), evaluate the moves and do a very deep search, up to 14, out of the very few alternatives. Russian chess programmers were better those times. They came up with AVL trees e.g. But hardware won.

In Go it's completely different. A move generator makes no sense at all, and a depth search of 14 neither. There are not a few alternatives, there are too many. What you need is a good overall pattern matching of areas of interest and an evaluation of those areas. And we saw that this feature outplayed Lee Sedol. Sedol couldn't quite follow in the recalculation of the areas.

Same as in chess AlphaGo learned the easy thing, that the center is more important than the corners, something Lee forgot during the game. But it's not a deep search, it's a very broad search, and very complicated evaluation function. A neural net is perfect for this function.

> whereas in Go no such function seems to exist.

It does exist. It's the neural net. It's a simple pattern recognizer, which learns over time more and more.

Re:AlphaGo beats Lee Sedol again in match 2 of 5 by kotach on Thursday March 10, 2016 @06:24AM (#11258531)
AlphaGo has a learned evaluation function for each move.

Evaluation function exists but it is not as simple as it can be for chess.

Re:AlphaGo beats Lee Sedol again in match 2 of 5 by claudius on Thursday March 10, 2016 @08:17AM (#11258956)
On the other hand, 2^565 is already slightly larger than 10^170. In other words, a couple of hydrogen atoms as quantum bits can perfectly well encode every possible position.
Re:AlphaGo beats Lee Sedol again in match 2 of 5 by no_wave on Thursday March 10, 2016 @07:17AM (#11258722)
Starcraft has way more possible board states
Re:AlphaGo beats Lee Sedol again in match 2 of 5 by taneq on Thursday March 10, 2016 @08:01AM (#11258888)
There's a Starcraft AI League (http://sscaitournament.com/) you might be interested in.
Re:AlphaGo beats Lee Sedol again in match 2 of 5 by justsaysmthng on Thursday March 10, 2016 @05:40AM (#11258377)
Why am I feeling a bit scared of all this ?
Re:AlphaGo beats Lee Sedol again in match 2 of 5 by __john on Thursday March 10, 2016 @02:55PM (#11261788)
The oldest and strongest emotion of mankind is fear, and the oldest and strongest kind of fear is fear of the unknown. -- H.P. Lovecraft