Starcraft AI blog

I enjoyed the game TyrProtoss vs Simplicity on Benzene. Simplicity is not ranked high, but it plays some good games.

My proposed daring/solid metric turned out to draw a surprising degree of attention. Well, I was going to try it out anyway, but now I have reason to report in detail. Today I did only the first step, finding the elo values.

I chose to rate the players relative to a fictional opponent that scored exactly 50%, giving the fictional player elo 0, because it was easy that way. The game is zero-sum, so that’s the average player of the tournament, in a sense. We only care about elo differences, so the base is arbitrary.

bot	%	elo
Stardust	93.22	455
PurpleWave	79.44	235
BananaBrain	69.61	144
Dragon	62.38	88
McRave	57.22	51
Microwave	54.47	31
Steamhammer	54	28
DaQin	50.14	1
ZZZKBot	39.89	-71
UAlbertaBot	31.14	-138
WillyT	29.44	-152
Ecgberht	24.28	-198
EggBot	4.72	-522

I calculated the table by hand, which seemed easier for a first cut—I simply printed a big elo table and read it backwards, from winning percentage to elo difference. If the solidity metric works out, I’ll have to automate it. It doesn’t seem hard (maybe invert the function by binary search). In fact, the only reason it was easier to do it by hand the first time is that I’ll have to do it by hand anyway to verify that my code is correct.

Next: I want to draw graphs for each player showing the expected and actual scores against each opponent. That will give a visual indication of how well the metric will work out. If it works well, I’ll choose a way to turn it into a number.

A win against a stronger player is an upset. A loss against a weaker player is an upset in the opposite direction; the weaker player upset you. Two players of the same strength may have different rates of upsets in their games: Maybe one often beats stronger players but loses to weaker ones, and the other has more consistent results and does not. It’s a difference in play style. I call the inconsistent, risk-taking player daring and the consistent, risk-avoiding player solid.

It should be possible to measure solidity from a tournament crosstable. But what is a mathematically correct way to do it? You don’t want to simply count upsets, because you expect to win a lot of games versus a player that is slightly better than you. You want to somehow take the severity of the upset into account. For example, a win rate that stands far from its expected value should count more. But what is the expected win rate if, say, one player scored 80% in the tournament and the other scored 50%?

Here’s one way. Finding expected win rates is what elo is for, so compute an elo rating for each player in the tournament. You could use a program like bayeselo to take all information into account, or you could simply use the tournament win rates to impute elo values, essentially running the elo function in reverse. The two methods will give slightly different answers, but not very different. Then you can use the elo function in the forward direction on the differences between elo values to find expected win rates for each pairing.

Then for each pairing you have an actual win rate from the tournament results, and a calculated expected win rate. By construction, the two are the same in an average sense—but not individually. All that is left is to turn these numbers into a metric of upset-proneness, or daring risk-seeking. I haven’t tried to work out the math of what the metric should be, but the outline is obvious. For each opponent, pick out the pairings that are upsets: Either higher-than-expected win rates against a stronger opponent, or lower-than-expected against a weaker opponent. You might ignore other pairings, on the theory that they are symmetrical anti-upsets, or you might try to refine your metric by assigning them upset values too (I think the results would be a little different but probably close). You want some difference function f(actualRate, expectedRate) that says how big the difference is; you might choose linear distance (subtract then take the absolute value). Then you want a combining function g() that accumulates the difference values into a final metric; if f is distance, then you might choose the arithmetic mean.

I’ve never seen a metric like this, but it seems like an easy idea. Has anyone seen it? Can you point it out?

Next: I want to try this for AIIDE 2020. If it works smoothly I may extend it to other past tournaments, to see whether bots retain a measurably consistent daring/solidity style over time.

Steamhammer played an excellent game versus Monster today. The game is kind of long and boring to watch, with repetitive action, but I’m pleased by the good play against stubborn defense. Steamhammer wasted some resources and missed some opportunities, but made no severe mistake at any point. It even expanded at a good time, which is depressingly rare in its ZvZs. Near the end, Steamhammer tried to put the cherry on top by ensnaring Monster’s mutalisks, but the mutas zoomed by too fast, the ensnare missed, and the queen was shot down. Oh well, dropping the cherry didn’t change the rest!

