archive by month
Skip to content

Steamhammer’s opponent model

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.

Trackbacks

No Trackbacks

Comments

Joseph Huang on :

This looks decent, but replays would give more accurate information. Unfortunately tournaments don't give you access to them in the middle.

Jay Scott on :

Agreed. Ability to check the replay after the game would be great. I am not holding my breath. :-) I expect I’ll have to make some changes to improve scouting.

MicroDK on :

To me it does not seem simple to store and read back all those data. Also, are you going to store data for all games vs an opponent?

LetaBot on :

I do wonder if this will take Proxy buildings into account. TvZ for example the Terran can build a factory and float it into the zerg main.

Jay Scott on :

It’s an idea. Encode location in one way or another, maybe main/forward/center/proxy, and store that too.

krasi0 on :

This is similar to what I have experimented with in the past. In fact, I also used k nearest neighbours. The experiment didn't turn out very successful so I gave up after many hours wasted in tweaking the input and output vectors. Let's see if you make it work properly against opponents like tscmoo Zerg or Steamhammer's huge arsenal of random ZvX openings.

Jay Scott on :

Aha, it’s not an all-new idea after all! I definitely expect it to work poorly against the most unpredictable opponents—thinking ahead to when I would do this is one of the reasons I have kept adding new openings to Steamhammer. How well the model works against a given opponent is also information that can be kept. It should be possible to make the asymptotic loss against the worst-case opponent go to zero.

Add Comment

E-Mail addresses will not be displayed and will only be used for E-Mail notifications.

To prevent automated Bots from commentspamming, please enter the string you see in the image below in the appropriate input box. Your comment will only be submitted if the strings match. Please ensure that your browser supports and accepts cookies, or your comment cannot be verified correctly.
CAPTCHA

Form options

Submitted comments will be subject to moderation before being displayed.