7 ms·

Deep Reinforcement Learning to Play StarCraft

116 points by wbthomason 10y ago

NikolaeVarius 10y ago
Screw Go. Beating the Terran Emperor in a game of Starcraft is when the computers will finally take over the world. It would be interesting though. How would a program that has PERFECT micro fare against a professional Starcraft player. Would a program reliably figure out how to kill 10 banelings with a few marines and a medivac by using the fact you can micro them to be able to do it without taking losses? Even if it could, would it know WHEN its even worth it to do so?
- hossbeast 10y ago
  They must constrain the AI to effectively only "click" on things at a rate and as far apart from the last thing clicked on such that a human could do it with a mouse
- computerex 10y ago
  In the past, Q-learning has led to models that perform at a superhuman level, so I wouldn't be surprised to see something similar.
- danielvf 10y ago
  There are already incredibly good micro StarCraft AI, able to operate at thousands of APM - this isn't the limiting aspect of current StarCraft AI. The "Hard" part of StarCraft is that it is a huge Rock Paper Scissors game with only the information you fight for. You have to be able to piece together a picture of your opponents actions and forces from small cues.
  - pkfrank 10y ago
    Wow, I hadn't seen this before. Here is "Automaton 2000" controlling 20 marines vs 40 banelings, without losing a single unit. https://youtu.be/DXUOWXidcY0?t=52 https://youtu.be/DXUOWXidcY0?t=52 Pretty cool.
    - vinchuco 10y ago
      That's incredible. The speed advantage here: https://youtu.be/IKVFZ28ybQs https://youtu.be/IKVFZ28ybQs Brings to mind the power of high frequency trading
    - danielvf 10y ago
      And as cool as that is, this is even more terrifying, as a hundred zergslings dodge seige tank cannons and destroy them. https://youtu.be/IKVFZ28ybQs https://youtu.be/IKVFZ28ybQs It's enough to make you scared for the future of humanity.
      - nickpsecurity 10y ago
        What... the... hell..!? That's basically what they show on movies where the action stars have superhuman movement. Except, it's zergling's perfectly coordinating the demolition of siege tanks. Awesome demo of AI micro.
anirul 10y ago
After loosing on the Go territory seams like fb is trying to challenge Alphabet on StarCraft. DeepMind already declared they will go for StartCraft as a next challenge does it mean that they accept the challenge? I'm actually happy to see what could be the result! The only weak point for the StarCraft community is that it would be on SC1 and not SC2.
- joseraul 10y ago
  Gabriel Synnaeve was already working on this long before joining FB. http://emotion.inrialpes.fr/people/synnaeve/ http://emotion.inrialpes.fr/people/synnaeve/
- kbody 10y ago
  Actually SC1 is the defacto choice when talking about StarCraft esports and the best choice since the best SC players have been honing their skills on SC1 for a long time (see South Korea SC1 esports scene).
  - ajsalminen 10y ago
    There are actual professional players still active for SC2 though. I don't think you can make that claim for SC1 because even though the competitive scene has been growing again nobody is getting a paycheck for playing competitive games.
    - knicholes 10y ago
      You've got to be kidding. There's one going on right now with a prize pool of $31k! http://wiki.teamliquid.net/starcraft/Main_Page http://wiki.teamliquid.net/starcraft/Main_Page
      - ajsalminen 10y ago
        Are you referring to the just completed Afreeca Starleague with $21k prize pool? Only the top two got more than a typical month's paycheck (winner did get over $10k) and it lasted a couple of months. There also haven't been any other events even close to that size this year for BW. Pro players don't typically live off tournament winnings.
pinouchon 10y ago
I think Starcraft is a very interesting challenge for AI because it involves planning in an environment that is only partially observable: you must scout in order to see what your opponent is up to, and even then, you don't see everything. If DeepMind works on this, I really hope that they constrain the AI (APM-wise) so that its only chance of winning is by good planning and strategy, not super-fast micro.
- danielvf 10y ago
  According to this paper Facebook is only working on micro - attempting to win a few simple (one to two unit types) battles that humans can win 100% of the time against AI. As you said, the glory of StarCraft is it's strategic level information game. Will be interesting to see what comes out of attempting to learn that.
