DeepMind Challenges for StarCraft
gamasutra.com
gamasutra.com
In Go, anyone can place a stone as well as anyone else, it's deciding where to place a stone that's the game. In Starcraft, not everyone can control the interface to the game equally well. Playing Starcraft without using the same interface as humans is like playing baseball with something other than a baseball bat.
Also, I think it's unfortunate that they're choosing Starcraft 1: Brood War (presumably because of API reasons) instead of Starcraft 2, since there are many more top-level players playing sc2 right now to give it a run for its money, with an evolving meta that could more likely adapt and challenge the AI after it wins some matches. SC2 is where the tournaments and money is right now (compared to BW), hence the best players devoting the most time.
It's something humans have to put up with, the AI should too?
> ""Why not StarCraft 2?"
> This is the question we always get asked when we tell people we are doing a BroodWar AI competition. This competition relies completely on BWAPI as a programming interface to BroodWar. BWAPI was created by reverse engineering BroodWar and relies on reading and writing to the program memory space of BroodWar in order to read data and issue commands to the game. Since any program that does this can essentially be seen as a map hack or cheat engine, Blizzard has told us that they don't want us to do anything similar for StarCraft 2. In fact, most of the StarCraft 2 EULA specifically deals with not modifying the program in any way. We are happy that Blizzard have allowed us to continue holding tournaments using BWAPI, and they have also helped out by providing prizes to the AIIDE tournament, however until their policy changes we will not be able to do the same for StarCraft 2."
[0] http://webdocs.cs.ualberta.ca/~cdavid/starcraftaicomp/report...
Looks really great. I hope they look into this.
That said, it would be cool to see SC2 for this, and maybe we'll see it eventually. But I think Blizzard would have to allow it in the end, considering they've been in direct contact with them about this.
In the MMO sphere, where the people being hired for development tend to have a decent grasp of how networking is supposed to work, you don't see the "reference client" being developed until quite late—first you get a server, and a client library that does enough physics and network-messaging to appease that server. Then both integration test suites for the server, and the reference client, are written in terms of that library. Thus, the "business rules" of the game's simulation are forcibly decoupled from the particular UI used to present them.
You can tell when a game team has hired some good network programmers, because—at least if the game is a competitive one—the game will have "match recordings" that are able to be replayed on reference client versions newer than the one used to create them. This is true of SC2 (and false of a ton of other games, even much more recent ones like, say, Super Smash Bros U.)
How do they do that? Simple: they keep all the old versions of the "business rules" simulation library around together with the reference client, with a stable ABI such that the newer client can load the older library versions. When you want to watch a match recorded for a given simulation ruleset, it loads the relevant simulation library.
So, if there exists such a library for your game, you don't have to reverse-engineer the entire client; only the library. Mind you, you could just use the library, the same way the reference client does; but the low coupling makes such a library also much easier to analyze and reverse-engineer. So both options are on the table for SC2 in a way they aren't for most games.
In that way there would be no need of any privileged API... and it would be more natural (i.e. interacting with the real way, instead of its abstracted version).
Yeah, I've followed Starcraft AI automation for a while. The people programming these AI systems have basically been creating individual unit AIs with a tiny bit of latency.
It's cool to watch but absolutely does not advance the game theory of Starcraft. If you actually had to ration moves, they would have to come up with quite interesting systems. I'd be fine with something borderline impossible like 500 APM - as fast as you can physically click buttons with 10 fingers. Not 2000 APM.
I think there's no need to make it use a keyboard/mouse, you should just add in some human like constraints that are assumed in the game (some limit on APM, some delay between moving the screen and being able to take an action/observe the state).
The interesting part would be whether they can build an AI, not a robot. It's unfortunate that both games are pretty figured out at this point though, it'd be interesting to see if an AI could be made that could react to a big metagame change like http://wiki.teamliquid.net/starcraft/Bisu_Build
Still, if there's no api then there's no point complaining.
"The system only gets raw pixels as input."
The results were pretty great, so it would be fascinating to see this work with Matt's version of SC2 as mentioned elsewhere in this thread: https://news.ycombinator.com/item?id=11326119
"The emulator’s internal state is not observed by the agent; instead it observes an image xt ∈ Rd from the emulator, which is a vector of raw pixel values representing the current screen. In addition it receives a reward rt representing the change in game score."
The paper: http://arxiv.org/abs/1312.5602
Further limiting the apm would be no different than limiting the AI itself. It wouldn't be any different than limiting the cpu/memory usage imo.
That's the easy part, though. If you can make a SC AI play well against a human you can certainly send mouse events into a window. It really doesn't show anything.
See for example Sikuli, which you can use for automated testing.
[1]: https://www.youtube.com/watch?v=DXUOWXidcY0 [2]: https://www.youtube.com/watch?v=IKVFZ28ybQs
also the APM is not unlimited, it is only very high.
They better keep fog of war on too.
APM is a huge indicator of Starcraft "skill". Its not the only thing of course, but winning "micro-battles" greatly changes the game.
I don't care how good Michael Jordan is. He'll never "win" a game of basketball vs a standard professional by shouting commands to an average joe.
Similarly, no average joe will be able to perform a muta-harass while retaining full-speed, taking only a single missile from a Turret. That sort of "micro-skill" takes practice and dexterity.
Too bad, it's really good.
DeepMind's system is all about finding patterns. It might do better on those aspects. It could even be trained to recognize some aspects of enemy intent, how the battles are going, etc. Thing is, there's lots of potentials for curveballs in Starcraft compared to Go or Atari games. Human pro's curveball on demand. Should be interesting to see what it can do.
I'm now thinking more explicitly of the book series I alluded to (The General series by S.M. Stirling and David Drake): the human is a commander, so the units are intelligent in their own right (thus, handled by the AI); and the AI is also giving the human commander real-time advice based on what knowledge it can discover through the human's vision (isolated from the other AI-instance doing micro, but "smart" in the sense that it can assume that the micro is being done by a [fallible] rational actor that thinks like it does.)
I feel like that "human in the middle" configuration would actually make for its own new subgenre of 4X/RTS-like games, if we could get it right; somewhat like a more interesting version of tower defense. Like an RTS, it would be about issuing orders; like a MOBA, you'd have direct control of a "champion" unit. But the job of the unit would be to give those orders, and your job as the player would be to get their position fortified while also gaining enough information to accurately strategize.
Come to think of it, this is what Dungeons & Dragons was originally supposed to be about, wasn't it? Commander-level characters going off to do scouting or other special ops for their army, advancing in rank and gaining underlings in the process. (D&D1e assumes you'll just already have a wargame going with an overworld hex grid, unit stats, etc., and just serves as a "what heroes do in a zoomed-in view" add-on to it. Thus why it doesn't come with its own battle system.)
I see what you're saying. Yes, I daydreamed about such models too. I got excited about two games that stepped into that direction: Supreme Commander's dual-monitor setup with a macro, commander-like view plus detailed, micro view; Full Spectrum Warrior and Full Spectrum Command. The S.C. setup shows people are dabbling in interfaces that might lead to that. FSW and FSC are straight implementations of what you describe: commanders controlling AI agents that are semi-autonomous and provide feedback. FSC isn't available to public but is what I wanted more: limited commander view with data on your troops, position, intel coming in from video feeds or satellite, and so on. A hybrid model might let me go Harbinger and "assume direct control" of a character or team.
"I feel like that "human in the middle" configuration would actually make for its own new subgenre of 4X/RTS-like games, if we could get it right; "
It could. I'm not sure what it will look like outside Full Spectrum Command or bots in shooter games. A lot of the experience comes from the style of the people playing plus their quirks. The Call of Duty Ghosts AI shows that we might be able to approximate that as it did it so well I thought I was playing online against rookies lol. Most fun bots ever were.
"Come to think of it, this is what Dungeons & Dragons was originally supposed to be about, wasn't it? "
I think it was meant to enable and constrain the imaginations of players so the game took place inside their head. I never played it but it was a brilliant idea. Come to think of it, you're onto something here because games like Skyrim have all kinds of autonomous people doing certain routines or behaving in certain ways. There's even contractors and mayors. Any of these people could benefit from AI. Just a matter of computing resources. Could have one world where everyone plays the same world whose characters are controlled via a server farm at developer's location. I originally envisioned that for Runescape when I failed to get them to create a version of it for AI research. It would've been great for testing pathfinding, build systems, strategy, chatterbots, and so on. Skyrim more so.
Note: We could also test a collective intelligence where individual agents publish what they learn to central forums organized by topic. AI expansions could take time to periodically scrape that, try to understand it, and factor it into their gameplay. Basically, simulating player help forums that humans use. Additionally, could build superintelligences, gods, or advanced/E.T. AI's that tap into that plus much of world state that shouldn't be available. Even let them make changes to map or items with that dynamic factored in.
Lots of potential that might not have been explored yet but could make even simpler bots a lot more fun to watch. ;)
I mean, what would an AI come up with given just mass zerglings vs mass zerglings. Would love to see the strategies possible with near unlimited attention and APM.
For example, while banelings, are considered hard-counter to marines, stimpacked marines are still faster than even speed-banelings not on creep and just a little bit slower on creep. Pros use splitting to minimize damage, but here, as you can see, it can be just ultimate showdown.
Another example would be high templars vs ghosts. It is fairly difficult for Terran player to target high templars, but just two EMP shots basically puts templars out of combat, and miss of those shots renders ghosts mostly useless.
So, any area-of-effect attacks would be mostly useless due to infinite APM. That means minus colossi, tanks, banelings, thors and many other units. Probably that means that some race will be somewhat (or, maybe, insanely) overpowered (my bet is on Terran due to possibility of multiple drops, which themselves could be useless, though (because AI can't "miss" a drop), and stim-marine micro). So, the game will require massive rebalancing.
I think this really demonstrates why putting in APM limits is super important, and as brought out elsewhere also making the computer input via mouse/keyboard and get data from the screen (maybe just a filter to ease up on the CV bits?). A lot of the fun in watching a StarCraft map is seeing how the big picture is balanced against the details, and where a person's limited congnition flows from one focus to another. Limited knowledge and scope of sight play a huge part in the skill.
But mostly I'm just ranting because dodging the splash damage feels unfair; goes against everything I stand for. Next we'll start seeing 5 Skill Rays bulldoze the map! (I'm going to be looking into this a lot more after work - it seems like a super cool project!)
Or maybe it is because opponent is also AI and automaton simply knows which target it will auto pick.
For their atari work, deepmind was using raw pixel data from the screen. You could do something similar for starcraft. I suspect the actual machine learning question is 'given a sequence of n frames of the game, where should i click next? repeat.'
A training set might look something like video of a game with a text file recording X,Y positions for every click and a timestamp that can be synced to the video. They need lots and lots of those.
From there things get drastically more complicated. To go from very unstructured data like that and form higher level representations that can be used for long term planning and strategy... That would be quite a feat.
But man, if Battle.Net did save all of them, there'd likely be hundreds of thousands, if not millions, available. That'd be pretty spectacular as a training set!
Yes, anything where the interface to the game becomes critical is difficult to fairly compare with humans. Board games can use a human as an actuator, micro-heavy games hopefully won't for a long time...
If you want "fairness" you can limit the instructions to what keyboard and mouse can actually interpret as in the limited latency between instruction that both the game, the OS, and the hardware can support.
USB has quite a bit of limitation for HID's and allot of the gaming mice and keyboards use various hacks to overcome them.
Games and OS also have limits I can easily issue more commands using my keyboard than SC2 can handle so not all key presses will actually register.
Not to mention is that the game actually has to run on regular hardware, start spamming your keyboard in a game and you see the CPU spikes, the game loop also puts quite a bit of limits on how many interrupts per second it can catch, and how long does it take for it to actually switch context (e.g. SC2 build menus).
That said after AlphaSC2 destroys another Korean national passtime I would definitely love to see human like input being used by AlphaSC2.
Not because I think humans deserve a fair fight, but because i think the most interesting part will be to see how AlphaSC2 has to modify it's play style to compensate for the limitations of having to use "meatbag" control methods.
https://en.m.wikipedia.org/wiki/Fitts%27s_law
It may also be interesting to model the state of the keyboard hand. Instead of allowing the computer to access keyboard shortcuts directly it could be forced to operate a virtual hand that is in turn operating a virtual keyboard. Constraints could be added to the speed of various finger movements. This provides balance but also captures authentic strategic tradeoffs. Like the resting position of the hand. I imagine if you had a nice visualization it could even reveal subtle optimizations that were practical for humans.
Didn't they just try to sell that department?
But they don't; even moderately competitive players can beat the best bots.
That's because the programmers are bad at AI for that kind of game. It just means human beings don't understand how to make a good AI for a game like starcraft. AKA the human being being the idiot that doesn't understand how to make one.
This isn't true, in general a bigger army will beat a smaller army every time.
After you can make equal size armies, the next problem is army positioning and when to take engagements.
Finally, after you can do all that, then you can get an extra bonus to your power by microing really well. But not every micro is about speed - most of the time it's about knowing what to do.
And even at the most extreme, it's less about clicking quickly and more about clicking precisely.
The AIs unit control speed may have to be limited to get interesting results where it has to use strategy.
In chess, go, and even simple atari games, you have a clear way of reading the current state of the game in which the next move will be based on. In SC, this state space includes the predictions of your opponent. What will your opponent build next? What will they try to do with their army? There's an element of theory of mind here, where opponents try to project themselves and preempt each other's moves.
For an AI to truly play and win against a SC pro, using only human level interfaces, it would need to learn how human minds will be playing the game. Otherwise, I think we can expect a strong AI with unconventional tactics that SC pros will be able to fool with tricks and take advantage of because the AI lacks a meta-game capability. A more "general intelligence" would be needed to play at this level, not just a learning algorithm that learns from the pixels on the screen.
e: ref--http://ai.cs.unibas.ch/_files/teaching/fs15/ki/material/ki02...
Or am I missing something?
This could be a dangerous idea. http://lesswrong.com/lw/x4/nonperson_predicates/
Micro and unit control is where the AI has the advantage.
Personally, I think (all else being equal) Dota might be an easier starting point than League because of its focus on item abilities, rather than champion abilities. Anybody can use a BKB in Dota, but in League you have Fiora W, Morg E, and a bunch of other things. You have a smaller set of abilities/effects to worry about.
The dodge/aim AI can be situationally good (Cass bots) but still, the best players do win against scripters. Scripters rarely make it into the elite echelons of the ladder; there's a situation right now with a former pro Korean player who started scripting but couldn't make it back into Master tier. You'd expect a former pro with very in-depth game understanding to play at the very tip top level with some 'aim assist' but it doesn't appear to be the case!
Your example of script-users not attaining high ranking in online play for league of legends is also misguided. Because the action space in league is so much smaller than in starcraft, it is much easier to develop an AI with game strategy competency for league. Combine that AI with perfect mechanics, and human players should be falling very readily.
The prevalence of lane swaps (2 go top, 1 goes bottom) in competitive is one major counterexample. In fact, these often turn into having 3 or 4 people in one lane at the start of the game, forcing a fast push strategy.
> Teams will farm with occasional gank attempts until the midgame, where there is a slow transition from farming to objective taking and teamfighting.
Stereotypical Chinese LoL matches are nearly all teamfights, for better or for worse. Regardless, laning and midgame is where I think you should consider my point of champion diversity as well. Here, mistakes can be more readily mechanically exploited (late game, mistakes are punished strategically), e.g. if a laner is far from baron without TP, exploiting a 5v4 fight is a strategic decision, whereas missing certain skills early on in certain matchups means a severely negative outcome if the opposite laner has the mechanics, e.g. no flash and Q on CD as Lux means any Morgana can flash ult for guaranteed kill. These have a bigger impact than racial considerations and probably make up for map considerations (idk)
The script user example is one of mechanics: top players still win against those with pixel perfect scripted mechanics. This is despite having some scripters having 'game strategy competency' (that might be a real thing, but I interpret it as a player having real game knowledge).
IMO the biggest challenge to a human player playing against a team of 5 AI-controlled players is that of communication; perfect understanding of each others' intent is a far cry from the communication of even practiced teams.
Even if some AI does defeat Flash in 2017, would they have defeated Flash in 2010?
The mechanical skill required for this game means you simply can't come back to the game after a year and resume where you left off. Knowledge and understanding aren't enough, your fingers must be lightning.
For micro, there are scripts: https://news.ycombinator.com/item?id=11325855
So, while it may be not easy to conquer humans, I don't see why it is out of our current reach.
- Controlling individual units: scouting, resource gathering, micro-management while attacking/retreating, ...
- Resource management and planning: knowing when and where to expand, save resources for certain points in the tech tree, e.g. so you can immediately build a bunch of units once a crucial research or building is complete, ...
- Figuring out what the opponent is building and what he could be doing: where is he and what race, what tech buildings are there, when does he start to harvest gas, key tech buildings may be hidden in other places of the map, essentially even not being attacked with certain units at a certain time may be a clue to some strategy
- Reading and using the terrain properly: High ground has an advantage, Terran can wall off certain entrances with a depot and a barracks, where would be good places for drops (and with what units), figuring out where the enemy could come from and which places to defend – all those vary by map quite a bit
- Finding a good strategy to counter what the opponent is doing: This ties into a few of the things above, because first it must be known what the enemy is doing. Keeping the strategy flexible enough to counter the enemy's counters, etc.
Some of those are necessary to solve in real-time (unit movement), some of those can be run in background and don't need to be frame-exact (strategy, etc.), which helps a bit. But there are still quite a few parts to playing the game, all of which are interconnected and require information from other parts. Many successful bots currently are rush bots, which exploit that most bots are weak in the beginning and are easy to create. Others rely on a number of fixed strategies and build orders that are chosen based on what the enemy is observed to do.
I might argue that the AI vs AI challenge in Starcraft is deeper and more difficult to master. But for AI vs Player the Starcraft AI has an enormous mechanical advantage. Being able to harass mineral lines in four different places is a big deal. Being able to perfectly micro multiple lines of attack/defense is a big deal. It's very unfair and very much in the AI's favor.
Chess < Go < Starcraft < League of Legends
In my moderately educated opinion.
Control them, sure-kiting 100 units at a time would be a breeze-but using them together in a coherent way is drastically more difficult.