AIs vs Humans - Next Battle: Starcraft (businessinsider.com)

braindrainbahrain writes: Having conquered checkers, chess, and more recently Go, artificial intelligence research now looks at the next frontier: the popular real-time strategy game of StarCraft.
Blizzard Entertainment's president reached out to Google's DeepMind researchers last month, who are now describing StarCraft as "our likely next target". But many top StarCraft experts believe AIs will fail because "Unlike machines, humans are good at lying," reports the Wall Street Journal. An executive at the Korea e-Sports Association tells them "It's going to be hard for AI to bluff or to trick a human player."

One University of Alberta computer scientist David Churchill counters that âoeWhen the AI finds that the only way to win is to show strength, it will do that. If you want to call that bluffing, then the AI is capable of bluffing, but there's no machismo behind it." Unfortuantely, for five years Churchill has been running AI-vs-human StarCraft tournaments, and "So far, it hasn't even been close... Using a mouse and keyboard, the world's top players can issue 500 or more commands a minute," the Journal reports. But they add that now both Facebook and Microsoft are also working on small StarCraft AI projects.

Comments

AI could with by cheating with insane micro

[JcMorin]

For instance, micro marine so they never stay closer than their maximum range... or any unit in fact. I'm also looking at tank and medivac drop... I would see a deadly combination here. But overall strategy, I don't think AI is ready to be human... yet.

Re:AI could with by cheating with insane micro

[Anonymous Coward]

For instance, micro [manage units] so they never stay closer than their maximum range...

The player is effectively commanding AI already. If we want to test strategy not fast twitch processing then such features should be added to the unit's AIs that both the strategic AI and players command. in other words: If the troops you nest into battle can't "never stay closer than their maximum range" on their own, then you have stupid troops who need to be replaced with smarter troops, i.e., if the AI wins because the game is an unrealistic simulation that favors AI's winning then it doesn't say shit about the AI beating a human... That would be like having the world's fastest mathematician compute square roots against a smart phone, and then claiming the smart phone was smarter than humans because it can perform billions of calculations per second.

If ( speed == win ) then victory = !strategic;

Re:AI could with by cheating with insane micro

[phantomfive]

I'm not sure how insane micro would be cheating, it is simply the computer being better at micro than humans.

Because it's not showing intelligence, it's being able to click fast. We already know computers can click faster than humans, that's not a question.
The "Starcraft AI" is a thing because they are trying to improve the intelligence of computers. If all they do is click fast, they have cheated on the goal of intelligence.

Re:AI could with by cheating with insane micro

[kwoff]

It's definitely keyboard, not mostly mouse. I think APM of 300 is more normal, but peaks of 500 happen. But APM includes things like "spamming" hotkeys, where you hotkey your buildings to say keys 4, 5, 6 and flick through them to check whether they're done building/training, and clicking like crazy before a unit can train yet (to make sure it starts ASAP). Example of Flash playing SC2.

There's another thing called EPM, which is Effective actions Per Minute. That eliminates most of the spammy kind of things (there's also where you right-click spam with the mouse on the ground many times to order a unit to go to basically one place but you're sort of perfecting the position, for example).

Re:AI could with by cheating with insane micro

[bev_tech_rob]

What I don't get is how a human issues 500 commands in a minute? That's more than 8 per second? What kind of commands are we talking about here? It's been a while since I last played Starcraft, I remember most stuff was mouse based except for some shortcut keys, how do you move the mouse so fast? Any good videos to see these guys in action?

Watch them play on Twitch.tv. The players go pretty fast and can't even follow what they are doing.

Re: AI could with by cheating with insane micro

[davec727]

Right, you can't build the AI this way and expect to succeed. In Chess, there are a maximum of 32 pieces sharing 64 possible locations. In Starcraft, there could be hundreds of units on the map at any of millions of possible locations. Chess is a complete information game, Starcraft is not. (Your knowledge of your opponent's position and strategy is dependent on what you can see and largely on indirect intuition about what you DON'T see.) In Chess, turns are taken and there is plenty of time to compute each action optimally. In Starcraft, there are orders of magnitude more possible actions you could command, and you must choose which units are most important to focus on at any moment. There's just a fundamentally different approach required. And I think a much more challenging one.

Computers are no good at lying is that a joke?

[backslashdot]

First off it's very easy to write an algorithm that lies and misinforms when optimal. Second, and this is a joke, have you ever seen a progress bar be accurate when downloading or installing something?

Re:Computers are no good at lying is that a joke?

[Amouth]

this is a joke, have you ever seen a progress bar be accurate when downloading or installing something?

There is a difference between being able to lie and being good at lying. Everyone knows that progress bar is wrong, so that is bad lying. Good lying would being able to convince you it is right and making you do something different than you would because of the lie.

Re:Computers are no good at lying is that a joke?

[Solandri]

Through years of trial and error, Starcraft build orders (the order in which you build units and buildings) have been optimized to get you to a certain build state in the minimum amount of time. Build orders are queued, which means there's no human-induced delay. An AI will have little to no advantage there - it could gain a slight advantage with building placement to minimize unit travel times.

If you've watched any advanced Starcraft tournament games, the end result usually comes down to players' ability to micro while maintaining these build queues (an AI would probably win at those), or to bluffing. That's when you fake out an opponent by showing him a unit or building to make him think you're going for a certain build, but then you go for a different build. Your opponent scouts you, guesses what build you're going for, and modifies his build to counter yours. But you know you've been scouted so you change your build. Then when he's built up his army and encounters you again, he finds you've switched to a different build that his is ineffective against. And since different builds require different buildings and technology trees, it's too late to switch builds. Your opponent has to try to hold on with his inferior build as best as he can until he can get a new tech build up and running, all the while hoping your next tech shift won't counter that.

