You thought a Zerg rush was bad before..
January 19, 2011 9:05 AM   Subscribe

The 2010 AI and Interactive Digital Entertainment conference hosted a Starcraft AI Tournament last October, pitting AI algorithms against each other. The winner was the Berkeley Overmind agent, and one member has written a fascinating article describing how their AI evolved, how it went up against one of the top SC players in Europe, and eventually won the competition.

There are videos available to view of the matches, along with SC replays (you'll need the SC game installed to view the replay files).
posted by SirOmega (30 comments total) 12 users marked this as a favorite
 
Starcraft is interesting because bad UI is a straight up feature of the game -- for example, there are mechanics where one must remember to do something every n seconds, so as to reward those that do remember and penalize those that are "too busy". More importantly, control over one's army is very loose, and near-inhuman levels of command issuance ("micro") are required to get the most out of one's units.

Quite literally, people measure their play by APM -- Actions Per Minute. If you can't manage over 200 (3.33 commands a second) you have trouble being competitive.

So there's a fundamental advantage to the AI here -- it can issue near infinite APM, in this case guiding the air units individually according to maximum value per move. This is fairly tremendous, and means that the AI Mutalisks are literally a very different unit with exceedingly different expected damage values than a human controlled unit.
posted by effugas at 9:18 AM on January 19, 2011 [10 favorites]


That being said, this is super cool research, and the fact that they've gotten the rest of the game figured out enough such that the superpowered mutalisks can even get into play is impressive.
posted by effugas at 9:19 AM on January 19, 2011


effugas, if it got to be a problem, it would be pretty easy to fix that by lowering the max APM for AI's.

Also interesting to me would be a combined human/computer player, using the pathing and default behavior of the ai, plus a computer player tweaking the strategy on the fly.
posted by empath at 9:21 AM on January 19, 2011


*err, human player tweaking, etc..
posted by empath at 9:21 AM on January 19, 2011


Starcraft is interesting because bad UI is a straight up feature of the game -- for example, there are mechanics where one must remember to do something every n seconds, so as to reward those that do remember and penalize those that are "too busy"

This is, btw, not quite accurate. The memory/busy work part of it does separate the terrible players from the great players, but at higher levels, the macro mechanics let players tweak their strategy for maximum efficiency. It's not just important that you use the macro mechanics, but how and when you use them. For Protoss, it matters which units you chronoboost, or whether you save it up. Same goes for terran and using mules vs scanning. The zerg macro mechanic is kind of lame, because you almost always want to inject larva and if you forget you can't really save it up like you can with mules and chronoboost, but there is still the option to spread creep and transfuse or use the queen to attack.
posted by empath at 9:26 AM on January 19, 2011 [1 favorite]


Yeah, in a few years I would expect this competition to have APM rate-limited (say, 200APM) category, so that the AI not only has to figure out what to do but how to spread out those actions over the next few seconds, or how to make the most of the commands its has at its disposal.
posted by SirOmega at 9:28 AM on January 19, 2011


Fascinating!

RTS games are fun in theory, but in practice your units are so stupid it becomes boring, you need to micromanage everything. I want a hybrid RTS where I can tweak the AI of my own units, but also make decisions myself. Internet, make it so!
posted by Tom-B at 9:39 AM on January 19, 2011 [1 favorite]


The silliness of micromanaging is why I always liked Total Annihilation. Its a shame that style of RTS never really caught on.
posted by cotterpin at 9:45 AM on January 19, 2011 [3 favorites]


Time, and with it the ability to issue commands, is also a resource that requires management.

I think a key feature of "RTS" is the Real-Time component. Otherwise, it just becomes strategy. Personally, I prefer pure strategy, but you don't get the adrenaline rush that you do with RTS. And I suck at Starcraft.
posted by Xoebe at 9:56 AM on January 19, 2011


ROFL! They Benny Hillified the video with Sparky the Wonder Drone!
posted by Xoebe at 10:05 AM on January 19, 2011


Wow, thanks for sharing this!
I've dabbled in working on strategy computing, and reading about their process is amazing. Makes me wish I was back in college working on it.. sigh. :)

I enjoyed playing starcraft many years ago, but haven't played in quite some time.
I also used to be an avid chess player, so the comparison of a chess "opening" to beginning resource strategy at starcraft was interesting, especially the way the expert player completely ruined the AIs plan during development! good stuff.
posted by kevdog at 10:24 AM on January 19, 2011


I think this is actually SC1 rather then SC2. The built in AI in SC2 is actually setup so that the "hardest" level (the insane AI) actually mines more minerals then you do, so it can produce units more quickly. The "Very Hard" AI is not all that hard to beat.
effugas, if it got to be a problem, it would be pretty easy to fix that by lowering the max APM for AI's.
You would really need to do more then that though, humans might have a high APM but I think a lot of that comes down to muscle memory in executing certain maneuvers. Not every APM is the same. For example, if you have a bunch of sentries and you want to lay down a bunch of force fields, that's a bunch of APM but it just requires pressing a key and hitting a mouse where you want to lay them down. It would be *really* hard to move individual units at the same frequency.

Even if you were APM limited, being able to optimize the actions would still give you a pretty huge advantage.
posted by delmoi at 10:34 AM on January 19, 2011


I'd say the biggest advantage the AI has here is the ability to instantly select every single unit in its army, individually, whereas human players are limited to a dozen saved slots plus whatever they can click.

At heart, I'm just not interested in a game which requires APM in excess of a couple of dozen. Which is why I play Civilization and RPGs, not RTSes.
posted by valkyryn at 10:39 AM on January 19, 2011 [2 favorites]


Time, and with it the ability to issue commands, is also a resource that requires management.

I think a key feature of "RTS" is the Real-Time component.


For sure, but I've never played a RTS that didn't make me feel like I was actively fighting the game' user interface at least as much as fighting the actual enemy. (Seems to me the iPad multi-touch screen is be a nearly** ideal solution to that problem.)

Given that an AI doesn't have to deal with the clickity-click, can conceivably individually control each unit optimally, and will never miss a production schedule by more than a microsecond, I can't see a human opponent being able to hang with AI... like EVER... once the tactics routines are nailed down.

** It's still a bit small -- a coffee table-sized Microsoft Surface would be fantastic!
posted by LordSludge at 10:55 AM on January 19, 2011 [1 favorite]


@LordSludge - you mean something like this
posted by silence at 10:59 AM on January 19, 2011


For sure, but I've never played a RTS that didn't make me feel like I was actively fighting the game' user interface at least as much as fighting the actual enemy.

I have mixed feelings reading about these AI projects because the way they've made fighting the AI the more of the game than the game has, well, killed the game for me.

Been waiting for Starcraft II for ten years and finally got it for Christmas. Played the entire single player campaign in about four days; literally could not get up from my chair. So done with that, said "okay, so clearly the BIG deal here is the multiplayer, right?" And the game tells me "welcome to multiplayer. We're starting you in the 'practice league.' We recommend you play fifty matches here before moving forward. ...What the balls?

There are also training areas to teach you how to use hotkeys correctly, because if you don't know them, you're pretty much fucked. I tried a few matches and unless you have the muscle memory to type out the equivalent of Ivanhoe in specific letter-press sequences you are going to waste fifty percent of that precious first two minutes scrolling you mouse over to command buttons.

Ultimately, this has all created wonderful new avenues for AI and robotics but the me from ten years ago feel like they had to ruin a great game for casual players to do it. Yes, Starcraft is an RTS, and yes, RT means "real time" but there HAD to have been a happy medium between chess and.... this.
posted by XQUZYPHYR at 11:17 AM on January 19, 2011 [1 favorite]


This competition uses Starcraft 1 and its expansion, Brood War. The screenshots in the article are a giveaway, and Goliaths don't exist in SC2 multiplayer.
posted by tylermoody at 11:35 AM on January 19, 2011


We recommend you play fifty matches here before moving forward. ...What the balls?

You can skip it, but you will absolutely get demolished on the ladder if you don't.
posted by empath at 11:40 AM on January 19, 2011


Ultimately, this has all created wonderful new avenues for AI and robotics but the me from ten years ago feel like they had to ruin a great game for casual players to do it. Yes, Starcraft is an RTS, and yes, RT means "real time" but there HAD to have been a happy medium between chess and.... this.

Starcraft multiplayer is casual?

posted by Sebmojo at 11:47 AM on January 19, 2011 [1 favorite]


More accurately, I can't see how it's ever been casual. SC is the byword for obsessively intricate tweaking of build orders and inhuman levels of skill and dedication. Adding a tutorial and a practice league has made it vastly more casual than it ever has been before.
posted by Sebmojo at 11:48 AM on January 19, 2011


you mean something like this

Well actually I meant playing RTS *on* the iPad (or MS Surface), but that app is pretty neat lateral thinking. I could see multiple players, each with their own iPhone or iPad, each with a different role -- some collecting resources, some building infrastructure, some building defenses, some spearheading attacks...
posted by LordSludge at 12:24 PM on January 19, 2011


RT means "real time" but there HAD to have been a happy medium between chess and.... this.

For something a little slowed down, I'd recommend you take a look at the (aging) Company of Heroes. There is a free-to-play online version that might be a decent place to start. It is possible through some strategies to make tradeoffs that allow you to temporarily focus your attention somewhere else. By any measure, it's a loss less clicky-click.
posted by minedev at 2:57 PM on January 19, 2011


Does that actually count as "AI" anymore?
posted by indiscriminate at 4:24 PM on January 19, 2011


Might be relevant to this thread - Starcraft 2 AI via Direct X Interception

This is a program that plays Starcraft 2 (SC2) by intercepting, understanding, and reacting to the D3D9 API stream, then sending keyboard and mouse commands back to SC2. It uses the D3D9 API Interceptor project. It is not at all like AIs made in the SC2 editor using the built in scripting language, or projects like BWAPI (which is for the original Starcraft only) that work by attaching to the address space of the host application. AIs written using these other methods are often able to bypass several restrictions that all human players must cope with; for example, they can simultaneously issue different actions to different units, they do not have an active viewport and are thus able to see exactly what is occurring off-screen at all times, and they do not have to deal with trying to click on ground units that are covered by flying units. I chose this method both because I both found it more novel than many other approaches taken to automation problems, and because being a computer graphics programmer it is easier for me to work with the graphics API calls rather than the SC2 code itself. Furthermore, working with the API calls generalizes more easily to interfacing with different applications. Of course, this AI still has a significant APM advantage over human players.
posted by xdvesper at 6:03 PM on January 19, 2011 [2 favorites]


RTS games are fun in theory, but in practice your units are so stupid it becomes boring, you need to micromanage everything. I want a hybrid RTS where I can tweak the AI of my own units, but also make decisions myself. Internet, make it so!
posted by Tom-B at 9:39 AM on January 19 [1 favorite +] [!]


I played a game exactly like how you describe. It's called World of Warcraft :)

What you do is you get really good at PVP. Then recruit and form a team and go play battlegrounds as a team leader.

Here's what you see - dots on the map representing your "units", as they advance to their objectives. Fog of war is total - you can't ever see enemy units. You must rely on verbal reports through your headphones to form a mental map in your mind where the enemy is attacking and defending. (For this you have to train your team to be extremely concise in relaying information). Based on the opposition they encounter and reports you receive, you have to reassign units, abandon objectives, switch strategies, anticipate where the opponent is striking next.

So - to some degree your "units" have their own AI - they are all human players after all. They can disobey your orders, they won't attack into a hopeless battle, they will assist nearby teams. In fact, I specifically recruit a few exceptionally good players who WILL disobey my orders occasionally - I can't micro-manage everything, and if they see a point of weakness in the enemy they will break away and take it. It's about trust. Yet I can't have my entire team consisting of such players, or my overall strategy will fall apart - where the various small units cannot rely on each other to be where I need them to be. I usually attach them as a +1 unit to a particular team which can function with or without them, leaving them free to roam.

And to some degree you can tweak your "units" AI - you give them instructions, group players who have synergies with each other, etc. You recruit only the types of players you want. You only intervene to give verbal orders when the situation evolves to something that wasn't included in your original strategy.

I felt like Ender on most days, watching the dots inch across the map, trying to imagine where the enemy was, hearing reports through my headset, giving out terse orders with my mic. The best part is when you've won, instead of just seeing your surviving marines and tanks on the screen, you can hear cheering over the headset.

This was absolutely the best game I have ever played.
posted by xdvesper at 6:20 PM on January 19, 2011


Last year I got a bit addicted to watching Husky's commentated replays of SC2 matches. For a while it was fascinating, like watching a series of beautifully animated games of chess where each time the pieces in play are different in all sorts of crazy ways and you never know what's going to happen.

I lost interest as it became obvious just how heavily the game mechanics rely on the deliberate limitations of the interface. For example, the usefulness of area-effect attacks like the protoss storm thing is dependent on players being unable to order basic ground units like marines to stand around in loose groups rather than bunch up together in easily-slaughtered lumps, and the importance of various interlocking rock-paper-scissors style unit-versus-unit matchups combined with the speed of battle, the limit on selected group sizes and the lack of control over unit targetting seems to mean that a lot of battles end up with one giant ball of units against another giant ball of units whittling each other away while the result is decided by who can give the right commands to the spellcaster units hanging around the edges, if it wasn't already decided by who had chosen the correct macro style. Oh well. Or am I missing something?

This is a program that plays Starcraft 2 (SC2) by intercepting, understanding, and reacting to the D3D9 API stream

Now that is impressive.
posted by A Thousand Baited Hooks at 3:31 AM on January 20, 2011


For sure, but I've never played a RTS that didn't make me feel like I was actively fighting the game' user interface at least as much as fighting the actual enemy. (Seems to me the iPad multi-touch screen is be a nearly** ideal solution to that problem.)
Well, with SC2 at least you really have to learn how to play it, using hotkeys and the keyboard and stuff. Complaining about not being able to pick it up instantly is like complaining about not being able to pick up a guitar and start wailing immediately.
So done with that, said "okay, so clearly the BIG deal here is the multiplayer, right?" And the game tells me "welcome to multiplayer. We're starting you in the 'practice league.' We recommend you play fifty matches here before moving forward. ...What the balls?
50 matches is the max. You don't have to play any at all if you don't want. The only difference between practice league and the real league is that the maps are setup so that you can't get into the other player's base without breaking down some rocks or getting air units. The reason for that is to give new players a chance to acclimate to multiplayer before getting destroyed in 2 minutes to a rush. The play speed is also slower. You're not playing against AI in the practice league.

The other thing is:
Ultimately, this has all created wonderful new avenues for AI and robotics but the me from ten years ago feel like they had to ruin a great game for casual players to do it. Yes, Starcraft is an RTS, and yes, RT means "real time" but there HAD to have been a happy medium between chess and.... this.
What the hell are you talking about? I don't even understand how this makes sense, because when you play multiplayer you play against other people, not the AI. How good or bad the other players are has nothing to do with the in-game AI.

When you play in the practice league, you play against other players in the practice league.

And beyond that, once you play a bunch of games you'll be "placed" with players at your same skill level. So if you suck, your opponents will suck too. It's designed so that you'll win about 50% of your games no matter how bad you are.

Honestly the comment is so bizarre. The AI competitions like this have absolutely nothing to do with the online game. They are all designed for SC1 and really only exist in the lab. People aren't using AIs when they play the game online, if they did they would get banned.
I lost interest as it became obvious just how heavily the game mechanics rely on the deliberate limitations of the interface. For example, the usefulness of area-effect attacks like the protoss storm thing is dependent on players being unable to order basic ground units like marines to stand around in loose groups rather than bunch up together in easily-slaughtered lumps, and the importance of various interlocking rock-paper-scissors style unit-versus-unit matchups combined with the speed of battle, the limit on selected group sizes and the lack of control over unit targetting seems to mean that a lot of battles end up with one giant ball of units against another giant ball of units whittling each other away while the result is decided by who can give the right commands to the spellcaster units hanging around the edges, if it wasn't already decided by who had chosen the correct macro style. Oh well. Or am I missing something?
Well, aside from the fact there are no practical limitations on group sizes, and that you can control unit targeting, you're right: Who wins the game is determined by the skill of players.
posted by delmoi at 4:36 AM on January 20, 2011


Oh, and also there's a whole meta-game of scouting and adapting what you do based on what you think your opponent is doing. So scouting, and preventing scouting is actually a key component.
posted by delmoi at 4:37 AM on January 20, 2011




OK, this has to go somewhere, it might as well be here:

Insanely awesome mothership end-game play from KiwiKAKI

posted by anthill at 3:06 PM on February 8, 2011


« Older Browser as Graphing Calculator   |   Twitter-controlled everything! Newer »


This thread has been archived and is closed to new comments