Author Topic: AlphaGo just beat one of the 5 best Go players in the world  (Read 10848 times)

LetterRip

  • Members
    • View Profile
AlphaGo just beat one of the 5 best Go players in the world
« on: March 09, 2016, 02:43:42 AM »
AlphaGo just beat Lee Sidol (Ranked somewhere between #5 and #3 of the worlds top Go players).  AlphaGo was also playing the white pieces (which move second) which is a significant disadvantage.  The pundits were predicting that Lee Sidol would win 5-0 or 4-1.  The strength that AlphaGo showed, suggests that it will likely be 5-1 or 4-1 in AlphaGos favor.

D.W.

  • Members
    • View Profile
Re: AlphaGo just beat one of the 5 best Go players in the world
« Reply #1 on: March 09, 2016, 09:45:40 AM »
I haven't been following this closely.  Is there a reason to be significantly more impressed than say chess computer vs. chess master competitions/tests?  I think I learned the rules of Go when I was VERY young, like elementary school young and don't remember how to play.  Are the possible iterations on moves and strategy just that much higher than chess that makes this particularly newsworthy?

TL;DR
Should I be more excited about this on the AI front?

LetterRip

  • Members
    • View Profile
Re: AlphaGo just beat one of the 5 best Go players in the world
« Reply #2 on: March 09, 2016, 12:46:02 PM »
DW,

go has a branching factor of around 200 per move, chess has a branching factor of around 20 - there are good heuristics and evaluation functions for evaluating a chess position, there are not really any good heuristics for evaluating a go position.  It was anticipated that beating a low level (2Dan) professional was 10 years away; and beating the best in the world might be 15-20 years away.

This has rocked the AI world - yeah it is a big deal :)

http://www.developereconomics.com/significance-alphago-golden-age-artificial-intelligence-just-dawned/

Miles Brundage argues that the significance of this milestone has been overstated

http://www.milesbrundage.com/blog-posts/alphago-and-ai-progress

http://www.nature.com/news/google-ai-algorithm-masters-ancient-game-of-go-1.19234

D.W.

  • Members
    • View Profile
Re: AlphaGo just beat one of the 5 best Go players in the world
« Reply #3 on: March 09, 2016, 12:54:17 PM »
Thanks for the run down.

TheDrake

  • Members
    • View Profile
Re: AlphaGo just beat one of the 5 best Go players in the world
« Reply #4 on: March 09, 2016, 02:25:30 PM »
AI in general languished for years after overpromising, now that it is delivering on natural language processing, image recognition, and other hard problems with deep neural networks it stands to put many millions of people out of a job.

LetterRip

  • Members
    • View Profile
Re: AlphaGo just beat one of the 5 best Go players in the world
« Reply #5 on: March 10, 2016, 03:38:19 AM »
The Go world is in shock.  AlphaGo just won the second game decisively and the pros are now expecting it to win the remaining three.  It appears to have reached the 'superhuman' level.  I'm curious what the DeepMind team estimates its Elo level at.

LetterRip

  • Members
    • View Profile
Re: AlphaGo just beat one of the 5 best Go players in the world
« Reply #6 on: March 10, 2016, 11:28:09 AM »
Before the first game the go Grandmaster was confidentially predicting he would win it 5-0 or perhaps 4-1.  After last nights match he said he is hoping he can win at least one game.

Seriati

  • Members
    • View Profile
Re: AlphaGo just beat one of the 5 best Go players in the world
« Reply #7 on: March 10, 2016, 01:17:51 PM »
go has a branching factor of around 200 per move, chess has a branching factor of around 20 - there are good heuristics and evaluation functions for evaluating a chess position, there are not really any good heuristics for evaluating a go position.
Not to be silly, but don't you think the complexity actually makes it easier for the computer to beat the human?  With chess there's a lot less (still quite a lot) of ways it can go and the human's have a strong sense of it.  I mean think about the much simpler game of tic tac toe.  A computer would never beat a competent player, all matches would end in a draw, no amount of additional process could change the result.  The only thing that would limit a computer in a super complex environment is if it's actually predictable - which wouldn't show for several games.

Fenring

  • Members
    • View Profile
