Starcraft AI blog

Here’s the secret connection between prioritizing your goals and novelty maps: Once you have explicit goals, another thing you can do is reason about them.

You’re playing on Crystallis. Human players somehow realize, without having to think about it, “I’ll need gas, so I should set workers to mine in the direction of a geyser.” How could a bot figure out the same thing? Imagine that you want to be able to play on any map, even a novelty map with strange features.

The bot should already know “I’ll need gas,” so the question is how it can figure out the way to get it. The bot also needs a model of the game, so that it can understand the effects of its actions and plan a sequence of actions to reach its goal. It needs to know that minerals can block movement and that workers can mine out minerals.

Means-end analysis was introduced into AI sometime around 1960 in the famous General Problem Solver program. It says, given a goal, seek means (aka actions) to reduce differences between the current situation and the goal. One way to put means-end analysis to work is in “plan repair,” which means finding workarounds for problems. It’s part of the AI topic of planning. If you like academic papers, here’s a list: Citeseer on plan repair.

Suppose the bot is terran. It already knows a basic plan to get gas: 1. Send an SCV to a geyser. 2. Build a refinery. 3. Transfer gas from the refinery to a command center with SCVs. If bot uses its model of the game to see whether the basic plan works, it will find that the first step fails; the SCV can’t get to the geyser. Can the plan be repaired? Working backward from the goal of being at the geyser, the bot might reason: If I can mine out this mineral block next to the geyser, then I can reach it. Can I mine out that mineral block? No, but these other mineral blocks are next to it, can I mine one of them out? If the bot keeps searching backward (using a means-end heuristic to speed things up: the mineral block closest to the command center is the one that minimizes the difference between the current situation and the goal), it will eventually find a path of mineral blocks to mine out to reach the gas. Problem solved.

The bot might also ask: Can I fly an SCV to the geyser? To fly it by dropship, I would need a dropship, which costs gas; no can do. Or I could float a command center and make an SCV, but there’s no place to land it; no can do. Or the bot might figure out how to push SCVs through the minerals enough times to reach the geyser, which probably is part of best play. If it’s clever enough, it might be able to compute an efficient combination of mining out minerals and pushing SCVs through the last minerals to start getting gas a little earlier.

Plan repair can work to solve many kinds of goals in many kinds of situations. A bot with that skill could play novelty maps at least passably, and could solve planning problems that come up in normal games. Obviously it’s a very complicated skill, and one that bot authors will not be in a hurry to implement. But I think it’s a destination we should aim to reach eventually. And the first step, of course, is to make your bot’s goals explicit.

Next: After the map is mined out.

Humans can play on crazy novelty maps where normal play does not work. We don’t have much trouble inventing special strategies for special maps. It’s a more extreme example of the human adaptability that we see in normal play. Bots have too much scripted behavior and can’t adapt at all to extreme novelty maps.

On the Blizzard map (2)Crystallis distributed with Brood War, the players start out separated by deep maze-like formations of 48-mineral blocks. Gas geysers exist, but they are also behind minerals, so before you can tech you have to mine a path through to a geyser. It’s a playable map, and maybe fun once in a while, but the strategies are vastly different than on a competition map (and terran would seem to have a big advantage). Crystallis seems to be well-known for crashing the BWTA terrain analyzer, so I expect many bots can’t play it at all. In this picture, look at the minimap to see how far the SCV’s have come from the original command center.

On (6)Crazy Critters, also included with Brood War, the map is so full of critters that it is difficult to place buildings. Units face big delays in moving as the pathfinder struggles with shifting critters. Here I opened with a forge and cannon to kill enough critters to make space for a gateway—I couldn’t find a way to place a gateway otherwise, but the random shifting of critters sometimes made room for smaller buildings, when the probe could arrive in time. The terran opponent is a built-in AI, which built a barracks in my base not because it wanted to proxy, but because that was the first open space it found. Also notice my soaring mineral count; I found myself unable to place enough buildings to spend my income. The map is frustrating to play on, but people can do it.

Less extreme concept maps from Blizzard include Blood Bath and Big Game Hunters. Both have been popular in their communities and people have developed specialized strategies.

Concept maps are rare in competition today, because they are difficult to balance, but they went through a period of popularity in pro tournaments around 2006-2008. Examples are Arkanoid, Demon’s Forest, Monty Hall, Plasma, Triathlon, Troy. Another interesting concept map is Fantasy, in which each quarter of the map has a different design, so that the map is not symmetrical and the game balance and strategy depend on the random starting positions. A lot of fun games with surprising strategies have been played on concept maps, and it would be cool if new ones were invented to meet today’s standards.

Here is Demon’s Forest as an example. Much of the 3-player map is covered by an array of doodads that block vision and sometimes bug out the movement of large units. Here an overlord off the top of the screen (visible on the minimap) provides vision of part of the array, and below two hydralisks are barely able to see beyond their snouts. I set up three other hydras in a triangle to show their lack of vision on the minimap.

Island maps were abandoned in competitive play after the early years, because they were imbalanced against zerg. But I wonder—today we know a lot more about how to balance maps. I don’t have the expertise to try it myself, but I would be interested to find out whether an island or semi-island map could be balanced today, using some variety of pro-zerg tricks: Smaller buildable areas, so that protoss and terran are forced to spread buildings across different areas; gas-only or low-mineral expansions, which zerg gets “for free” because zerg needs the hatcheries anyway; expansions or other areas with neutral creep colonies that zerg can use right off, but where other races need to kill the colonies first. The terran late-game information advantage could be reduced by putting a map doodad where the comsat would go in some expansion spots. There are more, you get the idea.

