4 ms·

The catch is that this isn't quite zero human knowledge, since the tree search algorithm is a human discovery, and not one that came easily to humans. It also m

The catch is that this isn't quite zero human knowledge, since the tree search algorithm is a human discovery, and not one that came easily to humans. It also massively cuts down on the search space for an appropriate policy function. That means that this setup isn't necessarily general. How applicable is MCTS to games with asymmetric information, a la Starcraft? What about games that can't quite be modeled with an alternating turn-based game tree like bughouse?

anomnomidas 9y ago
There's a Dota 2 bot by OpenAI that played games with itself and managed to beat a lot of pros in the scene. It's still SF mid only no runes and some restricted items, but it shows that there is also potential for Starcraft. https://blog.openai.com/dota-2/ https://blog.openai.com/dota-2/
- zardo 9y ago
  Maybe you know something we don't... "We’re not ready to talk about agent internals" What makes you think it uses a tree search?
tyler_larson 9y ago
That's not quite what they're talking about WRT zero human knowledge. The problem is that there's no intrinsic scoring system for Go, nothing specific to maximize, so it's difficult to tell a computer whether a given outcome is "good" or "bad". So early versions of AlphaGo used a collection of human-played Go games to get an idea of what constitutes "good" and what is "bad", so it can then train its model to predict whether a move will make things better or worse. This new system forgoes that step, and instead has the model play itself starting at random and looking for patterns that end up winning games. It's as if you gave the rules to the game of Go to a culture that's never heard of it before, and they evolved their own play style entirely in isolation. Their result is a model that is better than the one that was developed with human influence, and that's the interesting bit.
- sobellian 9y ago
  I understand that the paper means that they didn't train it on expert input. The significance of the research is that this is a more general way to construct a game AI. The question I am posing is how far we have to go on that front.
  - tyler_larson 9y ago
    So... like this? https://www.theverge.com/2017/8/9/16117850/deepmind-blizzard-starcraft-ai-toolset-api https://www.theverge.com/2017/8/9/16117850/deepmind-blizzard...
    - sobellian 9y ago
      Yes. It'll be interesting to see if their starcraft project uses the same algorithms or not. Note that the link merely describes software that could be used for feature engineering. It doesn't describe what NN architecture or tree search algorithms deep mind is using.
red75prime 9y ago
> What about games that can't quite be modeled with an alternating turn-based game tree like bughouse? Train a network which predicts future state of the game, given current state and input. Train a network which generates sensible inputs, given current state. Use MCTS.
- sobellian 9y ago
  Bughouse, starcraft, and other important games need to be modeled as simultaneous-decision games. Plain-vanilla MCTS is designed for alternating-decision games. To see why this is important, consider why min-max (which MCTS approximates) actually works. At any given point, the equilibrium strategy for the player to move is the move that maximizes their payoff, and the utility for each move can be found recursively. In simultaneous decision games, calculating the equilibrium strategy (which may even be a mixed strategy) is more complicated. See http://mlanctot.info/files/papers/cig14-smmctsggp.pdf http://mlanctot.info/files/papers/cig14-smmctsggp.pdf for various ways in which MCTS can be extended to simultaneous-decision games. It'll be interesting to see if DeepMind picks up a search algorithm someone else has researched, or if they come up with something entirely new.
  - red75prime 9y ago
    Thanks for the link. The thing I described roughly corresponds to SUCT. It's interesting how NN will be able to deal with uncertainty of enemy's state and moves.

anomnomidas 9y ago

There's a Dota 2 bot by OpenAI that played games with itself and managed to beat a lot of pros in the scene. It's still SF mid only no runes and some restricted items, but it shows that there is also potential for Starcraft. https://blog.openai.com/dota-2/ https://blog.openai.com/dota-2/

zardo 9y ago
Maybe you know something we don't... "We’re not ready to talk about agent internals" What makes you think it uses a tree search?

tyler_larson 9y ago

That's not quite what they're talking about WRT zero human knowledge. The problem is that there's no intrinsic scoring system for Go, nothing specific to maximize, so it's difficult to tell a computer whether a given outcome is "good" or "bad". So early versions of AlphaGo used a collection of human-played Go games to get an idea of what constitutes "good" and what is "bad", so it can then train its model to predict whether a move will make things better or worse. This new system forgoes that step, and instead has the model play itself starting at random and looking for patterns that end up winning games. It's as if you gave the rules to the game of Go to a culture that's never heard of it before, and they evolved their own play style entirely in isolation. Their result is a model that is better than the one that was developed with human influence, and that's the interesting bit.

sobellian 9y ago
I understand that the paper means that they didn't train it on expert input. The significance of the research is that this is a more general way to construct a game AI. The question I am posing is how far we have to go on that front.
- tyler_larson 9y ago
  So... like this? https://www.theverge.com/2017/8/9/16117850/deepmind-blizzard-starcraft-ai-toolset-api https://www.theverge.com/2017/8/9/16117850/deepmind-blizzard...
  - sobellian 9y ago
    Yes. It'll be interesting to see if their starcraft project uses the same algorithms or not. Note that the link merely describes software that could be used for feature engineering. It doesn't describe what NN architecture or tree search algorithms deep mind is using.

red75prime 9y ago

> What about games that can't quite be modeled with an alternating turn-based game tree like bughouse? Train a network which predicts future state of the game, given current state and input. Train a network which generates sensible inputs, given current state. Use MCTS.

sobellian 9y ago
Bughouse, starcraft, and other important games need to be modeled as simultaneous-decision games. Plain-vanilla MCTS is designed for alternating-decision games. To see why this is important, consider why min-max (which MCTS approximates) actually works. At any given point, the equilibrium strategy for the player to move is the move that maximizes their payoff, and the utility for each move can be found recursively. In simultaneous decision games, calculating the equilibrium strategy (which may even be a mixed strategy) is more complicated. See http://mlanctot.info/files/papers/cig14-smmctsggp.pdf http://mlanctot.info/files/papers/cig14-smmctsggp.pdf for various ways in which MCTS can be extended to simultaneous-decision games. It'll be interesting to see if DeepMind picks up a search algorithm someone else has researched, or if they come up with something entirely new.
- red75prime 9y ago
  Thanks for the link. The thing I described roughly corresponds to SUCT. It's interesting how NN will be able to deal with uncertainty of enemy's state and moves.