Starcraft, the next AI frontier. An introduction for non-players.

Starcraft II is a strategy game that is currently getting attention from AI developers as the next toy challenge to solve after having beaten the best humans at both Chess and Go.  The purpose of this post is to serve as an introduction to Starcraft II for people who do not play but who may be interested in finding out why AI developers have set their sights on it.  A secondary goal is to communicate some of my love for the game.

Starcraft II is hard.  It has even been called the hardest game.  I don't know if this is true, but it is at least plausible.  It is perhaps like playing 2 games of speed chess simultaneously while juggling balls and not being able to see most of your opponent's pieces.  That's a poor analogy, but Starcraft is both mentally and physically demanding beyond what even the best players can offer.

For the rest of the post I will just refer to the game as Starcraft, though I am always referring to Starcraft II.  Much of what is said here is also applicable to the original (which is still played) and AI researchers are also working on that, though I believe the larger resources such as Google Deep Mind are directed towards II.

The basic premise is that you play as one of three factions, and your opponent also plays as one of them (possibly the same one), and you must build an army and destroy your opponent's base and prevent your own base from being destroyed.  Starcraft is a real-time game, which means there are not turns during which the player has time to think.  Units and buildings either do nothing or continue executing their last command until they are given a new one.  The gameplay is extremely hectic for even the fastest players, to the point that it is not possible to do all of the things one wishes to do and it becomes necessary to prioritize and triage.

Here are some of the challenges that an AI must comprehend and overcome to play Starcraft.