How do humans adapt their play to unfamiliar map features? I don’t know, and it seems like it must be complicated. I picked novelty maps as an extreme example, but humans (given time to learn) adapt their play to all map differences, and in fact to all aspects of the situation. Circuit Breaker and Fighting Spirit are both standard maps and play similarly, but features of the maps—like the mineral-only on Circuit Breaker and its position next to a low-ground expansion—make for important strategy differences. In an example of a different kind of adaptability, Last gained an advantage over Flash in their recent ASL match by recognizing Flash’s habit of building his barracks forward, to lift off and scout sooner. Last scouted for the forward rax and harassed the building SCV. I’m very interested in understanding that kind of human adaptability so that bots can eventually reproduce it. I think bots won’t catch up with humans strategically until bots can adapt broadly and deeply by learning over time.

How can a bot even get started on a map like Crystallis? Without being told, how could it figure out what to do to get gas? Next: Means-end analysis.

I had been hoping that Zia would start to choose between its openings, and now that it has I want to see how it’s doing. So I watched a bunch of replays. It’s using strategy learning, though I can’t say in what form. I predicted that choosing between its strategies would be advantageous, and it’s true to an extent.

With more variety, Zia has become more entertaining to watch. I like it. Zia plays these openings that I’ve seen:

• 5 pool
• 9 pool
• 9 pool speed
• 12 hatchery

I didn’t catch it playing overpool or 12 pool, which you might expect to be common.

Zia’s opening chat message gives a hint about its opponent model. It says “Nice to meet you!” for new opponents and “Hi again!” for opponents it has met before. And it either predicts a “harsh game” or claims “I may overwhelm you.” I think it picks the second message when it believes it has found a strong counter strategy.

Against opponents with a single strategy which is directly countered by one of these openings, like ZZZKbot’s 4 pool (hard countered by 9 pool plus a sunken so that the trickle of attacking lings has no chance whatever), Zia seems to learn the counter and should then win every game. Zia even managed to find a strategy that gives it a chance against IceBot—Zia won a game which brought out weaknesses in both bots, weaknesses I didn’t realize IceBot suffered from.

And I see signs that Zia adapts after the opening. For example, I saw it add a spire when it needed scourge for air defense. I get the impression that it decides flexibly between hydralisks, mutalisks, and lurkers for the middle game—at least it’s not hardwired, maybe it’s random, I hope it’s learned. I have seen it play 12 hatch, 11 pool, 10 gas and also 12 hatch, 11 gas, 10 pool; I hope it’s foreseeing how much gas it will want to boot up its future unit mix.

Playing many openings does have a disadvantage: It’s harder to play all of them well. It’s not enough to know the build, you have to know how to play it, and it adds up to a lot of knowledge. The worst is Zia’s 9 pool speed opening, which it plays in a strange way as a late zergling all-in: It makes 100% zerglings until it attacks around supply 20-24; if it fails, Zia doesn’t have enough economy for the middle game. (I expect a 9 hatch build would strike harder if you want to play that way.)

Zia still plays poorly overall, if you ask me. It needs to brush up on skills like not sending drones through the enemy army. It needs better scouting (it doesn’t send out its initial overlord), better tactics (no, don’t run up the ramp to fight the bunker! Hit the SCVs in the expansion first!), better engagement skills (big groups of zerglings should surround before attacking), and better micro (in lings versus zealots, retreat a ling that will die in 1 more hit). And stuff. It’s a hard game.

Zia’s current description is “Implementing more strats . . .” I guess the author has the most fun with that, which is all that really matters, but it’s not the way to a winning bot. Breadth of skills, not depth of skills: You gain more by reducing your weaknesses than by increasing your strengths. Zia already has relative strength in strategy, and will improve most with other skills.

Hmm, I should write a post about The Winning Attitude for authors of game programs. Only for those who seek the winning attitude, of course; it’s optional.

Tomorrow: Novelty maps.

This post is for people who want to move their bot’s decision making beyond chains of if-then rules and hadn’t realized how easy it is to start.

As I mentioned in a comment a few days ago, I watched a game in which a protoss bot’s base was under attack by dark templar. The defender had a robotics facility and observatory, and it either had the smarts or got lucky enough to produce an observer during the attack. The new observer instantly set sail for the far side of the map to scout expansion spots, and the unopposed dark templar soon tore down everything, gg.

Well, maybe the defender didn’t how to use detection at all, but I want to draw a different lesson: Do the important stuff first. Defending your base is more important than finding out whether the opponent has expanded. Attach priorities to your goals.

From what I’ve seen, most bots make most of their decisions by if-then rules, and they do the important stuff first by checking the important rules first. And that’s a good start, but I think that adding a little more smarts can give a lot more adaptability.

Separate goals from their priorities. Every goal has an importance: Defending your base is necessary, it keeps you alive; scouting is less urgent, and so on. If you have an if-then chain, you can easily re-architect it as a goal priority calculation. Each rule, instead of performing its action, assigns a priority to its goal, or adjusts its goal’s priority. At the end, accept the top goal. Once you’ve done this mechanical code refactoring, your decision architecture is more flexible and you’re free to make decisions in more complicated ways without messing up your code.

I think of it as a simple kind of search. It’s a search over goals where the evaluation function tells you the goal’s importance. The evaluation function might do something complicated, but the decision architecture is easy to understand.

Once you’ve separated goals from priorities, a further step could be to separate goal priority from goal feasibility. Every goal needs some resources to accomplish. If you can figure out what those resources are, then you know how to divide your resources to accomplish multiple goals at once and move up to a whole new level of capability. Of course it can be hard to figure out the resources needed. What constitutes enough base defense? But if you can do it, then you can split your army in a principled way: These units to defend the main base, those split off to defend the new expansion—or those go to harass, or whatever. Or: This goal cannot be accomplished, give up on it. Or: These two minor goals can both be accomplished, and together they weigh more than the one major goal.

