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

[vk23]

Adept openings are more popular nowadays

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