usrevenge•

well yea, board games like chess the AI literally just calculates every possible move.

starcraft the AI (unless cheating of course) has no idea what i have and what i am doing unless he sends units to me or I attack him.

it will be interesting though because the AI should be able to micro manage units significantly better than human players, blink stalkers in SC2 would be a huge force multiplier if literally every single stalker that lost shields got blinked back at the moment shields were low/zero.

64
bobfishfish•

board games like chess the AI literally just calculates every possible move.

Chess is most certainly not a solved game yet. The AI calculates an optimal board state based on heuristics of it's past games.

See this for more info.

73
Buri_•

Yeah, I don't even know what the statement you quoted means. Every possible move leads to a new state with its own set of other possible moves that also each branch out. The complexity is mind boggling and a brute force approach is as well as impossible.

18
marcelluspye•

a brute force approach is as well as impossible

To solve chess, yes. But brute-force is essentially how Deep Blue beat Kasparov. The algorithms it was running weren't revolutionary compared to what was available at the time, but they designed special hardware optimized for crunching chess board numbers.

This is in contrast to DeepMind beating a top Go player, which while it had a massive amount of processing power behind it, was also based on having great algorithms to go with it.

21
MEaster•

I don't think you realise how good chess engines are these days. In 2009, a chess engine running on an HTC Touch HD, beat multiple grandmasters in the Mercosure Cup.

It doesn't do that through brute force, it does that by detecting which moves can be ignored.

14
oldsecondhand•

Deep Blue didn't use pure brute force, it just searched in a very high depth, but still needed heuristic functions.

13
triina1•

The point he is making is that chess is also ridiculously complicated and computers don't brute force it

2
[deleted]•

[deleted]

-2†
RadiantSun•

Chess is not a solved game but the way chess engines work is to calculate all the best moves from a particular position. They have "trees" that they calculate like 9 moves down from. You can run StockFish on your phone these days, and it will beat almost any human opponent.

3
Sacharified•

AI that can micro perfectly at a level impossible for humans already exists.

https://www.youtube.com/watch?v=mrbYd4OFrWE

https://www.youtube.com/watch?v=IKVFZ28ybQs

https://www.youtube.com/watch?v=DXUOWXidcY0

If you're going to pit AI against human players, the first question is how to handicap the AI in a way that its ability to formulate and respond to tactics/strategy is being tested rather than pure mechanics.

A dumb AI still has perfect precision and multitasking orders of magnitude better than that of a human and would probably win 100% of the time unless artificially handicapped.

If they want to test how an AI can handle a game with hidden information, a turn-based game would be preferable.

52
hesh582•

There is no need for handicapping, at least not yet. Humans consistently beat the best AI.

The reason for this is twofold: First, you need a lot more than micro to compete at the highest level of SC. No mattter how crazy the micro, humans tend to win by using misleading scouting info and countering, etc.

Secondly, those are not just amazing micro. They're amazing micro tricks. Sure, I wouldn't want to charge a line of banelings into a pack of perfect AI marines, like in that clip. So I wouldn't. I'd use fog to loop around, take advantage of observed ai patterns to move them into a dangerous map location as they back up, etc. The tricks are great and would help a human player tremendously, but without the deeper understanding humans still have they don't cut it on their own.

They don't win 100% of the time - the best AIs have tournaments with semi-pro players and routinely get crushed. If ais and their strengths and weaknesses were frequently encountered and played against, they'd be abused even more.

21
teerre•

Do you have examples of an ai always winning against humans with pure mechanics? Because if you watch that ai vs ai sc tournament it's pretty clear they have no chance against good humans and since it's an ai only tournament I don't think there's any handicap in that case (which might be not the case)

11
aztec2step•

the Starcraft AI isn't exactly advanced.

10

You must have never played with custom AI during Brood War. Those things were legitimately hard

3
Tonkarz•

It's designed to be fun to play against.

1
teerre•

What you mean by that? The point is if the most efficient way to program the ai was to make them mechanical gods, that's what people would do, rudimentarily or not. Being advanced doesn't change how you go about programming the ai

-5
Sacharified•

Maybe 'dumb' was too strong a word to use lightly in a discussion about AI.

The AI would have to reach a certain level in terms of strategic/tactical 'knowledge' to have a perfect win rate, but the level would be much lower that than required by a human to reach the top level of players.

Given enough sample data, an AI similar to AlphaGo (in terms of learning capabilities) could probably quickly find a number of strategies which could beat top humans 100% of the time when applied with perfect mechanics.