This goes, of course, for goals at all levels of abstraction: Strategic, tactical, unit control.

Tomorrow: Checking in on Zia again. After that: Novelty maps (a topic secretly related to this one, gnekh gnekh).

This rule of thumb occurred to me: Every strategy or tactic that requires specific knowledge to defeat, is likely to beat many bots.

If you don’t know how to fight carriers, then carriers beat you, and XIMP knows it. If you don’t know how to fight lurkers, then lurkers beat you. If you don’t have specific knowledge of dark templar, zergling rushes, or cannon rushes, then they’ll beat you.

“If you see an enemy structure in your base, kill it now even if you have to pull workers” is general knowledge and stops all kinds of proxies that are scouted, including cannon rushes. But if the cannons come up, to work around them or fight them you need specific knowledge of that situation.

Bots start out ignorant and adding knowledge is hard, so each bot tends to have only the knowledge that its author thinks crucial. So if you know any trick or tactic (no matter how crude and noobish) that you can defeat only with specific knowledge (no matter how little or how simple), then why not try it? Maybe your bot will be the next Stone, which had a frivolous strategy but a top score.

Tomorrow: Give your goals priorities.

About detection as a counter—I didn’t find much to say. Get it when you need it, or that is, when you expect to need it (react to the future).

I do have a few general observations. Each race has invisible stuff that’s valuable even when the opponent can detect it. Invisibility is a force multiplier, but wraiths, spider mines, dark templar, and lurkers can remain strong when seen.

Also, detecting invisible stuff is not the only way to cope with it. The area spells nuke, storm, maelstrom, stasis, ensnare, and plague do not care whether units in their area of effect are detected. Maelstrom, stasis, ensnare and plague make cloaked units visible. Only nuke and storm affect underground units. Walling or physically blocking with units can keep dark templar from crossing a choke—they’ll have to fight their way through, gaining time to get detection. Terran spider mines can defend against dark templar without needing to detect them.

how to detect

Every race gets a static early detector (that also provides air defense) plus a flying detector. I assume that the combination static detector + air defense design is intended to balance wraith cloaking.

terran
turret	early
comsat	midgame
science vessel	late

Because terran’s mobile detector is late, terrans get comsat for midgame detection. It’s part of the terran “low tech but adaptable” theme. Good opponents know how to exploit terran’s limited comsat energy: For example, dark templar can provoke scans at different places and times and eventually become able to get free hits. The more scans terran spends on cloaked units, the fewer are left to examine your base and your army composition and location.

protoss
cannon	early
observer	midgame

The protoss twist is that observers both provide detection and are cloaked.

zerg
overlord	early
spore colony	early

Zerg gets detection for free with overlords, so the main detection issue is usually whether and when to get overlord speed. For detection purposes, it’s a matter of weighing the safety of overlords and the ability to pre-position them where they may be needed. Whether and when you want to get drop also matters.

what needs detecting

terran
spider mines	midgame
cloaked wraiths	midgame
cloaked ghosts	late

Spider mines are so numerous that opponents often don’t try to detect them but force them or sacrifice units to clear them in a hurry.

protoss
dark templar	midgame
observers	midgame
stuff cloaked by arbiters	late

Permanent arbiter cloaking more or less forces terran to get vessels and protoss to bring observers. Zerg usually has overlords all over anyway and doesn’t have much trouble.

zerg
burrowed units	early
lurkers	midgame

Burrow traps are rare because they don’t often work, but we do see burrowed hydralisk traps sometimes versus corsair-reaver strategies. And burrowed zerglings for map vision and to delay expansions do appear in human play.

Apparently I have no deep insights into detection, but it was a request so I tried. Maybe it will be of use to bot authors who haven’t mastered the game yet.

Today’s topic of ground versus air is more complicated than yesterday’s topic of air versus air, so I don’t go into as much detail. Not that anybody was overwhelmed with details yesterday. It’s all Quite Abstract, ahem, allow me to adjust my spectacles.

Two systems of counters are designed into the game for ground units as a group versus air units as a group.

you need anti-air

The first and most basic system of counters is:

1. Not all ground units can shoot upward.
2. Those ground units that can shoot upward are more efficient than air units.

#1 means that as soon as the opponent has wraiths, your tanks need to bring goliaths along with them everywhere, or to stick to places where you can build turrets, or something. In every matchup, you have to worry about air defense. In PvZ, corsairs and not ground units are the favorite air defense, but that doesn’t change the principle.

#2 means that bringing goliaths is all you need. A few goliaths can beat a lot of wraiths, so you don’t have to give up on tanks altogether. Even if the opponent has mass carriers, goliaths are efficient and you can keep tanks. #2 also means that ground units tend to be more important than air units. The more efficient unit can overwhelm the enemy with strength; the less efficient unit will need to win with skill if it can win at all.

You may be surprised how thoroughly and carefully the units are designed so that ground has an advantage over air. 8 unupgraded marines, the same mineral cost as a battlecruiser (and much less gas cost), are about equal with a battlecruiser. 8 marines with stim can easily shoot down a battlecruiser. 2 hydralisks, the same mineral cost as a guardian, can shoot down a guardian. And so on.

air units have countervailing advantages

The second system of counters has to do with properties of air and ground units that hand air units an advantage sometimes, even though air loses head-to-head.

1. Air units can go anywhere.
2. Air units stack.

#1 means that air units can outmaneuver ground units to gain a local preponderance of force. They can make hit-and-run attacks, trying to stay a step ahead of the defenders, or to spread them thin so they can be defeated piecemeal, or to convince the enemy to spend on static defense. Ground beats air in a head-to-head fight, so air will avoid that and go for guerilla action until it gets far enough ahead to win straight up.

