7 ms·

I felt that Lee thought global sometimes, especially when he had time on the clock, but his mind could only take so much thinking, and time was catching up, so

I felt that Lee thought global sometimes, especially when he had time on the clock, but his mind could only take so much thinking, and time was catching up, so for a great many number of moves he thought locally. AlphaGo doesn't tire and thinks globally on every move. We saw that time and time again. Lee playing locally and AlphaGo surprising everyone with an unexpected move somewhere else on the board. Obviously it is better to be globally optimal than locally optimal.

highwind 11y ago
Doesn't principle of optimality state that if a solution is optimal than any of its sub problem must be optimal as well?
- wickawic 11y ago
  Instead of downvoting this comment, let me provide a counter example. Imagine the knapsack problem, where you can lift 10kg and you have a 10kg gold bar and 5kg cinderblocks. In this case solving 2 5kg knapsack problems will give you two cinderblocks, which is obviously not optimal. I don't know a lot about the strategy of go, but it seems to me that any play that doesn't take into account the entire state of the board is allowing for the same class of sub-optimal behavior as the example above.
  - felixgallo 11y ago
    the guy you're responding to is correct: https://en.wikipedia.org/wiki/Bellman_equation#Bellman.27s_Principle_of_Optimality https://en.wikipedia.org/wiki/Bellman_equation#Bellman.27s_P... and your attempted counterexample makes no sense (as the 'two cinderblocks' solution is not a subproblem of the optimal solution).
    - skybrian 11y ago
      Under this definition of "subproblem" the different parts of a Go board are not subproblems either. If the moves on different parts of a Go board didn't influence each other and could be solved separately via dynamic programming, it would be a much easier game (and probably uninteresting).
    - the_af 11y ago
      In what sense is he/she correct? In general, it's false that sub-problems of a problem with an optimal solution are optimal themselves.(Wikipedia's article says the same differently: "In computer science, a problem that can be broken apart like this is said to have optimal substructure.", implying some problems can't be broken apart like that). Also see: https://en.wikipedia.org/wiki/Optimal_substructure https://en.wikipedia.org/wiki/Optimal_substructure Maybe Go has this property of optimal substructure. Maybe it doesn't. I don't know, but it sure isn't immediately evident.
    - lorenzhs 11y ago
      From the very section of the article you quoted: "In computer science, a problem that can be broken apart like this is said to have optimal substructure." - There is no reason whatsoever that any problem could be broken down to this. In fact there are many problems for which it is known to be impossible. The article on optimal substructure lists a few.
      - daveguy 11y ago
        Yes. The principle of suboptimality only applies to problems which are optimally solved by dynamic programming. This is a small subset of problems and the knapsack problem is not one of those problems solved by dynamic programming. It does not have optimal substructure.
- pixl97 11y ago
  Imagine a condition where the local optima and global optima are not aligned.
- quietplatypus 11y ago
  Problem: One person remaining on island, 2 people left. Optimal solution: Kill yourself. Sub-optimal solution: Both live.
- sp332 11y ago
  But in Go you can only make one move at a time. So even if a move is optimal for one part of the board, there might be a different move that you should have made first.
leeoniya 11y ago
> Obviously it is better to be globally optimal than locally optimal. the implication of having machines dictate our behavior [WRT environment, each other] to optimize the survival of humans far into the future seems a bit closer to reality.
- asdfologist 11y ago
  I don't want to downplay the amazing breakthrough that AlphaGo represents, but I think it's a bit melodramatic to extrapolate from a program winning a board game to AI's impact on humanity's survival.
  - leeoniya 11y ago
    > winning a board game it's a board game of military strategy. while it is severly limited by its rules of play relative to real life, it is not inconievable that at some point it can dictate life and death as a capable military advisor. i think it is inevitable that we will utilize AI to make better predictions about our own future than weather forecasters. not in our lifetimes, of course.
    - asdfologist 11y ago
      You could have said the same thing about chess when a program beat Kasparov about 20 years ago.
      - leeoniya 11y ago
        the program that beat Kasparov did so using a brute-force search (full?) of a very limited search space. the reason that AI is different is because it doesnt need to (and cannot do so because the space is simply too large.) and 20 years ago is still well "within our lifetimes"
        Retric 11y ago
        The program that beat Kasparov avoided a full breadth first search because it was fairly easy to decide if something was a bad move. So, it could generally pick from a fairly small number of moves when branching. What makes GO so much harder than chess is how hard it is to evaluate the board and decide if a move is good or bad.
