Student StarCraft AI TournamentOpen to all; students can win prizes. The live stream of automated games can be entertaining; it is supposed to be 24/7 but is not fully reliable. Running since 2011.
The original StarCraft: Brood War, from 1998, is one of the great real-time strategy games and also a great AI challenge. Regular AI competitions exist. Some top bots use learning, and there is room for much more.
If you memorize this page and are still not satisfied, I started a Starcraft AI blog.
| Jay : game learning : StarCraft |
StarCraft is a magnificent AI challenge. To play well requires a top-level strategy, a plan (perhaps at multiple levels of abstraction) to implement the strategy, detailed control of a large number of units to implement the plan and to react to contingencies, deliberate information seeking (scouting), real-time replanning and re-strategizing when new information appears, all using plan recognition from the enemy’s actions in an environment where information is incomplete, deception may be wise, and impure strategies are often best (meaning that players should make some choices randomly). The low level decision cycle is fixed by the game at 24 logical frames per second, 42 milliseconds to (in principle) think about whether each unit (of perhaps hundreds) is taking the best action it can. Playing StarCraft is conceptually similar to robot control, minus the difficult low-level perception and motor aspects; it includes high-level perception, adversary planning under uncertainty, and detailed coordination of diverse resources.
Expert human StarCraft players do all this impressively well. Computers have the theoretical advantage of being faster, able to control each unit in a large army independently in real time. But as of 2015, human ability utterly dominates the computer’s speed advantage. The game is rich and difficult to play well, and bots are still at an ad hoc level of design maturity; authors are trying out ideas and in my view haven’t settled on a good concept yet. Many bots use machine learning for specific tasks, and I think there's wide scope for more.
StarCraft is also a complex game—skilled players know a lot of details of behavior. If a terran turret stops rotating, that means a protoss observer unit is parked exactly above it, blocking the turret from firing. You can start the turret up again by repeatedly pressing S for stop (laugh now), and it will shoot down the observer. That’s a gimmicky special case (basically a bug), but the regular behavior of units is complicated too. This post (using some information from this blog post) goes into some of the complexities. Basic unit characteristics can be coded (cost to build, movement speed, firing range, etc.), but I think it makes sense for a bot to learn the many fine points of how units interact with each other, with special abilities, and with terrain.
The AI competitions are possible in part because the game is old and its maker, Blizzard Entertainment, no longer tries to control cheating by players who use unauthorized software. That also means that technical support is unofficial. The interface software for bots, BWAPI, is a fan product and relies on analysis of the StarCraft binary. Expect care to get all the software to play together.
The competition pages include instructions and pointers to the software you’ll need.
Student StarCraft AI Tournament
Open to all; students can win prizes. The live stream of automated games can be entertaining; it is supposed to be 24/7 but is not fully reliable. Running since 2011.
AIIDE StarCraft AI Competition
An annual event with an academic focus, associated with the AIIDE conference. Every year since 2010.
CIG 2015 StarCraft AI Competition
With the Computational Intelligence and Games conference. Annual since 2011, with a new web address each year.
A few selected publications. I want to add one about plan recognition, but I haven’t found a convincing one yet.
A survey of real-time strategy game AI research and competition in StarCraft (2013)
Santiago Ontañón, Gabriel Synnaeve, Alberto Uriarte, Florian Richoux, David Churchill, Mike Preuss
Not the latest, but the most thorough overview.
Build Order Optimization in StarCraft (2011)
David Churchill, Michael Buro
You give a list of what things you want to build, and the build order planner BOSS does a branch-and-bound search to find a near-optimal plan to build them, assuming no interference from the enemy. When the enemy does interfere, you can tell BOSS the new circumstances and get a fresh plan. The underlying design is elegant, but the details grow complicated, and you may not always get an exactly optimal plan because of simplifying assumptions made to get real-time performance. You could say that the plans in sequence are “piecewise (until this plan is over or the situation changes) approximately optimal.” Solves the problem “build this stuff fast” which is usually what you want in the opening. It does not solve the middle game problem “use my money efficiently.” Needless to say, “what do I want to build?” is a separate question and not an easy one.
Portfolio greedy search and simulation for large-scale combat in StarCraft
David Churchill, Michael Buro
Methods used in the SparCraft system of combat simulation for tactical decisions (should I attack or run away?) and control of units during battle (“micro”). Details are simplified away for speed, but it is said to be pretty accurate. David Churchill’s bot UAlbertaBot appears to use SparCraft for attack/run-away decisions but not for micro, and I’m skeptical about whether the micro application is sound. Even if not, it could help with many other tactical decisions, such as “should I form up my army for the attack like this, or like that?” and “this mining base is under attack, should I leave the workers mining (the defense is enough), bring them out to join the fight (with their help the defense is enough), or run them away to try to keep them alive (the base may be lost)?”
StarCraft AI wiki
Not much total information, and some of it out of date. But I thought that StarCraft Brood War Data Mining was interesting.
StarCraft AI Competition Data Archive
Results of the AIIDE and CIG competitions for every year, with info about each event and each bot, sometimes including a bot download and an interview with the authors.
Bots
Category page from Team Liquid’s Liquipedia wiki, listing bots with brief information.
Atlantis
A Java framework for building StarCraft bots. Not a competitive bot in itself, the framework provides basic economy, scouting, and unit control behaviors but doesn’t include any combat strategy. The goal is to make it easy to get started.
OpprimoBot
Weaker C++ bot. A potential starting point for new development; some other bots are based on it.
tscmoo
Strong C++ bot. Winner of the 2015 University of Alberta competition. The bot has a large number of hand-coded strategies, and learns online which ones work well against each opponent. Capable but complex and idiosyncratic, it is probably not a good starting point for most people.
UAlbertaBot
Pretty strong C++ bot. Nicely designed and documented and includes two sophisticated systems well worth reusing, the build-order search BOSS and the combat simulator SparCraft. The rest seems to me just enough hand-coded logic (rather a lot) to play a reasonable game. That makes it a good starting point for fresh development, and many other bots are based on it. It does have strategy learning similar to tscmoo’s (lately turned off).
The 2015 AIIDE competition report shows off 7 games by the competition’s top 3 bots against an expert human player, Djem5. Djem5 made the bots look helpless in every game.
I would like to add a more impressionistic comparison. Here is a human game from the point of view of zerg player Zero against terran Mind on the map Circuit Breaker, played on 13 November 2015. Both are Korean former professional StarCraft players, elite players far stronger than Djem5.
Watch the zerg attack starting around 9:15. The terran forces were split into a home army to guard the base and a field army out to cause trouble. The split is necessary because zerg units are faster than terran but terran cannot simply camp at home, and possible because the terran army is stronger in a stand-up fight. In the attack, zerg exploits its mobility to bypass the field army and defeat the home army, breaking into the terran base. Zerg units immediately split into two task forces. One attacks the terran miners but is soon wiped out by the returning field army. The other, with lurkers, runs up the ramp to split the terran base and control the barracks, so that new marines coming out are killed. When a new terran tank is produced and joins the fight, the lurkers move back to the ramp to engage the marines in the field army, to do the most possible damage while they can. Tanks counter lurkers; lurkers counter marines.
Expert players instantly understand the connections between the tactical and strategic levels. Tactically, the zerg attack is an efficient use of units, despite being a suicide mission. Operationally, it is the exploitation of a fleeting opportunity to harm the enemy while the field army is distant. Strategically, it protects the creation of a new zerg base at the 7 o’clock corner. Overwhelmed by larger numbers of zerg units once the new base is fully on line, terran soon surrenders.
To represent machine play, here is a video from the Student StarCraft AI Tournament showing recent top bots, narrated by Nepeta.
Some low-level behaviors are impressive, but overall the bot play comes across as inconsequent, with little understanding of cause and effect. The bots are indecisive and have trouble staying out of range of unnecessary enemy fire. For example, watch the last game of the video, where protoss units repeatedly run into deadly long-range tank fire, retreat on seeing that no attack can succeed, then lose sight of the tanks and run back into range (hey, maybe the tanks moved away). The careful scouting and inference of intentions that we saw in the human game are not there at all.
I don’t think it’s because bot coders are bad. It’s because StarCraft is hard. That said, some improvements are obvious. Bots seem to lack the basic military instinct of “hit ’em where they ain’t” so extremely that they allow a large army to be distracted from its goal by a single passing enemy that poses no threat, or in an emergency send valuable workers out to fight and die instantly instead of making the enemy work to get them.
From here to the end of the article I discuss ideas to allow bots to approach the game in a more principled way, rather than the ad hoc way they do now. I believe, and the history of other games shows, that a principled approach is necessary to make big progress.
Above I mentioned opponent modeling.
How can a bot adapt rapidly to a novel situation? Hierarchical statistical models have been proposed as a solution, but I think we need more.
Humans come up with new ideas and adapt quickly to novel situations by reasoning from mental models. As of 2015, AI work is concentrating on empirical learning methods that cannot invent new ideas and that adapt gradually to novel situations. Forming models and reasoning about them is a key research area.
This two-part video shows a 2009 game between protoss Horang2 and terran Light, professional players at the time, on the map Destination. CholeraSC provides commentary.
Protoss hides one of his first probes in the terran base to build a later in-base proxy, meaning to build protoss buildings inside the terran base for a surprise attack. A proxy is usually an all-in strategy; if your proxy buildings are spotted too soon, you are likely to lose quickly. In-base proxy openings are rare in expert play because of the high risk. Here protoss Horang2 seems to have found a way to mitigate the risk with a one-off trick.
At 3:08 in the first part of the video, a terran SCV makes a loop around the north of the terran base to check for early protoss shenanigans (watch the minimap in the lower left), but the probe was so early that it is already hidden away to the east. At 4:30 a terran marine scouts the north again; terran believes he only needs to look north, because a protoss proxy to the east would be seen by the mining workers. Afterward, the undiscovered probe moves north and builds the proxy in the area just scouted, gaining a large advantage and easily winning the game.
Horang2 must have studied his opponent’s play closely to notice the gap in scouting that could be exploited. Just as the marine scout could not see the probe, the probe could not see the marine, yet the probe built the proxy right after the marine was gone, so Horang2 likely knew Light’s timing from study of past games. This deeply ingenious innovation is far beyond the state of the art for AI, but we can imagine in outline how to do it by opponent modeling with analysis of the model for exploitable behaviors. What the model might look like is an interesting question!
Succeed with this trick against a bot, and the bot will react poorly and lose on the spot. Bots in 2015 are only able to react sensibly to expected situations. Light, though mortally hurt, was able to make shift to fight on for a while.
Imagine that Horang2 and Light played another game on the same map. Would the same trick work again? No, even without checking the game replay to see exactly what happened, Light would understand that the proxy was possible only because a probe snuck into his base, figure out where it must have been hiding, and be sure to scout there. Countering the trick once it is known is much easier than thinking up the trick in the first place. A bot could do this with a general form of explanation-based learning: Infer an explanation of how the opponent achieved its results, then with the explanation in hand, choose a plan to counter the opponent’s actions. EBL and similar reasoning techniques allow humans to learn from one trial what takes a purely empirical learning agent many, many trials. Reasoning makes for fast adaptation.
Note: 1980’s research into EBL cast the learning problem in narrow logical inference terms, which was eventually shown to be fruitless. Instead of recasting the insight behind the invention of EBL into new terms, people mostly lost interest. The idea behind the original insight is: Given a theory (what you already know) and an observation (what you see), you may learn something if you can use the theory to infer an explanation of the observation (if you can interpret what you see). If you have an explanation for how a probe built in your base without being noticed, then you learn a weakness in your play and get a strong hint about how to correct it. The EBL insight holds no matter the form of your theory; a logical model, or a statistical model, or any kind that will let you draw inferences from what you see. (A hierarchical Bayesian model seems like a good try.)
In my view, the integration of reasoning and empirical learning is what AI needs to be working on now. StarCraft is a magnificent AI challenge.
Learning and use of highly abstract information is another key research area.
Suppose you want to model StarCraft strategy. The most basic considerations, independent of specific game play, are the economy, the technology, and the military force of each player. At any given moment, spending more on one of those means you’re investing less in the others. A bot with that basic abstract model would have to learn the details of how the game outcome depends on each, but once it had learned, it could do high-level reasoning about StarCraft strategy.
For example, the famous “zerg rush” (technically a zergling rush) sacrifices early economy (workers to mine minerals) for tech (a spawning pool to allow hatching zerglings) and a quick military force (the zerglings) that may be able to surprise and overwhelm the enemy. A bot with the basic strategy model would be able to discover tech rushes on its own and learn which ones are effective when (a dark templar rush can win if the opponent is unprepared; a battlecruiser rush, not so much). Reasoning and empirical learning together are more than the sum of the parts.
A more complete model that included time and terrain would be able to reason about maps as well. It would be able to figure out for itself that a zergling rush is more effective on a small map, and understand the reason: The opponent has gotten less done by the time the zerglings arrive. The bot with a model would be able to discover proxy strategies on its own, making its play more varied; many proxy strategies exist that humans play occasionally but no bot plays today because each strategy has to be individually coded and tuned. It could also make sensible strategic decisions in everyday situations: The opponent just invested in an expansion, which will help its economy soon. If we’re about even then I could either expand myself to keep up, or attack now while the opponent’s army is briefly stretched because of the diverted funds and larger area to defend. 2015 bots cannot understand this simple logic.
One idea: An abstract strategy model that has learned to predict the future strategy state amounts to a simulator and can be used for Monte Carlo planning to make strategy decisions. If it’s good enough, it could see several steps ahead and discover tricky strategies: If I do X it forces the opponent to respond with Y, then I can exploit Y with Z: If I build corsairs, that will force zerg to counter with hydralisks, then I can threaten the hydralisks with psionic storm (one of the ideas behind the most popular and successful current protoss versus zerg strategies).
A defining aspect of intelligence is foresight: I could do A or B, and A looks like it will turn out better. That is why successful programs in most games feature lookahead search—to play well, you have to compare alternatives.
In most game searches, the search looks at concrete game states in full detail, or with only mild abstractions (such as ignoring the 50-move rule in chess). Concrete game states are easy for the programmer to think about. Above I proposed searches through abstract strategy spaces to find good strategies. In StarCraft, the game state is only partially known, since you can’t tell what your opponent may be doing outside your view. It’s still possible to carry out a concrete search by estimating or sampling the parts of the game state that are unknown, but it’s not convenient. Also, the game state is large and complex, which makes it expensive to reason about, and StarCraft is a real-time game. Searching over abstract game states should help a bot make decisions faster.
A way to think about it: One node of an abstract search corresponds to many different game situations, which in a concrete search would be different nodes. Suppose I’m thinking about how to move my large army around the map to gain an advantage. A concrete search where I simulate the movement of each unit might be good for figuring out how to move through a choke point without creating a traffic jam, but it will be expensive if I want to look further ahead. An abstract search might say, “I don’t care where each individual unit is, I want to group my units and maneuver the groups to protect myself and threaten my enemy.” The bot MaasCraft as described here (a “faq” link from a data table in U. Alberta’s Starcraft AI Competition Data Archive) uses an abstract search of that kind. (It mentions Lanchester’s Equations, a very simplified way to estimate the outcome of a battle.)
To compare situations and know what to choose, a search needs some kind of evaluation function, whether a traditional heuristic evaluator or playouts (a statistical sampling evaluator that works by playing out possible future events). The combination of search with evaluation will create much more flexible and adaptive play than the brittle rules that many bots now use to make decisions.
A bot may want different kinds of search for different kinds of decisions.
Humans learn to exploit their opponents’ weaknesses with terrifying ease. Above I gave one example of how a human can learn important facts from a single trial via explanation-based learning. But there’s more to it.
StarCraft bots are good enough that they can beat average players—but only once. By the second game, a human who lost has typically already figured out a winning plan and will not lose again. This video of a “bonus Man vs. Machine match” from the Student Starcraft AI Tournament 2015 shows an average player losing one game badly and bouncing back to win the second.
More skilled humans, who won’t lose in the first place, can spot mistaken patterns of play within seconds and exploit them on the spot. An example is this video of human zerg Bakuryu versus protoss bot Aiur, a demonstration game from the 2012 AIIDE. See the action at about 5:00 minutes in where Bakuryu realizes that one zergling can distract the bot’s zealots for a long time, allowing zerg to make extra drones and gain an economic advantage.
I don't know how to duplicate this devastating human adaptability, even in principle. It's an open research question. I suggest approaching the question as plan recognition or goal recognition. I might start with a catalog of possible goals and try to understand how to recognize each one.
Some cases are easy. If you see a train of workers passing by, then the goal is probably “transfer workers to another base,” and you may be able to tell which base. Plug the information into the bot's search and it should come up with a smarter plan than it would have otherwise: “Find and attack the new base!” That would already be an advance over current bots.