#2 means that air units can use mass more effectively than ground units. A group of mutalisks can stack up so that they all attack at the same time. If they are picking off marines, then rear marines may be unable to return fire—mutas will try to hit when marines are in poor formation. The same for other air units. This advantage of mass air is why each race has an air splash unit, as I talked about yesterday—the air splash unit means that the defender’s advantage remains even against mass air. Air splash at least forces mass air to scatter and lose its stacking advantage.

Also, every race has an air siege unit that can win the game if unopposed. If the map is mined out and nothing is left but a couple battlecruisers for one side, the cruisers can slowly yamato away static defense and blast down everything else. Protoss has carriers and zerg has guardians. Even when opposed, the long range attacks make cliff positions valuable.

Tomorrow: Detection. Though I haven’t thought of much to say about it yet.

I got a suggestion by e-mail to theorize about ground, air, and detection. It’s a vague request, but I take it to be about the systems of counters designed into the game, many of which are arranged rock-scissors-paper style: valkyries counter wraiths, battlecruisers counter valkyries, wraiths counter battlecruisers. So, in hope that this will be of use to some people....

Instead of facing the question head on, I’ll start with air as an example. The design of the air combat units in Brood War is more straightforward than the design of the ground units. The terran and protoss designs are closely similar in outline:

terran unit	ground attack	air attack
wraith	weak	strongest
valkyrie	-	splash
battlecruiser	strong	strong

I’m leaving out spell units like science vessels and spells like wraith cloaking. Not to mention all the details that I’m not mentioning.

protoss unit	ground attack	air attack
corsair	-	splash
scout	weak	strongest
carrier	strong	strong

Each has a ground harass unit with a strong anti-air attack, a splash anti-air unit to counter mass air, and a capital ship that is strong all-around and resistant to direct splash attacks. The difference is that for terrans, the ground harass wraith is cheap and the splash valkyrie is expensive, while protoss has it the other way around, a cheap corsair and an expensive scout. Corsairs counter scouts, scouts counter carriers, carriers counter corsairs—at least notionally. A carrier has base armor 4, so a corsair with attack 5 can barely scratch its hull, but corsairs counter interceptors, which can be as good. Head to head, 1 carrier can easily defeat 4 corsairs which cost more than the carrier and its interceptors. With enough corsairs and a situation that allows them to stand off and attack interceptors, the costs go the other way. The moral is, the outline is only an outline and details count.

“Corsairs counter scouts” is another simplification. Air units stack to attack together (and there’s a limit to how widely they can scatter and still act as a fleet), and air splash damage also stacks. So the anti-air splash units become more cost effective in relation to the enemy as the enemy fleet gets larger. The larger the fleet the harder it can be countered, so the net effect on strategy in terran and protoss matchups is to make ground combat more important, at least until late game when capital ships come out.

The zerg design is different—

zerg unit	ground attack	air attack
scourge	-	strongest
mutalisk	weak	weak
devourer	-	splash
guardian	strong	-

—because the strengths and weaknesses are split up differently and have some twists. As suicide units with low hit points, scourge are risky and difficult to use in large numbers, but they’re efficient when they hit. Devourers don’t do splash damage directly but by splashing acid spores, so that devourers become support units—that’s good game design, it means players have to coordinate units. Mutalisks are the only air unit of any race that is both cheap and versatile, and they’re faster than battlecruisers or carriers, but they are countered by scourge and by devourers plus anything that can attack air, and they don’t directly counter any air unit of any race except guardians.

Consider the timings of the anti-air splash units. Corsairs fly early, so terran and zerg should be reluctant to commit to large air fleets vP until late game. Valkyries are later and more expensive, so zerg can harass early with mutalisks vT; scouts are too expensive to be harassment units. Devourers fly late and zerg needs overlords, so opponents vZ can go air if they choose. That and the high mobility of air units is why ZvZ is usually a mutalisk-scourge battle until late game (which is not often reached).

The cross-race unit counters are understandable in outline from these tables plus a little background knowledge: Battlecruisers can one-shot scourge, so scourge counters carriers harder than cruisers. Devourers splash in a way that counters capital ships with their heavy armor, unlike valkyries and corsairs. That’s most of the greater-than/less-than knowledge of counters needed for air-to-air fights. It doesn’t say how much greater than; to code it, you need numbers. Knowledge of counters is about knowing which units to build and which units to send; combat itself ain’t so simple.

The idea of today’s post is to set a point of view. It’s like setting a nail. Now when I get down to it you should know what I’m hammering on.

Tomorrow: Air versus ground, in general terms.

3 example games to give an idea how to cannon rush at the pro level, with lessons for bots in both offense and defense. This is only a taste of the range of variations—different timings and positions and mixes of techniques are possible.

a standard main-base cannon rush

This is the most recent pro cannon rush game: Jaehoon cannon rushed Shuttle in game 2 of their round-of-8 ASL match on 21 August 2016 (game 2 starts at 47:50 in the video). It’s an in-base cannon rush behind the main mineral line, and Jaehoon’s version is as standard as can be for a rare strategy. Call it a canon cannon rush. The requirements and steps were:

1. it works on 2-player maps, where you don’t have to scout the opponent’s location
2. there must be room to proxy where the opponent may not see
• here, behind the opponent’s main mineral line
3. send out one of your first probes: watch the north base in the minimap, a probe sets out immediately
4. sneak the probe into position: Jaehoon skirted the edge of the enemy base in hope of staying unseen
5. proxy a pylon, then a forge
6. build 2 rear cannons first, to fortify the position before it is scouted
• the rear cannons should be as sheltered as possible; Jaehoon used buildings and trees as shelter
7. around the time the 2 rear cannons finish, add 2 front cannons in range to attack
• the opponent will see the front cannons, but the rear cannons protect them

