An English-language Go site with game commentary and analysis, notably of the AlphaGo versus Lee Sedol matches.
Commenters link its AlphaGo game analyses and reader comments on search and weak moves, and its profile of Go Seigen.
> What they've proved is that the same kind of intelligence required to play Go can be implemented with computer hardware. Before now, software couldn't beat a ranked human player at Go no matter how much computing power we threw at it.
I don't think that's quite true as a description of what we knew about computer Go previously, though it depends on what precisely you mean. Recent systems (meaning the past 10 years, post the resurgence of MCTS) appear to scale to essentially arbitrarily good play as you throw more computing power at them. Play strength scales roughly with the log of computing power, at least as far as anyone tested them (maybe it plateaus at some point, but if so, that hasn't been demonstrated).
So we've had systems that can in principle play to any arbitrary strength, if you can throw enough computing power at them. Though you might legitimately argue: by "in principle" do you mean some truly absurd amount, like more computing power than could conceivably fit in the universe? The answer to that is also no; scaling trends have been such that people expected computer Go to beat humans anywhere from, well, around now [1], to 5 to 10 years from now [2].
The two achievements of the team here, at least as I see them, are: 1) they managed to actually throw orders of magnitude more computing power at it than other recent systems have used, in part by making use of GPUs, which the other strong computer-Go systems don't use (the AlphaGo cluster as reported in the…
GoGameGuru just published a commentary of the game with some extra insight https://gogameguru.com/lee-sedol-defeats-alphago-masterful-comeback-game-4/
The author thinks that Lee Sedol was able "to force an all or nothing battle where AlphaGo’s accurate negotiating skills were largely irrelevant."
[...]
"Once White 78 was on the board, Black’s territory at the top collapsed in value."
[...]
"This was when things got weird. From 87 to 101 AlphaGo made a series of very bad moves."
"We’ve talked about AlphaGo’s ‘bad’ moves in the discussion of previous games, but this was not the same."
"In previous games, AlphaGo played ‘bad’ (slack) moves when it was already ahead. Human observers criticized these moves because there seemed to be no reason to play slackly, but AlphaGo had already calculated that these moves would lead to a safe win."
Which, I add, is something that human players also do: simplify the game and get home quickly with a win. We usually don't give up as much as AlphaGo (pride?), still it's not different.
"The bad moves AlphaGo played in game four were not at all like that. They were simply bad, and they ruined AlphaGo’s chances of recovering."
"They’re the kind of moves played by someone who forgets that their opponent also gets to respond with a move. Moves that trample over possibilities and damage one’s own position — achieving less than nothing."
And those moves unfortunately resemble what beginners play when they stubbornly cling to the hope of…
https://gogameguru.com/lee-sedol-defeats-alphago-masterful-comeback-game-4/
> This was when things got weird. From 87 to 101 AlphaGo made a series of very bad moves.
It seems to me, that these bad moves were a direct result of AlphaGo's min-maxing tree search.
According to @demishassabis' tweet, it had had the "realisation" that it had misestimated the board situation at move 87. After that, it did a series of bad moves, but it seems to me that those moves were done precisely because it couldn't come up with any other better strategy – the min-max algorithm used traversing the play tree expects that your opponent responds the best he possibly can, so the moves were optimal in that sense.
But if you are an underdog, it doesn't suffice to play the "best" moves, because the best moves might be conservative. With that playing style, the only way you can do a comeback is to wait for your opponent to "make a mistake", that is, to stray from a series of the best moves you are able to find, and then capitalize that.
I don't think AlphaGo has the concept of betting on the opportunity of the opponent making mistakes. It always just tries to find the "best play in game" with its neural networks and tree search – in terms of maximising the probability of winning. If it doesn't find any moves that would raise the probability, it picks one that will lower it as little as possible. That's why it picks uninteresting sente moves without any strategy. It just postpones the…
>No, I assure you that stockfish definitely does not look "all the way down (ie to states where the game is over)" in most positions, even with pruning - that would take too long. It uses a static evaluation function to evaluate positions without searching down the tree further
Ehh alright, it calculates the value of a node exactly (or exactly assuming its evaluation function). MCTS does not.
To be clear, what I meant, that you pulled out of context is that Minimax requires an exact calculation of the value of each child before choosing the best and returning it, this requires either simulating every possible game, or an evaluation function (depth-pruning). MCTS uses monte-carlo methods to estimate the best paths instead of trying all of them naively. At t=infinity, MCTS is equivalent to Minimax, because it will try all nodes. But it can run in time constrained systems better because it picks a much smarter order to run in.
>You described the "Monte Carlo" part of MCTS but not the "Tree Search" part. It's right in the name! See for example the first paragraph on page 20 of https://gogameguru.com/i/2016/03/deepmind-mastering-go.pdf, which clearly describes AG constructing a search tree.
yes. That has nothing to do with minimax though.
Which is what I said. AlphaGo uses pruning. AlphaGo doesn't use minimax with or without pruning, it uses MCTS (with pruning).
> No, stockfish uses minimax with pruning... Minimax actually needs to look at all possible branches all the way down.
No, I assure you that stockfish definitely does not look "all the way down (ie to states where the game is over)" in most positions, even with pruning - that would take too long. It uses a static evaluation function to evaluate positions without searching down the tree further.
> MCTS simulates games randomly and creates a distribution of expected value for each one based on some cool math.
You described the "Monte Carlo" part of MCTS but not the "Tree Search" part. It's right in the name! See for example the first paragraph on page 20 of https://gogameguru.com/i/2016/03/deepmind-mastering-go.pdf, which clearly describes AG constructing a search tree.
Minimax obviously will produce perfect play in both chess and Go, but we can't use it because it takes too long. Hence we prune and truncate the search tree. When we truncate it we use an approximation of the value of the node (the static evaluation function); when we prune we sometimes use the static evaluation function as well. This is true in both MCTS and in Stockfish.
>I wonder if AlphaGo has some specialized knowledge to handle ladders
Yes. A representation of ladders is among the input features of its neural networks.
https://gogameguru.com/i/2016/03/deepmind-mastering-go.pdf
Stone colour 3 Player stone / opponent stone / empty
Ones 1 A constant plane filled with 1
Turns since 8 How many turns since a move was played
Liberties 8 Number of liberties (empty adjacent points)
Capture size 8 How many opponent stones would be captured
Self-atari size 8 How many of own stones would be captured
Liberties after move 8 Number of liberties after this move is played
Ladder capture 1 Whether a move at this point is a successful ladder capture
Ladder escape 1 Whether a move at this point is a successful ladder escape
Sensibleness 1 Whether a move is legal and does not fill its own eyes
Zeros 1 A constant plane filled with 0
Player color 1 Whether current player is black
(The number is how many 19x19 planes the feature consists of.)