This is the first (0th) part of the Creating a Starcraft AI series. Here is the next part, and the index for all the posts.
Introduction
One of my passions is writing an AI for Starcraft: Brood War. This might seem random, but I became interested after finding the Student Starcraft AI tournament page here, and subsequently the Discord community. I even wrote my Bsc thesis on this topic. Originally, i just wanted to write about a specific problem (how to represent build orders), but i decided that i might as well go all the way, and document, and comment how my bot is built from the ground up. So here we are – if you are familiar with Starcraft, or even with the tournament, feel free to skip the following few paragraphs. I probably won’t reach a point where i describe the original problem in this post, but i’ll try.
The game
For those unfortunate few, who do not know, Starcraft: Brood War is a genre-defining RTS (Real-Time Strategy), that came out in the golden year of 1998. The remastered version came out a few years ago, but you can download the original legally, completely free from here. Starcraft is the original game, Brood War is it’s subsequent expansion – since basically no one plays the original, i’ll use the terms Brood War and Starcraft interchangeably from now on. Starcraft was one of the first games to become a fully-fledged e-sport. In the game’s universe, three different races fight for control of the galaxy, with very distinct atmosphere, and game mechanics. The Terran, who are future humans with strong defensive units, and all-around versatility, the Zerg, who are Alien (or Tyranid) like biological creatures with great hordes to overwhelm their foes, and the Protoss, who are mystic psionic aliens, with elite, strong units, and strong abilities. You have three basic resources: Minerals, which can be freely mined from deposits (also called crystals because their look), Vespene gas, that can be mined from geysers after building a specific building on them (Refinery/Extractor/Assimilator), and supply, which is provided by units or buildings.
I don’t really want to go deeper with the introduction, if you haven’t, go play the game! It basically can run on a washing machine (I remember playing it on my 486 with 40 Mhz). Alternatively, if you’re at work or something, there are approximately 42 trillion videos about it on YouTube. Here you have a great example:
The balance, metagaming, and culture
Brood War enjoys a strong following, and tournament scene to this day. Strategies are constantly researched, evolved, and countered. A great collection of those, and a lot of replays can be found on Liquipedia. The balance of the three races is notoriously good, as even after 20 years, there is no clear winner. Since a lot of efficient strategies, and counters are already researched, a lot of games are about recognizing, and effectively negating the opponent’s moves. Most units are good at one specific task, like anti-air, ground defense, or being cheap and cost effective. What buildings, and units to build, and when is a major part of winning games. This is in general called macro play, as it primarily requires careful managing of resources, not fast reflexes.
Contrary to that, there is micro play. Since we are talking about 1998, the unit’s AI and handling was not the standard we are used to today. Pathfinding, attacking, prioritization were very basic (Again, compared to today’s games. What the programmers did was astonishing in their own time, Starcraft is one of the best games ever made), and could be done far better by humans. A lot of actions can be only performed manually – you can send an unit to attack an area, but using abilities (also called spells) can only be done by selecting the unit, pressing the ability button/hotkey, and manually targeting it. Doing this very fast is one of the trademarks of good players, and a very important measurement is APM (actions per minute). Humans peak around 300, and only for short periods of time. Micro play is utilizing the unit’s abilities, attacks, movement, positioning, etc. the best way possible. One of the good examples of this is “kiting”, when a faster unit with a longer range attacks, then retreats, before the opposing unit can reach it.
The best players, have to be experts in micro and macro play as well. Also, a big part of the scene is recording, and viewing replays, where you could see all of the players’ moves, resources, etc. at the same time.
The AI tournament scene
And if you are somewhat familiar with the Brood War scene, this is where you should begin reading. In the tournament’s page, there is a short introduction, and tutorial. I assume you read that, and maybe tried out. I decided to code in Java, for the sole reason that i’m a boring enterprise Java developer at Boring Enterprises Gmbh, and everyone knows that boring enterprise development is always done in Java.
Also, i didn’t want to learn a new programming language when i had about 2 months to complete my thesis. My first bot was a Terran one, and not very good at that, but the point was not to win a tournament, just to make something resembling artifical intelligence.
For my new project, i decided on a Zerg bot. As a human, i mostly played Zerg (contrary to my time when i was a dog), and at the time of the writing, Terran and Protoss are dominating the ladder, so it seems like a good idea.
First, the most important thing is to get a good name for my bot. For this, i invoked the power of memes, and named it JumpyDoggoBot, as zerglings are just heckin jumpy doggos doin Terran a big concern.
In my experience, a major part of beginning this is wrestling with the API. Since the BWMirror API is a Java wrapper for the C++ BWAPI, it’s not always perfect, and sometimes methods are not implemented correctly, and we need to work around that. This is not to diminish the all the good work the developers done on this, they did a tremendous job, but in software development, nothing is ever perfect. Also, i’d like to make this better, and develop the BWMirror itself, but at the moment, my C++ knowledge isn’t sufficient, and more importantly, i just don’t have the time.
Another thing to note, that there is a BWAPI4J project underway, to replace BWMirror. This isn’t terribly important for my purposes.
So i’ll do the next best thing, and document the bugs, the workarounds, and contact those responsible for this. Together, we will make a better future.
At the beginning of the article, i mentioned that my problem is build orders. To elaborate on this, first we have to define, what exactly a build order is. Here you can find an example. At first look, there is a lot to unpack. I’ll elaborate on these points, to better decompose the problem. Most of those points are implicit, and just generally understood, or intuitively done by humans. 2 Rax FE means “Two barracks fast expand”, but obviously no one has the time to type out all that.
- “Vs Zerg” – Yeah, some build orders are useful against specific races, and those only.
- Things like “11/18 – Barracks”. This means when you have 11 supply of the 18 total, you build a barracks. Not only buildings, but upgrades also can be mentioned here.
- Implicit: How you fill those supply, with workers or soldiers?
- No mention: Building placement. For now, let’s use the building placement used in the SSCAIT tutorial.
- Implicit: Expansion. Most maps have a natural expansion, “natural” in short, which is close by the main base, and has the same amount of resources, or close to.
What inspired this article is how do i represent these buildings/upgrades? For my thesis bot, i created a BuildOrder object, which had very static properties – if the supply reaches X, build thing. Meanwhile, i just built one or two types of units, so the supply eventually got filled up.
Let’s examine Problem 1. My build order was the aforementioned 2 Rax FE. This has worked reasonably well against Zerg (I only tested vs. the built-in AI, not other bots), and almost always got pwned by Protoss. How can i switch, and adapt? Sometimes back and forth, as my opponent will presumably do the same? (My) Short answer is graphs and triggers. The long answer is, let’s do everything else from the ground up, and then try that out. As of yet, i don’t know how long that will take, neither in development or blogging effort.
I managed to not write any code for this introduction so far. Let’s just keep it that way, and i’ll examine some very basic problems in the next article.