h4nkoslo 10y ago
It's a misconception that StarCraft is a strategy game. If you look at how it's actually played by human pros, it looks closer to a fighting game; very reflex-driven & heavy on micro-interactions. You would expect an un-gated AI with effectively infinite actions per second to do very well.
- zitterbewegung 10y ago
  I think you are confusing the focus that is apparent in the micro of the game or micromanagement which requires high APM to the macro such as getting enough bases to keep on creating units to fight and troop composition.
- kmnc 10y ago
  Are you not just generalizing from only watching pros vs pros where the skill gap between them is probably very small thus making it seem like the only difference is in mechanical ability?
- devindotcom 10y ago
  Well, it literally is a real time strategy game. It's just that once the meta stabilizes, macro advantages become fewer and fewer and micro skills become the deciders. Perhaps at this point it might be better to refer to it as a real time tactics game. The AI would presumably not fail at micro so it would dominate at this point in the game's lifecycle, but it might be able to be taken advantage of at a macro level.
- empath75 10y ago
  It works on several different levels. You're talking about what competitive players call 'micro', which could be considered the implementation of the strategy. I haven't played for a while, but usually there are a few basic 'builds', which are essentially memorized openings-- and there are 3 types of openings -- Macro builds where you focus on building an economy, while sacrificing military resources for a long-game, 'all-in' builds, which sacrifice your economy to build an early military advantage and win within the first few minutes, and various mid-range builds that try to do a little bit of both. An all in is largely just down to micro and execution and it either wins or it doesn't, but the other two types of builds have a large strategic element-- for example, you need to scout to check if your opponent is all-in-ing, you can do harassment to distract your opponent from implementing his strategy by interrupting his economy, and then there's planning for the end game, building defenses, and the whole question of what you do if your original plan fails for one reason or another. There's a lot of thinking involved on multiple levels simultaneously, both spacial and temporal.
nickpsecurity 10y ago
Prior work and why I love StarCraft as a testbed for AI described here: http://webdocs.cs.ualberta.ca/~cdavid/starcraftaicomp/report2015.shtml http://webdocs.cs.ualberta.ca/~cdavid/starcraftaicomp/report... The two papers in RTS techniques sections are a must read for an idea of what problems it poses along with results of prior attempts. The ability of human pro's to detect AI patterns and defeat them with bluffs is pretty consistent. StarCraft, like Poker, involves lots of psychological analyses and ploys. Even if Google or Facebook make one, I still think of humans as superior until it can learn how to beat them with mere dozens to hundreds of games rather than what was fed into AlphaGo. That wasn't human equivalent or superior so much as approximating the results of nearly all human activity in the space then focusing it against one human. You could call it superhuman but it required tons of activity by brilliant humans. Brilliant humans require little with the champions a lot less than the automated techniques. Lots of self-discovery with limited data. I want to see the AI's pull that off plus keep it going when encountering humans with innovative, never-before-seen strategies. That's when I'll give them credit as useful on barely-defined problems with curveballs like humans.
Analemma_ 10y ago
This is pretty cool, although I think MOBAs (Dota, LoL) would be an even better test of AI skills than StarCraft. They also have imperfect information, but place more importance on strategy and less on micro than StarCraft; require some game theory and bluffing in the draft, and would need multiple agents to cooperate (assuming you set it up so that you had 5 AIs play the game, with well-defined communication channels, rather than one controlling the five players, which I think is the right way to go). Seems like there's more potential for useful AGI techniques in that direction.
scrollaway 10y ago
If anyone is interested in deep learning around Blizzard games, there is an active AI community around Hearthstone in the `#hearthsim` and `#hearthsim-ai` channels on Freenode. cf https://hearthsim.info https://hearthsim.info. Starcraft AI discussions welcome! We're also discussing support for such projects using game replays from HSReplay.net :)
wamatt 10y ago
Generalized reasoning in strategy games AI is an especially difficult problem for machine learning. IRL, top StarCraft players routinely model their opponents mental states and psychology to create an edge. So perhaps it's worth pointing out, that this paper specifically addresses a sub-problem of Starcraft play, micromanagement ('micro') [1] The game engine runs at 24 frames per second. (As an aside, 'frames' in this context likely does not map to physical FPS of the display). >We ran all the following experiments with a skip_frames of 9 (meaning that we take about 2.6 actions per unit per second). The research team found that attempting to move at a superhuman pace (eg one action every frame), resulted in a subpar performance and hyper-parameterization indicated 2.6 to be an ideal action per second. In context, this translates to an APM of 156. Or, roughly half that of professional Korean e-athletes. [2] [1] https://en.wikipedia.org/wiki/Micromanagement_(gameplay) https://en.wikipedia.org/wiki/Micromanagement_(gameplay) [2] https://en.wikipedia.org/wiki/Actions_per_minute https://en.wikipedia.org/wiki/Actions_per_minute
- aab0 10y ago
  "The researchers found that attempting to move at a superhuman pace (eg one action every frame), resulted in a subpar performance." Moving at extremely fine-grained timesteps can make learning much more difficult, because now a reward arrives millions of timesteps delayed rather than hundreds or thousands. It's like trying to teach a NN to compose piano music by starting down at the 1ms raw audio level. This is part of why audio synthesis was so difficult up until recently with DeepMind's WaveNet. In theory, being able to move every frame should enable extremely superhuman performance, but in practice, you can't learn your way there. So often people will chunk data to make it easier to learn the higher-level concepts: operate on words, rather than characters, for example.
  - raus22 10y ago
    Why not go the other way and decrease the actions per minute so you learn the overall point of the game , And with each game the actions per minute increases.
    - 10y ago
