To win at Starcraft, machines need to figure out how to lie | Hacker News Reader

To win at Starcraft, machines need to figure out how to lie

wsj.com

76 pointsjonbaer75 comments

I think the Starcraft pros tend to think about what separates top pros from mediocre pros. They see these things, like better 'mind games', as what makes Starcraft hard.

The thing is, a game needs to be very carefully balanced for these scissor/paper/rock dynamics to emerge. This type of balance is not the default --- it's the product of careful design, and empirical tuning.

In human vs AI, this balance will almost surely be broken. The AI will have perfect control, even with APM constraints. Its attention can be split between two attacks perfectly. It won't play at all like a human.

So, the resulting human vs AI gameplay is unlikely to be strategically deep. If the AI can learn to play Starcraft at all competently, it will probably crush. It will probably find a dominant strategy that it can re-execute exactly the same every time, which the human can't stop.

Making the AI work well for Starcraft will be very difficult. In Chess and Go the actions are discrete; in Starcraft the actions are all analog. But the gameplay requires much deeper search than the Atari games Deepmind learned in its early paper. So I think the game will be very difficult for the AI. But not for the reasons people are talking about.

Being able to have multiple battles at the same time is not terribly interesting, because humans can scale this as well. Team up two humans and they'll be able to do twice the work. Teaming two players to play a Go or a chess game against a computer wouldn't do that much good though.

I've recently read Ender's Game and there was an interesting idea in there. In the book it is hive queens controlling the Buggers fleet with exquisite control, yet Ender is able to exploit this as a weakness, as every human is a sentient being capable of thinking and acting independently, so as a commander he was only giving high-level orders to his lieutenants and they did the rest. Which is how humans have fought wars.

But that's not the case here, in most Starcraft tournaments it's 1v1. So it would be one 1 AI mounting serveral attacks at the same time against one humain player with the limitations it entails.

Things happened in Enders Game due to authorial fiat nothing more. https://m.youtube.com/watch?v=L4_zFYnnn2Y

Game designers spend a lot of effort in RTS game keeping the AI from crushing people. This showes up not just in the games AI but also unit mechanics. https://m.youtube.com/watch?v=mHbloVZ15Pc

Actually RTS AI is really bad and they almost all cheat to keep up with the player.

Having an AI that plays like a human is less fun. 'Cheating' is simply how developers can easily balance things.

EX: Often there are units capable of infinite harassment with perfect micro. That's so far from being fun it's never part of actual game AI.

Large base, small waves. It's a simple formula that makes people feel great!

PS: Of course it goes deeper, units need to have basic AI because people can't micro manage large numbers.

I know, but there are even competitions where people write RTS AIs that can do micro like that, and humans still often beat them. Some game developers have great lengths to make good RTS AI that plays fair and like a human, and they are still easy to beat for skilled players.

If you team up two humans, they need to be very well coordinated to work together effectively, otherwise they'll just get in each other's way.

Starcraft 2 has a mode like this called Archon Mode, where two players control the same units. The conflicts that can arise from this can be pretty fun to witness.

It appears the starcraft developers had the same conversation we are having here.

A similar mode was present in the original Starcraft, albeit without the cool name. (It was simply called "team melee".)

No, it's a completely different thing. In Archon Mode, two physical players share control of a single in-game player. A lot more coordination is required or they'll both be giving counter-orders most of the time.

It's been a long time since I played team melee, and I've never played Starcraft 2 multiplayer, but reading back, I'm pretty sure they're the exact same thing:

http://starcraft.wikia.com/wiki/Team_Melee

http://starcraft.wikia.com/wiki/Archon_Mode

https://www.reddit.com/r/starcraft/comments/314e28/archon_mo...

> I've recently read Ender's Game and there was an interesting idea in there. In the book it is hive queens controlling the Buggers fleet with exquisite control, yet Ender is able to exploit this as a weakness, as every human is a sentient being capable of thinking and acting independently, so as a commander he was only giving high-level orders to his lieutenants and they did the rest. Which is how humans have fought wars.

I've read enough about real-world military strategy on Quora to know that this is nonsense. The amount of national resources that go into command and control networks is immense, these networks play a huge role in making our military unassailable. Something like the Bugger hive queens would be practically impossible to deal with in any real way, deception would be impossible to rely on.

Deception is critical in an invasion, defenders have the advantage of knowing the terrain. If you could rely on a sensor network to reliably and instantaneously tell you where all the threats are, then you could simply rely on mobile forces to go wherever they're needed. Unless the attackers have an overwhelming numerical advantage, they won't be able to break through.

