<
>

Infinite APM? Artosis on DeepMind and StarCraft - Part 2

Provided by Adela Sznajder/DreamHack

As I mentioned in my previous article, both speed and attention are extremely valuable resources in StarCraft. With an unlimited supply of speed and attention, I think that it would be possible to make an AI that would never lose to a human; the very fundamentals that the game's balance are built upon would be broken.

For this article, just like in the last one, I'm going to pretend that the other half of this equation, the problems of choosing the AI's speed and attention resources, are already solved. With this problem out of the way, I'm pretty certain that we will not get an unbeatable AI.

An AI has a lot going for it. Professional gamers have a timer in their head that lets them know what's possible within the game based on the information that they have or assume. For instance, if you decide to go for an early mass-Zergling rush against a professional, they will almost never be surprised at how many Zerglings you have. A professional, while they will not necessarily always be ready for anything, will know what is possible to have off of the bases that you have or they think you have at the time.

An AI steps this up a level. After scouting it's opponent's base, like a human, the AI will take a count of buildings, units and mining workers. What the AI will do above is what the player does: instantly calculate when your miners were on and off of the minerals, and keep track of your continued expected income. It will also know the instant that any building finishes, and re-adjust all timings of possible units, techs and economy each and every time it scouts. This is not too far off of what an experienced pro gamer is capable of, but it is certainly more precise.

We can even take this aspect of the AI a bit further. The AI should be able to keep track of every unit that dies in every battle throughout the game, consistently updating a count on how much you have spent and how much you have left to work with. The moment anything goes over its maximum expectation, even by a few minerals, the AI should be able to deduce that you took an additional base and begin reacting with that in mind as well. Each time any units appear on its screen, the AI will have near-exact supply counts in certain areas, accounting for almost exactly what is missing. It could know the speed of each unit and how quickly those units can get into other areas. Of course, professional gamers do all of these things as best they can (which, believe me, is surprisingly accurate), but the AI should have a leg up in these areas.

There have been programs out for years that can calculate the fastest way to get into a tech or unit, and of course by watching replays of top pros, the build orders should be easy enough to come by. So the AI should be able to hit any build order with absolute precision and speed. The pro gamer won't be able to come out ahead in this area.

After my first article, and even up to this point, it's kind of been all doom-and-gloom, showing ways in which the AI is extremely scary ... but this is where it's time to turn it back around. There are some things that are going to be very, very hard for an AI to deal with.

Mind Games

There are mind games played constantly between high-level opponents.

Imagine you are Terran and your opponent is Protoss. You scout and see both a Robotics Facility and a Templar Archives building. Your SCV dies. Instantly you think: Dark Templar drop! But here is where you have to be careful. Your opponent knows that you scouted his tech rush. He has just as many options as you do here. Do you immediately put down three Turrets to guard your base against Shuttles and the Cloaked Dark Templars? If you do, that's 125 Minerals for an Engineering Bay plus three Turrets at 75 Minerals each -- 350 Minerals total. Some lost mining time as well. Oh yeah, also, if you spend all of those minerals right now on defensive structures, then your next two Factories will be slower, which means you will have slightly fewer units for each moment going forward compared to a game in which you didn't get the Engineering Bay and Turrets. Let's break it down a little more simply:

Option One: Do nothing about the tech you saw building.

- If your opponent canceled the Dark Templar Drop after your scouted it, you are now ahead! Congrats!

- If your opponent continued with the Dark Templar Drop after you scouted it, you are now dead! Oops!

Option Two: Build the Engineering Bay and three Missile Turrets.

- If your opponent canceled the Dark Templar Drop and just went into Macro-based play, you are going to be a bit behind and find it hard to be as forceful when you need to be on the map.

- If your opponent continued with the Dark Templar Drop, you take no damage and are now ahead.

This is the most simple, binary way that I can write out what this tiny part of the early game could look like. At the professional level, it's never going to look exactly like this. A professional can't really make the call that his opponent will cancel the Templar Archives, because if he's wrong, he will lose. More likely, the Terran will have to decide what he can get away with.

