3 ms·

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.

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.