Starcraft AI blog

At its most general, a learning system consists of a data structure, a learning algorithm to update the data structure with new data, and a retrieval algorithm to answer questions from the learned data structure. You could say it is a specialized kind of memory, with a data store and ways to get information in and out. The information you get out is not the same as what you put in, and that is part of what makes it useful. Or you could say that ordinary computer memory is a learning system with no loss and no generalization.

One of my goals for Steamhammer’s opponent model is to learn from a single game. There is a well-known class of learning systems which makes it easy, because their data store is nothing more than a record of the original input data, called instance-based learning or memory-based learning. This simplest example is the k-nearest neighbors algorithm family: Your data is a set of points (x, y) , input x gives output y (where x and y might be, say, vectors). To learn from a new data point, simply store it along with the others. To answer questions of the form “what’s the output for input x?” you find a given number, k, of x‘s nearest neighbors according to some distance measure, and average their outputs (using whatever kind of average may be appropriate for your problem). A fancier class of systems that can draw complex conclusions from a single example goes under the name case-based reasoning, where the data store is a database of structured “cases”, or examples.

Anyway, I thought I should use a method in the nearest neighbor family. It’s the simplest way to meet my goals.

What should my data points look like? Well, what information does Steamhammer use to make strategy decisions? It looks at the enemy’s current unit mix. I want to be able to predict the enemy’s unit mix at a given time: “Oh no, those zerglings are early, it’s a rush!” or “this enemy switches to goliaths and hardly any tanks, I should build up hydralisks next.” Both are nothing more than unit mix @ time.

My data points are games, boiled down to sequences of unit mixes. In the first implementation, Steamhammer takes a snapshot of the unit mixes of both sides every 30 seconds, “this many drones, that many zerglings, ....” I also threw in some supplementary information: The map, the opening chosen, and as shortcuts for opening selection the times at which the enemy got various things, such as the first combat units, the first flyers, the first detection, and so on. And it simply appends all the data to a file named after that opponent.

To answer the question “what will the enemy’s unit mix be at time t?” the first implementation finds the nearest neighbor. It looks through the game records to find the best match game, the past game against the same opponent which is most like the current game, according to a similarity measure which adds up differences in unit mixes over time, up to the current time in the current game. (So the best match will change at most once every 30 seconds.) Having found the best match, it looks up the recorded enemy unit mix in the best match game record which is closest to time t and calls that the prediction. It’s dead simple.

That was my motivation. In fact, the game records have endless uses beyond predicting the enemy unit mix. For example, to figure out whether an opening is safe to play against this opponent, run the timings of the opening against the timings of the game records. If the opening always gets defenders in time, then the enemy will not smash you with a rush (or at least it will only be a surprise once). Or if you notice that the enemy never gets detection, then go lurkers and get an easy win. And so on.

Einstein, hand me the simplicity!

You can see why I thought the method was obvious. With clear goals and the right background knowledge, it is obvious. And you can see why I thought I could get it working within a few weeks; there is nothing complicated here. If I were a better coder, I would have succeeded.

Of course, it may turn out that the simplest option is not good enough. For the first cut I wanted to take the easiest way. If some part turns out to work poorly, I have improvements up my sleeve. The possible improvements are as endless as the possible uses.

• The recorded unit mixes include buildings. Buildings are especially important for predicting what the opponent is up to, but my first cut similarity measure does not understand that. It treats the difference between 1 barracks or 2 the same as it treats the difference between 1 marine or 2, and that is obviously not ideal.
• For some purposes, it may be better to record the total units ever made (or ever seen, if the enemy’s) instead of the current unit mix, because the current mix depends on the outcome of battles as well as the strategy followed.
• If the best match is not close at all, maybe it should be ignored.
• If there are a number of good matches, maybe they should be averaged together.
• Surely the current unit mix should have a role in predicting the next unit mix. In the first cut, it is ignored.

The bottom line is that my first implementation may or may not work adequately. But I’m confident it can be improved until it does work.