6 ms·

A lot of people here seem to be underestimating the difficulty of this problem. There are several incorrect comments saying that in SC1 AIs have already been ab

• strgrd 9y ago
  I wonder if we will see any advanced cheese strats come out of this. I'm assuming some implementations will eventually develop micro control that is far beyond any human player's capabilities, which would make things like all-in probe rushing much more viable. Instead of playing the normal meta in a computer-vs-human, I imagine an advanced AI would simply send all of its workers off the mineral line as soon as the game starts, and attempt to out micro the human opponent before they can build an army-producing building.
  • ionforce 9y ago
    I know this isn't the exact same as the article, but when genetic algorithms were introduced to solve for build orders, the "seven roach rush" was in vogue, something that was unexpected at the time and "discovered" using GA. I think there is a space for finding strategies that have more leeway in execution and thus are more suitable for humans to pilot rather than have machine level micro.
    • Tanner 9y ago
      I love the story of the Seven Roach Rush. To quote the linked article, "The most interesting part of this build, however, is how counter-intuitive it is. It violates several well-known (and well-adhered-to) heuristics used by Starcraft players when creating builds." I'm fairly certain that this application of machine learning will present some surprising strategies. http://lbrandy.com/blog/2010/11/using-genetic-algorithms-to-find-starcraft-2-build-orders/ http://lbrandy.com/blog/2010/11/using-genetic-algorithms-to-...
      • LASR 9y ago
        > I'm fairly certain that this application of machine learning will present some surprising strategies. And so it begins...
    • FrozenVoid 9y ago
      Part of the problem SC2 units are not very balanced and each patch tries to make them "more balanced". SC2 design settled on making unique units at cost of balance. Roaches in fact are quite overpowered, with very fast regen and quick ranged attack(they move as fast as hydralisks). A versatile and low-cost unit(cheaper than a Hydralisk). And the reason they're so powerful, SCII units of other races in general are more powerful than broodwar units and have less weaknesses. Broodwar instead has weak, easy dying units that force micro to extend their lifespan. SC2 units always have easy regen/heal/repair and the player just masses them in huge attack groups with minimal micro(their blocking boxes are tiny and pathing is good enough). The rock-paper-scissors from broodwar(which ephasized soft-counter) morphed into hard counters to everything, which lowered the strategic depth to "make whatever kill the majority of enemy unit type"(since its the best cost-effect decision at any point). SC2 "pro matches" are never decided in micro battles, they're most a competition on who can more effectively spend resources. SC2 micro is laughably unoriginal and tactically irrelevant(resource competition is far more important). ..And the reason SC2 can't have good micro in principle is not the 3D engine overhead, its server latency and lag. Perfect LAN games in broodwar with sub 10ms latency and millisecond reflexes can't exist within central servers hosting hundreds of players.
  • MichaelDickens 9y ago
    Previous AI StarCraft tournaments have put an actions-per-minute (APM) cap on the AIs, which prevents them from micro-managing individual units.
    • sanderjd 9y ago
      I think this definitely needs to be the case if this is going to be an interesting research project at all. Edit: Nevermind, my intuition in this seems to be wrong - someone more knowledgeable about this claims below that computer mechanics are still not as good as a good human's in the SC1 version of this.
      • jtolmar 9y ago
        In SC1 it's trivially easy to make a bot that spams so many actions it prevents your units from functioning properly. In fact it's easy to do accidentally. A lot of my early efforts into making a bot have been trying to find ways to reduce its APM without making it harder to code. "More actions = better" makes sense because we're used to human players who are using all their actions for something relatively effective and because (I'll assert) they're well below the optimal APM. But the optimal APM is probably something like 1000, not the 10k a bot can easily reach.
        • daemin 9y ago
          So the challenge for the AI would be to figure out which action to do with the limited supply of actions and time.
  • jtolmar 9y ago
    Currently bot micro can perfectly time hit and run "dance" maneuvers on all their attacking units independently (several top bots are Terran and do this with Vultures). But solving this in a way that takes terrain into account is much, much harder, and a skilled human could chase the whole army into a wall and kill it. Similarly there are worker rush bots that do some impressive things against other bots, but positioning is hard and a skilled human can beat the bot by clumping its workers up in the right shape.
  • oh_sigh 9y ago
    A sensible thing for human-AI matches is to enforce a maximum number of actions per second and/or actions over period of time, which would be in line with a standard human player.
  • bitxbitxbitcoin 9y ago
    I'd say we're certainly going to see crazy advanced cheese strats - ones that humans wouldn't be able to hope to pull off. This could definitely be done with computer micro and wouldn't be defendable with human micro. An example would be moving probes around in such a way to maximize their shield regen - or switching the top clickable unit while stacked - who knows...
    • baddox 9y ago
      But if that's all the AI can do, and people know it, then defending should be pretty easy. Any worker or land-based rush can be fairly trivially defended by walling off.
  • deleted 9y ago
    [deleted]
  • WhiteOwlLion 9y ago
    Actions per minute (APM) could be limited to a max of 100.