For a game that is not in the least excellent but is interesting for its mistakes, I like yesterday’s Steamhammer-Slater game. I watched the game live, and when Steamhammer bumbled the defense of its natural I steeled myself for a quick upset. But it was not so quick after all. The game is a showcase of ways to go wrong on both sides. Some of Steamhammer’s mistakes remain unresolved because my planned fixes are complicated and need to be implemented as projects.

The latency compensation bug is still making me scratch my head. The easiest way to work around it is to use the Micro module’s order tracking; Steamhammer already keeps track of what orders it has given to units, including larvas, so it doesn’t need to rely on BWAPI to keep it straight. I traced the backbone of the production code and added the minimal workaround, a two-line addition to the code that decides whether a unit should be added to the set of candidate producers. And... it didn’t work. In order to control where zerg units are made, to do things like make drones at bases that don’t have enough drones, there is a special-case low-level routine, and it ignores the set of candidate producers and does its own calculations from scratch—slightly complicated calculations that the candidates don’t make easier. I’m still thinking about the right fix. Maybe I can find a way to make it simple and powerful at the same time.

It is, by the way, a serious bug. In Steamhammer, the effect is to sometimes—at predictable times—drop a unit that was queued for production. Among other things, it turns 12 hatch openings into 11 hatch. I had noticed that Steamhammer was playing 11 hatch surprisingly often, but it does have a full suite of intentional 11 hatch openings, so I didn’t realize that it was due to a bug.

The annual SSCAIT is past the halfway point of the round robin phase, and it’s time to take stock. The numbers keep changing, but here’s a snapshot.

Stardust has slowly climbed to #1 after its weak start, with only 4 losses after 50 games, as compared to #2 Monster with 7 losses after 67 games. Stardust has strong chances to hold its #1 position, though it has played fewer games. Stardust’s worst upset was against #29 ICEbot, while Monster’s was against #47 Junkbot. #5 PurpleWave is unexpectedly low, below #4 BananaBrain; from games I’ve seen, I suspect it did not get its usual thorough preparation, or perhaps the prep was concentrated on top opponents so that it can succeed in the elimination phase. #6 Iron is doing better than I expected, and is ahead of #7 Hao Pan, though they are ranked close and the edge may not stick. #9 Xiao Yi is also higher than I expected.

#14 Skynet by Andrew Smith is the only classic unupdated bot to hang on in the top 16. Other classics #17 UAlbertaBot by Dave Churchill and #18 XIMP by Tomas Vajda are just outside, and there is a gap with #16 Proxy so they may remain outside at the end of the round robin. #19 McRaveZ I had hoped to do better; its muta micro is good but its muta decision making (which target to seek, when to attack and when to run away) is not nearly as good as Monster’s. #20 Microwave has been slowly upping its win rate and has an outside chance of making it into the top 16 by the end; I imagine its learning is figuring out how to compensate for the bugs in this version.

Steamhammer is at #13 at the moment after a few losses, but I’m still forecasting that its most likely finish is #9 or #10. It has played more of its tough games than its easy games.

Some bots get special icons on the unofficial crosstable by Lines Prower. It’s a cute touch, though for me it makes the table harder to read. The funniest is Krasi0P’s linux penguin for 2 wins and Windows logo for 2 losses. I don’t understand McRaveZ’s icons. A salt shaker for losses, OK, but a secret agent for wins? I may be missing some background. PurpleWave gets a purple heart for wins. Maybe Lines Prower doesn’t know what a purple heart means to Americans?

The just played Simplicity vs BananaBrain is a fine game by Simplicity. The early defense against zealots was especially well done, and Simplicity’s tech and attack decisions were good. Recommended.

In the meantime, I’ve hit a bug that’s slowing me down. I found a reproducible case where production fails because it tries to use the same larva to produce two drones. It looks like slippage in BWAPI’s latency compensation: The production system picks a larva to produce a drone. Ask the type during the same frame after giving the morph order, and you get egg; that is latency comp at work. Ask again a couple frames later, and the egg has turned back into a larva; the production system picks it a second time, and the second morph can only fail. I think it should be easy to work around, but can it be fixed? Latency compensation is not expected to be perfect.

It makes me wonder what other slippages may be hiding under the rug.