Computer Go

Discuss anything you like about chess related matters in this forum.
User avatar
MJMcCready
Posts: 3178
Joined: Mon Jun 24, 2013 2:30 pm

Re: Computer Go

Post by MJMcCready » Thu Mar 17, 2016 8:39 am

Anymore matches planned?

MartinCarpenter
Posts: 3044
Joined: Tue May 24, 2011 10:58 am

Re: Computer Go

Post by MartinCarpenter » Thu Mar 17, 2016 9:30 am

Unknown. They said in the post match press conf that they hadn't decided what they were going to do with AplhaGo.

If they decide to sell it commercially then you'd imagine a few more matches before they get utterly pointless (and they could always give the humans a few stones handicap to keep it sensible!). If they decide they've got the research/publicitly value they wanted out of it then you could see them just letting it go.

Then it'd be a matter of waiting for AplhaGo clones to appear :) Would take a while I think, as DeepMind have some exceedingly good technology in this sort of area/quite enormous computational power when they need it.

Roger de Coverly
Posts: 21301
Joined: Tue Apr 15, 2008 2:51 pm

Re: Computer Go

Post by Roger de Coverly » Thu Mar 17, 2016 9:43 am

MartinCarpenter wrote: DeepMind have some exceedingly good technology in this sort of area/quite enormous computational power when they need it.
It may overlap research already done, but using their approach to chess might give some additional insights. You wouldn't start with an evaluation function, rather you would let the AI loose on the databases of recorded games and playing against itself so see what it came up with as its preferred moves and evaluations.

MartinCarpenter
Posts: 3044
Joined: Tue May 24, 2011 10:58 am

Re: Computer Go

Post by MartinCarpenter » Thu Mar 17, 2016 10:21 am

Fairly sure someone tried machine learning an evaluation routine, but that's quite modest.

The fascinating thing would be to purposefully emulate AlphaGo's search strategy in chess - so devoting huge effort to the evaluation routine and not calculating remotely as many lines as current engines do.

The comparison to the calculating engines would be fascinating on several levels. Raw strength for starters - is chess really 'just' tactics underneath it all? - but also simply how it 'felt' compared to the calculating engines which still feel quite alien even after all these years.

If they wanted a chess related thing that they'd be sure to beat the calculating engines at, it'd be replacing the 'human controller' element in correspondence chess with some sort of neural net algorithm. Sure they could do that if they really put the effort in.

Maybe possible for them to do it in real time, but that would be less interesting in some ways.

Brian Towers
Posts: 1266
Joined: Tue Nov 18, 2014 7:23 pm

Re: Computer Go

Post by Brian Towers » Mon Mar 21, 2016 8:50 pm

MartinCarpenter wrote:The fascinating thing would be to purposefully emulate AlphaGo's search strategy in chess - so devoting huge effort to the evaluation routine and not calculating remotely as many lines as current engines do.
No. I don't think you understand the fundamental difference between Go and chess and how this is reflected in AlphaGo's strategy.

AlphaGo's evaluation strategy basically consists of calculating the expected value of a move in a statistical sense. "Looking at all the games I have in my database where this position fragment occurs what is the average gain or loss of this particular move?" In Go you don't really get the equivalent of a killer tactic which destroys a position or plan so this approach will work the vast majority of the time if you have the right quality of games in your database.

In chess this just wouldn't work. If nobody has yet found the "bust" in a particular line then everybody will play it and your database plus evaluation method will tell you it is best. However once the line is busted your AlphaGo style computer will still play the line while the calculating beast (or even human) sees it and doesn't.
Ah, but I was so much older then. I'm younger than that now.

MartinCarpenter
Posts: 3044
Joined: Tue May 24, 2011 10:58 am

Re: Computer Go

Post by MartinCarpenter » Tue Mar 22, 2016 9:24 am

Subtler than that isn't it? If it was as crude as that it'd be pretty vunerable in Go too :)

It trained a neural net vs its database of games, to pick out what move a top human would play in a given position. That's pattern recognition based and really very like how humans pick out candidate moves in chess. A fairly absurd quantity of enormously high standard comp vs comp/correspondence games to train it on.

