Starcraft AI blog

PerfectBot 1.0, which deploys every processor cycle optimally to play the best possible Brood War, is scheduled for release at the end of time. I doubt it will be later. How will PerfectBot figure out its enemy’s opening plan?

Saa, who knows? But we can guess part of it.

Needless to say, PerfectBot picks up on more cues than bots today. A few possibilities:

• direct cues
  • what is the map? (different strategies will be good)
  • what are the respective base positions?
  • what buildings did we see? (tech, production, expansion...)
  • what units did we see?
  • what minerals has the enemy mined?
  • does the enemy have gas? still mining?
  • what information did the enemy collect about what I’m doing?
• effort cues (how much should we have seen?)
  • where and when and how long did we scout?
  • could there be unfound hidden buildings?
  • do we have units forward to put pressure on or to see the enemy moving out?
• behavior cues (what is the enemy army doing?)
  • when did the enemy scout?
  • are the first enemy units hanging back or out on the map?
  • what goals does the enemy building placement support? (e.g. a wall-in is better for some strategies than others)
  • is the enemy trying extra hard to prevent scouting?

PerfectBot does at least two kinds of inference. First, it figures out what is physically possible under the rules of the game. “Mutalisks can be out at time t, not earlier.” Second, it recognizes cues associated with strong strategies. By combining the two, PerfectBot can narrow down the situation accurately.

How do strategy cues work? The enemy has three choices about the message it sends with every visible action it takes:

1. play a straight move that supports the chosen strategy
2. pay a strategic cost to take a deceptive action
3. play badly with disadvantage

Straight moves tend to be strategy cues, but they also make your strategy effective. Bad moves can be ignored in strategy inference; in theory they only decrease the hazard that PerfectBot faces in the range of possible futures.

Deceptive moves come with a more difficult theory. Think of a deceptive move as a move to confuse the opponent: A move that looks strong for a different strategy than you are playing (researching air weapons to look like dragoon range while you prepare a reaver drop), or that goes above and beyond to hide information (blocking the ramp with drones to keep the scout out). First, a deceptive move always incurs a cost, meaning that it makes the strategy in some way less likely to succeed. If it had no cost, it would be a straight move that happened to give little information away. Second, the payback for the cost of deception does not occur in the game in which you play a deceptive move (not against an opponent as smart as PerfectBot). The theory is related to the theory of bluffing in poker: Game theory says you should bluff a certain amount of the time, varying by situation, and the payback for bluffing is the opponent’s higher uncertainty all the time. PerfectBot knows its opponent may be pulling a trick, and (since it’s perfect) it knows what the available tricks are, but it still has to prepare for a wider range of future events (could be dragoons, could be reaver drop).

Based on the combination of cues and analysis of possibilities, PerfectBot can do something like assign probabilities to future events (“overlords hanging around outside my base, high chance of slowdrop around time t”) and play to maximize its odds of winning.

You can’t deceive today’s bots because they’re not smart enough to take the bait. So first we should concentrate on the strategy cues of straight moves: If you know what the good strategies are and how to play them, you can find the straight cues. Knowing the good strategies, for example with a database of builds like LetaBot’s, is a strong start.

Instead of relying on human knowledge of good strategy, we could try to compute good strategies with a search through strategy space. I imagine that’s how PerfectBot gets its knowledge. I’ll write about that tomorrow—it’s easy enough that I can imagine trying it this year.

I’m also looking forward to ideas for combining physics knowledge of what’s possible with cues. If the opponent is going mutas, when will they come out? (Ever notice experts building turrets literally at the last second?) Maybe try a build order search along the lines of UAlbertaBot’s BOSS, but applied to the opponent.

High level theory like this is super vague but I hope it’s helpful for thinking about concrete ideas so that tomorrow’s bots can become smart enough to be tricked.