Can AlphaGo beat Imperial?

Tweet

2016.07.05

DeepMind's Demis Hassabis recently singled out StarCraft as a potential challenge for AlphaGo. It's a fascinating, and bold, target. StarCraft is a partial information game with many different short- and long-term trade offs, and because you have so many units, ways to position them, research options, buildings, resources, StarCraft's game tree size dwarfs Go's. Compared to chess, Go is complex, but in the grand scheme of things, a game involves roughly 75 decisions with less than 361 legal moves. I'm not saying this to diminish AlphaGo's achievement. On the contrary, I never thought an AI would dominate a match against a top player this soon. It seems like yesterday that Go AIs were, at best, playing at the level of good amateurs.

Still, how far can AlphaGo go? Or perhaps more generally, how far can deep reinforcement learning go? I'd love to see hard numbers, but the game tree size of the {Starcraft, Fire Emblem, Civilization} of this world must be humongous. Players have to make several decisions every seconds, if not several decisions per second. Yet, personally, I'm equally interested in seeing how far deep learning-based reinforcement learning can go for board games. Chess is certainly on the table, but what about other board games? Take one of my favorites: Imperial.

So what the hell is Imperial? Like chess and Go, Imperial is a deterministic perfect-information game. While Go is complex, it is relatively "flat" in the sense that the game is a grid with one object (the stone). In contrast, Imperial has many different objects. Military units and factories make the game look like a standard variation of Risk, but the game has a twist: players are not assigned to a country at the beginning of the game. Countries make their moves in turn, but who control the country at any given time is determined by who invested the most in it. This simple rule creates complex strategies where players will take control of countries in poor shape to help their investments elsewhere.

I doubt Google cares about an obscure (yet awesome) board game like Imperial, but maybe they should, because (I think) it highlights a bit of a blind spot for deep reinforcement learning. The main issue with Imperial is not that the game is very complex (it isn't), or that a particular rule would trip the AI. The issue is simply that we have no large databases of games to feed to an algorithm. Data deluge or not, it's typical to have little data when faced with a new problem, and it's not the end of the world for all machine learning approaches. We can encode a rough model ourselves, something fairly common with probabilistic graphical and statistical relational models, or by transferring knowledge from a similar problem.

Putting together a reinforcement learning agent based on my (upcoming) open-source C++ library for statistical relational learning is very high on my priority list, we'll see if it can beat Imperial. That said, I'd also like to see deep reinforcement learning tackle this kind of problem. After all, transfer learning is high on the radar of deep learning researchers, and we can't really talk of general intelligence as long as the A.I. needs to learn everything from 0.

let world = "世界" in print $ "Hello " ++ world ++ "!"