The opponent should know you’ve proxied as soon as they scout your base. They still have to find the proxy itself. If the opponent finds out in time to stop the 2 rear cannons from finishing, the cannon rush fails and the rusher is set far back.

In this case the cannon rush succeeded and Shuttle had to abandon mining in his main, but that was not enough in itself for Jaehoon to win. A pylon and 2 cannons already cost as much as a nexus, and the cannons can’t move. Shuttle canceled his gas and second gateway and built a nexus at his natural. Jaehoon was able to get gas and pull ahead in tech. Watch the rest of the game to see more followup!

These are the requirements and steps to cannon a pro. You see why it can’t be played often. It may be a little easier to cannon a bot!

Lesson for bots which cannon rush: Don’t go overboard. Jaehoon could have added more cannons and killed buildings, but the time and expense would have put him behind. Follow up with gateway units.

Lesson for bots which get proxied in any way: If the opponent’s base doesn’t have enough stuff in it, scout in and around your own base for a proxy. Ideally, count minerals and compare total mining to the buildings and units that you see. You may also want to scout the center of the map. If you want to be safe no matter what and don’t mind paying for it, don’t wait but always scout your own base (like some versions of Tscmoo).

Lesson for bots which get cannon rushed: If you can’t mine your main minerals, you still need to mine. Expand!

a Nal_rA natural cannon rush

In Nal_rA vs. Zergman from 2006 on Rush Hour 3 (a 3-player map), Nal_rA shows us a similar cannon rush, but executed later against the enemy natural instead of the enemy main. The requirements and steps:

1. there must be room near the opponent’s natural to proxy where the opponent may not see
• here, to the side of the opponent’s natural base location
2. this build works against an opponent who can be expected to fast expand—mostly zerg
3. scout at a normal timing
• I suspect Nal_rA decided on the build when his scout crossed paths with the overlord
4. build a pylon and forge in your main
• Nal_rA built the forge in the back where it might not be seen at first
5. sneak a second probe into position
• Nal_rA sent the probe in a loop to avoid any zerg scouts
6. build the pylon, 2 hidden rear cannons, and 2 front cannons as above
• start the front cannons as the hatchery finishes
• zerg benefits if the hatchery can be canceled in time

Zergman reacted in an interesting way, and the game is entertaining.

Lesson for bots that get cannon rushed: Zergman’s sunken colonies remind us that sunkens can keep cannons away. Zerg bots need to learn how to place sunkens to keep the cannons from pushing ever closer. Protoss bots can place counter-cannons for the same purpose. Terran... has more work to do until tanks come out. Terran should build away from the cannons and be prepared to float buildings to new spots.

a Nal_rA cannon containment

Not as standard as first two example games. In Nal_rA vs. Orion from 2007 on Blue Storm, Nal_rA shows us how to build up a cannon containment even against strategically correct counterplay, by also proxying gateways. Orion opened 9 pool, the best opening if you get cheesed, and still ends up crushed by Nal_rA’s strong creative play. The requirements and steps:

1. it works on 2-player maps, where you don’t have to scout the opponent’s location
2. send out a very early probe
3. predict the overlord scouting path to avoid being seen
4. build a pylon, then a forge
5. Nal_rA made only one cannon before the first gateway
• variations are possible
• this variant emphasizes adding zealots in early
6. add more cannons and zealots until the containment is tight
7. after or while doing that, defeat any forces outside the containment
8. if the last step is successful, then the enemy is weakened and the game is almost over

Look at the beautiful placement of that first cannon, walled in by terrain, minerals, geyser, and the pylon and forge. That is what makes the build work; without that excellent placement, Nal_rA would have to build 2 cannons before the first gateway and would have fallen behind in mobile units. Even the next cannons are tucked behind gateways to reduce their attackable surface. Nal_rA did not build cannons in the open until there was enough defense to protect them as they warped in. At some point I will look into the wall-building code in LetaBot and see whether it can be adapted to uses like this.

Zerg opened with the safest anti-cheese opening, 9 pool, and followed up in a strategically logical way at every point. Orion did make tactical mistakes, though. The good moves:

1. send zerglings across the map to force Nal_rA to warp cannons in his main
2. get an expansion, so as not to be trapped on one base
3. switch to hydralisks, which are more efficient against zealots and cannons

Zerg could have countered the proxy by scouting his natural: Hold the first overlord there for a while, or send an early drone to check it. When the proxy is found, pull drones to stop it, and zerg is ahead. But if protoss were playing normally, then the extra scouting effort would put zerg on the back foot.

Lesson for bots which get cannon contained: It’s important to have a worker outside the containment. Keep your scout alive, or send out a worker before the cannons finish. Cannons mean that your opponent has little offensive force yet, so you can fast expand at any convenient base. Produce forces at your new expansion and you can go for the enemy main, or sandwich the containment, or whatever you want. Other reactions may be good too depending on the situation, but this way is natural, and I’ve never seen a bot do it.

Update: Cannon like a newbie basher. This 3 minute video shows a cannon rush in which you block off a space behind the enemy minerals with 2 pylons and place a cannon between them, where it can’t be reached. You’ll never see this rush in a pro game, because it’s trivial to beat if you know how to push units through the minerals. But I have never seen a bot that knows how to push through the minerals.... This variant has the advantage of simplicity; it works on many maps and in a wide variety of situations.

“Cheese” is a put-down, and the proper definition of “cheese” has a flavor of “stupid trick that you shouldn’t have beaten me with.” But who cares? I can pretend to be objective, and define a cheese strategy as: A surprise strategy which is all-in and fails if the opponent scouts or expects it. If the opponent pays a cost to stay safe against cheese, then game theory says that you may want to take the risk to cheese a certain percentage of the time to force your opponent to pay. The cost can be the need to stick to rush-safe strategies, or only the cost of scouting for proxies. It depends on your risk of losing with risky cheese versus the opponent’s cost to stay safe, of course.