kotach 11y ago
AlphaGo is approximating global optimality by finding local optimality. Local optimality is already computationally very hard, but it is exactly what AlphaGo is doing. The rollouts they are doing, evaluating every probable move, it is a search process of trying to find local optimality. You have a current state of the board and you're trying to find a decision that minimizes your future regret. It is by definition local optimality. Global optimality would be finding a sequence of moves that wins you a game.
- robotresearcher 11y ago
  > Global optimality would be finding a sequence of moves that wins you a game. Is it known that Go is winnable? It may be that only a draw could be guaranteed. A globally optimal player would be provably able to do (whichever of these it turns out to be) for any legal position. This is harder than winning a particular game.
  - kotach 11y ago
    7.5-point komi variant played by AlphaGo and Lee has a win or lose outcome. There's no draw. But yes, a more formal definition of global optimality does not include victory as a necessary outcome.
    - robotresearcher 11y ago
      Wikipedia says: "the stronger player will typically play with the white stones and players often agree on a simple 0.5 point komi to break a tie ("jigo") in favor of white." Which suggests ties can occur in practice with human players, but are then broken wrt an external parameter. In terms of optimality, is it known in Go whether an optimal player can force a win against (i) all suboptimal players; and (ii) another optimal player, based on whether they play first or second? I realize we don't know the optimal policy but sometimes we can decide (non)-existence anyway. Anyone happen to know for Go?
      - kotach 11y ago
