4 ms·

- As all problems can be converted to Markov Decision Processes, this is a moot point. The transition may not be efficient in terms of states/actions, but since

- As all problems can be converted to Markov Decision Processes, this is a moot point. The transition may not be efficient in terms of states/actions, but since we just nearly solved a problem with more states than the atoms of the universe, this seems to be a moot point. In addition, most problems for humans are actually in the form of {state,action}. Just because now ML is popular and it's all about putting label on data does not make this less true. Other algorithms already exist (POMCP) which are direct transformations of MCTS for uncertain environments. Determinism is not needed both for MCTS nor for POMCP, so that point is void too. - I don't see what the problem is with that. Nearly all tasks humans would currently gain in getting automated have plenty of human experience before it. This is why training in any field even exists. Sure it would be cool to send a drone in unexplored territory with no knowledge and come back later to a self-built city, but I don't see how putting that milestone a bit later is in any way a problem. - The hardware requirements for any new interesting breakthrough to do something important have always been immense. Just as for Deep Blue, or to all the graphite experiments where we can only produce just milligrams of it at a time, or to solar panel, each new discovery innovates in a specific direction. It is just a matter of time before the new method is substantially improved and will be able to run on single machines. To expect otherwise is foolish, to complain about it is pointless. EDIT: This is not to contradict the general point. That we don't need new breakthroughs is utterly false in so many ways it's not even funny. However this certainly is an AI breakthough, one that many AI researchers (myself included) thought it would take AT LEAST 10 years to come to pass. Breaking 10 years in 1 seems like a breakthrough to me.

doctorstupid 11y ago
This is besides your main point, but I just want to add that the 'problem' of Go is not nearly solved. Rather, nearly solved is the problem of beating a human Go player. There is quite a difference.
- platz 11y ago
  I wouldn't expect global maximums to even be definable for most problems
  - emodendroket 11y ago
    I think a "solution" for Go is a program that can play to a win (or a draw, I guess) in any circumstance, right? I mean, like, you can create a tic-tac-toe program that plays perfectly and will never lose, but you cannot do this for go.
    - drdeca 11y ago
      ... Yet. Growth mindset.
- jacquesm 11y ago
  > the 'problem' of Go is not nearly solved. And it is very likely that it will never be, the number of combinations is simply too large.
  - zardo 11y ago
    That doesn't (necessarily) mean a proof can't be found that a certain ruleset leads to optimal play. Tic-tac-toe can be solved without examing the entire state space of the game.
    - jacquesm 11y ago
      That's mostly because of trivial symmetry and even taking that into account Go space is in the most literal sense astronomic, simple numbers don't work in describing just how large it is.
Smerity 11y ago
Thanks for the good discussion :) + The issue with MCTS was not that it couldn't be extended to non-determinism (you're correct re: POMCP) but that it requires a simulator which produces at least a reasonably accurate model of the world. This simulator is almost always hand engineered. Determinism and perfect information simplify both the task and the creation of the simulator. The state in Go also contains all history required to perform the next optimal computation - i.e. the system doesn't have to have any notion of memory - yet the state in most real world tasks is far more complicated, at least in regards to what needs to be remembered and how that should be stored. + The point of the hardware requirements is that hardware advances will advance the state of the art in Go but will not do the same in many other ML tasks. Whether or not we have 1x or 10x AlphaGo distributed's computing power in our pocket is not the issue - the issue is that such computing power won't assist many tasks as the potential of our ML models are not compute bound. There's also disagreement about how concerted the "10 year jump" was, which is mentioned in the article by Miles Brundage. Many people (including Michael Bowling, the person who designed the system that "solved" limit heads-up Texas Hold Em) predicted professional level Go play around now. Whilst it might be held by many, I also feel it was a media reinforced estimate.
- svalorzen 11y ago
  Simulators should be fast, sure, however that they should be deterministic to be fast is something I do not believe. We have millions of programs already that make use of pseudo random generated numbers, and they don't seem to be suffering performance problems because of that. And about the state and memory concern, mcts does not care directly about it, since for it the simulator is used as a black box and its internals are irrelevant to it. Instead, as long as any environment configuration can be described in terms of state (essentially a unique state->number conversion must be possible - and even then not always) mcts will work. And since it also does not care about the size of the state space, the concern that having memory as one of the factors in the state would be problematic is also unfounded. I also disagree on the specificity of AlphaGO. Mcts has been used successfully in many fields after its initial usage and tuning for Go. I did my thesis on similar algorithms. In the same way, it does not matter whether AlphaGO can be directly used on other problems. What matters is the new idea of using NNs in order to improve substantially and with little overhead the value estimations used by mcts to explore the decision tree. This is the true breakthrough. The fact that the first implementation of this idea is a Go playing program is irrelevant, it's more like a showcase of the goodness of the approach.

