[qub1t]

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.

Go is a discrete game where the game state is 100% known at all times. Starcraft is a continuous game and the game state is not 100% known at any given time.

This alone makes it a much harder problem than go. Not to mention that the game itself is more complex, in the sense that go, despite being a very hard game for humans to master, is composed of a few very simple and well defined rules. Starcraft is much more open-ended, has many more rules, and as a result its much harder to build a representation of game state that is conducive to effective deep learning.

I do think that eventually we will get an AI that can beat humans, but it will be a non-trivial problem to solve, and it may take some time to get there. 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.

[gradys]

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.

[autokad]

i feel like you misunderstood that part of the argument.

he is saying representing the state is very hard, and you are saying: given a well represented state, ML is very good at finding the important features, reducing the dementionality, and finding mathematical transformations, etc.

deep learning has been so successful with images because representing them is trivial - flattened pixel vector.

with your last paragraph is that in starcraft, that raises some questions on what rules is the AI going to adhere to.

in SC, you don't view the entire board. you view the minimap / hear noises and alerts and decide were to focus your attention on the map. in battle, being able to click and accurately place attacks quickly is important.

Do you give the computer full view of what they would be able to see? does the computer have 10 million clicks per second abilities, essentially every action is like hitting pause and then making the next action?

[gradys]

I was actually assuming the input representation would just be a video stream, which (combined with audio) is enough for human players, but looking more into it, it's a lot more than a video feed[1].

It feels a little like cheating, but I guess processing the game UI video feed isn't the interesting part of the problem. Plus, it makes the problem much more accessible to hobbyists who can't afford the GPU cluster required to productively experiment on models that process streams of 1080p video.

Still, in principle, I think modern ML modeling approaches could handle the problem of transforming the video feed into a useful high level state representation. I don't think I misunderstood the OP in that regard at least.

[1] - https://github.com/deepmind/pysc2/blob/master/docs/environme...

[Arwill]

Using just the video feed, the AI would be required to reconstruct an overview of the strategic situation, and then develop a forward strategy on top of that involving individual units. Even for a much simpler game like doom, video-only input is enough for strategies like "see an enemy, target and shoot it as fast as possible".

For an AI to be able to effectively compete in a complex game like SC2, preparing high-level inputs is important. Look at these like shortcuts, heuristic approximations of task that would be hard to represent and train with deep learning. I would guess an implementation would need multiple independent nets for various tasks, combined with heuristics. Then each could be separately trained to do the given task.

[halflings]

People should just read the article, I think. It answers all the things you are debating (limit on APM, what features are used, what models they already tried and how well they perform).

[FrozenVoid]

>a ConvNet to process individual frames combined with a recurrent layer to track state over time. > are harder to apply Thats an understatement: Starcraft is immune to Monte-Carlo approach or anything based on analyzing pixel data: The tree state of actual battle has thousands of choices pet unit per second with minor variations in location, there is no discrete state of chessboard(at best millions of cells): viewing the game at low-level(pixels) creates gigantic amount of data. units constantly move/attack/die and get blocked by other units/terrain.

Predicting an enemy move(MC simulation) will be impossible and you can make several moves per second(even at 120-140 APM) easily. That means 1.you need real-time response, unlike Go there isn't a time buffer to decide 2.you always need to react at the current time(or allowing enemy advances) 3.there are very few "good moves" in starcraft(moving randomly on the "board" will just waste time) , so MC simulation will miss them more than 99% of time due randomness.

MC approach is vastly inferior in this case, i think they'll be forced to operate on higher level strategy rather than just microing every unit optimally(i.e. treating it like chess in real-time). Brute-forcing billions of potential moves simply won't work.

[kaden]

>Brute-forcing billions of potential moves simply won't work.

The problem is all AI/ML is essentially recorded, recursive, constrained brute forcing.

[FrozenVoid]

You can apply it on higher level like that guy who bruteforced the 7roach rush for Zerg in SC2. http://lbrandy.com/blog/2010/11/using-genetic-algorithms-to-... Problem is that build orders are just optimizing the opening economy and these unbalanced openings will be just patched out in the future.

