5 ms·

Really interesting and close match, it was great listening to the expert player analyse the game and having the final score be uncertain until very late in the

by krig 11y ago

Really interesting and close match, it was great listening to the expert player analyse the game and having the final score be uncertain until very late in the game. I found the discussion around weaknesses in the Monte Carlo tree search algorithm interesting. It sounds like the opinion from the expert is that there are some inherent weaknesses in how MCTS tends to play moves against theoretical moves from the opponent that don't make sense; ie. that AlphaGo sees a potential win that would only happen if the human player made very bad moves. It's fascinating that the seeming weakness in AlphaGo would come from the algorithmic part of the AI and not the neural net. Could it be that as the neural net becomes stronger and stronger at the game, eventually the algorithmic part of it would become less useful to it? If that's the case, it really feels like this could be the path to truly general AI.

GolDDranks 11y ago
I think the "weakness" isn't that much of a weakness in the sense, that it's still playing optimally given it's search space – but it doesn't know how to overplay to make a comeback. (Overplay is a non-optimal play that is intended to be confusing for the opponent. AlphaGo doesn't regard it's opponent in any way, or assess what might be confusing for him, it just plays moves that it thinks are optimal.) A (min-max, alpha-beta-pruning) tree search is the optimal way to determine your best move if you can afford to search the situation space globally. However, as that's clearly impossible, there's clever ways to reduce the search space. Random pruning, as a "normal" monte carlo search would do, or semi-random pruning with a neural network estimating the situations, like AlphaGo does. However, as the search space is now non-global, it might exclude the optimal solution. And thus, the min-max-assumption doesn't hold: your opponent might come up with moves that you didn't think of, screwing your calculations off. If your opponent is a god ( = can afford global search space), or at least has a search space that is a strict superset of yours, it's "game over, man". But: if your opponent isn't a god, it's likely that his search space is NOT the same as yours. And you can exploit the fact. If you have any idea what kind of search space your opponent has, you can come up with moves, that he couldn't have included in his tree search, and bet on that his/her "hidden" moves aren't better than yours. Currently AlphaGo doesn't do that. It behaves like it'd be playing against... well, against another AlphaGo.
- krig 11y ago
  Right, but that seems like it'd be a limitation of algorithmic play, but not necessarily of the neural nets of AlphaGo - though since the neural nets are primarily built through AlphaGo playing against itself, I would suspect that such deep "flaws" would be difficult to root out.
  - GolDDranks 11y ago
    I'd imagine human players don't have as deep search trees as computers, but stronger policy networks. That means that you can exploit the humans by choosing move sequences that evaluate lowly up to some depth, and surge in value in the deepest depth. Also, I'd imagine that you could have a NN that tries to evaluate how "confusing" or "hard to read" a move is to human player, and use that as a factor in evaluating moves. But I'd imagine it's hard to find data for training that kind of a NN.
- taneq 11y ago
  > If your opponent [...] has a search space that is a strict superset of yours, it's "game over, man". Not necessarily. I think that's what we saw in game 4; that despite AlphaGo having a general advantage in terms of search space, it's still possible for the weaker of two strong-but-imperfect players to 'get lucky' and play a move that the stronger player didn't anticipate or account for.
  - GolDDranks 11y ago
    No, that's what search space means: that move sequence wasn't part of AlphaGo's search space. (The NN pruned it out.) If it was, it would've found it. That means that AlphaGo's search space was NOT a strict superset of Lee's.
  - Shaanie 11y ago
    If he didn't anticipate or account for that move, that means his search space wasn't a strict superset. Unless I'm missing something, you're essentially repeating what OP said after his "But: if your opponent isn't a god, it's likely that his search space is NOT the same as yours.".