Perfect mechanics won't do you much good if you don't utilise them at least reasonably well.

3
dreamsplease•

Civilization 5 or something similar would be a good place for AI. The devs of that game just give the stupid AI advantages at higher difficulties.

3
hesh582•

I actually don't know that civ is a great example.

It's not actually that deep. There aren't really all that many optimal choices each turn, and the "algorithms" for optimal efficient play are pretty figured out and static.

Beyond that, though, civ V might not be a great place either because at high levels of play random chance starts being more and more determining. There's a huge amount of both guesswork and good fortune involved regarding starting location, barbarians, ruins, natural wonders, etc. If you shoot for the great library at first and lose by two turns, you've essentially lost. If you don't, you've won. There's a lot of that sort of thing - it's fun to play with but there isn't really as much skill involved passed a certain point as people make it out to be.

10
Mandena•

Have you actually watched high level NQ gameplay though? I don't ever really see those players bank everything on a wonder. In fact I don't think I've ever seen a top player lose because of a wonder loss.

4
LetaBot•

There has already been research on it (but they used openciv):

http://www.extremetech.com/extreme/90046-computer-learns-to-play-civilization-by-reading-the-instruction-manual

as a matter of fact, this Civilization AI (text mining) got me to the idea to text mine the Liquidpedia for Brood War build orders for my BW bot.

2
Jerthy•

This is the most powerful aspect of AI - i don't really think it would need very advanced strategies, bluffing, hiding proxies etc - all it needs is few units with powerful micro abilities. It wont be long before it will notice blink-stalkers. And at that moment everyone gets fucked.

That said i still want to see alphago at its full potential, at least at first.

2
Arquinas•

Would making the AI simulate reflex time help? Like, say the AI is really good at managing multiple complex tasks simultaneously, better than a human player.

Now, give it a random modifier for each task equilevant to a click of the mouse or key so that it takes between 200-300 MS everytime to do it.

1
JoshuaPearce•

The solution I like isn't to handicap the AI, but to give the human equal mechanical assistance. Just like we'd have in a war against super smart aliens, or skynet. That kind of contest would be decided by cleverness, not micromanaging.

Frankly, the UI shouldn't be a factor in a game of strategy, it's just an evil we can't work around yet.

1
chedabob•

board games like chess the AI literally just calculates every possible move

In the days of Deep Blue, this was the case. But Chess bots are now way more sophisticated, and Google's recent victory in Go could not have been done by pure brute force.

13
Pindaman•

Wouldn't it be fair to match the APM roughly around what a human does?

8
usrevenge•

I don't think so, by fairness I meant not cheating like almost all (or all?) AI does in games like this. if you play vs the top level AI in sc2 they gather resources faster and iirc know what you are doing at all times.

even if at max 500apm or w.e the micro could potentially spot on by an AI.

7
Apathy_is_Death•

That's not solving the issue. Because if you constraint the APM you then only try to make the APM as efficient as possible. A 500 APM AI will always be better than a 500 APM human. Not to mention 500APM is already high for humans, I think there was a guy in SC1 who had average of 550-560APM at some point but he was one of the only ones. It translated to about 300-350effective apm. He didn't achieve much in the game.

On the other hand you had people like savior who had like 250apm and were starleague champions.

1
Firrox•

In human vs human games, you really don't know what your opponent is doing until you scout them, either. That's what early, structured builds are for.

I'm sure an AI can learn what builds are most effective vs certain races, and even come to predict what a human might do in the next game depending on how the previous game went. Such are strategies humans use now.

4
celphy•

Tasks like building a wall that limits access to your highground are already highly complex. Following a non map specic buildorder is very hard for AI.

2
Firrox•

I'd love to see that challenged.

1
celphy•

Have a look at this pdf. This is an approach using an API. It doesnt need to rely on the actual graphical output of the game. Considering you couldn't just work around it using directx calls but would need to actually gather information from an image, yeah, building a wall isn't going to be as trivial as you thought.

2
Tonkarz•

The thing is that you can program AI to scout as well, but the human player can trick it.

1
thomar•

it will be interesting though because the AI should be able to micro manage units significantly better than human players, blink stalkers in SC2 would be a huge force multiplier if literally every single stalker that lost shields got blinked back at the moment shields were low/zero.

It would be interesting to isolate the units in Starcraft that benefit from fast micro-managing, and also the metagame for units that human players can run well against those tactics.

