Hacker News Reader

Comment by highwind | Hacker News Reader

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

View on HN

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.

the guy you're responding to is correct:

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).

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).

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

Maybe Go has this property of optimal substructure. Maybe it doesn't. I don't know, but it sure isn't immediately evident.

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.

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.

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.

Imagine a condition where the local optima and global optima are not aligned.

Problem: One person remaining on island, 2 people left.

Optimal solution: Kill yourself.

Sub-optimal solution: Both live.

Reply on news.ycombinator.com