loser777 10y ago
Increased AI performance in RTS is always exciting, but part of me is disappointed by the fact that the AI doesn't "see" or interact with the game that humans do. That is, humans don't play the game by querying the state/status of each unit and then issuing commands via some API. It would be fun (though complicate things significantly) to produce an AI that at least has some notion of a mouse/keyboard so that you could see it in action from a first person perspective.

116 points by wbthomason 10y ago

Screw Go. Beating the Terran Emperor in a game of Starcraft is when the computers will finally take over the world. It would be interesting though. How would a program that has PERFECT micro fare against a professional Starcraft player. Would a program reliably figure out how to kill 10 banelings with a few marines and a medivac by using the fact you can micro them to be able to do it without taking losses? Even if it could, would it know WHEN its even worth it to do so?

hossbeast 10y ago
They must constrain the AI to effectively only "click" on things at a rate and as far apart from the last thing clicked on such that a human could do it with a mouse
computerex 10y ago
In the past, Q-learning has led to models that perform at a superhuman level, so I wouldn't be surprised to see something similar.
danielvf 10y ago
There are already incredibly good micro StarCraft AI, able to operate at thousands of APM - this isn't the limiting aspect of current StarCraft AI. The "Hard" part of StarCraft is that it is a huge Rock Paper Scissors game with only the information you fight for. You have to be able to piece together a picture of your opponents actions and forces from small cues.
- pkfrank 10y ago
  Wow, I hadn't seen this before. Here is "Automaton 2000" controlling 20 marines vs 40 banelings, without losing a single unit. https://youtu.be/DXUOWXidcY0?t=52 https://youtu.be/DXUOWXidcY0?t=52 Pretty cool.
  - vinchuco 10y ago
    That's incredible. The speed advantage here: https://youtu.be/IKVFZ28ybQs https://youtu.be/IKVFZ28ybQs Brings to mind the power of high frequency trading
  - danielvf 10y ago
    And as cool as that is, this is even more terrifying, as a hundred zergslings dodge seige tank cannons and destroy them. https://youtu.be/IKVFZ28ybQs https://youtu.be/IKVFZ28ybQs It's enough to make you scared for the future of humanity.
    - nickpsecurity 10y ago
      What... the... hell..!? That's basically what they show on movies where the action stars have superhuman movement. Except, it's zergling's perfectly coordinating the demolition of siege tanks. Awesome demo of AI micro.