seanwilson 11y ago
> It sounds like the opinion from the expert is that there are some inherent weaknesses in how MCTS tends to play moves against theoretical moves from the opponent that don't make sense; ie. that AlphaGo sees a potential win that would only happen if the human player made very bad moves. Why can these very bad moves not been pruned from the search?
- rincebrain 11y ago
  Some can, but as you can see with how human players commented on the early AlphaGo moves, you can't necessarily objectively quantify moves as "good" or "bad" correctly without exhaustive search, so you make an approximate prediction and go from there. But for every threshold of calculating that, you'll always either see moves that are just "good" enough to not be below the threshold (and get "why can't we prune these out"), or just "bad" enough to require it explore that space of the tree if a human player unexpectedly chooses them (e.g. the brilliant move that came in game 4, and AlphaGo's figurative loss of equilibrium.)

by krig 11y ago

GolDDranks 11y ago

I think the "weakness" isn't that much of a weakness in the sense, that it's still playing optimally given it's search space – but it doesn't know how to overplay to make a comeback. (Overplay is a non-optimal play that is intended to be confusing for the opponent. AlphaGo doesn't regard it's opponent in any way, or assess what might be confusing for him, it just plays moves that it thinks are optimal.) A (min-max, alpha-beta-pruning) tree search is the optimal way to determine your best move if you can afford to search the situation space globally. However, as that's clearly impossible, there's clever ways to reduce the search space. Random pruning, as a "normal" monte carlo search would do, or semi-random pruning with a neural network estimating the situations, like AlphaGo does. However, as the search space is now non-global, it might exclude the optimal solution. And thus, the min-max-assumption doesn't hold: your opponent might come up with moves that you didn't think of, screwing your calculations off. If your opponent is a god ( = can afford global search space), or at least has a search space that is a strict superset of yours, it's "game over, man". But: if your opponent isn't a god, it's likely that his search space is NOT the same as yours. And you can exploit the fact. If you have any idea what kind of search space your opponent has, you can come up with moves, that he couldn't have included in his tree search, and bet on that his/her "hidden" moves aren't better than yours. Currently AlphaGo doesn't do that. It behaves like it'd be playing against... well, against another AlphaGo.

krig 11y ago
Right, but that seems like it'd be a limitation of algorithmic play, but not necessarily of the neural nets of AlphaGo - though since the neural nets are primarily built through AlphaGo playing against itself, I would suspect that such deep "flaws" would be difficult to root out.
- GolDDranks 11y ago
  I'd imagine human players don't have as deep search trees as computers, but stronger policy networks. That means that you can exploit the humans by choosing move sequences that evaluate lowly up to some depth, and surge in value in the deepest depth. Also, I'd imagine that you could have a NN that tries to evaluate how "confusing" or "hard to read" a move is to human player, and use that as a factor in evaluating moves. But I'd imagine it's hard to find data for training that kind of a NN.
taneq 11y ago
> If your opponent [...] has a search space that is a strict superset of yours, it's "game over, man". Not necessarily. I think that's what we saw in game 4; that despite AlphaGo having a general advantage in terms of search space, it's still possible for the weaker of two strong-but-imperfect players to 'get lucky' and play a move that the stronger player didn't anticipate or account for.
- GolDDranks 11y ago
  No, that's what search space means: that move sequence wasn't part of AlphaGo's search space. (The NN pruned it out.) If it was, it would've found it. That means that AlphaGo's search space was NOT a strict superset of Lee's.
- Shaanie 11y ago
  If he didn't anticipate or account for that move, that means his search space wasn't a strict superset. Unless I'm missing something, you're essentially repeating what OP said after his "But: if your opponent isn't a god, it's likely that his search space is NOT the same as yours.".

seanwilson 11y ago

> It sounds like the opinion from the expert is that there are some inherent weaknesses in how MCTS tends to play moves against theoretical moves from the opponent that don't make sense; ie. that AlphaGo sees a potential win that would only happen if the human player made very bad moves. Why can these very bad moves not been pruned from the search?

rincebrain 11y ago
Some can, but as you can see with how human players commented on the early AlphaGo moves, you can't necessarily objectively quantify moves as "good" or "bad" correctly without exhaustive search, so you make an approximate prediction and go from there. But for every threshold of calculating that, you'll always either see moves that are just "good" enough to not be below the threshold (and get "why can't we prune these out"), or just "bad" enough to require it explore that space of the tree if a human player unexpectedly chooses them (e.g. the brilliant move that came in game 4, and AlphaGo's figurative loss of equilibrium.)