3
eorld•

In chess the AI definitely doesn't calculate every possible move, that would be impossible with current technology. There are more possible chess games than atoms in the observable universe (~10^80). The estimated lower bound for possible chess games is 10^120.

2
GrassWaterDirtHorse•

I remember there being a vanilla AI versus AI show tourney a while ago. Due to the way Blizzard coded Zerg AI, Overlords wouldn't be moved as a group but as individuals which resulted in some stupidly high APMs whenever something threatened overlords.

1
Lucarai•

Ooh machine learning could really be cool with this

1
DuduMaroja•

That's what scouting is for, very easy to do and cost effective

1
ClockworkOnion•

starcraft the AI (unless cheating of course) has no idea what i have and what i am doing unless he sends units to me or I attack him.

the same thing they are trying to do with hearthstone AI vs humans. the AI get pummeled because it can't or doesn't grasp the deeper mechanics of the game. Chess and Go are very binary in their nature and the AI uses heuristics to determine which moves it can ignore and which ones to play. It simply can't do that in Hearthstone or StarCraft.

1
omegashadow•

You are hilariously wrong. The idea of just calculating all the moves is daft and pretty much impossible.

Look not too long ago people who were not intricately familiar with Deep Blue would tell you that computers where nowhere near ready to take on Go, but thanks to a project where YEARS of computer time were dedicated to Go alone we are close.

When Starcraft as a challenge for AI has been taken on by a team of researchers for 4 or 5 years and progress is looking tough then we can start discussing this at all.....

Edit: Also worth noting, starcraft is on a different level mostly because it's a game where not all the information is available to both players. If you could set a game mode where there was no fog of war for both players I recon that a team of researchers could have reasonably performing bots in 5 or so years. But with imperfect information it becomes a whole new can of worms as to whether AI can get heuristic results well enough.

0
Tonkarz•

well yea, board games like chess the AI literally just calculates every possible move.

Actually, that's not true. The AI calculates a few moves in advance, and only down possible moves that it decides are both "good" on it's part and likely on it's opponent's part. The real trick with chess AI is not raw processing power, but how good your AI is at deciding which future possibilities are worth calculating.

0
Dag-nabbitt•

The lack of visibility means that computers can’t simply calculate all the possible moves their opponent might make

That was true with Go as well. You cannot brute force Go. The number of moves available increases too quickly.

I think the real-time part is a more interesting differentiation. I also think they should start with something a bit mechanically simpler, like a MOBA. Where you only have a handful of units, rather than 100+ ones.

41
viking977•

Ha, I'd love to see a computer try and play dota. Mechanically simpler, yes, but an ai would have to contend with 10 times the human variables.

19
Dracious•

I'm curious how well a dedicated ai could do actually, since even though there are a lot of human variables, most come down to gank, teamfight or push, as well as laning in the early game and maybe some jungling or a roshan attempt.If an ai can determine what the players are doing and categorize them into one of these groups it might actually be fairly easy to program what it should do.

On top of this building items would be pretty easy, follow a pre determined build with some variables for counters, e.g give each opposing players spells a number rating, and if the rating of the enemy team is over x then buy a bkb, if someone has evasion and you a carry get a MKB, that sort of thing.

I would say play a support well would probably be the hardest thing to do, since a good support needs to ward, deward, gank and roam lots early, know when it sacrifice yourself, know when it hold back, whilst a more core hero is a little simpler.

I'm not saying they would be even close to pro players or anything, but I think with some effort they could compete against mediocre/average players.

2
viking977•

A single bot on a team of humans is one matter. Dota is such that a team can win 4v5 without much difficulty. I figure the best bot we could hope to build at current level technology would be at best a small handicap, assuming you could direct it slightly with pings and stuff.

A team of bots against a human team? No way they could ever win consistently without cheating (again, with current technology). Hell, dota's insane bots DO cheat and they're still not that that hard to beat alone, let alone with a five man team.

Any programmer that can get a bot to smoke gank properly deserves a Nobel prize IMO.

4
Lost4468•

Only the impossible to realistically brute force it part is true for Go. Go has all the information available to the computer at all times, StarCraft does not.

18
cobbyb•

In Go the computer could see every move the human player was making. The problem in Starcraft is trying to take into account all the things the human player could be doing but it cannot see. Current AIs are pretty horrible at this and even with their inhuman control lose against low level players. They also have lots of issues deciding when it is a good time to trade units or when to initiate combat. It is the fog of war and the importance vision denial plays in the game that will make StarCraft an interesting challenge.