Is the Protoss going to make the Shuttle to drop the DTs in my base? If so, can I get a Wraith to push it away so that it can't drop directly into my main (forcing the DTs into one area, which would use just one Turret)? Where will he drop the DTs when the shuttle gets to my base? Will he drop them on the edge of my base? If so, can I lay enough Spider Mines between there and my important buildings to fend them off without dedicated detection? How quick is my opponent with his micro? Will I have enough Vultures that I can get a Comsat and kill a DT with one scan and one volley before he picks it back up? What's my base layout look like? Can I use a combination of one Turret and Spider Mines to force the DT where I need it to go to kill it? How heavily will he micro this DT? Can I cause damage to him while he's trying to hurt me with this drop, forcing him to look away so that I can easily clean up the harassment?

The answers to these questions come from lots of places. The current Metagame. Previous games against this opponent. Previous games seen from this opponent in similar situations. Tendencies you've already seen in the game of this opponent -- such as micro style and attention given to various things that have already happened in this game or this series.

There are also times where randomizing in-game information is important. For instance, let's imagine again that we are inside a Terran vs Protoss game. Terran has gone for a fast Factory, as is the norm, but Protoss has a Probe inside of his base, trying to see what comes next. It takes a while to hunt down the wily Probe, and this is a moment where you must consider using mind games and randomization to get an edge on your opponent.

After building the Factory, in a perfect Terran build order, you have some options regarding your Vespene Gas income. If you want to go for a quick Command Center, you will take two SCVs off of your gas and put them back on your minerals; you don't need the extra gas, and this will help with building the Command Center quickly. If you want to go for a 2-Factory rush or a fast Starport, you will keep your SCVs on.

The time for this decision will coincide with the Probe being alive in your base. It's important for both sides to consider the options here. If you keep your SCVs on gas until the Probe dies, your build order and economy will be worse off if you are going for the fast Command Center build, but your opponent will have to consider the possibility of a strong early-game push or fast tech. If you decide to take your SCVs off of gas, but are planning on going for faster tech or a second Factory, this will all be delayed, but your opponent will more likely discount these options. The consideration of whether or not to randomize versus the strength of more perfectly aligned build orders is important.

""Even if it has studied all of the many strategies I've used, I'll go at it with an unstoppable strategy I've prepared.""

Lim "BoxeR" Yo Hwan

A huge part of professional StarCraft is knowing your opponent and using that knowledge in the right way. How much you use that knowledge is a mind game in itself. It's important as a professional to be aware of your perceived image. What does your opponent know about you? What games has he seen recently? What games hasn't he seen recently? What range of strategies is he putting you on this game? Where does he think you are weak? What does he fear from your play? Every piece of information can be put to use, whether it's something you know about him, or he knows about you.

Now, I'd imagine that an AI would play with full force against all opponents, not taking into consideration a lot of what I've said here. This actually can be very smart. For instance, if there is someone who you fear or respect, it is often smarter to skip out on mind games and just play your best, most direct strategies. Playing too many mind games is worse than not mind gaming at all. If you go too deep, if you get too fancy, you will have sabotaged yourself.

StarCraft isn't a best-of-1 game. Hiding nothing sometimes is important. Hiding lots sometimes is important. Being aware of your perceived image is important. Would the AI figure out that it needs to randomize tons of factors in order to beat a professional over the long term? You can't hide who you are in StarCraft -- you can only hope to use your opponent's knowledge of who you are against him.

I think this is a good place to bring up the super-confident statement made by The Emperor of Terran himself, BoxeR ( 임요환 Lim Yo Hwan): "Even if it has studied all of the many strategies I've used, I'll go at it with an unstoppable strategy I've prepared."

As soon as I saw this quote, I knew exactly what he meant. There will be some flaw within the AI. Everything you do in StarCraft has a cost, somewhere you have to cut a corner. With enough games under his belt, BoxeR, or any other extremely experienced pro gamer, would find where the AI would be "cutting" these corners. I'm going to illustrate how to find a hole in the AI's play. There will be patterns, and patterns are dangerous in StarCraft.

Please know that this is probably the most basic example I can give, and there are countless others throughout the game.