[albinofrenchy]

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.

[strgrd]

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]

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]

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-...

[FrozenVoid]

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.

[Retric]

SC2 is very balanced when you look at the total game across a range of skill levels. Each unit is balanced around costs, attention, utility, requirements, and other units. Ex queens are awesome early game as they hit air, don't take gas or larva, and have high HP, but late game it's all about healing ultralisks plus anti air.

Roaches take a lot of supply, are armored so take more dammage from tanks and can't hit air which is their counter. They are also ranged so they don't share dammage upgrades with lings or ultralisks. Late game players will sacrifice them for more useful units and they need a larger investment in overlords.

PS: If you watch some high level games units generally have their time to shine as part of individual games progression.

[jtolmar]

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.

[MichaelDickens]

Previous AI StarCraft tournaments have put an actions-per-minute (APM) cap on the AIs, which prevents them from micro-managing individual units.

[sanderjd]

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]

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]

So the challenge for the AI would be to figure out which action to do with the limited supply of actions and time.

[bitxbitxbitcoin]

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]

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.

[oh_sigh]

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.

[WhiteOwlLion]

Actions per minute (APM) could be limited to a max of 100.

[littlestymaar]

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

[TulliusCicero]

As someone who probably has played at a higher level than you I disagree.

Yes, it's true that mechanics are a large determinant in who wins between people. But pro humans are not easily thrown off by odd or novel strategies or tactics. They can react to things that introduce small wrenches into their build order without serious issues. Players can even adapt to things they've never seen before. The issue with Starcraft is that the state space is so large that it will likely be hard to get an AI that can flexibly and intelligently react to unusual or bizarre things that mess with their build order, because the neural nets will have nothing to account for, say, a mid-game cannon rush, or whatever.

If it was simply a matter of computers taking humans things and executing them better, computers would already be better than humans at Starcraft (there have been plenty of AI competitions using Brood War), but they're not. Not even close.

[littlestymaar]

> But pro humans are not easily thrown off by odd or novel strategies or tactics.

In tournament, with all the inducted stress they definitely do : see Lilbow vs Life in blizzcon 2015, or the whole run of Symbol in Iron Squid one. For BW, see Flash vs Stork in whatever MSL or OSL finals (in 2009 or 2010 I think).

> the neural nets will have nothing to account for, say, a mid-game cannon rush, or whatever.

The AI just need to know how many 2-2 zerglings you need to destroy a cannon in that position (or hydras, or whatever unit it has available around and pick the most cost-effective way to deal with the cannon). The thing is that the AI can deal with this in the most efficient way while perfectly microing two groups of mutalisks and defending against a reaver drop[1].

In fact you don't even need deep learning for that since there's a finite number of encounters like this (cannon vs any unit) and I'm pretty sure some guy on TeamLiquid already covered it in depth :p.

> there have been plenty of AI competitions using Brood War

AI competition featuring matches of AI vs AI are interesting, my point is that AI vs man probably won't.

[1] OK, I'm mixing events really unlikely to occure at the same time but you get the idea.

[36bydesign]

He said pros are “not easily” thrown off by novel strategies, not that they are “never” thrown off by such, so your examples are the exceptions that prove the rule.

FWIW I think you also drastically underestimate how many things the AI has to take into account. It isn’t just how many 2-2 zerglings you need to destroy a cannon, it’s making educated guesses of what you’re opponent is doing while you’re attacking the cannons, or how the terrain affects how you can attack, or what units the opponent may have be in the fog of war ready to ambush. Represting all these factors, let alone calculating them, is no trivial task.

[knicholes]

I'm pretty sure you're aware that Life has been banned from professional SCII for match fixing, but if not, I just want to throw that in there.

[qub1t]

I used to be pretty active on iccup, and I was a masters-level sc2 player for a while during the beta and when it was first released. So I'm definitely familiar with starcraft and what it takes to become a good player.

