AlphaGo Zero: Learning from scratch
deepmind.com
deepmind.com
I also wonder how much it’s style of play changes if it were re trained, due to the random start that it is given. Maybe that would produce something like seeds for procedurally generated worlds in games. Like if they could find a seed for a Chinese or japanese players, or ones that more aggressive styles. This is some pretty cool work and may open up even more doors for pure reinforcement learning
> To assess the merits of self-play reinforcement learning, compared to learning from human data, we trained a second neural network (using the same architecture) to predict expert moves in the KGS Server data set; this achieved state-of-the-art prediction accuracy compared to pre vious work 12,30–33 (see Extended Data Tables 1 and 2 for current and previous results, respectively). Supervised learning achieved a better initial performance, and was better at predicting human professional moves (Fig. 3). Notably, although supervised learning achieved higher move prediction accuracy, the self-learned player performed much better overall, defeating the human-trained player within the first 24 h of training. This suggests that AlphaGo Zero may be learning a strategy that is qualitatively different to human play.
EDIT: changed a set of neurons to neural network per andbbergers comments
Sorry to be that guy, but the AI hype is getting out hand. COSYNE this year was packed with papers comparing deep learning to the brain... it drives me nutty. Convnets can be reasonably put into analogy with the visual system.... because they were inspired from it. But that's about it.
To address your actual comment: I would argue that this is not really interesting or surprising (at least to the ML practitioner), it is very well known that neural nets are incredibly sensitive to initialization. Think of it like this: as training progresses, parameters of neural nets move along manifolds in parameter space, but they can get nudged off of the "right" manifold and will never be able to recover.
Sorry for the rant, the AI hype is just getting really out of hand recently.
Machine learning is specifically not magic. Blackboxes are not useful. Convnets work so well because they build the symmetries of natural scenes directly into the model - natural scenes are translation invariant (as well as a couple of other symmetries), anything that models them sure as hell better have those symmetries too, or you're just crippling your model with extra superfluous parameters.
Makes neuroscience seem kinda bleak doesn't it?
There has been a lot of great work lately building up a theory of how these things work, but it is very much still in the early stage. Jascha Sohl-Dickstein in particular has been doing some great work on this.
We don't even have answers to the most basic questions.
For instance (pedagogically), how the hell is it possible to train these things at all? They have ridiculously non-convex loss landscapes and we optimize in the dumbest conceivable way, first-order stochastic gradient descent. This should not work. But it does, all too often.
Not a great example because there are easy hand wavy arguments as to why it should work, but as far as proofs go...
The hand wavy argument goes as follows: - we're in like a 10000 dimensional space, for the stationary point we're at to be a true local minima that means each one of those 10000 dimensions goes uphill in either direction. It's overwhelming likely that there's at least one way out - there are many many different ways to set the params of the net for each function. Permutation is a simple example.
We really have no idea how these things work.
Anyone who tells you otherwise is lying to you...
Of course we do. It's matching a smooth multi-dimensional curve to sample data.
What I found interesting was mainly that it was us who nudged the parameter space you talked about into the "wrong" one manifold, especially given how old and complicated Go is. The sheer amount of human brain power that has been put into getting good at a game wasn't able to find certain aspects of it, and in 60 hours of training a neural network was able to.
We absolutely should and do look to the brain for inspiration.
I'm taking issue with the rather ham-fisted series of papers that have come out in recent years aggressively pushing the agenda of connections between ML and neuro that just aren't there.
Are you sure that humans have done more net compute on Go than Deepmind just did? The Go game tree is _enormous_, humans are bias. We don't invent strategies from scratch, we use heuristics handed down to us from the pros (who in turn were handed down the heuristics from their mentors).
To me, it's not so interesting or surprising that the human initialized net performed worse. We just built the same biases and heuristics we have into that net.
The question is whether it can do so efficiently. As far as I know, alternating applications of affine transforms and non-linearities are not so useful for some computations that are known to occur in the brain such as routing, spatio-temporal clustering, frequency filtering, high-dimensional temporal states per neuron etc.
When you're a big scientific figure, I think that you have some extra responsibility to the public to only say things you're very confident about. Or otherwise very clearly communicate your uncertainty!!
It's not like neuroscientists know that either.
I'm not an expert, but my impression is that this is not really a reasonable claim, unless you're only considering very small function-like subsystems of the brain (e.g. visual cortex). Neural nets (of the nonrecurrent sort) are strict feed-forward function approximators, whereas the brain appears to be a big mess of feedback loops that is capable of (sloppily, and with much grumbling) modeling any algorithm you could want, and, importantly, adding small recursions/loops to the architecture as needed rather than a) unrolling them all into nonrecursive operations (like a feedforward net) or b) building them all into one central singly-nested loop (like an RNN).
The brain definitely seems to be using something backprop-like (in that it identifies pathways responsible for negative outcomes and penalizes them). But brains also seem to make efficiency improvements really aggressively (see: muscle memory, chunking, and other markers of proficiency), even in the absence of any external reward signal, which seems like something we don't really have a good analogue for in ANNs.
The constraints you mention aren't deal breakers. We can make RNNs without maintaining a global state and fully unrolling the loop. See synthetic gradients for instance. NNs can do unsupervised learning as well, through things like autoencoders.
"These search probabilities usually select much stronger moves than the raw move probabilities of the neural network; MCTS may therefore be viewed as a powerful policy improvement operator. Self-play with search – using the improved MCTS-based policy to select each move, then using the game winner as a sample of the value – may be viewed as a powerful policy evaluation operator. The main idea of our reinforcement learning algorithm is to use these search operators repeatedly in a policy iteration procedure ..."
The fact that this reinforcement training is unsupervised from the very beginning is quite exciting and may lead to better heuristics for other kinds of combinatorial optimization problems.
As a side note, the main application I have seen with adversarial learning research is with photo recognition, but I guess you could have an adversarial network exist to help help improve an object recognition network. At that point it would probably become something between adversarial and reinforcement learning. However, with game based reinforcement learning, it doesn't require a second specific network as the adversary, it can easily just be paired against itself.
It isn't a dumb question, they are very similar in some ways. They mainly differ in what exactly the goal of the opponent is. In this case, it is to help improve itself, however in typical adversarial situations it is solely to exploit (become its adversary).
One thing Alpha go has told us clearly is that it thinks human players over value the margin of victory vs the probability of victory.
That way, each player could know, at all times, (one major factor that goes into) their probability of winning. They'd still have to mentally adjust it for the likelihood of them and their opponent making an error, and how that can be controlled by making intimidating moves, etc. But it could lead to much tighter control on the abstract flow of the game.
It'd almost be like the computer was the general, issuing strategy, picking battles; and the human player the tactician, fighting those battles.
Knowing that the opponent's winning probability changed from 52 to 57 was interesting only because it hints at a mistake. In case of such a large change the program suggests the move it would have played.
I saw an annotated game record and there were no variations: I remember a suggested move that made me wonder "why!?".
Another benefit of seeing the value of the winning probability is an assessment of who's ahead. However that's already possible with the score estimation that programs and go servers provide. Sometimes is crude, sometimes is good, but it's the score, not the winning probability that humans can estimate when playing. The best probability estimate I can make is: if the score is close and the game is still complicated, it's 50-50; if the score is close but the game is almost over, it's 95-5 for who's ahead. If the score is not close, the player with more points will probably win.
AlphaGo now appears to be better than humans in all aspects of gameplay, and it better at calculating very thin margins of probability that a human cannot. This is not unique to any individual aspect of its gameplay; against humans it can also win by huge margins depending on what mistakes the human makes.
I'm talking specifically about game #4 of the Lee Sedol games.
> I wonder if this system produced more new styles of play.
Absolutely. One such innovation has been the use of early 3-3 invasions [1]. There are many more, and indeed AlphaGo's games are still being analyzed by professional players. Michael Redmond, a 9-dan professional, has been working with the American Go Association on one such series [2].
> I wonder if the fact that it had no outside reinforcement made it produce movements that we have already seen that are somehow inherent to the game...
Interestingly, yes. Strong players have commented that AlphaGo seems to agree with things that players like Go Seigen [3] have suggested in the past, but that were never fully developed or understood [4].
Very, very interesting work indeed.
[0] https://senseis.xmp.net/?ShinFuseki
[1] https://www.eurogofed.org/index.html?id=127
[2] http://www.usgo.org/news/category/go-news/computer-goai/mast...
[3] https://senseis.xmp.net/?GoSeigen
[4] https://lifein19x19.com/forum/viewtopic.php?f=13&t=14129
They do say the rules used for all games, including self-play, set komi consistently to 7.5 .
If the strongest AI was consistently winning predominantly with one color it would be an indication that komi isn't fair for the best play.
Of the 20 games released for the strongest play it appears white won 14 times and black 6. I don't think that is enough to be conclusive but maybe komi is too high.
I wonder if different "correct" play at the strongest levels would be learned with a 6.5 komi.
From a theoretical standpoint, any non-integer komi should lead to one player winning 100% of the time. So even if the actual win ratio is 14:6 at komi=7.5 that might still be the best value.
I agree that with perfect play, it will be a 50% of a tie to each side. But it is still interesting to ask for a better estimate of practical play.
Or am I misunderstanding the hardware requirements?
for whatever reason, it's no longer feasible in modern pro game (not to mention that this could result in no winner if each player wins half the game), so komi was introduced. at first at 5.5, and steadily climbed higher to 7.5 at present. In pro game, even a change of 1 is considered a big deal, so from 5.5 to 7.5 is hardly trivial.
Now with alphago playing "perfect" games against itself, we might finally be able to put to rest the debate of the correct komi (the Japanese Go associations for decades have kept meticulous records of every professional game, in order to find the correct komi).
There is a big "but" though. The correct komi at Alphgo Zero's level might not be the correct komi for human level players (AlphaGo is estimated to be 2-3 handicaps above human play; this is a bigger gap between the average pro player and the best amateurs).
Indeed, the change from 5.5 komi to 7.5 komi also had a lot to do with the change in play style rather than simply zooming in on the "correct" komi number. In the 70s and 80s, predominant play style was more conservative, and 5.5 might well be the correct komi for the time (defined as resulting in 50:50 chance of winning for either side). As play style shifted to become more aggressive and confrontational (actually fueld somewhat by the introduction of komi), it was discovered that komi needs to be raised to keep chances of winning at 50:50.
To make an analogy, suppose one is playing a casino game of chance that gives the house a slight advantage (similar to the first mover advantage for black in go). If one only makes small bets, the house will end up winning only a small amount. in other words, the player needs to be compensated by a small amount to make the game "fair".
If however one makes big bets (i.e. more aggressive game play), then the compensation needs to be bigger too, to make the game "fair", even if the underlying probabilities have not changed.
following this logic, while 7.5 komi is fair for Alphago vs. alphago games, it might not be the right number for human games. I suspect it might be samller for humans.... if only we could calibrate Alphago to the average human level and generate millions of self-play games...
You've commented on the differences in the style of play that AlphaGo introduced, but the post you were replying to (by aeleos) was going a step further and hypothesising about the potential for a newer, completely 'non-human' style that AlphaGo Zero may have created.
Your comments definitely contribute to the discussion but it was bugging me that there appeared to be a tangent forming about AlphaGo that was overlooking AlphaGo Zero which would be the more interesting area to explore.
While it's true that there are national styles of play, the Chinese opening is not called that because it's really popular among Chinese people. It's called that because a particular Chinese pro helped popularize it, even though it was invented by a Japanese amateur.
See https://en.wikipedia.org/wiki/Chinese_opening for some more info. FWIW, I (a caucasian American) use this opening all the time. It's just a generally good opening if you like a certain style of play.
Came here to make this point.
It's Chinese Opening, not Chinese start – similarly recall that you have the French Defense / Italian Defense / Scandinavian Defense among chess opening variations and none of these implies that that opening variation is specific to that culture or nation.
https://intelligence.org/2017/10/13/fire-alarm/
Yes, this is not an AGI. But the hockey-stick takeoff from defeats some players, to defeats an undefeated world-champion, to defeats the version of itself that beat the world champion 100% of the time is nuts. If this happens in other domains, like finance, health, paper clip collection, the word singularity is really well chosen--we can't see past this.
> AlphaGo Zero does not use “rollouts” - fast, random games used by other Go programs to predict which player will win from the current board position. Instead, it relies on its high quality neural networks to evaluate positions.
There's no way to train an AI like this for, say, health: We cannot simulate the human body to the level of detail that's required, and we definitely aren't going to be able to do it at the speed required for a system like this for a very long time. Producing a definitive, objective score for a paper clip collection is very difficult if not impossible.
AlphaGo/DeepMind represents a very strong approach to a certain set of well-defined problems, but most of the problems required for a general AI aren't well-defined.
Do you care to give an example? Are they more or less well defined than find-the-cat-in-the-picture problem?
> Producing a definitive, objective score for a paper clip collection is very difficult if not impossible.
Erm, producing of objective comparison of relative values of Go board positions is still not possible.
You may have a seemingly good position and in two turns it seems that you have lost the game already.
"Finally, it uses a simpler tree search that relies upon this single neural network to evaluate positions and sample moves, without performing any Monte Carlo rollouts."
In this new version, MCTS is not even used to evaluate a position! Speaking as a Go player, the ability for the neural network to accurately evaluate a position without "reading" ahead is phenomenal (again, read the Nature paper last page for details).
You mean like go over and feed the neighbor's cat while they're on vacation?
How about instead, being able to clean any arbitrary building?
Go isn't remotely similar to the real world. It's a board game. A challenging one, sure, and AlphaGo is quite a feat, but it's not exactly translatable to open ended tasks with variable environments and ill-specified rules (maybe the neighbor expects you to know to water the plants and feed the goldfish as well).
The limiting factor with the neighbors cat is the robotics of having a robust body and arm attachment. We know that the scope of current AI can:
1) Identify a request to feed a cat
2) Identify the cat, cat food and cat's bowl from camera data
3) Navigate an open space like a house
Being able to clean an arbitrary building is also more the challenge of building the robot than the AI identifying garbage on a floor or how to sweep something.
It is not clear there are hard theoretical limits on an AI any more. There are economic limits based on the cost of a programmer's attention. There are lots of hardware limits (including processor power).
For "cat in the picture", every picture must have the cat first identified by a person, so the training set is much smaller, and Google can't throw GPUs at the problem.
The field progresses swiftly. https://arxiv.org/abs/1602.00955
A-ha! So we use AGI for this! :-)
For me, as someone who accepted and believed these claims about Go being qualitatively different, realizing that no, it's not qualitatively different (or that maybe it is, but not in a way that impedes state-of-the-art AI research) is increasing my skepticism in other claims that board games in general are qualitatively different from other tasks that AIs might get good at.
(If you didn't buy into these claims, then I commend you on your reasoning skills, carry on.)
Go is a deterministic game, but the large branching factor makes it challeging. The key issues and early literature in computer Go are summarized by Boozy and Cazenave (2001) and Muller (2002). Up to 1997 there were no competent Go programs. Now the best programs play most of their moves at the master level; the only problem is that over the course of a game they usually make at least one serious blunder that allows a strong opponent to win. Whereas alpha—beta search reigns in most games, many recent Go programs have adopted Monte Carlo methods based on the UCT (upper confidence bounds on trees) scheme (Kocsis and Szepesvari, 2006). The strongest Go program as of 2009 is Golly and Silver's MoGo (Wang and Golly, 2007; Gelly and Silver, 2008). In August 2008, MoGo scored a surprising win against top professional Myungwan Kim, albeit with MoGo receiving a handicap of nine stones (about the equivalent of a queen handicap in chess). Kim estimated MOGO's strength at 2-3 dan, the low end of advanced amateur. For this match, MoGo was run on an 800-processor 15 terailop supercomputer (1000 limes Deep Blue). A few weeks later, MoGo, with only a five-stone handicap, won against a 6-dan professional. In the 9 x 9 form of Go, MoGo is at approximately the 1-dan professional level. Rapid advances are likely as experimentation continues with new forms of Monte Carlo search. The Computer Go Newsletter, published by the Computer Go Association, describes current developments.
There's no word about how Go is qualitatively different to other games, but maybe the referenced sources say something along those lines. Personally, I took a Masters course in AI two years ago, before AlphaGo and I remember one professor saying that the last holdout where humans can still beat computers in board games was GO, but I don't quite remember him saying anything about qualititative difference. Still, I can recall hearing about the idea that Go needs intuition or something like that, except I've no idea where I've heard that. I guess it might come from the popular press.
I guess this will sound a bit like the perenial excuse that "if it works, it's not AI" but my opinion about Go is that humans just weren't that good at it, after all. We may have thought that we have something special that makes us particularly good at Go, better than machines- but AlphaGo[Zero] has shown that, in the end, we just have no idea what it means to be really good at it (which, btw, is a damn good explanation of why it took us so long to make AI to beat us at it).
That, to my mind, is a much bigger and much more useful achievement than making a good AI game player. We can learn something from an insight into what we are capable of.
False, because nobody ever bothered to study modern boardgames rigorously.
Modern boardgames have small decision trees but very difficult evaluation functions. (Exactly opposite from computational games like Go.)
Modern boardgames can probably be solved by pure brute force calculation of all branches of the tree, but nobody knows if things like neural networks are any good for playing them.
I've seen some AI research in more modern board games actually. I've read a couple of papers discussing the use of Monte Carlo Tree Search to solve creature combat in Magic: the Gathering and my own degree and Master's dissertation were about M:tG (my Master's was in AI and my degree dissertation was an AI system also).
I don't know that much about modern board games, besides collectible card games, but for CCGs in particular, the game trees are not small. I once calculated the time complexity of traversing a full M:tG game tree as O(b^m * n^m) = 2.272461391808129337799800881135e+5564 (where b the branching factor, m the average number of moves in a game and n the number of possible deck permutations for a 60 card deck taking into account cards included multiple times). And mine was probably a very conservative estimate.
Also, to my knowledge, Neural nets have not been used for magic-playing AI (or any other CCG playing AI). What has been used is MCTS, on its own, without terrible success. The best AI I've seen incorporates some domain knowledge, in the form of card-specific strategies (how to play a given card).
There are some difficulties in using ANNs to make an M:tG AI. Primarily, the fact that a truly competent player should be able to pick up a card it's never seen before and play it correctly (or decide whether to include it in a deck, if the goal is to also address deck-building). For this, the AI player will need to have at least some understanding of M:tG's language (ability text). It is my understanding that other modern games have equal requirements to understand some game context outside of the main rules, which complicates the traditional tactic of generating all possible moves, pruning some and choosing the best.
In any case what I meant to say is that people in AI have indeed considered other games besides the classical ones- but when we talk about "games" in AI we do mean the classics.
Only because of inertia. There's nothing inherently special about "classics". Eventually somebody will branch out once Go and poker are mined out of paper and article opportunity.
Once we do then maybe some new, interesting algorithms will be found.
In principle, every game can be solved by storing all possible game states in a database. Where brute-force storing is impractical due to size concerns, compression tricks have to be used.
E.g., Go is a simple game because at the end, every one of the fixed number of board spaces is either +1, -1 or 0. Add them up and you know if you won. This means that every move is either "correct" or "incorrect"; the problem of classifying multidimensional objects into two classes is a problem that we're pretty good at now, and things like neural networks get the job done.
A slightly more complex game like Agricola has no "correct" and "incorrect" moves because it's not zero-sum; you can make an "incorrect" move and still win as long as your opponent is forced to make a relatively more "incorrect" move.
Not sure how much of a difference that makes, but what's certain is that by (effectively) solving Go we've only scratched the surface. It's not the end of research, only the beginning.
I think you're underestimating the amount of work and determination it took to get to where we are today, though (I mean your comment about "inertia"). Classic board games have the advantage of a long history and of being well understood (the uncertainty about optimal strategies in Go notwithstanding). Additionally, for at least some of them like chess, there are rich databases of entire games that can be used outright, without the AI player having to generate-and-test them in the process of training or playing.
The same is not true for modern games. On the one hand, modern board games like Agricola (or, dunno, Settlers or Carcassonne etc) don't have such an extensive and multi-national following as the classics so it's much harder to find a lot of data to train on (which is obviously important for machine-learning AI players). I had that problem when considering an M:tG AI trained with machine learning: I would have liked to find play-by-play data on professional games but there just isn't any (or where there is it's not enough, or it's not in any standardised format).
Finally, classic board games have cultural significance that modern board games dont' quite match, despite the huge popularity of CCGs like M:tG or Pokemon, or Eurogame hits like Settlers. Go, chess and backgammon in particular have tremendous historical significance in their respective areas of the world- chess in Eastern Europe, backgammon in the Middle East, Go in SE Asia. People go to special academies to learn them, master players are widely recognised etc. You don't get that level of interest with modern board games- so there's less research interest for them, also.
People in game playing AI have been trying for a very long time to crack some games like Go and, recently, poker (not quite cracked yet). They didn't sit around twiddling their thumbs all those years, neither did they choose classical board games over modern ones just because they didn't have the imagination to think of the latter. In AI research, as in all research, you have to make progress before you can make more progress.
> my opinion about Go is that humans just weren't that good at it, after all. We may have thought that we have something special that makes us particularly good at Go, better than machines- but AlphaGo[Zero] has shown that, in the end, we just have no idea what it means to be really good at it (which, btw, is a damn good explanation of why it took us so long to make AI to beat us at it).
I really like that interpretation!
No, Go is a much less intelligent[1] game. It has a huge decision tree and requires massive amounts of computation to play, but walking trees and counting is exactly what computers do well and what humans do poorly.
[1] 'Intelligence' here means exactly that which differentiates humans from calculators: the ability to infer new rules from old ones.
The other is the entire reason for high APM, the stop/start problem. Pro players keep high APM so that when they actually need high EPM their muscle memory is already at full tilt. If you slow down your APM during lulls in the action it becomes harder to suddenly increase it when a fight happens.
Certainly that's an entirely human condition that a machine wouldn't need to worry about. But I'm not sure it means lack of skill.
This is an interesting question to ask in these "how far away is AGI" discussions:
I was once at a conference where there was a panel full of famous AI luminaries, and most of the luminaries were nodding and agreeing with each other that of course AGI was very far off, except for two famous AI luminaries who stayed quiet and let others take the microphone.
I got up in Q&A and said, “Okay, you’ve all told us that progress won’t be all that fast. But let’s be more concrete and specific. I’d like to know what’s the least impressive accomplishment that you are very confident cannot be done in the next two years.”
There was a silence.
Eventually, two people on the panel ventured replies, spoken in a rather more tentative tone than they’d been using to pronounce that AGI was decades out. They named “A robot puts away the dishes from a dishwasher without breaking them”, and Winograd schemas. Specifically, “I feel quite confident that the Winograd schemas—where we recently had a result that was in the 50, 60% range—in the next two years, we will not get 80, 90% on that regardless of the techniques people use.”
It will seem quite stupid and inept at first. So people will dismiss it. But when they have a system with general inputs and outputs that can acquire multiple different skills, that will be an AGI, and we can grow it's skills and knowledge passed human level.
The hockey stick is lying horizontally though instead of vertically. If it took 3 days to go from 0 to beating the top player in the world, I wouldn't have expected it to take 21 days to beat next version. I guess something happens at the top levels of Go that make training much harder.
On another note, I didn't look at the details closely but it seems AlphaGo Zero needed much less compute training time than Alpha Go Master. Could getting rid of any human inputs really make it that much more efficient? That implies it will be able to have an impact in many different areas, which is a bit scary...
(Updated - it took 3 days to beat the top player in the world.)
What is, perhaps, surprising is that human play happens to be relatively close to the asymptote. Although this could be explained by Alphago being the first system to beat humans. If its peek performance were orders of magnitude higher than humans, a weaker program would have already beaten us.
At some point, a military is going to develop autonomous weapons that are vastly superior to human beings on the battle field, with no risk of losing human lives, and there is going to be a blitzkrieg sort of situation as the relative power of nations shifts dramatically.
If we have two such countries we could have massive drone and cyberwars being fought faster than people even can comprehend what's happening.
Right now most countries insist on maintaining human control over the machinery of death. But that will only last for as long as autonomous death machines don't dominate the battlefield.
It's a fun challenge right now to build a machine that can win in Starcraft, but it's really a hop skip and a jump from there to winning actual wars.
"We don't know how AGI will arise; we don't know when; we don't know why; we don't know anything at all about it and we won't know anything about it until it's too late to do anything anyway; We must act now!!"
The question is- if we don't know anything about this unknowable threat, how can we protect ourselves against it? In fact, since we're starting from 0 information, anything we do has equal chances of backfiring and bringing forth AGI as it has of actually preventing it. Yudkowski is calling for random action, without direction and without reason.
Besides, if Yudkowski is none the wiser about AGI than anyone else, then how is he so sure that AGI _will_ happen, as he insists it will?
Yudkowski is fumbling around in the dark like everyone else in AI. Except he (and a few others) has decided that it's a good strategy, under the circumstances, to raise a hell of a racket. "It's dark!" he yells. "Beware of the darkness!". Yeah OK, friend. It's dark- we can all tell. Why don't you pipe down and let us find the damn light?
You exemplify exactly the attitude he's trying to combat. "Oh, nobody knows anything, let's not care about consequences and do whatever."
Are you sure you read the essay? That's literally the question he answers.
At any rate, we do have more than '0 information', and if you make an honest effort to think of what to do you can likely come up with better than 'random actions' for helping (as many have).
My reading of the article is that he keeps calling for action without specifying what that action should be and trying to justify it by saying he can't know what AGI would look like (so he can't really say what we can do to prevent it).
>> if you make an honest effort to think of what to do you can likely come up with better than 'random actions' for helping (as many have).
Sure. If my research gets up one day and starts self-improving at exponential rates I'll make sure to reach for th
So technically this version has lost every game it's ever won.
Jokes aside, it's pretty interesting to note that they were able to combine the "policy" and "value" networks. Good SO answers on the difference (https://datascience.stackexchange.com/questions/10932/differ...)
> accumulating thousands of years of human knowledge during a period of just a few days
It'd be interesting for what this would mean when things like a neural lace become a reality.
As an aside, anyone have any other links or references to others investigating learning algorithms with a 'tabula rasa' approach?
I believe their DotA 2 AI uses that approach
No, they've also played it against AlphaGo Lee and AlphaGo Master. The SGFs are available at: https://www.nature.com/nature/journal/v550/n7676/extref/natu...
Temporal difference learning was previously consider weak at 'tactical' games, ie ones with gamestates that require long chains of precise moves to improve position (like many checkmate scenarios in chess) .
For anyone more familiar with this technique, is it clear how the mcts/checkpoint system overcomes this? How sensative is the system to the tuning params for those parts of the alg. Like is Go a particularly good candidate because of the ~400 play positions resulting in a (relatively) small tree seach requirement? (I kinda cant believe im saying that go has 'a small search tree'!)
We us td learning for the ai in our game Race for the Galaxy, so it's neat to hear about possible avenues for improvement!
edit: OK, they're calling it policy iteration as opposed to TD learning. I guess I don't get the difference.
https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume4/kaelb...
It was interesting to note that TD-Gammon improved with expert designed features. I wonder if this was simply related to the technology of the field as it stood over 20 years ago or some underlying categorization or complexity associated with the games themselves (backgammon being more favorable to human comprehension than Go in this case).
> Even though TD-Gammon discovered insightful features on its own, Tesauro wondered if its play could be improved by using hand-designed features like Neurogammon's. Indeed, the self-training TD-Gammon with expert-designed features soon surpassed all previous computer backgammon programs. It stopped improving after about 1,500,000 games (self-play) using 80 hidden units.
For others: Richard Sutton, one of the pioneers of TD makes his Reinforcement Learning: An Introduction textbook available for free on his website: http://incompleteideas.net/sutton/ (MIT Press also links to it)
In addition to numerous journal articles, the creators wrote a lay-person book on their creation: Blondie24: playing at the edge of AI, by David B. Fogel [2].
This is amazing! The technology they came up with must be super generic.
> The neural network in AlphaGo Zero is trained from games of selfplay by a novel reinforcement learning algorithm. In each position s, an MCTS search is executed, guided by the neural network fθ. The MCTS search outputs probabilities π of playing each move. These search probabilities usually select much stronger moves than the raw move probabilities p of the neural network fθ(s); MCTS may therefore be viewed as a powerful policy improvement operator. Self-play with search—using the improved MCTS-based policy to select each move, then using the game winner z as a sample of the value—may be viewed as a powerful policy evaluation operator. The main idea of our reinforcement learning algorithm is to use these search operators repeatedly in a policy iteration procedure: the neural network’s parameters are updated to make the move probabilities and value (p, v)= fθ(s) more closely match the improved search probabilities and selfplay winner (π, z); these new parameters are used in the next iteration of self-play to make the search even stronger.
Statements like these always make me wonder why certain obvious things weren't tried. If it's so generic, why wasn't it tried on Chess? Or was it tried, failed to impress and thus didn't make it into the press release?
This is a big problem with all these public discussion on AI. Almost no one speaks about algorithm failures. I haven't seen a single research paper that said "oh, and we also tried algorithm in X domain and it totally sucked".
Modern Chess engines are designed to brute-force the search tree as efficiently as possible. I will go out on a limb here and say they would wipe the floor with AlphaGo, because AlphaGo's hardware would be more of a liability than an asset against a CPU.
See also: https://chessprogramming.wikispaces.com/Type+A+Strategy https://chessprogramming.wikispaces.com/Type+B+Strategy
Give me your results on OpenAI gym in a variety of different styles of games including GTA and WoW. I will believe you if a generic unsupervised algorithm running on a single machine is absolutely destroying the best players.
Until then ...
Universality is the real hard problem of AI. In the long run, a mediocre AI that does a lot of different things is far more useful that most targeted "superhuman" AIs. Most domains simply don't require better-than-human performance, but could still reap tremendous benefits from automation.
thx :)
For example, after this result it seems if you can reduce your problem domain onto Go (or a similarly structured game) you now have a way to create a superhuman solver. It may just be easier to do that then try to even figure out how to design and tune a new network.
I could imagine waking up in 10 years being confused at why all software efforts in the AI space are focused on just figuring out clever ways to map real problems onto a hodgepodge of seemingly random "toy" domains like Go and Chess and Starcraft. Hell, maybe the Starcraft bot will immortalize Starcraft in a way the game never would have been able to if it becomes a good reduction target for a lot of domains.
It kind of reminds me of how SVMs were "abused" by twisting non-linear domains into them via kernel methods, or by proving the NP-equivalence of a problem by reducing it onto 3-SAT, or how ImageNet's weights are being re-purposed for other image oriented prediction tasks.
[1] https://www.youtube.com/watch?v=5mvfpSdWsOo "Brute Force and Intelligent Paradigms of Learning"
1) Using Residual networks instead of normal convolutional layers
2) Using a smarter policy training loss that uses the full information from a MCTS at each move. In the previous version, I believe they just ran the policy network to the end of the game and used a very weak {0, 1} reinforcement signal over all of the moves played. Here, it looks like they use each run of MCTS to provide a fully supervised signal over all moves it explores.
"AlphaGo Zero is the program described in this paper. It learns from self-play reinforcement learning, starting from random initial weights, without using rollouts, with no human supervision, and using only the raw board history as input features. It uses just a single machine in the Google Cloud with 4 TPUs (AlphaGo Zero could also be distributed but we chose to use the simplest possible search algorithm)."
Stunning.
Genetic algorithms were used to evolve new, more efficient variants of existing electronic circuits. I dug it up - it was: https://www.scientificamerican.com/magazine/sa/2003/02-01/#a... Article "Evolving inventions". I have no idea if there is an open-access version anywhere.
As far as I remember, that approach led to some patents, because some of the inventions were better than existing solutions. One of the examples in the article was a low-pass filter (I dont remember if AI version was actually better or worse than human-made).
The essential element of this approach was that in electronics (as in go) there exist a well defined set of rules, that allows researchers to build a simulation engine with optimization/evaluation function that the AI targets by itself, without supervision. It's great to see that this approach is still alive, although in my humble opinion, application in electronics is much more interesting than Go.
The other SA article on this was The Darwin Chip which I think went into more detail.
One of the limitations was the lack of documentation for the actual bitstream.
https://www.nature.com/scientificamerican/journal/v288/n2/pd...
I'm surprised they're able to prevent a self-play equilibrium with such a simple loss function.
It's sort of like they are using auxiliary outputs but instead of using them to fit features, they are fitting to multiple ways of arriving at 'best play', through predicting value (SL) and predicting probability for best outcome (RL). In principle, they're doing the same thing but in practice it seems like they are making up for each others shortcomings (e.g. self-play equilibrium with RL).
Protein folding sounds like a nice idea for their next challenge.
The networks are great at perception and snap-prediction. Anything a human can do in 200ms is fair game. And with clever engineering, we can make magic happen by iterating or integrating those things.
But it's after that first 200ms that humans get really intelligent. When we can come up with an architecture that lets the networks themselves start simulating possibilities, backtracking, deciding when to answer now or to think more -- when the network owns the loop -- then it will get interesting.
Not guaranteed. The human brain has diffusion signalling (i.e. neurotransmitters passing out of the synaptic cleft, into a neighbouring one, and activating a receptor on some other spacially-local axon as a result.) And one of those signalling molecules is thought to represent, in its intensity, a confidence-interval bias adjustment (i.e. a pruning bias factor for MCTS.) So the brain's MCTS-equivalent process may rely on some extra-graphical properties of the brain-as-embodied-meat-thing.
Also, these signals pile up in the synaptic cleft until they’re picked up, so it’s not just about instantaneous transmissivity as if these were radio signals.
But also also, other stuff like monoamine oxidase is floating about in its own diffusion patterns, cleaning up these signals.
It’s basically like a “scent” communication embodied-actor model, but a very complex one where things like redox reactions with the atmosphere occur.
Oh, and there are “secondary messengers”: signals that trigger other signals that, among other things, inhibit the release of the original signal when received back at the sender, such that an dynamic equilibrium state is reached between the two signal types.
It's very interesting to see if it is able to handle much more advanced and tuned engines that exist for chess, game with considerable much more complicated rules?
And chess, while it does have more complex base rules, has a much lower combinatorial complexity than Go.
The problem with the current chess bots is that they play badly, badly. They choose a terrible random mistake to make every few moves, while some of their other moves are brilliant. They cannot accurately mimic beginner or intermediate level players.
I wouldn't bet on it though. SMP is notoriously hard to work with alpha-beta search and there are a lot of clever tricks (which is probably still not perfect). Maybe with ASICs, you could make it stronger, but then it wouldn't be as fair a comparison.
I'm talking about something similar to the described in the paper, 100% self-learned solution without using human heuristics, based on NNs. That could bring a totally new ideas into chess.
But shogi is much more obscure outside of Japan than go or chess, so it gets less interest, especially in the large-board variants.
But maybe not sexy enough, or we just don't hear about it as much.
Giraffe attempted this (with more standard tree search than MCTS and with only a value function rather than a combined policy/value network), but only reached IM level -- certainly impressive, but nowhere close to Stockfish.
Minimax with Alpha Beta pruning works in Chess because the search tree is way smaller. The reason why all this "Monte-Carlo Tree Search + Neural Nets" are being used in Go because Minimax + Alpha Beta pruning DOESN'T work in Go.
Your rating: 3664
Opponent's rating: 5000
Probability of winning: 0.000456879355457417
So 1 in 2,200 games... ouch
Lee Sedol's single victory is the first and the last.
Alpha particles can flip bits and cause erratic behavior, can they not?
"[The probability of] at least one bit error in 4 gigabytes of memory at sea level on planet Earth in 72 hours is over 95%"
EDIT: From the paper: "Surprisingly, shicho (“ladder” capture sequences that may span the whole board) – one of the first elements of Go knowledge learned by humans – were only understood by AlphaGo Zero much later in training" I'm surprised by the author's use of the word "Surprisingly" here.
[0] https://www.nature.com/nature/journal/v550/n7676/full/nature...
That represents a strong assumption about locality in the network design. I would expect AlphaGo to perform poorly on the game "Go with the vertices randomly permuted".
That means that this setup isn't necessarily general. How applicable is MCTS to games with asymmetric information, a la Starcraft? What about games that can't quite be modeled with an alternating turn-based game tree like bughouse?
"We’re not ready to talk about agent internals"
What makes you think it uses a tree search?
The problem is that there's no intrinsic scoring system for Go, nothing specific to maximize, so it's difficult to tell a computer whether a given outcome is "good" or "bad". So early versions of AlphaGo used a collection of human-played Go games to get an idea of what constitutes "good" and what is "bad", so it can then train its model to predict whether a move will make things better or worse.
This new system forgoes that step, and instead has the model play itself starting at random and looking for patterns that end up winning games. It's as if you gave the rules to the game of Go to a culture that's never heard of it before, and they evolved their own play style entirely in isolation.
Their result is a model that is better than the one that was developed with human influence, and that's the interesting bit.
Train a network which predicts future state of the game, given current state and input. Train a network which generates sensible inputs, given current state. Use MCTS.
To see why this is important, consider why min-max (which MCTS approximates) actually works. At any given point, the equilibrium strategy for the player to move is the move that maximizes their payoff, and the utility for each move can be found recursively.
In simultaneous decision games, calculating the equilibrium strategy (which may even be a mixed strategy) is more complicated. See http://mlanctot.info/files/papers/cig14-smmctsggp.pdf for various ways in which MCTS can be extended to simultaneous-decision games.
It'll be interesting to see if DeepMind picks up a search algorithm someone else has researched, or if they come up with something entirely new.
It's interesting how NN will be able to deal with uncertainty of enemy's state and moves.
“What are you doing?”, asked Minsky.
“I am training a randomly wired neural net to play Tic-Tac-Toe” Sussman replied.
“Why is the net wired randomly?”, asked Minsky.
“I do not want it to have any preconceptions of how to play”, Sussman said.
Minsky then shut his eyes.
“Why do you close your eyes?”, Sussman asked his teacher.
“So that the room will be empty.”
At that moment, Sussman was enlightened.
[1]. https://en.wikipedia.org/wiki/Havannah#Computer_Havannah
[2]. https://news.yale.edu/1999/06/01/successor-chess-new-game-st...
As Rodney Brooks pointed out, all technology happens within a context, not a vacuum. A general AI will come to exist in a world with a lot of other superhuman capabilities already in existence.
This is getting rather creepy to think of, even if it's still science fiction. At this point, I could see a computer that out-thinks humanity within decades. What would it think? What would we even do with its findings? Would we understand it? Would it understand itself? Would it know how to manipulate us?
If you multiply X by the amount of time it takes, on average, for a human to make a move... How many human lifetimes did Zero take to get to superhuman?
With the mass surveillance that is Google it's quite doable to test for human reactions on certain things. They got the tools to execute a certain plan and evaluate the effectiveness. Ofcourse it can also go in a benelovent way: like what kind of policy will benefit the most people? (semantics of 'benefiting' aside)
I atleast certainly hope these kinds of generic algorithms will be used to generate effective, meaningful policies that truly help the people. Still a far away future but one that gets closer by the day.
If we keep the board and pieces digital, then the board could change shape, the pieces could change color indicating a random association with a rule change, and what not.
It's more difficult to see how Go playing skills can translate to other domains. But for tasks in robotics, cybersecurity or fintech the power of self-play trained transfer learning becomes more apparent.
My bet is that simulation is going to be the crowning jewel in the AI field, replacing static datasets and supervised learning with "dynamic datasets" and rewards. It would help with data sparsity as well (where can you find an image of a donkey riding an elephant for the new ImageNet? - but you can sim that or any possible combination).
Not to mention that humans are fallen head over heels with simulation as well - VR headsets and games in general. I see a great future for simulation with both AI and humans. It will be our common learning/playing/research sandbox.
https://www.youtube.com/playlist?list=PLzuuYNsE1EZAXYR4FJ75j...
This sound super generic, so yes.
- a perfect information game
- with a relatively small input size (vs. arbitrary computer vision)
- cheap to simulate
- discrete action space
- deterministic
This isn't to take away from the magnitude of the achievement, but the nature of the problem itself makes the result less applicable to many tasks we might want to use RL for.
Without that, it is simply a tree search.
Excerpt from the paper:
> [AlphaGo Zero] uses a simpler tree search that relies upon this single neural network to evaluate positions and sample moves, without performing any Monte-Carlo rollouts.
This was... unexpectedly good.
It effectively reduces the branching factor of Go from the number of moves available, to the number of moves actually worth considering.
I might have missed this, but: Where are the actual rules of Go encoded? Mustn't there be some enumeration of what constitutes "capturing," how the win condition of the game is calculated, correct?
To start with "less than zero", though, it would be interesting to see them give the AI a 3D simulation of a room with a simulated Go board and a simulated stone, and give the AI a fixed amount of time for it to have its turn. Just by using the pixel data from a simulated camera, it could learn to use a simulated arm to place the simulated stone on the board in a legal position. The reward function would just have to say, at the end of each allotted time period, whether a legal move had been made or not, and the AI could bootstrap up from that.
By nothing they mean hints about what constitutes "good Go strategy". But it implicitly knows all of the rules of go.
I wouldn't discount it entirely though, some sort of clustering of actions may be able to reduce continuous action spaces to a manageable branching factor.
AFAIK the 2016 Nature paper is Alpha Go Lee. And now we skipped to AlphaGo Zero.
We built damn good boats, even before we knew anything formal about fluid dynamics, or even AIR.
Last time this was brought up, someone implied it's closed source so as not to boost the Chinese competitor.
https://www.blog.google/topics/google-cloud/google-cloud-off...