Starcraft AI blog

I thought this release of Steamhammer would take only a few days, but I had “some” scope creep. It is no longer a small release to restore terran and protoss to their shabby glory, but a full release with improvements and a range of fixes. Instead of version 2.2.1, I’ve renamed it version 2.3.

Today I added a feature which changes the current “main base” at times when it makes sense. New buildings go into the main base by preference. Formerly there was a feature that changed the main base at random times, in order to spread out buildings and alleviate the protoss construction bug. It led to a lot of poor decisions.

Now the building placer attempts to maintain at least one pylon near each nexus, so it can build there if necessary. It keeps track of how often building placement fails at each base—how many times the building ends up not placed because no available space had pylon power, or placed outside the base because there was no room inside. When a failure happens at one base, it looks around to see if there is another base which has fewer placement failures, and if so, switches to that as the main base. I hope that switching when necessary will work better than switching randomly.

I just finished a series of tests on the map Transistor, which has small starting bases with room for few buildings. Steamhammer protoss usually overflows into the natural before it puts a nexus there. I got a modest number of slow frames when building placement failed, but nothing disastrously bad. It’s getting close to good enough for now.

I have one more building placement feature to add for protoss, which I expect will make it actually good enough for now. Then I need to review the last few protoss openings. It shouldn’t take more than a few days, so based on recent experience, come back in a couple months.

After that will be Steamhammer 3.0, unless I change my plans again. Release schedule undecided. I’m planning to work on production goals next, a key part of turning abstract strategies into concrete build orders.

I wasn’t planning to implement the larva trick now, because it’s not important. But after testing it for yesterday’s post and finding it easy, the extra work to complete the feature took only minutes, so I went ahead.

Steamhammer determines “the direction to the minerals” from a base’s hatchery by averaging together the offsets of the mineral patches from the center of the hatchery, giving the location of the average mineral patch. (There was already code to do this for another reason, I only factored it out, and it’s barely a few lines anyway.) Once every 20 frames, starting on frame 1 (not 0), it sends Stop indiscriminately to every larva at a base hatchery whose minerals are to the left. It desists after an early game time limit, or when the spawning pool finishes; almost all benefit should be in the early game, and zerglings may be slowed down by starting at the edge of the mineral line.

There are weaknesses to the implementation. When morphing a drone, Steamhammer does not select the larva closest to the minerals, so it often chooses a larva that is still in the process of moving left. Judging by eye, I think this weakness eliminates a third to half of the potential benefit. It’s possible that the indiscriminate Stop commands could sometimes prevent a drone from morphing on time; I didn’t check, but if so it should be rare. Probably a little extra benefit could be captured by doing it all game long, but more smarts would be needed.

The benefit is tiny, as I mentioned yesterday. I tested by playing Steamhammer versus itself with the same opening on Heartbreak Ridge, so that the left base uses the larva trick while the right base does not. In Steamhammer’s implementation, the edge gained by moving drones to the left, so that they begin to mine minerals earlier, is smaller than the natural variation between runs caused by the game’s random differences in timing and position. The technique is worth something, but so little that it was hardly worth implementing, even though it was easy.

An ideal implementation would be better. If you know what units you want to produce in the near future, and what their jobs will be, you can select the larvas of left-facing hatcheries that will become local mining drones and use the larva trick only on them, and do it in time to get them moved into position before you morph them. But that is no longer a simple job, and the benefit will still be small.