Re: AlphaGo just beat one of the 5 best Go players in the world
« Reply #8 on: March 10, 2016, 01:36:30 PM »
Seriati, it all depends on what kind of heuristics are needed to teach a program how to play. Since AI still uses brute force methods the more calculations there are the harder it is for an AI to play properly. If it's the case that in GO many moves per turn can yield favorable results down the line then the AI would have to be able to process these exhaustively up to some number of moves ahead. Even though this complexity affects human players as well they can streamline their own heuristics to either avoid certain problematic lines or else to use tools other than hard computation to determine good position (which can include visual association, variation on common movements, or even creative exploration). Compared with chess it might be quite hard to teach an AI to evaluate a GO position, to say nothing of the fact that it has to have the processing power to explore its available options. In chess the modern AI heuristics have a much more streamlined sense of which moves can even possibly be good and so most are eliminated and not explored. Or, to work this from the reverse, since programmers seem to say it's harder to teach an AI GO than chess we can deduce from this backward that it must mean there are more possible good moves and that assessing board strength is harder.

Pyrtolin

  • Members
    • View Profile
Re: AlphaGo just beat one of the 5 best Go players in the world
« Reply #9 on: March 10, 2016, 02:02:58 PM »
Quote
Not to be silly, but don't you think the complexity actually makes it easier for the computer to beat the human?
No, because the exponential explosion of complexity completely frustrates traditional methods of computer intelligence. A computer can always win or force the result to a draw for tic tac toe, because it can easily search all possible outcomes and pick the best. Deep Blue eventually won chess because memory capacity finally increased to the point that it could process every possible chessboard configuration in reasonable time.

The possible board configurations for Go vastly exceed the capacity of computer memory and reasonable search time. That means that computers that try to play it must operate in a more human mode- using evaluation heuristics and something approximating intuition about how the game will go, rather than brute force computation to force the game to stay on paths that ensure the computer wins. That's something that has not yet managed to be well simulated on such a scale until now.

LetterRip

  • Members
    • View Profile
Re: AlphaGo just beat one of the 5 best Go players in the world
« Reply #10 on: March 10, 2016, 02:17:02 PM »
Seriati,

Quote
Not to be silly, but don't you think the complexity actually makes it easier for the computer to beat the human?  With chess there's a lot less (still quite a lot) of ways it can go and the human's have a strong sense of it.  I mean think about the much simpler game of tic tac toe.  A computer would never beat a competent player, all matches would end in a draw, no amount of additional process could change the result.  The only thing that would limit a computer in a super complex environment is if it's actually predictable - which wouldn't show for several games.

Say a computer can evaluate 100 billion moves per second.  at a branching factor of 200, depth 1/2 (i move) is 200, depth 1 (i move, you move) is 40000, depth 3/2 is 8,000,000 depth 2 is 1.6 billion, depth 5/2 320 billion, depth 3 64 trillion (6.4 * 10**13).  So to see just 3 moves ahead, a computer will take 640 seconds or 11 minutes.    To make a good move requires seeing ahead 20 or so moves - 1.0 * 10**92 possible moves, or using brute force would take around 3.5 10**73 years.  Since the average move of a game in go only allows about 1 minute of thought, it is simply not feasible.   You need some way to reduce the number of moves to consider.  Humans do this through pattern recognition and intuition.

LetterRip

  • Members
    • View Profile
Re: AlphaGo just beat one of the 5 best Go players in the world
« Reply #11 on: March 10, 2016, 02:19:12 PM »
Quote
Not to be silly, but don't you think the complexity actually makes it easier for the computer to beat the human?
No, because the exponential explosion of complexity completely frustrates traditional methods of computer intelligence. A computer can always win or force the result to a draw for tic tac toe, because it can easily search all possible outcomes and pick the best. Deep Blue eventually won chess because memory capacity finally increased to the point that it could process every possible chessboard configuration in reasonable time.

No the branching factor of chess doesn't allow that.  However we had good enough heuristics to evaluate a position and what were 'good moves' that the worthless moves could be pruned quite early in the tree.  For Go there simply weren't good heuristics to evaluate the position and to prune the possible moves to only 'good' moves.

scifibum

  • Members
    • View Profile
Re: AlphaGo just beat one of the 5 best Go players in the world
« Reply #12 on: March 10, 2016, 02:22:51 PM »
Seriati,

Quote
Not to be silly, but don't you think the complexity actually makes it easier for the computer to beat the human?  With chess there's a lot less (still quite a lot) of ways it can go and the human's have a strong sense of it.  I mean think about the much simpler game of tic tac toe.  A computer would never beat a competent player, all matches would end in a draw, no amount of additional process could change the result.  The only thing that would limit a computer in a super complex environment is if it's actually predictable - which wouldn't show for several games.

