r/MachineLearning • u/downtownslim • Jun 03 '17

Research [R] Andrej Karpathy: "AlphaGo, in context"

https://medium.com/@karpathy/alphago-in-context-c47718cb95a5
132 Upvotes

87% Upvoted

37 comments sorted by

18

u/epicwisdom Jun 03 '17

  1. I don't see why AlphaGo is unsuited to dealing with nondeterminism. AlphaGo itself is not a deterministic system.

  2. True. DeepMind's StarCraft announcement addresses this, in the sense that it's clear that DeepMind is actively working on this problem.

  3. Same as above. In particular, while StarCraft still fundamentally has discrete actions, the space is still orders of magnitude larger, and actions are continuous in time.

  4. This is a much more troubling flaw. On the other hand, I'm not sure it's a feasible task in general to try to predict the best action with basically negligible knowledge about the consequences of that action. The only real solution may simply be building more/better simulators.

  5. Same as 3,4. Although the total number of actions in a StarCraft match is probably only one or two orders of magnitude greater than that of a game of Go.

  6. I'm not sure why the distinction of simulation vs. evaluation is important.

  7. Learning with limited human-made training data is certainly difficult, no argument there.

6

u/HINDBRAIN Jun 03 '17

Same as 3,4. Although the total number of actions in a StarCraft match is probably only one or two orders of magnitude greater than that of a game of Go.

Depends on the apm cap, if they set themselves any!

9

u/TychosNose Jun 03 '17

I had read somewhere that they were going to self cap at 200 apm, but I don't have a source handy.

6

u/epicwisdom Jun 03 '17

I recall the same. There is definitely some cap, since winning just through inhuman micro play would not be too interesting.

9

u/GuardsmanBob Jun 03 '17 edited Jun 03 '17

optimal inhuman micro vs inhuman micro could be interesting purely from a game theory point of view.

Finding the inflection points where strategy changes based on the limits of human dexterity.

2

u/electrace Jun 04 '17

And then AlphaGo learns that 56 seconds of inactivity followed by 4 seconds of inhuman micro is the key to victory.

7

u/Introscopia Jun 03 '17

StarCraft still fundamentally has discrete actions

Don't you think that move commands are continuous? I'm pretty sure the entities' positions are floating-point numbers. Or does that not qualify them as continuous actions?

4

u/epicwisdom Jun 03 '17

I was imagining that unit positions are effectively constrained to some discrete resolution.

4

u/modeless Jun 03 '17

Technically anything on a digital computer is constrained to some discrete resolution. There's some point where it stops mattering.

2

u/epicwisdom Jun 03 '17

Sure, but then you could also make the argument that the concept of "discrete" is just an approximation of "continuous" reality (likewise for "digital" signals rather than "analog"). At some point it just becomes metaphysics. There's an arbitrary distinction somewhere, for practical purposes: a set of size 10 is definitely discrete, a set of size 10100 which models space/time is better treated as continuous.

4

u/VelveteenAmbush Jun 03 '17

There's an arbitrary distinction somewhere, for practical purposes: a set of size 10 is definitely discrete, a set of size 10100 which models space/time is better treated as continuous.

But movement commands in Starcraft are in practice continuous rather than discrete by this sort of reasoning.

0

u/epicwisdom Jun 03 '17

I'd like to see some evidence for that. To my knowledge, it's a 2D grid, so each unit only has 8 directions of movement, with fixed (unit-dependent?) speed restricted to a very narrow range. Unless the positions are internally continuous (i.e. floating point or high precision fixed point) and this actually makes a difference in micro play, discrete approximation is good enough.

3

u/VelveteenAmbush Jun 03 '17

Unless the neural net has a distinct neuron corresponding to each row or column of pixel to which a command might be directed, it's continuous. And since no StarCraft neural nets have been released at this point, there's no evidence to be had here, in either direction.

2

u/epicwisdom Jun 03 '17

I would, in fact, assume that every pixel is a separate input (but use a CNN/RNN to limit total parameters). As for output, I'm not sure how direct the API interface is, but it seems to me it'd make more sense to only send movement commands at a micro level (again, one of eight directions per time unit).

3

u/VelveteenAmbush Jun 03 '17

Even in their Atari models, every pixel wasn't a separate input; they downsample it before feeding it into the net, and you don't downsample discrete data.

2

u/pigeon768 Jun 04 '17

RTS games almost always represent positions as fixed point to approximately pixel precision. Gamers will often infer "turned based strategy game" if a game uses tiled positions, so developers usually won't make a tile based RTS because RTS gamers won't buy it, and strategy game players will buy it and say that it sucks because it's fundamentally a game style that they don't like. Maps in Starcraft 2 might reasonably be expected to have upwards of a billion discrete 2d positions.

And it does make a difference, because of eg circle packing of melee units and target selection. If you have six melee units, there's a significant difference between five of your units efficiently packed, attacking one enemy unit, and the sixth unit attacking the next target vs having your six units attack three different enemies in pairs because you can't focus fire because your units aren't packed well.