I think you're misunderstanding a big part of what is "easy" and "difficult" for humans vs ai. Yes, go is absolutely a more challenging games for humans than starcraft (I also play go, although not very well - currently around ~7k on igs). Starcraft is strategically a much simpler game than go. You are correct in stating that mechanics is what makes starcraft hard for most people, and yes if the computer knew exactly what to do, it would be able to execute it faster and without making any multi-tasking mistakes. But strategy is not what makes starcraft a challenge for ai. Tasks that are trivial for humans can be extremely difficult for ai.

Computers are way better at tree searching than humans, for the obvious reason that they run much faster than brains. So games with relatively small state-spaces, like checkers, are solved quickly. But as you increase the state space, it becomes impossible to search all possible future moves, and this was why go was intractable for such a long time.

The big advancement in alphago is that by using deep learning it is able to evaluate different board-states without doing any search, using a neural net. This allows it to massively prune the search space. Humans are able to do this through "intuition" gained through experience - talk to any advanced go player and ask them about specific moves and they will tell you things like "this shape is bad" or "it felt like this was a point of thinness". AlphaGo was able to gain this "intuition" by training on a massive dataset of go board positions.

In go, the rules are very simple - 19x19 board, each turn you can put a stone in any not-surrounded open space. Its also a turn based game. The state at any given time is fully known. Starcraft is real-time, there are tons of different actions you can take, the actions are not independent (pressing attack does something different if you have a unit selected or not), the game state is not fully known and a given state can mean different things depending on what preceeded it. Not to mention that the search space is massively massively larger. To create a representation of this that can be fed into a neural net and give meaningful results (something like at a given tick, score all possible actions and find the best one) is going to be incredibly difficult. An order of magnitude more difficult than go, imo.

[gambler]

>The big advancement in alphago is that by using deep learning it is able to evaluate different board-states without doing any search, using a neural net.

It still uses a Monte-Carlo Tree Search to get to the level where it can beat human pro players.

>Starcraft is real-time, there are tons of different actions you can take, the actions are not independent (pressing attack does something different if you have a unit selected or not), the game state is not fully known and a given state can mean different things depending on what preceeded it.

And yet StarCraft is extremely primitive as far as strategy games go. Most of the stuff you can do in the game simply doesn't matter, and the stuff that matters could be modeled at a much coarser level than what people see on the screen. Knowing how this stuff works, I'm willing to bet this is exactly how Deep Mind will approach the problem. They will try many different sets of hand-engineered features and game representations, then not mention any of the failed efforts in their press releases and research papers.

The choice of StarCraft as their next target reeks of a PR stunt. Sure, there might be no AIs that play at pro level now, but there wasn't any serious effort or incentive to build one either, and now Google will throw millions of dollars and a data-center worth of hardware at this problem.

As far as I'm concerned, real AI research right now isn't about surpassing human performance at tasks where computers are already doing okay. It's about achieving reasonable level of performance in domains where computers are doing extremely badly. But that won't get you a lot of coverage from the clueless tech press, I guess.

[36bydesign]

What are their other options besides Starcraft2? This doesn’t seem like a PR stunt (not that the PR isn’t a bonus), but there’s already a history of AI competitions for Brood War, the game is more balanced than arguably any other RTS, and even though it is “primitive” as a strategy game in your estimation, AI isn’t ready to tackle a more advanced strategy game.

[gambler]

>What are their other options besides Starcraft2?

Uh, real strategy games? Something like this:

https://www.gog.com/game/m_a_x_m_a_x_2

Very simple ruleset, huge strategic depth.

[danpalmer]

Why do you not think StarCraft is a real strategy game?

[gwern]

> It still uses a Monte-Carlo Tree Search to get to the level where it can beat human pro players.

I'm not sure this was true of the first AlphaGo, probably wasn't true of the Sedol AlphaGo, and definitely isn't true of Master.

[Shoop]

Do you have an article about this? I never heard that AlphaGo moved away from MCTS.

[gwern]

It uses MCTS, but that's not the same thing as the claim, now is it? If you look at the win rates in the AG paper for the NN vs MCTS+NN and then consider the performance curve, use of a single TPU, crushing superiority of Master's flawless 60 blitz matches and Ke Jie matches despite very fast moves, the released self-play matches, and comparing with FB's Dark Forest, it's clear that the AG NN all on its own, without any MCTS, is a truly formidable player that would likely crush many pros, although I don't know if it would reach Sedol or Ke Jie levels of play.

