I was at the 2003 match of Garry Kasparov vs Deep Junior -- the strongest chess player of all time vs what was at that point the strongest chess playing computer in history. Kasparov drew that match, but it was clear it was the last stand of homo sapiens in the man vs machine chess battle. Back then, people took solace in the game of Go. Many boldly and confidently predicted we wouldn't see a computer beat the Go world champion in our lifetimes.
Tonight, that happened. Google's DeepMind AlphaGo defeated the world Go champion Lee Sedol. An amazing testament to humanity's ability to continuously innovate at a continuously surprising pace. It's important to remember, this isn't really man vs machine, as we humans programmed the algorithms and built the computers they run on. It's really all just circuitous man vs man.
Excited for the next "impossible" things we'll see in our lifetimes.
> Many boldly and confidently predicted we wouldn't see a computer beat the Go world champion in our lifetimes.
Sadly as I write this my uncle and personal hero who spent 17 years of his life working towards a Ph.D. on abstraction hierarchies for use in Go artificial intelligence, has been moved into hospice care. I'm just glad that in the few days that are left he has a chance to see this happen, even if it is not the good old-fashioned approach he took.
[1] He recently started rewriting the continuation of this research in golang, available on Github: https://github.com/Ken1JF/ah
Thanks for the link. I started reading his thesis. While AlphaGo is obviously exciting, it seems like your uncles approach could help us better understand how humans play go which seems hugely valuable. I look forward to exploring his thesis further.
AlphaGo's architecture resembles much closer to how humans think and learn.
I initially learned Go to be able to have some chance of an AI. I then had some transformative experiences that coincided with my early kyu learning of basic Go lessons. On of the big lessons in Go is to learn how to let go of something. Taking solace in anything on the Go board is one of the blocks you work through when you develop as a Go player.
I had already known about two years ago that just the Monte Carlo approach was already scalable. If Moore's Law continues, it was a matter of time before the Monte Carlo approach would start challenging the professional ranks -- it had already gotten to the point where you just needed to throw more hardware at it.
AlphaGo's architecture adds a different layer to it. The Deep Learning isn't quite as flexible as the human mind, but it can do something that humans can't: learn non-stop, 24/7 on one subject. We're seeing a different tipping point here, possibly the same kind of tipping point when we witnessed the web browser back in the early 90s, and the introduction of the smartphone in the mid '00s. This is way bigger (to use a Go terminology) than what happened with chess.
This isn't about Moore's Law though. From the AlphaGo paper:
> During the match against Fan Hui, AlphaGo evaluated thousands of times
> fewer positions than Deep Blue did in its chess match against
> Kasparov; compensating by selecting those positions more intelli-
> gently, using the policy network, and evaluating them more precisely,
> using the value network—an approach that is perhaps closer to how
> humans play. Furthermore, while Deep Blue relied on a handcrafted
> evaluation function, the neural networks of AlphaGo are trained
> directly from gameplay purely through general-purpose supervised and
> reinforcement learning methods
My understanding is that it is much more expensive for AlphaGo to evaluate a position than it was for Deep Blue. I'm not certain, but I would be surprised if AlphaGo did not need significantly more computation than Deep Blue.
edit: some actual estimates. Deep Blue had 11.38 GFLOPS[1]. According to the paper in Nature, distributed AlphaGo used 1202 CPUs and 176 GPUs. A single modern GPU can do between 100 and 2000 double precision GFLOPS[2]. So from GPUs alone AlphaGo had access to 4-5 orders of magnitude more computing power than Deep Blue did.
A brute force approach for Go doesn't work. It doesn't work for humans (deep reading skills) and doesn't work for computers. The Monte Carlo approach was the first one that allowed Go AIs to scale with the hardware. This was at least two years ago.
AlphaGo went way beyond that. It actually learned more like how a Go player does. It was able to examine and play a lot of games. That's why it was able to beat a 2p pro, and within less than half a year, challenge a 9p world-class player at least on even terms.
The big thing isn't that AlphaGo is able to play Go at all at that level, but that learned a specific subject much faster than a human.
Strong agreement that it wasn't purely about computational power, and that there were significant software advances. I just want to make the point that hardware has advanced considerably as well.
This 1000 times. Extrapolating Deep Blue's 11GFlop supercomputer to today with Moore's law would be a 70TFlop cluster. AlphaGo is using 1+PFlops of compute (280GPUs referenced for competition in [0]). That's an insane amount of compute.
While it's fun to hate on IBM, it's not really fair to say Deep Blue was throwing hardware at the problem but AlphaGo isn't. Based on the paper AlphaGo will perform much worse in terms of ELO ranking on a smaller cluster.
The AlphaGo that beat the 2p European champion five months ago was not as strong as the AlphaGo that beat Lee Sedol (9p). I don't think this was just the AlphaGo team throwing more hardware. I think they had been constantly running the self-training during the intervening months so that AlphaGo was improving itself.
If that is so, then the big thing here isn't that AlphaGo is the first AI to win an official match with the currently world's strongest Go player. It's that within less than half a year, AlphaGo was able to learn and grow to go from challenging a 2p to challenging the world's strongest player. Think about that.
I think it's fair to say that in the future, people will look back and wonder how it was possible to live without having a good AI.. similar to how we look past at caveman and wonder how they could live without electricity. AI is really just a tool that we leverage, the same was as we leveraged the wheel or electricity.
Yep. I was just talking with the founder of a startup I work with. His son was born in the past 5 months or so. The son is never going to live in a world that doesn't have deep learning. Like the kids who never knew what the world was like before the smartphone. Like the kids who never knew what the world was like before the web browser.
And AI is just one strand. There are several strands that are as deeply changing, that is happening simultaneously.
I remember someone speaking about the shift between classical hard sci fi and more current sci-fi authors like Neal Stephenson or Peter Hamilton. The classical authors like Heinlein or Asimov might do world building where they just change one thing. What would the world be like if that one thing changed? After a certain point though, things were changing so fast that later authors didn't do that. There were too many things that changed at the same time.
Here's a video where teens discover Windows 95: https://www.youtube.com/watch?v=8ucCxtgN6sc It gives a visual analogy of what you're saying about the new generation and AI!
Correct. It played like a top level human player, pretty evenly matched with Lee Sedol. AlphaGo from yesterday would have wiped the floor with AlphaGo from 6 months ago.
Various commentators mentioned how both players, human and synthetic, made a few mistakes. Even I caught a slow move made by the AI. So whether Lee Sedol was at the top of his peformance, or not, is a bit of a debate. But the AI was clearly on the same level, whatever that means.
It was an intense fight throughout the game, with both players making bold moves and taking risks. Fantastic show.
That could be true, but according to some articles I was reading at the time (sorry no src), the nature of their engine is that you cannot determine just how strong it is by playing one game because it plays to "just win", and not to win by as much as possible (paraphrase). So maybe it was barely good enough to be 2p, maybe it was already much stronger.
6 months ago it was clearly stronger than Fan Hui 2p. You don't beat someone at that level 5-0 without being consistently stronger.
Fan Hui said the machine played extremely consistently 6 months ago. He said playing the computer was "like pushing against a wall" - just very strong, very consistent performance.
This is misleading. AlphaGo beat a 2p player five months ago. Now it has beaten a 9p player. That tells is nothing about it's improvement in the intervening time. Given only this information, however unlikely, AlphaGo could have actually been stronger before.
Replying to scarmig, No. Player A may consistently beat Player B who may consistently beat Player C who consistently beats Player A.
There are different strategies depending upon how much emphasis is placed upon early territorial gains as opposed to "influence" which is used for later later territorial gains.
Similarly, playing "passive" moves that make territory without starting a "fight" versus agressively contesting for every piece of territory available.
It's more that there are different styles of winning, and a human will tend to specialize in such a style. But generally, someone who is consistently stronger will win over someone who is consistently weaker, regardless of style.
What I always think about with AI, and speaking to the "man's programming vs man" higher up, is what we'll get when we can teach computers how to solve these problems so that e.g. They could come up with the solution for + implement something like this on their own.
Is the Monte Carlo approach specific to Go in terms of A.I. challenges? Or is the Monte Carlo approach gaining traction in other A.I. problems as well?
I am tremendously unfamiliar with recent A.I developments.
Monte Carlo Tree Search is a key technique in previous computer Go programs (and other games). The improvement here was using the deep learning network as the value function to evaluate nodes in the tree and the policy network to determine the search order.
MC tree search isn't specific to Go, no. It's been used for other games including imperfect information ones like poker. I believe that the main reasons for using MC search is that it does not require an evaluation function, and it acts as an anytime algorithm so you can get a "good enough" answer within arbitrary time constraints.
What kind of source do you want? It's a saying in the go community, people believed (including me) that a bot couldn't beat a human in our lifetime, some people had more extreme view and thought that it would never be possible.
Anything written. I'll be particularly happy with higher "quality" sources -- books, quotations in newspapers, etc. -- but honestly, I'm not that picky and will accept an anonymous comment on a random forum.
"Fotland, an early computer Go innovator, also worked as chief engineer of Hewlett Packard’s PA-RISC processor in the 70s, and tested the system with his Go program. “There’s some kind of mental leap that has to happen to get you past that block, and the programs ran into the same issue. The issue is being able to look at the whole board, not the just the local fights.”
Fotland and others tried to figure out how to modify their programs to integrate full-board searches. They met with some limited success, but by 2004, progress stalled again, and available options seemed exhausted. Increased processing power was moot. To run searches even one move deeper would require an impossibly fast machine. The most difficult game looked as if it couldn’t be won."
Thank you for the source. I believe this is a good written example of how conservative estimates were as recently as May of 2014.
Nonetheless, the quoted estimate in the article (mentioned twice, including in the second sentence) is "I think maybe ten years", ie 2024, which while inaccurate is probably "in our lifetimes".
There are a lot of quotes in that article though. And a number are in the vein of not being sure how they were going to get from where they were to better-than-human. Not my field in any case but I think it's fair to say that there was a lot of skepticism about even the general path going forward even relatively recently.
It seems unlikely that a computer will be programmed to drub a strong human player any time soon, Dr. Reiss said. ''But it's possible to make an interesting amount of progress, and the problem stays interesting,'' he said. ''I imagine it will be a juicy problem that people talk about for many decades to come.''[1]
Not quite what you are after, but it's pretty clear that he didn't think it would be beating the world champion in 14 years.
Serious predictions actually inferred from the progress of existing (MCTS and others before) bots, which was something like 1 stone every two years (I don't recall the details, but it's easy to find out there). Top professionals were estimated to be something like 10 stones stronger than the best bot at 2008, so 2025 wouldn't sound too conservative.
"At the US Congress 2008, he [Myungwan Kim] also played a historic demonstration game against MoGo running on an 800 processor supercomputer. With a 9 stone handicap, MoGo won by 1.5 points. At the 2009 congress, he played another demonstration game against Many Faces of Go running on 32 processors. Giving 7 stones handicap, Kim won convincingly by resignation."
(Kim Myung Wan (born 1978) is a 9d Korean professional who has taken up residence in the Los Angeles area as of 2008)
Go seemed to progress in a lot more fits and starts than did chess (which, admittedly, probably had a lot more effort put into it). Prior to 2005 or so, Go programs were relatively weak and there were people working on them who were saying that they didn't really see a path forward.
Then people hit on using Monte Carlo which was the big step forward you show in your graphs. But then, that progress seemed to stall to the degree that various people were quoted in a Wired article a couple years ago about how they weren't sure what was going to happen.
> Many boldly and confidently predicted we wouldn't see a computer beat the Go world champion in our lifetimes.
To add to that, in Godel Escher Bach, Hofstadter in 1979 predicted that no chess engine would ever beat a human grandmaster player. It just goes to show how hard it is to predict what is, and also will remain, impossible for machines!
Francis Collins? said something like: people underestimate the change in the short term and overestimate it in the long term (there is my flying DeLorean and the hotel on the Moon).
"We always overestimate the change that will occur in the next two years and underestimate the change that will occur in the next ten. Don't let yourself be lulled into inaction."
I've never felt playing against what is suppose to be an entire room of machines (wether Deep Blue or Watson) to be fair. What would be fair is to limit the total mass of the computer to say 200kg and leave it at that. What is effectively happening is AlphaGo is running on a distributed system of many, many machines. Even Watson took an entire room. Google is paying a premium to push AlphaGo to win.
It's a proof-of-concept. What they've proved is that the same kind of intelligence required to play Go can be implemented with computer hardware. Before now, software couldn't beat a ranked human player at Go no matter how much computing power we threw at it. Now we can. Give it ten years and, between algorithmic optimizations and advances in processing, you'll have an unbeatable Go app on your phone.
Indeed. The first time a computer defeated a human in Chess it was this[1] size (1997). In 2009 it became possible to fit a grandmaster into this[2].
> Pocket Fritz 4 won the Copa Mercosur tournament in Buenos Aires, Argentina with 9 wins and 1 draw on August 4–14, 2009. Pocket Fritz 4 searches fewer than 20,000 positions per second. This is in contrast to supercomputers such as Deep Blue that searched 200 million positions per second. Pocket Fritz 4 achieves a higher performance level than Deep Blue.[3]
The first steps are always the most inefficient. Make it work, make it right, make it fast.
GM Michael Stean lost to Cyber 176 (a mainframe 'supercomputer') in 1977 (at blitz). AFAIK this was the first time a computer defeated a GM; they began defeating IMs and experts some ten years before that. Kasparov himself lost to Fritz 2 at blitz as early as 1992.
"Under tournament conditions" is the condition everyone forgets. Go AIs were competing with ranked players given handicaps of varying degrees of absurdity.
> Give it ten years and, between algorithmic optimizations and advances in processing, you'll have an unbeatable Go app on your phone.
I find this overly optimistic because of the huge amount of power required to run the Go application. Remember, we're getting closer and closer to the theoretical lower limit in the size of silicon chips, which is around 4nm (that's about a dozen silicon atoms). That's a 3-4x improvement over the current state of the art.
The computer to run AlphaGo requires thousands of watts of power. A smartphone can do about one watt. A 3-4x increase in perf per watt isn't going to cut it.
If there will be a smartphone capable of beating the best human Go players, my guess is that it won't be based on general purpose silicon chips running on lithium ion batteries.
On the other hand, a desktop computer with a ~1000 watt power supply (ie. a gaming pc) might be able to do this in a matter of years or a few decades.
As solid as your argument may be, everyone saw arguments like this over and over. Every single time they were solid. For a time, it was the high frequency noise that would not be manageable (80s), then heat dissipation (90s), then limits on pipeline optimization (00s) and now size constraints on transistors. They were all hard barriers, deemed impossible and all were overcome.
I already know that your answer will be: "but this time it is a fundamental physics limit". Whatever. I'm jaded by previous doomsday predictions. We'll go clockless, or 3D, or tri-state or quantum. It'll be something that is fringe, treated as idiotic by current standards and an obvious choice in hindsight.
Our brains use roughly ~20 watts though, so we know that the power constraints can be overcome, if not in silicon then it may be biological machines we use in the future.
The previous problems were solved because people were willing to spend hundreds of billions of dollars to solve them. And they are still spending that kinds of money.
If the normalcy bias was in effect, they wouldn't be spending that money.
Actually Normalcy Bias may in fact feed that kind of money spending until such time as reality hits. Assuming that people will automatically act more logically when large amounts of money is in play flies in the face of recent history. Just look at the recent housing loan crisis. Normalcy Bias played a part there.
It's certainly possible that we'll break more barriers with clever engineering and new scientific breakthroughs. But that doesn't mean the Normalcy Bias isn't in play here.
Normalcy bias may have people spending lots of money on fabs assuming that the problems would be solved by the time the fabs are built.
However, I'm talking hundreds of billions spent on R&D to specifically to solve problems associated with chip manufacture. It took on the order of 25 years to solve each of the problems listed in the grandparent's post. Nobody would spend that kind of money or time on something that they think somebody else would solve.
People have probably spent billions of dollars to find a cure for cancer, but there isn't one that works for all cancers and most are still very bad news.
Say you spent a hundred billion dollars to extinguish the sun- that wouldn't work. How much money you spend is irrelevant when you're up against what people call "hard physical limits".
Isn't our inability to cure all cancers a limitation of our knowledge more than a hard physical limit?
I've read several articles saying that different cancers are not exactly the same disease, but more like different diseases with the same symptom (uncontrolled tumor growth) and different etiology, even sometimes different from person to person, not just from tissue to tissue. This was said to be a reason that a general cancer cure is so elusive. But is it really thought of as impossible, not just elusive?
Maybe our inability to extinguish the sun is also a limitation of knowledge more than a hard physical limit!
Even if I'm right about this, your description of the situation would still be accurate in that there would be no way to simply throw more money at the problems and guarantee a solution; there would need to be qualitative breakthroughs which aren't guaranteed to happen at any particular level of expenditure. If people had spent multiples of the entire world GDP on a space program in the 1500s, they would still not have been able to get people to the moon, though not because it's physically impossible to do so in an absolute sense.
There is a lot of room for improvement with the implementation. The way we are using deep neural networks at the moment is exellent for prototyping, but far from optimal. For instance, this paper http://arxiv.org/abs/1511.00363 shows that you can replace floating point operations by simple bitwise operations without losing too much precision in DNNs for image recognition. Together with a better (that is, compiled, instead of interpreted) representation of the inference step I would expect an order of magnitude improvement at a small loss in precision. More software tuning, especially the kind of low-level optimizations that most chess programs do, should yield another big improvement.
Finally, the hardware we are using to run these programs is insane. Sure the silicon is approaching some hard physical limits, but your processor spends most of that power trying to make old programs run fast...
My prediction is that with enough ressources it is possible to write a Go AI which runs on general purpose hardware that's manufactured on current process nodes and fits in your pocket.
I don't think you appreciate how much of this is good algorithms, and how little you need sheer computing power to get good results.
If you look at http://googleresearch.blogspot.com/2016/01/alphago-mastering... you'll find that Google's estimate of the strength difference between the full distributed system and their trained system on a single PC is around 4 professional dan. Let's suppose that squeezing it from a PC to a phone takes about the same off. Now a pocket phone is about 8 professional dan weaker than the full distributed system.
If their full trained system is now 9 dan, that means that they can likely squeeze it into a phone and get a 1 dan professional. So the computing power on a phone already allows us to play at the professional level!
You can get to an unbeatable device on a phone in 10 years, if self-training over a decade can create about as much improvement they have done in the last 6 months, AND phones in 10 years are about as capable as a PC is today. Those two trade off, so a bigger algorithmic improvement gets you there with a weaker device.
You consider this result "overly optimistic". I consider this estimate very conservative. If Google continues to train it, I wouldn't be surprised if there is a PC program in a year that can beat any Go player in the world.
You're right, it won't be a general purpose computing device the way we conceive of it with the von Neumon architecture.
It'll likely be hardware that can be generalized to run any kind of deep net. The iPhone 5S is already capable of running some deep nets.
As a friend mentioned, it isn't the running of the net, it's the training that takes a lot more computational power (leaving aside data normalization). A handheld device that is not only capable of running a deep net, but also training one -- yeah, that will be the day.
There are non von Neuman architectures that are capable of this. Someone had figured out how to build general-purpose CPUs on silicon made for memory. You can shrink down a full rack of computers down into a single mother board, and use less wattage while you are at it.
This really isn't about having a phone be able to beat a Go player. Go is a transformative game that, when learned, it teaches the player how to think strategically. There is value for a human to learn Go, but this is no longer about being able to be the best player in the absolute sense. Go will undergo the same transformation that martial arts in China and Japan has gone through with the proliferation and use of guns in warfare.
Rather, what we're really talking about is a shot at having AIs do things that we never thought they could do -- handle ambiguity. What I think we will see is -- not the replacement of blue collar workers by robots -- but the replacement of white collar workers by deep nets. Coupled with the problems in the US educational system (optimizing towards passing tests rather than critical thinking, handling ambiguity, and making decisions in face of uncertainty), we're on a verge of some very interesting times.
Please do elaborate. I try to base my assumptions (which I accept may turn out to be completely wrong) on physics and experience in working in semiconductors.
I just don't see a 1000x+ decrease in the power required happening in a decade or two without some revolutionary technology I can't even imagine. Is this what you meant? I'm sure most people couldn't imagine modern silicon chips in the 1950s vacuum tube era. But now we're getting close to the theoretical, well-understood minimums in silicon chips, so another revolutionary step is required if another giant leap like that is to be achieved.
> physics and experience in working in semiconductors
> without some revolutionary technology I can't even
> imagine
I suspect (in the nicest possible way) that in a lineup of your imagination (on current assumptions) vs the combined ingenuiety of the human race driven by the hidden hand, the latter wins.
exDM69 never said it's not gonna happen, he just said that it's not going to happen in ten years, and I agree with him. Revolutions never occurs that quickly. To achieve that we don't just need an improvement of the current state of the art, we need a massive change and we don't even know what it's going to look like yet ! This kind of revolution may occur one day but not in ten year.
And it could even never happen, remember that we don't have flying cars yet ;)
It seems to me that the people who say "it won't happen" do tend to have a much better reason to say it won't happen (or rather that it _probably_ won't happen) than the people who insist the next big revolution is just round the corner just because the last big revolution did happen.
The optimistic position is a bit like saying: "I 've lived 113 years, I'm not going to die now!". It's entirely possible for a trend to reverse itself. If machine learning has taught us something is that background knowledge (in this case, of processor technology) gives you much better results than just guessing based on what happened in the past.
Heterogenous computing is already used in AlphaGo (and your smartphone). 3d chips will come to mainstream devices in a few years, but will give "only" a modest performance boost, say 2x or so.
The rest of the technologies you mention have great potential but will they be available in a smartphone in one decade? I don't think so.
You might ultimately only need some specialized "neural processing instruction set" for either the GPU cores or for the CPU cores. Or at least, I don't see any obvious obstacles to that.
I feel the same way about the chips reaching their physical limits. But I keep waiting for a new way we use them. We used to just churn out MHz and that was the metric. Then we got hyper-threading, multi-cores, GPU and other specific processors and new ways of programming to go with it all. I imagine we'll see the same. Just like the brain has different areas of processing, I'm hoping we'll see the same in silicon chips. Just like how we offload work from the general purpose cpu to the more efficient purpose build gpu or sound card etcs. Not saying every computer is going to have a GO chip in it, but maybe someday we'll have machine learning processors or who knows what. But yeah the advancements will be new designs and new ways of processing instead of more power.
Sure. But so far, we've found that revolutionary step every time we've hit these sorts of walls, and if I was a betting man I'd wager we'll do the same again.
Right, but just as a contrast: Technological progress speed has been at an all-time high since the begin of the industrial revolution.
It might as well slow down again and we have to remember that most humans in history saw little to no advances in technology over their lifetime.
I'm excited for the possibilities modern science opens up but I also think we might reach a point where fundamental progress stalls for a century or two.
A Go app likely wouldn't rely on the native processing power of the smartphone.
An AlphaGo app could be created today for a smartphone. The bottleneck isn't the phone it's the cost of the cloud computing resources behind it.
Perhaps a combination of Moore's law and economy of scale would make it affordable sooner than we think.
The Xbox One, for example, already subcontracts difficult problems out to Azure.
No, they haven't shown that the same kind of intelligence required to play go can be implemented in computer software. The methods AlphaGo uses are not the same as the intelligence a human uses at all. What they have done is prove an implementation of computer go in software is capable of beating a human player, not that they have implemented the same kind of intelligence as the human player.
> What they've proved is that the same kind of intelligence required to play Go can be implemented with computer hardware. Before now, software couldn't beat a ranked human player at Go no matter how much computing power we threw at it.
I don't think that's quite true as a description of what we knew about computer Go previously, though it depends on what precisely you mean. Recent systems (meaning the past 10 years, post the resurgence of MCTS) appear to scale to essentially arbitrarily good play as you throw more computing power at them. Play strength scales roughly with the log of computing power, at least as far as anyone tested them (maybe it plateaus at some point, but if so, that hasn't been demonstrated).
So we've had systems that can in principle play to any arbitrary strength, if you can throw enough computing power at them. Though you might legitimately argue: by "in principle" do you mean some truly absurd amount, like more computing power than could conceivably fit in the universe? The answer to that is also no; scaling trends have been such that people expected computer Go to beat humans anywhere from, well, around now [1], to 5 to 10 years from now [2].
The two achievements of the team here, at least as I see them, are: 1) they managed to actually throw orders of magnitude more computing power at it than other recent systems have used, in part by making use of GPUs, which the other strong computer-Go systems don't use (the AlphaGo cluster as reported in the Nature paper uses 1202 CPUs and 176 GPUs), and 2) improved the scaling curve by algorithmic improvements over vanilla MCTS (the main subject of their Nature paper). Those are important achievements, but I think not philosophical ones, in the sense of figuring out how to solve something that we previously didn't know how to solve even given arbitrary computing power.
[1] A 2007 survey article suggested that mastering Go within 10 years was probably feasible; not certain, but something that the author wouldn't bet against. I think that was at least a somewhat widely held view as of 2007. http://spectrum.ieee.org/computing/software/cracking-go
[2] A 2012 interview though that mastering Go would need a mixture of inevitable scaling improvements plus probably one significant new algorithmic idea, also a reasonably widely held view as of 2012. https://gogameguru.com/computer-go-demystified-interview-mar...
"Recent systems (meaning the past 10 years, post the resurgence of MCTS) appear to scale to essentially arbitrarily good play as you throw more computing power at them. Play strength scales roughly with the log of computing power, at least as far as anyone tested them (maybe it plateaus at some point, but if so, that hasn't been demonstrated)."
This is exactly the opposite of my sense based on following the computer go mailing list (which featured almost all the top program designers prior to Google/Facebook entering the race). They said that scaling was quite bad past a certain point. The programs had serious blindspots when dealing with capturing races and kos[1] that you couldn't overcome with more power.
Also, DNNs were novel for Go--Google wasn't the first one to use them, but no one was talking about them until sometime in 2014-2015.
[0] Not the kind of weaknesses that can be mechanically exploited by a weak player, but the kind of weaknesses that prevented them from reaching professional level.
> Play strength scales roughly with the log of computing power
To be fair, a lot of the progress in recent years has been due to taking a different approach to solving the problem, and not just due to pure computing power. Due to the way go works, you can't do what we do with chess and try all combinations, no matter how powerful of a computer you have. Using deep learning, we have recently helped computers develop what you might call intuition -- they're now much better at figuring out when they should stop going deeper into the tree (of all possible combinations).
There've definitely been algorithmic improvements, but from what I've read so far, the change in search algorithms, from traditional minimax search to MCTS, has been the biggest improvement, more than deep learning.
The game itself, however, scales exponentially, and there's nothing to do about that, so if you enlargen the board, no computer... And no human may be able to play it well.
The achivement was a leap towards the human level of play (and quite possibly over it). There might be additional leaps, which will take AIs WAY beyond humans, but none of those will scale linearily in the end. (And yeah, I guess you didn't want to say that either)
Then you can say that, in 10 years, if we indeed have reached that point. Otherwise it'd just an empty prediction, and his perfectly valid point stands.
The real achievement is in the algorithm. To make an analogy, the accomplishment of putting a man on the moon required that we understand enough to make a rocket. We could have put hundreds of car engines together but that wouldn't ever have gotten us to the moon.
AlphaGo utilizes the "Monte Carlo tree search" as its base algorithm[1]. The algorithm has been used for ten years in Go AIs, and when it was introduced, it made a huge impact. The Go bots got stronger overnight, basically.
What novel thing AlphaGo did, was a similar jump in algorithmic goodness. It introduced two neural networks for
1) predicting good moves at the present situation
2) evaluating the "value" of given board situation
Especially 2) has been hard to do in Go, without playing the game 'till the end.
This has a huge impact on the efficiency of the basic tree search algorithm. 1) narrows down the search width by eliminating obviously bad choises and 2) makes the depth at where the evaluation can be done, shallower.
So I think it's not just the processing power. It's a true algorithmic jump made possible by the recent advances in machine learning.
Especially 2) has been hard to do in Go, without playing the game 'till the end.
This is what struck me as especially interesting, as a non-player watching the commentary. The commentators, a 9-dan pro and the editor of a Go publication, were having real problems figuring out what the score was, or who was ahead. When Lee resigned the game, it came as a total surprise to both of them.
Just keeping score in Go appears to be harder than a lot of other games.
Score in Go is captured stones plus surrounded empty territory at the end of the game. Captures are well defined when they happen, but territory is not defined until the end.
The incentive structure of the game leads to moves that firmly define territory usually being weaker, so the better the players, the more they end up playing games where territory is even harder to evaluate.
> but that wouldn't ever have gotten us to the moon
Fitting analogy. There was a line in the film Blood & Donuts about the moon being ruined when they landed on it, which I couldn't really feel until today.
A top smartphone chess program can beat pretty much all but the best few players in the world. Do you think it's fair to pit a 150 gram device against a 70 kg human?
Although a fairer comparison would be against 1 kg of brain. Comparing against a human would need to include all the infrastructure for the device such as energy production or the manufacturing equipment required.
But nevertheless, fitting so much computing power in such a small device is a great achievement.
Not really, the brain to operate also needs all the other systems. Just as a CPU needs all the other parts to function. And including the manufacturing equipment is just as false, in the sense that you would have to include his mother (as biological manufacturing)
The human can run off resources that are available "in the wild", self-repair, and self-replicate at better than 1:1 (that is, a group of n humans produce >n offspring), whereas the smartphone needs a huge amount of infrastructure to repair it and produce new ones.
I don't think any mass comparison is really meaningful, mind, but it's not that simple.
Advanced chess players require a society which produces enough surplus to afford enough leisure to allow someone to not only produce a brain not damaged by starvation, but to allow them to use that brain to learn chess at a high level. It took a very long time for humans to get to that level, even though chess is a fairly old game.
My point is, humans "in the wild" likely didn't have any equivalent to chess, because they didn't have sufficient leisure time. Chess is a product of an environment that's just as "artificial" as the one which produced cell phones.
Games, including complex ones, go back a long way in human history. I've seen various claims about how much free time people have in primitive societies and I don't know enough to really know which are correct. The modern style of chess play relies on having openings books and computer assistance, but that's less true of go, which AIUI is learned largely through practice and a cultivation of taste and instinct (and the pieces can just be a set of stones and a grid scratched in the dirt).
Games may have existed, but the relative skill level of the players was likely a lot lower when people weren't spending as much time mastering the game, spreading and consuming strategy knowledge, and constantly holding events to compete and refine the best players.
I think the entire analogy is stretched a little thin of the players requiring all of this, but I also think the original attack on the Go AI based on it's mass is off base as well.
The story of Chess, according to Iranian mythological sources (recounted in Shahnameh) is that it was presented to the Iranian Court by the emissaries of the Indian Court, as a 'semantic puzzle' invented by Indian sages. (These games, it should be noted, were pedagogical in nature and used as symbolic means of training monarchs by the intellectual elites.)
The response of the Iranian sages was the invention of Backgammon, to highlight the role of Providence in human affairs.
The origin is unclear. The fact that the thematic of a game of war is prevailing now, to me means that it might have as well been in the beginning. Actually it shows at least that those semantics are relevant to war, and to live, so what I was saying stands.
Of course it involves war, but note how they teach the young prince it is (a) better to let the Vazier (your Queen) do all the heavy duty lifting, and (b) it is perfectly honorable to hide behind fortifications in a castle.
The self-repair and self-replicate come at a very hard cost, in the sense that it requires food, water and oxygen, while machines only need electricity. And the replication is actually incomplete in the sense that it starts in a very small state where it needs the three resources to actually become a complete human (adult) and dies if not taken care by a third-party in such early state (parents).
Plus, not far away in the future we will be able to connect an smartphone to a 3D circuit printer and print a new one, to achieve 'self-replication'
Seems like a pretty arbitrary limitation. 70 years ago Colossus filled an entire room, now it can be emulated on a Raspberry Pi. The really groundbreaking part is the algorithm.
1202 CPUs and 176 GPUs is the figure mentioned in the Nature paper. But it's important to understand that this is the computer used to train the networks used by the algorithm. It took about 30+ days worth of wallclock to train it. That's about 110 megawatt-hours (MWh) worth of energy required!
During the play, the computational requirements are vastly less (but I don't know the figures). It's still probably more than is feasible to put in a smartphone in the near future. Assuming we get 3x improvement in perf per watt from going to ~20nm chips to ~7nm chips (near the theoretical minimum for silicon chips), I don't think this will work on a battery powered device. And CPUs are really bad at perf per watt on neural networks, some kind of GPU or ASIC setup will be required to make it work.
That's not correct; those numbers refer to the system requirements while actually playing. To quote from the paper:
> Evaluating policy and value networks requires several orders of magnitude more computation than traditional search heuristics. AlphaGo uses an asynchronous multi-threaded search that executes simulations on CPUs, and computes policy and value networks in parallel on GPUs. The final version of AlphaGo used 40 search threads, 48 CPUs, and 8 GPUs. We also implemented a distributed version of AlphaGo that exploited multiple machines, 40 search threads, 1202 CPUs and 176 GPUs.
In fact, according to the paper, only 50 GPUs were used for training the network.
The cumulative amount of person-hours that went into training Lee Sedol (All the hours spent training his instructors, sparring partners, developing Go theory, playing out, and drawing inferrences from the outcomes of long-dead expert players) is probably more then 500 years. AlphaGo, on the other hand, had to start from scratch.
Given the rules, and a big book containing every professional go game ever played, and no other instruction, it's not entirely clear to me that Lee Sedol would be able to reach his current skill level in 500 years.
And thus why we're not destined to compete with AI, that 110MWh worth of training time can be instantly available to all other Go bots. If only I could have access to a Grandmaster's brain when I needed it!
Are they vastly less, though? The core of the algorithm is still a deep Monte Carlo Tree Search which AlphaGo gets quite a boost on computationally for being able to fire it off in parallel. It's obviously incorrect to take the training system and assume it's identical to the live system, but I think it's disingenuous to say the live system didn't have some serious horsepower.
Yes, for neural networks usually training them takes many orders of magnitude more resources than just using them.
For this particular example, training a system involves (1) analysis of every single game of professional go that has been digitally recorded; and (2) playing probably millions of games "against itself", both of which require far more computing power than just playing a single game.
I'm very aware of that. What I'm saying is that AlphaGo is not merely a neural net reporting best moves directly off the forward propagation. There are two nets which essentially act as proposal distributions for an exploration/exploitation tradeoff in the search space of game trees by which AlphaGo reads positions essentially out to the end of the game and ranks them by win rate (this is Monte Carlo Tree Search). The net moves are "nice" (I think they run at like 80% win rate against some other Go AIs? Maybe I'm misremembering) but the real heart of what makes AlphaGo play well is the MCTS which requires some vast resources to execute—live resources.
I was actually thinking primarily of distributed training time for the networks and playing time for the system, rather than the number of GPUs running this particular match. Also, I thought the number of GPUs in October was more on the order of 1,000? Happy to be told I'm mistaken though.
What a strange sentiment. You would only delay the inevitable outcome. Sure, it wouldn't win now, but processing power will become stronger and machines get smaller. What was the point?
Chess engines and processing power have since then advanced to a point where my phone can now reliably beat Carlsen. There is no reason to suppose Go is different in that respect. In 10 years, DeepMind will fit into a phone.
It's way more about algorithmic improvements than hardware improvements though.
Deep Blue evaluated 200 million positions per second. I don't think top programs of today could get to 2 million positions per second on a smartphone (I get about 10 million pos/second on my i7 3770 quad). It's all about improvements in search algorithms as well as position evaluation.
True. Without hardware improvements the processors that can evaluate 2 million positions per second while 'fitting' into a phone (qua processing power and power usage) would not exist though.
Besides disagreeing with you, this actually isn't true at all. In competition, AlphaGo doesn't rely on particularly expansive hardware. For training, yes, but not for playing.
Considering the complexity of the human brain, it seems only fair to balance out a competitor's handicap in some way. Your idea seems to anticipate the logical progression of these tests: "Nature made this mind inside this small object, the brain, why don't we do that?" Regardless, the trend of course is toward miniaturization. I see news like this recent story: "Glass Disc Can Store 360 TB" http://petapixel.com/2016/02/16/glass-disc-can-store-360-tb-...
to back up imagined futures like the film Her: https://youtu.be/WzV6mXIOVl4 (and that film doesn't even address whether the OSes are connected through a wireless network).
This stuff is happening fast, and we might have found ourselves, historically, in a place of unintelligible amounts of change. And possibly undreamt of amounts of self-progression.
It's the software that's impressive. Why does how many physical computers it takes to run the software matter? It's physical footprint will almost certainly shrink as computers get more powerful.
That's based on the assumption that computing must exist as silicon transistors. When would we have reached the bounds of computation based on physical limits if we had stuck with vacuum tubes. The point is computation is an abstract concept and not tied to the physical medium that we use.
Of course there are physical constraints on computing, but measuring by weight is rather stupid. Measuring the energy consumption seems to be a way better metric (even though "computation per energy" is clearly a human win).
Not to mention that we suddenly forgot that computers have their own units of measurement, such as clock speed (hertz) and memory size (bytes).
> (even though "computation per energy" is clearly a human win)
Is it? The problem here is it is really hard to compare the TCO. For example prime human computation requires years and years of learning and teaching, in which the human cannot be turned off (this kills the human). A computer can save its state and go in a low or even a zero power mode.
>such as clock speed (hertz) and memory size (bytes).
Which are completely meaningless, especially in distributed hybrid systems. Clock speed is like saying you can run at 10 miles per hour, but it doesn't define how much you can carry. GPUs run a far slower clock speed than CPUs, but they are massively parallel and are much faster than CPUs on distributed workloads. Having lots of memory is important, but not all memory is equal and hierarchy is even more important. Computer memory is (hopefully) bit perfect and a massive amount of power is spent keeping it that way. That is nice when it comes to remembering exactly how much money you have in the bank. Human memory is wonderful and terrible at the same time. There is no 'truth' in human memory, only repetition. A computer can take a picture and then make a hash of the image, both of which can be documented and verified. A human can recall a memory, but the act of recalling that memory changes it, and the parts we don't remember so well are influenced by our current state. It is this 'inaccuracy' that helps us use so little power for the amount of thinking we do.
TCO? I'm mentioning solely the electricity the machines consumes (by machine I mean both the human brain and the computer).
Are the units I proposed perfect for the job? Of course not, just look how much you wrote. But I bet that if you do the same "thoroughly" analysis for measuring computing by weight you'll be able not only to write a fat paragraph such as your last one, you can write a whole book on who wrong/meaningless/stupid it is (not that anyone would read such book though).
...it was the last stand of homo sapiens in the man vs machine...
But who made that machine?
I'd say a more precise evaluation would be that the ability to program a machine to assist in playing chess outdid the ability to play chess without such assistance.
This is my generation's Gary Kasparov vs. Deep Blue. In many ways, it is more significant.
Several top commentators were saying how AlphaGo has improved noticeably since October. AlphaGo's victory tonight marks the moment that go is no longer a human dominated contest.
It was a very exciting game, incredible level of play. I really enjoyed watching it live with the expert commentary. I recommend the AGA youtube channel for those who know how to play. They had a 9p commenting at a higher level than the deepmind channel (which seemed geared towards those who aren't as familiar).
I totally recommend it. Learning Go is a beautiful experience.
It is indeed very interesting to play against another new player just to see what you come up with, then do some reading and solve some basic problems (it may even be a good idea to have a look at the easier problems before playing your first game), play more games, read more advanced books, join KGS... It is a very nice rabbit hole to fall into.
Many Go players suggest starting with Atari Go (aka Capture Go). It has the same rules as Go, but the starting position is predetermined and the winner is the player to capture the first stone.
You only need to play a few rounds of Atari Go, say 30 minutes to an hour to get a grasp of the capturing rules and then you can move to a 9x9 or 13x13. I'd go straight for the 13x13 because it's not that much bigger but it has much more depth into it without being overwhelming. And many Go boards have 19x19 on the other side and 13x13 on the other.
The drawback with Capture Go is that it emphasises the capturing part perhaps a bit too much. I prefer introducing players to a variant with the same rules as capture go, except the winning condition is "having the most pieces on the board". This is essentially the same thing as regular go, but without all the fuffing about with learning scoring and such.
When played on a small enough board, the games take about as long time as capture go games.
> The drawback with Capture Go is that it emphasises the capturing part perhaps a bit too much.
I definitely agree. Just a few games (ie. just a few minutes) of Atari Go every now and then should be enough to teach that and then move on the the real thing.
Yep, terrific commentary by Myungwan Kim 9p on the AGA channel.
For the folks who aren't as familiar with the game, how did you find the commentary (for any channel)? What would you be interested in hearing for events like these?
I watched most of the game on the Deepmind Youtube channel. Although I barely know the rules of Go, it was really nice that explained a lot of the strategies, although aside from the basic explanations most of the rest still flew over my head. I was still hooked, though.
However it was infuriating that many times they switched randomly between video feeds, so I couldn't actually see what the commentators were talking about on their board. Once it even got stuck on "Match starts in 0 minutes" for a couple minutes!
I've been finding it pretty unwatcheable. Does anyone know of a version that doesn't have the technical issues? (I'm very happy with the commentary, but the video keeps cutting to this 0 minutes screen and audio is patchy).
Same the "game will start in 0 seconds" thing kept cutting the audio in and out, and obstructing the board footage. Terrible for an uploaded youtube clip. I can understand issues with the live stream. But it's already over. Couldn't someone have edited that out?
Those technical issues were only a problem a few times at the beginning of the broadcast. 99% of the footage is fine, just stick with it. The problems disappear.
I really enjoyed Myungwan's down-and-dirty commentary, and watching him get lost in some variations, and it was just incredibly exciting to see him get won over to AlphaGo during the game. From about move 50, I was just viscerally excited to see where things went, and the game did not disappoint in any way.
I've read a few different reviews and watched Michael Redmond's live commentary as well, who obviously has a slower Japanese style of play than Myungwan, and his variations all exhibited a very thorough style and sensibility, but I think he missed the key moment, and Myungwan called it -- the bottom right just killed Lee Sedol, and it was totally unexpected.
And, Sedol was thinking about it too, because right after he resigned, he wanted to clear out that bottom right corner and rework some variations. I presume that's one frustration playing with a computer -- they'll have to instrument AlphaGo to do a little kibbitzing and talking after a game. That would be just awesome.
If you are very, very inspired by AlphaGo's side of this, it's really incredible to imagine, just for a moment, that building that white wall down to the right was in preparation for the white bottom right corner variation. The outcome of that corner play was to just massively destroy black territory, on a very painful scale, and it made perfect use of the white wall in place from much earlier in the game.
If AlphaGo was in fact aiming at those variations while the wall was being built, I would think at a fundamental level, Go professionals are in the position that chess grandmasters were ten years ago -- acknowledging they will never see as deeply as a computerized opponent. It's both incredibly exciting, and a blow to an admirable and very unusual group of worldwide game masters.
Building the wall down to attack the bottom right corner isn't something outrageous, not to those at the level of Sedol. AlphaGo definitely played amazing, as the game was very technical in term of fighting. But the "flow" (chase out weak group then invade a corner) is a fairly common situation. I don't think it's a matter of AlphaGo seeing strategy further than Sedol. It might have had much deeper calculation and reading than Sedol - as showed in deflecting the attachment in lower right - but that's a bit of a different story.
I'm planning to watch the AGA coverage later, after watching the DeepMind coverage live. I found the DeepMind pair a bit underwhelming. Redmond was excellent at playing through some variations, but they did get very distracted at times, and away from what was actually happening. His co-host was playing a little too strong on the 'I'm so nervous' line, I felt. So I didn't spot the significance of the bottom right pivotal moves. Thanks for the recommendation, I'm looking forward to the AGA coverage even more now.
Having worked on some code very similar to this, showing the computer's best moves would be quite artificial. Here's some thoughts as to why that is:
1. The computer can discard all its current best ideas and flip through new ones so fast, it would be a flickering blur to humans.
2. Even if we put a speed limit on it, the move being considered is itself the result of considering a lot of slight variations.
3. The ability to _articulate_ in a human language what makes the move nice is itself a "hard problem" closely related to natural language processing.
4. Even just having some color codes or symbols and grouping related ideas has some serious problems: now the visualization is pretty technical to begin with, the computer is still able to memorize and compare moves at an unbelievable rate, and it's still fundamentally not the same as the method Go masters use to find a solution.
I can back this up a bit. I created a strong Chess engine variant and had it visually show what the computer was considering as moves with strengths as color strength. It would even show what it considered your best counter-moves.
Even with all that thinking output on the screen, the computer would still soundly beat myself and another (intermediate) player.
Here are some screenshots to illustrate what I'm talking about:
Regarding the first one, I don't think this would be a serious issue. It shouldn't show what move its considering, just the current best option. It would probably converge on a good move within the first second. Running the free, quick analysis from chess.com on my Iphone has a great visualization that rapidly updates the computer's scoring of the current position and shows what it thinks is the best move, as well as pointing out any previous moves it thinks are mistakes/blunders.
I watched the commentary on Youtube and it was fantastic! I don't play go myself but I was glued to the screen the whole way. I particularly enjoyed how the commentators demonstrated why the moves made sense by playing theoretical future moves right on the board they had up.
I really enjoyed the deepmind channel, but it's too long for me to enjoy in its entirety. I think a 15 minute video recapping the game and its crucial strategic moments would be fascinating.
I don't know much about go, so it was like a long Go lesson. That was interesting, but in terms of immediate gratification it was pretty dull. One very calm hyper-focused person describing what another very calm hyper-focused person is doing.
Many thanks! I checked their youtube channel many times during the game, hoping they would cast this, as I found the Redmond commentary a little too shallow.
I don't understand how the AGA live stream didn't appear there for me?!
It can be hard to bite your tongue when you see the other (non-native) speaker struggling for words...
Andrew Jackson's role is invaluable in clarifying MyungWan Kim's thoughts: the infamously opaque "play this one, and then this one", or his white/black colour mix ups...
I personally think they're a good combo. Andrew is getting gradually better at only jumping in when necessary.
The game was bound to be exciting due to the matchup. AlphaGo's moves were for the most part not exciting for much of the match, IMO. It seemed content to follow the outline that was unfolding rather than setting an agenda, and executing really well towards the end. I can't wait to see how it plays as black and moving first.
It either seems like the earlier match vs Euro 3p didn't show AlphaGo's full strength, or it has improved much in the interim. Other takes?
I was really hoping to see a more technical discussion than what I found here in the comments. It's too bad that such a cool accomplishment gets reduced to arguments about the implications for an AI apocalypse and "moving the goalposts". This isn't strong AI, and it was at least believed to be possible (albeit incredibly difficult), but it is still a remarkable achievement.
To my mind, this is a really significant achievement not because a computer was able to beat a person at Go, but because the DeepMind team was able to show that deep learning could be used successfully on a complex task that requires more than an effective feature detector, and that it could be done without having all of the training data in advance. Learning how to search the board as part of the training is brilliant.
The next step is extending the technique to domains that are not easily searchable (fortunately for DeepMind, Google might know a thing or two about that), and to extend it to problems where the domain of optimal solutions is less continuous.
They used the game database to learn the value network, then reinforcement learning of the policy network was performed on self-play games. I.e., the machine learned to play from existing data, then played against itself to learn the search heuristics (the policy network) without the need for expert data.
Your claim still doesn't make sense. They either used expert data or they didn't. If the algorithm would lose when they remove the expert data, then they really do need expert data.
The tree search wasn't even the novel part of the algorithm... the authors even cite others who had used the identical technique in previous Go algorithms.
It seems that my original comment is unclear. My apologies for the ambiguity. I did not mean that they do not need any expert data, but that part of the training did not require a training data set.
They definitely need training data to learn the value function, but training the policy network is based on self-play. While MCTS is not new, I believe bootstrapping reinforcement learning with self-play to train a policy network that guides the MCTS is novel.
I posted in the earlier thread because this one wasn't up yet[1].
Some quick observations
1. AlphaGo underwent a substantial amount of improvement since October, apparently. The idea that it could go from mid-level professional to world class in a matter of months is kinda shocking. Once you find an approach that works, progress is fairly rapid.
2. I don't play Go, and so it was perhaps unsurprising that I didn't really appreciate the intricacies of the match, but even being familiar with deep reinforcement learning didn't help either.
You can write a program that will crush humans at chess with tree-search + position evaluation in a weekend, and maybe build some intuition for how your agent "thinks" from that, plus maybe playing a few games.
Can you get that same level of insight into how AlphaGo makes its decisions?
Even evaluating the forward prop of the value network for a single move is likely to require a substantial amount of time if you did it by hand.
3. These sorts of results are amazing, but expect more of the same, more often, over the coming years. More people are getting into machine learning, better algorithms are being developed, and now that "deep learning research" constitutes a market segment for GPU manufacturers, the complexity of the networks we can implement and the datasets we can tackle will expand significantly.
4. It's still early in the series, but I can imagine it's an amazing feeling for David Silver of DeepMind.
I read Hamid Maei's thesis from 2009 a while back, and some of the results presented mentioned Silver's implementation of the algorithms for use in Go[2].
Seven years between trying some things and seeing how well they work and beating one of the best human Go players. Surreal stuff.
Regarding 2, the point is that a valid move in Go is to put a stone everywhere on an empty position each turn on 19x19 grid. So the number of valid move is not comparable at all with Chess.
What an incredible moment - I'm so happy to have experienced this live. As noted in the Nature paper, the most incredible thing about this is that the AI was not built specifically to play Go as Deep Blue was. Vast quantities of labelled Go data were provided, but the architecture was very general and could be applied to other tasks. I absolutely cannot wait to see advancements in practical, applied AI that come from this research.
The position evaluation heuristic was developed using machine learning, but it was also combined with more 'traditional' algorithms (meaning the monte-carlo algorithm). So it was built specifically to play go (in the same way deep blue used tree searching specifically to play chess.....though tree searching is applicable in other domains).
I just wrote a blogg about this. I was up to 1am this morning watching the game live. I became interested in AI in the 1970s and the game of Go was considered to be a benchmark for AI systems. I wrote a commercial Go playing program for the Apple II that did not play a very good game by human standards but did play legally and understood some common patterns. At about the same time I was fortunate enough to get to play both the woman's world Go champion and the national champion of South Korea in exhibition games.
I am a Go enthusiast!
The game played last night was a real fight in three areas of the board and in Go local fights affect the global position. AlphaGo played really well and world champion (sort of) Lee Sedol resigned near the end of the game.
I used to work with Shane Legg, a cofounder off DeepMind. Congratulations to everyone involved.
I watched the commentary that Michael Redmond gave (9-dan-professional) and he didn't point out one obvious mistake that Lee Sedol made the entire match. Just really high quality play by AlphaGo.
Really amazing moment to see Lee Sedol resign by putting one of his opponent's stones on the board.
Yeah according to Redmond, it seemed that AlphaGo made a few "mistakes" whereas Sedol made none. And yet AlphaGo came out substantially ahead. So I'm not sure what that means. Perhaps we need to see more in-depth analysis of the moves, but it seems that AlphaGo just out-calculated Sedol.
I wonder if their move selection algorithm takes into account the "surprise" factor: given two moves that are almost equal in strength when analyzed to a depth of N, chose the one that looks worst at N-1. That is, if all else is equal, assume that you can search deeper than your human opponent, and lay traps accordingly.
Besides trap-laying, there's also a second useful "surprise" factor: your opponent is likely to have spent time on your clock to read out follow-ups to your most likely move. By throwing in an unlikely (but still good!) move you're forcing them to expend time on their clock to re-think their follow-ups.
That's interesting. And a sign of truly understanding what a human would think.
Btw. There's a concept in Go called "overplaying". That means selecting a move that isn't objectively the best you could come up with, but that is most confusing, considering the level of the opponent. It's generally thought of as a bad practice, and if you misestimated the level of your opponent, she can punish you by exploiting the fact you didn't play your best move.
I don't know about surprise, the the AKA stream was pretty shocked when AlphaGo was playing aggressively from the 5th line/column from the right early in the game. Apparently going in on the 3rd is already very risky and the 4th is almost never done.
According to DAVID ORMEROD in his commentary at https://gogameguru.com/alphago-defeats-lee-sedol-game-1/, black (Lee Sedol) made plenty of mistakes from the start to the end, and they were seriously questioning his form. White (AlphaGo) made only a few mistakes in the middle, which allowed Black to catch up a bit, but he had no chance, esp. in the endgame.
I would love to see an expert analysis of the game, but there were definitely a few moves where AlphaGo was "pushing from behind" that were probably not what an expert human would play.
Yeah. It was the bottom right corner that I talked about. But some speculation says it was part of AlphaGo's plan so I am extremely looking forward to today's game now.
According to Myungwan Kim, 9p, commenting on the game in the AGA channel [1], Lee Sedol made a mistake right at the beginning and spent the rest of the game hoping to claw it back; he said he would resign about 15 min before he did.
EDIT: but this postmortem [2] of the game is far more nuanced and doesn't reach the same conclusion.
I was really expecting Lee Sedol to win here.
I'm very excited, and congratulations to the DeepMind team, but I'm a bit sad about the result, as a go player and as a human.
That is a gigantic over-simplification. All machines are application specific, even machine-learning based ones. They all require human supervision, whether through goal setting or fixing errors.
There are some areas where machines are better than humans, and playing Go is now one of them, but that doesn't mean machines will replace humans in all facets at any given point in time. We grow, our tools grow, and the cycle repeats.
Skill related. I'd be interesting to see how quickly driving AIs take to beat the best human drivers, in a weight-equal vehicle. An algorithmic competitor in formula one, would be interesting.
Racing cars aren't limited by the driver's G tolerance, I don't think. They generate 4G-ish, from what I hear on the F1 coverage. Well within driver capabilities. Their G is limited by tyres.
The recent video of Boston Dynamics Atlas robot looked like it could walk about as well as a human, maybe even better at recovering its balance (see it heroically walking through snow).
I see "AI" doing well in games that have simple inputs, a limited range of legal outputs, and relatively easy "goodness" measures.
I see nothing that might be able to tell us why gravitational mass is the same as inertial mass, for example, or any moves in that direction. This "AI" is good at simple games.
Renting them in the cloud for a single game should actually not be all that expensive. Around 100 USD per game perhaps? And the price is only going to fall.
An Amateur can learn plenty from slightly weaker version on less hardware already.
"AlphaGos Elo when it beat Fan Hui was 3140 using 1202 CPUs and 176 GPUs. Lee Sedol has an equivalent Elo to 3515 on the same scale (Elos on different scales aren't directly comparable). For each doubling of computer resources AlphaGo gains about 60 points of Elo."
So has AlphaGo raised its level so far just by continuing with the games against itself? Or did they just throw their entire server farm at it? (Or both, probably.)
Facebook's Go engine is not remotely close to competing with AlphaGo. In fact, it's about comparable to the pre-existing top Go programs; the only newsworthy thing about it is that it's from Facebook and it uses neural nets.
Since AlphaGo's architecture was published in nature, wouldn't it be somewhat straightforward to reproduce something similar to it given the resources of Facebook and an already existing team of people tackling Go? I would expect other Go software to quickly follow in AlphaGo's footsteps and then build on it, perhaps surpass it by adding some different optimizations.
Just a question to throw out there - does anyone feel like statements like this one "But the game [go] is far more complex than chess, and playing it requires a high level of feeling and intuition about an opponent’s next moves."
… seem to show a lack of understanding of both go and chess?
I understand there may be some cross-sports trash talking, but chess, played at a high level by humans, relies on these things as well. The more structured nature of chess means that it is (or at least was) more amenable to analysis by brute force computer algorithm, but no human evaluates and scores hundreds of millions of positions while playing chess or go.
Eh, the mainstream media is going to say this regardless, and I suppose it's just unrealistic to expect them to draw a distinction between complex for humans and amenable to brute force computation but statements like this always seemed to show a remarkable lack of awareness of how people actually play these games (though I am not an especially skilled chess or go player).
No, I think the statement's approximately correct. Chess has an average branching factor of 35, Go has an average branching factor of 250, intuition is required to prune candidate moves in Go in a way that it is only extremely minimally required in Chess.
But is this true as humans play it? I'm not good enough at either to really know for sure, but my impression is that while the branching factor makes a big difference for computers, it is essentially impossible for a human to manage the branching in either game (massive numbers of branches vs exceptionally massive numbers of branches). As a result, humans play both games at a high level by relying on intuition.
For instance, I read a while back (approximating and paraphrasing to follow...) that top chess players can think up to 10 moves ahead along a very few branches. So let's say that in chess, there are 30 million possible positions to evaluate, and in go, there are 300 trillion. They're both such an order of magnitude different for humans that it makes really no difference in terms of how we play the game, so intuition takes over. For computers, it's a different story.
I think humans usually have ten or less plausibly-good moves to consider per turn in Chess, and simply consider all of them, compared to tens to hundreds in Go.
I know I will offend chess players by saying this but.. I feel like chess is more of a IQ contest, while Go is more Art-ish in how you move and slowly cripple and surround your opponent.
Realistically speaking, there aren't that many moves you can do in chess. Most of them are just blunder that would get you insta-killed by a good player. Contrast that to Go where there are so many good moves. This is why I think the Go AI is more impressive.
Part of me thinks that at some point in the future, we'll have Chess "solved". Not in a "That computer is too good for humans", but more in a mathematical sense where all avenues will have been explored and at any point you mathematically know from a position whether you 100% win. So, the computer will make a move, a second computer will make a move, and then they will agree on a draw. To be able to achieve this, I think it will be some kind of rainbow table for chess (on a much bigger scale obviously), where you can represent one position by a hash and just brute-force all possible solution from the "end-game" to the initial board. So, it's not even about AI, more about bruteforce and hardware. I know it's not possible to do this at the moment but quantum computing would be.
Totally could be the same for Go, but yeah the search space seems much bigger. I feel in chess there are a few good moves on every turn whereas for Go it seems there are so many. But then, it may be because I'm less good at Go and I don't see the "obvious" move, not that I necessarily see it in chess but you know what I mean.
think of it this way:
The search space for chess is much smaller, so we can lean very heavily on brute forcing in our A.I. implementations.
The search space for Go is much larger, so while brute force searches are critical in tight fighting, and in endgame play, something more has to happen to play go well in the middle game.
Chess fell to a much earlier generation of A.I.
While Go held out until A.I. as a field had advanced as well several generations/decades as well.
Agreed. The part I object to is the unqualified statement that go requires a high degree of intuition, whereas chess doesn't. As humans play the game, I think it's safe to say that this is generally inaccurate. Both games, for humans, rely very heavily a high degree of intuition.
I would tend to agree that there is something interesting and new at work here, though, in that computers didn't get better than humans at go simply by applying the same brute force algorithm, just with more processing power. It does suggest that at least some of what we previously thought required "intuition" can be modeled through a random forest (I think that's what they're using, if not RF, then some other combination of ML).
In the video for the second match, a Google employee mentions that a neural net they call the policy net (trained on a large sample of historical games) provides intuitive moves, while another NN evaluates board strength. They apply the policy net to find multiple interesting moves, then continue to apply the net to anticipate the opponents moves to generate a tree of possible moves. It then just settles on which move to make that gives it the best odds of winning
I can't comment on Go, but with simpler games like Othello it's fairly apparent when your opponent is A.I. driven or human driven, in how they try to move the board position. Even against expert human players.
In suppose the defence of the statement is that in chess intuition is used by humans, but not required for a computer. In go the computer needs it too.
The funny thing about AI at this scale is we don't really know why the computer does what it does. It's more of a inductive extrapolation that we can verify that a technique works for a small problem, so we'll throw a whole bunch of GPU power and data at it and it SHOULD work for a big problem. How it actually works is fuzzy though as there's just a couple of gigabytes of floats representing weights in neural networks. No human can look at that and say: "Oh! I see why it made that move". It's so much data that it becomes kind of nebulous what the AI is doing.
It certainly seems incomprehensible now, but that isn't necessarily true in neural networks - the amazing thing about some of the experiments using the results of intermediate layers in image recognition is that they seem to be building up higher and higher order "understanding" as you get to deeper and deeper layers which correlates directly with how a human might explain their strategy.
You can imagine a means of interpreting intermediate layers of alphago's weighting function similar to the second image in [1] (not the best example, I apologise) that would produce images or other abstract representations of the strategy that layer was encoding, similar to how a human might classify moves or patterns into categories.
Seems to be similar for intuition in humans–some moves just feel right, and they're the result of thousands of hours of experience. You can justify it afterwards, but the intuition itself usually comes first.
The AI google designed is architected similarly to how the brain works in dual process theory: you have a NN providing intuition like system 1 and a supervisor much like system 2 which double checks system 1
The neural net guides the search for the right move, but the program ultimately considers many possible sequences and picks the one it thinks is best. The program could justify its choice in the same way human players do: by playing out alternative choices and showing how those choices would have put it into a worse position.
> No human can look at that and say: "Oh! I see why it made that move".
Well, it depends. During the game last night there were quite a few forced moves that require an immediate and unique reply. The motivation for the reply is quite clear. But that's the simple stuff.
The obvious problem is that speed of tactical execution can make up for a lot of strategic thought. The famous example: you can rush a line of siege tanks with zerglings if you can micro them fast enough[0].
That's great and all, but it's already been done by much more simplistic algorithms by abusing the mechanical nature of the game.
Some units are balanced by the fact that no human can manipulate them to their full potential. Once you remove that restriction, the AI can abuse the speed of execution, acting as a force multiplier that will cover any strategic lackings.
If they want DeepMind to really "play" Starcraft in the traditional sense, i.e. make it win based on decision making and reasoning about the game, then they'll need to artificially rate limit its APM.
It was designed to be hard to win with the algorithms known to researchers back then. I cannot tell if it has something substantially harder than Go has. High branching factor, deep tree and positions that are hard to evaluate with a simple heuristic are present in Go. Does Arimaa have something else up its sleeve?
A human was beaten with some thousands of CPUS & GPUS. On a calorie level, the human is still more efficient.
On a time to learn these skills... going from zero (computer rolls off assembly line) to mastery, the computer wins.
Actually maybe the computer wins even on the caloric level, if you consider all the energy that was required to get the human to that point (and all the humans that didn't get to that point, but tried).
But the computer certainly does not win on the amount of training samples required.
The human is at the same level as the computer now for Go, but the computer has had much more training samples as Lee Sedol could process in his lifetime.
The next step is to reduce the training time/samples for the computer to get the same performance.
Learning is the ability to generalise from examples. Learning is far easier to define than intelligence. Whether algorithms can learn better than humans (generalise better from the same training data) is actually probably a more interesting question than whether they can get better results given unlimited data.
EDIT: But come to think of it this is a bad example, because you don't need any training data at all to learn to play a game well. Computer programs can play against themselves and rediscover strategies that work well. It's just an advantage.
I don't want to put a limit on the computer, not at all.
But I do think humans have an edge on computer because at least for now, humans can learn the same skills from less samples (at least in this example: Go)
Of course, if there are many samples, the computer can go through those faster, but if there are no samples already and the computer has to learn example by example as humans do as well, humans may still have an advantage.
Of course, this advantage will diminish as well as AI advances.
How do you count examples? The computer can generate its own examples by playing against itself. So in theory it needs 0 examples. This is not a useful metric at all.
What I mean is that I am more impressed by anyone of anything that can do a task (go, golf, chess, learning a foreign language, doing the dishes even) well with just a single example, or e.g. an hour of training.
Being able to train in solitude is an advantage indeed. You need two humans to do this, but you also need two AlphaGo-instances as well.
Are you going to count all the games that the human played in their head too? What about the learning done in the human brain when sleeping? Do you count that too?
I don't think it's silly at all. I think you have a good point about this particular contest, but there are plenty of other applications where training data is prohibitively expensive or time-consuming to collect. One way to proceed is to work on making it easier to collect and curate this data, and another is to work on algorithms that require much less data to obtain good performance.
That's a good point, but it's still orders of magnitude below what a human -- even a devoted one -- could ever review.
Of course, there are many ways you can do the comparison:
Time to build: The AlphaGo team didn't have billions of years of evolutionary tinkering to work with in refining biological heuristic/learning systems.
Hardware limits: though still more efficient at search than previous designs, AlphaGo still has a lot more storage space and inter-component bandwidth than a human brain, plus better latency. Will the algorithms improve to the point that they can perform well on an extremely restricted architecture?
Beating humans in Go is, in itself, not all that exciting. Go bots have been beating strong humans for quite some time now (just not the very top humans).
There are other implications that make this AlphaGo progress super exciting though. Go captures strategic elements that go well beyond the microcosm of one nerdy board game.
That's the real reason Go has been around for >2,000 years, and why this AI progress is relevant, despite its limited "game domain".
I wrote about it here, from my perspective of an avid Go player & machine learning professional [1].
I disagree with this due to the rate of AlphaGo's progress. Consider CrazyStone which was the previous state of the art in Go computers. That program reached 5dan after many years of development and has not shown any signs of being able to reach Lee Sedol level (9dan).
In October of this year AlphaGo beat a 5dan player, bringing it into the range of CrazyStone. Only ~6 months later it beats a 9dan player which means it is now ~400 Elo higher. This means the new version would be predicted to beat the old version ~99% of the time.
Such incredible consistent progress of a problem considered somewhat intractable is notable and exciting. Imagine where this machine will be in 6 more months.
Yes, AlphaGo's progress is amazing. I don't think there's any disagreement there :)
But I don't think you know much about Go, if you can say Fan Hui is "just" 2 dan professional.
What do you reckon the strength difference is between 2p and 9p?
Nitpick: while AlphaGo today is certainly stronger than AlphaGo last October, it doesn't follow in any way from the fact that both programs beat their respective opponents. A > B, C > D, D > B, therefore C > A? By "400 ELO", no less?
Yes. This is the point. To what extent can AlphaGo transfer what it has learned in Go to other domains. It was a very smart move to train their first AI on Go!
Can someone explain why this is more impressive than a computer beating top chess players over a decade ago? I'm not very familiar with Go, and while there were far more squares on a Go board, it seems less sophisticated than chess to me.
Maybe Go has way more moves possible and emergent strategies or something I'm not taking into account.
Here's a way to measure the sophistication of a game of skill. Consider two players A and Z. A is a ten-year-old who has just been told the rules; Z is God. Now, in between them, put a series of other players B, ..., Y, where B beats A 2/3 of the time, C beats B 2/3 of the time, ..., Z beats Y 2/3 of the time. (We assume God doesn't use his magical divine powers to cheat by, e.g., making Y play bad moves.)
Unfortunately, God is not readily available for comparison, so we'll use the best human players instead.
How many links are there in that chain? The more there are, the more there is to learn about the game, and hence the deeper and more sophisticated the game is. (So you might think, anyway.)
If you rate players using the Elo system, beating someone 2/3 of the time corresponds to being about 150 points stronger. A complete beginner at chess might have an Elo rating of 500, compared with the world champion somewhere around 2900, giving 16 links in the chain.
In go, beating someone 2/3 of the time corresponds to being about one kyu/dan rank stronger. A complete beginner might be 30 kyu; the best players are stronger than 9 amateur dan, so that's at least 40 links in the chain. (Lower-numbered kyu ranks are stronger; after 1 kyu comes 1 dan, and then higher-numbered dan ranks are stronger.)
So by this measure -- which you may or may not find convincing -- go is a more sophisticated game than chess.
Here is the best argument I know against this definition. Define the game of "tenchess" as follows. To play a game of tenchess, you play ten games of chess and the winner is whoever wins more games (a draw if the same number). Then it's easy to see that tenchess has a longer chain, as defined above, than chess; if I win 2/3 of my chess games then I win 79% of my tenchess games, so I can win 2/3 of my tenchess games with a smaller advantage. (I am ignoring the existence of draws for this calculation, just for simplicity.) But surely tenchess isn't a deeper game than chess; it's just longer. Perhaps go's longer chain is just the result of its being a longer game.
> In go, beating someone 2/3 of the time corresponds to being about one kyu/dan rank stronger
This isn't true. One kyu/dan rank stronger means being 1 stone stronger (so winning 50% of the time when playing White with reverse komi). In practice this may correspond to winning 2/3 of the time with normal komi for high dan players, but that doesn't hold for low kyu players. A 29k has maybe a 51% chance of winning against a 30k because both will make huge mistakes. So although the 29k can score on average 13-15 more points than the 30k in a given game, this advantage is swamped by the large standard deviation of scores in beginner games, turning the win/loss outcome into essentially a coin flip.
Fair comment about very weak players. My impression is that the element of chance goes way down well before you get to high dan level, though. How sure are you that I'm wrong?
Quite sure. 17k players still make many huge mistakes, and at the other extreme, God (say 13d) would win 100% of the time against a 12d player. Given that the win ratio for a one rank difference starts at 50% for extreme beginners and ends at 100% for God, maybe you should be the one explaining why you'd expect a significant plateau at 2/3 instead of a smooth increase.
I agree. In particular, I wasn't arguing for anything special to happen at p=2/3. I was hopeful, though, that p=2/3 might be a tolerable approximation over a reasonable range of skill levels.
Having played a bit with some toy models, I've changed my mind a bit; my guess is that p=2/3 is a reasonable approximation for few-dan and few-kyu amateurs, but that outside, say, the 5k-5d range it's far enough off to make a substantial difference.
So, what does this do to those (anyway fairly bogus) "depth" figures? My crappy toy model suggests that for a 2/3 win probability you need a 3-rank difference around 24k, a 2-rank difference around 12k, a 1-rank difference around 2d, a 0.5-rank difference around 8d. And I estimate God at 15 amateur dan (if Cho Chikun is 9p and needs 4 stones from God then God is 21p; if, handwavily, 9d=3p and one p-step is 1/3 the size of one d-step, then God is 21p = (3+18)p = (9+6)d = 15d). So we need maybe 20 steps from God to 5d, then maybe 10 from there to 5k, then maybe 5 from there to 15k, then maybe 5 from there to 30k. That's 40 steps -- not so very different from what we get just by pretending one rank = one "2/3 win probability" step, as it happens.
The tenchess counterargument doesn't work in the context of Elo (from which chain lengths are derived).
A has 150 more Elo rating than B in chess. Elo says A has a 2/3 EV on the game result, and B has 1/3.
In tenchess, A will get 20/3 points on average and B will get 10/3 points. A will have more points than B in 79% of tenchess games, but the Elo ratings will not change. Elo doesn't consider winning and losing as binary. (This is why draws behave sensibly.) Just as a tie between these players cause A to lose rating, so too would a marginal win from A.
I think I wasn't clear enough. Here is how you play a game of tenchess. (1) Play ten games of chess. (2) You get 0 points if you won fewer chess games than your opponent, 1 point if you won more, 1/2 a point if you won the same number.
In particular, you don't get the total number of points you'd have got by playing the chess games individually. You get 0, 1/2, or 1. In particularly particular, A doesn't get any fewer points from a marginal win than from a blowout. (Just as, when playing chess, you don't get fewer points from taking 100 moves to grind out a tiny positional advantage than from a 20-move brilliancy.)
So A and B don't get 20/3 and 10/3 points on average from a game of tenchess; that's the number of "chess points" they get on average, but the average of the number of chess points isn't a thing that actually matters when they're playing tenchess.
(If A wins 2/3 of the time at chess and they never draw, then it turns out that A gets about 0.855 points per tenchess game.)
"The game has long interested AI researchers because of its complexity...the average 150-move game contains more possible board configurations — 10^170 — than there are atoms in the Universe, so it can’t be solved by algorithms that search exhaustively for the best move."
Chess is quite tactical and brute-force-y -- the board is quite small, games are quite short, and there aren't all that many possible moves at any given point.
A program can play pretty good chess on modern hardware just by alpha-beta searching with a fairly simple evaluation function for the leaves of the search tree.
The best programs are cleverer than that; they have sophisticated evaluation functions, they prune and extend their searches, etc. But at heart, what makes them so strong is that they can search deeply.
That approach doesn't work so well for go. The board is 6x the size, games are 4x as long, the "branching factor" (number of moves available in a given position) is 10x as large. (All figures very crudely approximate.) If you try to make a fairly-dumb searcher in go, it will play very badly.
So how do humans manage to play well in go? By smarter searching, with a better idea of what moves are worth considering; by thinking strategically; by having a feel for the shape of a position ("moving here is likely to be very valuable").
Those are all things that feel like they are harder to make a computer do, and come closer to actual intelligence, than doing well at chess just by doing an enormous search.
The first of those is certainly correct. AlphaGo (like most modern go programs) organizes its searches in quite a different way from a typical chess program. It's not clear how far it deserves to be called smarter, though, since a lot of what it's doing is playing out lots of games fairly stupidly[1] and seeing how they go on average.
[1] Compared with how it actually plays. One of the achievements of AlphaGo, I think, is that it can reasonably quickly select moves for its playouts that are actually pretty good.
The second is more debatable. But, e.g., AlphaGo selects and evaluates moves using neural networks trained on a large amount of high-quality play, and the effect of this is that given a position it can quickly "see" how good it thinks the position is and what moves might be effective, without doing any searching, as a result of feeding the position through a big neural network that does some mysterious calculation we don't understand well. Which is, at that level of abstraction, pretty similar to what you might say about a human go player.
Whether any of this has any bearing on more general artificial intelligence is an entirely different question, which I will not attempt to get into.
Firstly there are vastly more positions in Go.
Secondly, it's very hard to evaluate a Go position, especially at the start of the game when there are few stones on the board. In chess you can get a long way using a simple evaluation (K=99, Q=9, R=5, B=3, N=3, P=1).
>In chess you can get a long way using a simple evaluation (K=99, Q=9, R=5, B=3, N=3, P=1).
I guess it depends on your idea of a "long way". Using only your simple evaluation a program would be rated somewhere around 1000-1200. It would lose every single game to an average tournament player.
In chess there are various pieces with differing powers, with Go it seems like they all have similar powers. Again, I don't really know the game and might be wrong, but that was my impression.
One thing that's cool about Go is that the pieces get their value and power not from the rules, but from how they are used. In an actual game of Go, you will find groups of ten pieces that are casually thrown away, and you will find single pieces that the whole game revolve around. In the rulebook, they are the same piece, but in actual effort expended to save/attack them, you'll see they're valued vastly differently.
This happens in chess too, of course, but in Go their value is decided only based on how they are used. The sophistication is about the same, but the rules are simpler.
Actually, that's the draw of Go over Chess for me. The different powers in chess seems arbitrary. We can easily imagine aliens coming up with Go by convergent evolution, but not Chess. Too many free parameters.
Yes, the fascination lies in the strategies that emerge from the simple base.
It's worth mentioning that Lee Sedol mentioned in an interview that even if he loses a single game against AlphaGo, he will have lost the match. He was expecting to win all 5 games.
As a ~1 dan amateur, whether the game was "really, really close" was not clear to me. For one of my games, yeah it was close, but professional play is on such another level I'm not sure how close this game should be considered.
I watched two 9d pro commentaries, Redmond's and Kim Myungwan's. Redmond was obviously being charitable in saying the game was close near the end. Myungwan said the victory was apparent several moves before the resignation, and Myungwan also said AlphaGo was clearly stronger than himself.
Either way, even if this game should be considered close, it's still not clear if AlphaGo was holding back in order to hold a secure win. It's possible it can play at a higher level, but it wasn't needed. We can't really know AlphaGo's strength until (if) it is beaten. The following matches will be very interesting.
I'm truly amazed also, I'm not surprised or shocked. Once I knew that the previous master was beaten, I knew it's just a matter of time to see the #1 player topped.
What would be shocking is to find out that a famous writer, musician or scientist is in fact, just an alias for an advanced AI system :) It needs a little trick, because people should be tricked into believing that there's a real person behind the name.
What this actually means is that "the approach" AlphaGo team developed to "computationally" play Go, which is an computationally intractable problem, will be very useful in other computationally intractable problems. The media is going to get crazy without understanding what actually happened.
If you are going very hysteric over this and thinking that robots are going to take over then please try this:-
Before the start of the game add/remove/update any rules of the game and tell both the players - the human and computer - at the start of the game about new rules and lets see who wins.
This not only shows the insane advances in computer AI, but an incredible advancement between the Fan Hui games and this one. Im still going through the kifu to get a sense of how could it have improved so much in only 6 months.
I feel like it started being more aggressive, playing more fighting moves....whereas in the last match it was playing mostly a defensive game (I'm not an expert by any stretch of the imagination, though).
I want to scratch my itch and play some go. I suck, and playing against other players online I get destroyed so quickly I feel like I'm ruining their fun. Where can I find a fun bot with variable difficulty?
Extremely interesting news and kind of sad as a human being :)
I don't really know that much about AI, but hopefully some experts can tell me - how different are the networks that play go vs chess for example? Or recognise images vs play go?
What I mean is - if you train a network to play go and recognise images at the same time, will the current techniques of reinforcement learning/deep learning work or are the techniques not sufficient at the moment?
If that works, then it really does seem like a big step towards AGI.
This is basically a combination. A "traditional" chess program would use a tree search, but trees get quickly ot of hand since they grow exponentially. The trick is to prune them, and they trained a network to do that. It selects just the moves that look good to it. (It has some level of randomness to it, too) After reaching deep enough in the search tree, they use another network to evaluate who's winning. Usually this is hard to do in Go, and that's why the second network is quite novel and helpful.
So, they use a combination of techniques. And they're doing well at it.
right, yes, but my question was meant to be a bit more general - this and various other results have shown that it is possible to train a deep net to do a specific task very successfully - my question was if it's possible to train it to do two or more tasks as successfully or will the network then have to be exponentially larger. I suppose there is no known way to "combine" trained networks together.
The standard is to have each neural net be trained just for one task, as you say; there may be research into multi-skill neural nets but I have yet to see any. AlphaGo in particular is extremely specialized to Go, even in terms of how the algorithm is implemented.
I had a feeling that AlphaGo would beat Lee Sedol yesterday after watching Fan Hui's interview [1].
According to Hui's recall, the defeat all came down to these things: the state of the mind, confidence and human error. The gaming psychology is a big part of the game, without the feelings of fear of being defeated and almost never making mistakes like humans do, machine intelligence beating human at the highest level of competitive sports/games is inevitable. However, to truly master to game of Go, which in ancient Chinese society, it's more of an philosophy or art form than a competitive sport, there is still a long way to go.
There were a ton of details Hui cannot speak of due to the non-disclosure agreement he signed with DeepMind, but those were the gist of the interview.
In the end, AlphaGo match is 'a win for humanity', as Eric Schmidt put it. [2]
To my untrained eye, AlphaGo was already way ahead by move 29 in the match tonight with black having a weak group in the upper side, while black wasted a lot of moves on the right side as white kept pushing (Q13, Q12), which white erased later because those pushes were 4th line for black and the area was too big too control. Black never had a chance to recover this bad fight. After those reductions and invasion on right side white came back to the 3-3 at C17 which feels like solidified the win.
Some people are asking what was the losing move for Lee Sedol? I wanted to joke and say "the first one.." but maybe R8 was too conservative being away from the urgent upper side where white started all the damage.
The way AlphaGo plays is more general purpose than other game playing systems. It doesn't have any heuristics, rules, or game rule books programmed into it, it learned to play Go like you would. The same technique could be applied to other areas, the same way DeepMind originally got super-human level Atari 2600 game performance purely by having it watch pixels.
What I mean is that it doesn't have particular heuristics programmed into it by observing chess experts. It seems to me that the general technique of having policy and value networks combined with monte carlo search scales to other domains and doesn't require the amount of expertise that it took to get Deep Blue to a winning level.
Another way to look at is, is how fast they were able to make it a lot better in a few months.
Unless I'm wrong, the AlphaGo paper doesn't mention transfer learning at all. Yes, the methods are new and exciting, but I mean there are hand-crafted features in the MCTS.
Unlike with the Atari games, AlphaGo learned from a large database of human games. It'll be interesting to see how much that matters when they try it again without it.
I went looking for that xkcd to post an "obligatory xkcd needs updating" comment, but you beat me to it!
What surprises me about it is that connect four was only solved in 1995; that seems relatively late for a 6x7 grid with only 7 possible moves per turn.
No surprise at all, human brain is an organ with limited neurons, and computer doubles its performance very 18 months. In fact not just the chess, I would say that AI will beat human all around at unlimited ratio in the future, when they learned how to improve themselves especially.
I was just thinking, does AlphaGo's game strategy also emulate some sort of psychological strategies used by real human, such as bullying, confusing or making fun of its opponent when it sees fit.
What do you guys think of the future progress on the game Go? Will our only chance against AI be to team up with an AI to beat the lone AI? Like in this article about centaur chess players: http://www.wired.co.uk/magazine/archive/2014/12/features/bra... (2014) It all sounds very Gundam Wing to me.
Hand-coded board position evaluation heuristics [1]
AlphaGo:
Search via simulations (Monte Carlo Tree Search) +
Learned search heuristics (policy networks) +
Learned patterns (value networks) [2]
Human strongholds seem to be our ability to learn search heuristics and complex patterns. We can perform some simulations but not nearly as extensively as what machines are capable of.
The reason Kasparov could hold himself against Deep Blue 200,000,000-per-second search performance during their first match was probably due to his much superior search heuristics to drastically focus on better paths and better evaluation of complex positions. The patterns in chess, however, may not be complex enough that better evaluation function gives very much benefits. More importantly, its branching factor after using heuristics is low enough such that massive search will yield substantial advantage.
In Go, patterns are much more complex than chess with many simultaneous battlegrounds that can potentially be connected. Go’s Branching factor is also multiple-times higher than Chess’, rendering massive search without good guidance powerless. These in turn raise the value of learned patterns. Google stated that its learned policy networks is so strong “that raw neural networks (immediately, without any tree search at all) can defeat state-of-the-art Go programs that build enormous search trees”. This is equivalent to Kasparov using learned patterns to hold himself against massive search in Deep Blue (in their first match) and a key reason Go professionals can still beat other Go programs.
AlphaGo demonstrates that combining algorithms that mimic human abilities with powerful machines can surpass expert humans in very complex tasks.
The big questions we should strive to answer before it is too late are:
1) What trump cards humans still hold against computer algorithms and massively parallel machines?
2) What to do when a few more breakthroughs have enabled machines to surpass us in all relevant tasks?
Note: It is not entirely clear from the IBM article that the search heuristics is hand-coded, but it seems likely from the prevalent AI technique at the time.
Strong AI is not necessarily a bad thing. Instead of worrying about questions 1 & 2, we could be thinking less about constraint and competition with AI and more about cooperation and goal-orientation: e.g. the work of Yudkowsky (https://intelligence.org/files/CFAI.pdf) or some of the thoughts provided by Nick Bostrom http://nickbostrom.com/. Goal-orientation is preferable to capability constraint because the potential benefits are far larger.
Tl;dr: I, for one, welcome our robot overlords (so long as they don't behave like our robot overlords).
I agree that superintelligence could bring enormous benefits to humanity but the risks are very high as well. They are in fact existential risks, as detailed in the book Superintelligence by Bostrom.
That is why we need to invest much more research efforts on Friendly AI and trustworthy intelligent systems. People should consider contribute to MIRI (https://intelligence.org/) where Yudkowsky, who helped pioneer this line of research, works as a senior fellow.
AI is good for rules based systems, but most of the worlds problems that need to be solved don't have rules in the same way a board game does.
Sure it's cool that a computer beat a human at a board game, but thats like celebrating a penguin being better at fishing than a person with bare hand
It's almost kind of bad timing in the U.S., what with one of the most insane primary seasons in our history -- this will probably not make the news at all let alone the front page like Kasparov's and Magnus's games did.
Learning from experience goes both to the program and to the champion. Does this mean if the champion keeps playing with the machine several times, he has a chance of winning?
It'll be interesting to see what new things we learn about Go itself from DeepMind. The game is very deep, and apparently we haven't found the bottom yet!
I think it will be very interesting if Lee Sedol can win one. Humans have different blueprints and environments. Who is to say a human can't become better?
AlphaGo can be beaten. It uses reinforcement learning so it will perform the set of moves that in the past led to its win. So predictable. Sedol just needs to take control and make it play in a predictable fashion. Also, perhaps play obscure moves that AlphaGo wouldn't have trained on. Perhaps next year's Go winner will have a PhD in computer science.
Will humans be able to keep up with the depth of analysis these AIs will have, or will it become a problem for the AI to dumb down its thinking in order for us to grasp it?
More generally, scientists using AI for research will probably have to do research on the research, to understand what the AI discoveries mean. Maybe they mean something we can't grasp at all, in which case they go completely over our heads, like ants trying to learn about the finer points of financial markets. We will probably have to learn new concepts and even new languages designed by the AI to convey the meaning.
I wouldn't say "dumb down" but it definitely needs to explain why it took some lines of reasoning. With deep learning, you need to rebuild the whole system with different test-cases to change a minor behavior.. but imagine if we could just say "Why did you do that? XYZ. And adjust it: "Oh, gotcha. You can't because of ABC", and then the AI has that problem solved. I guess that would be the next step in AI. I think it's called symbolic reasoning.
i would like to see the same match, but switched placed. alphago plays itself, this time as black, to kind of see the choices it would make, and if they would align with lee's.
Worrying about the effect of strong AI on sexual relationships is like worrying about the effect on US-Chinese trade patterns if the Moon crashes into the Earth.
Who says? I mean, computers can be used for multiple purposes, and although some applications of AI seem more "noble" or "intellectual" than others, the pursuit of knowledge and sexual relationships are both sense pleasures that we indulge in to make ourselves feel good. On a very large scale, one is hardly more noble than the other.
Maybe someone can hack a dating/popular fetish forum or one of the many IM services used heavily for that sort of thing and we can get a dataset to teach computers to sext!
The thing that was supposed to take at least 10 years happened. Only last month people were still saying that no way AlphaGo will beat the champion and that it will be crushed. Today everybody will have seen it coming and say that it was normal.
Yet people will still tell that worrying about AI taking over is like worrying about overpopulation on Mars, and that this is a problem at least 50 years out.
Highly optimised single-function algorithms like this are impressive stuff and can lead to useful tools, but that's it. This gets us no closer to strong AI than a tic tac toe program. Until we have systems that can tackle a wide range of fundamentally different problems and independently adapt strategies for dealing with one class of problems to deal with other classes of problems, systems like Alphago will remain one trick wonders with little relevance to 'true' AI.
Edit: I do understand that the techniques used to implement Alphago can be used to implement other single-function solvers. That doesn't make it a general purpose strong AI.
Welcome to the AI effect! Every time AI makes an accomplishment, it is disregarded. The goalposts are perpetually moved. "AI is whatever computers can't do yet."
People said for years that Go would never be beaten in our lifetime. They said this because Go has a massive search space. It can't be beaten by brute force search. It requires intelligence, the ability to learn and recognize patterns.
And it requires doing that at the level of a human. A brute force algorithm can beat humans by doing a stupid thing far faster than a human can. But a pattern recognition based system has to beat us by playing the same way we do. If humans can learn to recognize a specific board pattern, it also has to be able to learn that pattern. If humans can learn a certain strategy, it also has to be able to learn that strategy. All on it's own, through pattern recognition.
And this leads to a far more general algorithm. The same basic algorithm that can play Go, can also do machine vision, it can compose music, it can translate languages, or it could drive cars. Unlike the brute force method that only works one one specific task, the general method is, well, general. We are building artificial brains that are already learning to do complex tasks faster and better than humans. If that's not progress towards AGI, I don't know what is.
The "moving goalposts" argument is one that really needs to die. It's a classic empty statement. Just because other people made <argument> in the past does not mean it's wrong. It proves nothing. People also predicted AGI many times over-optimistically; probably just as often as people have moved goalposts.
I don't know what you are trying to say. I'm making an observation that whenever AI beats a milestone, there are a bunch of pessimists that come out and say "but obviously X was beatable by stupid algorithms. I will beleive AI is making progress when it beats Y!"
Those arguments absolutely are wrong. For one thing it's classic hindsight bias. When you make a wrong prediction, you should update your model, not come up with justifications why your model doesn't need to change.
But second, it's another bias, where nothing looks like AI, or AI progress. People assume that intelligence should be complicated, that simple algorithms can't have intelligent behavior. That human intelligence has some kind of mystical attribute that can't be replicated in a computer.
I said exactly what I said. Calling out "moving the goalposts" does not refute the assertion that this does not get us nontrivially closer to AGI.
Whenever AI beats a milestone, there are a bunch of over-optimists that come out and make predictions about AGI. They have been wrong over and over again over the course of half a century. It's classic hindsight bias.
Yes it does! If you keep changing what you consider "AI", every time it makes progress, then it looks like we are never getting closer to AI. When in fact it is just classic moving goalposts.
And the optimists are being proven right. AGI is almost here.
That's because it hasn't been beaten yet! As soon as a chatbot beats a turing test, there will be a lot of AI deniers come out and say that the Turing test doesn't measure 'real' intelligence, or isn't a valid test for <reasons>.
I know this is true, because there are already a lot of people that think the Turing test isn't valid. They believe it could be beaten by a stupid chatbot, or deception on the part of AI. Just search for past discussions on HN of the Turing test, it comes up a lot.
There is no universally accepted benchmark of AI. Let alone a benchmark for AI progress, which is what Go is.
No one claimed that Go would require a human level AI to beat. But I am claiming that beating it represents progress towards that goal. Whereas passing the Turing test won't happen until the very end. Beating games like Go are little milestones along the journey.
Viewed that way, I'll accept that beating Go represent progress. That's not the same as saying that it represents imminent evidence that singularity style strong AI is almost upon us, as suggested in the post I was replying to. In the long term it might turn out to represent very minimal progress towards that goal.
Chatbots ate trivially easy to beat. Just try teaching it a simple game and ask it to play it with you. Basically any questions that require it to form a mental model of something and mutate or interrogate the model state.
Many of the chatbot Turing test competitions have heavily rigged rules restricting the kinds of questions you're allowed to ask in order to give the bots a chance.
In case you're not aware, AlphaGo's key component is based on the same type of Deepmind system that learned to play dozens of Atari games, to superhuman levels, by watching the pixels, without any programmatic adaptation to the particular Atari game. At least the version of AlphaGo that played in October was far less specialized for Go than Deep Blue was for chess. Demis Hassabis says that next up after this is getting Deepmind to play Go without any programmatic specialization for Go. Your reply would be appropriate if we were talking about Deep Blue, chess, and 1997.
That's incorrect. The features that AlphaGo uses are not pixel level features, but board states - and the architecture between AlphaGo and the Atari network is completely different.
It's still an incredibly achievement - but it's important to be accurate.
For AlphaGo, a "pixel" is a point on the board. It uses essentially the same convolutional neural networks (CNNs) that are in state-of-the-art machine vision systems. But yes, the overall architecture is rather different from the Atari system, due to the integration of that CNN with Monte Carlo Tree Search.
Sorry, you're off base a bit. The Atari system did use a Deep Neural Network / Reinforcement algorithm, but as the original poster was trying to point out, the rules of Go were very much hard coded into AlphaGo. From what this [1] says, multiple DNNs are learning how to traverse Monte Carlo trees of Go games. The reinforcement piece comes in choosing which of the Go players is playing the best games.
While the higher portions do share some similarities with the Atari system, at a basic level this is a machine that was designed and trained to play Go. AlphaGO is 'essentially the same' as the Atari system in the same way that all Neural Networks are 'essentially the same.'
Is this an extremely impressive accomplishment? Yes. However, doesn't seem to qualify as anything close to generalizable.
I didn't say AlphaGo is essentially the same as Deep Q Networks. I said the convolutional neural network part of it is essentially the same. We agree that the integration of that CNN into the rest of the system is very different.
It's best to say that alphago uses neural networks, which are extremely general. The same way planes and cars both use internal combustion engines. ICEs are extremely general. They produce mechanical energy from gas, and are totally uncaring whether you put them into a plane or a car. The body of the plane is necessary, but isn't really the interesting part.
Likewise NNs are uncaring what application you put them into. Give them a different input and a different goal, and they will learn to do that instead. Alphago gave it's NN's control over a monte carlo search tree, and that turned out to be enough to beat Go. They could plug the same AI into a car and it would learn to control that instead.
Note that even without the monte carlo search system, it was able to beat most amateurs, and predict the moves experts would make most of the time.
I'm not sure that's correct. MCTS has well known weaknesses, and isn't even a predictive algorithm. MCTS on it's own couldn't get anywhere near beating the top Go champion, that requires deepminds neural networks.
>> In case you're not aware, AlphaGo's key component is based on the same type of Deepmind system that learned to play dozens of Atari games, to superhuman levels, by watching the pixels, without any programmatic adaptation to the particular Atari game.
The Atari-playing AI watched the pixels indeed, but it was also given a set of actions to choose from and more importantly, a reward representing the change in the game score.
That means it wasn't able to learn the significance of the score on its own, or to generalise from the significance of the changing score in one game, to another.
It also played Atari games, that _have_ scores, so it would have been completely useless in situations where there is no score, or a clear win/loss situation.
AlphaGo is also similarly specialised to play Go. As is machine learning in general: someone has to tell the algorithm what it needs to learn, either through data engineering, or reward functions etc. A general AI would learn what is important on its own, like humans do, so machine learning has not yet shown that it can develop into AGI.
I think you are confusing utility functions with intelligence. All AIs need utility functions. An AI without a utility function would just do nothing. It would have no reason to beat Atari games, because it wouldn't get any reward for doing so.
Even humans have utility functions. For example, we get rewards for having sex, or eating food, or just making social relationships with other humans. Or we have negative reinforcement from pain, and getting hurt, or getting rejected socially.
You can come up with more complicated utility functions. Like instead of beating the game, it's goal could be to explore as much of the game as possible. To discover novel things in the game. Kind of like a sense of boredom or novelty that humans have. But in the end it's still just a utility function, it doesn't change how the algorithm itself works to achieve it. AGI is entirely agnostic to the utility function.
>> I think you are confusing utility functions with intelligence.
No, what I'm really saying is that you can't have an autonomous agent that needs to be told what to do all the time. In machine learning, we train algorithms by giving them examples of what we want them to learn, so basically we tell them what to learn. And if we want them to learn something new, we have to train them again, on new data.
Well, that's not conducive to autonomous or "general" intelligence. There may be any number of tasks that your "general" AI will need to perform competently at. What's it gonna do? Come back to you and cry every time it fails at something? So then you have a perpetual child AI that will never stand on its own two feet as an adult, because there's always something new for it to learn. Happy little AI, for sure, but not very useful and not very "general". Except for a general nuisance, maybe.
Edit: I'm saying that machine learning can't possibly lead to general AI, because it's crap at learning useful things on its own.
Machine learning doesn't "need to be told what to do all the time". No one told alphaGo what strategies were the best. It figured that out on it's own, by playing against itself.
There is also unsupervised and semi-supervised learning, which can take advantage of unlabelled data. Even supervised learning can work really well on weakly labelled data. E.g. taking pictures from the internet and using the words that occur next to them as labels. As opposed to hiring a person to manually label all of them.
I don't know what situation you are imagining that would make the AI "come back and cry". You will need to give an example.
>> Machine learning doesn't "need to be told what to do all the time". No one told
alphaGo what strategies were the best.
Of course they did. They trained it with examples of Go games and they also programmed it with a reward function that led it to select the winning games. Otherwise, it wouldn't have learned anything useful.
>> There is also unsupervised and semi-supervised learning, which can take
advantage of unlabelled data.
Sure, but unsupervised learning is useless for learning specific behaviours. You use it for
feature discovery and data exploration. As to semi-supervised learning, it's
"semi" supervised: it learns its own features, then you train it with labels so
that it learns a mapping from those features it discovered to the classes you
want it to output.
>> I don't know what situation you are imagining that would make the AI "come back and cry"
>Of course they did. They trained it with examples of Go games and they also programmed it with a reward function that led it to select the winning games. Otherwise, it wouldn't have learned anything useful.
Yes, but it doesn't need to be trained with examples of Go games. It helps a lot, but it isn't 100% necessary. It can learn to play entirely through self play. The atari games were entirely self play.
As for having a reward function for winning games, of course that is necessary. Without a reward function, any AI would cease to function. That's true even of humans. All agents need reward functions. See my original comment.
>That was an instance of humour
Yes I know what humour is lel. I asked you for a specific example where you think this would matter. Where your kind of AI would do better than a reinforcement learning AI.
That's reinforcement learning and it's even more "telling the computer what to do" than teaching it with examples.
Because you're actually telling it what to do to get a reward.
>> Without a reward function, any AI would cease to function.
I can't understand this comment, which you made before. Not all AI has a reward function. Specific algorithms do. "All" AI? Do you mean all game-playing AI? Even that's stretching it, I don't remember minimax being described in terms of rewards say, and I certainly haven't heard any of about a dozen classifiers I've studied and a bunch of other systems of all sorts (not just machine learning) being described in terms of rewards either.
Unless you mean "reward function" as the flip side of a cost function? I suppose you could argue that- but could you please clarify?
>> your kind of AI
Here, there's clearly some misunderstanding because even if I have a "my kind" of AI, I didn't say anything like that.
I'm sorry if I didn't make that clear. I'm not trying to push some specific kind of AI, though of course I have my preferences. I'm saying that machine learning can't lead to AGI, because of reasons I detailed above.
>That's reinforcement learning and it's even more "telling the computer what to do" than teaching it with examples.
No one tells the computer what to do. They just let it do it's thing, and give it a reward when it succeeds.
>Not all AI has a reward function. Specific algorithms do. "All" AI?
Fine, all general AI. Like game playing etc. Minimax isn't general, and it does require a precise "value function" to tell it how valuable each state is. Classification also isn't general, but it also requires precise loss function.
Sure they do. Say you have a machine learning algorithm, that can learn a task
from examples, and let's notate it like so:
y = f(x)
Where y is the trained system, f the learning function and x the training
examples.
The "x", the training examples, is what tells the computer what to learn,
therefore, what to do once it's trained. If you change the x, the learner can do
a different y. Therefore, you're telling the computer what to do.
In fact, once you train a computer for a different y, it may or may not be
really good at it, but it certainly can't do the old y anymore. Which is what I
mean by "machine learning can't lead to AGI". Because machine learning
algorithms are really bad at generalising from one domain to another, and the ability to do so
is necessary for general intelligence.
Edit: note that the above has nothing to do with supervised vs unsupervised etc. The point is that you train the algorithm on examples, and that necessarily removes any possibility of autonomy.
>> Fine, all general AI. Like game playing etc.
I'm still not clear what you're saying; game-playing AI is not an instance of
general AI. Do you mean "general game-playing AI"? That too doesn't always
necessarily have a reward function. If I remember correctly for instance, Deep
Blue did not use reinforcement learning and Watson certainly does not (I got access to the
Watson papers, so I could double-check if you doubt this).
Btw, every game-playing AI requires a precise evaluation function. The
difference with machine-learned game-playing AI is that this evaluation function
is sometimes learned by the learner, rather than hard-coded by the programmer.
The thing about neural networks is they can generalize from one domain to another. We don' have a million different algorithms, one for recognizing cars, and another for recognizing dogs, etc. They learn features that both have in common.
>The "x", the training examples, is what tells the computer what to learn, therefore, what to do once it's trained. If you change the x, the learner can do a different y. Therefore, you're telling the computer what to do.
But with RL, a computer can discover it's own training examples from experience. They don't need to be given to it.
>I'm still not clear what you're saying; game-playing AI is not an instance of general AI.
But it is! The distinction between the real world and a game is arbitrary. If an algorithm can learn to play a random video game, you can just as easily plug it into a robot and let it play "real life". The world is more complicated, of course, but not qualitatively different.
1) this isn't a single function algorithm
2) the human mind is FULL of ugly, highly optimized hacks that accomplish one thing well enough for us to survive. Don't assume that human intelligence is this magical general intelligence, rather than a collection of single function algorithms.
Sort-of repeating a comment I made last time AlphaGo came up:
As far as I know there is nothing particularly novel about AlphaGo, in the sense that if we stuck an AI researcher from ten years ago in a time machine to today, the researcher would not be astonished by the brilliant new techniques and ideas behind AlphaGo; rather, the time-traveling researcher would probably categorize AlphaGo as the result of ten years' incremental refinement of already-known techniques, and of ten years' worth of hardware development coupled with a company able to devote the resources to building it.
So if what we had ten years ago wasn't generally considered "true AI", what about AlphaGo causes it to deserve that title, given that it really seems to be just "the same as we already had, refined a bit and running on better hardware"?
It's easy to say that, in the same way that people now wouldn't be surprised if we could factor large numbers in linear time if we had a functional quantum computer!!
10 years ago no one believed it was possible to train deep nets[1].
It wasn't until the current "revolution" that people learned how important parameter initialization was. Sure, it's not a new algorithm, but it made the problem tractable.
So far as algorithmic innovations go, there's always ReLU (2011) and leaky ReLU (2014). The one-weird-trick paper was pretty important too.
[1] Training deep multi-layered neural networks is known to be hard. The standard learning strategy—
consisting of randomly initializing the weights of the network and applying gradient descent using
backpropagation—is known empirically to find poor solutions for networks with 3 or more hidden
layers. As this is a negative result, it has not been much reported in the machine learning literature.
For that reason, artificial neural networks have been limited to one or two hidden layers
It's only difficult because no one threw money at it. It's like saying going to Mars is difficult. It is - but most of the technology is there already, just need money to improve what was used to go to the moon.
If you asked people 10 years ago before the moon landing if it was possible, I too would agree it's impossible. But after that breakthrough it opened up the realm is possibilities.
I see AlphaGo more of an incremental improvement than a breakthrough.
Agreed. People don't realize that all of the huge algorithmic innovations (LSTMs, Convolutional neural networks, backpropagation) were invented in past neural net booms. I can't think of any novel algorithms of the same impact and ubiquity (e.g. universally considered to be huge algorithmic leaps) that have been invented in this current boom. The current boom started due to GPUs.
Something being invented previously doesn't mean that it existed as a matter of engineering practicality; improved performance is some but not all of that. Just describing something in a paper isn't enough to make it have impact, many things described in papers simply don't work as described.
A decade ago I was trying and failing to build multi-layer networks with back-propagation-- it doesn't work so well. More modern, refined, training techniques seem to work much better... and today tools for them are ubiquitous and are known to work (especially with extra CPU thrown at them :) ).
The point is that no one could train deep nets 10 years ago. Not just because of computing power, but because of bad initializations, and bad transfer functions, and bad regularization techniques, etc.
These things might seem like "small iterative refinements", but they add up to 100x improvement. Even when you don't consider hardware. And you should consider hardware too, it's also a factor in the advancement of AI.
Also reading through old research, there is a lot of silly ideas along with the good ones. It's only in retrospect that we know this specific set of techniques work, and the rest are garbage. At the time it was far from certain what the future of NNs would look like. To say it was predictable is hindsight bias.
Reconnecting to my original point way up-thread, my point is these "innovations" have not substantially expanded the types of models we are capable of expressing (they have certainly expanded the size of the types of models we're able to train), not nearly to the same degree as backprop/convnets/LSTMs did way back decades ago (this is important because AGI will require several expansions in the types of models we are capable of implementing).
Right, LSTM was invented 20 years ago. 20 years from now, the great new thing will be something that has been published today. It takes time for new innovations to gain popularity and find their uses. That doesn't mean innovations are not being made!
> As far as I know there is nothing particularly novel about AlphaGo,
By that standard there's nothing particularly novel about anything. Everything we have today is just a slight improvement of what we already had yesterday.
World experts in go and ML as recently as last year thought it would be many more years before this day happened. Who are you to trivialize this historic moment?
Some experts in Go less than 10 years ago believed it would be accomplished within 10 years. Also, you didn't actually refute his argument. Can you point to an algorithm that is not an incremental improvement over algorithms that existed 10 years ago? MCTS and reinforcement learning with function approximators definitely existed 20 years ago.
No, that's what they're saying. Take any invention and you can break it down into just a slight improvement of the sub-inventions it consists of.
A light bulb is just a metal wire encased in a non-flammable gas and you run electricity through it. It was long known that things get hot when you run electricity through them, and that hot things burst into fire, and that you can prevent fire by removing oxygen, and that glass is transparent. It's not a big deal to combine these components. A lot of people still celebrate it as a great invention, and in my opinion it is! Think about how inconvenient gas lighting is and how much better electrical light is.
Same thing with AlphaGo. Sure, if you break it down to its subcomponents it's just clever application of previously known techniques, like any other invention. But it's the result that makes it cool, not how they arrived at it!
All algorithms are incremental improvements of existing techniques. This isn't a card you can use to diminish all progress as "just a minor improvement what's the fuss".
No, not all inventions are incremental improvements of existing techniques. Backpropagation and convolutional nets, for example. Now, you might counter with the fact that it's just the chain rule (and convolution existed before that), but the point is it that algorithm had never been used in machine learning before.
People have used neural nets as function approximators for reinforcement learning with MCTS for game playing well before AlphaGo (!!).
Your lightbulb example actually supports my point. The lightbulb was the product of more than a half-century of work by hundreds of engineers/scientists. I have no problem with pointing to 70 years of work as a breakthrough invention.
I think the thing that would surprise a researcher from ten years ago is mainly the use of graphics cards for general compute. The shader units of 2005 would only be starting to get to a degree of flexibility and power where you could think to use them for gpgpu tasks.
I got my first consumer gpu in 1997 and was thinking about how to do nongraphical tasks on it almost immediately. I didn't come up with anything practically useful back then and they were much more limited but I don't think someone from 2006 would find it surprising to hear that this was a thing.
I don't know... CUDA was released almost 9 years ago. So I don't think it's a stretch to suggest that cutting edge researchers from 10 years ago would have been thinking about using GPU's that way.
Human mind... pshaw. You say this "human" thing is special? I don't see it: In my day we also had protons and electrons... all you're showing me is another mishmash of hadroic matter and leptons. So you've refined the arrangement here and there, okay, but I don't see any fundamental breakthrough only incremental refinement.
The effectiveness? Ten years ago researchers thought humanlike intelligence must necessarily involve something more than simple techniques. Today that position becomes a lot harder to defend.
You are not a general purpose strong AI either. Your mind could easily consist of a whole bunch of single-function solvers, combined into networked components.
Regarding your edit, I'd wager that it won't stay true for long. Eventually the single-function problem of orchestrating and directing a bunch of sub-solvers in a similar manner to the human brain will become feasible. At that point true general purpose AI will exist, for all intents and purposes.
And when that happens I guarantee someone will be on HN saying it is "trivial" and "not a real advancement" and "we already basically knew how to do this". Because that's what people say every time something interesting happens in AI, without fail.
I don't think anyone's claiming that AlphaGo is an AGI in and of itself, just that it's a significant step towards one. There's still a lot to go before we can toss a standardized piece of hardware+code into an arbitrary situation and have it 'just figure it out'.
It's only been the first round and I'm not throwing in the towel yet. Unlike AlphaGo, Lee Sedol has an opportunity to learn from their opponents since AlphaGo takes about 30 days of wall clock time to train the networks. There will be 5 games during the next week.
Despite my optimism, the writing is on the wall. AlphaGo and algorithms like it will only improve as you throw more CPU time at them. I actually want Lee Sedol to win, not because it would uphold some kind of human supremacy but because I want to see the AI guys put some more effort (and CPU time) into it. It would be a real shame if they'd win on their first attempt.
DeepMind is an algorithm which clearly improves a lot on traditional tree search. But how will a better tree search algorithm lead to AI taking over? Why does winning at Go mean AI is closer to taking over the world than when it won at Chess?
It's not an improved tree search. Deepmind was almost pro level purely using the deep learning network before doing any Monte Carlo search.
One way of looking at the significance of this is that it might tell us that relatively simple machine learning algorithms can capture key aspects of the versatile human cortical capacity to learn things like Go using sheer pattern recognition. (It's amazing that human visual cortex can do that.) If the human brain were more mystical in its power, then human-level ability to recognize Go patterns wouldn't have been penetrable at all to a comparatively simple neural algorithm like deep learning.
From another standpoint, this could show that we're reaching the point where, when an AI algorithm starts to reach interesting levels of performance, a much-encouraged Google dumps 100,000 tons of GPU time and 5 months of a few dozen researchers' time to improve the algorithm right past the human performance level. In N years from now when it's a more interesting AI system doing more interesting cognition, we could see a more interesting result materialize when a big organization, encouraged by some key milestone, invests 5 months of time and massively more computing power to further improve an AI system.
Monte Carlo Tree Search was necessary and itself a massive improvement over minimax but not sufficient for creating a Go program to challenge professional players. The true innovation here is the neural networks. Without those networks to guide it AlphaGo plays far worse than existing programs.
The fact that those networks are sufficient is pretty incredible. We already knew that by inventing them we had created a very pure form of pattern recognition, but it's surprising that the pattern recognition coupled with some tree search seems to be all you need to play Go as well as humans.
It's not impressive to you that we've now reproduced a piece of human intelligence, "intuition", which was previously considered out of reach?
> but it's surprising that the pattern recognition coupled with some tree search seems to be all you need to play Go as well as humans.
Is it really all we need? Or it is more that they threw a lot of hardware to it? What if if a part of its efficiency is because they threw a lot of GPUs with a huge network, rather than having a NN efficient by itself?
We see that: "AlphaGos Elo when it beat Fan Hui was 3140 using 1202 CPUs and 176 GPUs. Lee Sedol has an equivalent Elo to 3515 on the same scale (Elos on different scales aren't directly comparable). For each doubling of computer resources AlphaGo gains about 60 points of Elo."
What does a lot of hardware means? The human brain has about 100B neurons with about 100+ dendrites per neuron, while AlphaGo has about 1K CPUs with about 2B transistors per CPU.
I am wondering how much the amount of hardware they used had an effect on the bottom line, compared to the wisdom of their algorithm. Everybody knows it's a great step in AI. But how much? How much their algorithm is smart? Or simply put did they overfit by throwing a lot of layers and GPUs to the task? Or the algorithm is truly smart? What is the ratio of that.
It is the same question for the data they used. Facebook, Google and others seem to agree that, at the end, the quantity and quality of data are more important than the algorithm itself. So how much is it at play here? Knowing that will be able to show us why it is performing well and how much we can appreciate their work.
Basically, the ("lots of hardware") distributed implementation gets ~3100 points in the Elo rating against ~2900. ~2900 is still sufficient to win against Fan Hui. So I would say, that yes, this algorithm has most of the merit here.
It's totally impressive! I'm excited for the future of DeepMind and to see what other kinds of things we can build from neural networks. I'm just saying that we have to be careful with what kind of intelligence we ascribe to an algorithm like this. An AI is not going to take over the world by impressing us with its game-playing skills.
I'm not going to fear an AI whose idea of "the world" is a computer game, an AI that isn't even aware of the existence of the real world, and isn't even aware of the existence of the set of real world actions.
I think, almost by definition, you won't be afraid of anything until it's already coming for you. By that time it will already have the capability to decide your future.
I don't think it's accurate to call AlphaGo 'improved tree search' the way that Deep Blue was improved tree search. You could with equal justice call it an improved neural net.
The correct characterization is that it's a hybrid of deep learning and tree search. It's also a hybrid in the feature representation for the algorithm. There are raw features (board state), but there are also handcrafted features for the tree search.
I'd say both characterizations are accurate. Neither the tree search nor the neural net could have accomplished this on their own. But the essential interface to the algorithm is the tree search: it's picking the best move from a set of legal moves determined by formal game rules. The real world doesn't follow formal game rules. I find it difficult to see the progression from this victory to some kind of real-world AI takeover.
Sure, but when you say "tree search" people think of the traditional kind of expert system-based tree search. Traditional tree search methods prune trees by approximating subtrees according to some very specific rules decided on by human experts. This means in a tree search system, the computer cannot actually evaluate a position any better than the humans that designed it. The way it performs better is by running very many of these evaluations deep down in the tree.
When you're talking about some other kind of evaluation function, such as Monte Carlo rollouts, you usually prefix that to the tree search (in the case of Monte Carlo rollouts, "Monte Carlo tree search" or MCTS) to indicate that besides the basic fundamental task common to almost all AIs (finding the optimal branches in a decision tree) it functions completely differently from the expert systems.
So is the case with this program, which (in a first pass) approximates subtrees by a trained neural net, rather than Monte Carlo rollouts or an expert system. So using terminology that suggests classical expert system tree search is bound to cause confusion (as you noticed).
Infinite state/belief/world space. Infinite action space. It's not so much that there aren't rules (there are - physics), it's that the complexity of the full set of rules is exponential or super-exponential.
And? This does not address my argument that the complexity is beyond-combinatorially explosive (infinite spaces). I'm not talking about the space of possible board states. I'm talking about merely the set of all possible actions.
EDIT: clarified my language to address below reply.
...and it's possible to train learning agents to sense and interact with a world described by high dimensional continuous vector spaces, for instance using conv nets (for sensing audio / video signals) and actor-critic to learn an continuous policy:
The fact that the (reinforcement) learning problem is hard or not is not directly related to whether the observation and action spaces are discrete or continuous.
I don't understand why would the "number of spaces" matters. What matters is can you design a learning algorithm that performs well in interesting spaces such as:
- discrete spaces such as atari games and go,
- continuous spaces such as driving a car, controlling a robot or bid on a ad exchange.
A really really large number of distinct decisions that need to be made. A car only needs to control a small set of actions (wheels, engine, a couple others I'm missing). A game player only needs to choose from a small set of actions (e.g. place piece at position X, move left/right/up/down/jump).
Well, by that logic, why can't you describe Lee Sedol as applying an "improved tree search" that happens to have really good move selection heuristics and static board evaluation function as well? After all, all good human Go players read ahead a few moves.
The issue is that we don't take the threat seriously, since we believe we have plenty of time to solve it. Some don't even believe it's a threat at all (will unplug it, right?)
This 10 years to beat go prediction shows that our time estimates are wildly ignorant.
Yet people will still tell that worrying about AI taking over is like worrying about overpopulation on Mars, and that this is a problem at least 50 years out.
As hard as writing AI for a problem space like "how to win at Go" is, it's several orders of magnitude easier than creating a general AI with the self-awareness required to see us as a threat.
There is a lot of progress being made in AI right now. Hard problems that were expected to take decades, are being beaten regularly. Who is to say how much AI could advance in the next 20-30 years? Do you really believe there's less than a 50% chance strong AI won't be invented in your lifetime?
There is a lot of progress being made in AI right now. Hard problems that were expected to take decades, are being beaten regularly. Who is to say how much AI could advance in the next 20-30 years?
"We've beaten some hard problems more quickly than expected therefore we'll likely beat other hard problems more quickly than expected" is logical induction. It's equivalent to "I just flipped a coin and got heads. I'll probably get heads again on the next flip." Don't do that. :)
Do you really believe there's less than a 50% chance strong AI won't be invented in your lifetime?
I don't know. I don't really see the value in speculating.
>I just flipped a coin and got heads. I'll probably get heads again on the next flip
Which is corrrect, if you don't know the true probability of flipping heads. You might find, for example, that it's a trick coin with two heads and no tails.
You absolutely can predict future progress from past progress. E.g. Moore's law held true for decades after the observation was made. If you see a technology advancing rapidly, then there is no reason to say it will stop in the near future!
>I don't really see the value in speculating.
Because everything depends on this prediction. The invention of AI will be the most significant event in the history of humanity. It will totally change the world. Or likely, destroy it. Being prepared for it is absolutely necessary.
Why would you have a strong prior belief about the invention of AGI? Now you are claiming to have far more certainty than I am.
>By your logic, you can predict the failure of AGI predictions by past failures of (every) AGI prediction.
This logic is extremely flawed. First not every prediction was wrong. Many people predicted it would happen in 2045, a few in 2030.
Second there's no reason past predictions represent the accuracy of future predictions about the same thing. Predictions should get more accurate over time, and early predictions are expected to be wildly wrong.
And third there's anthropic bias. If they were right, then we wouldn't be here to speculate about it. We can only ever observe negative outcomes, therefore observing a negative outcome shouldn't update your priors at all.
There is all kinds of value in speculating. We do it all the time in things like war games. 'If neighbor $x attacked us, what would happen?, would they win?, what can we do to prevent this?'.
Of course this may in your mind hold very little value now, but I promise if and when it occurs you will change your mind quickly on that topic.
Do you think it's better to propose we won't, and not start preparing for a smarter-than-human intelligence. Or to propose we might, and that we should prepare for it to happen?
On the face of it we should definitely have a strategy for dealing with strong AI, but with no knowledge of what strong AI will look like how would we prepare for it? There's ostensibly nothing we can do. Until we make more progress in the field we can't make any preparations other than wild speculation. And that is what I see no value in.
The interesting thing is that this algorithm taught itself to master the game. If you're writing a chess engine, you just "write the AI for the problem space" in a few dozen lines of code, as you put it, and let brute force do the rest. In the case of DeepMind, faced with a game where a traversal approach is numerically impossible, its programmers gave it the ability to improve by playing against itself.
That's the difference between a neural net -- which until about an hour ago was a phrase that reliably set off my snake-oil detector -- and a simple tree search. DeepMind just beat a Go master... and nobody can say exactly how it did it.
I think it's the same as what happened when the perceptron was the big thing in the 50s/60s. Many made far overreaching conclusions about how the problem of AI had been solved.
I think you misunderstood, I am referring to the fact that Marvin Minsky in 1966, asked Gerald Sussman to "spend the summer linking a camera to a computer and getting the computer to describe what it saw".
We certainly got nearly there, but it was nearly 50 years later, not 3 months.
Similarly, something that might look somewhat simple to us right now, might also be a lot more difficult.
They don't invent moves that they weren't explicitly programmed to play, though, do they? People at the top level of play have been beaten by chess programs but not surprised by them, the way the Go professionals have been in this case. DeepBlue didn't teach us anything about chess that we didn't already know.
How do you outlaw black box algorithms? What is a black box algorithm? Should we outlaw all calls to libraries we don't have the complete source code to?
I can't understand the call to regulate a technology when it is decades (much more that 10-20 years) away from possibly existing in a state that we can't even imagine. Add to that legislators with zero technical literacy. That's essentially advocating for shutting down all research into a technology that can improve millions of lives.
A black box algorithm is any algorithm that wasn't really written by a human. It isn't about having the source code, it is about utilizing the output of a neural network, which is built up by multiplying a bunch of inputs by weight values and is basically nonsense when you look at it.
Basically any algorithm where you are training it with tons of samples and then it creates a logic tree that is not written by a human is a black box algorithm.
By the time AI technology gets to the point that we realize we should regulate it we will be too late.
I for one did not say to not worry, and I bet $1500 vs. $2250 on Sedol winning the match before getting cold feet and arbing my outstanding bets down to $400 vs. $700.
Can't you just look at the creators of the program? Demis says he certainly does not worry about a "terminator" or "ex machina" style scenario and also predicted they would win: http://www.bbc.com/news/business-34266425
Beyond that, it seems reasonable to call for discussion about how AI is used [as he also does in that article].
You are not a counterexample to Teodolfo's claim, which was about people who did say not to worry.
[EDITED to add:] Oh, I see, your point is that it looks like AlphaGo is doing better than an "AI moves fast" advocate expected, rather than (per Teodolfo) no better than some "AI moves slowly" advocates expected. Fair enough.
Why does Teodolfo even need a citation for that? Are you really suggesting that there is no group of people who believe AI is not a threat to worry about, and believed that AlphaGo would win?
I'm sure there's someone on the planet. Which is a very different state of affairs from the one that would obtain if a well-known AI researcher had, say, made a $1500 public bet on AlphaGo winning, while also loudly declaring that worrying about AGI was like worrying about overpopulation on Mars, in the company of other researchers declaring similar combined expectations.
What actually happened was the reverse of that; AI moved faster than I publicly bet a large sum of money on it moving, and I was already worried before then.
I'm not aware of the reverse-reverse having happened.
If you're claiming something as a successful advance prediction to bolster belief in a general model, it's fair play to ask for a record of that advance prediction.
Go is literally infinitely more easy to solve than general intelligence. "Literally" in the sense that Go has a finite number of board states, while a general intelligence must be able to deal with an infinite amount of novel situations, presumably by generalising from previously experienced ones.
Infinity is a real problem. When you try to learn from examples, you first need to see "enough" examples of whatever you're trying to learn. If there are infinitely many such examples, no matter how clever you are in tackling your search space there will always be infinitely many examples of infinitely many situations you've never come across, and that you won't be able to learn.
The typical example of this is language. You could give a learner all phrases of a given language every produced and it would still be missing an infinite amount of necessary examples. Somehow (and it's freaky when you stop to think about it) humans get around this and we can produce and understand parts of infinity, without sweating it.
Machine learning is simply incapable of generalising like that and anyone who thinks AGI is just around the corner has just failed to consider what "general" really, really means.
Though to be fair, now that I had my little rant I have to admit that you don't need to go "general intelligence" before you can be really, really dangerous. Even if AI doesn't "take over" it can do a lot of damage, frex if we start using autonomous weapon systems or hand over critical infrastructure maintenance to limited and inflexible mechanical intelligence.
Yes, but the point is that you 're not going to brute-force this. If it's finite you can hope to approximate it. If it's not finite, you can't even approximate it.
Look- take Monte Carlo methods. You can sample a very big number of events and hope to get some useful information from that. If you sample infinity, though, what do you get? Infinity.
I was one of the people who rooted for the champion last month, and my position hasn't changed. Last night's game was very exciting, but if the pressure doesn't get to Sedol he has a chance. He made some mistakes in the game and AlphaGo played incredibly well. General opinion I've seen so far is that the lead switched hands in a few places, although I'm waiting for professional commentaries to illuminate what possibilities were there for both players - the played game is always just the tip of the iceberg
The last victory was significant, but this victory was far more significant. The professional dan scale isn't exactly linear and the ranks can't simply be compared numerically even when they are granted by the same organization - and Korea, China and Japan all have at least one organization of professional go players that each maintain their own rankings. Sedol is a current top player who has won many, _many_ titles and Fan Hui is 10 years out of regular professional play and doesn't have a title to his name. What people were saying before is still true today. All of the reporting has suffered from the usual problems of describing something specialized to the general public, and all the typical inaccuracies of such journalism (compounded by Google's PR department being the source of some of it).
Congratulations to the team at Deepmind, and I'm wishing good luck for Sedol in the remaining matches - if he wins we would certainly get to see a second series rematch some months down the line, and that would be very exciting for go fans everywhere.
Lee Sedol should have played that top left 3,3 move earlier (at least before white covered it) WTF. Humanity is not longer at the top of the intelligence pyramid...
Tonight, that happened. Google's DeepMind AlphaGo defeated the world Go champion Lee Sedol. An amazing testament to humanity's ability to continuously innovate at a continuously surprising pace. It's important to remember, this isn't really man vs machine, as we humans programmed the algorithms and built the computers they run on. It's really all just circuitous man vs man.
Excited for the next "impossible" things we'll see in our lifetimes.