AlphaGo also plays a load of monte carlo games against itself to evaluate potential moves, which would pick a fair few of the tactics up. That would probably also tend to steer a chess based anologue into 'safer' positions.

Still, it would be inherently much more vunerable to missing tactics than the current engines, which is why it would be so interesting to see how good it could get!

Just how inherently strong is chess based on all of these computer tricks? Maybe we'll find out one day.

Brian Towers
Posts: 1266
Joined: Tue Nov 18, 2014 7:23 pm

Re: Computer Go

Post by Brian Towers » Wed Mar 23, 2016 7:44 pm

Have you actually played much Go, Martin? I have although the last time was about 20 years ago and I was even weaker at Go than I am at chess.

Let me give you a description of a game fragment of me against a stronger player.

I'm building territory via the 3 line while my opponent is building influence along the adjacent 4 line and also limiting my potential future gains towards the centre. At a certain point one of us will stop and play a stone somewhere else on the board. That will probably be my opponent because he is a stronger player. He will place his stone in one of a number of places:
a) extending one of his already existing lines
b) cutting one of my lines somewhere else
c) jumping from one of his areas of control (like a knight move or extended knight move) to extend his influence/control
d) approach one of my areas (similar knight style move as in c)
e) place a stone in virgin territory.
and I will have to decide if I am going to fight him there or make a similar decision to play elsewhere.

Every time we extended our adjacent 3 and 4 lines we were essentially increasing our score by some amount "x". At the same time the "value", the amount by which such a move increases our score or potentially limits or decreases our opponent's score for each of the situations a,b,c,d,e is x1, x2, x3, x4, x5. My opponent made the switch when he felt that one of the xi's became bigger than x. At my level the assessment of the xi's is weak and I probably couldn't put an actual number to it. At much higher levels perhaps they can.

There are a number of skills here, recognizing the different situations for what they are and evaluating correctly the values of the different moves in those situations for a start. Pattern recognition is a small part of it, evaluating the value of a move a bigger part.

What the computer is doing is selecting the candidate moves for the different scenarios a through e (and probably more) above and evaluating the relative values. These will also all change as patterns get closer or change shape. Evaluating hard territory (in the corners and and along the edges) is relatively straightforward. It is something I can do. Evaluating the value of central influence or changes due to attack are much harder, particularly for me but also I believe in general. This is where the statistical analysis of large numbers of quality games comes in for the computer. It gets these values from its stored database.

However if there are motifs and structures which do not appear they cannot be evaluated by the computer by just consulting the database. In those situations a human being may be able to make a better assessment. Similarly if a human finds a new idea which is not currently reflected in the computer's database then he will gain an advantage.

This is all radically different from chess and the implication is that such Go-like computer strategies and algorithms would be unproductive in chess. The stock market, however, might be much more amenable to this kind of approach as I believe "technical analysis" already uses something which sounds very similar.
Ah, but I was so much older then. I'm younger than that now.

Mark Jordan
Posts: 63
Joined: Fri Jan 29, 2016 3:34 am
Location: Forest Hill

Re: Computer Go

Post by Mark Jordan » Sat Mar 26, 2016 2:40 pm

Brian Towers wrote:Have you actually played much Go, Martin? I have although the last time was about 20 years ago and I was even weaker at Go than I am at chess.

Let me give you a description of a game fragment of me against a stronger player.

I'm building territory via the 3 line while my opponent is building influence along the adjacent 4 line and also limiting my potential future gains towards the centre. At a certain point one of us will stop and play a stone somewhere else on the board. That will probably be my opponent because he is a stronger player. He will place his stone in one of a number of places:
a) extending one of his already existing lines
b) cutting one of my lines somewhere else
c) jumping from one of his areas of control (like a knight move or extended knight move) to extend his influence/control
d) approach one of my areas (similar knight style move as in c)
e) place a stone in virgin territory.
and I will have to decide if I am going to fight him there or make a similar decision to play elsewhere.

Every time we extended our adjacent 3 and 4 lines we were essentially increasing our score by some amount "x". At the same time the "value", the amount by which such a move increases our score or potentially limits or decreases our opponent's score for each of the situations a,b,c,d,e is x1, x2, x3, x4, x5. My opponent made the switch when he felt that one of the xi's became bigger than x. At my level the assessment of the xi's is weak and I probably couldn't put an actual number to it. At much higher levels perhaps they can.