D-Day would not have been feasible without the ability to deceive the Germans as to which beaches they were going to land the troops, a lot of time and effort went into planning that deception.

Humans only stood a chance against the buggers due to their overwhelming weaponry, which will trump tactics and strategy every time. No way with that kind of weaponry would it even be a fair fight, any mildly competent general could have won with that advantage. The defensive response to overwhelming conventional superiority is guerrilla warfare, not trying to stand and fight toe-to-toe with nukes.

Felt like a bit of a cop-out to me, authors should be required to spend some time on Quora verifying their basic assumptions, it would make for much better stories. Naturally Card didn't have access to it, and I still enjoyed the book. But it could have been much much better.

.... Quora being known the world over as an elite military strategy academy, of course.

I ignored Quora for a long time, but once I took a look at it, it quickly became a valued part of my life. I've been on lots of Internet fora over the years, Quora really nails the problem of signal-noise ratio you typically get with forums, even HN isn't immune.

I've learned more about the real world around us from Quora than I have from almost every other source. Only Stratfor rivals it, and that's only in the realm of geopolitics.

Of course, you'd learn more at an actual military academy about strategy, but Quora does the work of getting the people that already went to those academies to boil down everything they learned into short, readable essays.

In fact, I'm finding that I'm reading fewer long-form journalism articles and blogs because I find Quora so compelling. Those were my previous bar-none best source for information.

Nothing beats curated long-form journalism for variety, but there's still a lot of noise and the work of separating it out is onerous enough and Quora is easy enough that I've already subconsciously switched, not bothering to maintain my RSS workflows. If I want some variety, I'll fire up Feedly or Pocket and pull out a few articles, but generally I'm looking to iterate on my high-level model of how the world works, geopolitical analysis from Stratfor and watching smart people answer stupid questions at Quora is the best bang-for-the-buck I've encountered for that. HN is the best place for business-specific information, if it weren't for that I'd have moved on a long time ago, I've been so far unable to find a good vein to mine for business on Quora, though it's half-decent with finance, though HN still beats Quora there too.

Nitpicking but in SC2, or any video games, actions aren't analog.

A unit's position is a function of 3 _probably_ 32bits numbers, giving 2^96 discrete positions.

You can get that number much higher probably, by adding other factors like current speed, orientation, etc.

You're right though that you have to tackle the problem differently, because while you'll be able to try to define a strategy in go by iterating over a bunch of discrete possibilities in the 19x19 grid, there is no way you can do that for a 2^hundreds size grid with current tech.

I guess AlphaGo is in for a few semesters on strange attractors!

How would strange attractors assist?

Making the AI work well for Starcraft will be very difficult. In Chess and Go the actions are discrete; in Starcraft the actions are all analog.

With Starcraft, you can throw sheer processing power at strategic decisions. If you're able to fast-simulate gameplay, even just on the order 10's of thousands of possibilities a second would give you a decent feel for overall strategic decisions. Sure, some nonlinearity might throw a result off by a huge factor, and you wouldn't have searched that. The opponent, human or AI, is faced with the same challenge, though. In the end, no one can predict the future because of chaotic nonlinearities. The best we can do is best account for the odds.

To go deeper, the challenge of balance begin from the most basic decision in Starcraft.

Starcraft has three races and random. At top pro levels, picking random is unheard of and actually extremely difficult to play against because it complicates your very early decisions.

Im also interested in who would be picked to play against DeepCraft. Flash would be incredible but he's retired. I'm curious which top level talent will be left by the time the bot is ready to play

A wild idea would be to get a couple of top level talent together and let them play against DeepCraft for the first time, at the same time.

TaekBangLeeSsang vs DeepCraft. I'd watch the hell out of that.

http://wiki.teamliquid.net/starcraft/TaekBangLeeSsang

Flash is playing Broodwar and this is about Broodwar, not Starcraft 2. I still agree that the level of competition will be even lower by the time a proper bot will be ready (which will take a lot of years).

I could have sworn I saw an earlier source where Hassabis said it would be SC2, not SC1.

As an aside, the "best player in the world" referred to in the article is the SC2 player SoS. I think Zest is pretty commonly viewed as best in the world right now, even if he loses the current GSL. They mentioned SoS because... he won blizzcon?!

Then again, a bot that could play SoS would be truly marvelous

The article is a mess anyway since they are mixing both games up. They start talking about the franchise, then go on to Starcraft 2 and afterwards to Broodwar.

