Starcraft AI blog

This came up (again) in comments to yesterday’s post. Steamhammer too often exceeds the time limit when playing a long game as protoss. It happens when the bot’s base fills up with buildings and there is no room for a new building. The building placer doesn’t understand the situation and keeps retrying, and meanwhile no buildings can be constructed. Building placement is slow so after a while it exceeds the time limit. Even if it didn’t exceed the time limit, the bot would likely lose the game because inability to place a building freezes the production queue so that nothing can be produced.

In principle. the same problem affects all races. In practice, terran can place buildings freely and zerg makes so few buildings that they almost always fit on available creep. If zerg wants a lot of sunkens, it doesn’t build them all at once, and each one extends the creep so that there is more space.

There are 3 different mitigations in the code that reduce the problem but don’t come close to solving it.

• Protoss buildings are allowed to touch each other vertically, blocking horizontal movement. This reduces the space taken, but occasionally causes units to get locked in enclosures.
• Steamhammer can randomly choose a new “main base” where future buildings will be placed. It considers doing this whenever a pylon is placed and more than one base is available to place it. This often causes buildings to spill unnecessarily into the center of the map.
• A special case in the production code recognizes when building construction is being retried, and retries less often.

Other simple mitigations that I have considered also don’t solve the problem.

A full solution, in my view, has 2 parts. The first part will be to make building placement much faster. I have 2 ideas that together I expect to speed up building placement by an order of magnitude or more. These ideas are made easier by the base data infrastructure that I’m writing now (see yesterday, new base placement code). I’m currently working on Steamhammer version 1.4.1. My plan is that building placement will be fast no later than version 1.4.3, I hope sooner. Expect a production freeze, but that is better than an instant loss.

The second part is to reason about building placement. The absolute minimum is to recognize: “Oh, building placement failed. It’s going to keep failing until a pylon finishes.” Then at a minimum it can stop adding buildings. Better, it could find a good place with space around it, and put a pylon there. I should be able to do that in the 1.4.x series, and it will solve the problem for good. There are complications that I will have to deal with. For example, if there is free supply then Steamhammer shouldn’t let unit production stop just because building construction is stopped or delayed.

Another step could be to recognize when a base is full, and stop trying to place buildings there. Put them somewhere else. The new base data should make that easier, too.

I want to go further, and write a general placement planner to optimize the placement of buildings and units. You specify goals: Place buildings compactly, while leaving space for units to pass. Form a wall at the front with as few gaps as possible. Place static defense to defend both the natural and the ramp to the main. Set lurkers just far enough apart that only 1 at a time gets hit by storm. Set tanks out of sunken range and in siege range and vision range. Spread out tanks to defend this choke. Prefer to put tanks on high ground. The placement planner figures out good places. It will be complicated, but I expect that with the speedups I have in mind it will be fast enough.

Time control in general is an issue that Steamhammer should tackle eventually. As it stands, near the start of the game the maximum time per frame is commonly at least 25 times greater than the mean time per frame, and it tends to increase as the game goes on. Steamhammer gets by because it does almost everything fast enough, so that it doesn’t have to worry much about breaking the time limit. When I add tactical analysis and other expensive features, that will probably change. It will become necessary to check whether there is time for each task, and defer or suspend or abort tasks that threaten to go over. I’ll figure that out when I get there.