11 ms·
DeepMind Challenges for StarCraft
- deleted 11y ago[deleted]
- klog 11y agoI would say Koreans are on supercomputer AI level in this game.
- broodbucket 11y agoStarCraft would indeed be interesting for one of these challenges, however the peak of human skill in this game has already been lost. Tournaments are dwindling, many players have moved on to other games like StarCraft II or retired. The remaining players aren't at the level that they were, say, 5 years ago, when there were two major televised starleagues. Even if some AI does defeat Flash in 2017, would they have defeated Flash in 2010? The mechanical skill required for this game means you simply can't come back to the game after a year and resume where you left off. Knowledge and understanding aren't enough, your fingers must be lightning.
- DanBlake 11y agoOne of the issues to overcome is the advantage machines can have in individual unit manipulations vs what a human can do in terms of APM https://www.youtube.com/watch?v=SZawUuAccnc https://www.youtube.com/watch?v=SZawUuAccnc
- detaro 11y agoIf anyone, Google has the image recognition and robotics tech to make a robot sitting in front of a screen, with keyboard and mouse ;) Yes, anything where the interface to the game becomes critical is difficult to fairly compare with humans. Board games can use a human as an actuator, micro-heavy games hopefully won't for a long time...
- dogma1138 11y agoNot really since electromechanical engineering would then be the bottle neck. If you want "fairness" you can limit the instructions to what keyboard and mouse can actually interpret as in the limited latency between instruction that both the game, the OS, and the hardware can support.
- smilekzs 11y agoThe game is capable of accepting a much higher APM than Korean pro players are capable of pulling off even at peak. IMHO the AI should be subject to an APM limit (e.g. sliding window).
- dogma1138 11y agoNot if it's done over the normal channels (USB) many players not even "pro korean" ones can easily encounter input issues like key rollover limits and polling rates on your mouse. USB has quite a bit of limitation for HID's and allot of the gaming mice and keyboards use various hacks to overcome them. Games and OS also have limits I can easily issue more commands using my keyboard than SC2 can handle so not all key presses will actually register. Not to mention is that the game actually has to run on regular hardware, start spamming your keyboard in a game and you see the CPU spikes, the game loop also puts quite a bit of limits on how many interrupts per second it can catch, and how long does it take for it to actually switch context (e.g. SC2 build menus). That said after AlphaSC2 destroys another Korean national passtime I would definitely love to see human like input being used by AlphaSC2. Not because I think humans deserve a fair fight, but because i think the most interesting part will be to see how AlphaSC2 has to modify it's play style to compensate for the limitations of having to use "meatbag" control methods.
- smilekzs 11y agoIIRC the entire input polling/NKRO issue can be solved by simply switching from USB2.0 FS (aka USB1.1) to HS, which requires a more powerful keyboard/mouse controller.
- Mithaldu 11y agoThe problem is, as ActionButton argues in this review of Diablo 2 [0], Starcraft is a game that may contain some amount of strategy, but wherein the element of strategy is strongly over-powered by a reflex-based combat system more akin to Street Fighter than anything else. [0] http://www.actionbutton.net/?p=518 http://www.actionbutton.net/?p=518
- TulliusCicero 11y agoIf that was true, then bots would already easily dominate humans, just like they can for fighting games. But they don't; even moderately competitive players can beat the best bots.
- Umn44 11y ago"But they don't; even moderately competitive players can beat the best bots." That's because the programmers are bad at AI for that kind of game. It just means human beings don't understand how to make a good AI for a game like starcraft. AKA the human being being the idiot that doesn't understand how to make one.
- ktRolster 11y agowherein the element of strategy is strongly over-powered by a reflex-based combat system This isn't true, in general a bigger army will beat a smaller army every time. After you can make equal size armies, the next problem is army positioning and when to take engagements. Finally, after you can do all that, then you can get an extra bonus to your power by microing really well. But not every micro is about speed - most of the time it's about knowing what to do. And even at the most extreme, it's less about clicking quickly and more about clicking precisely.
- drwl 11y agoIt's not always the case where smaller armies lose to big armies. There are many situations in Starcraft where superior micro of less units can taken on more units. One example is Phoenixes versus mutalisks. For those who don't play, Phoenixes are faster and have slightly longer range than mutalisks. Phoenixes can infinitely shoot and run and kill of mutalisks.
- sesutton 11y agoI'm a little worried that the AI will quickly develop a simple early game strategy where it sacrifices economy for early units (an "all-in") that never loses because of its perfect unit control. The AIs unit control speed may have to be limited to get interesting results where it has to use strategy.
- LetaBot 11y agoIf the human player builds a wall, he/she will be ahead against a rushing bot.
- fatman13gg 11y agoIt would also be interesting to see if DeepMind challenges Dota 2 one day maybe. How they would handle a 5-man team game and adapting to major game updates?
- ktRolster 11y agoI think it's pretty simple, you just take the starcraft AI, reduce the number of units it can handle at a time, maybe simplify its economy logic, and then let it go. Easy.
- danharaj 11y agoThe interactions between individual unit types in a game like DOTA are much more complicated than, say, the interactions between marines, zerglings, and zealots; there are many more unit types, too.
- ktRolster 11y agoas someone else pointed out, the interactions between the units are like fighting games. Computers already have the advantage at fighting games (like Streetfighter). Micro and unit control is where the AI has the advantage.
- danharaj 11y agoThe complexity of the unit interactions also has a strategic layer (drafting, lane assignment, timing) which may be far more difficult to train and isn't just purely the micro aspect of the problem.
- tonyle 11y agoI like this idea. To be fair, You need five computers to communicate with each other. It will be a huge mark for ai if they can actually learn to communicate with effectively for achieving the goals. Vary the performance of each ai and allow them to swear at each other could get very interesting. I wonder if ai can emulate the toxic side of gamers......
- hmate9 11y agoI think poker would also be a great challenge. It is a special game because as well as the math, you also have to understand your opponent and adjust accordingly. It'd be interesting to see weather DeepMind can beat professional poker players who have different playing styles.
- CyberDildonics 11y agoThere has been lots of research into many areas of AI poker.
- jhspaybar 11y agoMy understanding is that limit Texas Holdem poker is essentially solved. No limit is a different thing though, one mistake and you could be done.
- bradleyjg 11y agoI think that's heads up limit texas holdem, not limit holdem in general. e: ref--http://ai.cs.unibas.ch/_files/teaching/fs15/ki/material/ki02-poker.pdf http://ai.cs.unibas.ch/_files/teaching/fs15/ki/material/ki02...
- im3w1l 11y agoWouldn't that depend on what you want to achieve? To maximize $/h you need to understand your opponents weaknesses and exploit them. But if you just to beat the best humans, and don't care about the margin with which you beat them, then playing a mathematically perfect game should be enough. And before you ask, a mathematically perfect game can incorporate occasional bluffs, and occasional calling of bluffs, this would be known as a Mixed Strategy. Or am I missing something?
- eru 11y agoThat's about it for a two player game. Anything with more than two people has more interesting / complicated properties.
- dave_sullivan 11y ago> StarCraft is closed source, making it quite challenging to run simulations. One of the techniques used by AlphaGo is reinforcement learning, which involves a huge amount of simulation. In order for DeepMind to overcome this limitation, it’s likely that novel abstractions of the state-space will need to be developed. For their atari work, deepmind was using raw pixel data from the screen. You could do something similar for starcraft. I suspect the actual machine learning question is 'given a sequence of n frames of the game, where should i click next? repeat.' A training set might look something like video of a game with a text file recording X,Y positions for every click and a timestamp that can be synced to the video. They need lots and lots of those. From there things get drastically more complicated. To go from very unstructured data like that and form higher level representations that can be used for long term planning and strategy... That would be quite a feat.
- eru 11y agoAnd you can run the StarCraft binary in a VM to be able to roll the game state back and forward.
- dsl 11y agoGame replays (including all the fun data like player clicks, unit selection, movements, and exact timing) are stored in an easily parsable format. https://github.com/GraylinKim/sc2reader/wiki/Replay-Format-Home https://github.com/GraylinKim/sc2reader/wiki/Replay-Format-H...
- ktRolster 11y agoArtosis wrote his view on the topic, it's probably worth a read: http://espn.go.com/esports/story/_/id/15019778/infinite-apm-artosis-deepmind-starcraft-part-2 http://espn.go.com/esports/story/_/id/15019778/infinite-apm-...
- ShardPhoenix 11y agoIt sounds like he has no idea about the machine learning basis of Alpha Go (and therefore presumably any future Starcraft AI) and thinks all this complex decision making has to be programmed in by hand (which would indeed be nigh-impossible).
- nickhalfasleep 11y agoDoes anybody else think teaching a rapidly evolving strong AI about how to be really good at war might be a bad thing?
- forrestthewoods 11y agoI want to see StarCraft next and then League of Legends/DOTA. The control advantage an AI has in StarCraft is immense. It exists in League of Legends, especially when perfectly coordinating 5 different characters, but it's less impactful.
- bottled_poe 11y agoThe control required to master SC2 is far beyond any MOBA style game. AI for MOBA games seems trivial compared to AI for a large scale RTS. It's the difference between controlling 1 unit vs 100 units.
- forrestthewoods 11y agoI don't think I agree with that at all. If you can control 1 unit it's trivial to control 100. I might argue that the AI vs AI challenge in Starcraft is deeper and more difficult to master. But for AI vs Player the Starcraft AI has an enormous mechanical advantage. Being able to harass mineral lines in four different places is a big deal. Being able to perfectly micro multiple lines of attack/defense is a big deal. It's very unfair and very much in the AI's favor. Chess < Go < Starcraft < League of Legends In my moderately educated opinion.
- komaromy 11y ago> If you can control 1 unit it's trivial to control 100. Control them, sure-kiting 100 units at a time would be a breeze-but using them together in a coherent way is drastically more difficult.
- lumpypua 11y agoFrom an above poster: https://www.youtube.com/watch?v=IKVFZ28ybQs https://www.youtube.com/watch?v=IKVFZ28ybQs
- bottled_poe 11y ago
- Monory 11y agoWell, anyone who says that advantage in micromanagement is not a big thing should see "Automaton 2000" videos. Given that automaton is a map script and thus can have virtually unlimited APM, it beats people from a horribly disadvantageous positions (40 banelings vs 21 marine [1], or 100 zerglings vs 20 sieged tanks [2]). [1]: https://www.youtube.com/watch?v=DXUOWXidcY0 https://www.youtube.com/watch?v=DXUOWXidcY0 [2]: https://www.youtube.com/watch?v=IKVFZ28ybQs https://www.youtube.com/watch?v=IKVFZ28ybQs
- diskcat 11y agoYeah. infinite apm would make stuff like marine being able to turn around and shoot instantly OP. it was just impossible to exploit before with human reflex. also the APM is not unlimited, it is only very high.
- nickpsecurity 11y agoI agree. It's one of only areas the AI's have been hood at. Pathfinding and build orders being other two. AI should be limited to a specific number of actions a minute comparable with opposing player or best human champ. Then, we're grading it on its "thinking" instead of dexterity. They better keep fog of war on too.
- derefr 11y agoOr, the AI could be set up like AlphaGo was: as a computer giving instructions to a merely human player. I'd love to see what a powerful StarCraft AI would do if trained to "predict and compensate for" not only its opponent, but also the inevitable human errors in faithfully executing its strategy. A certain Sector Command and Control Unit springs to mind...
- dragontamer 11y agoA huge amount of Starcraft is the intense APM training regiment that the pros undergo. APM is a huge indicator of Starcraft "skill". Its not the only thing of course, but winning "micro-battles" greatly changes the game. I don't care how good Michael Jordan is. He'll never "win" a game of basketball vs a standard professional by shouting commands to an average joe. Similarly, no average joe will be able to perform a muta-harass while retaining full-speed, taking only a single missile from a Turret. That sort of "micro-skill" takes practice and dexterity.
- scottjad 11y agoStarcraft is a game that is played with mouse and keyboard (or game controller on console). I think in order to say an AI has beat a human, it should have to use the same interface that a human uses. That's part of the definition of the game. In Go, anyone can place a stone as well as anyone else, it's deciding where to place a stone that's the game. In Starcraft, not everyone can control the interface to the game equally well. Playing Starcraft without using the same interface as humans is like playing baseball with something other than a baseball bat. Also, I think it's unfortunate that they're choosing Starcraft 1: Brood War (presumably because of API reasons) instead of Starcraft 2, since there are many more top-level players playing sc2 right now to give it a run for its money, with an evolving meta that could more likely adapt and challenge the AI after it wins some matches. SC2 is where the tournaments and money is right now (compared to BW), hence the best players devoting the most time.
- deleted 11y ago[deleted]
- ludamad 11y agoBut Brood War has been thoroughly explored, and is a much more stable target (SC2 is prone to game-shaking patches). Back when pro play was just ending, I was astonished by the level of play. While players may need a bit to practice against the AI, a good AI spurring more play is really exciting to me.
- barbs 11y ago
- d0m 11y agoI know bliz doesn't want it, but it would be so much better with sc2.
- anaconda123 11y agodamn bored
- confiscate 11y agoDeepMind is becoming a nightmare for South Koreans
- ddxv 11y agoThis is an amazing project. Thank you for that post. I would love to find some teams working on this who are interested in adding junior level engineers.
- nickpsecurity 11y agoSurvey paper below introducing Starcrafy challenges plus all the AI's that failed to conquer humans. https://hal.inria.fr/docs/00/87/10/01/PDF/survey.pdf https://hal.inria.fr/docs/00/87/10/01/PDF/survey.pdf
- hiq 11y agoAn AI with human-like abilities (so no infinite APM for instance) would be great for balance problems in competitive video games. Just run the AI a certain number of times, and if some race or unit always wins the game, there's definitely a problem.
- timwaagh 11y agoI'm rather suprised there are no player beating ais for starcraft. i dont think it should be very hard as decisions need to be made very quickly in this game and humans are bound to make more than a few mistakes. but perhaps i'm underestimating the problem. it may have something to do with the limitations of the api though.
- ygra 11y agoYou're underestimating the problem. And there are several: - Controlling individual units: scouting, resource gathering, micro-management while attacking/retreating, ... - Resource management and planning: knowing when and where to expand, save resources for certain points in the tech tree, e.g. so you can immediately build a bunch of units once a crucial research or building is complete, ... - Figuring out what the opponent is building and what he could be doing: where is he and what race, what tech buildings are there, when does he start to harvest gas, key tech buildings may be hidden in other places of the map, essentially even not being attacked with certain units at a certain time may be a clue to some strategy - Reading and using the terrain properly: High ground has an advantage, Terran can wall off certain entrances with a depot and a barracks, where would be good places for drops (and with what units), figuring out where the enemy could come from and which places to defend – all those vary by map quite a bit - Finding a good strategy to counter what the opponent is doing: This ties into a few of the things above, because first it must be known what the enemy is doing. Keeping the strategy flexible enough to counter the enemy's counters, etc. Some of those are necessary to solve in real-time (unit movement), some of those can be run in background and don't need to be frame-exact (strategy, etc.), which helps a bit. But there are still quite a few parts to playing the game, all of which are interconnected and require information from other parts. Many successful bots currently are rush bots, which exploit that most bots are weak in the beginning and are easy to create. Others rely on a number of fixed strategies and build orders that are chosen based on what the enemy is observed to do.
- jmnicolas 11y agoIMHO it's not artificial intelligence it's just intelligent scripting. A real AI, like a human shouldn't be programmed for something specific but adapt itself to what it encounters.
- stared 11y agoWhen it comes builds: https://www.rockpapershotgun.com/2010/11/02/genetic-algorithms-find-build-order-from-hell/ https://www.rockpapershotgun.com/2010/11/02/genetic-algorith... For micro, there are scripts: https://news.ycombinator.com/item?id=11325855 https://news.ycombinator.com/item?id=11325855 So, while it may be not easy to conquer humans, I don't see why it is out of our current reach.
- proc0 11y agoI'm not as optimistic as most seem to be. I think SC adds a completely new layer to the game, that none of the previously learned games had. It's not enough to play the game just by rules that are implied by the pixels. In chess, go, and even simple atari games, you have a clear way of reading the current state of the game in which the next move will be based on. In SC, this state space includes the predictions of your opponent. What will your opponent build next? What will they try to do with their army? There's an element of theory of mind here, where opponents try to project themselves and preempt each other's moves. For an AI to truly play and win against a SC pro, using only human level interfaces, it would need to learn how human minds will be playing the game. Otherwise, I think we can expect a strong AI with unconventional tactics that SC pros will be able to fool with tricks and take advantage of because the AI lacks a meta-game capability. A more "general intelligence" would be needed to play at this level, not just a learning algorithm that learns from the pixels on the screen.
- ucho 11y agoMaybe Civ? I guess the single game takes too long but I still would love to see it as default AI is totally crap and relies on handicaps.