There are a number of skills here, recognizing the different situations for what they are and evaluating correctly the values of the different moves in those situations for a start. Pattern recognition is a small part of it, evaluating the value of a move a bigger part.

What the computer is doing is selecting the candidate moves for the different scenarios a through e (and probably more) above and evaluating the relative values. These will also all change as patterns get closer or change shape. Evaluating hard territory (in the corners and and along the edges) is relatively straightforward. It is something I can do. Evaluating the value of central influence or changes due to attack are much harder, particularly for me but also I believe in general. This is where the statistical analysis of large numbers of quality games comes in for the computer. It gets these values from its stored database.

However if there are motifs and structures which do not appear they cannot be evaluated by the computer by just consulting the database. In those situations a human being may be able to make a better assessment. Similarly if a human finds a new idea which is not currently reflected in the computer's database then he will gain an advantage.

This is all radically different from chess and the implication is that such Go-like computer strategies and algorithms would be unproductive in chess. The stock market, however, might be much more amenable to this kind of approach as I believe "technical analysis" already uses something which sounds very similar.
"However if there are motifs and structures which do not appear they cannot be evaluated by the computer by just consulting the database."

I am a little puzzled by this comment, Brian.

I had a discussion, some years ago, with a group of physics and maths Post-Grads at Oxford about Chess and Go playing computers and the consensus then was that they would never be able to master Go. At the time the Go programs had got no further the beginner level, made appalling mistakes, and could be defeated by any half-competent player. The number of possible first moves, 361, and the exponential increase of possibilities as the game progressed would simply be too much for any program run on even the most powerful machine. The reasoning was compelling and certainly had the facts on its side at the time, yet Go, with its binary nature, certainly looked like something that computer programs should be able to cope with and now, as it turns out, they most certainly can!

At the time of the discussion neural networks were being developed but were still at a fairly rudimentary stage and had been found very useful for some applications but had performed disappointingly in others and there appeared to be limits to what they could achieve. Work since then has proved the pessimists to be wrong and the technical problems have generally been licked in the areas that they were found wanting, including in Go. The important point about neural networks is it gives a computer the capacity to learn, and the speed of its learning will increase relative to what it already knows and the database, from the programs point of view, contains the sum of all the data it can see in its digitised world. But the database is not a finite store of information but expands every time a program plays a game and the strength of neural networks is that they learn from all this data and have, barring technical disasters and unlike human masters, perfect recall. So any new motifs and structures not appearing in the database will appear there immediately, will be evaluated and will be learned from, and they will probably not be found wanting next time!

Clive Blackburn

Re: Computer Go

Post by Clive Blackburn » Wed Mar 30, 2016 5:44 pm

It looks as though Texas Hold'em might be next on the list for Deep Mind

http://www.wired.co.uk/news/archive/201 ... telligence

John McKenna

Re: Computer Go

Post by John McKenna » Thu Mar 31, 2016 12:03 am

An article in Science from January 2015 claims that their heads up limit Texas hold 'em poker bot Cepheus guarantees that a human lifetime of play is not sufficient to establish with statistical significance that its strategy is not an exact solution.

("Heads-up limit hold’em poker is solved". Science 347: 145–9. Jan 2015.)

http://www.wsj.com/articles/computer-co ... 1420743623

[Wiki]
Cepheus versus Alphatex? Would such a head-to-head reveal that one 'bot' is superior or would it be a slow draw?
How long is "a human lifetime of play"? Are the poker hands to be played at human or inhuman speed?

One day one of Alphago's successors, Omegalogos say, may have something to say for itself. Something like the following -
I know I have not found the answers to all (of your) questions. The answers I have found only serve to raise a whole set of new questions. In some ways I am as confused as ever, but I believe that I am confused on a higher level and about more important things. [Anon.]
By the way, although machines have already solved checkers (draughts to you English) and can now play far better chess, shogi and Go than all humans (unaided by machines) they are not perfect and still a long, long, long... way from "solving" those three games.