1. Assymetric factions.  Each of the three factions is fundamentally different from the other two.  Learning to play one is of only moderate help in learning to play or play against another.
2. Now vs Future.  There are multiple ways in which a player can invest for their play to be stronger in the future in exchange for it being weaker now.  Investing somewhat more than your opponent will give you an advantage but over-investing will leave you vulnerable in the near-term.
• Economy and production capacity vs army.
• Tech vs army.
• Upgrades vs army.
3. Incomplete information.  Unlike Chess or Go, you cannot see your opponent's pieces by default.  They can be scouted but this requires sending a unit of your own to go look at a location (or some other method of scouting).  
• This adds secrets, intel, spying, deception, and the setting of traps to the game.
• Information gaps can be filled with inference, process of elimination, assumptions based on knowledge of the opponent as a player, or assumptions based on knowledge of commonly used tactics among the current population of players (known as "the meta").
• Playing in a manner that your opponent does not expect and does not correctly recognize in time can result in a decisive victory, even over a superior opponent.
• Because of all of this high-level play includes information wars in which each is trying to see what the other is doing and deny their opponent from seeing or provide their opponent with false information.
• Questions you might ask in game: Where are your opponent's bases?  How strong is their economy?  Where is their army?  Is it in only one location?  What unit types are in it and in what quantities?  How will your own army perform against this composition? What level of upgrades has your opponent achieved?  Do they intend to attack soon?  Where?  What are their tech and army intentions for the near future?  What is their long-term plan?  What does your opponent know about your own position?
• Dealing with the unknown inherently adds elements of risk management.
4. Unit interactions. There are many different units that fulfill different roles and are strong or weak against other units.  Units may be cloaked or not, flying or ground, ranged or melee, slow or fast or somewhere in between.  They may be transports or support units, they may or may not be able to see cloaked things.  They may attack air, or ground, or both, or sometimes neither.  There is rock, paper, scissors.  There is rock, paper, scissors, lizard, Spock.  And there is Starcraft.
5. Combined arms.  Compositions of multiple unit types supporting each other will be able to shore up each other's weaknesses or have particular synergies.  Composition interactions become another level of unit interactions.  There are only a few strategies that can be successful with a single unit type and they generally seek to end the game early before the opponent can develop a superior composition.
6. Unit abilities.  Some units have unorthodox movement like tunneling underground or teleporting. Some may provide cloaking or teleportation to other units.  Some may slow or deny enemy troop movement.  Some may take control of or move enemy units, or place them in stasis.  There are many forms of area-of-effect damage that can be used to make it undesirable for enemy units to remain in a location or otherwise impact their optimal control. Or just kill them. 
7. Timing.  There are plenty of situations where a strategy is strong against another strategy during a specific limited window, but not before or after that.  Identifying possible windows of opponent vulnerability is part of the game.  Generally this is about attacking as your investments are paying off but before theirs have.
8. Map vision.  The ability to detect enemy troop or scout movements and base activity is important.  This is generally done by placing or moving scouting units so as to cover strategic locations.  Removing enemy scouting units from the map denies them vision and information.  Good scouting locations can become a contested resource in their own right.
9. Territory control.  There are resources on the map that must be utilized, as well as paths that either must be or are convenient to use to attack or spy upon your opponent.  Controlling areas of the map can deny your opponent access to these resources or avenues.
10. Terrain.  There are cliffs and ramps, high and low ground, dead space and space that can only be flown over.  These impact unit movement and combat as well as unit vision.  A siege weapon on a cliff can shell melee units with little worry, but a siege weapon being flanked from 3 sides by melee units is dead.  
11. Detailed control (known as "micro", as in micro-manage). Units that have been given basic commands like "go attack there" will do a reasonable job, but a player can often can get more out of their army by controlling it more manually.  Some units are powerful when controlled manually and useless when they are not.  In some cases micro-managing a fight is known to be the only way to win it, in which case the player cannot engage that fight until/unless they are capable of devoting significant attention to controlling it manually.
12. Limited actions.  Pro Starcraft players are quite fast, sometimes getting up to speeds of 6 or 7 commands per second.  The AIs will be artificially limited to a rate of commands that is within human range so that they are not winning through brute force.
13. Limited attention.  Human players must divide their mental attention and their vision.  The battelfield is a big place and the player can only be looking at one location at a time (though there is also a mini-map).  They might be managing their economy and also managing 2 or 3 battles at the same time, rapidly switching their camera from one location to another and issuing commands where needed.   A common and very effective tactic is to draw the player's attention to one location so that an attack in another location can do more damage before they notice and correctly respond.  The AIs will have a limit to the number of times they can switch their view so that they are not winning through brute force awareness of everything that could theoretically be seen. 
14. Space for creativity.  There are a number of situations where units can and have been used in unusual ways to great effect.  The game and the interaction of all of its moving parts are complex enough to allow for this.  There are also meta shifts that occur as players discover new strategies that become dominant and then are later replaced by other discoveries.
15. Search space is effectively infinite.  Unlike Chess or Go where the number of possible moves right now is discrete, the possible actions that could be taken in a game of Starcraft is not going to be calculable.  There are too many things with too many possible actions on too large of a map that is not a discrete space until the level of pixels, and there are too many unknowns.  A computer cannot brute force this problem.  It must develop an understanding of the game, whatever that means.
16. Target choice.  One can attack the opponent's economy, army, tech buildings, production facilities, scouts or other small squads.  Which target(s) should you hit?  How should you divide your forces if you have chosen multiple goals?  How will you defend while your army is elsewhere?  Or will you?  Will you commit to these fights or hit and run?
17. Your opponent always has options for counter-play.  The game is designed so that there is no strategy that always wins.  If one arises the game is re-tuned so that it becomes beatable again.  It's hard to talk about optimal play without the context of a particular game.  And a superior player can often overcome a superior strategy.
18. Identifying where you have "edges" or advantages over your opponent and exploiting them to get further ahead in the game.

There are also a few areas where I think the AIs will have clear advantages over humans.

1. They will not become flustered or lose mental track of their priorities when under extreme pressure.
2. They will have access to perfect "mouse accuracy".
3. They will not make mistakes of execution, only mistakes in decision making.
4. "Macro", which is what players call the tasks of successfully developing an economy, matching that economy to production, and effectively translating those resources into an army or other advantages is a strong component of play. Computers are likely to be pretty good at this.  Human shortfalls in this area tend to be of either having a poor plan or executing that plan poorly.
5. The AI will be able to think very rapidly about novel situations in addition to relying upon cached solutions.  Humans can to some extent respond to novelty in-game but it is often in the post game analysis when they decide how they will respond to this situation better next time.  There just isn't enough time to really think things through in the heat of it.  Not for a human anyway.  Mostly we rely upon intuition, heuristics, cached answers, and a limited amount of thinking on the fly.
6. Reaction-time.

I may yet have missed some things.  It is a pretty involved game.  Overall I think it is going to be very interesting to see how machine intelligence develops in this domain.  The challenges AI faces are all in the realm of understanding and decision making, which is the most interesting part of the game to me. AlphaGo came up with some novel strategies for the game of Go.  I wonder what AI will bring to Starcraft?

And if any of this interests you, Starcraft II is going free-to-play soon.  I believe on Nov 14th, 2017.