I can't fully agree here. I do agree a working ai will crush human players. But the challenge lies in that the entire state is not known. The opponent is hidden by fog, and unlike chess and go, things happen around around the map while you are not watching, i.e. You have to remember things like putting workers into the gases you built earlier, and pull them out if an all in is coming. The challenge lies in making the computer comprehend such decisions. Otherwise i think it will be hard to play a game of imperfect information at super human levels.

Or it might find a new strategy that is totally imbalanced and unbeatable

Actually I think the imperfect information favors the machine. It's much easier to for an AI than human to control 10 scouting units and gain more information while doing everything else in the game.

  The challenge lies in making the computer comprehend such decisions.

Does comprehending the decision go beyond: see x units / specific setup > need y units to counter > need z resources > switch to z resources.

Early game you cant afford 10 scouts.

I think the difficulty of interpreting the information and the act of information gathering itself as a basis for planning and decision making is hard.

The Spring RTS had lots of open AI development because of its open nature (maybe it still has). You could just pick various AI:s for different players and have them play against each other etc...

After a certain points they got really annoying to play against - it was always doing small scale harassment and evading with a perfect equation so you couldn't really ever catch it (unless you had much faster units). Besides actions per minute constraints, to be playable the AI at least should have some kind of reaction delay like humans have.

I think this sort of thing will improve once AIs are trained using the human's enjoyment of the game as the primary utility function. This could be as simple as asking users to rate the preceding game at its conclusion.

It could be as subtle as using the player's apm or other activity metrics as a proxy for enjoyment, if correlations were shown in play testing labs. This could allow for more training data, and less annoyance to users, who might be reluctant to provide manual ratings.

The next step after that is adaptive AI, where the computer learns what you find enjoyable personally.

I give it ten years before this is how every game works.

Edit: Google has said that negative signals are extremely important to its search. A user bypassing the #1 result for the #2 is hugely bad for #1, but only a mild boost for #2. Similarly, perhaps minimizing "ragequit"s is a valid objective!

I wonder if it'd matter if the computer had both a max APM, and a requirement that its actions can only be in a field of view at one time, and that it can only change the field of view a certain number of times per minute. This would better simulate the constraints a human faces.

You might think that's unfair to the computer, but we're also not requiring the computer use a mouse and keyboard, so we're actually giving it an advantage. I mean, if Starcraft were programmed such that I could control every unit with my mind instantaneously, I'd also do better than a human trying to toggle through hotkeys and micro with the constraints of a mouse/keyboard interface.

Just make the UI use a PC like a real player. It should look at the screen like everyone else.

What people miss is that StarCraft is a physical game primarily, with tactical elements, not the other way around. There are a lot of fans who know the game well and can make all the right decisions, but will never be able to execute it in real time.

Execution of strategy is what separates the professional StarCraft players, and in that way it's much closer to professional sports than Go / Chess.

What if the pace of gameplay were slowed down 5x? Would execution still be an issue?

That is a really good question. I would love to see tournament players playing against each other and non-pros in a 5x slower or 10x slower game. Among the pros would be most interesting. Does everyone now play about equally well? Does some random barely pro destroy the field because that player has a better grasp on the strategy that was convoluted by the rapid aspect. If you compare to chess, good blitz players aren't always good at long games and vice versa. Computers are much better at fast blitz games (beating pros well before Kasparov in 1996). I expect that even if DeepCraft performs well in a full speed game a slower more strategic game would have the humans at an advantage (at least for a while).

This is like asking what basketball would be like if you weren't required to dribble. It might be interesting to think about, but would probably result in a different game.

This is like asking what basketball would be like if you weren't required to dribble.