This is why in Starcraft it's not just important to scout, it's important to know how much of your base your opponent has scouted. You'll see advanced players do all sorts of crazy things like start constructing a building, then when their opponent's scout has left or been killed, they'll destroy the building and construct a completely different one. All the unit strength the AI can muster won't do it any good if the human has bluffed it into building ground combat units, while the human has built up a massive army of air units. And like the early computer chess games, once word gets out that an AI is vulnerable to a certain bluff, people will abuse it over and over.

Re: Computers are no good at lying is that a joke?

[backslashdot]

You seem to think a computer can't understand probabilities and can't learn from prior mistakes. That's a false notion. If a computer keeps falling for the same trick it can adjust itself so it acts more probabilistic.

Re: Computers are no good at lying is that a joke?

[Solandri]

Oh, I know a neural net can learn and tweak its responses based on past experiences. The beauty of bluffing is it can totally screw up that learning process

For years, Ty Cobb famously overran 3rd base instead of stopping every time a certain player fielded the ball. That forced the player to throw the ball to third base to force Cobb back. Eventually the player got used to Cobb overrunning third base and his throws to force him back got lazy and slow. Then one day in an important game with the score tied, Ty Cobb overran third base, the player made a lazy throw to third to force him back, and Cobb broke for home and scored the winning run.

Really good players develop an innate sense for when an opponent is bluffing. I can't explain how it works, but I know it does. When I was kid, I had this innate sense for The Price is Right. I could predict with about 95% accuracy when the announcer was going to say the prize was a new car. I have no idea how I did it, but my subconscious was getting some sort of signal from the inflection of his voice or the delay in his speech or something that told my conscious mind that he was going to say a new car. Ty Cobb was also exceptional at this sort of thing. When a teammate once asked him how he was able to hit so well against a certain pitcher who gave everyone else problems, Cobb replied that the pitcher's ears wiggled every time he was about to throw a curve.

This works when your mind is flexible enough to consider all possible inputs, even the seemingly irrelevant ones. It doesn't work with an AI programmed to look at only a limited number of "important" inputs to keep the CPU load down.

Data vs the Zackdorn

[spire3661]

Data couldnt beat Kolrami, so he forced him into what would have been an indefinite stalemate. Kolrami found this incredibly insulting and forfeit. Data won by having no ego. He busted him up.....

Another big problem is training resistance

[SuperKendall]

It seems like an AI would be really susceptible to being "trained" to react in a certain way by a player, who could then take advantage of that by sending up fake signals early and doing something that takes advantage of the anticipated AI response.

That may seem the same as "AI's cannot lie", but it's actually more about an AI being more susceptible to bluffs than a human player would be.

Just a Blizzard publicity stunt to stay relevant

[Woldscum]

Blizzard is a dying company. HOTS is a huge flop. Overwatch will also be a flop. Starcraft is basically dead. Diablo has a following and Hearthstone is the only real hit they have. WoW is kept on life support by the fanboys. After the next expansion flops again it will finally die.

Cheese-o-matic

[DraconPern]

Every games will be over in 4min as the computer just cheeses everyone.

As An AI Researcher

[Anonymous Coward]

I'm a CS Masters student doing a thesis on a RTS AI. Computers can beat humans, we just haven't tossed enough CPU at it yet. RTS are exactly the same as checkers, chess, go, etc... except you have more pieces, more board positions, and more than one piece can be moved per turn. To reduce that into something computable, you need good abstractions. Once you have those the game becomes a tree search, same as all the board games. Google/IBM can bring enough computing resources to the table to win. There are some bumps in that: imperfect information, teams, etc... but they don't change the core algorithms.

Computing the entire game tree is too expensive. They'll probably do it at a unit/battle level, at a squad level, at a city level, and at a long term strategy level. Doing things at different levels greatly reduces the search space. From your training data you'll know how well you can expect the battle manager to handle an upcoming attack with an expected loss of XYZ at some probability, so the strategy component doesn't need to bother with all the minor details of how to fight it.

500 commands a minute? That's nothing. With the computing resources of a super computer, expect the AI to be able to issue an order to every individual unit every game turn. And yes, at the game engine level all real-time strategy games are actually turn based.

When you have the resources, a tree search over a game's state space with a little bit of memory (so the enemy can't get your units stuck in a circle) is effectively unbeatable.

Civ V

[FunkSoulBrother]

How about they work on writing an AI that can play a competent game of Civ V without cheating.

RTS is much less interesting since a big component of RTS is actions per minute/reflex based. Of course a computer is going to be better at that.

Starcraft API

[braindrainbahrain]

BTW, if anyone wants to jump in and design their own Starcraft AI, this API is available for you to do it (I have no connection to the API project, btw).

The API is for the Starcraft Broodwar. If anyone knows of an API for the more recent Starcraft II, please post.

Re: Just a Blizzard publicity stunt to stay releva

[s4m7]

Starcraft confirms it.

Re:Hacker News

[phantomfive]

Problem with Hacker news is they don't have a funny mod, so everyone is always uptight, because if you don't say something insightful, you'll get voted down.

It's a lot more relaxed at Slashdot.

Blatantly obvious name for the AI ...

[Qbertino]

Overmind.