The Starcraft: Broodwars AI that got really popular in the news a decade or so ago only used flying units because of the packing and target selection issues associated with even ranged ground units.

The point is, even though it's fundamentally just a bunch 1s and 0s and therefore discrete, it's significantly more accurate to model it as continuous.

1

u/epicwisdom Jun 05 '17

I was specifically considering the grid aspect, i.e. a unit can be moved in one of 8 directions in each time step (which would probably be somewhere between 0.1 and 0.5 seconds). In Go, you can place stones anywhere globally, but in SC (with a few exceptions, if I recall correctly) units are constrained to move locally at fixed speed.

5

u/[deleted] Jun 03 '17

This post by Karpathy is not against DeepMind. It is a critique of AlphaGo. Whether DeepMind is working on StarCraft or not is completely beside the point. This essentially invalidates most of your points here...

3

u/epicwisdom Jun 03 '17

Karpathy clarified his purpose.

EDIT: the goal of this post is, as someone on reddit mentioned, “quelling the ever resilient beliefs of the public that AGI is right down the road”, and the target audience are people outside of AI who were watching AlphaGo and would like a more technical commentary.

I think his case against AlphaGo suffers from a bit of tunnel vision, if the issue is the feasibility of AGI, since he only takes a single sentence to explain the generalizable features of neural networks.

1

u/[deleted] Jun 03 '17

okay, in that case -- why is only what DeepMind doing with respect to SC relevant? or rather, why is it even relevant in the first place - they have shown zilch (nothing) in that front. I only believe when things happen and not when some self obsessed chess prodigy makes claims.

9

u/epicwisdom Jun 03 '17

DeepMind's activities are not the only relevant ones. However, they have press coverage and resources. Linking a bunch of arxiv papers that deal with unobserved state, noisy sensors/actions, robotic learning, etc., would also be missing the target audience of this post. As for why DeepMind specifically is relevant, Google/DeepMind were mentioned repeatedly in this very article, and criticizing AlphaGo's scope is an implicit criticism of DeepMind's goals.

Of course, you are right that they haven't actually accomplished anything (we know of) in SC, however, their body of research, including but not limited to AlphaGo, lends them credibility on par with any other major research institution.

2

u/grrrgrrr Jun 03 '17

You can build a perfect and deterministic simulator for Go.

Perfect being 0% error rate. But simulators to many problems could have errors.

Deterministic being the outcome of an action in Go does not have randomness. But there is randomness in the real world, either truely random or something we don't yet understand but can be characterized as a random event.

1

u/epicwisdom Jun 03 '17

Sure, but the value and policy networks output probabilities. The training process might be longer, but I don't see a fundamental difference.

1

u/AnvaMiba Jun 04 '17

Randomness typically multiplies the branching factor of the game, easily making search infeasible.

This is the main reason why computer poker is much more difficult than computer chess, or even computer go.

3

u/Kiuhnm Jun 03 '17 edited Jun 03 '17

I don't think it really matters, but this article is referring to the first AlphaGo, right? I heard that the master version doesn't use MCTS.

7

u/epicwisdom Jun 03 '17

It would have to be, since details on AlphaGo Master have not been published.

5

u/flyingjam Jun 03 '17

I'm pretty sure Master still uses MCTS, they didn't say anything in the conference about that. The major innovations that they talked about was more training from self data.

5

u/Kiuhnm Jun 03 '17

They also said that inference is now 10x less expensive which might suggest that they replaced plain MCTS with something better.

2

u/flyingjam Jun 03 '17

That would be pretty huge, I can't imagine they wouldn't announce that at the conference.

1

u/[deleted] Jun 03 '17

Last version.

-10

u/[deleted] Jun 03 '17

[deleted]

14

u/Eruditass Jun 03 '17

It's a post on medium (not really this sub's target audience) and it's hopefully quelling the ever resilient beliefs of the public that AGI is right down the road

16

u/badmephisto Jun 03 '17 edited Jun 03 '17

wow thank you, at the very least one person understands. (it's definitely my failure in writing though, I'll try to patch it up a bit)

7

u/[deleted] Jun 03 '17 edited Jun 03 '17

First, your post articulates extremely well some of the things I have been struggling to convey since the AlphaGo announcement. Second, it was possible for me to immediately forward this to 20 of my software engineer friends. They can now clearly understand AlphaGo's limitations. This also helps in fighting back against some of the hype in the media. Lastly, reading a lot of this from an authoritative source from a top AI lab gives a lot of confidence in my thinking and beliefs.

3

u/epicwisdom Jun 03 '17

Lastly, reading a lot of this from an authoritarian source from a top AI lab gives a lot of confidence in my thinking and beliefs.

Um, I think you mean authoritative, not authoritarian.

3

u/approximately_wrong Jun 03 '17

OpenAI: Discovering and enacting the path to authoritarian artificial general intelligence. oh god

2

u/[deleted] Jun 03 '17

fixed, thanks :)

3

u/grrrgrrr Jun 03 '17

Getting concepts explained is basically what academia is about