Starcraft AI Competition

post by JoshuaZ · 2011-01-19T21:45:59.444Z · LW · GW · Legacy · 7 comments

Ars Technica has an article about A Starcraft AI competition.. While this is clearly narrow AI there are some details which may interest people at LW. The article is about the best performing AI, the "Berkeley Overmind." (The AI in question only played as Zerg, one of the three possible sides in Starcraft. In fact, it seems that the AIs in general were all specialized for a single one of the three sides. While human players are often much better at one specific side, they are not nearly this specialized).

Highlights from the article:

StarCraft was released in 1998, an eternity ago by video game standards. Over those years Blizzard Entertainment, the game’s creator, has continually updated it so that it’s one of the most finely tuned and balanced Real Time Strategy (RTS) games ever made. It has three playable races: the human-like Terrans, with familiar tanks and starships, the alien Zerg, with large swarms of organic creatures, and the Protoss, technologically advanced aliens reliant on powerful but expensive units. Each race has different units and gameplay philosophies, yet no one race or combination of units has an unbeatable advantage. Player skill, ingenuity, and the ability to react intelligently to enemy actions determine victory.

This refinement and complexity makes StarCraft an ideal environment for conducting AI research. In an RTS game, events unfold in real-time and players’ orders are carried out immediately. Resources have to be gathered so fighting units can be produced and commanded into battle. The map is shrouded in fog-of-war, so enemy units and buildings are only visible when they’re near friendly buildings or units. A StarCraft player has to acquire and allocate resources to create units, coordinate those units in combat, discover, reason about and react to enemy actions, and do all this in real-time. These are all hard problems for a computer to solve.

Note, that using the interface that humans need to use was not one of the restrictions. This was an advantage that the Berkeley group used to full effect, as did other AIs in the comptetion.

We had to limit ourselves. David Burkett, another of Dan’s PhD students and the other team lead, says, “It turns out building control nodes for units is hard, so there’s a huge cost associated with building more than one [type of] unit. So we started asking: what one unit type [would be] the most effective overall?”

We focused our efforts on Zerg mutalisks: fast, dragon-like flying creatures that can attack both air and ground targets. Their mobility is unmatched, and we suspected they would be particularly amenable to computer control. Mutalisks are cheap for their strength, but large numbers are rarely seen in human play because it’s hard for a human to manage mutalisks without clumping them and making them easy prey for enemies with area attacks (attacks that do damage to all units in an area instead of a single target). A computer would have no such limitations.

The programmers then used a series of potential fields to control what the mutalisks did, with different entities and events creating different potential fields. A major issue became how to weigh these fields:

Using StarCraft’s map editor, we built Valhalla for the Overmind, where it could repeatedly and automatically run through different combat scenarios. By running repeated trials in Valhalla and varying the potential field strengths, the agent learned the best combination of parameters for each kind of engagement.

The article unfortunately doesn't go into great detail about the exact learning mechanism. Note however that this implies that the Overmind should be able to learn how to respond to other unit types.

There are other details in the article that are also interesting. For example, they replaced the standard path tracing algorithm that units do automatically with their own algorithms.

The final form of the AI can play well against very skilled human players, but it isn't at the top of the game. Note also that the Overmind is designed for one-on-one games. It should be interesting to see how this AI and similar AIs improve over the next few years. I'd be very curious how an AIXI would do in this sort of situation.

 

 

 

7 comments

Comments sorted by top scores.