Life In 19x19 :: Go and AI

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.

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

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

Quote:

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?

Boidhre wrote:

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 :batman:

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.

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.

Quote:

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

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

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

Hence, it probably isn't specially good for the game except, like Deep Blue, for a passing moment of PR.

Author:	Charles Matthews [ Fri Feb 20, 2015 9:58 am ]
Post subject:	Go and AI
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.

Author:	Joaz Banbeck [ Fri Feb 20, 2015 10:06 am ]
Post subject:	Re: Go and AI
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.

Author:	Uberdude [ Fri Feb 20, 2015 10:50 am ]
Post subject:	Re: Go and AI
Joaz Banbeck wrote: 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.

Author:	Boidhre [ Fri Feb 20, 2015 10:52 am ]
Post subject:	Re: Go and AI
Similar to that AI that solved heads-up limit hold'em? (Not sure if solved is the right word there given the method used)

Author:	John Fairbairn [ Fri Feb 20, 2015 10:55 am ]
Post subject:	Re: Go and AI
Quote: 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?

Life In 19x19 http://www.lifein19x19.com/

Go and AI http://www.lifein19x19.com/viewtopic.php?f=10&t=11497	Page 1 of 2

Author:	palapiku [ Fri Feb 20, 2015 10:57 am ]
Post subject:	Re: Go and AI
Do they accept monetary bets against that prediction? I'm willing to bet a few grand.

Author:	joellercoaster [ Fri Feb 20, 2015 11:02 am ]
Post subject:	Re: Go and AI
Boidhre wrote: 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

Author:	Boidhre [ Fri Feb 20, 2015 11:06 am ]
Post subject:	Re: Go and AI
John Fairbairn wrote: Quote: 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.

Author:	Boidhre [ Fri Feb 20, 2015 11:11 am ]
Post subject:	Re: Go and AI
joellercoaster wrote: Boidhre wrote: 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.

Author:	palapiku [ Fri Feb 20, 2015 11:15 am ]
Post subject:	Re: Go and AI
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.

Author:	Uberdude [ Fri Feb 20, 2015 11:25 am ]
Post subject:	Re: Go and AI
palapiku wrote: 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.

Author:	palapiku [ Fri Feb 20, 2015 11:57 am ]
Post subject:	Re: Go and AI
Uberdude wrote: 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.

Author:	John Fairbairn [ Fri Feb 20, 2015 12:01 pm ]
Post subject:	Re: Go and AI
Quote: 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.

Author:	RobertJasiek [ Fri Feb 20, 2015 12:03 pm ]
Post subject:	Re: Go and AI
"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.

Author:	Polama [ Fri Feb 20, 2015 12:11 pm ]
Post subject:	Re: Go and AI
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?

Page 1 of 2	All times are UTC - 8 hours [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/

Author:	Codexus [ Fri Feb 20, 2015 12:55 pm ]
Post subject:	Re: Go and AI
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...

Author:	John Fairbairn [ Fri Feb 20, 2015 4:05 pm ]
Post subject:	Re: Go and AI
Quote: 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.

Author:	Charles Matthews [ Sat Feb 21, 2015 3:04 am ]
Post subject:	Re: Go and AI
John Fairbairn wrote: 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.