• gobugat 9y ago
  This. Somehow I was expecting the implementation of mechanics to be the easy bit, compared to high-level strategic planning and tactics. Curious to see whether these will emerge by themselves, or if they will need to provide some heuristics (use drops, harass, all-in, etc. )
• greedy_buffer 9y ago
  > Starcraft is a continuous game and the game state is not 100% known at any given time. It seems to me that multiplayer games may feel continuous to a human player but are still designed around a series of discrete states called ticks where each tick is determined from the previous state plus inputs. Why is this distinction made in the context of how difficult it is to develop an AI?
  • jncraton 9y ago
    You're basically correct in terms of SC not technically being continuous. There are discrete steps under the hood. One of the significant challenges is figuring out how to use 42ms (the frame duration on fastest speed) of computing time to decide what actions, if any, to take next. You don't have the luxury of taking many minutes to decide one move as you would in a game like chess or go. You also don't alternate taking discrete turns with your opponent, despite having discrete frames. It may be best to not take an action in a given frame. This is particularly true if the AI is attempting to stay under an APM threshold, as it has to decide if an action is worth the opportunity cost. It is also necessary for a quality SC AI to remember what has happened in the past. A chess board position is identical regardless of how the game got there, but this is not the case in StarCraft. An AI has accumulated lots of information about its opponent that is no longer visible to it in the current frame (unit movements, gas/mineral counts, number of workers active, etc), and this needs to be recalled and play into decision making.
    • haeffin 9y ago
      SC2 ticks faster than SC1 - you only have 22ms. You don't need to tie everything to tick rate though, a strategy module could update way slower.
      • giblaz 9y ago
        Bingo. If this had the tasks split up among multiple threads/processes correctly and using a very fast performing language + good developers, the tickrate is less important. Some army control module could manage the unit micro within the bound of a tick with other modules updating other info the system draws from to perform actions.
• haeffin 9y ago
  I don't know if I would label SC2 as continuous. I don't think anything happens to the game state at a finer granularity than tick level. So to me it seems that it's also discrete (but with the state changing 44.8 a second at default speed). I agree though that this looks more challenging for ML methods. I haven't looked at if they limit the rate of commands that the AI can issue, otherwise this will be something that can be a very big advantage to the AI once it learns to micro ...
  • TulliusCicero 9y ago
    It's not literally continuous, but it is real-time rather than turn-based, and positions of units are essentially floats rather than (a small range of) ints. That makes it effectively continuous (too large to just generate a tree of all possible actions and then prune).
    • dyarosla 9y ago
      Are you sure positions of units are essentially floats? Given how the units seem to arrange themselves (from what I see), I would guess that it's not close to the full range of floats, and instead there are just a few fractional pixel locations that units snap to. This is just a guess however. -- If this is the case though, the space could be represented by taking larger integer values (say, a magnitude of 1 or 2 higher) to represent positions at a fractional pixel level (say, in 100ths of a pixel).
      • LASR 9y ago
        It's most certainly integers on a very small grid.
      • TulliusCicero 9y ago
        Even if you just bucketized things at the pixel level, that leaves you with a range in the thousands for each dimension.
      • Double_Cast 9y ago
        Buildings snap to a grid. Units take up space according to a hitbox. Hitbox size varies according to each type of unit (E.g. Thors are huge). This becomes important when dealing with AoE. Consider a group of mutalisks. If you select-all and issue an attack-command or move-command, the mutalisks will bunch up tight and then disperse. Cf a video on the "magic-box technique". So I wouldn't be surprised if position-values were floats.
