It is currently Thu Mar 28, 2024 10:31 pm

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 39 posts ]  Go to page 1, 2  Next
Author Message
Offline
 Post subject: Go and AI
Post #1 Posted: Fri Feb 20, 2015 9:58 am 
Lives in gote

Posts: 448
Liked others: 5
Was liked: 187
Rank: BGA 3 dan
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.


This post by Charles Matthews was liked by 2 people: Boidhre, Joaz Banbeck
Top
 Profile  
 
Offline
 Post subject: Re: Go and AI
Post #2 Posted: Fri Feb 20, 2015 10:06 am 
Judan
User avatar

Posts: 5539
Location: Banbeck Vale
Liked others: 1103
Was liked: 1456
Rank: 1D AGA
GD Posts: 1512
Kaya handle: Test
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

Top
 Profile  
 
Offline
 Post subject: Re: Go and AI
Post #3 Posted: Fri Feb 20, 2015 10:50 am 
Judan

Posts: 6725
Location: Cambridge, UK
Liked others: 436
Was liked: 3719
Rank: UK 4 dan
KGS: Uberdude 4d
OGS: Uberdude 7d
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.


Last edited by Uberdude on Fri Feb 20, 2015 10:55 am, edited 1 time in total.

This post by Uberdude was liked by: jeromie
Top
 Profile  
 
Offline
 Post subject: Re: Go and AI
Post #4 Posted: Fri Feb 20, 2015 10:52 am 
Oza

Posts: 2356
Location: Ireland
Liked others: 662
Was liked: 442
Universal go server handle: 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)

Top
 Profile  
 
Offline
 Post subject: Re: Go and AI
Post #5 Posted: Fri Feb 20, 2015 10:55 am 
Oza

Posts: 3647
Liked others: 20
Was liked: 4626
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?

Top
 Profile  
 
Offline
 Post subject: Re: Go and AI
Post #6 Posted: Fri Feb 20, 2015 10:57 am 
Lives in sente
User avatar

Posts: 761
Liked others: 152
Was liked: 204
Rank: the k-word
Do they accept monetary bets against that prediction? I'm willing to bet a few grand.

Top
 Profile  
 
Offline
 Post subject: Re: Go and AI
Post #7 Posted: Fri Feb 20, 2015 11:02 am 
Lives with ko
User avatar

Posts: 230
Location: London
Liked others: 288
Was liked: 65
Rank: OGS 2k
OGS: Joellercoaster
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:

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

Top
 Profile  
 
Offline
 Post subject: Re: Go and AI
Post #8 Posted: Fri Feb 20, 2015 11:06 am 
Oza

Posts: 2356
Location: Ireland
Liked others: 662
Was liked: 442
Universal go server handle: Boidhre
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.

Top
 Profile  
 
Offline
 Post subject: Re: Go and AI
Post #9 Posted: Fri Feb 20, 2015 11:11 am 
Oza

Posts: 2356
Location: Ireland
Liked others: 662
Was liked: 442
Universal go server handle: Boidhre
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 :batman:


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

Top
 Profile  
 
Offline
 Post subject: Re: Go and AI
Post #10 Posted: Fri Feb 20, 2015 11:15 am 
Lives in sente
User avatar

Posts: 761
Liked others: 152
Was liked: 204
Rank: the k-word
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.

Top
 Profile  
 
Offline
 Post subject: Re: Go and AI
Post #11 Posted: Fri Feb 20, 2015 11:25 am 
Judan

Posts: 6725
Location: Cambridge, UK
Liked others: 436
Was liked: 3719
Rank: UK 4 dan
KGS: Uberdude 4d
OGS: Uberdude 7d
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.

Top
 Profile  
 
Offline
 Post subject: Re: Go and AI
Post #12 Posted: Fri Feb 20, 2015 11:57 am 
Lives in sente
User avatar

Posts: 761
Liked others: 152
Was liked: 204
Rank: the k-word
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.

Top
 Profile  
 
Offline
 Post subject: Re: Go and AI
Post #13 Posted: Fri Feb 20, 2015 12:01 pm 
Oza

Posts: 3647
Liked others: 20
Was liked: 4626
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.

Top
 Profile  
 
Offline
 Post subject: Re: Go and AI
Post #14 Posted: Fri Feb 20, 2015 12:03 pm 
Judan

Posts: 6087
Liked others: 0
Was liked: 786
"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.

Top
 Profile  
 
Offline
 Post subject: Re: Go and AI
Post #15 Posted: Fri Feb 20, 2015 12:11 pm 
Lives with ko

Posts: 248
Liked others: 23
Was liked: 148
Rank: DGS 2 kyu
Universal go server handle: 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?

Top
 Profile  
 
Offline
 Post subject: Re: Go and AI
Post #16 Posted: Fri Feb 20, 2015 12:49 pm 
Lives in gote

Posts: 448
Liked others: 5
Was liked: 187
Rank: BGA 3 dan
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?


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.

Top
 Profile  
 
Offline
 Post subject: Re: Go and AI
Post #17 Posted: Fri Feb 20, 2015 12:55 pm 
Dies with sente
User avatar

Posts: 101
Location: Geneva, Switzerland
Liked others: 66
Was liked: 57
Rank: DGS 6k
KGS: Codexus
DGS: Codexus
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...

Top
 Profile  
 
Offline
 Post subject: Re: Go and AI
Post #18 Posted: Fri Feb 20, 2015 2:42 pm 
Lives in gote

Posts: 448
Liked others: 5
Was liked: 187
Rank: BGA 3 dan
Codexus wrote:
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".

Top
 Profile  
 
Offline
 Post subject: Re: Go and AI
Post #19 Posted: Fri Feb 20, 2015 4:05 pm 
Oza

Posts: 3647
Liked others: 20
Was liked: 4626
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.

Top
 Profile  
 
Offline
 Post subject: Re: Go and AI
Post #20 Posted: Sat Feb 21, 2015 3:04 am 
Lives in gote

Posts: 448
Liked others: 5
Was liked: 187
Rank: BGA 3 dan
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.

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 39 posts ]  Go to page 1, 2  Next

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: std and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group