Let's just stay with Terran vs Protoss here. BoxeR doesn't wall-in at his ramp, allowing the scouting Protoss Probe to get into his base. The Probe goes straight to BoxeR's Command Center to take count of how many SCVs are there and how many Minerals have been mined. Let's say that the Probe discovers the SCV count is lower than expected, and it didn't see enough buildings to account for the Minerals it sees mined.

Where will this Probe go next? Does it scout around the base looking for buildings that would explain these missing Minerals? If so, it is losing time scouting more mischievous places outside the main base. If not, then it might assume that there is a threat to its early-game safety when, in fact, there is not. You cannot scout everywhere on the map. There is absolutely a point of lost returns on scouting. Any professional can create a heat map for you in a matter of seconds, detailing where the likely hiding spots are, but simply knowing these hot spots allows the pros to play around them, which allows counter-play by the opponent.

Again, there is a point of lost returns on scouting. BoxeR will be able to hide things. Or even hide nothing. There is no way for the AI to know if BoxeR has just decided to not spend Minerals on time. He could have 500 Minerals missing in the form of buildings that the AI cannot find, but will then look for. By making his build order slightly worse (for instance, building the Command Center when he has 500 mMnerals instead of 400), or by making additional SCVs and hiding them on an unscouted edge of his base, the AI will have trouble filling in the puzzle of what's going on. There will be holes, and a smart professional will find them.

With the multitude of tricks at the disposal of a top professional, the AI could be forced to play a middle-of-the-road build as a "cover-all", (which, of course, is a super-weak strategy), or the AI could be forced to take a risk somewhere. That super-weak strategy or that risk is where the professional will strike.

BoxeR, currently a professional poker player, is the perfect place to segue into the next unsolvable problem for an AI:

Percentage Plays

This is the second part of why BoxeR is so sure that he could take on an AI. Like poker, there are percentage-based plays in StarCraft. You can choose to take a risk so drastic that the game is nearly out of everyone's hands. Let me give you a perfect example:

Once upon a time, many years ago, there was a match between two of the top Non-Korean Professional StarCraft players: Steven "Smuft" King and Nick "Testie" Perentesis. Both were playing Protoss in this match, and the percentage play in question came from Smuft on the map Tau Cross. Tau Cross is a three-player map, meaning one of the main bases was empty. In this PvP matchup, Smuft sent out an early Probe and blindly chose another main base. Without scouting, he made two proxy Gateways. Testie happened to be there, and promptly died to the ensuing Zealot rush.

Now this is something that not one person thought of before the match or even the tournament. It's a super risky play, so much so that it's probably not even a good strategy to use. In fact, it's basically a one-use-only strategy. Once you use the build, it will be on everyone's radar for the foreseeable future, so you can't even be caught practicing such a thing. To take a look at the percentage of it working is really simple. Fifty percent chance you choose the correct main base. If it's not your opponent's base, let's put your win percentage at less than 1 against an equally skilled player. If it is the right base, you should be beating your opponent almost 100 percent of the time. Your equally skilled opponent cannot even count this build as viable, because to do so would set him in such a defensive posture that he would already be at a large disadvantage going into the mid-game. The strategy is basically a coin flip.

Despite the fact that the original StarCraft has been played professionally for 17 years, there are still one-time strategies that haven't been seen. How do you respond to a one-time strategy that has never been seen? Well, if it's prepared correctly, you probably just lose to it.

In Closing

I think this article might be more about how hard and complex it will be to make an AI that can win at StarCraft, rather than if it can happen. Obviously, over a long enough time period, AIs will surpass humans. I would love to see what an AI can do in StarCraft. If DeepMind could end up beating a professional SC pro, it'd be about as cool as I can imagine. Interesting, fun, awesome to watch ... but not in the same interesting, fun and awesome-to-watch ways that are why I love StarCraft.

I've been quoted in the past saying that StarCraft is as much art as it is science. StarCraft was built to be played by imperfect humans, and it is their very imperfections that give us the true beauty within the games. That struggle of fighting against yourself, against the game, against your opponent, and playing with your heart on the line, giving your all and expressing yourself with every action. That's what StarCraft is. There's something very genuine and relatable watching humans play StarCraft ... something I'm not sure an AI will ever replicate.