[littlestymaar]

This comment in insightful, thanks !

> Not to mention that the search space is massively massively larger

That's what I'm not really convinced about. The build-order space is not that big (compared to Go's positions) and once you got a good micro-management engine I'm affraid this will lead to something like : if protos or zerg pick protoss then 8 gate -> 9 pylon -> scout : if no counter to 4-gates, then 4-gates and win from out-microing.

[jtolmar]

The preferred opening for Protoss in PvZ (on most maps) is the forge fast-expand. If the Zerg player doesn't want to play an economic game in response, they have a variety of all-in strategies available. There is a lengthy article on Team Liquid about how Protoss should respond to these.

http://wiki.teamliquid.net/starcraft/Protoss_Counter_to_Zerg...

What I'd note here is that:

1. It's a rather long list.

2. Good scouting is required for most of these situations.

3. There are terrain-based considerations all over the place.

4. There are considerations based on how many units were lost in earlier engagements all over the place.

Enumerating all the build orders (#1) is pretty easy (as you said, build order space isn't that big), but the interaction between terrain and building placement (#3) is a lot more complex and starts to interact with the full game's massive search space more, and the followups are dynamic (#2, #4) so I don't think the game will degenerate into a solved solution as long as it looks anything like regular play.

It's possible that there's some degenerate micro-based solution that turns everything on its head, of course. Bot-based vulture micro might rewrite part of the Terran matchups, but it doesn't seem insurmountable yet. My own bot gets units across the map 5% to 10% faster than normal, but that doesn't look like enough to break the game even with a 4pool.

[sidusknight]

Protoss hasn't went FEE PvZ in a long time. It used to be good, though.

[jtolmar]

Well, egg on my face then. What's the current choice?

[littlestymaar]

Actually I realize that my cyclist vs motorcycle analogy is better that I first thought :

You might think that a race between the winner of the last Tour de France and an automated motorcycle is a good challenge because automated driving is hard (especially with crowd running around on the road and temporary road signs for the race circuit).

But in fact it wouldn't be funny because all the motorcycle have to do is follow the cyclist during the whole race (which is not really challenging in term of self driving AI) and just sprint during the last couple dozen metters with no hope for the cyclist to win.

It might only become interesting AI-wise if you add arbitrary rules like «limit the power of the motorcycle» and/or «limit the amount of fuel to limit the number of accelerations». But you're not really doing a Man vs Machine challenge.

[moh_maya]

That's only assuming they are competing at the same time. An average of timed trials across a pre-defined route (like TDF) would allow you to present a similar challenge to both the human & the automated motor cycle.

Couldn't an analogous structure be used to assess the AI for the SC II as well?

Disclaimer: I only know about SC. Not really a player.

[meric]

What about AI's fighting each other on Starcraft 2? Will that be interesting?

[bluetwo]

Interesting. So would you say that there are two parts here, figuring out a general strategy for a new map and then maximizing execution?

[Double_Cast]

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.

[empath75]

Except you can only execute your plan until you have contact with your opponent, and then it's improvisation. The rest of the game is only 'easy' if you've executed your opening far better than your opponent, or you have a rock-paper-scissors situation where your build dominates theirs. Both situations are not very common at the pro level.

[littlestymaar]

More often than not, yes even though there's some counter-examples with some players playing against the meta with great succès.

[bluetwo]

I wonder if AI will be able to bring that to another level. Recognize the counter and adapt.

Interesting to see unfold.

[Double_Cast]

It's possible you're referring to the tradeoff between exploration vs exploitation.

[rryan]

Do StarCraft AIs (the ones that are included with the game) cheat? (e.g. can they see past the fog of war?)

[jtolmar]

The ones built into the game can see past fog of war. Blizzard published a nice overview of how they work, though I don't think it actually mentions that cheat. http://classic.battle.net/scc/faq/aiscripts.shtml

The ones created using BWAPI cannot (you can call a function that lets you, but it's banned in all tournaments). The one thing that BWAPI bots know that a human doesn't is a persistent unit ID - if a marine leaves fog of war and comes back, you can check if the ID is the same and know whether it's the same marine. It also tells you where cloaked units are, but a skilled eye can see those already.

[yulaow]

Are you sure? I remember the video about the whole blizzard story and the Ai creator of starcraft2 said that the new AIs, compared to those of starcraft, have only the same information a player has and no way to "cheat"

[jtolmar]

I thought the question was a bout the original game?

I don't know much about the SC2 AIs. You could play some games and watch the replays to tell if consistently looks like it's responding to things it shouldn't know. I remember it being pretty blatant in BW.

[TulliusCicero]

Last I checked most of them don't cheat, but a few do (I think they're labeled as cheating though?).

[Impossible]

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.

[gradys]

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]

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...

[taneq]

If you're gonna be like that, our 'real' universe may well be discrete given that there are minimum possible lengths and time intervals.

[steinystein]

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.

[Impossible]

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.

[kornish]

The term the grandparent post meant to use is "imperfect information game" versus Go, which is a "perfect information game."

[haeffin]

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]

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]

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).

