Starcraft AI blog

Regardless of any other adaptation skills you may have, if you can predict your enemy’s opening build, you can better counter it. But it’s not simple. Steamhammer tries to distinguish between opponents that play a fixed build, and those that vary their openings. For those that vary their openings, there is much more: Some choose randomly. Some like to repeat the opening that won the last game, switching only on loss. Some stick with an opening that wins more than a given percentage. Some try openings systematically, “A didn’t work, B is next.” Some choose randomly with some probability distribution over the more successful choices. Sometimes openings are treated as black boxes distinguished only by their names, sometimes as strategies which are understood to counter other strategies (Steamhammer does both at different times).

I am wondering whether it makes sense to write a rock-paper-scissors analyzer that tries to tease out exploitable patterns in the opponent’s behavior (there are established techniques), and combine it with a game solver to make better initial opening choices. On the one hand, many bots have exploitable patterns that I know about. If an RPS analyzer can find the patterns too, Steamhammer might seem to gain the mysterious “star sense” to always play the right thing for no visible reason. On the other hand, it’s relatively easy to reduce your exploitability to a low level—use randomness wisely. Also, as Steamhammer gains skills to adapt its strategy during the game, the initial opening choices make less difference. The gain might be little. And by trying to exploit patterns, Steamhammer could itself become more exploitable; it might backfire.

The parts of the system would be:

1. Classify the enemy build. Steamhammer already does this, though it needs improvement.

2. Statistically analyze the sequence of (win/loss, my opening, your opening) under the assumption that the opponent is trying to counter what we’re doing. Knowing what-counters-what may factor in. The output should be a probability distribution over opening classes, “what are they likely to do?”

3. Knowing what-counters-what definitely factors in here: Solve the game. We start with a prior probability of winning for each of our openings against each opening class the opponent might play, and thanks to Bayes we can update it as we learn about the opponent. That gives us a game matrix with uncertainties in the payoffs. (Since Steamhammer knows a huge number of opening builds, making the game matrix too big to fill in, I would classify Steamhammer’s openings too so that the output only decides which class of opening to play.) Without an RPS analyzer, we can solve the game (I expect I would use a Monte Carlo method to handle the uncertainties) and play not far from a Nash equilibrium (i.e., almost perfectly assuming unexploitable play from the opponent). If an RPS analyzer can make a good estimate of the opponent’s plans, in the best case we can do better: We can exploit the opponent’s deviation from the Nash equilibrium to win more than if we played to a Nash equilibrium ourselves.

It’s unclear to me whether either the RPS analyzer or the game solver is worth the effort. Does anybody have an opinion? Perhaps some bot I haven’t looked at has similar ideas?