doctorstupid 11y ago

This is besides your main point, but I just want to add that the 'problem' of Go is not nearly solved. Rather, nearly solved is the problem of beating a human Go player. There is quite a difference.

platz 11y ago
I wouldn't expect global maximums to even be definable for most problems
- emodendroket 11y ago
  I think a "solution" for Go is a program that can play to a win (or a draw, I guess) in any circumstance, right? I mean, like, you can create a tic-tac-toe program that plays perfectly and will never lose, but you cannot do this for go.
  - drdeca 11y ago
    ... Yet. Growth mindset.
jacquesm 11y ago
> the 'problem' of Go is not nearly solved. And it is very likely that it will never be, the number of combinations is simply too large.
- zardo 11y ago
  That doesn't (necessarily) mean a proof can't be found that a certain ruleset leads to optimal play. Tic-tac-toe can be solved without examing the entire state space of the game.
  - jacquesm 11y ago
    That's mostly because of trivial symmetry and even taking that into account Go space is in the most literal sense astronomic, simple numbers don't work in describing just how large it is.

Smerity 11y ago

Thanks for the good discussion :) + The issue with MCTS was not that it couldn't be extended to non-determinism (you're correct re: POMCP) but that it requires a simulator which produces at least a reasonably accurate model of the world. This simulator is almost always hand engineered. Determinism and perfect information simplify both the task and the creation of the simulator. The state in Go also contains all history required to perform the next optimal computation - i.e. the system doesn't have to have any notion of memory - yet the state in most real world tasks is far more complicated, at least in regards to what needs to be remembered and how that should be stored. + The point of the hardware requirements is that hardware advances will advance the state of the art in Go but will not do the same in many other ML tasks. Whether or not we have 1x or 10x AlphaGo distributed's computing power in our pocket is not the issue - the issue is that such computing power won't assist many tasks as the potential of our ML models are not compute bound. There's also disagreement about how concerted the "10 year jump" was, which is mentioned in the article by Miles Brundage. Many people (including Michael Bowling, the person who designed the system that "solved" limit heads-up Texas Hold Em) predicted professional level Go play around now. Whilst it might be held by many, I also feel it was a media reinforced estimate.

svalorzen 11y ago
Simulators should be fast, sure, however that they should be deterministic to be fast is something I do not believe. We have millions of programs already that make use of pseudo random generated numbers, and they don't seem to be suffering performance problems because of that. And about the state and memory concern, mcts does not care directly about it, since for it the simulator is used as a black box and its internals are irrelevant to it. Instead, as long as any environment configuration can be described in terms of state (essentially a unique state->number conversion must be possible - and even then not always) mcts will work. And since it also does not care about the size of the state space, the concern that having memory as one of the factors in the state would be problematic is also unfounded. I also disagree on the specificity of AlphaGO. Mcts has been used successfully in many fields after its initial usage and tuning for Go. I did my thesis on similar algorithms. In the same way, it does not matter whether AlphaGO can be directly used on other problems. What matters is the new idea of using NNs in order to improve substantially and with little overhead the value estimations used by mcts to explore the decision tree. This is the true breakthrough. The fact that the first implementation of this idea is a Go playing program is irrelevant, it's more like a showcase of the goodness of the approach.