Say a computer can evaluate 100 billion moves per second.  at a branching factor of 200, depth 1/2 (i move) is 200, depth 1 (i move, you move) is 40000, depth 3/2 is 8,000,000 depth 2 is 1.6 billion, depth 5/2 320 billion, depth 3 64 trillion (6.4 * 10**13).  So to see just 3 moves ahead, a computer will take 640 seconds or 11 minutes.    To make a good move requires seeing ahead 20 or so moves - 1.0 * 10**92 possible moves, or using brute force would take around 3.5 10**73 years.  Since the average move of a game in go only allows about 1 minute of thought, it is simply not feasible.   You need some way to reduce the number of moves to consider.  Humans do this through pattern recognition and intuition.



I would amend: Humans do this pattern recognition and intuition that may involve unconscious mental processes that the players can't describe and we can't presently reverse engineer.  We don't know for sure how the best humans are good at Go, so it's not straightforward to apply computing to the problem to beat them at their own game. 

TheDrake

  • Members
    • View Profile
Re: AlphaGo just beat one of the 5 best Go players in the world
« Reply #13 on: March 10, 2016, 04:00:25 PM »
They took an entirely different approach than the type of branching search that worked for Deep Blue.

Quote
Here we introduce a new approach to computer Go that uses ‘value networks’ to evaluate board positions and ‘policy networks’ to select moves. These deep neural networks are trained by a novel combination of supervised learning from human expert games, and reinforcement learning from games of self-play. Without any lookahead search, the neural networks play Go at the level of state-of-the-art Monte Carlo tree search programs that simulate thousands of random games of self-play. We also introduce a new search algorithm that combines Monte Carlo simulation with value and policy networks.

One of the fun things about neural networks is that they actually remain almost as much of a mystery as human intelligence. They just sort of work, but when they fail, we don't really know how or why. We just send it back for more training.


Lloyd Perna

  • Members
    • View Profile
Re: AlphaGo just beat one of the 5 best Go players in the world
« Reply #14 on: March 10, 2016, 04:05:38 PM »
Quote
Not to be silly, but don't you think the complexity actually makes it easier for the computer to beat the human?
No, because the exponential explosion of complexity completely frustrates traditional methods of computer intelligence. A computer can always win or force the result to a draw for tic tac toe, because it can easily search all possible outcomes and pick the best. Deep Blue eventually won chess because memory capacity finally increased to the point that it could process every possible chessboard configuration in reasonable time.

The possible board configurations for Go vastly exceed the capacity of computer memory and reasonable search time. That means that computers that try to play it must operate in a more human mode- using evaluation heuristics and something approximating intuition about how the game will go, rather than brute force computation to force the game to stay on paths that ensure the computer wins. That's something that has not yet managed to be well simulated on such a scale until now.

In fact, even deep blue did not evaluate every possible move. There are just too many of them.  Chess playing software pretty much universally uses a algorithm called a minimax search with alpha-beta pruning.  Essentially they use a heuristic to evaluate each position in the search tree and give it a score.  They then use these scores to minimize the number of lines that need to be evaluated.  For Chess we are able to create very useful scoring heuristics.  The problem with Go has been the difficulty in doing this positional analysis.  Even the strongest human players have trouble explaining why any given move/position is superior to another.  The revolutionary thing about this AlphaGo program is that it's using machine learning to do this position evaluation.

Seriati

  • Members
    • View Profile
Re: AlphaGo just beat one of the 5 best Go players in the world
« Reply #15 on: March 10, 2016, 08:11:25 PM »
Say a computer can evaluate 100 billion moves per second.  at a branching factor of 200, depth 1/2 (i move) is 200, depth 1 (i move, you move) is 40000, depth 3/2 is 8,000,000 depth 2 is 1.6 billion, depth 5/2 320 billion, depth 3 64 trillion (6.4 * 10**13).  So to see just 3 moves ahead, a computer will take 640 seconds or 11 minutes.    To make a good move requires seeing ahead 20 or so moves - 1.0 * 10**92 possible moves, or using brute force would take around 3.5 10**73 years.  Since the average move of a game in go only allows about 1 minute of thought, it is simply not feasible.   You need some way to reduce the number of moves to consider.  Humans do this through pattern recognition and intuition.
You guys know computers better than I do, my thinking was just based on the idea that with so many possibilities the full consequences of the computer's strategy may not be evident to the human player, and similarly, the consequences of the human strategy may not be so devastating to the computer if it makes a "wrong" move.  Are there more paths to victory from a given position in Go than Chess?  If so, I'd think even if the computer can't parse the ultimate consequence from start it should be able to parse a probable set of consequences and keep picking the best set after each player's turn.
 