Not really. The "physical" aspect of Starcraft is an information input/output feat. It's still arguably the same abstract game. Arguably, it's no longer a sport however. (And maybe it wouldn't be a "game" in the sense that basketball and football are "games" for people.)

Solving THAT game (where we get as close as possible to a brain -> machine interface and it becomes completely strategic) is interesting, but it's not StarCraft. Arguably it's the same abstract game, but when you bypass constraints (applicable only to humans), you probably should have targeted something else without those constraints in the first place. In our case, a turn-based strategy game that is equally complex and with limited information (Civilization?!).

I still play the original starcraft (broodwar) every week, and I'll have to agree with you.

once the AI is given micro mechanics and perfect execution, you just can't beat it: https://www.youtube.com/watch?v=dOIgFkyfStg

However, pros can still perform "cheese" tactics where they attack extremely early on, and the AI won't be able to properly defend because it needs cash to get an army. So if we do start to see deepmind eventually play starcraft, it will need lots of hand-holding and special programming to deter early cheese tactics.

I see you linked Berkely Overmind and said that its micro can't be beaten.

Don't you remember the Human VS AI matches that took place with Overmind right after the tournament that year?

Watch an amateur human tear through its mutalisks. https://youtu.be/hmXY_pkU2Wc?list=PL9F69781768E85502&t=591

The video just shows that the AI can perfect attack mechanics - it's still a simple AI. If deepmind was thrown at the game, it could learn to deceive/cheese/micro/drop and really do some serious damage.

I hope DeepCraft could do those things, since no other AI can at this point. And I hope it can do them better than any human. And I hope that DeepCraft can pivot its strategy on a dime when needed, in response to the human doing something. And I hope that it can do well against the myriad of play-styles that professionals have developed across the the three unique races.

My point is that DeepCraft is still gonna be quite a ways off, and is going to involve a lot more than just learning how to micro, cheese, drop, etc. (Which, by the way, would be quite a feat to even develop an AI that can learn these things since StarCraft has such a huge search space)

Having played Starcraft at a somewhat high level, I don't agree. The very best players will beat an inferior player without surprises, either just by knowing when to be aggressive and when to be defensive, with smart tactical plays, forcing an opponent into a position where they will be at a disadvantage later on, or sheer multi-tasking. What machines lack is sheer intuition.

For example, it is possible to chip away at your opponent's economy by loading units into a dropship and flying it into the back of your enemy's base. To increase your chances of doing damage, you should probably set up multiple of these at the same time, or attack the front while dropping, but you also need to know that a dropship works best when it's fully loaded (8 small units, 4 medium units or 2 large units) - if it's not fully loaded, part of your investment is wasted and your attack will be sub-optimal.

Learning this as an AI isn't going to be easy because there are lots of scenarios when you can do a drop like described above perfectly and it'll still lose you the game - maybe your opponent had some optimally placed anti-air defenses, or they were just getting ready for a huge all-out frontal attack just as you arrived, so their army is vastly superior.

Intuition can be simulated with algorithms and massive computing power.

It seems like most people in this thread are claiming that high APM and the ability to have perfect control over everything happening on the map will give the AI an advantage that will force a win.

Here is a video of one of the best current StarCraft bots losing to an D-rank (low skill) human player. The bot's APM is ~5500 while the human's is ~200. https://www.youtube.com/watch?v=ztNYOnx_YQo

The fact is, no AI has ever beaten even an amateur player in a tournament. Even with great micro, if your play is too predictable then the human will learn it and exploit it.

I, for one, am very excited to see the development of new StarCraft AIs. And especially SC2 AIs so that it can challenge the current world champions.

'Eugene Kim' should be Yoo-Jin Kim aka SoS.

> An advanced human player might, for example, feign weakness on one side of the playing field while mustering a pack of mutalisks—fire-breathing dragon-like creatures—on the other side of the board.

Fire-breathing? I must have not been paying attention...

http://eu.battle.net/sc2/en/game/unit/mutalisk

No fire-breathing : "Weapon: Glave Wurm"

I know. I was pointing out the... creative... journalism.

They missed a hyphen. Fire-breathing-dragon-like. I agree they are similar in some ways to fire breathing dragons.

> But some of the world’s biggest nerds are confident that machines will meet their Waterloo on the pixelated battlefields of the computer strategy game StarCraft.

Er .... sorry, but Waterloo was a decisive battle that lead to the dismissal of a pan european empire. I don't think we will see the end of the "machines" any time soon. A better comparison would have been Austerlitz (but then it isn't much celebrated in the Anglo-Saxon world).

The AI had better be able to interact using a mouse and keyboard. Any time I see the "AI wins!" headline, for anything real time, it was invariably given a superior interface. Watson getting a text file sent to it instead of having to read the screen or listen to Alex read the answer for example. If the machine isn't watching a monitor and forced to use the same input methods as the players, then sure it will "win," but it will be a cheat, not a triumph of AI.

Exactly. I think, in contrast to chess or go, Starcraft is not only a "mind game", but also requires physical agility and precision for command outputs. Those Starcraft top players all have had wrist injuries and so forth [1].

If the AIs were to become strong enough to compete against Starcraft players, they would have the unfair advantage of being able to give a lot more actions per second.

[1] https://www.reddit.com/r/starcraft/comments/16mkmg/injuries_...

You could limit the APM the AI can use I think :/ Give it the same number of APM as the mean of the top 100 players. Something of the sort...

What if the pace of play were slowed down 5x, so it became about strategy and not execution?

