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.

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.

_________________
Help make L19 more organized. Make an index: https://lifein19x19.com/viewtopic.php?f=14&t=5207

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.

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

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?

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

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

_________________
Confucius in the Analects says "even playing go is better than eating chips in front of tv all day." -- kivi

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.

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

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.

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.

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.

"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.

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?

I'm sure what he meant was at the level of Deep Blue and chess. The wording is mine, of course. Too much is being read into it verbally (a 19x19 failing, indeed). The only clear prediction made is of dramatic progress in level.

The thing is that Demis does actually know something about traditional games.

I think in this context it was meant as "it can play the game as well as human champions". At least this the claim I have been hearing lately: that within a few years, computers will beat humans at go.

The new piece of the puzzle is the so called "deep learning". From what I have seen so far that seems to be the same as good old neural networks but apparently now they work much better. After training them with a large data set of human games, they are apparently not bad at predicting the likely next move.

That alone does not make a go AI that is stronger than current programs. But the idea would be to combine that with the Monte-Carlo Tree Search algorithm used in the current generation of go AIs. So basically instead of playing random games, the MCTS would use the neural network to get its candidate moves. Which could possibly result in a pro level go AI according to some people. (that seems a bit of a leap of faith to me but it's possible)

In that sense, the way to build a champion level go AI has been almost solved from a research point of view, and all that's left is some software engineering to actually combine the parts

I'm not entirely convinced this is the end of the story...

Nor I. Odd that no one's reaction in this thread is "good for the game".

But no-one appears to have said "bad for the game" either. My guess is that people in the games world have already absorbed the chess experience and would just see a go computer as another tool - in other words, be rather neutral.

That said, there is an abiding problem with chess computers in that they can't explain (or even actually) prove to humans why one move is better than another. Conceivably, neural networks might shed some insight for a human, but the present paper talks about Monte Carlo to shore up the bulwarks, so this research doesn't seem to be going in a promising direction for providing illumination. Hence, it probably isn't specially good for the game except, like Deep Blue, for a passing moment of PR.

With the difference that it is rare to find a person who hasn't heard of chess; while the average person hasn't heard of go (in the West). The "Google takes seriously" cachet is quite something.