Another definition of “cheese” is: An all-in opening that sacrifices economy to an extreme degree. It doesn’t say how extreme, but it’s closer to how people use the word in practice.

Against a human you can’t play cheese often, because it fails if expected. By definition! But bots are not good at expecting things. Most bots are vulnerable to cheesy openings and only a few have strategy learning that may be able to learn to defend, so—why don’t other bots cheese more?

I’ll talk not only about cheese by my definition, but also other risks or tricks that seem cheeselike. I was only pretending to be objective.

cheese that current bots try

• 4-pool, 5-pool, 6-pool
• cannon rush, cannon contain
• dark templar rush (not cheesy, but risky if it’s very fast)
• hard zealot rush (not cheesy, but all-in when protoss commits to it)
• SCV rush (in some LetaBot versions, and formerly by Stone)
• BBS (two barracks before depot, played by Tyr)
• marine rush (10 barracks into infinite marines, UAlbertaBot)

other cheese

• offensive sunken in ZvZ (ASPbot did this in 2011)
• proxy hatchery
• proxy 5 rax (LetaBot used to do this with bunkers; variations are possible)
• proxy factory (make super-early vultures to kill workers)
• barracks float, factory float (into the enemy base)
• proxy gateways (which can mix with cannons)

The offensive sunken in ZvZ can work when combined with another attack. By itself it just fails if the opponent reacts. The natural other attack is, of course, a 4 pool or 5 pool after you scouted with a drone.

You can make anything at a proxy hatchery. In the early game you make zerglings or sunkens. If you get burrow, a drone may be able to hide in the enemy base for a long time before proxying. If you somehow remain unscouted in the middle game, you might build lurkers. In the late game, drop a drone in for creep to support a nydus. All these are risky cheese plays; if scouted, they lose resources for nothing.

I think it’s strange that we see zergling rushes and marine rushes with BBS, but no zealot rushes with early forward gateways. On a 2-player map, building gates near the enemy base at 5 and 6 supply kills most bots effortlessly. Many other forward and center gate variations are possible, at least up to 9-9 center gates.

In another point, if you’re making an all-in rush, there’s no disadvantage to bringing some workers along for the fight, no matter your race. Terran of course can make bunkers. Protoss can make a proxy shield battery (typically in the enemy natural) to support the rush—the pylon is “free” since you need it anyway.

It’s also strange that we see no in-base proxies other than cannon rushes. Many bots will pop like a balloon when you hide a gateway or two in their base. Against a terran bot that doesn’t scout its base, you can hide a probe and make a late in-base proxy gate for dark templar. Or try this BBS variation as terran: Scout early, and build your first barracks in a distant part of the enemy base, near a cliff. Build the second barracks beneath the cliff and float it up beside the first.

Some slower tech rushes are so risky that you could call them cheese. 1-base lurker is one example. AIUR’s fast 4-zealot drop is another.

cheeselike tactics

You can block stuff with a worker/pylon/etc. It’s not cheese, but it’s tricky and cheeselike.

• gas steal
• mineral steal
• manner pylon
• pylon block of terran add-on (especially the first machine shop)
• block natural hatchery/nexus (common against 12-hatch)
• block opponent from walling
• block opponent’s exit (on maps with a small exit like Heartbreak Ridge)
• pylon prison, a crazy blocking trick

Bots still know how to steal gas, but I think they've given up on doing it because they stopped seeing advantage. I think that once bots can read and react to the opponent's strategy well enough, they should go back to stealing gas, but only at times when it will channel the opponent's strategy in a direction that the bot can exploit. Opponent modeling helps. If you know that your opponent’s tech causes you trouble, then steal gas to delay their tech.

You can order your scouting worker to mine an enemy mineral patch, and then the enemy can't mine it at the same time. You can steal 8 minerals or stop mining early and start again. It's mild harassment that slows down enemy mining slightly. If you also steal gas, you can steal 8 minerals, steal 8 gas, steal 8 minerals... which is not useful but is funny.

Manner pylon is advantageous if done at the right time and place. It can cause the opponent to lose more minerals in mining time than the pylon cost. The reason we only occasionally see manner pylons in pro games is that pros prevent it when they care, briefly idling a worker to stop it if necessary. Manner pylon can be worth it in the early game, and it can be worth it later in the game at expansions. I think it's safe to guess that very few bots will react correctly to manner pylon; they will not know how to prevent it, and they will lose more mining time than necessary when it happens. Bots with fixed build orders will mess up their timings. It can be a little tricky to pull off a manner pylon, though, because you can only build it when the spot is free of enemy workers. Good players can predict when the spot will be free and slide through the mineral line with the right timing to build the pylon in passing.

Cheese is healthy for bots because opponent bots need specific knowledge to respond well, and there are many kinds of cheese so much knowledge is needed. But cheese can also be difficult to play well. Current bot cheese is plain cheddar next to pro artisanal cheese. Tomorrow: Cannon like Nal_rA.

LetaBot suggested I should write about the decline of the rushbots. He pointed out that ZZZKBot by Chris Coxe (the best of them) is no longer a top bot on SSCAIT, but has fallen to the middle of the pack, and that UAlbertaBot has lost ground too. I’ll add that cannon rushes were never reliable, but remain moderately successful.

It would be interesting to examine the decline in historical data, but I don’t have the historical data. I once thought of setting up a job to scrape the SSCAIT page once a day, to save the game results for analysis, but I decided there were better uses for my time.