The particulars of the interface are really not the point of these exercises

Why do you think that controlling a mouse and keyboard would be hard? Industrial robots can do stuff like that with sub-millimeter precision and super-speed.

Controlling the motors of a drone or the moving surfaces of a fly-by-wire plane is much more complex than moving a mouse or hitting some keys.

Even with perfect mouse control, the AI would still be limited by the viewport offered, which is a tiny sliver of the map, and the refresh rate of the monitor, which would be at most 120 FPS I'd think. Information gathering would have to be balanced against issuing commands, as both take from a shared resource pool of viewport time.

Forcing an AI to play with a mouse, keyboard, and monitor is a huge handicap compared to giving it a God's-eye view API.

It would literally need just one frame to see and store all available information in said frame. This means that in just a few frames, it could jump around the entire map and get a complete overview of what's available. It could easily be abstracted away, meaning the AI has access to a complete view of the map from its point of view, provided by a relatively simple conventional piece of software which just now and then jumps across the entire map and processes the images. It's thus not really an interesting problem to solve in this context, just a minor annoyance.

He didn't say it would be hard, just more fair.

Taken to the limit, an AI with an API to the game can take micro-control of every character. His high-level strategy might not even matter, if every character can fight optimally. At the very least, an AI would have an advantage when starting multiple battles, since he doesn't have the "switching" overhead of panning around the screen, clicking on items to issue orders, etc. But that "god mode" option is not available to a human. (Even if we slowed down the game, the human would get likely get bored before playing optimally.)

But if the AI were limited in the same way a human was, the AI couldn't monitor an infinite number of battles at the same time, couldn't issue control instructions infinitely fast, etc.

Maybe the AI can click around "fast enough" that it wouldn't matter (we don't know). But at least it would be a fair fight.

You are missing the point of man vs machine competitions. It's unbalanced on purpose. The aim is to see if an AI with all its unique advantages can best a human with their unique advantages. It is not to create a physical robot that has to mimic the disadvantages of a human.

That's not cheating, it's a agreed upon rules. Making an AI that can beat a human is already very hard. Next you'll add other arbitrary requirements, like limiting the wattage to what the human brain uses...

I'm not missing the point. If you have to modify the game itself to allow the AI to compete, then it's cheating. It would be like self driving cars that required specialised roads.

Let the AI use USB for keyboard and mouse, and hdmi to see; then you don't have to modify the game.

What you're suggesting is that an AI can't really drive unless it's operating the car the same way a human does, i.e. with a steering wheel and pedals rather than having a direct digital interface into the car.

No. I even said what the analogy would be for self driving cars. I'm calling out the BS of the marketing scams for investment dollars that are these contests. Point out that and a bunch of people get butt hurt because they need that investment money.

Bullshit, a human only has 2 eyes, but a self driving car can see in all directions at once. You are just making up arbitrary rules.

I think you're missing the point of man vs machine competitions when we're talking about testing intelligence.

Machines are obviously better at everything requiring fast-twitch reflexes and massive data analysis. There's nothing interesting in a competition there.

In Starcraft, the fear is that machine-level micro may make it completely pointless. A human could play strategically better and still lose because the physics of moving a mouse are different than the physics of a transistor.

Guess what, StarCraft AI competitions aren't new, so your fear is misplaced.

I'm just explaining the concern that you were dismissing, whether it's valid in this instance or not.

It should be pretty easy to simulate the physical constraints that players are under in terms of actions per minute, etc.

You bring up a good related point, although I don't care as much about the mouse and keyboard. My issue is with the UI.

This is different from checkers or chess or go. The Starcraft UI is part of the balance of the game itself, so if you change it you are changing the game. People do this all the time to help humans beat other humans, and we call it cheating. Why is it magically not cheating if we do it for AI?

If they do have to change the UI (e.g. hook a datastream directly into the AI), the opponent should be able to install any mods they want. Otherwise the AI is playing one game while the human is playing another.

Terrible headline; machines are already great at "lying"; recent progress in poker, for example.

I don't think we can say they are "great" at lying. Complexe instant and continuous lying is far from great and that's why computers are very far from crushing human at games like sc2

What's the progress? Last time I checked, they were able to play slightly modified abc (i.e. take opponent's range into account) and have negligible winrate at micro to small stakes before rakeback.

We changed the headline to the subtitle last night because the main title is so baity. If that's not good enough, the best way to explain that is to suggest a better title—i.e. an accurate and neutral title that preferably uses representative language from the article. When users do this, we're happy to use their suggestions.

Reply on news.ycombinator.com