It would seem the more possibilities at each stage the less likely the human can accurately evaluate them.  As you pointed out, we rely on all kinds of pattern recognition, and then use that to try and force predictable results.  If the computer is somewhat randomly finding "good" results, wouldn't it almost always be "seeing" something that the human doesn't?  It would only be by random chance (possibly low probability) that the "best" solution it comes up with at any point is the one or one of the few the human player expects.

Edit, I mean think of an even more complex game.  A million balls are flying across a table, paused with their vectors and velocity known, you have to redirect one ball to cause the maximum number of balls to fly off the opposite side of the table.  It's almost certain that the computer would always beat the human, isn't it?
« Last Edit: March 10, 2016, 08:14:27 PM by Seriati »

Fenring

  • Members
    • View Profile
Re: AlphaGo just beat one of the 5 best Go players in the world
« Reply #16 on: March 10, 2016, 10:15:11 PM »
It would seem the more possibilities at each stage the less likely the human can accurately evaluate them.  As you pointed out, we rely on all kinds of pattern recognition, and then use that to try and force predictable results.  If the computer is somewhat randomly finding "good" results, wouldn't it almost always be "seeing" something that the human doesn't?  It would only be by random chance (possibly low probability) that the "best" solution it comes up with at any point is the one or one of the few the human player expects.

Another factor answering this question is that humans not only employ pattern recognition but also impose pattern and design onto their gameplay. A human might look at an early position and envision a late game board position and endeavor to move the action in that direction. An AI cannot do this and doesn't have the programming to 'desire' particular outcomes. Rather it uses a numerical evaluation of the given board position based on some values, as the others have said, and also looks several moves in advance and weighs the value of those positions. It simply chooses the move leading to a board position of highest value. In short, the AI operated based on rote - albeit a rigorous one. Based on this the human is actually more likely to envision a late game position than the AI would, as the AI is looking so many moves ahead and judging based on what it sees on the table. A corollary to this is that if a human is employing a novel or inventive line the AI won't be able to predict where it's headed since there is no play history on that line, whereas the human has a pre-chosen path to experiment with that is meant to disrupt expectation. In short there is a mind-game at work here that an AI can't cope with since it doesn't 'prepare' for games as such and try to outwit a particular opponent. That being said if the AI is sufficiently powerful these disadvantages will be irrelevant compared to its computational superiority.

TheDrake

  • Members
    • View Profile
Re: AlphaGo just beat one of the 5 best Go players in the world
« Reply #17 on: March 11, 2016, 10:19:22 AM »
It would seem the more possibilities at each stage the less likely the human can accurately evaluate them. 

Edit, I mean think of an even more complex game.  A million balls are flying across a table, paused with their vectors and velocity known, you have to redirect one ball to cause the maximum number of balls to fly off the opposite side of the table.  It's almost certain that the computer would always beat the human, isn't it?

There's definitely some truth to what you are saying. Once a computer has been trained to solve complex problems, it does them accurately, tirelessly, and instantly. There are modern fighter planes that humans are incapable of flying because of the millions of adjustments that have to be done faster than a human could perceive the need.

There's a time component in many of these, whether it is Google's self-driving car or otherwise. The other aspect is defeating the top human. AI go and chess were beating the majority of humans quite some time ago. Computers played at a Master level in the early 80s.

This makes AI all the more formidable. AI doesn't have health problems that cause it to withdraw from the match, trouble sleeping the night before, or breakups. You can also make a COPY of an AI, so once you have one super-awesome go playing program, you have as many as you want almost for free. Unlike the deployment of robotics, which took many years to displace humans because it required building new factories and spending lots of money.

The biggest thing that limits AI is narrow focus. A go playing program isn't any good at sorting email for you. A human's best ability is by using powers of analogy and a broadly trained mind to solve unique or unusual problems rather than a well-understood one. So, an AI might do great at your new pong game, but it will fail to the human for a long time while it trains. A human can instantly walk up to the table, understand your instructions, and start whacking a modest amount of balls back.

LetterRip

  • Members
    • View Profile
Re: AlphaGo just beat one of the 5 best Go players in the world
« Reply #18 on: March 11, 2016, 10:50:16 AM »
TheDrake,

Quote
The biggest thing that limits AI is narrow focus. A go playing program isn't any good at sorting email for you.

That is the other important aspect of this.  The amount of go specific programming is quite limited.  The same code can be thrown at a database of data for all sorts of problems and with minor changes applied to the new problem.