The rushbots are failing because rushbots have not changed and their opposition has improved in defense. The defense improvements include safer openings, better worker micro, and more cautious play with early military units (such as Tscmoo stationing early units defensively in its mineral line). Also the SCV rushbot Stone has been replaced with the non-rushing Iron—if Stone were still playing on SSCAIT, maybe its results would still be good. Or maybe not, we don’t know; its disappearance reduced pressure to improve rush defense. The fact that SSCAIT admins are tired of zerg rushbots (as we all are) and have disabled many of them also reduces pressure to improve rush defense.

This is going on a bit of a tangent, but I’ll tell a story. Once upon a time I was playing (on Lost Temple, it was that long ago) as zerg versus a protoss who was clearly better than me (which wasn’t saying much). I saw the protoss army move out toward my mineral-only. I had prepared a backstab: I ran a dozen speedlings past the protoss natural into the undefended main mineral line. Then I had to turn my full attention to defense, narrowly holding the attack, and I didn’t see what happened with the backstab. After I lost the game I watched the replay. I was astonished to find that the protoss had not lost a single probe to my backstab, but had microed probes to glitch out my lings and kill them safely. I hadn’t known it was possible. It was a memorable lesson: Micro can make the difference between losing everything and losing nothing.

Worker micro is a key skill, and it’s basic to good play. Even today’s best bots have visible flaws in their worker micro. As long as that remains true, the zerg rushbots have a chance to win even against some safe strategies, and they have a role to play as teachers. But if they want to keep that role they’ll have to improve their zergling micro. They need to know how to avoid defenders while attacking vulnerable workers, when to step back and change targets, and when to gather up a force before striking. At least they need to go around the bunker instead of running straight into it and dying.

For the rest of the post, I’ll concentrate on zergling rushes.

4 pool and 5 pool are objectively sound, and can be played at pro level. Like any playable opening, they counter some enemy strategies and are countered by others. If a pro plays a safe opening, then a 4 pool or 5 pool will lose. But pros are always looking for an edge, and they will correctly play unsafe greedy openings to get one—if you never play an unsafe opening, you are leaving money on the table. And if your opponent plays unsafe openings often enough, then it is correct to make them pay the cost for the risk they are taking. Also some openings are in-between, safe-ish but vulnerable to better micro or better luck.

4 pool comes in two variations. The build order for the more aggressive variant is: 4 pool, 6 lings. The other variant is: 4 pool, 1 drone, 6 lings; with the extra drone you have more economy but you can get 2 fewer lings before the first overlord. There is not much difference between the variants; they are both do or die. 5 pool is a little slower, but your stronger economy means that you need to do less damage to the enemy to break even. You can accumulate minerals while attacking, which gives options to transition into another strategy. 5 pool can be played against any race, but experts don’t 4 pool against protoss because protoss will normally survive and you need that touch of extra economy to make it to the middle game.

This old Team Liquid post lists pro games and statistics for 4 and 5 pool games between 2004 and 2009. There are not many; play them often and you’ll lose often; play them occasionally to punish greed and you’ll do well. 5 pool was played as recently as 17 July in Effort vs. Shuttle on the first day of the ASL (Afreeca Starcraft League). (It’s the first game of the cast, starting at 9:37 into the video. The English commentators didn’t count the drones and never realized it was a 5 pool.) Watch the game if you want to see the economic risk of a zergling rush. Effort got lucky and scouted the right way with his overlord, but Shuttle also got lucky and saw the lings in time to make a shield battery and pull the minimum number of probes to hold. Effort struggled for the rest of the game to catch up, but despite strong aggressive play in the middle game never drew even.

6 pool, 7 pool and 8 pool are considered inferior. They are seen as giving up economy without enough payback: The zergling attack at the later timing is too weak to be threatening.

9 pool is no longer a rush but a mainstream build. With 9 pool and zergling speed, the lings have greater potential to run by defenses, they can catch and kill fleeing workers, they can switch between targets with agility, and they’re generally more dangerous. And even this non-rush build is economically risky except in ZvZ. Overpool (overlord at 9 drones, then spawning pool at 9 while the overlord is in the egg) is the fastest build that is common outside ZvZ.

If you always play the same strategy, then you set yourself up for a counter. Bots with strategy learning will learn to counter you. If you always play the same cheese strategy like 4 pool or 5 pool, with standard hard counters, then you set yourself up to lose every game. Zergling rushes are sound, but not as your only opening.

If your bot has strategy learning, then I think it deserves at least one cheese opening to punish weak or greedy opponents. Zergling rushes are only one possibility—they are vanilla cheese, if the metaphor doesn’t make you gag. Tomorrow: More cheesy goodness. Cheese is great, cheese is good, and we thank it as our food.

Funny picture: Until just before this screenshot of a game between Igor Lacik's bot and Overkill, both sides were mining from this base. As you can see, terran ended up winning it... with a displaced command center.

Zia was reuploaded today. Its new description says “It has memory, and is trying to play like people do.” It sounds like it can now choose among its strategies as I hoped. It will take a lot of games to see how well it works....

What do y’all think I should write about?

I don’t have any shortage of material. I have 3 posts in my reserve, already written and pretty much ready to go, plus a to-do list of ideas, including a couple that I’m eager to get to.

But I think it’s time to pause and see what everybody else wants. I’ve been running down my own road, and maybe you think there are other cool avenues.

Is there a burning topic I’ve ignored? An idea I’ve mentioned that I should go into more detail about? Is there something in AI that you don’t know how to get started with? I may not know how either, but I can find out. Maybe a deep dig into this, or a wide survey over that? What do you say?

Post a comment or drop me e-mail. I’ll give feedback a few days to accumulate before I go once more into the breech.

Here’s what I learned in analyzing Skynet.

Skynet’s skills come across to me as first drafts of what you’d really want to implement. In looking at each one, it’s easy to see points that could be improved and shortcuts that were taken to get it working more easily. On the other hand, Skynet has a lot of different skills; the shortcuts paid off in time saved.

