Why AlphaGo Is Such a Big Deal
quantamagazine.org
quantamagazine.org
(I am not an AI researcher, but I work with AI researchers, like by putting on training programs and recruiting for them, and working out of the same office, and this is a summary of [my understanding of] their discussions about this topic.)
AGI is a Hard Problem (TM), and no one really knows how hard it is. General intelligence is made of algorithms that are somewhere on a spectrum between dizzyingly complex math that we have decades+ more work to develop, and simple components that someone in their basement could stumble upon at any moment if only we had a couple key insights. (Sorry for the gross oversimplification.)
Before AlphaGo there was a whole area of probability space that seemed plausible--a whole area of complexity that had yet to be worked out in detail. AlphaGo proved that more or less current AI tech was sufficient for that problem (current meaning one incremental step forward, as opposed to some revolutionary insight). That's why they "moved the field forward by 10 years"--by proving that the work that AI researchers basically expected to have to do over the next 10 years is not necessary.
Said another way, we're closer to the "simple components" end of the spectrum than we collectively thought. AlphaGo proved that, and that's why it's a big deal.
I could play my entire life and never achieve the level of play Lee Sedol has. AlphaGo surpassed that level in a matter of months.
As a matter of fact, many professionals that play the game for a living as their main occupation, since they're kids, will never achieve the level that Lee Sedol has.
Also from here, they can add more infrastructure and feed the bot with more training data and let it train for a longer time, and it will be distancing it more and more from human level play.
Then, this task specifically is not just any random task... it's one of the most complex games, one the oldest games, and is also professionally played and studied.
Then, AGI is not a requirement for disrupting our world. You can have ANI for one specific task that is performed by millions of humans and you have disrupted the world enough to make it a problem.
I wonder what happens once we grow an AI whose purpose is to excel at training other AI's. Will we see an exponential leap forward in the speed with which they are trained?
A recent(-ish) Computerphile video has a good overview of the AI-self-improvement problem.
https://www.youtube.com/watch?v=5qfIgCiYlfY
I recommend watching the previous video first, which introduces the problem of strong-AI rapidly finding solutions (especially with poorly-specified questions) that may not be in humanity's best interest.
https://www.youtube.com/watch?v=tcdVC4e6EV4
Before anybody jumps to overly-sensational conclusions, note that the last video in that series, Rob Miles explains how exponential self-improvement is an extreme point in the space of possible AI development. We don't know how to predict discoveries[1], so we need more research into AI, so we can hopefully make something that isn't exponentially growing beyond our understanding.
https://www.youtube.com/watch?v=IB1OvoCNnWY
[1] see James Burke's non-teleological view of change
I'm baffled at how easily people assuming a computer thinking something means it's going to happen. There are a trillion pieces that have to fall in place for that to happen accidentally, and if it doesn't happen accidentally, your problem is a human social problem, not an AI problem.
And I know what someone is going to think: "The AI might be smart enough to figure out how to make those trillion pieces fall in place." But then, who cares? So what if it figures out how to do something. It still has to be done. And we're the ones who have to do it.
For an extreme example, you could imagine an AI getting rich from the stock market (or mechanical turk, etc), then buying up ridiculous amounts of land for paperclip factories and paying workers. The people that want to feed their families or get rich from selling their factories are the ones who will enact the AI's plans. How many conscientious objectors do you expect?
Of course you might be skeptical that is even possible. So there is always slower world take over paths. It could slowly earn tons of money, hack into the world's computer systems, trick and persuade humans winning social influence, design superior macroscale robots, etc.
The only important part is that the AI be far smarter than humans. Which seems inevitable to me, since it can rewrite and improve its own code, and run on giant computers that are far faster than human brains. If it isn't smarter than us at first, it will be eventually. Unless you really believe that humans are close to optimal intelligence.
At every step of this process this machine will be under intense human scrutiny, and we'll be constantly asking it to meet our demands, and if it ever fails to do so we will replace it with one that does.
That is the environment in which such an AI would be trying to evolve. And thus it will evolve into a faithful servant, because nothing else will survive.
And even if it were secretly developing plans, we'd be able to see how wasteful those plans end up being, and we'd purge them. We kill those processes that run functions that we don't see the value in. This is state-of-the-art design. You don't get state-of-the-art by having your back turned.
Mor importantly: you're glossing over "self-improvement." How does the computer know what an "improvement" is? We tell it what an improvement is. And an improvement will be "it is better at meeting our needs," not "it is better at being secretive and conniving and getting it's own way." In fact, "getting it's own way" is very obviously a bug, and if it happened, you'd have a useless program. One that wastes precious CPU cycles on who-knows-what, and you'd prefer it spent that effort doing what you want, rather than planning for what you don't.
We're not going to invest trillions into building some super AI and completely forget about it. After we give it control of all of our natural resource harvesting and infrastructure.
No, what you're talking about is a deity. If you invent a deity, then my thoughts on the matter don't really apply, since I'm not a deity. But that's no worse than advanced aliens landing on Earth, and just about as likely to happen.
For Go, the competition is on a different level that you couldn't just build a machine to play.
In one, very tiny area, sure. But step outside the very specific task of playing winning moves in go, and Lee Sedol wins every time. AlphaGo can't explain its moves to someone learning go, let alone cognitive tasks we take for granted like moving feet in a way that produces transportation. AlphaGo can't even do things that other programs can do, like play chess.
Sure, you can "disrupt" with Monte Carlo algorithms like AlphaGo in the San Francisco startup sense of the word "disrupt", but that's also not new. AIs have been doing that for years in finance, genetics, chemistry. We've been able to write code that does one thing well for decades--what we lack is code with breadth of application, and AlphaGo doesn't even make a dent in that.
I'm pretty sure lee sedol cannot explain his own moves either. Yes, he can rationalize why that move is a good move, but he won't be able to explain the complete reasoning process that led to that move, because it relies on intuition. He cannot train a random person to play at the level of lee sedol.
If you look at the human brain, every part learns to do just one thing. Alphago is like having just the part of the brain that plays go. Moving from there to something more general is a question of assembling the parts. Building a biped robot that walks and plays go is not a hard problem.
The fundamental question is whether us humans are more than the sum of our parts. If you add task-specific AI bits together, will you at some point have something that becomes a person, or will it always be a collection of features?
I think you're wrong here. I don't see why that wouldn't be the case?
The "intuition" just means he arrives at the move quickly without consciously going through the thought process, but why wouldn't he be able to reconstruct it?
Now people say it doesn't matter. What is next?
And while those applications are narrow, they're significant progress in a short period of time.
In this game from only 4 years ago you could see one of the state of the art bots getting humilliated by an anonymous professional player: http://gosensations.com/?id=2&server_id=1&new_id=1392
In 2006 a paper was published (by Remi Coulom) showing that just playing random moves and combining those random playouts with a tree search scaled up in strength arbitrarily as you throw more computational resources at the problem.
Google made them a little less random and threw a ton of hardware and optimizations at it. (Basically 20 times as much as anyone before them, which goes a long way of explaining the performance jump)
Don't make this something it is not.
So, we do have this nice tool that sort of lets us "look" in "general" way, but it is not entirely understandable, or traceable, which is the nature of NN... It would be nice to be able to prove exactly why something happened, and to be able to have reproducible, exact training.
Anyway... I guess I don't have much of a point beyond these two vague minor thoughts, but I did want to add them in here...
1. AlphaGo doesn't just use neural networks. If it did, it would almost certainly loose 0-5. It also uses Monte-Carlo tree search, which is an algorithms that made a huge leap in the strength of Go bots. The rub is that MCTS is a flavor of "brute-force" algorithm. What does that tell you about the nature of Go?
2. None of the individual components in AlphaGo are theoretically novel. In fact, all of them are very well-known: conv. nets, MCTS, data-mining, reinforcement learning. What does that tell you about the nature of this particular game-playing AI compared to its many brethren?
(By the way, I wonder how many of the journalists praising Google for Alpha Go even heard of Rémi Coulom. Shouldn't he be at least be mentioned somewhere in all these articles?)
NNs have shown a lot of promise in the last few years. They are just starting to make their way to new applications like Go playing. So in that sense AlphaGo is a sign of things to come.
Which is interesting in its own right, since ANNs have been the subject of research for more than half a century. If anything, all their ups and downs should make people more cautious about bold predictions.
That's the thing: AlphaGo is more like a rocket than it is like us. It can play a game better than all of us but it can't do anything else.
The paper about AlphaGo is really disappointing in some ways. Even Facebook's Go/AI research paper had more novel techniques in it. But 2 dudes fiddling at Facebook aren't going to beat a dedicated team of 20+ with a PR mission to fulfill...
Think of it this way. Strong AI would lose to Weak AI at Go. So Strong AI is not in AphaGo's evolutionary path. Strong AI is the kind that authors and expresses things. Weak AIs are computational marvels.
The brilliance of Strong AI would be in its capacity to build targeted Weak AI systems. And that is how Strong AI will beat any Weak AI system.
If Strong AI is what we have, then just look at our relationship with AlphaGo. We created it, and it beat us at Go.
Also, science is unpredictable. So saying we're 10 years ahead of schedule is not a scientific statement at all. Someone said it, and it was wrong, but they weren't speaking for the thousands of scientists working on new ideas as opposed to refining old ones.
When humans build a calculator, do we say that the calculator beat humans at math, or humans beat calculators because we create them? Not really, they are just a tool. The problem with humans and calculators is the interface is rather clunky. You can't directly interface with the digital inputs of the calculator, but instead do so millions of times slower than a computer can.
With strong AI this is not apt to be the case. Yes, it will create weak 'computational' AIs to do some tasks very well, but the speed that it will be able to interface and classify results at will be much faster than we are able to obtain. Where you and your calculator are very different things, ASI and it's calculators will not be.
The new calculator will beat the old calculator. Humans don't beat calculators themselves. But only humans have the capacity to improve on calculators. And this is truly all we've been doing with science and technology ever since day one. And yes, they're all just tools. AphaGo is just a tool. It told the dude moving the pieces where to move the pieces to beat the world champion who was moving pieces without any help. AlphaGo2 will be a better tool.
> much faster than we are able to obtain
Would that be that important though? Compare IBM Watson with the Jeopardy champion, except, this time he gets to use Google. Watson has a direct line, Ken Jennings does not. So what? Calculators are the same thing. We don't benefit from a direct link, at least at that level. It gives us the answer, and we can read it. We only want the answer anyway. Having to download all the details is redundant. The mind reading interface is what is clunky, when we're already wireless. Seeing is enough.
> ASI and it's calculators will not be.
Right, so you're switching to hardware now. Artificial human enhancement is the go-to answer many will give you here, but it's a bit too sci-fi for me.
But regardless, the strong-weak divide still stands. We would create tools to solve the problem. And this is where strong AI and calculators will differ, regardless of what other similarities they may have, physical or otherwise.
P.S. Michael Nielsen must be one of the very few people who can explain any concept in almost absolute clear and simple terms.
Which strikes me as a fair point. I'm sure there are lots of positives to staying near family and friends, and if you have stronger community ties you may well be more active in that community.
Your comment is like saying that AlphaGO doesn't choose each move separately, it considers a sequence of moves. Of course it does, but it still can output each move one at a time.
Yes you can write a chatbot that chooses a character at a time, but no chatbot using a per character chunk has been considered remotely successful since before Eliza.
I agree that the branching factor is not well defined for a chatbot. Although it definitely is not 26.
But that suffices to show that a process which is choosing from a very constrained set of options is still in a different class of success than AlphaGo. The options chosen at each step are more constrained than the choice of moves in Go, so the argument "the difference between solving go and solving tech support is the number of options available at any time" is insufficient.
One might be able to define a better notion than branching factor that takes into account how many steps are needed as well as how much it branches in each step and such a thing is probably much larger for tech support than it is for go. But such an argument would be hard to state well, I think.
One more thing. You are wrong in case of tech support, i've trained a lot of networks using ML, but not only neural networks, i've used markov chains, mcts etc. What you have wrote is ONLY a speculation, nothing more.
Tech support for most of the products have finite states because they have finite use cases and finite code base. You know how paypal support looks like? In 99% of cases it's copy paste. What do you think support people know about the product ? They get couple of weeks of training and that's all they know about tech support of that product. It's only matter of time when you will get AI product tech support.
For example, My Air conditioner was not working correctly last week. These were my considerations:
1) I can investigate
2) I can call someone
3) I can investigate and try to repair
4) I can ignore it
5) I can destroy it
6) ???
Apply to college or go to trade school... Move to Silicon Valley or stay put... Decide to have children with my wife...
All of these would start off as large state spaces, but would inevitably shrink as each state is considered. At least, that is how I solve my decisions. Lots of lists that get worked down...
The real dilemma in decision making the determination of the outcome you desire, or better yet... the probability of attaining the desired outcome. If I am not mistaken, I read in _Thinking Fast and Slow_ that humans are pretty terrible at prediction, probability and remembering exact details. Furthermore, humans brains would meltdown if we sorted through 64 state spaces for every decision. We mostly live by rules of thumb and easy thinking...
I think AlphaGo could make me a better human.
If there were an AlphaHVAC, AlphaMATH, AlphaPlumbing, AlphaStucco, AlphaEMS, AlphaLogic, AlphaMorals etc., etc. we could have modal expert systems we point at whatever we need to know and do. Emergency field medicine is a lot like remodeling a bathroom with mold. Once you discover the problem, you follow algorithms to fix the issues. It was the same with my HVAC system. In emergency field medicine, they even call them algorithms.
Then we can combine the expert systems under some kind of unifying command structure... have them "talk" to each other, learn from one another.
AlphaGo has shown that complex, difficult, and downright ugly problems can be modeled and yield results better than the lifetime training of a human in the game of Go (at least for now). IMO, Deepmind will mark the transition to the age of Transhumanism.
I'm not exactly sure what you mean by this, but I'm pretty sure I don't want it to happen.
Completely general AI is a long way off, but tech support and other specialisms are feasible using expert systems, which were each limited to a single area of expertise. These were limited by their knowledge bases but they did work - and they had one advantage over deep learning - we knew how they worked and they were able to explain their reasoning - the main problem was getting them adopted and deployed.
Cannot be brute-forced? Uh, you mean like with Monte Carlo Tree Search? Which AlphaGo actually uses?
One could arguably claim that something like minmax is brute force, since you only prune subtrees that are provably sub-optimal.
But a search algorithm or heuristic that prunes over 99.99999999% (there are more 9s, but I won't bother calculating the right number) of the search space is not brute force.
I would agree that under one extremely nitpicky definition of brute force, brute force means searching every state. But chess engines are widely considered to be brute force. They don't have neural nets or fancy nonlinear function approximators for board state evaluation. But they most certainly don't search every single position. Their search depth is capped.
Nonlinear function approximations are pretty common due to combining several evaluation heuristics and indexing in to tables with weights with the output of previous heuristics.
As for neural networks - the extra nonlinear layers seem to have too much computational overhead compared to the increase in evaluation accuracy. Chess board state can be reasonably approximated with linear terms and few cherry-picked higher order terms.
Point being, it is significant that something like MCTS can be so effective at Go even without machine learning.
Whether chess engines and go engine are brute force or not just depends on how you define brute force:
* If you cut variations where you have heuristical indications they don't affect the result, is that still brute force?
* If you cut variations where you have mathematical, provable evidence they don't affect the result, is that still brute force?
And what about ourselves? Building AlphaGo is a feat of human intelligence, but how does it improve that human intelligence itself? How do we become smarter? We can build machines to solve problems that we don't understand, but they solve them in ways that we still don't understand. Except- we're not even trying anymore. We've given up. Knowledge is hard. Logic is hard. Just throw a bunch of GPUs at the problem and make it go away.
Far from this being a promising time for artificial intelligence, I fear we're about to see a great dumbing down as funding is cut to everything but neural networks research. A kind of AI summer, as it were.
Might this combined system be closer to understanding, logically, what it has learned?
Sometimes I wonder if inside of ourselves we come up with logical reasoning after intuition has pre-illuminated the path forward (based on experience). Or perhaps many different forms of thinking run in parallel, influencing each other. Each of us may have a very, very different combination of instinct, intuition, logic, etc.
That's like saying computers are not smart. It's meaningless. Computers are as smart as the algorithms they run and neural networks are as smart as the neural connections within them. Neural networks are models of computation as much as current computer architectures are.
As far as we know, neural networks indeed are at the core of human intelligence. Human brain is an extremely complicated neural network with plenty of side mechanisms, many of which we possibly do not know about yet. Nonetheless it's unlikely that the underlying building blocks are not neural networks.
What is probably several orders of magnitude more complex than uncovering the static architecture of the human brain, is understanding the way it is trained. Note that this is the case with artificial neural networks as well.
I doubt that we will ever understand human intelligence "from above". It doesn't seem implausible to me that there is some general complexity theory law which prohibits intelligence "understanding" itself.
What about collective intelligence? What could prevent many intelligent agents from collectively reverse-engineering the algorithms they are individually running? Let say they then build a simulator and can use it to predict how any possible instantiation of their intelligence would behave. Can they (collectively) "understand" it any more than that? What question could you pose to test if they really understood it "from above"?
Right.
Quick intro to neural models, for the only very slightly mathematically inclined.
Neural networks solve this equation:
Y = W ⋅ X
Where X a matrix of inputs to a function ƒ, W a matrix of its coefficients and Y a matrix of its outputs.
Once that's done once for all N instances of X in our dataset, a time period which we term an epoch, Y is used to calculate a measure of error, typically mean squared error:
MSE = 1/N ∑ (Y' - Y)²
Where Y' the true value of Y that we're trying to approximate. This is repeated until the cows come home, or until the network has converged, whichever comes home first (er, hint).
And that's neural networks in a nutshell. There's nothing much more complicated than that (er, in theory), there's no magic and certainly nothing "like the brain" in them at all. They're just optimisation over systems of functions. We learned how to solve systems of functions with matrix multiplication when we were at high school. I'm pretty sure we did - I've personally repressed the memory but I'm pretty sure I did once have it.
Why do people insist on calling them "neural"? Who the fuck knows. Way back in the 50s, the perceptron was based on a model of neural activation, where a neuron "fires" when its electrical charge crosses over a threshold. This was originally represented with a binary step function (the very one used in Perceptron classification). That was, at the time, deemed to be "a good model" of neural activation. A good model, my foot. Soon people moved on to sigmoid functions which are "a better model" of neural activation. Whatever.
I've also heard it that, say, conv nets (convolutional neural networks) are "like the brain", presumably because if you squint at the layer connection diagrams long enough, conv nets start to look a bit like idealised models of the parts of the brain that handle vision. But if you squint long enough, everything starts to look like everything else. Hell, you might suggest that neural networks are based on the effin Tree of Life from Cabala, and Geoff Hinton is Alistair Crowley reincarnated.
The whole "brain" thing is just an abstraction. You should not read too much into it. And don't listen to the people who try to convince you neural networks are magic- they're not. It's high school maths and a lot of very expensive processing power.
P.S. If my notation doesn't make sense to you, you may need to use a different font in your browser; sorry about that.
The artificial neural network model you described works more like a brain than, say, a traditional von Neumann computer. It works less like a brain than, say, HTM, which is another type of an artificial neural network. There are even more biologically plausible NN models (e.g. those used in HBP).
The bottom line is, a large number of connected neurons is at the core of human intelligence. Everything else is just details.
That's a great example of the magical thinking that prevails in discussions of neural networks today.
You only need to put your ducks in a row to figure out why it makes no sense. "The brain" you say "has lots of connections". "Therefore, if something has many connections, it's like a brain". I hope that raises a big red flag with bells on for you, 'cause it sure does for me.
Spaghetti carbonara looks a lot like a brain (it's made of fibers and it's an off-white, sticky mess). I've never known it to be intelligent, though maybe it's just too smart for me, eh?
People are not smart by that same definition. We rarely - if ever - take something from one domain (say playing chess) and then find ourselves capable of applying it to another domain (say playing 'go') without significant adaptation.
The little bit that gets recycled from one turn based game to the next hardly matters and I highly doubt there is someone out there that is a world champion or master class performer in more than one game using the same set of heuristics.
That these limited AIs are unaware of themselves and mechanical is a different thing altogether.
[0] http://blog.codinghorror.com/thanks-for-ruining-another-game...
If AlphaGo was intimidating today, having soundly beaten the best human Go player in the world, it'll be no contest after a few more years of GPUs doubling and redoubling their speeds again.
In the AlphaGo paper they said their cluster version (with the 170 GPUs Atwoods mention) were the limit of what hardware could do for their algorithms. They tried using much larger clusters, but it didn't really improve performance.
This actually fits his point that for chess, most of the performance gain over the last ten years has come from better algorithms. In particular for chess, better tuning of variables, through projects like fishtest (http://stockfishchess.org/)
It seems like many of these problems can only be solved using algorithms with require a certain amount of computing power. However once we've reached that particular amount of power, further progress really lies in the algorithms.
What is the class of problems beyond go and closed world games which this work attacks?
[1] http://lesswrong.com/lw/vq/the_weighted_majority_algorithm/
The tricky part is that using the "best (rather than better) than random guidance" in the Monte Carlo simulations makes the performance worse.
We don't understand very deeply why that is.
What is "this specific line of research" though?
Monte Carlo simulations with tree search? This is a bit tricky because simulation the playout requires a "fixed" world or something that can be simplified to it.
Deep Convolutional Neural Networks? Those are very broadly applicable, most famously in image recognition, in fact one reason why Google and Facebook were on this is because they are probably using them a ton...
If you're referring to the recent "deep learning classifies this random noise as a dog" news, keep in mind that humans are far more suited to more abstract tricks like wearing makeup than learning the perfect static to fool an image recognition algorithm. Even with computer assistance and access to AlphaGo in order to train the perfect pathological boards, the high branching factor of go makes it impossible to for a human to remember what the relevant pathological board would be halfway through the game.
(Also, keep in mind that the adversarial reinforcement learning is essentially training against as many pathological boards as possible. Image recognition isn't trained this way.)
So I don't think you're right about this. I feel like the era of "makeup" tricks is finished (though maybe there's still one or two wins left from this approach). If Lee beats AlphaGo, I think it's because their strengths are truly similar.
When I learn Go, there are all sorts of techniques such as joseki, life-death, tesuji. AlphaGo implicitly learned these techniques, since it learned from professional games, which are experts in those topics.
This is my problem with neural networks in general, since they do not discuss how go boards divide into smaller problems or heuristics for putting them back together.
to be corny, Go is really a teaching tool for how people think logically and abstractly. It's not about teaching computers.
This strategy is called "chunking", and is an adaptation humans have developed to solve complex problems. There's no reason to artificially constrain AI to use the same crutches we do.
I have never won a game of chess in my entire life. Not against any human player or any Commodore 64 chess program on the easiest setting. I don't expect I ever will. I know how the pieces move and that's about it.
Watson playing Jeopardy was different. That I could "get", and that impressed me.
I think your general point stands, AI learns slowly in terms of number of iterations (consider how many times a five year old needs to be told the pronunciation of an unusual word or what emotion a certain tone conveys vs training a neural net).
...but highly unlikely. In the best case, that works out to something like reviewing 10 new games every single day. If a game takes 1 hour to properly review, and a person needs 8 hours of sleep, that leaves just 6 hours in a day to eat, manage hygiene, exercise, be with family, travel to competitions, play yourself and do all kinds of other studies you need to.
This part is confusing in my opinion. It makes it sounds like AlphaGo is not using Monte Carlo Tree Search, which is mentioned earlier. However, this is exactly what AlphaGo is doing, except with the policy network in place of previous methods for initializing move priors, and the value network in place of traditional methods for terminating and scoring simulations.
(But you need the tree search to make a strong player)
https://www.quora.com/How-significant-is-the-AlphaGo-victory...
I thought that many of the answers were quite insightful.
Disclaimer: I also wrote an answer, but the submission deadline for the knowledge prize is over.
> We have learned to use computer systems to reproduce at least some forms of human intuition.
Hmm .... Let's examine that claim:
To set aside the game of Go, we start with an analogy: A human can walk 10 miles to town, and a car can help one drive the same 10 miles to town. But what a car does to get to town is very different from what a walking human does. Both approaches get to town, and the car is much better in various ways, but this does not mean that a car walked like a human. To be clear, specifically the car did not "reproduce" the way a human gets to town; e.g., the car did not have two legs. Both the human and the car got to town? Yes. The car "reproduced" how a human got to town on two legs? No.
Similarly, a motor boat does not "reproduce" some forms of human swimming.
This pattern of using science, engineering, etc. to get results comparable with those of unaided humans is very old with many great examples from especially the last 100 years.
Further, on "intuition", there are many tasks that humans do with human intuition where science, engineering, and computing do comparably well, but that does not mean that the science, etc. has "reproduced" human intuition.
Similarly, on the game of Go, AlphaGo got some game successes that humans get via human intuition, but that does not mean that AlphaGo "reproduced" human intuition, not in general and not even in the specific case of the game of Go.
Early in IBM's mainframe computing, in the common publicity, there was a related claim that IBM's computers were "gigantic electronic human brains". Those computers were no more "human brains" than Henry Ford's Model T was gigantic mechanical human legs. A car is not human legs, and an early IBM computer was not a human brain.
IMHO, there is an important point here: From the publicity about IBM's early computers to the claim in the OP I quoted above, there are claims that computing and computer science are reproducing some of how humans do things. But so far this claim is false, seriously false, not even close to the truth: Computers are no closer to reproducing human intelligence or "intuition" than Ford's Model T was to reproducing human legs.
Instead, apparently AlphaGo is a some high dimensional data fitting to yield a classification system, that is, given a board position in Go, AlphaGo reports 0 for bad for the AlphaGo player and 1 good for the AlphaGo player. So, they have a classifier.
But classifiers go way back, to Leo Breiman's random forests, classification and regression trees (CART), logistic regression, a huge range of statistical tests, e.g., in some cases of advanced radar target detection, and much more. Many such solutions have been very valuable, and maybe AlphaGo or its techniques will also be valuable, but none of this in any sense reproduces human intuition or really anything about humans -- not yet, not even close.
Net, while it's a free country and people can disagree, which is one role of HN, IMHO, the quote I gave above from the OP is scientifically irresponsible. It just isn't really true. At best it is just hype.
Even evaluating a single play state is a difficult problem, let alone looking forwards to 'simply taking the route giving max probability of success'. That's not simple at all.
Go is fiendishly difficult to evaluate. The traditional techniques that work in chess don't work well in Go (if at all). All the pieces have the same 'value'. More or less pieces isn't necessarily better or worse, it depends on the board layout. It's not at all easy to say who's winning or losing at most points in the game, or if there even is a winner or a loser. There is no mathematically-obvious way to compare two play states and say one is better than the other. The branching factor is huge, making the usual forward-looking techniques extraordinarily expensive. The number of possible legal boards states is something like 90 orders of magnitude greater than the number of atoms in the observable universe, making backward-looking techniques like minimax impossible, even if you could easily assign an evaluation function to each state.
You play out the game to the end.
making backward-looking techniques like minimax impossible, even if you could easily assign an evaluation function to each state.
That's exactly how AlphaGo works though. Read this paper, it was the landmark result that showed how to do this: http://www.remi-coulom.fr/CG2006/
AlphaGo uses the same technique, just optimized a bit more.
Nope. You could play out to one or several ends, but there is a huge number of possible end games at any given point. Simply saying 'play out the game to the end' is a gross simplification.
The average branching factor is something like 200, so just to fully evaluate just 5 moves ahead would require traversing 320 billion game states. Go games are 100-200 moves per game, so 5 moves ahead doesn't even get you close to the end of a game. At the first move there are 208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935 legal board states you'd have traverse to reach all end games. Yes, that's an exact figure. (http://tromp.github.io/go/legal.html)
How big is that figure? If you counted up the number of fundamental particles in the entire universe, and for each fundamental particle there was another complete universe of fundamental particles and you counted all of those too, and then do all of that once for every person in the USA add up their answers, you'd be at about 3% of the way to that value.
You simply cannot do a full evaluation to the end of the game: it's computationally infeasible.
That's exactly how AlphaGo works though (minimax)
No, it's not. Minimax requires working back from all end-game states, and there are too many end-game states to be evaluated. I suggest you read the paper yourself. It's about doing random partial evaluations and forward-looking searches of the game space, and choosing clever subsets to evaluate, precisely because you can't evaluate them all. The 'backing up' referred to in the paper is backing evaluation values up the tree after you've looked ahead a while, not starting at all possible end games and backing up from there, as in classic minimax. Some of the basic concepts are similar to classic tic-tac-toe or chess algorithms, but combining them in new ways.
AlphaGo uses the same technique, just optimized a bit more.
And a fighter jet uses the same technique as a paper aeroplane, only optimized a bit more...
You can sample several randomly played out games. I think you knew this, and I hope you understand that sampling works, but for some reason you went on a completely irrelevant tangent.
Minimax requires working back from all end-game states
Practical implementations that need to achieve good but not perfect play are content to stop at a point before that.
Again, do you know this and are intentionally misunderstanding me and throwing up irrelevant facts? I'm sure you did given that you even acknowledge the above (no need for terminal states) in your previous post.
The difficulty of Go was that there was no way to combine tree search with the uncertainty inherent in Monte Carlo samples with a low sample count. The paper I mentioned fixed this, and hence was THE major breakthrough. The resulting algorithm is still quite simple, yet plays arbitrarily strong, also in practice, when given more computing resources.
It makes a minimax-like algorithm work for go because it estimates the terminal results by Monte Carlo sampling the results of the games when played out by a random (or in practise, not entirely random) player.
Practical implementations that need to achieve good but not perfect play are content to stop at a point before that.
Indeed, but that's not the basic minimax algorithm (which is what I was discussing) and the branching factor of go makes classic minimax infeasible even if you modify it to be forward-looking. Basic minimax is not good for Go. At all. You have to combine it with other techniques for it to be even vaguely effective. You know this, but didn't mention it. So how is anyone supposed to infer that you know it?
I can see now that you have a decent understanding of the actual solution, but that's not at all what you wrote above.
For example, you said to evaluate a game board you need to 'play the game through to the end' -- which hides all that complexity of monte-carlo tree evaluation, etc. Read what you wrote again from the point of view of someone who isn't yourself.
Simply saying 'Play the game through to the end' by itself is neither correct nor accurate. Because that implies evaluating the rest of the game to its conclusion. i.e. every board state. You omitted any other detail or reference. So I descibed how and why it's not feasible (which you now discount as going off at a tangent). You gave no prior indication of understanding this.
Another example: in a previous comment I described how backward looking techniques like the minimax algorithm are not feasible for go, and you said:
"That's exactly how AlphaGo works though".
But it isn't at all:
Classic minimax is backward-looking (starts at end states and works backwards -- this is what I was talking about, and what I described); AlphaGo (and the paper you linked to) is forward-looking (starts at current root and works forwards).
Classic minimax is full-tree evaluation; AlphaGo is partially-evaluating.
Minimax is deterministic; AlphaGo is stochastic/random sampling.
Minimax uses a simple single-value single-direction evaluation function; AlphaGo uses a complex bi-directional multi-value evaluation.
I could go on.
Read any treatise or any introduction to AI for Go and pretty much the first chapter will be describing how classic minimax is not suitable without heavy modification.
e.g. https://www.youtube.com/watch?v=5oXyibEgJr0
AlphaGo uses some of the same concepts, but applied very differently, as you appear to already know. Yet after I mentioned minimax (which is well-known as an infeasible algorithm for go), you responded:
"That's exactly how AlphaGo works though".
Which is not at all true.
And then you link to a paper that describes precisely how it's not how it works, and why minimax-related techniques alone don't work, in stark contradiction to yourself.
I'm not intentionally misinterpreting what you wrote: I'm taking a reasonable interpretation of what you actually wrote, which appears to show a lack of understanding on your part. I don't think there is a lack of understanding, now, but it's hard to come to a different conclusion based on what you wrote before.