Hacker News Reader

Comment by atrudeau | Hacker News Reader

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.

View on HN

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

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

What he's saying is that if AlphaGo played optimally, there'd be No point in playing.

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

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.

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

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.

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?

The questions you pose require solving the game, at least (ii).

https://en.wikipedia.org/wiki/Solved_game

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

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.

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.

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.

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

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.

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

You could have said the same thing about chess when a program beat Kasparov about 20 years 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"

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.

>What makes GO so much harder than chess is how hard it is to evaluate the board.

And the 300-fold increase in branching factor.

First order branching factor is less important than you might think.

You could setup a game of Nim: https://en.wikipedia.org/wiki/Nim with much higher branching factor vs Go, but because you can trivially separate a winning moves vs. losing moves those branches become irrelevant in Nim. AKA, if there are 2,000 winning moves then they are all equivalent.

Deep Blue wasn't a full brute-force search, and AlphaGo does perform plenty of brute-force searching too.

how do you know that AI is not already advising the military on certain tactics? even an isolated system that analyzes data gathered by intelligence analysts, weather, radar, etc. and can suggest an a flight path and timeline for insertion or airstrike (especially in context with other operations in-theater) would basically be that, wouldn't it? i mean, i doubt it's guys on the DoD version of google maps plotting routes by hand.

i have a hard time believing something like that isn't already in use to some extent, at least for special operations forces. how long until they just hook that into the drone fleet? what if they already have? autopilot on a modern fighter/bomber is basically the same thing, except there's a human in the loop, right?

that would also go along nicely with the whole matrix / skynet plot that seems playing out in real life right now...

Humans are better at thinking globally than they are at acting globally. It's not clear that a "wise" AI would be helpful to us. It would tell us to do things that we already know we ought to be doing, but that we don't do for local, near-term-selfish reasons.

this is true, but it mostly comes down to 1. don't obliterate each other, 2. don't destroy your dependencies, 3. don't out-consume your dependencies (overpopulate, etc).

however, point 2 is only understood from a very high level by humans. we know the dependency chain goes deep, but we don't know exactly which branches can be ignored without effect and which are critical.

our default is to protect all the things "just in case"

It'll have to work like the last story in I, Robot.

"Optimization" presumes the existence of concrete criteria by which an outcome may be judged, and often a timeframe within which to judge it (e.g. if I want to maximize my wealth when I retire I should fully fund my 401(k), but if I want to maximize my wealth next year then I shouldn't fund it at all). A board game has unambiguous criteria for victory; human civilization, not so much.

Reply on news.ycombinator.com