Two decades after Deep Blue conquered chess and a year after AlphaGo took down go, there are still games that artificial intelligence can’t beat.
AI researchers like games because they offer complex, concrete, and exciting challenges, which can unlock broader applications. Take it from AlphaGo creator Demis Hassabis: Games "are useful as a testbed, a platform for trying to write our algorithmic ideas and testing out how far they scale and how well they do and it’s just a very efficient way of doing that. Ultimately we want to apply this to big real-world problems."
How close is AI to beating different games? We asked a couple of AI experts for an update.
"StarCraft" is the next big target
After Google’s AlphaGo defeated grandmaster Lee Se-dol in go — that deceptively simple game of black and white stones with an immense number of possibilities — Hassabis called "Starcraft" "the next step up."
Google engineer Jeff Dean, who leads the Google Brain project, went further: "'StarCraft' is our likely next target."
"Starcraft," released in 1998 by Blizzard Entertainment, is a real-time strategy game where players build a military base, mine resources, and attack other bases.
It has become a focus for AI researchers for a few reasons: it’s highly complex, with players making high-level strategic decisions while controlling hundreds of agents and making countless quick decisions. It’s popular, as the first major esports game and practically the national sport of South Korea in the 2000s. It also has a relatively big research community with annual AI competitions dating back to 2010, a publicly accessible programming interface, even support from Blizzard.
Despite all this attention, the best "StarCraft" bots can easily be beaten by top humans. The bots tend to be good at low-level unit interactions but bad at high-level strategy, especially when it comes to adapting that strategy on the fly. They may also make dumb mistakes.
"There is progress, but it’s maybe a little bit underwhelming," says Julian Togelius, the co-director of the NYU Game Innovation Lab.
Human player Djem5 destroyed bot tscmoo in this 2015 match after finding an undefended base.AIIDE
This has a lot to do with the type of people building "StarCraft" bots. Brilliant though they may be, they tend to be solo hobbiests who have nowhere near the resources of large companies.
That could be changing. In addition to Google’s hinted interest, Facebook and Microsoft researchers have published papers involving "StarCraft."
"With the increased attention that "StarCraft" AI is getting from large companies, if they do end up spending time and money on this problem, this will accelerate progress dramatically," says David Churchill, a professor at the Memorial University of Newfoundland who runs the "StarCraft" AI tournament.
Even if big companies do get involved, beating "StarCraft" will require breakthroughs we haven’t seen before. Deep learning — the seemingly miraculous technique of feeding computers extremely large sets of data and letting them find patterns — was central to Google solving "Breakout" and other simple games; it helped Facebook understand "StarCraft" combat; and it played a significant role in cracking go. And yet …
"I have a feeling this is not going to work so well for "StarCraft," Togelius says. "You need planning to play this complicated game, and these algorithms, deep nets, are not very suited to it."
Some games are hard, some are easy
While "StarCraft" is the white whale, plenty of videos games present their own AI challenge.
Turn-based strategy games like "Civilization" require similar strategic decisions, often with more long-term planning, but less rapid unit control.
"We don’t have very strong playing 'Civilization' agents but they haven’t done that much work into it," Togelius says.
"In my opinion, a game like 'Civilization' would be strictly easier for AI to beat than a game like 'StarCraft,'" Churchill says.
Can bots play "Civilization" better than humans? Ominous question. 2K Games/Firaxis
What about "League of Legends," the popular game where players control single heroes in complex team battles?
"I have talked to certain people who think that it would be really easy to make a 'League of Legends' AI that could beat the world champions, but I don’t necessarily agree," Churchill says.
"It would be easier than 'StarCraft' in the sense that you don’t have so many different levels of control, but you’d still have the issue of teamwork, which is very complex," Togelius says.
Can bots win at "League of Legends"? YouTube/Riot
"FIFA" and other sports games could be difficult, too. As with "StarCraft," they require control of an extremely high number of variables.
"You have 11 players, and if you say each player can do one of 4 different things, then your number of possible actions is four to the power of 11 — which is about 4 million," Togelius says. For comparison, he notes, chess players choose from around 35 possible moves every term, go players from around 300.
For first-person shooters like "Call of Duty" and "Halo," being able to program a bot with perfect aim is a huge advantage.
"Some people think if you have perfect aim, then AI will never lose," Churchill says. "But others say there are strategic elements of the game that can overcome perfect aim."
Fighting games like "Street Fighter" are relatively easy for bots.
"Unfortunately I think too much of the challenge is in having fast reactions, and you can have arbitrarily fast reactions if you are a computer," Togelius says.
Platformers are relatively easy too.
For instance: "’Super Mario Bros’ is essentially solved, at least for linear levels," Togelius wrote in an email.
This 2009 AI was able to crush "Super Mario Bros" (red lines show paths being evaluated). Robin Baumgartner
Role-playing games can be tricky.
"Skyrim" requires "understanding narrative" and "a wide variety of cognitive skills," Togelius writes online.
As for card games — remember those? — they still pose some interesting questions. Two-person limit Texas Hold’em has been solved, but group games and unlimited betting options are still a problem. In Bridge, bots haven’t mastered deceptive play, bidding, or reading opponents and still can’t beat the world champions.
The playful linguistics of crossword puzzles are a challenge as well.
And we’re not even getting into robotics (Cristiano Ronaldo is way better than robots at soccer).
The ultimate challenge is general game AI
A few years ago, Togelius noticed a problem with video game AI competitions. People inevitably start programming bots with extensive human-knowledge about how to beat a game, rather than focusing on true artificial intelligence.
"People submit more and more domain-specific bots — in the car-racing competition you had people submitting bots that started hard-coding elements of tracks and cars and so on — and the actual AI part gets relegated to smaller and smaller roles," Togelius says.
It was this frustration that led him to start the General Video Game AI (GVGAI) competition in 2014. In this competition, players submit bots that compete in an unknown set of ten simple games. To win, the bots have to be flexible and adaptable — something closer to humans.
"General intelligence is not the capacity to do one thing, it’s the capacity to do almost anything you’re faced with," Togelius said.
For now, the bots in GVGAI aren’t great.
"On most games, [they are] not human-level," Togelius says. "On fairly simple shooters, such as 'Space Invaders, you have bots that are better than humans, but on things that require long-term planning, they are often considerably under human level."
Give them time. Togelius says interest in the competition is growing fast. Notably, one of its sponsors is Deepmind, the Google subsidiary behind AlphaGo.
"Space Invaders" is easy for bots. Midway
Human-machine teams could be the future
As humans are surpassed in game after game, we can hold onto one reassuring fact: centaurs could do better than humans or computers.
Centaurs, a term for human-machine pairings taken from the mythological creature that was half-human-half-horse, have already proven more effective than humans or computers at chess (at least when given enough time, at least for now).
"The human uses his or her intuition and ideas about what to do and ideas about long-term strategies and uses the computer to verify the various things and to do simulations," Togelius says.
A similar pattern might hold true in "StarCraft"— and beyond.
"I could very much imagine a future where we have centaur teams in 'StarCraft,' where you have a human making high-level decisions and various AI agents at different levels executive them," Togelius says. "That is also how I imagine the place AI technologies will more and more take in our society."
Other people have drawn similar conclusions. Togelius pointed to roboticist Rodney Brooks, who predicts in the classic book "Flesh and Machines" that future humans "will have the best that machineness has to offer, but we will also have our bioheritage to augment whatever level of machine technology we have so far developed."
