I did not see Alpha Go's invasion of the top left corner coming.
The black group consisting of 3 stones (B13, C12, E12) did not seem alive at first, but it turned out to not only live but completely reduce white's corner.
The underlying technology is far more general than than you think. In addition to playing Go, it has already been used to play video games[1], diagnose diseases[2], and make Google's datacenters more efficient.[3]
In each case with lots of manual tweaking to get the best performance. Deep learning is not magic; you need to find the right kind of architecture for your problem, and that requires prior knowledge. Humans will still be in the loop for at least the next decade or so.
'Humans' are fucked one way or another. We were always fucked. Our parents and grandparents were always fucked. Did you expect to live forever? The future will contain our children, and they will be better in each and every way.
And they won't be human.
The main concern is data efficiency. AlphaGo essentially baked good movies into value and policy network by playing millions of times. In reality, unless you have a really good simulator, deep reinforcement learning is almost never applicable.
'data efficiency' -- that's a good candidate for the next buzz imo. People talk a lot about how massive amounts of data regressed over giant networks of dumb functions happens to perform well on many tests, but they ignore the fact that the performance of the system is sick. It fails if you tweak the input by small amounts that would never confuse a human. You shouldn't NEED that much data. You need better priors. Current ML systems rely on arbitrary coincidences to succeed at multiple choice tests. I did that in courses I didn't go to class. They are primitive and childish and won't scale with pure data/processing. We are still missing something.
Humans develop prior by accumulating experiences. Laws of physics are discovered through experimentation and introspection over many data points.
So what we really need is a life-long learner - a machine learning algorithm that could extract knowledge from many tasks and store that in its long-term memory. The fact that we don't have an architecture for long-term memory is the main road blocker towards this goal.
There are a lot of problems for which you effectively have limitless data.
For example, optimizing the shape of an aerofoil, wing, wind turbine, ship, pump, etc. The "real" data is the result of computationally costly fluid dynamics simulations. The network uses as much of those as it likes to modify the design to be better.
There are also a lot of problems where there is nearly limitless data (ie. > 10^12 bytes of data). Examples would be MRI/CT scans, all internet video, all TV channels, etc.
>There are a lot of problems for which you effectively have limitless data.
>For example, optimizing the shape of an aerofoil, wing, wind turbine, ship, pump, etc. The "real" data is the result of computationally costly fluid dynamics simulations.
I'm doing something similar at the moment. The data is not limitless. It's in fact quite expensive.
In most cases you still need to generate the large number of simulations in your training set, and the simulations are computationally expensive to do. If you're doing it on a metered platform you can tie the cost of the data set directly to the number of cpu hours need to generate it, and from there to a dollar value.
You can view there being 5 dimensions/concerns with large scaling factors containing issues needing solving to be generally applicable.
1. How to search
2. How to resolve breadth concerns
3. How to resolve depth concerns
4. How to resolve large training requirements
5. How to form and resolve recursive goals
With AlphaGo, it looks like they may have solved 3
1. Search. Monte Carlo will likely be used from here on out. Much more efficient than full brute force search (chess style).
2. Breadth - Policy network. Reduced branching factor from 250 to between 5 and 10.
3. Depth - Value network reduced depth from roughly 75 to < 20
Next they're working on applying reinforcement learning to their two NNs. Ie seeing if they can optimize how well they can do and how quickly they can learn. Maybe there are large gains there.
If so, the final task would be finding a game or situation that required nesting of sub-goals like everyday life does.
They've made some impressive gains.
> In reality, unless you have a really good simulator, deep reinforcement learning is almost never applicable.
I could see Deep Mind applying this to something like catching a ball in the near future. Just to show it's generality. It's not that different of a problem space than learning to play breakout.
Chess AI does not use brute force search. It evaluates board positions with heuristics (eg. pieces captured, blocked pawns, possibility of castling, etc.), and uses the estimated chance of winning to prune the search tree with techniques such as alpha-beta pruning[0].
Both board evaluation and tree pruning are more difficult in Go. In Chess, capturing material is very important, but capturing stones in Go is often useless because the stones are in a bad position ("dead"). You can't decide who's winning just by counting captures. It's very difficult to hand code a board evaluation function, but AlphaGo's neural network solved the problem.
However, the neural network alone, with no tree search, was only enough to reach strong amateur level. Unlike Chess, where moves usually have consequences in the near future, a move in Go can be important tens or even hundreds of moves later. Alpha-beta pruning doesn't handle very distant consequences well, but Monte Carlo tree search does much better. Combined with the neural network it was enough to beat humans.
Minmax as used in chess is nothing more than a Depth First Search constrained within the space of moves of agents acting in their own self interest. It searches the maximum number of plies it can (you can think of a ply as a move by a single player in chess[0]) within the time & memory it has allowed.
This approach is brute forcing the search space restricted by computational limits. Alpha-Beta is just an optimization to minmax and not a fundamental change in the search approach.
Chess and Go are very different games and need to be treated as such. Lots of the recent excitement about Go is due to the innovations in machine learning and specifically deep learning that have been discovered. Particularly their performance on such a complex game - significantly more complex than chess. It was predicted that Go wouldn't be able to match top strength professionals for another 5 to 10 years.
AlphaGo Played Lee Sedol last year (considered one of the top players of the past decade) and won.[1] AlphaGo beating this prediction by so much was a large part of the excitement for last year's event.
The reason for the excitement was demonstrating that Monte Carlo search, which was originally dismissed as inferior, was a significantly better approach for the game of Go. Monte Carlo is a probabilistic based approach that uses random sampling - this is very different from the DFS approach used in chess.[2] It has proven be to very effective and without another breakthrough will almost certainly be the option used going forward.
DeepMind claims that AlphaGo has already paid for itself when it was used to cut Google’s data center cooling costs, so it is not infeasible there may be many other domains which may benefit.
It has been cited in a number articles quoting Demis Hassabis; Hassabis repeated the claim in his recent talk on AG (specifically, that deep RL related to AlphaGo has reduced Google datacenter cooling costs by 40% and is saving Google hundreds of millions of dollars a year) and added in the additional interesting detail that Google has changed its datacenter design plans to add in additional sensors & controls for the deep RL agents.
They haven't gone into detail as to how exactly this is done, but my guess is that they use their historical data series on cooling/electricity consumption to bootstrap and then it learns online normally with policy gradients (since cooling and temperature control seem like something with continuous actions rather than a few discrete ones, so an actor-critic rather than DQN).
If you look more closely at the details here (beyond just deepminds blog post) you'll see that
1. It has not yet been deployed to all data centers. They just turned the system off for a period of time and looked at how much extra money it cost to run the data center like that, then extrapolated.
2. There was already a Google engineer back in 2012 who applied neural networks to this problem and saw huge gains (There is a blog post about this somewhere). In the deepmind blog post, they don't compare to this system, do for all we know it could just be a small refinement of that system. It is actually not clear whether deep RL was actually used or not from the deepminds blog post: it is only kind of implied.
> If you look more closely at the details here (beyond just deepminds blog post)
Where would that be? As far as I know, the DM blog post and Hassabis's occasional discussions are the most detailed public information available. And they don't mention that it's just a brief demo.
> 2. There was already a Google engineer back in 2012 who applied neural networks to this problem and saw huge gains (There is a blog post about this somewhere)
So, that was 2 years deeper into the deep learning revolution, post-DeepMind acquisition, doesn't actually say it was a NN (the diagram could be literally any ML model from linear model to random forest), doesn't say they reduced costs by anything approaching 40%, or even are using it in production at all aside from the one instance they patched around some downtime.
"Today we’re releasing a white paper (PDF) on how we’re using neural networks to optimize data center operations and drive our energy use to new lows."
Ah, missed that. In any case, the paper confirms what I said: they haven't used it in practice, and the only time they have was the brief one mentioned in the post where it resulted in a small PUE saving (it quotes 0.02, off an unspecified reduced load but note for comparison the average PUE of ~1.12, so saving anything remotely like 40% is unlikely).
Here is a followup from the same lead author of the paper referred to in that first blog post (Jim Gao) who apparently was involved in Deepmind's project. Note the conspicuous lack of any sort of reference to deep reinforcement learning
Using forecasting for 'control' doesn't make too much sense (why the need to train a second ensemble to prevent overshoot if it's just supervised learning?), and the first author on that post, is not Gao but Richard Evans who is a DeepMind deep RL researcher (most recent publications: "Deep Reinforcement Learning in Large Discrete Action Spaces", "Deep Reinforcement Learning with Attention for Slate Markov Decision Processes with High-Dimensional States and Actions", "Reinforcement Learning in a Neurally Controlled Robot Using Dopamine Modulated STDP").
"Say you’re a data center architect working at Google. It’s your job to make sure everything runs efficiently and coolly. To date, you’ve achieved that by designing the system so that you’re running as few pieces of cooling equipment at once as possible — you turn on the second piece only after the first is maxed out, and so on. This makes sense, right? Well, a variant of AlphaGo named Dr. Data disagreed.
“What Dr. Data decided to do was actually turn on as many units as possible and run them at a very low level,” Hassabis says. “Because of the switching and the pumps and the other things, that turned out to be better — and I think they’re now taking that into new data center designs, potentially. They’re taking some of those ideas and reincorporating them into the new designs, which obviously the AI system can’t do. So the human designers are looking at what the AlphaGo variant was doing, and then that’s informing their next decisions.” Dr. Data is at work right now in Google’s data centers, saving the company 40 percent in electricity required for cooling and resulting in 15 percent overall less energy usage."
At the very least I think this is deceptive because the source (If you keep clicking on links) for the 40 percent savings is the original blog post, and there's no other information saying things have been rolled out fully, yet the Verge is seems to imply that here.
I am somewhat convinced that something resembling RL was used based on your argument in the other thread, but I think even you would agree that calling it "a variant of alphago" is a pretty big stretch.
I can believe "deep RL related to AlphaGo" but that was somehow transmuted to "[AlphaGo] was used to cut Google’s data center cooling costs", which doesn't make sense.
> AlphaGo essentially baked good movies into value and policy network by playing millions of times.
I don't think that's a very good description of how AlphaGo was trained at all; you're essentially saying it merely overfits the training set, yet it clearly generalizes rather well to unseen board situations and still evaluates them sucessfully. No machine learning system would be found usefull if all it could do is merely memorize the training data.
Re the use of deep reinforcement learning, well for one the role of reinforcement learning in the first version of AlphaGo, the one described in the Nature paper was rather limited, and a small part of its training; it just made a ~3d KGS policy network into a ~5d KGS bot, and used to generate a training sample for the value net. If we had enough recorded human games to train the value net directly, that'd be an unnecessary step anyhow. And you could create such a training set w/o reinforcement learning since there are pure monte carlo bots stronger than 5d KGS - but that'd be far more computationally expensive.
But its still not really true that there aren't obvious applications of deep reinforcement learning - indeed robotics is one promising application, and that seems rather relevant. this paper initially demonstrated an impressive improvement in manipulative tasks, and you can prob follow its numerous citations for newer stuff: http://arxiv.org/abs/1504.00702
I do agree that this exact architecture in AlphaGo prob doesn't have applications beyond just teaching us how to play go better; it seems too specialized. I believe they mean it in just the vaguest possible sense; that the kind of deep algorithms demonstrating incredible performance in AlphaGo have diverse applications; but this should not come as a surprise to anyone even loosely following what people have done with deep learning in the past couple of years anyhow.
I'm a huge proponent of alpha Go and I think it is a revolutionary leap.
The key I think is,
> yet it clearly generalizes rather well to unseen board situations and still evaluates them sucessfully
I'm not sure this has been proven to be meaningful in a general sense, as you seem to also imply. Extrapolation can be a tricky answer subtle business. What about unusual board sizes, for which no training data exists? Or if you changed a rule? I'm sure deepmind would say the adversarial approach would work for these cases, but I'm not sure it would. Would be very interesting to see if humans could 'learn' a new state more quickly than the algorithm.
That might provide a hint that the algorithm is 'just' fitting the data well (with appropriate baked in regularization, of course). Or if it can more generally 'learn' given system rules.
Hm, well you are no doubt right that it doesn't generalize well to a change of rules. Reminds me of that game DeepZen played. It was trained with a komi of 7.5 and it played too soft and lost when in the actual match komi was 6.5 (or maybe it was the other way around?). A human does not have much trouble adapting to such small rules variations, but at least the version of DeepZen that played that match was hard-coded for that exact komi value, because that's what what used in all of its training examples, and wasn't given as a parameter. It shouldn't be a hard limit of the approach - indeed I think AyaMC was said to have been trained with some flexibility in its komi.
Still, I think AlphaGo does demonstrate amazing positional judgement in unseen board states, and that this is visible in the details of how it plays out particular situations. No two games are exactly alike - difficulty of go for computers is precisely in its extreme combinatorial explosion - and in particular tactical situations every detail of the situation matters. Yet you can see AlphaGo judging the correct sequences of moves, "knowing" how to make a particular group alive for eg, even when a particular other move seems more natural. And probably the most amazing thing about how it plays is how early it becomes completely sure that its got an advantage on the board, and how precisely it judges how much it needs to keep the advantage to the end. Every detail of the board is again relevant here, and basically no human would be so confident so soon. A go bot that couldn't adapt its tactics to unseen situation would be easy to beat; just ensnare it in a large complicated fight, and you're going to kill a big group and guarantee a win. Ofc people tried this in some masterP games, and turns out AlphaGo is tactically just as strong.
So, its basically like with other generalizations you can get from machine learning; a net trained on say ImageNet will generalize to different poses, occlusions, contexts and variations of objects similar to what it was exposed in training etc and still do a superhuman job of classifying such pictures, but will naturally be quite hopeless with completely unseen items. So too AlphaGo seems to know the game of go, generalizing from seen examples to correct judgements in other states, but would be quite hopeless if tested on even a slight variation of the game rules.
Go works precisely because it is a small closed system. An interesting match (from an AI perspective) would be a pro playing alphago on an unusual board (eg, one in the shape of a cat). The pro would take everything he knows about the game and apply it to the odd situation. Alphago is so specifically tuned that it cannot even handle any case except 19x19 (and maybe 9x9). Another interesting question would be small rules changes like "you may not play on any star points or any point directly touching them until turn 30".
Go has deep strategy, but it is very well defined in terms of what can and cannot be done and those rules are not particularly complex. Power grids in contrast are far more complex. There are thousands of rules, but also many more thousands of unwritten assumptions and case-by-case analysis. A final issue is that there exist unsolved and unrecognized problems.
The last AI winter (deep learning is just the latest rebrand) came from researchers overstating their accomplishments and making promises about general intelligence that could not be kept. Any claim about anything that requires general intelligence in the near future is undoubtedly overpromising.
> Alphago is so specifically tuned that it cannot even handle any case except 19x19 (and maybe 9x9).
Do you have any sources to back this assertion? It sounds unintuitive as I know object recognition sytema are usually trained on small images but they generalize well to arbitrary image sizes. What you are describing sounds like overfitting.
The paper itself repeatedly says that all 48 layers of the policy network are 19x19 matrices. To make the point though, they initially train alphago using actual games. After a hundred thousand or so training games, it's finally ready to start playing and learning. There are less than a couple dozen recorded games on larger boards.
If you haven't played go very much, you may thing that "it's just a bigger board". 19x19 is commonly used because it has an even balance of edge and center influence (in reality, edge influence seems to be slightly higher). With the 13x13, corner plays have overwhelming influence in the center. At 9x9, there is basically no center strategy at all. Normal strategies starting in the corners and expanding influence toward the center don't work as effectively with larger boards (the larger the board, the more this becomes true).
This is a much different issue than image recognition in that strategy doesn't scale in the same way that images do.
I wonder what would be the result if the rules of the game were tweaked slightly (in an arbitrary fashion) just before a game, then the match went ahead as before. My guess would be Ke Jie would be fine and would adapt fairly quickly and AlphaGo would look pretty bad.
I think the AI/human crossover boundaries are at meta boundaries. As we get more meta, humans do better over AI. AI has been eating up the lower meta levels for some time now. It has been a very long time since a human could do division faster than a computer.
The question is how far does this meta staircase ascend, and if/when will AI climb all the way to the top?
You can make huge fundamental changes like "you cannot connect 3 stones in a row" or you cannot make a certain shape with your stones. There are 'bad' shapes in go that you learn when you're young that almost never surface in higher levels of play (of course you would make a non-bad shape illegal). You can say every 15 turns you get 2 moves in a row and they are stagged (this is game-breaking). You can ban certain josekis ('standard moves' early in the game). You can make each captured stone worth 2 points instead of 1.
Every move, you flip 6 coins. If all 6 come up as heads, you swap seats and colors with your opponent.
This means that an advantageous board position is much less important, and it will be in both players favour to keep the board position very near evenly matched.
Not always. A player that thinks he will lose a game that's tied in the last 8-ish moves will have an incentive to create a highly unbalanced game. That way, that player gets a 50% chance of winning.
Given that there's only one flip left and you need 6 heads, he has a 1/2^6 or 1/64 chance to win.
In go the last 8 moves is almost never going to make the difference (the last 20-40 moves in a game that doesn't end in resignation there are almost no mistakes in pro games).
It's not general AI, no one said it was. It's similarly not going to play checkers at the drop of a hat like KJ could.
The thought experiment a little more refined, like alphago programmers get time to implement only validMoves() and makeMove() then let the same learning process go on it, I wouldn't count it out. If you only flip the switch once the new game variant starts, before a human has even begun to take an action the computer will have played out thousands if not millions of games using MCTS and slowly training up its networks in real time instead of using a static one. As the game progresses the bot should only get better and better.
sounds like General Game Playing task. Well, MCTS alone is often used in that domain, and it wouldn't surprise me if Ke Jie was a weaker checkers player than just a brute MCTS, nevermind any attempts to use neural nets (if that would even make sense for checkers?)
Two approaches used by the previous version of AlphaGo (MCTS and a NN for position evaluation) have been tried in the past in computer chess with relatively poor results, while in the past few years they were already giving good results for Go.
The current version might be using some different techniques that could be more useful, though. They should release some details in the next few weeks.
Can't they effectively "solve" chess with the power of AlphaGo? Someone posted on the last thread that the AI plays one game of go every 2 seconds against itself to train (that's ~150 moves/second). Wouldn't chess be solved for all combinations in a matter of days?
AlphaGo's strength is in choosing which moves to consider. Solving a game means considering every move (up to alpha-beta pruning) -- AlphaGo's techniques don't help with this.
Short answer is no. One estimate says there are 10^120th possible chess games. I'm not doing the math now, but I believe that falls into the not-physically possible within our lifetime using known physics.
An "If you had started calculating at the beginning of the universe, you wouldn't have even tackled a sliver of the work by now" type of problems.
What I mean by solving "every" move is that the AI would be able to determine which trees are a "losing" state and not continue, removing well over 99% (or 99.999% I don't know) of the possible games. I guess maybe solve is not the correct answer but something like 99% presumption on the best or best 3 moves.
In both games, AIs find moves by way of a search tree that looks at the possible moves and looks for one leading to a win (see e.g. https://en.wikipedia.org/wiki/Minimax ). Since testing all possible moves (i.e. an exhaustive search) is infeasible, to be practical they instead use heuristics to decide the value of a given state of the game, so they don't have to search all the way to a win or loss every time. So the core of this is a good heuristic function to evaluate board states to guide the search (although in addition, a lot of the work that was done on chess AIs previously was about pruning the search tree so bad lines of search could be abandoned more quickly). I'm not sure what the state of the art is for this in chess, but one of the innovations of AlphaGo was to train a deep convolution network with data from millions of games with their board states and those games' eventual outcomes and thus creating an evaluation function (the 'goodness' of a state is its likelihood to lead to an eventual win). This may or may not be able to also improve chess AIs, depending on how close to 'perfect' the current best-of-breed heuristic is - someone else would have to chime in on this.
The other big improvement from AlphaGo was using another deep convolution network trained on moves from all those games to create an 'expand' function. Unlike chess, the branching factor of that search tree in Go is ridiculously high, because you can place a stone pretty much anywhere on a big board, while in chess the set of legal moves at any given time is fairly limited. So that neural network they use as an expand function allows them to prioritize the order in which moves are considered. This innovation isn't necessary for chess as the branching factor is much lower - but it might still provide an input for the prioritizing the order in which moves are evaluated.
After learning how all this worked, I understand why Deepmind themselves seem more impressed with their Atari AI, as it actually learned how to play the game from first principles by just looking at the pixels and being told its score, whereas, the approach above, impressive as it is, still actually just plugs the neural networks into existing algorithms, rather than use them for the core decision making process too.
I don't think it will necessarily be as good at chess, because chess has a much smaller search space. So "stupider" methods can actually work, while Go requires very good pattern recognition to prune the search space.
I was impressed when this happened last year. Funny how all the AI fear mongering was the same back then. But a year later the result is just driving a car poorly around a GTA map. Oh and AlphaGo still winning Go matches. Scary indeed.
When Ke Jie says : "I also thought I was very close to winning the game in the middle but maybe that’s not what AlphaGo was thinking". Do we know what AlphaGo was thinking ?
From what I've heard AlphaGo does maintain an estimate of what its odds of winning are at any given point in the game. Not sure if anyone from DeepMind has released any of that data from game 2 though.
The problem with professional dan ranks is that they're capped at 9p, and each association has different rules for awarding that rank. Because of this there is a lot of variance among 9p.
For instance, Fernando Aguilar 6d (aguilar1 and aguilar on KGS), an amateur dan from Argentina, has defeated Hasegawa Sunao 9p as well as Yo Kagen 9p. In theory this should not have happened.
If the cap didn't exist, I think Alpha Go may be around 13p, based on the fact that Lee Sedol and Ke Jie may be able to give reverse komi to many top 9p players, and that Alpha Go may be about 3 stones stronger than both. Park Yeong-hun is less often mentioned but he may be playing at a higher level to that of Lee Sedol.
I don't know Fernando Aguilar but is the reason he's 6D not that he's capped at it before becoming professional? IIRC when I played in SF bay area (probably all of USA in the AGA), you couldn't get higher than 6D(7D?) without becoming a pro. I think in tournament lineup you would see something like Mr. A 6D (7.2) where the 7.2 was his estimated rating but it was a long time ago.
Not entirely sure about caps at the amateur level. At least go servers don't have such cap, and there's certain mapping between KGS ranks to offline amateur ranks. The highest attainable rank at Go servers is 9d, aguilar is 6d there.
71 comments
[ 4.2 ms ] story [ 132 ms ] threadThe black group consisting of 3 stones (B13, C12, E12) did not seem alive at first, but it turned out to not only live but completely reduce white's corner.
1. https://deepmind.com/blog/enabling-continual-learning-in-neu...
2. https://deepmind.com/applied/deepmind-health/
3. https://deepmind.com/blog/deepmind-ai-reduces-google-data-ce...
Reassuring. Really.
However, I am not buying the claim that the algorithm is going to transform many other domains:
" The system could help optimize power grids, he says, or streamline shipping routes, or refine scientific research."
by Wired https://www.wired.com/2017/05/googles-alphago-levels-board-g...
The main concern is data efficiency. AlphaGo essentially baked good movies into value and policy network by playing millions of times. In reality, unless you have a really good simulator, deep reinforcement learning is almost never applicable.
Humans develop prior by accumulating experiences. Laws of physics are discovered through experimentation and introspection over many data points.
So what we really need is a life-long learner - a machine learning algorithm that could extract knowledge from many tasks and store that in its long-term memory. The fact that we don't have an architecture for long-term memory is the main road blocker towards this goal.
For example, optimizing the shape of an aerofoil, wing, wind turbine, ship, pump, etc. The "real" data is the result of computationally costly fluid dynamics simulations. The network uses as much of those as it likes to modify the design to be better.
There are also a lot of problems where there is nearly limitless data (ie. > 10^12 bytes of data). Examples would be MRI/CT scans, all internet video, all TV channels, etc.
>For example, optimizing the shape of an aerofoil, wing, wind turbine, ship, pump, etc. The "real" data is the result of computationally costly fluid dynamics simulations.
I'm doing something similar at the moment. The data is not limitless. It's in fact quite expensive.
In most cases you still need to generate the large number of simulations in your training set, and the simulations are computationally expensive to do. If you're doing it on a metered platform you can tie the cost of the data set directly to the number of cpu hours need to generate it, and from there to a dollar value.
1. How to search 2. How to resolve breadth concerns 3. How to resolve depth concerns 4. How to resolve large training requirements 5. How to form and resolve recursive goals
With AlphaGo, it looks like they may have solved 3
1. Search. Monte Carlo will likely be used from here on out. Much more efficient than full brute force search (chess style). 2. Breadth - Policy network. Reduced branching factor from 250 to between 5 and 10. 3. Depth - Value network reduced depth from roughly 75 to < 20
Next they're working on applying reinforcement learning to their two NNs. Ie seeing if they can optimize how well they can do and how quickly they can learn. Maybe there are large gains there.
If so, the final task would be finding a game or situation that required nesting of sub-goals like everyday life does.
They've made some impressive gains.
> In reality, unless you have a really good simulator, deep reinforcement learning is almost never applicable.
I could see Deep Mind applying this to something like catching a ball in the near future. Just to show it's generality. It's not that different of a problem space than learning to play breakout.
Both board evaluation and tree pruning are more difficult in Go. In Chess, capturing material is very important, but capturing stones in Go is often useless because the stones are in a bad position ("dead"). You can't decide who's winning just by counting captures. It's very difficult to hand code a board evaluation function, but AlphaGo's neural network solved the problem.
However, the neural network alone, with no tree search, was only enough to reach strong amateur level. Unlike Chess, where moves usually have consequences in the near future, a move in Go can be important tens or even hundreds of moves later. Alpha-beta pruning doesn't handle very distant consequences well, but Monte Carlo tree search does much better. Combined with the neural network it was enough to beat humans.
[0] https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning
This approach is brute forcing the search space restricted by computational limits. Alpha-Beta is just an optimization to minmax and not a fundamental change in the search approach.
Chess and Go are very different games and need to be treated as such. Lots of the recent excitement about Go is due to the innovations in machine learning and specifically deep learning that have been discovered. Particularly their performance on such a complex game - significantly more complex than chess. It was predicted that Go wouldn't be able to match top strength professionals for another 5 to 10 years.
AlphaGo Played Lee Sedol last year (considered one of the top players of the past decade) and won.[1] AlphaGo beating this prediction by so much was a large part of the excitement for last year's event.
The reason for the excitement was demonstrating that Monte Carlo search, which was originally dismissed as inferior, was a significantly better approach for the game of Go. Monte Carlo is a probabilistic based approach that uses random sampling - this is very different from the DFS approach used in chess.[2] It has proven be to very effective and without another breakthrough will almost certainly be the option used going forward.
[0] - https://en.wikipedia.org/wiki/AlphaGo_versus_Lee_Sedol
[1] - https://en.wikipedia.org/wiki/Ply_(game_theory)
[2] - https://en.wikipedia.org/wiki/Monte_Carlo_method
They haven't gone into detail as to how exactly this is done, but my guess is that they use their historical data series on cooling/electricity consumption to bootstrap and then it learns online normally with policy gradients (since cooling and temperature control seem like something with continuous actions rather than a few discrete ones, so an actor-critic rather than DQN).
2. There was already a Google engineer back in 2012 who applied neural networks to this problem and saw huge gains (There is a blog post about this somewhere). In the deepmind blog post, they don't compare to this system, do for all we know it could just be a small refinement of that system. It is actually not clear whether deep RL was actually used or not from the deepminds blog post: it is only kind of implied.
Where would that be? As far as I know, the DM blog post and Hassabis's occasional discussions are the most detailed public information available. And they don't mention that it's just a brief demo.
> 2. There was already a Google engineer back in 2012 who applied neural networks to this problem and saw huge gains (There is a blog post about this somewhere)
I don't remember this.
https://blog.google/topics/environment/deepmind-ai-reduces-e...
"Say you’re a data center architect working at Google. It’s your job to make sure everything runs efficiently and coolly. To date, you’ve achieved that by designing the system so that you’re running as few pieces of cooling equipment at once as possible — you turn on the second piece only after the first is maxed out, and so on. This makes sense, right? Well, a variant of AlphaGo named Dr. Data disagreed.
“What Dr. Data decided to do was actually turn on as many units as possible and run them at a very low level,” Hassabis says. “Because of the switching and the pumps and the other things, that turned out to be better — and I think they’re now taking that into new data center designs, potentially. They’re taking some of those ideas and reincorporating them into the new designs, which obviously the AI system can’t do. So the human designers are looking at what the AlphaGo variant was doing, and then that’s informing their next decisions.” Dr. Data is at work right now in Google’s data centers, saving the company 40 percent in electricity required for cooling and resulting in 15 percent overall less energy usage."
I am somewhat convinced that something resembling RL was used based on your argument in the other thread, but I think even you would agree that calling it "a variant of alphago" is a pretty big stretch.
(Just nitpicking here.)
I don't think that's a very good description of how AlphaGo was trained at all; you're essentially saying it merely overfits the training set, yet it clearly generalizes rather well to unseen board situations and still evaluates them sucessfully. No machine learning system would be found usefull if all it could do is merely memorize the training data.
Re the use of deep reinforcement learning, well for one the role of reinforcement learning in the first version of AlphaGo, the one described in the Nature paper was rather limited, and a small part of its training; it just made a ~3d KGS policy network into a ~5d KGS bot, and used to generate a training sample for the value net. If we had enough recorded human games to train the value net directly, that'd be an unnecessary step anyhow. And you could create such a training set w/o reinforcement learning since there are pure monte carlo bots stronger than 5d KGS - but that'd be far more computationally expensive.
But its still not really true that there aren't obvious applications of deep reinforcement learning - indeed robotics is one promising application, and that seems rather relevant. this paper initially demonstrated an impressive improvement in manipulative tasks, and you can prob follow its numerous citations for newer stuff: http://arxiv.org/abs/1504.00702
I do agree that this exact architecture in AlphaGo prob doesn't have applications beyond just teaching us how to play go better; it seems too specialized. I believe they mean it in just the vaguest possible sense; that the kind of deep algorithms demonstrating incredible performance in AlphaGo have diverse applications; but this should not come as a surprise to anyone even loosely following what people have done with deep learning in the past couple of years anyhow.
The key I think is,
> yet it clearly generalizes rather well to unseen board situations and still evaluates them sucessfully
I'm not sure this has been proven to be meaningful in a general sense, as you seem to also imply. Extrapolation can be a tricky answer subtle business. What about unusual board sizes, for which no training data exists? Or if you changed a rule? I'm sure deepmind would say the adversarial approach would work for these cases, but I'm not sure it would. Would be very interesting to see if humans could 'learn' a new state more quickly than the algorithm.
That might provide a hint that the algorithm is 'just' fitting the data well (with appropriate baked in regularization, of course). Or if it can more generally 'learn' given system rules.
Still, I think AlphaGo does demonstrate amazing positional judgement in unseen board states, and that this is visible in the details of how it plays out particular situations. No two games are exactly alike - difficulty of go for computers is precisely in its extreme combinatorial explosion - and in particular tactical situations every detail of the situation matters. Yet you can see AlphaGo judging the correct sequences of moves, "knowing" how to make a particular group alive for eg, even when a particular other move seems more natural. And probably the most amazing thing about how it plays is how early it becomes completely sure that its got an advantage on the board, and how precisely it judges how much it needs to keep the advantage to the end. Every detail of the board is again relevant here, and basically no human would be so confident so soon. A go bot that couldn't adapt its tactics to unseen situation would be easy to beat; just ensnare it in a large complicated fight, and you're going to kill a big group and guarantee a win. Ofc people tried this in some masterP games, and turns out AlphaGo is tactically just as strong.
So, its basically like with other generalizations you can get from machine learning; a net trained on say ImageNet will generalize to different poses, occlusions, contexts and variations of objects similar to what it was exposed in training etc and still do a superhuman job of classifying such pictures, but will naturally be quite hopeless with completely unseen items. So too AlphaGo seems to know the game of go, generalizing from seen examples to correct judgements in other states, but would be quite hopeless if tested on even a slight variation of the game rules.
Go has deep strategy, but it is very well defined in terms of what can and cannot be done and those rules are not particularly complex. Power grids in contrast are far more complex. There are thousands of rules, but also many more thousands of unwritten assumptions and case-by-case analysis. A final issue is that there exist unsolved and unrecognized problems.
The last AI winter (deep learning is just the latest rebrand) came from researchers overstating their accomplishments and making promises about general intelligence that could not be kept. Any claim about anything that requires general intelligence in the near future is undoubtedly overpromising.
Do you have any sources to back this assertion? It sounds unintuitive as I know object recognition sytema are usually trained on small images but they generalize well to arbitrary image sizes. What you are describing sounds like overfitting.
If you haven't played go very much, you may thing that "it's just a bigger board". 19x19 is commonly used because it has an even balance of edge and center influence (in reality, edge influence seems to be slightly higher). With the 13x13, corner plays have overwhelming influence in the center. At 9x9, there is basically no center strategy at all. Normal strategies starting in the corners and expanding influence toward the center don't work as effectively with larger boards (the larger the board, the more this becomes true).
This is a much different issue than image recognition in that strategy doesn't scale in the same way that images do.
It isn't an "algorithm" as you think it is. It's not like deep blue or chess AIs specifically built for chess.
DeepMind is "general" and a step towards a somewhat general AI ( though we are nowhere close to general AI ).
Nobody taught Deepmind to play Go. It taught itself how to play Go.
> In reality, unless you have a really good simulator, deep reinforcement learning is almost never applicable.
That's all learning is...
I think the AI/human crossover boundaries are at meta boundaries. As we get more meta, humans do better over AI. AI has been eating up the lower meta levels for some time now. It has been a very long time since a human could do division faster than a computer.
The question is how far does this meta staircase ascend, and if/when will AI climb all the way to the top?
This means that an advantageous board position is much less important, and it will be in both players favour to keep the board position very near evenly matched.
In go the last 8 moves is almost never going to make the difference (the last 20-40 moves in a game that doesn't end in resignation there are almost no mistakes in pro games).
The thought experiment a little more refined, like alphago programmers get time to implement only validMoves() and makeMove() then let the same learning process go on it, I wouldn't count it out. If you only flip the switch once the new game variant starts, before a human has even begun to take an action the computer will have played out thousands if not millions of games using MCTS and slowly training up its networks in real time instead of using a static one. As the game progresses the bot should only get better and better.
The current version might be using some different techniques that could be more useful, though. They should release some details in the next few weeks.
http://www.popsci.com/science/article/2010-12/fyi-how-many-d...
The other big improvement from AlphaGo was using another deep convolution network trained on moves from all those games to create an 'expand' function. Unlike chess, the branching factor of that search tree in Go is ridiculously high, because you can place a stone pretty much anywhere on a big board, while in chess the set of legal moves at any given time is fairly limited. So that neural network they use as an expand function allows them to prioritize the order in which moves are considered. This innovation isn't necessary for chess as the branching factor is much lower - but it might still provide an input for the prioritizing the order in which moves are evaluated.
After learning how all this worked, I understand why Deepmind themselves seem more impressed with their Atari AI, as it actually learned how to play the game from first principles by just looking at the pixels and being told its score, whereas, the approach above, impressive as it is, still actually just plugs the neural networks into existing algorithms, rather than use them for the core decision making process too.
I don't think it will necessarily be as good at chess, because chess has a much smaller search space. So "stupider" methods can actually work, while Go requires very good pattern recognition to prune the search space.
https://twitter.com/demishassabis/status/867584056095002624
https://events.google.com/alphago2017/
For instance, Fernando Aguilar 6d (aguilar1 and aguilar on KGS), an amateur dan from Argentina, has defeated Hasegawa Sunao 9p as well as Yo Kagen 9p. In theory this should not have happened.
If the cap didn't exist, I think Alpha Go may be around 13p, based on the fact that Lee Sedol and Ke Jie may be able to give reverse komi to many top 9p players, and that Alpha Go may be about 3 stones stronger than both. Park Yeong-hun is less often mentioned but he may be playing at a higher level to that of Lee Sedol.
https://www.gokgs.com/graphPage.jsp?user=aguilar1
An informal mapping among ranking systems can be seen here:
http://senseis.xmp.net/?RankWorldwideComparison
Servers usually manually override ranks for professional players...
But going back to my point, a 9p should be consistently stronger than a 6 dan amateur, but these counterexamples challenge that.