anirul 10y ago

After loosing on the Go territory seams like fb is trying to challenge Alphabet on StarCraft. DeepMind already declared they will go for StartCraft as a next challenge does it mean that they accept the challenge? I'm actually happy to see what could be the result! The only weak point for the StarCraft community is that it would be on SC1 and not SC2.

joseraul 10y ago
Gabriel Synnaeve was already working on this long before joining FB. http://emotion.inrialpes.fr/people/synnaeve/ http://emotion.inrialpes.fr/people/synnaeve/
kbody 10y ago
Actually SC1 is the defacto choice when talking about StarCraft esports and the best choice since the best SC players have been honing their skills on SC1 for a long time (see South Korea SC1 esports scene).
- ajsalminen 10y ago
  There are actual professional players still active for SC2 though. I don't think you can make that claim for SC1 because even though the competitive scene has been growing again nobody is getting a paycheck for playing competitive games.
  - knicholes 10y ago
    You've got to be kidding. There's one going on right now with a prize pool of $31k! http://wiki.teamliquid.net/starcraft/Main_Page http://wiki.teamliquid.net/starcraft/Main_Page
    - ajsalminen 10y ago
      Are you referring to the just completed Afreeca Starleague with $21k prize pool? Only the top two got more than a typical month's paycheck (winner did get over $10k) and it lasted a couple of months. There also haven't been any other events even close to that size this year for BW. Pro players don't typically live off tournament winnings.

pinouchon 10y ago

I think Starcraft is a very interesting challenge for AI because it involves planning in an environment that is only partially observable: you must scout in order to see what your opponent is up to, and even then, you don't see everything. If DeepMind works on this, I really hope that they constrain the AI (APM-wise) so that its only chance of winning is by good planning and strategy, not super-fast micro.

danielvf 10y ago
According to this paper Facebook is only working on micro - attempting to win a few simple (one to two unit types) battles that humans can win 100% of the time against AI. As you said, the glory of StarCraft is it's strategic level information game. Will be interesting to see what comes out of attempting to learn that.

h4nkoslo 10y ago

It's a misconception that StarCraft is a strategy game. If you look at how it's actually played by human pros, it looks closer to a fighting game; very reflex-driven & heavy on micro-interactions. You would expect an un-gated AI with effectively infinite actions per second to do very well.

zitterbewegung 10y ago
I think you are confusing the focus that is apparent in the micro of the game or micromanagement which requires high APM to the macro such as getting enough bases to keep on creating units to fight and troop composition.
kmnc 10y ago
Are you not just generalizing from only watching pros vs pros where the skill gap between them is probably very small thus making it seem like the only difference is in mechanical ability?
devindotcom 10y ago
Well, it literally is a real time strategy game. It's just that once the meta stabilizes, macro advantages become fewer and fewer and micro skills become the deciders. Perhaps at this point it might be better to refer to it as a real time tactics game. The AI would presumably not fail at micro so it would dominate at this point in the game's lifecycle, but it might be able to be taken advantage of at a macro level.
empath75 10y ago
It works on several different levels. You're talking about what competitive players call 'micro', which could be considered the implementation of the strategy. I haven't played for a while, but usually there are a few basic 'builds', which are essentially memorized openings-- and there are 3 types of openings -- Macro builds where you focus on building an economy, while sacrificing military resources for a long-game, 'all-in' builds, which sacrifice your economy to build an early military advantage and win within the first few minutes, and various mid-range builds that try to do a little bit of both. An all in is largely just down to micro and execution and it either wins or it doesn't, but the other two types of builds have a large strategic element-- for example, you need to scout to check if your opponent is all-in-ing, you can do harassment to distract your opponent from implementing his strategy by interrupting his economy, and then there's planning for the end game, building defenses, and the whole question of what you do if your original plan fails for one reason or another. There's a lot of thinking involved on multiple levels simultaneously, both spacial and temporal.

nickpsecurity 10y ago