TheDrake

  • Members
    • View Profile
Re: AlphaGo just beat one of the 5 best Go players in the world
« Reply #19 on: March 11, 2016, 10:56:16 AM »
Well, sure. Like all neural networks. But the training data is still quite unique, as are the parameters, as you know. You can't just plug in stock market data and suddenly AlphaGo is trading like a pro. I could be wrong, but that's not my understanding of it. I guess we'll find out when google publishes their next feat, but I'm not sure they will. They are very close to the vest when it comes to technology that solves problems that are not curious novelties lacking monetization.




Pyrtolin

  • Members
    • View Profile
Re: AlphaGo just beat one of the 5 best Go players in the world
« Reply #20 on: March 11, 2016, 11:42:53 AM »
Quote
Edit, I mean think of an even more complex game.  A million balls are flying across a table, paused with their vectors and velocity known, you have to redirect one ball to cause the maximum number of balls to fly off the opposite side of the table.  It's almost certain that the computer would always beat the human, isn't it?
The trick is that that's actually not more complex. It's harder for a human because it requires a wide scope of calculation and timing, but you're talking about a single state, set formulas and a deterministic solution. There are no future forks after you've made the change, just a single fork. So, if you have 50 balls, you have 50 linear things to calcualte. Hard for a human, but linear calculations are what a computer does best, even if they have to be done in parallel. With chess there are 20 first moves that each player can technically make, so just to get 2 moves in, you need to calculate 200 things, shorter calculations, sure, but that just means that you've truncated the computer's primary advantage (calculating the predictable) and emphasized its primary weakness (anticipating the unpredictable).

The computer will only lose tic tac toe if it's programed to throw the game. The same goes for chess, since we can cut the decision space to the point where it can effectively evaluate every possible board configuration that it will allow to happen (and not waste time on the ones that it can effectively prevent in the first place. It may have blind spots, but the only way to exploit those is to know them and intentionally play to them it's almost certain that you won't find them by accident unless you're effectively playing randomly and get lucky)

The core of the Go achievement means that we've managed to teach a computer to compensate for what has been a traditional weakness by letting it build its own metrics for evaluating the unknown based on practical experience. That's a huge step toward something resembling cognition and not simply applying brute force linear processing of some subset of possibilities.

LetterRip

  • Members
    • View Profile
Re: AlphaGo just beat one of the 5 best Go players in the world
« Reply #21 on: March 12, 2016, 10:20:54 AM »
And AlphaGo won game 3 crushingly.  It was impressive to watch Lee Sidol fight at the end.  It is really depressing though to see such a great player having his world turned upside down and blaming himself for 'playing badly', when he probably played better in this third game than any other player in the world would or could have.

I really can't wait till DeepMind releases more information about the match after it is over.  I'm curious what Elo they estimate it is at right now and I'd really like to see its evaluation of the various moves (ie what it would consider 'blunders' by the human players; and its evaluation of moves that it has made that commentators felt were 'bad').

LetterRip

  • Members
    • View Profile
Re: AlphaGo just beat one of the 5 best Go players in the world
« Reply #22 on: March 13, 2016, 05:10:06 AM »
Lee won the fourth game!  He found a brilliant forcing sequence that AlphaGo overlooked.  It might have still won, but it 'went crazy' and started playing bizarre moves  (this happens because it starts searching for a better move, and when it finds sequences that involve a different bad move it delays the loss beyond its search horizon).  This is a problem common with monte carlo search roll outs.

NobleHunter

  • Members
    • View Profile
Re: AlphaGo just beat one of the 5 best Go players in the world
« Reply #23 on: March 13, 2016, 12:25:16 PM »
I am oddly cheered by the victory for team human :p

LetterRip

  • Members
    • View Profile
Re: AlphaGo just beat one of the 5 best Go players in the world
« Reply #24 on: March 13, 2016, 01:35:46 PM »
Interesting - in the conference it sounds like it was the only move he could see that didn't immediately lose, he didn't realize it was one that gave him strong winning chances.

LetterRip

  • Members
    • View Profile
Re: AlphaGo just beat one of the 5 best Go players in the world
« Reply #25 on: March 15, 2016, 05:08:46 AM »
AlphaGo won the final match.

What is interesting is that it blundered in the opening badly (as in played series of moves that even most beginners understand is a losing sequence and lost quite a few points), and then gave away a lot of free points in the middle game, yet still was able to win.  Once the fix a few blunders and bugs, and especially if they increase its playing strength more, it will be nearly unbeatable.