The other major use of the larva trick is to control egg blockades. If you have a wall consisting of a hatchery on the right and terrain or another building on the left, and zealots come knocking, you can move a larva to the left of the hatchery and morph it into an egg that blocks the gap. See the game Shark vs Reach (2008), explained on this TeamLiquid thread (it’s an example game on Liquipedia's larva trick article). I’m also fond of a famous 2x2 game from 2006—it may be from before the larva trick was discovered, but the video segment is short and worth seeing.

A larva follows a predictable path after it is tricked. If it is next to the upper half of the hatchery, it takes a route around the top; if in the lower half, around the bottom. The larva moves smoothly, so you can predict where it will be when. With good timing, you can morph an egg where you want, for example to push a unit away from your hatchery to gain time.

All 3 races have tricks they can sometimes do, depending on the starting position, to make workers spawn a little closer to the minerals they will mine. It provides a very small macro boost, starting early in the game when it matters most. I doubt that any of these tricks will make much difference in bot play; mineral locking gives a much larger edge. I haven’t noticed any bot implementing them. (Do you know of one?) On the other hand, they’re not hard to implement, and might possibly help the strongest bots.

terran

A fresh unit, just produced, appears to the bottom left of the building that produced it, like this new-made SCV:

If the minerals are on the left, cool. But in this case, the minerals are on the right, and the SCV starts far away. To get the SCV to spawn closer to the minerals, block the space on the left with your first supply depot. The left edge of the depot (3 tiles wide) is aligned with the left of the command center (4 tiles wide).

Then the SCV appears below the command center and to the right of the supply depot. You use your first supply depot because you want to start gaining the macro advantage (small as it is) right away; it matters most at the start of the game. Starcraft has consistent rules for where new units appear: As far toward the bottom and left of the producing building as possible. If you start with a barracks first, you can align the barracks (4 tiles wide, the same as the command center) exactly underneath, so that the SCV appears even closer to the minerals.

If SCVs are returning minerals at the time and place where the new SCV would spawn, blocking the spot, then the SCV may appear farther up the right side. That should not bother a bot in the least.

Pro terrans do this trick with their first depot. At their level of play, they think it’s worth it.

By the way, exit blocking tricks like this have game uses outside of macro. For example, if zerglings are attacking a barracks and the barracks is producing a marine, then zerg controls where the marine will spawn. Lings at the bottom left of the barracks can pull back a little so the marine spawns there, already surrounded. Pros do this too.

protoss

Protoss can do essentially the same trick with their first gateway, if the minerals are to the right of the nexus.

Pros do not use this trick, as far as I’ve seen. The gateway should start only a little later than the terran supply depot, so I think the trick should still bring a tiny macro advantage. I suppose that pros find other factors more important for gateway placement.

zerg

Zerg produces drones from larvas, and exit blocking tricks don’t apply. Zerg has a completely different trick, apparently a weird bug in Starcraft, that is useful if the minerals are to the left of the hatchery: The larva trick. Except for this trick, larvas are not controllable. When performed by a human, select any larvas you want to move to the left together with an overlord, and hit stop. You can use a controllable unit other than an overlord if you don’t mind it stopping. The selected larvas will slide to the left side of the hatchery and stay there. And the overlord stopped, so you probably want to send it on its way. When a new larva appears, you have to repeat the trick to make it move—no trouble for a bot.

When I tested it in Steamhammer, I found that the overlord was not necessary. Apparently the overlord is only included to bypass UI limitations that BWAPI does not emulate. This simple test code, which runs only once on frame 0, worked for me.

  if (BWAPI::Broodwar->getFrameCount() == 0 &&
      BWAPI::Broodwar->self()->getRace() == BWAPI::Races::Zerg)
  {
      Bases::Instance().myMainBase()->getDepot()->getLarva().stop();
  }

Bases::Instance().myMainBase()->getDepot() returns the main base hatchery. BWAPI provides getLarva() which returns its set of larvas.

The larva trick also has game uses outside of early macro.

Today I fixed what I think is the last serious bug that I introduced in version 2.0 last September. It was the one that causes innocent lurkers which are trying to walk across the map to move stutteringly or to vibrate in place. The bug turned out to also affect medics and defilers, though in a minor way that’s not easy to see.

How can it take half a year to fix serious bugs? I can list several reasons. I think that is a bad sign in itself.

1. Some of the bugs, including this lurker bug, were introduced in 2.0 but did not have visible bad effects until later—in this case, when I updated the micro system and taught it a stricter attitude toward executing commands. Experience says that Steamhammer has many invisible bugs that rarely bite or that have hard-to-see effects or that are complex and hard to trace back to a cause, but still need to be fixed. In any case, bugs that visibly hurt play get priority.

2. Some parts of Steamhammer inherited a UAlbertaBot habit that close enough is close enough, if some expected prerequisite is not there after all... eh, ignore this part of the job. As time goes on I’ve been making Steamhammer more strict about checking its arguments and preconditions, and complaining if anything looks wrong. But today I ran a test: How often does Steamhammer try to issue the same unit different commands during the same frame? That should only happen by mistake, and yet the UAlbertaBot code ignores it. The answer was that it happens many times per game—not often enough to break micro regularly, but there are sure to be bad effects. At some point I have to find time to chase down the causes and fix them, and then add an assertion so it can’t happen again without drawing attention. Bugs must be made visible!

3. Version 2.0 was a major reworking of squad-level tactics. Of course a big ship needs a long shakedown cruise. It didn’t help that I was hurrying to prepare for AIIDE.

4. The squad data structure and code structure are not designed to support the more complicated behaviors that I implemented in 2.0. I added a bunch of awkward bug-prone special cases. In Software Development Utopia, I would have redesigned the Squad class first, and then had a much easier time with the squad behavior. That would be more efficient in the long run, but it wold also stunt my short-term progress. Sometimes we prefer to accrue technical debt.

And the lesson is... um... take a systems view? That sounds good.

There are still a bunch of unfixed weaknesses (as opposed to outright bugs) that were introduced in version 2.0.... And yet the advances in 2.0 were necessary to keep progress going.

Well. So. I sort of got carried away and refactored the building placer. I guess it is a side effect of my instinct to improve any code that I touch. I fixed 3 different bugs. I squeezed out some redundant calculations, so the basic operation “can this building go here?” is faster. And I added a little mechanism to make it easy to throw in different special case building placement algorithms. I see the work as preparation for the more general placement planner that I’ll eventually write.

I think the 3 bugs were all inherited from UAlbertaBot. One was an off-by-one error that could give bad results for the right edge and bottom edge of the map. Another was a different off-by-one error that, half the time, caused the minimum space between buildings to be 1 tile more than configured. Fixing that makes building placement more compact and helps all races. The third bug was so rare that I have never seen it, but theoretically a macro hatchery might be bumped out of one base because it did not fit, and be placed in a neighboring base in a way that blocked the expansion hatchery location. Now I’ll never see it.

I wrote special case building placement for terran. Supply depots, academies, and armories are all 3x2 tiles and can be tightly packed. These buildings are placed in a single row along the edges of the map, as long as there is room. On most competition maps, the main bases are on the edge, so the special case kicks in. In between the slightly more compact building placement because of the bug fix, and the much more compact placement of early supply depots, Steamhammer’s terran gets farther into the game before it starts to sprawl buildings all over the map like Los Angeles. There’s no shortage of room for improvement (puns always intended), but I’m calling it good enough for now.

Now I want to figure out something equally effective... and equally simple for protoss.

Many bots have been in this situation: You’re playing against Tscmoo—and you’ve broken into its base! You’re winning! Your units zero in on the mining workers, which flee... and they’re good at running away. Sometimes they lead the attackers on a goose chase until rescue arrives, and Tscmoo survives to win after all. I’ve seen it happen. Iron is also particularly good at leading goose chases. How do you get your bot to avoid wasting time and concentrate on what’s important?

There are a lot of ways. You can give buildings priority and chase nothing that you can’t immediately hit. You can refuse to chase any unit that is fast enough to escape. You can chase only a certain distance before you turn back. You can attack only units that are approaching, not those that are out of firing range and fleeing (watch out for kiting). You can chase only units that are inside the perimeter of your formation, so that they are partly surrounded and have to dodge well to escape, and then they leave the perimeter and you stop.

I want to suggest another way: Don’t attack, defend an area. Draw a box or a circle around the area you want to attack, and defend it from enemies. Add a margin for hysteresis, so you don’t vacillate if an enemy moves into and out of the area. If you are trying to stop mining, defend an area around the enemy’s resources, including the resource depot. Your squad’s goal is to clear the area of all enemy units and buildings—to defend this part of the enemy base against enemies. If the workers run away, let them; you’ll destroy the resource depot that much sooner. If you’re trying to camp the enemy production (assuming it’s grouped together somewhat), the same idea works by defending a different area. (If your goal is to destroy key tech, then prioritizing those buildings is probably what you want instead.) You’re really attacking, not defending, so once you’ve cleared the defended area, move or enlarge the box and keep up the fight.

Unlike yesterday’s trick strategy that is useful only in special cases, the “defend a box” skill is good in many situations. You may already have the skill and use it for defense; the idea is that “defense” and “offense” are a matter of point of view. To defend overlords from corsairs with hydras, draw a box for the hydras to defend and keep your overlords there. Similarly to defend a mineral line against, say, wraith harass. For an offensive example, take a slow tank push. You can implement it by telling the tanks to defend an area, and gradually moving the area forward. Tanks in the rear will unsiege as the defended area goes out of range, move to the front, and siege again, and that’s a push. The same thing works for a lurker push.

Some bots are so single-minded that they never make air defense of any kind, no hydralisks or spore colonies but only zerglings, no cannons or dragoons but only zealots. Black Crow is a zerg example, and protoss Carsten Nielsen has the same mindset. Theoretically a terran might make only vultures and tanks, though I can’t think of one that doesn’t also make marines or turrets.

Strong bots can cope, of course. But for a lower ranked bot, such an aggressive enemy strategy can be tough to survive. It calls for solid skills that take time to develop. If you prefer a different route, then instead of countering with skill, it’s possible to counter with strategy. Here is a trick counter-strategy for terran:

1. Make a wraith. Well, make as many as you can afford, but 1 should be enough to win. The enemy cannot shoot up, so your wraith is immortal.

2. Lift off any building. Your floating building is immortal, so you cannot lose by having all your buildings destroyed. If you like, you can wait until the building comes under attack.

3. It is still possible to lose on points if you do not finish off the enemy in time, so there is one more step: Use your wraith effectively. Kill overlords and workers to prevent the opponent from constructing buildings faster than you can destroy them. Then slowly take out buildings one at a time. Don’t waste a moment shooting at zerglings or zealots. You don’t need to defend yourself, because you are immortal.

The plan does not automatically work against fast rushes, because you may not get far enough to make a wraith. Possible advanced skill: If you finish the starport but can’t finish a wraith in time, you may be able to lift off the starport and float it to a location that the enemy can’t reach or won’t easily find. And of course you have to decide which opponents to try it against; that might be the hardest part for a low-level bot (and it’s not hard).

Protoss or zerg can play a similar plan on many maps, though it is slower and requires more skills, including analysis of the map. For protoss, make a stargate and a scout as your immortal air unit. To avoid losing, get a robotics facility and shuttle, carry a probe to some place which is buildable and inaccessible by ground—an island or plateau—and make a pylon there. For zerg, you can slow drop a drone on an island base if one is available, and make an extractor, or save up money if the map has an inaccessible space big enough for a hatchery.

One of my ambitions is for Steamhammer to eventually invent this strategy on its own. Steamhammer doesn’t need to be able to reason out that the plan cannot lose; it is enough to recognize the enemy’s habits and come up with logical counters. Step 2 is, “uh oh, the command center is under attack by zerglings, I have to lift it.” Step 1 is not much harder, “here are the units this opponent has made in the past, and based on this history, I could go air.” It doesn’t have to notice that the enemy never gets anti-air, only that going air is a good choice. Step 3 seems to be the hard part.

Revising building placement for terran and protoss is taking longer than I expected. My simple plan was so simple that it was wrong (listen to Einstein!), and I had to throw out some bad work. I’ve decided that’s my last mistake; from here on out, I will be right every time. Even though I’m right now, I still need to put in the work.

I fixed the bug that causes dark templar to move erratically. It turned out that hiding behind it (how do you hide behind something invisible?) was a second bug that affects dark templar and makes DT drops useless (after fixing the bug that caused the transport to fail to load). Haven’t diagnosed the second bug yet.

Working through the openings helped me catch the major bugs, some of which have been around since September. The upside is that terran and protoss will be that much better.

I noticed that Hao Pan’s description says it uses COEP or Continual Online Evolutionary Planning to adapt its build order during the game. And Hao Pan is a successful bot. So I thought I’d write it up.

The original paper is from 2017, Continual Online Evolutionary Planning for In-Game Build Order Adaptation in StarCraft by Niels Justesen and Sebastian Risi. There is a corresponding github repo with source. Long-time followers may remember Niels Justesen the bot. Niels Justesen has other publications; if you like this paper, I suggest Playing Multi-Action Adversarial Games: Online Evolution vs. Tree Search as a followup.

A good implementation is not simple, but the basic idea is easy. You have a set of build order plans, which you create and update in the evolutionary algorithm style. And you have a way to measure how good a plan is; in evolutionary algorithm terminology, its fitness. When you need to make a build order decision, you select the current best plan and follow it.

OK, details. In this paper, a build order plan is simply a build order, a list of stuff to build (or research) in order. In principle, it can be any length. You start with a population of different build orders, which you can generate randomly if you don’t have any better ideas. You evaluate the fitness of each one. Probably on the first try none of them will be particularly fit, so you need to make more plans. You create new builds by treating each one as if it were a stretch of DNA, and introducing different kinds of recombination and mutation (traditionally, a lot of recombination and a little mutation). The paper explains the authors’ choices. And of course evaluate the fitness of the new child builds. To keep the population size down, you delete less fit builds.

In concept, the evolution process runs continuously, and you query it for the best known choice when you need to make a decision. The authors actually implemented a client-server architecture, with a build order server. You could run it in a different thread, or do evolution on demand, or whatever; it should all work. When you start to carry out a build, you have to update the population to reflect that: This build says make 4 probes, I made 1 probe, there are 3 left. And the fitness measure needs to know about the game state so it can tell how good a build is.

So how does that fitness measure work? There are 2 parts, a forward model that predicts what happens when you follow a build order, and the fitness itself which measures how good the result is. You feed the forward model with information about the game state; the authors use mainly unit counts for both sides. In the paper, the forward model ignores builds that are illegal (make a corsair with no stargate), because the builds will have all kinds of random stuff in them. The forward model simply simulates what units you end up with when.

The fitness itself is based on a model of what counters what. You know what enemy units you’ve seen, and the forward model tells you what units you will have yourself. The fitness measure knows that vultures beat zealots and lose to dragoons, so in the face of vultures it sees lower fitness in a build that keeps making zealots and higher fitness in a build with more dragoons.

The build order being evaluated for fitness may be long, and you don’t want to measure fitness only at the end. You might lose before then! So they measure momentary fitness repeatedly throughout the build, and combine the local fitness values into a total fitness value, giving more weight to local fitness values that are early in the build. You’re pretty sure what’s next, not so sure about what happens later.

There is a video showing a game as protoss versus the built-in AI. Production decisions are made by COEP, the micro and other behavior is UAlbertaBot. Beating the built-in AI is not impressive, but what’s worse is that COEP showed some strange behavior. For example, COEP chose to research air attack for no reason; it never made a stargate. Even if it was planning at one time to go carriers, it made no sense to research air attack that early. Possibly there was not enough computation time to weed out all bad decisions.

A weakness of the described version of COEP is that it only counts the enemies you’ve seen. It doesn’t try to predict the future enemy unit mix, or to weigh the risk to you of different enemy choices. But that’s a weakness of the implementation, not of the basic algorithm. Features like that can be implemented.

COEP is extremely general. You need a way to represent plans, an evolutionary way to modify them, and a way to evaluate them for fitness. I think that can describe any problem (some more naturally than others). You could use COEP for tactical decisions and micro decisions too, or for deciding what to have for lunch.

You pay for the generality with more computation. You end up inventing and evaluating many plans that you will never follow, including plans that are unrealistic or outright invalid. You can try directed evolution ideas to reduce the extra CPU time, but generality will come with a cost.

I expect that deep learning, if you can apply it, will work better than COEP. The disadvantage of deep learning is that it burns data by the supertanker load. With COEP you have to implement a bunch of stuff yourself instead of letting the computer figure it out, but you don’t need the mass of data, so it may be more accessible for a hobbyist. Of course, you can combine the methods: Follow the COEP architecture and use deep learning to create and modify the alternative plans, or to evaluate them, or both. Since deep learning is then solving an easier problem, training should be easier.

I’m thinking about unit tracking, and the many many issues it is connected with.

Steamhammer keeps a UnitData data structure to remember enemy units when they are out of sight. It’s only modestly modified from the one inherited from UAlbertaBot. The information manager keeps the information updated for both enemy and friendly units. But should it keep data on friendly units? On the one hand, it might be convenient to have a fixed format for all uses. And Steamhammer does use UnitData for friendly units in certain cases. On the other, it’s duplicating information that is already available directly through BWAPI. What’s the right design?

Many bots place a wrapper around BWAPI::Unit to keep their extra information. It seems like a good design, but I’ve been reluctant to switch to it, partly because there was no need for the extra work, and partly because I don’t understand all the ramifications. Now I’m thinking of doing the work anyway, and when do I ever understand all the ramifications? Well, I don’t need to decide yet.

Then there is the issue of inferred information. If I see a vulture, I know there is a factory, even if I’ve never seen the factory. It’s a known enemy building with almost no other information available; its location might be anywhere that I haven’t seen in the time it takes to build a factory and a vulture. If I see a tank, I know there is a factory with addon. If I see a dark templar, or if I see fast zealots, I know there is a citadel of Adun. I want Steamhammer to be able to draw all these inferences. Even with the current plan recognizer, it would make the recognition rules simpler. In the future, with a more powerful enemy strategy predictor, it will be valuable. I haven’t decided how to store the information. It could be fitted into a unit wrapper.

More inferences: If I see a spider mine, I know there’s a vulture and a machine shop. If I see a broodling, or a parasited neutral unit, I know there’s a queen. If I see something of the enemy’s on an island, or notice that the blocking minerals on an island have been mined out, I know there is transport. There may be an exception for units which were accidentally pushed through unwalkable ground, but that should be exceedingly rare. Also, some cases have an exception for mind control. If I dropped a worker on an island on Python, and it wandered near the edge, it could be mind controlled from a neighboring base, and the enemy could mine out the minerals and take the base without transport.

The idea of inferences with exceptions brings up the issue of estimates and uncertain inferences. As part of understanding the enemy strategy, you want to estimate the enemy’s economy—what count of resources mined so far, what rate of current mining? And the enemy’s production capacity—how many barracks, how many factories, how many starports? Sometimes, especially early in the game, you can get an accurate estimate by seeing the enemy’s army size and comparing it with what is possible. I saw when the first barracks was under construction, and by now it could have trained x marines, but I see x+n marines, so there are 2 barracks or more. More complex estimates are possible, based on income limits. On top of that, you can combine technical estimates made using the rules of the game with learned data (here’s what this enemy has done in the past). Fancy estimates like this do not fit into a simple unit tracking framework, but they interact with it; you have to take into account the intersection.

I’m not off the topic of unit tracking yet. When you get to the level of inferring the enemy’s plans based on all available information, there is one more input you want: A model of what the enemy knows about you. You can’t be sure what the enemy has seen, because the enemy may see you without being spotted in turn. There could be an overlord over that cliff watching, or the enemy units may have a longer sight range (for example, a probe has a longer sight range than an SCV or drone, thanks to protoss high tech). But when the early game enemy worker scout is cruising around your base, there is no problem (beyond technical details of visibility) keeping a unit tracking record of what stuff of yours it saw when. Top bots use their scouting data to get ready for what you are planning, and if you know what they know and can guess what they are getting ready for, you can lay better plans yourself (or try a trick like placing a hydra den in the main and a spire in a far corner of the natural).

These things will matter as I make progress on Steamhammer’s strategy adaptation, so I should start getting my ideas in order now.

I’ve just finished reading Tom Peeters’ master’s thesis about zerg ForceBot, called “Evaluating a Cognitive Agent-Orientated Approach for the creation of Artificial Intelligence in StarCraft”. ForceBot was written using the GOAL agent-oriented logic programming system (itself written in Prolog), and the StarCraft-GOAL Environment Connector (or just connector) that ties GOAL to Starcraft.

For me the interesting part of the thesis is the story of the development of ForceBot, which is divided into episodes or “milestones” for each tournament that the bot participated in. At the beginning of the story, Tom Peeters is fixing basic bugs like “the drone died, so the building was not constructed.” By the end, he was adjusting complex strategic reactions. Those of us who followed ForceBot’s career on SSCAIT may remember that it started out quite weak, and steadily progressed until it became a solid mid-tier bot. It was interesting to get a glimpse into ForceBot’s design and Starcraft knowledge.

ForceBot started with the most straightforward agent architecture: Each unit and building was a GOAL agent, and made its own decisions. To me, with the advantage of already having a well-developed view of how Starcraft bots can and should work, that seems obviously not the right approach. It’s too low-level; you want some form of abstraction, so that the bot can follow a coherent strategy and units can cooperate with each other without each agent having to understand the situation around them from scratch. I think a more natural approach is a hierarchy of agents, or at least a network with higher-level agents so that the unit agents can share a view of the world. And in fact ForceBot evolved in that direction, with higher-level “managers” taking over some of the work of the unit and building agents, and doing a better job because they had a more comprehensive view of the game situation. There are a lot of ways to do it, though, and any one bot can only explore a small part of the design space.

I was struck with how much of the development consisted of fighting with the GOAL system and the connector. Many updates were made to the connector, and the author struggled with architectural limitations and performance issues in GOAL. The main purpose of the project was to evaluate GOAL, so in a sense that’s what you want! But in my eyes, the result of the evaluation was that GOAL was not yet mature enough for this advanced project. There were too many stumbling blocks, and the bot was forced into design compromises that harmed its performance.

I approve of GOAL, though. It’s important to experiment with different software design philosophies, and agent architectures are intuitively appealing. With time and effort, good philosophies can be turned into good software tools, and it takes experience to make progress.

BWAPI 4.4.0 (release page) was released today (in my time zone). It fixes the known crashes of the recent version 4.3.0 and several other items, and extends getBuildUnit() to work in both directions.

Two fixes can affect how bots play. One is a correction of unit->getApproxDistance(), though it looks as though any error in the distance was very small. Still, perfect is better than good enough. The other is a correction to the buildability of map tiles: Fewer tiles are considered buildable. The note says it affects “some doodads” which cause a tile to be unbuildable; formerly, BWAPI thought you could build on them. I would be interested to know which map tilesets this affects—only certain tilesets, or maybe all of them but the doodads affected are relatively rare?

I’m sure I’m not the only author who will be waiting to see if this release is solid and is supported by tournaments (I expect it will be).

I have finally finished adjusting the terran openings, and I’m working on protoss. Initial signs are that protoss will be easier, but we’ll see. After that I need to make some changes to building placement.

It’s boring to work on openings all the time, so I diverted myself with a few other refinements. The biggest is another round of improvements to the tank siege/unsiege logic. The last round was a tiny tweak that made a difference only in rare cases. Tanks continued to fall into ludicrous siege-unsiege loops, often without firing a shot. This round I was more thorough. The decision to siege analyzes the situation to avoid common mistakes. The decision to unsiege is more strict; part of that I achieved as a side effect of improving tank targeting. The results are easy to see, and tank play is more consequent. Tank micro is still far from good, but the siege/unsiege logic is no longer the weakest link. Now the bigger problems are attack/retreat decisions, positioning, and the issue that Steamhammer has no understanding whatever of visibility.

In between the fixed openings—some are now stronger than they ever were before—and the fixed tank play, Steamhammer’s terran is looking up. I don’t think it’s hugely improved, because too many other problems drag it down, but to me the difference is unmissable.

I was intending the upcoming version 2.2.1 to be nearly the same as 2.2, with only the minimal updates to play on SSCAIT, but it is turning into something more.

A new version of Iron has been uploaded. It’s definitely different; the .dll file is about 25K larger, which makes it about 1.6% larger than the previous version. That’s a significant amount of code. But what is new? I played a few games and compared the binaries briefly, and so far I haven’t identified any specific differences. I searched them thar intertubes for discussion online, and came up empty. Does anybody know? I can’t tell whether it’s new code, or something like a difference in compiler settings that has no effect on play.

When I played Steamhammer versus Iron, the games went as I expected. Nothing was visibly different. I also played the 2 Iron versions against each other, though only for 2 games. They played exactly the same opening, with only the usual small timing differences caused by different starting positions and such. I could not identify anything new in the play. Each version won 1 game. To me, they looked the same.

Maybe somebody has heard from author Igor Dimitrijevic, or has more time than I do to compare for differences.

The AITT S2 tournament (not to be confused with AIST S2) has been announced, AI Tinycraft Tournament for bots with under 4000 bytes of source. Registration deadline is 1 April, submission is 1 May. For this edition, the maps are air oriented, with starting bases that are islands, or that begin isolated by ground with exits blocked by minerals that can be mined, or neutral buildings that can be destroyed. All 5 maps are difficult, and they have common points but they are quite different from each other.

• (2) Paradoxxx is an old island map with 2 bases worth of resources in each main: 14 mineral patches and 2 gas geysers. The only other gas expansions are overlooked by a wide high ground area that the players are to fight over. If you can control the central high ground, which has no resources itself, you can probably control both gas expansions in the long run.

• (2) Coulee is a Blizzard map from way back. Each starting base has a main and natural that are somewhat far by ground and close by air, and which together are blocked from the rest of the map by a row of mineral patches with 500 minerals each. There are corner bases blocked by a mineral patch of 24 minerals (modern maps generally have 8 or 0 minerals in that kind of blocking patch). And there are center bases that you can try to hold if you somehow gain enough map control. The 2 center gas geysers, with no minerals nearby, have only 2000 gas each. It takes a long time to mine through 500 minerals, so you probably want to go drop or air. You could also push 3 workers through the minerals (or build a command center and float it outside, then make 3 workers there) and take a corner base, but you’ll be lacking mobility.

• (3) Plasma from 2008 has several tricky features. The main is small, so not all your buildings will fit there. The ramp is narrow, so that large units cannot pass. There are arrays of neutral eggs blocking the paths between bases. You can mineral walk workers through the eggs, because there are mineral patches placed in view on both sides. Other units can only pass once eggs are destroyed to clear a path, and eggs are tough so that takes time. (Well, can only pass easily. It’s possible to push units through the eggs, but it’s not quick or reliable.) Next to each main are a mineral only natural near the ramp and a gas natural on the opposite side. The center area provides access to 3 high ground expansions, each of which overlooks 2 starting bases.

• (4) Sparkle is the 2018 island map that attempts to be fair to zerg. Each base comes with a natural that has a blocking building that must be destroyed before you can mine the gas. It also comes with a third that has 3 mineral patches and a geyser that only zerg can mine from. There are 4 center islands with a base each, but it is often preferable to take a second main because it has more resources.

• (4) Arkanoid is about destroying neutral stuff. Each starting position comes with 3 bases, a main and 2 equal naturals, one to each side. Each of the dual naturals is blocked by 4 neutral chrysalis units, though I’ve seen a number of games where players mine with an offset resource depot instead of clearing the position. There are 3 paths out of each base, but each path is blocked by neutral buildings, and then you have to destroy further neutral buildings to get anywhere else. It is key to know where you are going so that you can destroy the right buildings. Arkanoid historically favors terran and sneers at protoss.

Useful skills are drop, pushing units through minerals, mineral-walking workers through neutral units, destroying neutral stuff that is in the way, and floating terran buildings for scouting and for mobility. For example, on Coulee a terran could float a factory out of the base and make 1 tank to prevent the enemy from mining its own blocking minerals; there are unbuildable areas on the map, but not just outside the bases, so add turrets and more units and the enemy will be forced to stick with air or drop.

I expect we’re going to see some wacky strategies from the tiny bots. Carriers versus battlecruisers will not surprise me. On the downside, the maps have bad imbalances in human play, although bot play is known to be different. I expect that we will see mostly terran and protoss and few zerg.

I promised a post about how Steamhammer can eventually optimize its own openings. In fact, I intend for it to be able to invent its own openings from scratch, as well as adjust openings (whether hand written or automatically generated) based on calculations and experience. Here’s an outline of my ideas.

My next big project is strategy adaptation. A large part of it will be implementing abstract strategies and the ability to turn them into concrete lines of play. For example, “3 hatch muta” is an abstract strategy at a high level of abstraction, and Steamhammer’s opening lines ZvT_3HatchMuta and ZvP_3HatchMuta are concrete implementations of the strategy, optimized for different matchups. Once abstract strategies exist, Steamhammer will be able to experiment with different strategies by simply filling in its abstract strategy data structure—with random values if no other way—and playing out the game, turning the abstract strategy into a build order. I suppose I’ll do this at home rather than during tournaments! There are more focused ways to find new abstract strategies: Steal them from opponents, extract them from replays, systematically explore the lattice of strategies (since they are partially ordered) extending the promising avenues, note enemy timings and units and do a directed search for strategies that hit the timings and counter the units. The space of abstract strategies is exponentially easier to search than the space of build orders; that is the advantage of abstraction.

Another part of the strategy adaptation project is to collect data on opening lines—aka concrete build orders—with their resource use and timings and unit counts and stuff. If we play out a strategy and get a build order, we record the build order as an opening, and if we play the opening we measure its data in real games. With the measured data, we can compare openings to judge which one is better in a given situation: Does it hit the timings, does it counter the units, does it grow a strong enough economy, does it have adequate defenses?

One way to do the comparison, which both I and others have suggested, is to set up the armies of both sides and run the combat simulator. That compares army strengths; if you also know economy size and tech level, you can do a more comprehensive comparison.

Once you can compare 2 opening lines for goodness in a given scenario, you can optimize an opening line for the scenario without changing its abstract strategy. I think I’ll try goal-directed modifications to the opening line—the enemy attacked early here, we need units in time; or the enemy had too much stuff later, we need more drones to keep up. Modifications that pass the comparison check can be tried in games.

Many new skills are needed. My plans are more than my accomplishments, and my accomplishments turn out different from their original plans. Even so, I expect to get a system like this working eventually. If you try a new idea on Steamhammer and it has no counter, it will invent its own counter and polish it by experience and reasoning. Then I’ll have gotten somewhere.