robotresearcher 11y ago
For reference, AlphaGo is not globally optimal. Go is much too big for that. (edit: also there'd be no point playing a game against it!)
- Radim 11y ago
  I believe the OP refers to global/local as they are used in Go. There, global/local play is a concept taken for granted by humans, with explicit names like "sente" and "tenuki". I think the OP simply implies AlphaGo doesn't seem bound by these human cognitive crutches. This is not the same as "global" in the theoretical sense, as in "finding the perfect solution / exhaustive proof". See also "game temperature" [1] [1] http://senseis.xmp.net/?Temperature http://senseis.xmp.net/?Temperature
  - reikonomusha 11y ago
    What he's saying is that if AlphaGo played optimally, there'd be No point in playing.
  - atrudeau 11y ago
    Correct. Google seems to agree: "AlphaGo has the ability to look “globally” across a board—and find solutions that humans either have been trained not to play or would not consider." [1] [1] https://googleblog.blogspot.com.br/2016/03/what-we-learned-in-seoul-with-alphago.html https://googleblog.blogspot.com.br/2016/03/what-we-learned-i...
deleted 11y ago
[deleted]

highwind 11y ago

Doesn't principle of optimality state that if a solution is optimal than any of its sub problem must be optimal as well?

wickawic 11y ago
Instead of downvoting this comment, let me provide a counter example. Imagine the knapsack problem, where you can lift 10kg and you have a 10kg gold bar and 5kg cinderblocks. In this case solving 2 5kg knapsack problems will give you two cinderblocks, which is obviously not optimal. I don't know a lot about the strategy of go, but it seems to me that any play that doesn't take into account the entire state of the board is allowing for the same class of sub-optimal behavior as the example above.
- felixgallo 11y ago
  the guy you're responding to is correct: https://en.wikipedia.org/wiki/Bellman_equation#Bellman.27s_Principle_of_Optimality https://en.wikipedia.org/wiki/Bellman_equation#Bellman.27s_P... and your attempted counterexample makes no sense (as the 'two cinderblocks' solution is not a subproblem of the optimal solution).
  - skybrian 11y ago
    Under this definition of "subproblem" the different parts of a Go board are not subproblems either. If the moves on different parts of a Go board didn't influence each other and could be solved separately via dynamic programming, it would be a much easier game (and probably uninteresting).
  - the_af 11y ago
    In what sense is he/she correct? In general, it's false that sub-problems of a problem with an optimal solution are optimal themselves.(Wikipedia's article says the same differently: "In computer science, a problem that can be broken apart like this is said to have optimal substructure.", implying some problems can't be broken apart like that). Also see: https://en.wikipedia.org/wiki/Optimal_substructure https://en.wikipedia.org/wiki/Optimal_substructure Maybe Go has this property of optimal substructure. Maybe it doesn't. I don't know, but it sure isn't immediately evident.
  - lorenzhs 11y ago
    From the very section of the article you quoted: "In computer science, a problem that can be broken apart like this is said to have optimal substructure." - There is no reason whatsoever that any problem could be broken down to this. In fact there are many problems for which it is known to be impossible. The article on optimal substructure lists a few.
    - daveguy 11y ago
      Yes. The principle of suboptimality only applies to problems which are optimally solved by dynamic programming. This is a small subset of problems and the knapsack problem is not one of those problems solved by dynamic programming. It does not have optimal substructure.
pixl97 11y ago
Imagine a condition where the local optima and global optima are not aligned.
quietplatypus 11y ago
Problem: One person remaining on island, 2 people left. Optimal solution: Kill yourself. Sub-optimal solution: Both live.
sp332 11y ago
But in Go you can only make one move at a time. So even if a move is optimal for one part of the board, there might be a different move that you should have made first.

leeoniya 11y ago

> Obviously it is better to be globally optimal than locally optimal. the implication of having machines dictate our behavior [WRT environment, each other] to optimize the survival of humans far into the future seems a bit closer to reality.

asdfologist 11y ago
I don't want to downplay the amazing breakthrough that AlphaGo represents, but I think it's a bit melodramatic to extrapolate from a program winning a board game to AI's impact on humanity's survival.
- leeoniya 11y ago
  > winning a board game it's a board game of military strategy. while it is severly limited by its rules of play relative to real life, it is not inconievable that at some point it can dictate life and death as a capable military advisor. i think it is inevitable that we will utilize AI to make better predictions about our own future than weather forecasters. not in our lifetimes, of course.
  - asdfologist 11y ago
    You could have said the same thing about chess when a program beat Kasparov about 20 years ago.
    - leeoniya 11y ago
      the program that beat Kasparov did so using a brute-force search (full?) of a very limited search space. the reason that AI is different is because it doesnt need to (and cannot do so because the space is simply too large.) and 20 years ago is still well "within our lifetimes"
      - Retric 11y ago
        The program that beat Kasparov avoided a full breadth first search because it was fairly easy to decide if something was a bad move. So, it could generally pick from a fairly small number of moves when branching. What makes GO so much harder than chess is how hard it is to evaluate the board and decide if a move is good or bad.

kotach 11y ago

AlphaGo is approximating global optimality by finding local optimality. Local optimality is already computationally very hard, but it is exactly what AlphaGo is doing. The rollouts they are doing, evaluating every probable move, it is a search process of trying to find local optimality. You have a current state of the board and you're trying to find a decision that minimizes your future regret. It is by definition local optimality. Global optimality would be finding a sequence of moves that wins you a game.

robotresearcher 11y ago
> Global optimality would be finding a sequence of moves that wins you a game. Is it known that Go is winnable? It may be that only a draw could be guaranteed. A globally optimal player would be provably able to do (whichever of these it turns out to be) for any legal position. This is harder than winning a particular game.
- kotach 11y ago
  7.5-point komi variant played by AlphaGo and Lee has a win or lose outcome. There's no draw. But yes, a more formal definition of global optimality does not include victory as a necessary outcome.
  - robotresearcher 11y ago
    Wikipedia says: "the stronger player will typically play with the white stones and players often agree on a simple 0.5 point komi to break a tie ("jigo") in favor of white." Which suggests ties can occur in practice with human players, but are then broken wrt an external parameter. In terms of optimality, is it known in Go whether an optimal player can force a win against (i) all suboptimal players; and (ii) another optimal player, based on whether they play first or second? I realize we don't know the optimal policy but sometimes we can decide (non)-existence anyway. Anyone happen to know for Go?
    - kotach 11y ago

robotresearcher 11y ago

For reference, AlphaGo is not globally optimal. Go is much too big for that. (edit: also there'd be no point playing a game against it!)

Radim 11y ago
I believe the OP refers to global/local as they are used in Go. There, global/local play is a concept taken for granted by humans, with explicit names like "sente" and "tenuki". I think the OP simply implies AlphaGo doesn't seem bound by these human cognitive crutches. This is not the same as "global" in the theoretical sense, as in "finding the perfect solution / exhaustive proof". See also "game temperature" [1] [1] http://senseis.xmp.net/?Temperature http://senseis.xmp.net/?Temperature
- reikonomusha 11y ago
  What he's saying is that if AlphaGo played optimally, there'd be No point in playing.
- atrudeau 11y ago
  Correct. Google seems to agree: "AlphaGo has the ability to look “globally” across a board—and find solutions that humans either have been trained not to play or would not consider." [1] [1] https://googleblog.blogspot.com.br/2016/03/what-we-learned-in-seoul-with-alphago.html https://googleblog.blogspot.com.br/2016/03/what-we-learned-i...

deleted 11y ago

[deleted]