• Impossible 9y ago
  Minor nitpick, video games running on digital computers are by definition still discrete even if they feel continuous. Networked multiplayer wouldn't be possible in RTS games if that wasn't the case. The granularity of unit positions and turns in Starcraft obviously leads to a much larger state space, so I get what you're saying, for AI its effectively continuous.
  • steinystein 9y ago
    For a game of go the entire game state is known to each player. That's the diff. For vidya games state is hidden to the player if the player cannot 'see' it. Therefore u wrong fam.
    • kornish 9y ago
      The term the grandparent post meant to use is "imperfect information game" versus Go, which is a "perfect information game."
    • Impossible 9y ago
      I didn't say anything about hidden information. That clearly makes SC more challenging than Go, as it requires the AI to build some kind of mental model of possible player states from limited information.
  • deleted 9y ago
    [deleted]
  • gradys 9y ago
    They're discrete with such high cardinality that successful approaches will likely model them assuming they're basically continuous. Neural network layer activations are also discrete after all, but they're often 256+ dimensional vectors of float32s or float16s.
    • rjeli 9y ago
      Well, WaveNet[0] outputs audio in the time (not freq.) domain using PixelCNN, so it's not unthinkable. https://deepmind.com/blog/wavenet-generative-model-raw-audio/ https://deepmind.com/blog/wavenet-generative-model-raw-audio...
• littlestymaar 9y ago
  As a long time StarCraft fan I don't share your point of view : People usually refer to StarCraft as a strategy game but there's actually really little strategy involved : during the first weeks after a new map pool is released, the pro players explore different build orders that are strong on it. And after this period, when the meta-game has settled, the winner of a match (best of 3 or 5) is almost always the one who has the best mechanics (including scouting, unit micro-management and multi-tasking) and sc1 AI are already way better than humans in that field. Unless you add some artificial limitation to the AI (for instance, a hard limit of APM[1], at an arbitrary level) I don't really think the challenge will be exciting. Imho it will look like a race between a cyclist and a motorcycle : on the mechanics point of view, the machine wins easily without need for intelligence. [1] action per minute
  • bluetwo 9y ago
    Interesting. So would you say that there are two parts here, figuring out a general strategy for a new map and then maximizing execution?
    • littlestymaar 9y ago
      More often than not, yes even though there's some counter-examples with some players playing against the meta with great succès.
      • bluetwo 9y ago
        I wonder if AI will be able to bring that to another level. Recognize the counter and adapt. Interesting to see unfold.
    • Double_Cast 9y ago
      Skill is often divided into 3 components: macro-management; micro-management; and mechanics. Macro refers to decisions regarding economy. It includes finances, build order, counters, etc. Macro is mostly strategic. Micro refers to decisions regarding battle. It includes troop positioning, focus fire, kiting, etc. Micro is mostly tactical. Mechanics refers to execution. I.e. do your fingers have the dexterity and APM to accomplish your goals effectively? If not, practice makes perfect.
• gambler 9y ago
  >A lot of people here seem to be underestimating the difficulty of this problem. There are several incorrect comments saying that in SC1 AIs have already been able to beat professionals - right now they are nowhere near that level. Mostly because no one cared enough about solving this to spend 1/100th of the resources Google will undoubtedly throw at it.
• gradys 9y ago
  I think a big component is not really machine learning but more related to how to represent state at any given time, which will necessarily involve a lot of human-tweaking of distilling down what really are the important things that influence winning. I agreed with everything you said until here. Developing good representations of state is precisely what today's machine learning is so good at. This is the key contribution of deep learning. You seem to be supposing that a human expert is going to be carefully designing a set of variables to track, and in doing so conveying what features of the input to pay attention to and what can be ignored. Presumably the ML can then handle figuring out the optimal action to take in response to those variables. I think it's much more likely to be the other way around. ML is really good at taking high dimensional input with lots of noise and figuring out to map that to meaningful (to it, if not to us) high-level variables. In other words, modern AI is good at perception. What it's significantly less good at compared to humans is what might formally be called the policy problem. Given high level variables that describe the situation, what's the best course of action? This involves planning. We think of it in terms of breaking the problem into sub-objectives, considering possible courses of action, decomposing a high level plan into a sequence of directly executable actions, etc. AIs might "think" of this problem in different terms than these, but it seems like it still has to do this kind of work if it is going to have a chance to succeed. We don't have obvious ways to model this part of the problem. For the perception/representation building problem, I can almost guarantee the solution is going to be a ConvNet to process individual frames combined with a recurrent layer to track state over time. On the other hand, I'm seeing some plausible solutions to the policy problem emerging in the literature, but it's still very much an open question what will emerge as the go-to. In AlphaGo, this part of the problem is where they brought in non-ML algorithmic solutions like Monte Carlo tree search, and one of the reasons StarCraft is interesting compared to Go is that those algorithmic solutions are harder to apply.
  • albinofrenchy 9y ago
    I'd argue modern AI is sort of terrible at taking high dimensional data and finding an effective representation of it. It works better than a lot of other methods in ML but as far as I know pure reinforcement learning applications are sort of lack luster, and even dimensionality reduction success stories tend to rely on scrubbed, careful data treatment by people.
