Go and AI

[Charles Matthews]

I attended a talk in Cambridge yesterday evening by Demis Hassabis, now of Google DeepMind. It was about the company's work in Artificial (General) Intelligence. The announcement that go will be a solved problem, in Artificial Intelligence terms, by about 2016, was somewhat surprising.

It is interesting in itself, and particularly so for me since I was Demis's go teacher when he was a Cambridge undergraduate. Apparently they have a machine currently that is about my level. It should be noted that this is not by refining the kinds of techniques go programmers have applied in the past.

I may be in a position to assess what they have done so far from personal experience, at some future point. You'd have to get the whole talk to understand the context. What has been trailed in the press is the same type of algorithm learning Space Invaders.

[Joaz Banbeck]

Did he mention any other problems that are about the same complexity as go that he believed would be solved also?

If he mentioned only go, I'm really sceptical.

[Uberdude]

Did he mention any other problems that are about the same complexity as go that he believed would be solved also?

If he mentioned only go, I'm really sceptical.

http://www.cs.toronto.edu/~cmaddis/pubs/deepgo.pdf

Here is a paper co-authored by a bunch of Google Deepmind folks (including Aja Huang who you might know from KGS bot tournaments) on using deep convoluted neural networks to play Go. There is also a group at Edinburgh who did something similar. There was some discussion on this over at viewtopic.php?f=18&t=11207 (the google one mentioned in post 32) and a lot more on the computer go mailing list (Edinburgh one, Toronto/Google one . I presume this is the work to which Demis Hassabis was referring.

[Boidhre]

Similar to that AI that solved heads-up limit hold'em? (Not sure if solved is the right word there given the method used)

[John Fairbairn]

The announcement that go will be a solved problem, in Artificial Intelligence terms, by about 2016,

I know all the words but have no idea what this means. I'm guessing it could just mean they may know the true size of komi, not that a machine will beat all humans????

Also, if go is solved by 2016, shouldn't we expect chess to be solved tomorrow?

[palapiku]

Do they accept monetary bets against that prediction? I'm willing to bet a few grand.

[joellercoaster]

Similar to that AI that solved heads-up limit hold'em? (Not sure if solved is the right word there given the method used)

Different.

Don't know much about the algorithms behind the poker player, but I'm pretty sure it's unrelated to the Deep Convoluted Neural Networks stuff - I think the poker player uses a class of algorithm called "Counterfactual Regret Minimisation", which I am about to go and read about to figure out what that means

[Boidhre]

The announcement that go will be a solved problem, in Artificial Intelligence terms, by about 2016,

I know all the words but have no idea what this means. I'm guessing it could just mean they may know the true size of komi, not that a machine will beat all humans????

Also, if go is solved by 2016, shouldn't we expect chess to be solved tomorrow?

The headlines said they'd cracked poker but the reality was a very restricted form chosen to reduce the amount to learning time needed was used: http://www.nature.com/news/game-theoris ... er-1.16683

It's an extremely impressive method but I'd be amazed if they have a version of it that could solve 19x19 go in my lifetime with current technology. If they can 9x9 though it would be very impressive.

[Boidhre]

Similar to that AI that solved heads-up limit hold'em? (Not sure if solved is the right word there given the method used)

Different.

Don't know much about the algorithms behind the poker player, but I'm pretty sure it's unrelated to the Deep Convoluted Neural Networks stuff - I think the poker player uses a class of algorithm called "Counterfactual Regret Minimisation", which I am about to go and read about to figure out what that means

Thanks. I'd be interested to hear how they're different.

[palapiku]

From the introduction to that paper (http://www.cs.toronto.edu/~cmaddis/pubs/deepgo.pdf):

1. They claim that their program is 6d, purely based on the fact that it predicted the next move in professional games 55% of the time. That's not actually very impressive, without knowing what kind of move it makes the other 45% of the time. Not 6d. Indeed in the last paragraph of the paper they mention that the program played as if it misjudged the status of groups, so it basically plays shape and doesn't read, just as you'd expect a neural network to behave.

2. They claim that their program is on par with monte carlo programs, but those programs were only given 10,000 rollouts per move, not playing at full strength. Only an old, weak MC program was given 100,000 rollouts. Again, not very impressive and not actually on par.

The rest of paper is actually solid and very promising, but the introduction feels misleading regarding how much they actually achieved. Still, this might be a significant breakthrough. Probably not by 2016 though.

[Uberdude]

1. They claim that their program is 6d, purely based on the fact that it predicted the next move in professional games 55% of the time.

No they don't. They claim the move prediction success rate is similar to that of a 6d.

[palapiku]

No they don't. They claim the move prediction success rate is similar to that of a 6d.

Sure, which is misleading because in the end the only rank that's explicitly mentioned is 6d. But the program is not 6d. I can't believe this isn't intentional. And "move prediction success rate" doesn't seem like an interesting statistic anyway, it feels like it was just chosen because it makes them look better on paper.

[John Fairbairn]

They claim that their program is 6d, purely based on the fact that it predicted the next move in professional games 55% of the time.

Not having read the paper (too hard), this seems a little suspect as a proof of skill. Isn't it just the easy-wins part of the task? By predicting that the next move is adjacent to or one point away from the last move you can restrict the options enormously, and you can restrict them further by applying a sort of minimax on liberties, and so on. So you can get halfway there with just with a pencil and paper.

[RobertJasiek]

"Solved AI problem" means much more than 1) "computer stronger than strongest human". It even means much more than 2) "stating one correct solution". It means 3) "knowing and explaining all correct solutions". I'd be more than surprised if the weakest form (1) would be achieved in 2016. As a researcher in the stronger forms, I expect (2) to remain unsolved for about 400 years if today's techniques continue to be applied. It could be faster if theoretical informatics learned how to let programs do successful research. Nevertheless, my aforementioned estimate is optimistic and presumes that the 19x19 problem can be solved by conceptual devide&conquer. We have no guarantee for this yet; the complexity could be much greater.

IOW, whoever makes such statements about 2016 does not know what he is talking about.

[Polama]

There are 4 types of "solutions" to games.

Ultra weakly solved games: We can prove which player should win (or tie) from the start position, but can't give any advice on how to do that.

Weakly solved games: We can prove each move in a sequence is optimal for both players. However, we can't necessarily provide the correct response to non-optimal moves, so an algorithm might achieve an inferior result if the opponent makes a mistake.

Strongly solved games: we can provide perfect play from any position, even where one player has made a mistake.

Press Release Solved games: An AI can play it well.

The poker playing algorithm and any go solution by 2016 would be press release solved. Personally, I don't think Go will ever be weakly solved, but who knows?