15
MercWithaMouse•

Yeah i think they were trying to say that Go is a game of perfect information while Starcraft isnt.

6
dfjuky•

Theres already Starcraft AIs which can perfectly micro 30 mutas way beyond the capabilities of any human. The mechanics aren't the problem.

2
celphy•

But the AI is built in a way that doesn't mimick a player. It uses a game interface instead. It's not really clicking anywhere.

2
Apathy_is_Death•

I still think Starcraft is a 'bad' game for AI research. Just because it's real time.

What kind of constraints do you put on the AI? If you give it full access, it's basically playing a different game than the human. If you restrict it to keyboard+mouse inputs it's still playing a "different" game as the human because it has 1000+APM or whatever.

I'm positively sure that the easiest thing to beat humans in SC1 would be to focus on some kind of early cheese or just push with perfect micro, one that a human couldn't defend. Like imagine stimpack +1 timing with perfectly microed medics/marines. A zerg can't really do anything. A protoss might get a reaver out but good luck when the AI lets you get 1 kill per scarab. etc etc.

Just a rough example, but I believe that's the "easiest" way to beat the human. Go for a strat that hits early when scouting/strategy/etc have a weaker effect on the game than just pure micro.

But again, that wouldn't really prove anything. We already know 1000APM+ AI > human in micro.

So what do you do to make sure the game is 'fair' ?

16
celphy•

Every strategy can be countered. That's kind of the beauty of RTS in general. An early rush would work once or twice. Building an AI that can consistently beat top players on !unknown! maps is really fucking hard, 1000 apm or not.

The brood war AIs can't even fucking wall their base properly, scouting is terrible. Some of the bots win by building a shit ton of air units and scouting every pixel of the map. AIs are really bad at the moment.

6
IceNein•

Really hard, but not impossible, and in time it will become easier. Not only easier, but inevitable.

People like to champion the human brain as something special, but it's just a computer. Its a computer that is made up of neural networks rather than transistors.

We're not adding functionality to human brains year over year, but we are with microprocessors. We aren't upping the clock speed on the human brain.

3
celphy•

You the guy above just said real time is bad. We function in real time. Of course we want to beat ourselves, thats kinda the goal here.

2
IceNein•

What are you even talking about? I never said anything about real time.

0
Apathy_is_Death•

Yes they are. I'm not sure if it's because of BW or if the API is hard to manage or something, but if you look at SC2's AI some of them are capable of such micro the human stands little to no chance. It's true that automatron2000 or w/e it's called was mostly made via scripts and shit but iirc there was a playable map as well.

-1
Ideas966•

It'd be especially interesting to see how they make AI adapt to different maps and race match-ups which is a key part of StarCraft. I also wonder if it'd be easier or harder to try to make super-AI for SC1 or SC2.

2
[deleted]•

[removed]

1
[deleted]•

[removed]

1
[deleted]•

[removed]

1
[deleted]•

[removed]

1
CrackedSash•

Possible that it will use Starcraft Brood War because of BWAPI, which provides a way for an AI to control the game.

1
[deleted]•

[removed]

1
Orfez•

Give Google 2 years to develop their version of SC AI and machine will clean sweep every human opponent.

-1
Ebolatastic•

Fake teching into things is probably the hallmark of fucking an Ai. No matter how sophisticated, an Ai is usually reactionary whereas high level play here is far more complicated than an if then tree.

-2†
Aunvilgod•

The AI could also just rush every game so that these strategic decisions become rock-paper-scissors. And if it plays Protoss the opponent can't just turtle to be safe.

2
Ebolatastic•

Nah, an AI that rushes I think would give the opponent a serious advantage. The devs have made it so a failed rush basically cripples you and also rushes are the easiest to practice against. Its exactly why you probably cant make a perfect Starcraft AI because there are way too many things that happen. Comitting to a rush reduces the strategic optiona down to almost nothing.

0
Aunvilgod•

The devs have made it so a failed rush basically cripples you

Go tell that Kim Yoo Jin.

2
Apathy_is_Death•

I'd hoped you'd mention boxer from sc1 rather, or MKP.

Like imagine scv+marine rushes, it's basically early units versus early units every time. There's little if any strategical game going on. It's just mechanics vs mechanics, in that kind of scenario the AI would excel and easily win the best human players.

But is that really the point?

2