• eksemplar 9y ago
  I known nothing about what they are trying to solve, but it would be interesting if their goal was not just to beat humans but to make a game AI that was actually fun to play.
• smallnamespace 9y ago
  As a long-time high level SC2 player, one additional thing that makes SC2 so difficult is that the game has multiple layers of tactics and strategy that require specialized logic, but those layers also interact and synergize in a deep way. - There is the overall strategic game of 'Who is ahead economically? Given that, should I be expanding, attacking, or defending?', with the implicit understanding that the player with the current economic advantage puts pressure on its opponent to attack - There is a resource management and build-order system where you need to plan and optimize building as big and as effective a unit composition as quickly as possible, except there are a lot of tradeoffs: you can build for a stronger army sooner, as opposed to a weaker army alter - There is a tactical micromanagement battle where small groups of units are pitted against one another, and where small tactical movements can gain very large materiel advantages. Units are relatively short ranged, so to damage or defend effectively requires effective positioning. Most armies fight better as a cohesive group ('ball'), except there are units that specifically punish and do splash damage that need individual micromanagement. Battles can take place over a short period and be over quickly, or can be long-running positional skirmishes that last for half the game, where each player is constantly probing for weakness before one finally goes for the throat. - The economy fundamentally depends on worker units that are vulnerable to harassment, so the tactical battle requires a choice between putting everything into one large army and pushing, or splitting units into smaller groups and harassing in multiple places, or various mixes (small group to harass, bulk of army to defend, etc.) - If keyboard and mouse action rates are capped, then at every moment in time, the player must decide whether it is more profitable to devote actions to managing the army (micro) or managing the overall economy (macro). Choosing wrongly usually results in a loss - There is an implicit rock-paper-scissor tradeoff at the highest levels of the game: a 'greedy' strategy that cuts corners and favors economy over military will generally beat a 'safe' balanced strategy. Very aggressive strategies win against greed and generally lose against safe - There is the ability to scout your opponent to see whether they are going greedy, safe, or aggressive, but scouting requires an early investment in units and making subtle inferences about the opponent's build order, so the choice of whether to scout and how is not a trivial one - There can be bluffs where your opponent purposefully allows a scout of a key building, kills your scout, then cancels that building and chooses an entirely different technology instead And all these layers interact: - For example, if you go for an aggressive strategy, then you must commit blindly at the beginning of the game and often try to deny enemy attempts to scout you - If you scout that your opponent's army consists of units that are faster than yours, then they generally have much higher harassment potential, which pushes you towards a defensive posture. On the flip side, your opponent can use this threat to improve their economic position instead of attacking. There is long-term planning at the strategic, informational, and also tactical levels. Effective high-level play requires an accurate model of what your opponent is doing in an environment where it's easy for your opponent to deny acquiring that information. I'd wager that if you took two evenly matched professional level players, and then revealed the entire map to one player but not the other, you would go from a 50% to a 95%+ win rate.
• partycoder 9y ago
  From what I saw in the API, the AI will potentially have some key advantages like more accurate micromanagement, and that can make a significant difference in a combat setting. They can try to compensate for this by throttling the number of actions per minute, but that won't compensate for extremely well-planned pixel-perfect clicks. This is a very powerful tactical advantage that can offset strategic deficiencies, if any. Now, I would not compare SC1 bots to whatever DeepMind is going to create. SC1 bots were in their majority just rule-based bots with hand-coded strategies. DeepMind will create machine learning based bot, train it with data based on thousands if not millions of replays, and test it privately, maybe hiring a professional in the process (same they did with Fan Hui 5p), and make it play itself millions of times. It's a matter of time until they get it right and they get to pick when that time is. They will not organize a match until they feel their probability of winning is significant.