StarCraft: Building A Brilliant Brood War Bot
All about that base?
The Student StarCraft AI Tournament is an AI vs AI tournament which pits bots programmed to play StarCraft: Brood War against one another. SSCAIT started in 2011 and is one of three major Brood War AI tournaments. Last year's student division title went to Martin Rooijackers and his creation, LetaBot. They also won the 2014 student and mixed division. This year Martin and LetaBot made it through to the quarter-finals.
While the bots continue to battle I've been asking Martin to tell me more about how they work. Are some of Starcraft's races easier to build bots for than others? What's the hardest thing to get bots to do? And is LetaBot built to dominate a bot meta or could it take on humans too?
Pip: Hi Martin, can you tell me a little about yourself and why you take part in SSCAIT?
Martin Rooijackers: I am Martin Rooijackers, a master student at Maastricht University. Designing a StarCraft bot is part of my master thesis. The reason for participating in the SSCAIT is to test how well my algorithms perform against other bots.
Pip: Can you introduce LetaBot and tell me a bit about how the AI works?
MR: I started out LetaBot with the idea to create a Terran version of the Berkeley Overmind [the Berkeley Overmind is an AI agent for playing Brood War which won the AIIDE 2010 StarCraft competition - you can read a really detailed Ars Technica post about it here] with Wraiths instead of Mutalisks as the air unit that will dart around the place. While experimenting against other bots, I found that all of them had problems with the early game. So I decided to focus on that problem first.
LetaBot is still a work in progress, but in general it works as follows:
- Open with a build order [the order and timings you use to build units, structures and so on] that is safe from early aggression. Build a wall if needed.
- Try to expand as fast as possible when it is safe to do so.
- Tech up to air unit while keeping your bases safe [this means getting as far into the build order as you need to produce air units]
- Use the air dominance to gain map control and get more expansions
Pip: How did you first approach the problem of designing a Starcraft AI? (For example, were you looking at existing bots or did you start from scratch? Were you looking to solve particular challenges?)
MR: LetaBot was build upon the framework of UAlberta bot [current info for UAlbertaBot on GitHub], since that framework is very modular. Over time I added more modules into it like my mineral-gathering algorithm and my wall-building algorithm.
Pip: Which elements of playing StarCraft are easiest to achieve with bots?
MR: The easiest elements of StarCraft for a bot are:
- Elements that don't need an immediate solution (so they're less real-time constrained). [For those of you that know StarCraft here's an example:] My wall-building algorithm has several seconds to calculate a wall, because the first supply depot is only built after 5 extra worker units are built.
- Elements that can be easily formulated mathematically. An example of this is optimizing mineral gathering [minerals are a resource you go and mine in the game]. You want to reduce the round trip time, which is related to queueing theory.
- Elements where scripted behavior suffices. It is well known in RTS games that you generally don't really want units queued up, since those resources could be used elsewhere (like building a new building). But you do want to ensure that your production facilities are always producing. This is called macro in StarCraft (technically it is the unit production aspect of macro-management). This unit production step is easy for bots, because with their multi-tasking they can always keep an eye on all production facilities and ensure that they all have exactly one unit in production at all times.
Pip: And which elements (if any) are impossible to replicate with bots at the moment?
MR: It may surprise some, but despite being able to perform more actions per minute than a human player, the bots still have sub-par micro-management. Bots have faster individual unit control which allows them to use hit-and-run techniques [dealing damage then moving out of harm's way], but deciding where/when/how to attack/retreat is still a problem.
Pip: There seems to be a decent spread of races in the competition. Are they pretty much equivalent when it comes to the bot challenge or is it easier to program one race over the others?
MR: Due to the fact that micro-management is difficult for bots, it is easier to make a Protoss bot since the Protoss race isn't as micro-intensive as other races. Simply attack-moving can get you pretty far.
Terran can be strong due to the fact that most of their units are capable of hit-and-run tactics which the bot can perform for each unit individually. The main problem with this comes with dealing with the terrain/pathfinding. The other difficulty of Terran is that they only become strong when they have a big ball of units. So surviving early game is more difficult. But once a Terran bot gets out of the early game, it usually overpowers the Protoss and Zerg bots.
Zerg is perhaps the most difficult to program a bot for since Zerg relies heavily on things like flanking movements, surrounding armies, Mutalisk harassment and many more micro techniques.
Pip: You've been entering the competition for a while now - do you find you're programming your bot to play StarCraft or are you more focused on it playing to beat another bot? Basically I'm interested in whether these AI could theoretically play/beat a human or whether they're being built to fight one another.
MR: In the 2014 tournaments I made my bot abuse the lack of early-game defense of just about every bot out there. So back then I was making my bot such that it could defeat other bots (my bot was known as a bunker rush bot back then). After the Computational Intelligence and Games (CIG) 2015 tournament, I saw that rush bots had their last days at the number 1 spot. A sophisticated 4 pool bot [4 pool being an all-in strategy where you rush to build a spawning pool as fast as possible then throw waves of basic units at your opponent] named ZZZKbot won the CIG 2014 tournament. My prediction was that bot developers would realize that they had to develop their early game if they wanted to win.
In the AIIDE (Artificial Intelligence and Interactive Digital Entertainment tournament) several months later, ZZZKbot dropped to second place, and my 2 Rax SCV rush bot [this is a two barracks build that throws worker units and space marines at the enemy] that got 4th place in CIG now got 10th place in the AIIDE. So after that I added macro modules that I'd been working on into my bot, and my bot switched to a macro-oriented play-style. The latest version of my bot (unfortunately not finished in time for the SSCAIT) is finally capable of dealing with any early aggression that I know of. So basically after the CIG 2015 I abandoned trying to win by exploiting the faults in other bots and instead focused on a general macro play-style that can defeat both humans and bots.
Pip: What's the most difficult challenge you've had to solve with LetaBot?
MR: Holding off early game aggression while still going for a fast expansion. Once bots reach the mid-game, their multi-tasking helps them out significantly, but in the early game they don't have enough units to make use of it. With the text-mined build orders from Dennis Soemers and the help of a TeamLiquid user called CardinalAllin, my bot now has the capabilities to adapt to the opponent's army and reach the mid-game.
Pip: What have been your highlights from SSCAIT so far this year? Whose bots have you found most interesting and why? I'm not really a Starcraft player so it would be good to know who is using units well or interesting strategies or if there have been any unexpected breakthroughs in how they play.
MR: This year has been a resurgence of Zerg players. We've had:
- ZZZKbot: the most sophisticated 4 pool bot yet
- Marian Devecka: the newest version of this bot focuses on three units (Zergling/Hydralisk/Lurker). These three units aren't enough for the late game, but the mid-game attack from this bot has proven to be devastating enough to compensate for that fact.
- tscmoop: the bot that can use every unit [which makes it more versatile in theory]. good early defense and late game play, but it still has problems holding off a mid-game attack.
Then there is also a worker rush bot called Stone that managed to get to the quarterfinals utilizing the SCV's (Terran worker units) capability to repair other SCVs.
So the biggest change from last year is that early game aggression has become much more fierce, but at the same time the early game defense has been ramped up (pun intended (a ramp is a choke point you can use as a defensive position FYI* :) )).
These changes will mean that the focus will now shift towards mid-game aggression and defense. My prediction is that the next top CIG (or AIIDE if that comes first) bots will consist of bots that can perform a strong mid-game push and bots that can hold off such a push. There won't be any 1 base rush bots anymore in the Top 3. This tournament will be the last major StarCraft AI tournament to have them. From now on, every bot will have to expand in order to win a (major) tournament.
Thank you for your time!
The SSCAIT semi-finals and finals will take place on 30 January at 8pm CET (7pm GMT) - you can watch via Twitch.
*Pip very much appreciated the explanation because this pun would have sailed overhead otherwise!