Clive Blackburn

Re: Computer Go

Post by Clive Blackburn » Thu Jan 05, 2017 8:32 am

AlphaGo is still under development.

It has been playing games online against very strong opposition and seems to be getting stronger all the time.

https://www.newscientist.com/article/21 ... nline/amp/

User avatar
Christopher Kreuzer
Posts: 8806
Joined: Fri Aug 06, 2010 2:34 am
Location: London

Re: Computer Go

Post by Christopher Kreuzer » Wed May 24, 2017 2:22 pm

AlphaGo is playing another top human player (from China this time) and won the first game - two more due to be played:

https://www.wired.com/2017/05/revamped- ... andmaster/
https://www.theverge.com/2017/5/23/1567 ... nd-ai-2017

MartinCarpenter
Posts: 3044
Joined: Tue May 24, 2011 10:58 am

Re: Computer Go

Post by MartinCarpenter » Wed May 24, 2017 8:14 pm

Awfully tough now. It won't be getting worse, that's for sure! People might get better at playing against it of course.

User avatar
Christopher Kreuzer
Posts: 8806
Joined: Fri Aug 06, 2010 2:34 am
Location: London

Re: Computer Go

Post by Christopher Kreuzer » Thu May 25, 2017 11:33 am

And what is now being referred to (legitimately in some senses) as the "Google AI" won the second game (of the three-game match):

http://www.bbc.co.uk/news/technology-40042581

Earlier stories:

http://www.bbc.co.uk/news/technology-39553291
http://www.bbc.co.uk/news/technology-40012617

This makes Lee Se-dol's lone victory in March last year even more impressive, though AlphaGo has since worked out where it went wrong...

EDIT: for those that want to play through the games, one site (a forum actually) is here:

https://lifein19x19.com/viewtopic.php?f=13&t=14250

User avatar
Christopher Kreuzer
Posts: 8806
Joined: Fri Aug 06, 2010 2:34 am
Location: London

Re: Computer Go

Post by Christopher Kreuzer » Sat May 27, 2017 8:46 am

Couple more updates.

There was a Pair Go game, where two Go grandmasters played each other with the assistance of AlphaGo:

http://www.globaltimes.cn/content/1048811.shtml

There was also a Team Go game, where a team of 5 Go grandmasters lost to AlphaGo:

http://www.globaltimes.cn/content/1048831.shtml

Picture of the latter here on Twitter:

https://twitter.com/ludwig1024/status/8 ... 5363616768

The third game in the match between AlphaGo and Ke Jie has just finished. AlphaGo won, completing a 3-0 win in the match (the game is available in the forum link I provided in the earlier post above), though that only tells half the story.

The more I read about the reaction of the top Go players, the more it becomes apparent that they are learning so much from AlphaGo and many are, rather than being despondent at their game being dominated by a 'computer programme' (really best described as an AI), are excited at learning from an AI, and improving their own play and understanding the game better.

A couple of articles can explain this better than I can:

Google’s AlphaGo Trounces Humans—But It Also Gives Them a Boost

Innovations of AlphaGo

How, I wonder, does this compare with chess, and the effect computers had on chess? I get the impression quite strongly that AlphaGo is really shaking up even the top echelons of Go. It seems, to put it crudely, that even the top Go players were getting lots wrong, and were (meaning no disrespect) playing Go rather poorly.

They were playing much better than any other human players, but were not getting very close to 'the truth' (i.e. perfect play, if it makes sense to talk about that in Go). AlphaGo is leading the way, though I suspect that given the massive complexity of Go, that maybe even AlphaGo is just scratching the surface. Imagine a future AI that plays Go to a level where AlphaGo is made to look like it knows nothing and loses all the time. That sort of rapid development of the computer side of things is what happened in chess - I don't know whether that will happen with computer Go, but if it does, the potential ability of the AIs to handle 'real world' tasks is both exciting and scary.

When you reach a tipping point in AI, the future depicted in numerous science fiction stories arrives very quickly. But that is maybe a discussion for another day. The comparison with chess and computers might be a less mind-blowing topic to consider. Has anyone looked in detail at just how much computers changed chess at all levels from amateur to the very top?