Prior work and why I love StarCraft as a testbed for AI described here: http://webdocs.cs.ualberta.ca/~cdavid/starcraftaicomp/report2015.shtml http://webdocs.cs.ualberta.ca/~cdavid/starcraftaicomp/report... The two papers in RTS techniques sections are a must read for an idea of what problems it poses along with results of prior attempts. The ability of human pro's to detect AI patterns and defeat them with bluffs is pretty consistent. StarCraft, like Poker, involves lots of psychological analyses and ploys. Even if Google or Facebook make one, I still think of humans as superior until it can learn how to beat them with mere dozens to hundreds of games rather than what was fed into AlphaGo. That wasn't human equivalent or superior so much as approximating the results of nearly all human activity in the space then focusing it against one human. You could call it superhuman but it required tons of activity by brilliant humans. Brilliant humans require little with the champions a lot less than the automated techniques. Lots of self-discovery with limited data. I want to see the AI's pull that off plus keep it going when encountering humans with innovative, never-before-seen strategies. That's when I'll give them credit as useful on barely-defined problems with curveballs like humans.

Analemma_ 10y ago

This is pretty cool, although I think MOBAs (Dota, LoL) would be an even better test of AI skills than StarCraft. They also have imperfect information, but place more importance on strategy and less on micro than StarCraft; require some game theory and bluffing in the draft, and would need multiple agents to cooperate (assuming you set it up so that you had 5 AIs play the game, with well-defined communication channels, rather than one controlling the five players, which I think is the right way to go). Seems like there's more potential for useful AGI techniques in that direction.

scrollaway 10y ago

If anyone is interested in deep learning around Blizzard games, there is an active AI community around Hearthstone in the `#hearthsim` and `#hearthsim-ai` channels on Freenode. cf https://hearthsim.info https://hearthsim.info. Starcraft AI discussions welcome! We're also discussing support for such projects using game replays from HSReplay.net :)

wamatt 10y ago

Generalized reasoning in strategy games AI is an especially difficult problem for machine learning. IRL, top StarCraft players routinely model their opponents mental states and psychology to create an edge. So perhaps it's worth pointing out, that this paper specifically addresses a sub-problem of Starcraft play, micromanagement ('micro') [1] The game engine runs at 24 frames per second. (As an aside, 'frames' in this context likely does not map to physical FPS of the display). >We ran all the following experiments with a skip_frames of 9 (meaning that we take about 2.6 actions per unit per second). The research team found that attempting to move at a superhuman pace (eg one action every frame), resulted in a subpar performance and hyper-parameterization indicated 2.6 to be an ideal action per second. In context, this translates to an APM of 156. Or, roughly half that of professional Korean e-athletes. [2] [1] https://en.wikipedia.org/wiki/Micromanagement_(gameplay) https://en.wikipedia.org/wiki/Micromanagement_(gameplay) [2] https://en.wikipedia.org/wiki/Actions_per_minute https://en.wikipedia.org/wiki/Actions_per_minute

aab0 10y ago
"The researchers found that attempting to move at a superhuman pace (eg one action every frame), resulted in a subpar performance." Moving at extremely fine-grained timesteps can make learning much more difficult, because now a reward arrives millions of timesteps delayed rather than hundreds or thousands. It's like trying to teach a NN to compose piano music by starting down at the 1ms raw audio level. This is part of why audio synthesis was so difficult up until recently with DeepMind's WaveNet. In theory, being able to move every frame should enable extremely superhuman performance, but in practice, you can't learn your way there. So often people will chunk data to make it easier to learn the higher-level concepts: operate on words, rather than characters, for example.
- raus22 10y ago
  Why not go the other way and decrease the actions per minute so you learn the overall point of the game , And with each game the actions per minute increases.
  - 10y ago

loser777 10y ago

Increased AI performance in RTS is always exciting, but part of me is disappointed by the fact that the AI doesn't "see" or interact with the game that humans do. That is, humans don't play the game by querying the state/status of each unit and then issuing commands via some API. It would be fun (though complicate things significantly) to produce an AI that at least has some notion of a mouse/keyboard so that you could see it in action from a first person perspective.