[Double_Cast]

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.

[winthrowe]

I haven't looked at SC2 specifically, but would be surprised if they were floats; I sometimes read game dev blogs and RTSs on average tend to be implemented using int/fixed-point based positioning, to eliminate floating point imprecision as a source of multiplayer sync issues.

[TulliusCicero]

Even if you just bucketized things at the pixel level, that leaves you with a range in the thousands for each dimension.

[greedy_buffer]

> 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?

[teraflop]

Technically you're right, but there's a real qualitative difference. Each "tick" in a game like StarCraft is on the order of tens of milliseconds. When you send out an army to attack your opponent, it's quite possible that the actual confrontation won't happen until 10,000 ticks in the future.

Also, the dimensionality of the state space in a "continuous" game is orders of magnitude larger. In a game like chess or Go, you may have dozens or hundreds of moves available at each turn, but only a few of them will be "locally optimal". In StarCraft, there are many more degrees of freedom -- attack timing, positioning, formation, banking versus spending resources, and so on. A good AI will need to be able to abstract that huge state space down to something more tractable.

[gambler]

To the best of my knowledge, the only thing in SC2 that requires pixel-level precision is selecting units. Everything else can just as easily be represented as a fairly coarse grid with no loss of expressiveness. Buildings are explicitly snapped to a grid, and moving your units several pixels to either side simply doesn't matter. So calling SC2 "continuous" in terms of space is misleading.

I don't think there is anything that requires super-fast response times either, so you could conceivably get ~1 frame per second and not lose much information.

Well, IIRC, there are some visual indicators that rely on blinking, but I don't think they are crucial.

[smallnamespace]

Even with the restrictions you put in place, SC2's state space is much larger than any board game.

A typical game might last 15 minutes = 54000 60fps frames and a typical map is larger than 10k x 10k in terms of 'coarse units'.

For any given frame of animation there are at least a million valid actions - if you have 10 units then you can move any subset of those units to any place on your screen.

[gambler]

>Even with the restrictions you put in place, SC2's state space is much larger than any board game.

That depends entirely on how you represent it. You're forgetting that there are plenty of AIs that actually play the game right now. They just don't use the same kind of "interface".

>For any given frame of animation there are at least a million valid actions

That's Google's marketing cool aid. "Actions" that produce the exact same result cannot be meaningfully counted as separate actions, especially when you're trying to compare them to board game moves.

[jncraton]

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]

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]

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.

[jjn2009]

Its computationally difficult to calculate every possible move a character might do in the occluded region. This requires a long attention span and running simulations of possible opponent actions based on previous 'frames'. Alpha go solved some of this by reducing the amount of space searching and instead search the likely set of possible choices by the opponent but each evaluation is for a single frame. If for some reason a piece on a go board could disappear and reappear then during that time it was gone its impact on decision making would be either nil or skew heavily towards nil compared to the rest of the opponents pieces depending on how many frames in the past are used.

[badminton1]

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.

[gobugat]

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. )

[eksemplar]

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.

[gambler]

>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.

[smallnamespace]

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.