In other words, Andrew Smith put priority on breadth of skills rather than depth of skills. And it’s hard to argue with his choice, because Skynet is a great success, still a strong and interesting bot though its last update was in 2013.

I think it’s a key point. In a lot of posts I point out, “a better way to do X would be....” But you should only care if X is a weak point in your bot. It is better to play adequately in all respects than to play well in some and poorly in others. You want to minimize your worst weaknesses.

If you’re perfect at choosing the right unit mix to counter your opponent but your micro sucks, you lose. If you’re perfect at micro but you choose a stupid unit mix, you lose. Better to be fair-to-middling at both. Breadth of skills first.

You may be able to lift code from Skynet for your own bot, if you don’t mind being infected by its GPL license. You’ll probably have to do a bit of adapting to fit it into your own framework, but the code has clear interfaces and the important working parts seem mostly independent of the rest of the program. Once you’ve seen an idea it shouldn’t be too hard to reimplement it, either.

Skynet tries to avoid some area-of-effect spells and splash damage from some attacks. This is the fanciest skill that I’m writing up.

You can only avoid stuff that you can see coming. Skynet tracks threats in class AOEThreatTracker (where AOE stands for Area Of Effect), which creates and stores AOEThreat objects. Here is the key code from AOEThreatTracker::update(), which is called once per frame from the main onFrame() in Skynet.cpp:

	for each(Unit unit in UnitTracker::Instance().selectAllEnemy())
	{
		const BWAPI::UnitType &type = unit->getType();
		if((type == BWAPI::UnitTypes::Protoss_Scarab || type == BWAPI::UnitTypes::Terran_Vulture_Spider_Mine) && mUnitThreats.count(unit) == 0)
		{
			AOEThreat newThreat = AOEThreat(new AOEThreatClass(unit));
			mAllThreats.insert(newThreat);
			mUnitThreats[unit] = newThreat;
		}
	}

	for each(BWAPI::Bullet* bullet in BWAPI::Broodwar->getBullets())
	{
		const BWAPI::BulletType &type = bullet->getType();
		if((type == BWAPI::BulletTypes::Psionic_Storm || type == BWAPI::BulletTypes::EMP_Missile) && mBulletThreats.count(bullet) == 0)
		{
			AOEThreat newThreat = AOEThreat(new AOEThreatClass(bullet));
			mAllThreats.insert(newThreat);
			mBulletThreats[bullet] = newThreat;
		}
	}

Skynet recognizes enemy reaver scarabs and spider mines as splash damage threats. (A bot that might lay mines of its own should also recognize its own spider mines as threats. Skynet does not use mind control.) It also recognizes psionic storm and EMP as area effect spells to try to dodge.

What does it do with the information it’s tracking? Here’s the public interface from AOEThreatTracker.h:

	void update();

	AOEThreat getClosestGroundThreat(const Position &pos) const;
	AOEThreat getClosestAirThreat(const Position &pos) const;
	AOEThreat getClosestEnergyThreat(const Position &pos) const;
	AOEThreat getClosestThreat(Unit unit) const;

	bool isTargetOfThreat(Unit unit) const;

Psionic storm is both an air threat and a ground threat. Scarabs and mines are ground threats. EMP is the only energy threat. But of the 5 informational methods, only getClosestThreat() and isTargetOfThreat() are used in the rest of the code; the other 3 get methods serve no purpose. getClosestThreat() takes a unit and considers whether it is an air or ground unit to find the closest threat. It counts EMP as a threat to spellcasters only, even though all protoss units will lose their shields to it. It’s a little inconsistent; corsairs count as spellcasters, but Skynet never researches disruption web.

The results of all this tracking work are used in only one place, in BasicUnitAction::update(), which is a micro action like the others we’ve seen in the last days. The BasicUnitAction of course has very low priority among micro actions, so if the unit under consideration is already doing something else (like dragging the mine that is the threat), then none of this happens.

	const bool isTargetOfThreat = AOEThreatTracker::Instance().isTargetOfThreat(mUnit);
	if(!isTargetOfThreat)
	{
		const AOEThreat &closestThreat = AOEThreatTracker::Instance().getClosestThreat(mUnit);
		if(closestThreat)
		{
			const int distanceToThreat = mUnit->getDistance(closestThreat->getPosition());
			if(distanceToThreat < closestThreat->getRadius()+32)
			{
				stayAtRange(mUnit, closestThreat->getPosition(), closestThreat->getRadius() + 64, distanceToThreat);
				return true;
			}
		}
	}

First it remembers whether the current unit mUnit is the target of the threat, for later use. The explicit target does not dodge the threat (sometimes it can’t). If the current unit is not the target, but it is within range of at least one threat, then it finds the closest threat and tries to get out of its range. stayAtRange() calculates a direction and moves that way. There’s no attempt to avoid multiple threats, which are likely for spider mines; Skynet is happy to flee one and run into another. Also, I notice that AOEThreatTracker keeps careful track of each threat radius, but this code ignores it and flees to a fixed radius. I assume that’s good enough? Anyway, this limitation may explain why Skynet does not try to dodge lurker spines, which affect a long narrow area.

If the current unit is the target, the unit stays put so that the other units around it know what to do to avoid the threat. currentTargetUnit is whatever the current unit is already shooting at. This is not best if under attack by a reaver scarab, but it does help nearby units know which way to flee.

	// If the target of a threat, dont do anything to cause it to move
	if(isTargetOfThreat)
	{
		if(currentTargetUnit)
			mUnit->attack(currentTargetUnit);
		else
			mUnit->stop();
		return true;
	}

Skynet has other interesting skills. See BlockedPathManager and MineBlockingMineralTask, for example. But that’s enough for now.

Tomorrow: Wrapup and lessons learned.