Tuesday, March 15, 2016

AlphaGo and the future of game AI

If you aren't familiar with the game of go (also called baduk, weiqi, and a few other names) the recent news of a computer beating a human grandmaster may seem kind of boring and irrelevant.  After all, haven't computers been routinely beating human grandmasters at chess since 2005?

Chess, ironically, has more complex rules than go.  You can learn how to play go in, literally, about five minutes.  Yet making a computer program that can play go at an even semi-professional level has proven to be impossible until just now.


Because you can't predict your way to victory in go and that's how the chess playing programs win.

Deep Blue won against Kasparov not by actually playing chess, but by predicting what would happen from each move.  There's only 64 squares on a chess board, each piece only moves in a limited number of ways, therefore there's only so many moves that can be made at any given moment.  Deep Blue could predict hundreds of moves into the future, pick the move that would give it the best outcome, and win.

That approach doesn't work with go simply becuase the play space is too big.  There are 64 squares in chess, and each piece can only move so many ways.  In go there are 361 spaces to play in, and any space can be played at any time.  That's just too much to predict.

As a result, go playing programs were never very good.  They can beat a beginner easily, they can challenge a mid level amateur, and even a lower ranking master player could beat them with no real difficulty.  The grandmasters never bothered playing a go program before (at least not in tournaments, I'd be surprised if they hadn't played a few in less public arenas just to see).

AlphaGo wins not by predicting but by actually playing, thinking, more like a human does.  It's a combination of two neural nets (one for strategic evaluation, one for local fights), some old school heuristic AI programming, and yes as much prediction as they could manage (humans try to predict too).

And it just beat one of the very best human go players in the world 4-1 in a five game match.

The team behind Deep Mind says that they're going to try turning their attention to StarCraft: Brood War.  Not StarCraft II, because of all the DRM and such they can't hook their program directly into SC2, while building a custom AI for SC:BW has been possible since it was released.

I have little doubt that they'll be able to make a very good StarCrat player out of Deep Mind.  There are more options in SC than in go, but at the same time its actually simpler from a certain standpoint.  And, of course, any computer will have a micro game that is just plain unbeatable.  I suppose for the sake of fairness they'll have to cap Deep Mind's APM, but even with an APM cap it'll doubtless have a better micro game than any human.  The only question then is strategy, and if Deep Mind can master the strategy of go, I think it'll win in StarCraft no problem.

Don't misunderstand, I love StarCraft, but compared to go it just isn't very strategically deep.

Personally I'd love to see how it does at Civilization.

Leaving aside the potential for developing actual general purpose AI, that is a human level self aware mind, what this means in the shorter term is the possibility of a genuinely challenging AI in single player games.

A much less complex version of the same sort of neural net program that they use with AlphaGo, in a decade or so when computer power makes that possible on your home rig, would allow for a single player opponent that is challenging without cheating.

Right now the only real way for game AI to be a challenge is by cheating.  StarCraft II, for example, allows its AI to have more resources, do more damage, take more damage, etc.  In Civilization the AI gets free resources, city bonuses, etc.  Name a game, if there's an AI that tries to be challenging, it almost certainly does so by allowing the AI to cheat.

Some games make this a central gameplay mechanic (AI Wars for example).  Others try not to talk much about it.  But they all do it.

For now anyway.

Right now Deep Mind is a hugely expensive, highly experimental, result of centuries of programmer time, and it requires a truly staggering amount of CPU just to work.  But give it a decade or so and all that will be possible to package into a game you buy for $60.  Or heck, a bit less than that for cloud based AI.

No comments:

Post a Comment