AlphaGo - Mastering the game of Go with deep neural networks and tree search | RL Paper Explained
❤️ Become The AI Epiphany Patreon ❤️ ► https://www.patreon.com/theaiepiphany
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬

In this video, I cover the seminal AlphaGo paper - the first system to beat a professional Go player in the game of Go. 

A task previously considered beyond the reach of current AI systems and at least 10 years off into the future, but neural networks proved them wrong!

You'll learn about:
✔️All of the nitty-gritty details around AlphaGo
✔️How MTCS and other subcomponents work

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
✅ AlphaGo movie: https://www.youtube.com/watch?v=WXuK6gekU1Y&ab_channel=DeepMind
✅ Karpathy on AlphaGo: https://medium.com/@karpathy/alphago-in-context-c47718cb95a5
✅ Silver on UCB algo: https://www.youtube.com/watch?v=sGuiWX07sKw&list=PLqYmG7hTraZBiG_XpjnPrSNw-1XQaM_gB&index=12&t=2370s&ab_channel=DeepMind
✅ MTCS explained: https://www.youtube.com/watch?v=UXW2yZndl7U
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 

⌚️ Timetable: 

00:00 Intro
00:37 Context behind the game of Go 
04:10 High-level overview of components - SL policies
07:25 RL policy network
09:30 The value network
11:15 Going deeper
16:30 Details around value network
19:05 Understanding the search (MTCS)
27:10 Evaluation of AlphaGo
33:30 Older techniques
34:40 Even more detailed explanation of APV-MTCS
37:40 Virtual loss
41:00 Engineering
45:30 Neural networks and symmetries

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
💰 BECOME A PATREON OF THE AI EPIPHANY ❤️ 

If these videos, GitHub projects, and blogs help you,
consider helping me out by supporting me on Patreon! 

The AI Epiphany ► https://www.patreon.com/theaiepiphany
One-time donation: 
https://www.paypal.com/paypalme/theaiepiphany 

Much love! ❤️
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 

💡 The AI Epiphany is a channel dedicated to simplifying the field of AI using creative visualizations and in general, a stronger focus on geometrical and visual intuition, rather than the algebraic and numerical "intuition". 

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
👋 CONNECT WITH ME ON SOCIAL 
LinkedIn ► https://www.linkedin.com/in/aleksagordic/ 
Twitter ► https://twitter.com/gordic_aleksa 

Instagram ► https://www.instagram.com/aiepiphany/ 
Facebook ► https://www.facebook.com/aiepiphany/ 

👨‍👩‍👧‍👦 JOIN OUR DISCORD COMMUNITY:
Discord ► https://discord.gg/peBrCpheKE

📢 SUBSCRIBE TO MY MONTHLY AI NEWSLETTER:
Substack ► https://aiepiphany.substack.com/

💻 FOLLOW ME ON GITHUB FOR COOL PROJECTS: 
GitHub ► https://github.com/gordicaleksa 

📚 FOLLOW ME ON MEDIUM:
Medium ► https://gordicaleksa.medium.com/ 
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬

#alphago #deepmind #reinforcementlearning
 What's up? In this video I'm going to cover AlphaGo paper or mastering the game of Go with deep neural networks and research. And I guess all of you already know and heard a lot about it. They even made a movie about AlphaGo. Everything we've ever tried in AI just falls over when you try the game of Go. The number of possible configurations of the board is more than the number of atoms in the universe. After you've finished with this video, you'll have a much better background. And I strongly suggest you go ahead and watch the complete movie if you haven't already. The game kind of turned on its axis. That is not a confident face. Okay, with that out of the way, let's jump into the paper. So basically, why is Go interesting? The reason it's so interesting is that all of the other famous board games such as chess, checkers, etc. were already solved much earlier. Like basically, in 1997, Deep Blue program has beaten Garry Kasparov, the best chess player in the world at that point of time. And all of the other games were also solved, but Go still wasn't solved. And people predicted that we'll need at least, so I think in 2014 or 2015, people thought that we'll need at least 10 more years to actually solve the game. And then in 2015-16, Destiny appeared and cracked the game of Go. So it's a pretty big deal and it's a seminal. It's a breakthrough in the world of AI. And yeah, so basically, what is Go to start with? So basically, it's an old Eastern game that was, I think, invented in China a couple of thousand years ago. And basically, you have a 19 by 19 board and you place these kind of white and black stones on the intersections. And the whole goal is to acquire as much territory as possible. So you can see here, the white here actually gained all of the axes belong to the white player. And the game finishes in two ways. Either you win because the opponent resigned or you win because the game ended and you have more territory than the opponent. Those are the basics. Now let's jump into the details of the paper and I'll slowly start going from the high level explanation. I'll go into the depth at the end of the paper. So yeah, stick with me. Okay, so as a bit of theory, basically, all the games that have perfect information have this thing called the optimal value function. In games that have perfect information such as Go because it's completely observable, compare that to poker, maybe where you don't know the cards of the opponent, so it's partially observable. Here in perfect information games, you have this thing called optimal value function. Once you have the optimal value function, you can play using it just following the greedy policy and you'll win. You'll basically play the most optimal you can if the other players are also playing the optimal game. So that's some game theory for you. But basically, we'll find a way how to approximate this function and we'll also use something called policy function and Monte Carlo tree search to get to the final AlphaGo layout. And I'll slowly start digesting all of those parts for you. So before that, why is Go so hard? And one of the reasons, the main reason basically is that the search space is huge. So in games like chess, you have the breath is around 35 and the depth is around 80. So you can just kind of average out all of the branches and get this number. And the final number of states is B raised to the power of D. So you can see that chess has a lot of states, but it's nowhere near close to Go, so you have basically 250 raised to the power of 150. That's a huge amount of states. And all of the previous approaches such as the minimax search, such as the depth minimax search with the alpha, beta, pruning, whatever, failed to solve the search. And even pure Monte Carlo tree search methods, which are proven to be really good and effective for other board games, failed miserably when deployed to Go. So let's see how this paper actually coped and found the solution to solve this hard, difficult game. And yeah, here is the kind of the high level overview of the whole system. And it has a couple of components. So the main components are these. So we first have this thing called policy network. And what the policy network does is the following. You input a state where the state is the following. So you basically have a 19 by 19 board, right? And they'll just have some handcrafted feature maps. You'll end up with a 19 by 19 times 48 volume, which you'll be inputting into CNN. And that's pretty much it. And you don't need to know anything about those specifics. So here is, for example, one of the features is these things called liberties. And those are basically the empty slots around a certain player. Maybe we have a black here and some of the liberties would be the red circles here. And you kind of you somehow integrate that information into that feature, into those feature maps. And you input those and use that as the as the current state. So with that out of the way, let's just see how it works. So the first thing they do is they train this thing called supervised learning policy network. And what they do is the following. So they have a huge database of professional, so experts playing game of go. And it's they just train this policy network as a simple supervised learning method using the simple SL method. And so basically you input the state. Here's a visual representation. So you input the state here and out of the policy network comes this vector of probabilities distributed over the whole board. So there's basically a 19 by 19 vector of probabilities. And what they do here to train it is the following. So they just have these tuples, a bunch of these tuples, I think 30 million. But we'll get to those details a bit later. And we have these tuple and tuples. And so what they do is the following. So they have a CNN. So that's the policy network. So just basically plug in the S, the state, and you get out the probabilities. So you just want to do a simple cross entropy loss here. And basically whatever the action that the professional player played. So maybe that's this one. You want to make sure that you push that one to one and you make sure that the other ones go to zero. So because this is softmax, you just basically do log on this action and minus log and you just minimize that loss. So if I just plot that. So that's the minus log. And you want to make sure that the probability of that particular action goes to one. And then we'll have the loss dropping down to zero. So that's how they train it. And that's super simple. So it's just that you need a lot of data and they have a big CNN, 12, 13 layers deep. Again, we'll get to those details a bit later. So but that's the policy network. Okay. The self supervised policy network. Then we have this thing called the rollout policy. And it's trained in the same fashion. The only difference is that it's much smaller. It's actually it's not a DNN. It's not a neural network. It's a it's a simple linear layer. And it's trained on less data because it's it's has a smaller capacity. OK. Once that's done, you want to train something called the RL policy network. And what you do basically is you take this trained this pre trained supervised learning policy and you just initialize this RL policy network. And then you create a huge pool of different policy networks. And you just let them play against each other. So something we call self play in the field of reinforcement learning. And basically after after you train those against each other, you basically then train those networks using policy gradient methods. And again, I'll give you a simple intuitive explanation and then we'll dig into equations. But what you basically do so you have two players and they play they play the game of go. And now let's say that each of these lines represents the action. So let's say that this player won. So player one player two. So at the end, the player one won. And so basically what you'll do is you'll take all of the actions that that player did and you'll make sure they are more like they have higher probability. And on the other hand, you'll take the player two and you'll make sure that the actions that that player took in those specific states are less probable the next time. And then you'll just take the player two. You'll input it into the pool of players, potential players. You'll update your your current your RL policy. And that's how you'll continue doing it. You'll be improving your policy. You'll be putting the opponents into the pool and you'll be playing against them and basically do the policy gradient. And that's how you learn the policy network. Again, just a high level explanation will get equations. Basically, I just want you to have this mental picture. The actions if you won, you want to make sure that the actions you played in those particular states are of higher probability. And if you lost, you want to make sure that the actions are actually less probable next time you use that network. That's it. It's really simple. It's basically you can treat it as a classification task for all of those couples. OK, so the trick here is we won't be using this RL policy network in the final AlphaGo algorithm. So why do we have it? Well, we have it in order to bootstrap this thing called the value network. And what the value network does is you give it the state and it just tells you how likely are you to win in that particular state. So it has values between one and minus one. If it outputs one, that means you're highly likely to win. If it outputs minus one, that means you're going to lose and anything in between. Yeah, just you can interpolate yourself. OK, so you can see here the again the visualization of the value network. The output is a scalar, which tells you how good that state is. So that's basically our best approximation of the value state function in RL. OK, so the way we train the value network is we take a bunch of so we have we play a bunch of self play games. And from each game, we take a single state and the outcome of the game and we train the value network to regress that outcome. So we'll again we'll get to details, but like that's the high level picture. So you want to make sure that it learns how to basically regress. It's again a supervised learning on a data set that we extracted from the self play games. And that's it. So once we have all of those networks, we'll be using them and combine them into this thing called Monte Carlo Tree Search. And we'll use these networks to better to kind of scope the breadth and the depth of the tree search. And that's how the ultimate algorithm, the final algorithm will look like. So we'll slowly get to those details, but this was the high level picture. Hopefully you understand everything. OK, now let's start digging into some equations and let's see how the SL policies train. So we basically want to maximize the likelihood of the human move a selected in state s. And here you can just symbolically see that basically you want to move. So for that particular action, you just want to maximize it given the state. So those are these state action tuples and you just do a step along the gradient, which will kind of boost up the probability of that action and diminish all of the other probabilities. Simple classification, basically cross entropy loss. Don't get confused by these expressions. This just means that the update step is proportional to this one. But you basically do cross entropy loss and that's it. So it's a 13 layer CNN basically. And you train it on 30 million positions and position is just a fancy name for the state. And so that's the data set I was mentioning here. And yeah, so finally, once we have this network pre trained, they showed that on the on the test set, you can predict with 57 percent accuracy the next step that the expert will play. So that's a huge improvement compared to the previous state of the art, which was 44.4. And that actually translates into much higher probability of winning the game as we'll soon see. OK, so that was the SL policy. Now, the fast rollout policy already explained it's a linear softmax. It just has a bit different input. Basically, again, some go magic, some hand crafting. And so the thing with this network is it has a much smaller accuracy, so 24.2. But the thing is, it's much faster because it's so smaller. So the inference is two microseconds compared to this SL policy, which has three milliseconds. Now you'll see why this will be useful and once we get to the search part of the algorithm for the aerial network, let's see how we train that one. So, again, we train the current policy network, which is initial initially initialized using the SL policy network. And we randomly select some previous iteration of the policy network. So that's the self play part of the game. And this is how you, again, how you update the weights of that policy network. Basically, it's again proportional. So the update step is proportional to the gradient. So that's the same thing as this one. But there's a trick. There is this ZT and that's the outcome. So that means if you won, you'd get plus one. And then that means you basically end up in the same situation as here. You'll basically want to make sure that all of the actions you played get get like higher probability in those particular states. And if you lost, then you'll have minus one. That means you'll move. You'll actually move in the opposite direction. So you'll make sure that the actions are less probable and that intuitively makes sense. And in expectations, all of that will lead you to have much better policy function. OK. And when you play head to head, when you take this RL policy that was trained using self play and you compare it with the SL policy network, you can see that it will win in 80 percent of the games. So it improved dramatically. And if you use no search whatsoever, and we still haven't I still haven't explained the search, but we'll get there. And if you don't use a search, you can actually just use this RL policy and you'll win in 85 percent of the games against this open source go pro. And of course, go program called Pachi. And it's not the best one out there, but it was pretty decent. And it's it's awesome to see that without any search whatsoever. And this thing, this Pachi thing, it uses a bunch of simulations, a bunch of search, and it still loses against a pure DNN approach without any MTCS Monte Carlo tree search. So those are some of the details. Let me show you what this chart means. This one tells you that depending how many filters you have in your CNN, you will be improving the training accuracy. And this is the final AlphaGo model. And you can see that the as expected, the battery gets on this KGS supervised data set, the battery will get against the final version. And the final CNN they took had 192 layers. As you can see, that's this curve, it's got a decent trade off between the performance and its way faster than these bulky big networks. So it's a trade off they did. OK, we'll get to this chart in a bit later when we start talking about search. OK, we saw how to train the policy networks. We saw how to train the RL policy as well. And you saw this is pretty much simple cross entropy. It's a simple classification task pretty much ignoring this part. And let's see how we train the value network. So the value network is trained like this. So it's basically a regression task. And what this means is the following. So let's say we have state S and let's say that the final outcome going from that state was maybe ZT was one. That means we won playing from this state. So in let's say that the value function gave us maybe zero point seven. So because of that, this difference, this is plus one and this is zero point seven. That means you have zero point three, a positive number scaling the value function. That means you'll increment. You'll you'll you'll kind of update this to go from zero point seven. Next time you'll see the state you'll maybe you'll maybe tell you maybe out with zero point seventy five. But if the value function was off by much more, if it was maybe I don't know if it was zero point three or zero point two, then this difference would be zero point eight. And that means you take like a bigger step and a bigger gradient. And that means that you'd go from maybe zero point two. You'd next time you see the step, you'd output zero point thirty five. So you can see we had a bigger increment here than here. And that's how it pretty much works. So it's L2 L2 loss, basically. Nothing special there. Simple regression. You always have to be supervised at the end in order to learn using gradient based methods. So again, I explained how they train it. They they they so they had some problems overfitting. So if you if you if you train this value network the following way. If you took two players and they played a game and if you were using every single state and the final outcome, which may be plus one for the this player, then you'd kind of overfit because the states are highly correlated. And so what it did is instead from every single game, they just take a single random state and couple that with the final outcome ZT. And that's what they use. And after training on 30 million data points, they they pretty much avoid the overfitting. And you can see that they have zero point two to six and zero point two three four on training and test sets, which is minimal overfitting. Before that, they had zero point thirty seven on the test set, which is much higher than zero point nineteen on the training set when they just take this naive approach. So that's the reason they took just a single couple from a single game. And that's how they avoided overfitting on this problem. OK, finally, search. Let me see how I'll explain this. So here are some equations which will make sense in a second. Basically, let's start with this diagram. So this chart here tells you the following. So we're in a current state and we want to do a bunch of simulations in order to improve our predictions. So what we'll do is we'll somehow create these priors. And in order to create these priors, we'll use the SL policy network. So we'll just input the state. We'll through this SL policy network, it will give us some priors. And using those priors, you can see that we'll end up with some. So every single edge will have this score associated with it. So that's a Q. So it's an action value function plus this U of P. And we'll see what it is. And we just maximize that score. And that's how we traverse the tree. And once we get to the leaf node. So once we get here or here and we'll just keep this for a moment. Expansion steps will go like this. Evaluation. So once we get to the leaf node, we do the two things. So the first thing is we pass that state into a value network. So we pass this into a value network and it will give us the estimate of how good that state is. And secondly, we'll do a rollout using the fast policy network. So basically from this state, using that policy, we'll be playing the game and then we'll get to the final state. We'll get some reward and using those two informations, those two snippets, we'll do something called backup. Where we'll from the leaf node going to the root node, we'll be updating the edges with some statistics. So we somehow update those statistics. We use those statistics to calculate the Q values. And later we use those Q values to again in the next simulation to again do this simulation. So when you do a bunch of these simulations, the values, the Q values and the visitation counts will be much more predictive of the final outcome. And you'll finally use the visitation count from the edge to pick the best action from that particular state. And that's the root state. So if you're currently confused, that's totally fine. We'll slowly digest each of these pieces in a second. Okay, so I skipped the expansion part because it's not usually you won't do expansion in every single step. So basically expansion happens once you. So for example, let's say this is a leaf node and it has it was visited 39 times so far. So out of all the simulations we had so far, we visited the state exactly 39 times and we have something called and threshold, which basically and they have it. The nominal value here is 40. So once you get the next time you visit this leaf, the number of visits will rise to 40 and you'll want to expand this node. So how to expand it? Well, again, you just use the SL policy network. You input the state and you get the new priors and then you can you just pick the using the this the score that you'll pick the next state as the leaf. So the one that had the max value, this will be your leaf node. And then again, you just proceed with the evaluation. You do the you pass it through the value function. You do the rollouts and you just kind of update the statistics up the tree, the entry updates. OK, so that's the Monte Carlo tree search like a high level overview and we'll slowly start to better understand how it works. So how do we pick the actions? So again, I said action value function plus this you think and this algorithm is called P. You see T or polynomial upper bound. Upper confidence bound for trees algorithm and if you're familiar with UCB, this will come will be pretty easy. David Silver had a really nice explanation of UCB, so I'll link that in the description. But here it will be enough to just understand this on like intuitively. Basically, this thing, the you part is proportional to the prior and to the number of visitations of that particular edge. So what that means is the following. So initially, this thing will be really small to zero. So basically have the you part being proportional to the prior. So you get the prior from the SL network, remember? So once you start visiting this this edge a lot of times, so that that particular action from that particular state, this thing will start to go to infinity, which means that the whole you part will go to zero. And that means that initially you are preferring. So that's something called confidence in the face of uncertainty. So you'll basically prefer exploration and you won't be focusing on in the Q value. But as time goes on, this will go to zero. And you'll basically because you visited this edge a lot of times, you have a decent you have more confidence in your Q estimate. And then if the Q estimate is high, that means that that particular action from that state is really promising. So you'll keep continue exploring that part of a subtree. So, yeah, hopefully that makes a bit more sense now. And don't worry, we'll get even deeper than this. OK, so small optimization detail you basically don't want because the SL network is a huge CNN. You don't want to use it repeatedly. You just once you calculate the priors for a specific leaf node, that's it. You just store the priors and you don't recalculate it again. So that's that's a small detail. So how do we get the Q values, which we later use to do navigate to traverse the tree? So this is how we get the Q values. Basically, we first calculate this thing. So the value function, it's a simple weighted average between the value function and the rollout outcome. So that's this part. So once we do the rollout and we do the V part, we take those values and we average them. And these 0.5 here for the lambda, which means they'll equally take from the value estimate as well as from the rollout estimate. That's the V. And finally, in order to get the Q, you'll just divide that by the number of visitations of that particular edge. And that's your Q estimate. So this is just a fancy way of saying, hey, in iteration I, did you visit the state S and action A? If you had, just increment this. So just a fancy way of saying from N simulations we had, how many of those simulations did traverse this particular edge S A? So that's it. And that's how you calculate the Qs. So if we were following along, you may be confused about why are we using SL policy to calculate the priors. And the reason is simple experiment. They tried both. So it's worth noting that the SL policy P sigma performed better in AlphaGo than the stronger RL policy network P row. Basically, but on the other hand, the value function was derived from the stronger RL policy network. So, yeah, it performed better than the value function derived from the SL policy network. Just a simple detail. Again, experiments are pretty common in deep learning. So, yeah, even though we'd expect that the RL policy would perform better, it did not. And they make some assumption here, presumably because humans select a diverse beam of promising moves, whereas RL optimized for a single, for the single best move. Not sure whether that's the best explanation, I guess. Yeah. OK, so that was the search part. We saw all of the components on the high level. Let's see some results. And here on the Y axis, you can see the L rating. And so what's what I hope I'm pronouncing that right. So you know, or something like that. So basically, when you have a 230 point gap, that means you have a 80 percent probability of winning. So that means translating that into human language, you have player one and player two. And this guy has 230 points more in ELO than this guy. That means he'll win in 80 percent of the games in expectation. So that's it. So once we know the Y axis on the X axis, you can see the following things. So these two are open source go programs. This one was using it wasn't using this Monte Carlo tree search. It used some older search heuristics, some variations of Minimax probably. And then we have two commercial go programs. Here we have Fan Hui, who was you probably know this guy. He actually was one of the main actors in the AlphaGo movie. Really cool guy. He was a European champion at that point of time. And you can see the scores. And this is the AlphaGo. And this is finally the distributed version of the AlphaGo. So on multiple machines, not on a single machine. And you can see this one is really bad. Beginner level, all of the other go programs were amateurs. And finally, only the AlphaGo achieved two then. So this is just some go specific ranking. So we had he was to then professional and AlphaGo was in the same ballpark. And the distributed version was even stronger. So that's about it. You can see AlphaGo finally achieved professional level rankings. And here are just some ablation studies. Basically, when you use both the rollout, the fast rollout, both the value function and the policy network to estimate the priors. That's the best thing to do. Once you remove the value, we drop. Once you remove the rollouts, we drop even further. So that means that the rollouts are even more important. They're really important in evaluating those leaf nodes. So yeah, here just a simple ablation of different. Once you increase the number of threads, you can see the yellow goes up. Once you increase the number of GPUs and hold the 40 threads, you improve again the performance and finally distributed. Once you start adding up more GPUs, you again, as expected, you get more performance. So compute, especially in RL, is something that can improve things. And we know that from GPT family of models as well. So throw more compute at it and you'll get better results. That's for sure. The trick here is they only had five seconds for each move. So they have some limitations. And that's something that you hear each program use approximately five second computations. And using that constraint, we get these yellow scores. Otherwise, we had more time would get even higher yellow scores. OK, so some detail about the hover implementation. So the AlphaGo uses an asynchronous multi-threaded search that executes simulations on CPUs and computes policy and value networks in parallel on GPUs. So basically those fast policy rollouts, they'll be delegated to CPUs and the slower, the bulkier policy evaluations, such as the one that calculates the priors and the value function that estimates the leaf node, will be just offloaded to a GPU. And that's a small optimization they did. And you can see a bunch of hardware here. And the final distributed version of AlphaGo used multiple machines, 40 threads, 1,200 something CPUs and almost 200 GPUs. It's a huge amount of hardware. OK, I'll skip this part. Not that interesting. And I'll skip this. So this was just a couple of. So the five games they played against Fanhui and they won each of the five games back in 2015 or 16. So you can just check out. I personally don't understand, never played Go, but you don't need to understand Go in order to understand the actual implementation and deep learning approach part of this paper. OK, one more detail. The kind of the ablations with that lambda term combining the value function estimation and the rollout estimation. And they're just complementary. So the value network approximates the outcome of games played by the strong, but in practically slow network. Well, the rollouts can be can precisely score and evaluate the outcome of games played by the weaker, but faster rollout policy. So basically, because policy only takes two microseconds, you can execute it multiple times. And finally, the estimates will get much closer to the value function, which is slower, but more accurate. And combining them is kind of complementary. So, yeah, again, experiments, experiments. OK, I think this was the the the the this was the high level part. And I've got only two more pages left where we'll dig into even more details and you'll really understand how this thing works. Before that, just a quick mention. So the AlphaGo evaluated thousands of times fewer positions where the position is again a synonym for state. Then Deep Blue didn't just match against Casperov 97. So basically it's a much smarter approach. It's not as brute force as Deep Blue was. So that's again plus one for AlphaGo. And so it's provided a hope that human level performance can now be achieved in other seemingly intractable A.I. domains. So the good thing about this paper is that it gave us hope that when something looks so insolvable, when the search space is so huge, as in the case of Go, and people thought we'll need additional 10 years to solve it and we solved it in a year or two after that prediction was made, this gives us hope that who knows, maybe a couple of years down the road we'll be solving some problems which we now think are uncrackable. So who knows. Okay, that was the first part. Getting even deeper. The last two pages will get you a really firm grasp and understanding of AlphaGo. So let's dig into it. Quick note here. Prior to AlphaGo, in order to solve board games, people used this thing called Minimax Search. And you probably heard of it in your favorite CS class. And then people invented some better heuristics like Depth-first Minimax Search with Alpha-Beta pruning, which achieved superhuman performance in chess, checkers, and Othello, but has not been effective in Go. So after that, people started implementing this thing called Monte Carlo Tree Search without using DNNs. And basically this one dramatically improved performance in a bunch of different board games as well as in Go in particular, but it still wasn't good enough by itself to just push it into the professional league, to push those algorithms into professional level. Okay, so let's see now every single detail about the search algorithm. So I mentioned the statistics and here are the statistics. So each edge stores a set of statistics. And here we can see the prior. So that's the thing we calculate using the SL network. We store the visitation counts for that particular edge. We store the cumulative Monte Carlo estimates coming from the value function and coming from the rollouts. And finally, we calculate the Q and we store that in each and every edge. And we just calculate the Q using all of these previous statistics. So, yeah, keep that in mind. I mentioned the P-UCT. So that's the variant of the upper confidence bound algorithm for trees, the ECT. And this is the exact formulation. So they have something called this coefficient which just weighs this U part compared to the Q part. So this is the complete equation. And this is just a hyperparameter like your lambda parameter. And they set it to five. Again, probably hyperparameter search. And here is a prior. Here is the visitation. So we were just missing this part. So what it means is the following. Let's say we have the parent state and we have the child state. And if we're calculating the P-UCT value for this edge, we're basically counting the number of visitations that this child, that his parent had. So let me now translate this, try and translate this equation into human language. What it basically means is the following. So the more visitations your parent had and the less times they visited you, but you have a strong prior, that means this edge will be highly likely to visit the next time. So if we were visiting a lot of the other children of this parent, so that would mean that this numerator part would increase. But we haven't been visiting this child, that means that this part would be low. So this one is low, this one is high, this will explode. And then we have the prior, so if it's non-zero and will never be zero, that means eventually we'll want to explore this particular node. So that's the exploration versus the exploitation tradeoff I was mentioning previously. Now you can see every single detail. And this search control strategy initially prefers actions with high prior probability and low visit count, but asymptotically prefers actions with high action value. So that's this one. So as I said, this will go to zero. And finally, you'll be just traversing the tree using the action value functions. Okay. Optimization detail again, the leaf position is added to the queue for evaluation by the value network unless it has previously been evaluated. So again, we'll just run the leaf node through the value functions only once and that's it, just a small optimization. One more interesting thing here is this. So they have this concept of a virtual loss. And what it does is the following. So let's say we have a root node and we traverse some path and we got to a leaf node. And so because now we have to evaluate this node, right, so we have to pass it through the value network. So the value network is on some GPU there and we have to do a rollout and that means we'll have to delegate that to some CPU. So we have some CPU here and basically we'll have some delay before this is calculated, before the game is done. And before this inference on the GPU is done. So in that time, what we want to do is we want to make sure that the other threads are not exploring this exact same path. Because remember, Monte Carlo Tree Search has a bunch of simulations going on in parallel. So there's a bunch of different threads we're trying to calculate and improve upon the estimates of this search tree. And so we want to discourage them to visit the same trace as this one. So what we'll do is we'll for each every edge. So these are the states and the connections are the edges. So basically what we'll do is we'll increase the artificial increase the visitation counts by three, where three is this number of virtual laws. They use number three and will also decrease the Monte Carlo estimate. So these W values, the cumulative estimates will decrease them by three, which will effectively do the following thing. So as you can see, looking at this equation, the PUCT equation, because this will get bigger, that means that this term will get smaller. So U will get smaller and also Q, because Q is calculated by averaging, just a second, so Q, this is Q. You can see that that's how we calculate and because this part, the cumulative part is smaller, Q will be smaller. So that means every single of these edges will have smaller probability. And so the other parallel threads won't be visiting it until we finish up with this value inference and rollout. Then we'll just kind of counteract this. So we'll add minus three, so we'll delete this and we'll add plus three here. And we'll finally add the Z estimate, the actual estimate from the rollout, and we'll add the visitation count will be increased by one. So finally, we have the exact state that we want to be in. So hopefully this was clear enough. If not, please comment down in the comment section whether this was confusing. Okay, that was the virtual part of the tree. So at the end of the simulation, the rollout statistics are updated in backward pass through each step, replacing the virtual losses by the actual outcome. So you can see we counteract the virtual loss, we increase the visitation count, we counteract the virtual loss, and we add the actual rollout outcome. So that's the whole trick. Okay, this is how the Q is evaluated again. This is 0.5, so we'll have equal contribution coming from the value function, averaged over the number of visitations of that particular edge. Same goes for the rollouts, that's how we get the Q. And that's it. Now, there is more details. Hopefully you find this interesting, because there is a lot of engineering here. AlphaGo is not a new novel research per se, but the whole engineering pipeline and everything put together is awesome, and that's why they achieved the results they did. So I mentioned the prior calculations. So once we have the leaf and we want to expand it, you basically feed it through an SL policy network. But the thing is, again, SL policy is on some GPU, so until you get the actual priors, you'll have to wait. And that's why they have this thing called the tree policy. And we never heard about this policy so far, so this is the fourth policy network. They only mention it here. And what it does, it provides the placeholders for the priors. So before we get the actual priors from the GPU, they just put some roughly good priors, not the best ones, so these ones will be higher quality. So it's a similar thing to this virtual loss. So it's a placeholder before we get the actual results. And you'll see this pattern repeating in this paper. Okay. And finally, the priors are computed by the SL policy, and they use this beta to control the temperature. That means you basically, you know what the temperature does to softmax, so the lower temperature will kind of make it sharper distribution. So yeah, that's a minor, not that important detail. Finally, at the end, so it selects the action with the maximum visit count. And this is less sensitive to outliers than maximizing the action value function, value, okay? So basically, that means the following. So we have a route, and we did a bunch of simulations. So now we have pretty decent statistics and much better approximations to the actual Q values. And now we have some numbers here. Maybe this edge was visited 32 times. This one was visited only three times. This one was visited 50 times. So we'll pick up this edge, and that's the action we'll play, and we'll end up with a new state. And now maybe Lissedol will play the game, and he'll bring us to some other state, and then we'll do the Monte Carlo again. Okay, that's how the game plays off. Okay? But again, some tricks. We want to reuse the tree at subsequent time steps. So that means the following. So we were calculating this huge tree at this root state here, okay? And Lissedol decided to... and we decided to go here. And once we go here, we still have a bunch of simulations that went down and calculated the statistics for this part of the subtree. We'll just throw away this part, but we'll still have some statistics here, and so we won't have to recalculate those from scratch. Again, smaller optimization detail. It kind of helps you build up this picture of what it takes to actually make this thing work. So it's one thing to just say, hey, we're using policy gradients, supervised learning, blah, blah, blah. But when you actually see what it takes to make this thing work, there's a lot of details, a lot of distributed programming, software engineering, testing, trying out things, experimenting. So, yeah, just keep that in mind if you don't already know it. And finally, the match opponent version of the AlphaGo continues searching during the opponent's move. So that means once we get into the... once Lissedol, for example, is... it's history, we're still calculating. We're still trying to approximate a better approximation of this. So we're here. We're still building up the Monte Carlo tree search. So wherever does Lissedol take us to some state, we'll have better approximations of the subtree here because we continued calculating the Monte Carlo... updating the Monte Carlo tree. And, yeah, again, one more detail. It extends the search if the action maximizing visit count and the action maximizing action value disagree. So if the Q value and the N value tell you to take different actions, so there is some discrepancy there and we want to improve it. And so they just keep calculating until they agree. And then we know we have much better estimate and we're more certain that we'll win. Okay. Those were the most important parts of the AlphaGo. Now, I'll just wrap this up with a couple more details around the neural networks. And that's it. We already heard a lot of details about this policy. So it's a linear softmax. That's why it's so fast, two microseconds. And, again, it was trained on eight million positions. So the huge SL policy was trained on 30 million positions. This one was trained on less data because it's smaller, less capacity, basically. But it's the same approach to training this one. And there is some additional heuristics which I won't mention. So just keep in mind that, again, lots of details which go into this once you start really digging deep. I want to mention symmetries. And what's the thing with symmetries? Well, because the board looks like this. Let's say, just to mark this orientation like this. So we can have, you can imagine four different rotations you can perform. So maybe you can rotate this thing by 90 degrees and you'll end up in this layout. And you can also have reflections. So you'll end up with eight different possibilities to feed this into a CNN. And when they use the raw policy, the RL policy network to play the game, they do the following. They take all of the eight configurations and they feed that into the policy network and they just average out all the probabilities across those eight configurations. And they just get a better actually gameplay by doing that, better probabilities, better distributions over actions. And yeah, just keep that in mind. And also the actual Monte Carlo tree search I was mentioning so far, what it does is makes use of an implicit symmetry ensemble that randomly selects the single rotation slash reflection for each evaluation. So that means once you get to the leaf node, you'll sometimes take a random element from this group of symmetries and do the actual inference on top of that one. And they just showed that this improves things. The reason is they actually augmented the data set using all of those eight different elements from that group. So that's the reason they're using it. They get more data, thus they get better weights and yeah, they use it in the search as well. So yeah, symmetries, if you didn't expect any symmetries, here they are. I know that Alpha Fold is also using some interesting symmetries. The paper still hasn't hasn't come out, but I read some blogs and it's probably using some equivalent types of deploying models. So we'll see that anyways. A bit about computation. I found this interesting. It takes 50 GPUs and you need to train this for three weeks to train the actual the SL policy network. So that's a lot of compute and that's just the final network without any hyperparameter. Then we have for the RL policy, they train it for one day on 50 GPUs and finally to train the value network, they have 50 GPUs for one week. So that's more than a month to train the final configuration of this algorithm. Plus you have the Monte Carlo tree search during the inference. It's a lot of compute that went into this. Yeah, just keep that in mind. Okay, let me see if we have some interesting details here. I mentioned this already. So we have the pool of opponents for the RL policy. So here is a small detail that's probably important. So I previously had only ZT here and that's not exactly correct. So we're not using that simple version of the policy gradient algorithm. We're using something called Reinforce Policy Gradient. Here we just, in order to reduce the variance and keep the same bias, we just subtract this thing called the baseline and they're just using the value function. So basically everything else remains the same. So across every single game and every single step, we average the gradients according to this thing. And you can treat this as an advantage. Basically, if you won and the value function was maybe 0.8, so that's plus one, that means you have a smaller update. So you want to make sure that that action goes up, but like by just a little bit. So hopefully you have intuitive understanding why this is here. I won't get into the maths. It doesn't change. It doesn't change the maths. The expectation remains the same. Thus the bias is unchanged. Only the variance is reduced here. But it's the same thing as you intuitively. It's the same thing as you only had ZT. So if it's easier for you, just ignore the V portion. I think that's pretty much it. Okay, I've covered everything. There is a lot of things that went into this. Here are some of the hyperparameters I was using. The threshold was 40. The virtual loss, the part for the P-UCT algorithm, the mixing parameter, the temperature for the SL policy. A lot of hyperparameters took a lot of work from a team of people from DeepMind to create this thing. So yeah, it's pretty awesome. So let me know if you found this video interesting. If you did, you know the drill. Hit the subscribe button. Click the bell icon to get notified. And see you in the next video. Until next time, keep learning deep.
[{"start": 0.0, "end": 8.0, "text": " What's up? In this video I'm going to cover AlphaGo paper or mastering the game of Go with deep neural networks and research."}, {"start": 8.0, "end": 13.0, "text": " And I guess all of you already know and heard a lot about it. They even made a movie about AlphaGo."}, {"start": 13.0, "end": 17.0, "text": " Everything we've ever tried in AI just falls over when you try the game of Go."}, {"start": 17.0, "end": 22.0, "text": " The number of possible configurations of the board is more than the number of atoms in the universe."}, {"start": 22.0, "end": 27.0, "text": " After you've finished with this video, you'll have a much better background."}, {"start": 27.0, "end": 31.0, "text": " And I strongly suggest you go ahead and watch the complete movie if you haven't already."}, {"start": 31.0, "end": 34.0, "text": " The game kind of turned on its axis."}, {"start": 34.0, "end": 37.0, "text": " That is not a confident face."}, {"start": 37.0, "end": 40.0, "text": " Okay, with that out of the way, let's jump into the paper."}, {"start": 40.0, "end": 52.0, "text": " So basically, why is Go interesting? The reason it's so interesting is that all of the other famous board games such as chess, checkers, etc. were already solved much earlier."}, {"start": 52.0, "end": 63.0, "text": " Like basically, in 1997, Deep Blue program has beaten Garry Kasparov, the best chess player in the world at that point of time."}, {"start": 63.0, "end": 67.0, "text": " And all of the other games were also solved, but Go still wasn't solved."}, {"start": 67.0, "end": 76.0, "text": " And people predicted that we'll need at least, so I think in 2014 or 2015, people thought that we'll need at least 10 more years to actually solve the game."}, {"start": 76.0, "end": 82.0, "text": " And then in 2015-16, Destiny appeared and cracked the game of Go."}, {"start": 82.0, "end": 87.0, "text": " So it's a pretty big deal and it's a seminal. It's a breakthrough in the world of AI."}, {"start": 87.0, "end": 91.0, "text": " And yeah, so basically, what is Go to start with?"}, {"start": 91.0, "end": 98.0, "text": " So basically, it's an old Eastern game that was, I think, invented in China a couple of thousand years ago."}, {"start": 98.0, "end": 108.0, "text": " And basically, you have a 19 by 19 board and you place these kind of white and black stones on the intersections."}, {"start": 108.0, "end": 111.0, "text": " And the whole goal is to acquire as much territory as possible."}, {"start": 111.0, "end": 117.0, "text": " So you can see here, the white here actually gained all of the axes belong to the white player."}, {"start": 117.0, "end": 121.0, "text": " And the game finishes in two ways."}, {"start": 121.0, "end": 130.0, "text": " Either you win because the opponent resigned or you win because the game ended and you have more territory than the opponent."}, {"start": 130.0, "end": 132.0, "text": " Those are the basics."}, {"start": 132.0, "end": 137.0, "text": " Now let's jump into the details of the paper and I'll slowly start going from the high level explanation."}, {"start": 137.0, "end": 139.0, "text": " I'll go into the depth at the end of the paper."}, {"start": 139.0, "end": 141.0, "text": " So yeah, stick with me."}, {"start": 141.0, "end": 153.0, "text": " Okay, so as a bit of theory, basically, all the games that have perfect information have this thing called the optimal value function."}, {"start": 153.0, "end": 157.0, "text": " In games that have perfect information such as Go because it's completely observable,"}, {"start": 157.0, "end": 164.0, "text": " compare that to poker, maybe where you don't know the cards of the opponent, so it's partially observable."}, {"start": 164.0, "end": 167.0, "text": " Here in perfect information games, you have this thing called optimal value function."}, {"start": 167.0, "end": 173.0, "text": " Once you have the optimal value function, you can play using it just following the greedy policy and you'll win."}, {"start": 173.0, "end": 178.0, "text": " You'll basically play the most optimal you can if the other players are also playing the optimal game."}, {"start": 178.0, "end": 180.0, "text": " So that's some game theory for you."}, {"start": 180.0, "end": 186.0, "text": " But basically, we'll find a way how to approximate this function and we'll also use something called policy function"}, {"start": 186.0, "end": 190.0, "text": " and Monte Carlo tree search to get to the final AlphaGo layout."}, {"start": 190.0, "end": 194.0, "text": " And I'll slowly start digesting all of those parts for you."}, {"start": 194.0, "end": 198.0, "text": " So before that, why is Go so hard?"}, {"start": 198.0, "end": 203.0, "text": " And one of the reasons, the main reason basically is that the search space is huge."}, {"start": 203.0, "end": 209.0, "text": " So in games like chess, you have the breath is around 35 and the depth is around 80."}, {"start": 209.0, "end": 213.0, "text": " So you can just kind of average out all of the branches and get this number."}, {"start": 213.0, "end": 217.0, "text": " And the final number of states is B raised to the power of D."}, {"start": 217.0, "end": 222.0, "text": " So you can see that chess has a lot of states, but it's nowhere near close to Go,"}, {"start": 222.0, "end": 225.0, "text": " so you have basically 250 raised to the power of 150."}, {"start": 225.0, "end": 228.0, "text": " That's a huge amount of states."}, {"start": 228.0, "end": 231.0, "text": " And all of the previous approaches such as the minimax search,"}, {"start": 231.0, "end": 236.0, "text": " such as the depth minimax search with the alpha, beta, pruning, whatever,"}, {"start": 236.0, "end": 238.0, "text": " failed to solve the search."}, {"start": 238.0, "end": 245.0, "text": " And even pure Monte Carlo tree search methods, which are proven to be really good and effective for other board games,"}, {"start": 245.0, "end": 249.0, "text": " failed miserably when deployed to Go."}, {"start": 249.0, "end": 256.0, "text": " So let's see how this paper actually coped and found the solution to solve this hard, difficult game."}, {"start": 256.0, "end": 262.0, "text": " And yeah, here is the kind of the high level overview of the whole system."}, {"start": 262.0, "end": 265.0, "text": " And it has a couple of components."}, {"start": 265.0, "end": 268.0, "text": " So the main components are these."}, {"start": 268.0, "end": 270.0, "text": " So we first have this thing called policy network."}, {"start": 270.0, "end": 273.0, "text": " And what the policy network does is the following."}, {"start": 273.0, "end": 276.0, "text": " You input a state where the state is the following."}, {"start": 276.0, "end": 280.0, "text": " So you basically have a 19 by 19 board, right?"}, {"start": 280.0, "end": 283.0, "text": " And they'll just have some handcrafted feature maps."}, {"start": 283.0, "end": 290.0, "text": " You'll end up with a 19 by 19 times 48 volume, which you'll be inputting into CNN."}, {"start": 290.0, "end": 292.0, "text": " And that's pretty much it."}, {"start": 292.0, "end": 295.0, "text": " And you don't need to know anything about those specifics."}, {"start": 295.0, "end": 300.0, "text": " So here is, for example, one of the features is these things called liberties."}, {"start": 300.0, "end": 302.0, "text": " And those are basically the empty slots around a certain player."}, {"start": 302.0, "end": 306.0, "text": " Maybe we have a black here and some of the liberties would be the red circles here."}, {"start": 306.0, "end": 312.0, "text": " And you kind of you somehow integrate that information into that feature, into those feature maps."}, {"start": 312.0, "end": 315.0, "text": " And you input those and use that as the as the current state."}, {"start": 315.0, "end": 318.0, "text": " So with that out of the way, let's just see how it works."}, {"start": 318.0, "end": 324.0, "text": " So the first thing they do is they train this thing called supervised learning policy network."}, {"start": 324.0, "end": 325.0, "text": " And what they do is the following."}, {"start": 325.0, "end": 332.0, "text": " So they have a huge database of professional, so experts playing game of go."}, {"start": 332.0, "end": 341.0, "text": " And it's they just train this policy network as a simple supervised learning method using the simple SL method."}, {"start": 341.0, "end": 344.0, "text": " And so basically you input the state."}, {"start": 344.0, "end": 345.0, "text": " Here's a visual representation."}, {"start": 345.0, "end": 352.0, "text": " So you input the state here and out of the policy network comes this vector of probabilities distributed over the whole board."}, {"start": 352.0, "end": 358.0, "text": " So there's basically a 19 by 19 vector of probabilities."}, {"start": 358.0, "end": 361.0, "text": " And what they do here to train it is the following."}, {"start": 361.0, "end": 365.0, "text": " So they just have these tuples, a bunch of these tuples, I think 30 million."}, {"start": 365.0, "end": 366.0, "text": " But we'll get to those details a bit later."}, {"start": 366.0, "end": 369.0, "text": " And we have these tuple and tuples."}, {"start": 369.0, "end": 370.0, "text": " And so what they do is the following."}, {"start": 370.0, "end": 371.0, "text": " So they have a CNN."}, {"start": 371.0, "end": 373.0, "text": " So that's the policy network."}, {"start": 373.0, "end": 380.0, "text": " So just basically plug in the S, the state, and you get out the probabilities."}, {"start": 380.0, "end": 383.0, "text": " So you just want to do a simple cross entropy loss here."}, {"start": 383.0, "end": 386.0, "text": " And basically whatever the action that the professional player played."}, {"start": 386.0, "end": 388.0, "text": " So maybe that's this one."}, {"start": 388.0, "end": 395.0, "text": " You want to make sure that you push that one to one and you make sure that the other ones go to zero."}, {"start": 395.0, "end": 403.0, "text": " So because this is softmax, you just basically do log on this action and minus log and you just minimize that loss."}, {"start": 403.0, "end": 404.0, "text": " So if I just plot that."}, {"start": 404.0, "end": 406.0, "text": " So that's the minus log."}, {"start": 406.0, "end": 409.0, "text": " And you want to make sure that the probability of that particular action goes to one."}, {"start": 409.0, "end": 411.0, "text": " And then we'll have the loss dropping down to zero."}, {"start": 411.0, "end": 413.0, "text": " So that's how they train it."}, {"start": 413.0, "end": 414.0, "text": " And that's super simple."}, {"start": 414.0, "end": 419.0, "text": " So it's just that you need a lot of data and they have a big CNN, 12, 13 layers deep."}, {"start": 419.0, "end": 421.0, "text": " Again, we'll get to those details a bit later."}, {"start": 421.0, "end": 423.0, "text": " So but that's the policy network."}, {"start": 423.0, "end": 424.0, "text": " Okay."}, {"start": 424.0, "end": 426.0, "text": " The self supervised policy network."}, {"start": 426.0, "end": 429.0, "text": " Then we have this thing called the rollout policy."}, {"start": 429.0, "end": 431.0, "text": " And it's trained in the same fashion."}, {"start": 431.0, "end": 434.0, "text": " The only difference is that it's much smaller."}, {"start": 434.0, "end": 436.0, "text": " It's actually it's not a DNN."}, {"start": 436.0, "end": 437.0, "text": " It's not a neural network."}, {"start": 437.0, "end": 439.0, "text": " It's a it's a simple linear layer."}, {"start": 439.0, "end": 445.0, "text": " And it's trained on less data because it's it's has a smaller capacity."}, {"start": 445.0, "end": 446.0, "text": " OK."}, {"start": 446.0, "end": 450.0, "text": " Once that's done, you want to train something called the RL policy network."}, {"start": 450.0, "end": 460.0, "text": " And what you do basically is you take this trained this pre trained supervised learning policy and you just initialize this RL policy network."}, {"start": 460.0, "end": 466.0, "text": " And then you create a huge pool of different policy networks."}, {"start": 466.0, "end": 468.0, "text": " And you just let them play against each other."}, {"start": 468.0, "end": 472.0, "text": " So something we call self play in the field of reinforcement learning."}, {"start": 472.0, "end": 480.0, "text": " And basically after after you train those against each other, you basically then train those networks using policy gradient methods."}, {"start": 480.0, "end": 485.0, "text": " And again, I'll give you a simple intuitive explanation and then we'll dig into equations."}, {"start": 485.0, "end": 490.0, "text": " But what you basically do so you have two players and they play they play the game of go."}, {"start": 490.0, "end": 494.0, "text": " And now let's say that each of these lines represents the action."}, {"start": 494.0, "end": 496.0, "text": " So let's say that this player won."}, {"start": 496.0, "end": 498.0, "text": " So player one player two."}, {"start": 498.0, "end": 501.0, "text": " So at the end, the player one won."}, {"start": 501.0, "end": 511.0, "text": " And so basically what you'll do is you'll take all of the actions that that player did and you'll make sure they are more like they have higher probability."}, {"start": 511.0, "end": 522.0, "text": " And on the other hand, you'll take the player two and you'll make sure that the actions that that player took in those specific states are less probable the next time."}, {"start": 522.0, "end": 524.0, "text": " And then you'll just take the player two."}, {"start": 524.0, "end": 528.0, "text": " You'll input it into the pool of players, potential players."}, {"start": 528.0, "end": 532.0, "text": " You'll update your your current your RL policy."}, {"start": 532.0, "end": 534.0, "text": " And that's how you'll continue doing it."}, {"start": 534.0, "end": 536.0, "text": " You'll be improving your policy."}, {"start": 536.0, "end": 544.0, "text": " You'll be putting the opponents into the pool and you'll be playing against them and basically do the policy gradient."}, {"start": 544.0, "end": 546.0, "text": " And that's how you learn the policy network."}, {"start": 546.0, "end": 549.0, "text": " Again, just a high level explanation will get equations."}, {"start": 549.0, "end": 553.0, "text": " Basically, I just want you to have this mental picture."}, {"start": 553.0, "end": 560.0, "text": " The actions if you won, you want to make sure that the actions you played in those particular states are of higher probability."}, {"start": 560.0, "end": 565.0, "text": " And if you lost, you want to make sure that the actions are actually less probable next time you use that network."}, {"start": 565.0, "end": 567.0, "text": " That's it. It's really simple."}, {"start": 567.0, "end": 572.0, "text": " It's basically you can treat it as a classification task for all of those couples."}, {"start": 572.0, "end": 579.0, "text": " OK, so the trick here is we won't be using this RL policy network in the final AlphaGo algorithm."}, {"start": 579.0, "end": 580.0, "text": " So why do we have it?"}, {"start": 580.0, "end": 584.0, "text": " Well, we have it in order to bootstrap this thing called the value network."}, {"start": 584.0, "end": 591.0, "text": " And what the value network does is you give it the state and it just tells you how likely are you to win in that particular state."}, {"start": 591.0, "end": 594.0, "text": " So it has values between one and minus one."}, {"start": 594.0, "end": 597.0, "text": " If it outputs one, that means you're highly likely to win."}, {"start": 597.0, "end": 604.0, "text": " If it outputs minus one, that means you're going to lose and anything in between. Yeah, just you can interpolate yourself."}, {"start": 604.0, "end": 608.0, "text": " OK, so you can see here the again the visualization of the value network."}, {"start": 608.0, "end": 611.0, "text": " The output is a scalar, which tells you how good that state is."}, {"start": 611.0, "end": 617.0, "text": " So that's basically our best approximation of the value state function in RL."}, {"start": 617.0, "end": 625.0, "text": " OK, so the way we train the value network is we take a bunch of so we have we play a bunch of self play games."}, {"start": 625.0, "end": 634.0, "text": " And from each game, we take a single state and the outcome of the game and we train the value network to regress that outcome."}, {"start": 634.0, "end": 638.0, "text": " So we'll again we'll get to details, but like that's the high level picture."}, {"start": 638.0, "end": 642.0, "text": " So you want to make sure that it learns how to basically regress."}, {"start": 642.0, "end": 647.0, "text": " It's again a supervised learning on a data set that we extracted from the self play games."}, {"start": 647.0, "end": 649.0, "text": " And that's it."}, {"start": 649.0, "end": 656.0, "text": " So once we have all of those networks, we'll be using them and combine them into this thing called Monte Carlo Tree Search."}, {"start": 656.0, "end": 663.0, "text": " And we'll use these networks to better to kind of scope the breadth and the depth of the tree search."}, {"start": 663.0, "end": 667.0, "text": " And that's how the ultimate algorithm, the final algorithm will look like."}, {"start": 667.0, "end": 672.0, "text": " So we'll slowly get to those details, but this was the high level picture."}, {"start": 672.0, "end": 674.0, "text": " Hopefully you understand everything."}, {"start": 674.0, "end": 679.0, "text": " OK, now let's start digging into some equations and let's see how the SL policies train."}, {"start": 679.0, "end": 684.0, "text": " So we basically want to maximize the likelihood of the human move a selected in state s."}, {"start": 684.0, "end": 689.0, "text": " And here you can just symbolically see that basically you want to move."}, {"start": 689.0, "end": 694.0, "text": " So for that particular action, you just want to maximize it given the state."}, {"start": 694.0, "end": 708.0, "text": " So those are these state action tuples and you just do a step along the gradient, which will kind of boost up the probability of that action and diminish all of the other probabilities."}, {"start": 708.0, "end": 713.0, "text": " Simple classification, basically cross entropy loss."}, {"start": 713.0, "end": 715.0, "text": " Don't get confused by these expressions."}, {"start": 715.0, "end": 720.0, "text": " This just means that the update step is proportional to this one."}, {"start": 720.0, "end": 723.0, "text": " But you basically do cross entropy loss and that's it."}, {"start": 723.0, "end": 726.0, "text": " So it's a 13 layer CNN basically."}, {"start": 726.0, "end": 731.0, "text": " And you train it on 30 million positions and position is just a fancy name for the state."}, {"start": 731.0, "end": 735.0, "text": " And so that's the data set I was mentioning here."}, {"start": 735.0, "end": 748.0, "text": " And yeah, so finally, once we have this network pre trained, they showed that on the on the test set, you can predict with 57 percent accuracy the next step that the expert will play."}, {"start": 748.0, "end": 755.0, "text": " So that's a huge improvement compared to the previous state of the art, which was 44.4."}, {"start": 755.0, "end": 763.0, "text": " And that actually translates into much higher probability of winning the game as we'll soon see."}, {"start": 763.0, "end": 765.0, "text": " OK, so that was the SL policy."}, {"start": 765.0, "end": 770.0, "text": " Now, the fast rollout policy already explained it's a linear softmax."}, {"start": 770.0, "end": 774.0, "text": " It just has a bit different input."}, {"start": 774.0, "end": 779.0, "text": " Basically, again, some go magic, some hand crafting."}, {"start": 779.0, "end": 787.0, "text": " And so the thing with this network is it has a much smaller accuracy, so 24.2."}, {"start": 787.0, "end": 791.0, "text": " But the thing is, it's much faster because it's so smaller."}, {"start": 791.0, "end": 798.0, "text": " So the inference is two microseconds compared to this SL policy, which has three milliseconds."}, {"start": 798.0, "end": 809.0, "text": " Now you'll see why this will be useful and once we get to the search part of the algorithm for the aerial network, let's see how we train that one."}, {"start": 809.0, "end": 817.0, "text": " So, again, we train the current policy network, which is initial initially initialized using the SL policy network."}, {"start": 817.0, "end": 821.0, "text": " And we randomly select some previous iteration of the policy network."}, {"start": 821.0, "end": 823.0, "text": " So that's the self play part of the game."}, {"start": 823.0, "end": 828.0, "text": " And this is how you, again, how you update the weights of that policy network."}, {"start": 828.0, "end": 830.0, "text": " Basically, it's again proportional."}, {"start": 830.0, "end": 833.0, "text": " So the update step is proportional to the gradient."}, {"start": 833.0, "end": 835.0, "text": " So that's the same thing as this one."}, {"start": 835.0, "end": 836.0, "text": " But there's a trick."}, {"start": 836.0, "end": 838.0, "text": " There is this ZT and that's the outcome."}, {"start": 838.0, "end": 841.0, "text": " So that means if you won, you'd get plus one."}, {"start": 841.0, "end": 846.0, "text": " And then that means you basically end up in the same situation as here."}, {"start": 846.0, "end": 854.0, "text": " You'll basically want to make sure that all of the actions you played get get like higher probability in those particular states."}, {"start": 854.0, "end": 857.0, "text": " And if you lost, then you'll have minus one."}, {"start": 857.0, "end": 858.0, "text": " That means you'll move."}, {"start": 858.0, "end": 860.0, "text": " You'll actually move in the opposite direction."}, {"start": 860.0, "end": 865.0, "text": " So you'll make sure that the actions are less probable and that intuitively makes sense."}, {"start": 865.0, "end": 872.0, "text": " And in expectations, all of that will lead you to have much better policy function."}, {"start": 872.0, "end": 873.0, "text": " OK."}, {"start": 873.0, "end": 881.0, "text": " And when you play head to head, when you take this RL policy that was trained using self play and you compare it with the SL policy network,"}, {"start": 881.0, "end": 884.0, "text": " you can see that it will win in 80 percent of the games."}, {"start": 884.0, "end": 886.0, "text": " So it improved dramatically."}, {"start": 886.0, "end": 893.0, "text": " And if you use no search whatsoever, and we still haven't I still haven't explained the search, but we'll get there."}, {"start": 893.0, "end": 902.0, "text": " And if you don't use a search, you can actually just use this RL policy and you'll win in 85 percent of the games against this open source go pro."}, {"start": 902.0, "end": 905.0, "text": " And of course, go program called Pachi."}, {"start": 905.0, "end": 909.0, "text": " And it's not the best one out there, but it was pretty decent."}, {"start": 909.0, "end": 913.0, "text": " And it's it's awesome to see that without any search whatsoever."}, {"start": 913.0, "end": 926.0, "text": " And this thing, this Pachi thing, it uses a bunch of simulations, a bunch of search, and it still loses against a pure DNN approach without any MTCS Monte Carlo tree search."}, {"start": 926.0, "end": 928.0, "text": " So those are some of the details."}, {"start": 928.0, "end": 931.0, "text": " Let me show you what this chart means."}, {"start": 931.0, "end": 940.0, "text": " This one tells you that depending how many filters you have in your CNN, you will be improving the training accuracy."}, {"start": 940.0, "end": 942.0, "text": " And this is the final AlphaGo model."}, {"start": 942.0, "end": 951.0, "text": " And you can see that the as expected, the battery gets on this KGS supervised data set, the battery will get against the final version."}, {"start": 951.0, "end": 954.0, "text": " And the final CNN they took had 192 layers."}, {"start": 954.0, "end": 963.0, "text": " As you can see, that's this curve, it's got a decent trade off between the performance and its way faster than these bulky big networks."}, {"start": 963.0, "end": 966.0, "text": " So it's a trade off they did."}, {"start": 966.0, "end": 970.0, "text": " OK, we'll get to this chart in a bit later when we start talking about search."}, {"start": 970.0, "end": 972.0, "text": " OK, we saw how to train the policy networks."}, {"start": 972.0, "end": 976.0, "text": " We saw how to train the RL policy as well."}, {"start": 976.0, "end": 980.0, "text": " And you saw this is pretty much simple cross entropy."}, {"start": 980.0, "end": 985.0, "text": " It's a simple classification task pretty much ignoring this part."}, {"start": 985.0, "end": 988.0, "text": " And let's see how we train the value network."}, {"start": 988.0, "end": 990.0, "text": " So the value network is trained like this."}, {"start": 990.0, "end": 992.0, "text": " So it's basically a regression task."}, {"start": 992.0, "end": 994.0, "text": " And what this means is the following."}, {"start": 994.0, "end": 1003.0, "text": " So let's say we have state S and let's say that the final outcome going from that state was maybe ZT was one."}, {"start": 1003.0, "end": 1006.0, "text": " That means we won playing from this state."}, {"start": 1006.0, "end": 1013.0, "text": " So in let's say that the value function gave us maybe zero point seven."}, {"start": 1013.0, "end": 1019.0, "text": " So because of that, this difference, this is plus one and this is zero point seven."}, {"start": 1019.0, "end": 1024.0, "text": " That means you have zero point three, a positive number scaling the value function."}, {"start": 1024.0, "end": 1026.0, "text": " That means you'll increment."}, {"start": 1026.0, "end": 1030.0, "text": " You'll you'll you'll kind of update this to go from zero point seven."}, {"start": 1030.0, "end": 1035.0, "text": " Next time you'll see the state you'll maybe you'll maybe tell you maybe out with zero point seventy five."}, {"start": 1035.0, "end": 1046.0, "text": " But if the value function was off by much more, if it was maybe I don't know if it was zero point three or zero point two, then this difference would be zero point eight."}, {"start": 1046.0, "end": 1052.0, "text": " And that means you take like a bigger step and a bigger gradient."}, {"start": 1052.0, "end": 1056.0, "text": " And that means that you'd go from maybe zero point two."}, {"start": 1056.0, "end": 1061.0, "text": " You'd next time you see the step, you'd output zero point thirty five."}, {"start": 1061.0, "end": 1065.0, "text": " So you can see we had a bigger increment here than here."}, {"start": 1065.0, "end": 1068.0, "text": " And that's how it pretty much works."}, {"start": 1068.0, "end": 1071.0, "text": " So it's L2 L2 loss, basically."}, {"start": 1071.0, "end": 1072.0, "text": " Nothing special there."}, {"start": 1072.0, "end": 1073.0, "text": " Simple regression."}, {"start": 1073.0, "end": 1078.0, "text": " You always have to be supervised at the end in order to learn using gradient based methods."}, {"start": 1078.0, "end": 1081.0, "text": " So again, I explained how they train it."}, {"start": 1081.0, "end": 1085.0, "text": " They they they so they had some problems overfitting."}, {"start": 1085.0, "end": 1090.0, "text": " So if you if you if you train this value network the following way."}, {"start": 1090.0, "end": 1104.0, "text": " If you took two players and they played a game and if you were using every single state and the final outcome, which may be plus one for the this player, then you'd kind of overfit because the states are highly correlated."}, {"start": 1104.0, "end": 1113.0, "text": " And so what it did is instead from every single game, they just take a single random state and couple that with the final outcome ZT."}, {"start": 1113.0, "end": 1115.0, "text": " And that's what they use."}, {"start": 1115.0, "end": 1121.0, "text": " And after training on 30 million data points, they they pretty much avoid the overfitting."}, {"start": 1121.0, "end": 1129.0, "text": " And you can see that they have zero point two to six and zero point two three four on training and test sets, which is minimal overfitting."}, {"start": 1129.0, "end": 1138.0, "text": " Before that, they had zero point thirty seven on the test set, which is much higher than zero point nineteen on the training set when they just take this naive approach."}, {"start": 1138.0, "end": 1147.0, "text": " So that's the reason they took just a single couple from a single game. And that's how they avoided overfitting on this problem."}, {"start": 1147.0, "end": 1151.0, "text": " OK, finally, search."}, {"start": 1151.0, "end": 1153.0, "text": " Let me see how I'll explain this."}, {"start": 1153.0, "end": 1160.0, "text": " So here are some equations which will make sense in a second."}, {"start": 1160.0, "end": 1163.0, "text": " Basically, let's start with this diagram."}, {"start": 1163.0, "end": 1166.0, "text": " So this chart here tells you the following."}, {"start": 1166.0, "end": 1173.0, "text": " So we're in a current state and we want to do a bunch of simulations in order to improve our predictions."}, {"start": 1173.0, "end": 1177.0, "text": " So what we'll do is we'll somehow create these priors."}, {"start": 1177.0, "end": 1181.0, "text": " And in order to create these priors, we'll use the SL policy network."}, {"start": 1181.0, "end": 1183.0, "text": " So we'll just input the state."}, {"start": 1183.0, "end": 1187.0, "text": " We'll through this SL policy network, it will give us some priors."}, {"start": 1187.0, "end": 1196.0, "text": " And using those priors, you can see that we'll end up with some. So every single edge will have this score associated with it."}, {"start": 1196.0, "end": 1199.0, "text": " So that's a Q. So it's an action value function plus this U of P."}, {"start": 1199.0, "end": 1203.0, "text": " And we'll see what it is. And we just maximize that score."}, {"start": 1203.0, "end": 1207.0, "text": " And that's how we traverse the tree. And once we get to the leaf node."}, {"start": 1207.0, "end": 1212.0, "text": " So once we get here or here and we'll just keep this for a moment."}, {"start": 1212.0, "end": 1215.0, "text": " Expansion steps will go like this. Evaluation."}, {"start": 1215.0, "end": 1219.0, "text": " So once we get to the leaf node, we do the two things."}, {"start": 1219.0, "end": 1223.0, "text": " So the first thing is we pass that state into a value network."}, {"start": 1223.0, "end": 1228.0, "text": " So we pass this into a value network and it will give us the estimate of how good that state is."}, {"start": 1228.0, "end": 1233.0, "text": " And secondly, we'll do a rollout using the fast policy network."}, {"start": 1233.0, "end": 1240.0, "text": " So basically from this state, using that policy, we'll be playing the game and then we'll get to the final state."}, {"start": 1240.0, "end": 1248.0, "text": " We'll get some reward and using those two informations, those two snippets, we'll do something called backup."}, {"start": 1248.0, "end": 1254.0, "text": " Where we'll from the leaf node going to the root node, we'll be updating the edges with some statistics."}, {"start": 1254.0, "end": 1261.0, "text": " So we somehow update those statistics. We use those statistics to calculate the Q values."}, {"start": 1261.0, "end": 1269.0, "text": " And later we use those Q values to again in the next simulation to again do this simulation."}, {"start": 1269.0, "end": 1280.0, "text": " So when you do a bunch of these simulations, the values, the Q values and the visitation counts will be much more predictive of the final outcome."}, {"start": 1280.0, "end": 1287.0, "text": " And you'll finally use the visitation count from the edge to pick the best action from that particular state."}, {"start": 1287.0, "end": 1289.0, "text": " And that's the root state."}, {"start": 1289.0, "end": 1296.0, "text": " So if you're currently confused, that's totally fine. We'll slowly digest each of these pieces in a second."}, {"start": 1296.0, "end": 1304.0, "text": " Okay, so I skipped the expansion part because it's not usually you won't do expansion in every single step."}, {"start": 1304.0, "end": 1314.0, "text": " So basically expansion happens once you. So for example, let's say this is a leaf node and it has it was visited 39 times so far."}, {"start": 1314.0, "end": 1323.0, "text": " So out of all the simulations we had so far, we visited the state exactly 39 times and we have something called and threshold,"}, {"start": 1323.0, "end": 1327.0, "text": " which basically and they have it. The nominal value here is 40."}, {"start": 1327.0, "end": 1335.0, "text": " So once you get the next time you visit this leaf, the number of visits will rise to 40 and you'll want to expand this node."}, {"start": 1335.0, "end": 1339.0, "text": " So how to expand it? Well, again, you just use the SL policy network."}, {"start": 1339.0, "end": 1351.0, "text": " You input the state and you get the new priors and then you can you just pick the using the this the score that you'll pick the next state as the leaf."}, {"start": 1351.0, "end": 1355.0, "text": " So the one that had the max value, this will be your leaf node."}, {"start": 1355.0, "end": 1360.0, "text": " And then again, you just proceed with the evaluation. You do the you pass it through the value function."}, {"start": 1360.0, "end": 1366.0, "text": " You do the rollouts and you just kind of update the statistics up the tree, the entry updates."}, {"start": 1366.0, "end": 1376.0, "text": " OK, so that's the Monte Carlo tree search like a high level overview and we'll slowly start to better understand how it works."}, {"start": 1376.0, "end": 1385.0, "text": " So how do we pick the actions? So again, I said action value function plus this you think and this algorithm is called P."}, {"start": 1385.0, "end": 1392.0, "text": " You see T or polynomial upper bound."}, {"start": 1392.0, "end": 1399.0, "text": " Upper confidence bound for trees algorithm and if you're familiar with UCB, this will come will be pretty easy."}, {"start": 1399.0, "end": 1403.0, "text": " David Silver had a really nice explanation of UCB, so I'll link that in the description."}, {"start": 1403.0, "end": 1408.0, "text": " But here it will be enough to just understand this on like intuitively."}, {"start": 1408.0, "end": 1418.0, "text": " Basically, this thing, the you part is proportional to the prior and to the number of visitations of that particular edge."}, {"start": 1418.0, "end": 1425.0, "text": " So what that means is the following. So initially, this thing will be really small to zero."}, {"start": 1425.0, "end": 1429.0, "text": " So basically have the you part being proportional to the prior."}, {"start": 1429.0, "end": 1436.0, "text": " So you get the prior from the SL network, remember? So once you start visiting this this edge a lot of times,"}, {"start": 1436.0, "end": 1442.0, "text": " so that that particular action from that particular state, this thing will start to go to infinity,"}, {"start": 1442.0, "end": 1445.0, "text": " which means that the whole you part will go to zero."}, {"start": 1445.0, "end": 1453.0, "text": " And that means that initially you are preferring. So that's something called confidence in the face of uncertainty."}, {"start": 1453.0, "end": 1458.0, "text": " So you'll basically prefer exploration and you won't be focusing on in the Q value."}, {"start": 1458.0, "end": 1463.0, "text": " But as time goes on, this will go to zero. And you'll basically because you visited this edge a lot of times,"}, {"start": 1463.0, "end": 1467.0, "text": " you have a decent you have more confidence in your Q estimate."}, {"start": 1467.0, "end": 1473.0, "text": " And then if the Q estimate is high, that means that that particular action from that state is really promising."}, {"start": 1473.0, "end": 1477.0, "text": " So you'll keep continue exploring that part of a subtree."}, {"start": 1477.0, "end": 1484.0, "text": " So, yeah, hopefully that makes a bit more sense now. And don't worry, we'll get even deeper than this."}, {"start": 1484.0, "end": 1491.0, "text": " OK, so small optimization detail you basically don't want because the SL network is a huge CNN."}, {"start": 1491.0, "end": 1497.0, "text": " You don't want to use it repeatedly. You just once you calculate the priors for a specific leaf node, that's it."}, {"start": 1497.0, "end": 1502.0, "text": " You just store the priors and you don't recalculate it again. So that's that's a small detail."}, {"start": 1502.0, "end": 1508.0, "text": " So how do we get the Q values, which we later use to do navigate to traverse the tree?"}, {"start": 1508.0, "end": 1513.0, "text": " So this is how we get the Q values. Basically, we first calculate this thing."}, {"start": 1513.0, "end": 1522.0, "text": " So the value function, it's a simple weighted average between the value function and the rollout outcome."}, {"start": 1522.0, "end": 1529.0, "text": " So that's this part. So once we do the rollout and we do the V part, we take those values and we average them."}, {"start": 1529.0, "end": 1537.0, "text": " And these 0.5 here for the lambda, which means they'll equally take from the value estimate as well as from the rollout estimate."}, {"start": 1537.0, "end": 1543.0, "text": " That's the V. And finally, in order to get the Q, you'll just divide that by the number of visitations of that particular edge."}, {"start": 1543.0, "end": 1554.0, "text": " And that's your Q estimate. So this is just a fancy way of saying, hey, in iteration I, did you visit the state S and action A?"}, {"start": 1554.0, "end": 1564.0, "text": " If you had, just increment this. So just a fancy way of saying from N simulations we had, how many of those simulations did traverse this particular edge S A?"}, {"start": 1564.0, "end": 1574.0, "text": " So that's it. And that's how you calculate the Qs. So if we were following along, you may be confused about why are we using SL policy to calculate the priors."}, {"start": 1574.0, "end": 1587.0, "text": " And the reason is simple experiment. They tried both. So it's worth noting that the SL policy P sigma performed better in AlphaGo than the stronger RL policy network P row."}, {"start": 1587.0, "end": 1595.0, "text": " Basically, but on the other hand, the value function was derived from the stronger RL policy network."}, {"start": 1595.0, "end": 1602.0, "text": " So, yeah, it performed better than the value function derived from the SL policy network."}, {"start": 1602.0, "end": 1608.0, "text": " Just a simple detail. Again, experiments are pretty common in deep learning."}, {"start": 1608.0, "end": 1613.0, "text": " So, yeah, even though we'd expect that the RL policy would perform better, it did not."}, {"start": 1613.0, "end": 1622.0, "text": " And they make some assumption here, presumably because humans select a diverse beam of promising moves, whereas RL optimized for a single, for the single best move."}, {"start": 1622.0, "end": 1628.0, "text": " Not sure whether that's the best explanation, I guess. Yeah."}, {"start": 1628.0, "end": 1636.0, "text": " OK, so that was the search part. We saw all of the components on the high level. Let's see some results."}, {"start": 1636.0, "end": 1645.0, "text": " And here on the Y axis, you can see the L rating. And so what's what I hope I'm pronouncing that right. So you know, or something like that."}, {"start": 1645.0, "end": 1651.0, "text": " So basically, when you have a 230 point gap, that means you have a 80 percent probability of winning."}, {"start": 1651.0, "end": 1657.0, "text": " So that means translating that into human language, you have player one and player two."}, {"start": 1657.0, "end": 1669.0, "text": " And this guy has 230 points more in ELO than this guy. That means he'll win in 80 percent of the games in expectation."}, {"start": 1669.0, "end": 1675.0, "text": " So that's it. So once we know the Y axis on the X axis, you can see the following things."}, {"start": 1675.0, "end": 1683.0, "text": " So these two are open source go programs. This one was using it wasn't using this Monte Carlo tree search."}, {"start": 1683.0, "end": 1690.0, "text": " It used some older search heuristics, some variations of Minimax probably. And then we have two commercial go programs."}, {"start": 1690.0, "end": 1698.0, "text": " Here we have Fan Hui, who was you probably know this guy. He actually was one of the main actors in the AlphaGo movie."}, {"start": 1698.0, "end": 1704.0, "text": " Really cool guy. He was a European champion at that point of time. And you can see the scores."}, {"start": 1704.0, "end": 1708.0, "text": " And this is the AlphaGo. And this is finally the distributed version of the AlphaGo."}, {"start": 1708.0, "end": 1713.0, "text": " So on multiple machines, not on a single machine. And you can see this one is really bad."}, {"start": 1713.0, "end": 1721.0, "text": " Beginner level, all of the other go programs were amateurs. And finally, only the AlphaGo achieved two then."}, {"start": 1721.0, "end": 1730.0, "text": " So this is just some go specific ranking. So we had he was to then professional and AlphaGo was in the same ballpark."}, {"start": 1730.0, "end": 1734.0, "text": " And the distributed version was even stronger. So that's about it."}, {"start": 1734.0, "end": 1741.0, "text": " You can see AlphaGo finally achieved professional level rankings. And here are just some ablation studies."}, {"start": 1741.0, "end": 1749.0, "text": " Basically, when you use both the rollout, the fast rollout, both the value function and the policy network to estimate the priors."}, {"start": 1749.0, "end": 1755.0, "text": " That's the best thing to do. Once you remove the value, we drop. Once you remove the rollouts, we drop even further."}, {"start": 1755.0, "end": 1762.0, "text": " So that means that the rollouts are even more important. They're really important in evaluating those leaf nodes."}, {"start": 1762.0, "end": 1772.0, "text": " So yeah, here just a simple ablation of different. Once you increase the number of threads, you can see the yellow goes up."}, {"start": 1772.0, "end": 1779.0, "text": " Once you increase the number of GPUs and hold the 40 threads, you improve again the performance and finally distributed."}, {"start": 1779.0, "end": 1785.0, "text": " Once you start adding up more GPUs, you again, as expected, you get more performance."}, {"start": 1785.0, "end": 1794.0, "text": " So compute, especially in RL, is something that can improve things. And we know that from GPT family of models as well."}, {"start": 1794.0, "end": 1798.0, "text": " So throw more compute at it and you'll get better results. That's for sure."}, {"start": 1798.0, "end": 1804.0, "text": " The trick here is they only had five seconds for each move. So they have some limitations."}, {"start": 1804.0, "end": 1809.0, "text": " And that's something that you hear each program use approximately five second computations."}, {"start": 1809.0, "end": 1816.0, "text": " And using that constraint, we get these yellow scores. Otherwise, we had more time would get even higher yellow scores."}, {"start": 1816.0, "end": 1824.0, "text": " OK, so some detail about the hover implementation."}, {"start": 1824.0, "end": 1834.0, "text": " So the AlphaGo uses an asynchronous multi-threaded search that executes simulations on CPUs and computes policy and value networks in parallel on GPUs."}, {"start": 1834.0, "end": 1847.0, "text": " So basically those fast policy rollouts, they'll be delegated to CPUs and the slower, the bulkier policy evaluations, such as the one that calculates the priors and the value function that estimates the leaf node,"}, {"start": 1847.0, "end": 1854.0, "text": " will be just offloaded to a GPU. And that's a small optimization they did. And you can see a bunch of hardware here."}, {"start": 1854.0, "end": 1867.0, "text": " And the final distributed version of AlphaGo used multiple machines, 40 threads, 1,200 something CPUs and almost 200 GPUs. It's a huge amount of hardware."}, {"start": 1867.0, "end": 1874.0, "text": " OK, I'll skip this part. Not that interesting. And I'll skip this. So this was just a couple of."}, {"start": 1874.0, "end": 1882.0, "text": " So the five games they played against Fanhui and they won each of the five games back in 2015 or 16."}, {"start": 1882.0, "end": 1894.0, "text": " So you can just check out. I personally don't understand, never played Go, but you don't need to understand Go in order to understand the actual implementation and deep learning approach part of this paper."}, {"start": 1894.0, "end": 1905.0, "text": " OK, one more detail. The kind of the ablations with that lambda term combining the value function estimation and the rollout estimation."}, {"start": 1905.0, "end": 1914.0, "text": " And they're just complementary. So the value network approximates the outcome of games played by the strong, but in practically slow network."}, {"start": 1914.0, "end": 1921.0, "text": " Well, the rollouts can be can precisely score and evaluate the outcome of games played by the weaker, but faster rollout policy."}, {"start": 1921.0, "end": 1925.0, "text": " So basically, because policy only takes two microseconds, you can execute it multiple times."}, {"start": 1925.0, "end": 1933.0, "text": " And finally, the estimates will get much closer to the value function, which is slower, but more accurate. And combining them is kind of complementary."}, {"start": 1933.0, "end": 1944.0, "text": " So, yeah, again, experiments, experiments. OK, I think this was the the the the this was the high level part."}, {"start": 1944.0, "end": 1952.0, "text": " And I've got only two more pages left where we'll dig into even more details and you'll really understand how this thing works."}, {"start": 1952.0, "end": 1962.0, "text": " Before that, just a quick mention. So the AlphaGo evaluated thousands of times fewer positions where the position is again a synonym for state."}, {"start": 1962.0, "end": 1969.0, "text": " Then Deep Blue didn't just match against Casperov 97. So basically it's a much smarter approach."}, {"start": 1969.0, "end": 1976.0, "text": " It's not as brute force as Deep Blue was. So that's again plus one for AlphaGo."}, {"start": 1976.0, "end": 1984.0, "text": " And so it's provided a hope that human level performance can now be achieved in other seemingly intractable A.I. domains."}, {"start": 1984.0, "end": 1992.0, "text": " So the good thing about this paper is that it gave us hope that when something looks so insolvable, when the search space is so huge, as in the case of Go,"}, {"start": 1992.0, "end": 1999.0, "text": " and people thought we'll need additional 10 years to solve it and we solved it in a year or two after that prediction was made,"}, {"start": 1999.0, "end": 2007.0, "text": " this gives us hope that who knows, maybe a couple of years down the road we'll be solving some problems which we now think are uncrackable."}, {"start": 2007.0, "end": 2017.0, "text": " So who knows. Okay, that was the first part. Getting even deeper. The last two pages will get you a really firm grasp and understanding of AlphaGo."}, {"start": 2017.0, "end": 2029.0, "text": " So let's dig into it. Quick note here. Prior to AlphaGo, in order to solve board games, people used this thing called Minimax Search."}, {"start": 2029.0, "end": 2038.0, "text": " And you probably heard of it in your favorite CS class. And then people invented some better heuristics like Depth-first Minimax Search with Alpha-Beta pruning,"}, {"start": 2038.0, "end": 2044.0, "text": " which achieved superhuman performance in chess, checkers, and Othello, but has not been effective in Go."}, {"start": 2044.0, "end": 2053.0, "text": " So after that, people started implementing this thing called Monte Carlo Tree Search without using DNNs."}, {"start": 2053.0, "end": 2063.0, "text": " And basically this one dramatically improved performance in a bunch of different board games as well as in Go in particular,"}, {"start": 2063.0, "end": 2074.0, "text": " but it still wasn't good enough by itself to just push it into the professional league, to push those algorithms into professional level."}, {"start": 2074.0, "end": 2084.0, "text": " Okay, so let's see now every single detail about the search algorithm. So I mentioned the statistics and here are the statistics."}, {"start": 2084.0, "end": 2090.0, "text": " So each edge stores a set of statistics. And here we can see the prior. So that's the thing we calculate using the SL network."}, {"start": 2090.0, "end": 2099.0, "text": " We store the visitation counts for that particular edge. We store the cumulative Monte Carlo estimates coming from the value function and coming from the rollouts."}, {"start": 2099.0, "end": 2108.0, "text": " And finally, we calculate the Q and we store that in each and every edge. And we just calculate the Q using all of these previous statistics."}, {"start": 2108.0, "end": 2119.0, "text": " So, yeah, keep that in mind. I mentioned the P-UCT. So that's the variant of the upper confidence bound algorithm for trees, the ECT."}, {"start": 2119.0, "end": 2127.0, "text": " And this is the exact formulation. So they have something called this coefficient which just weighs this U part compared to the Q part."}, {"start": 2127.0, "end": 2136.0, "text": " So this is the complete equation. And this is just a hyperparameter like your lambda parameter. And they set it to five."}, {"start": 2136.0, "end": 2143.0, "text": " Again, probably hyperparameter search. And here is a prior. Here is the visitation. So we were just missing this part."}, {"start": 2143.0, "end": 2161.0, "text": " So what it means is the following. Let's say we have the parent state and we have the child state. And if we're calculating the P-UCT value for this edge,"}, {"start": 2161.0, "end": 2168.0, "text": " we're basically counting the number of visitations that this child, that his parent had."}, {"start": 2168.0, "end": 2175.0, "text": " So let me now translate this, try and translate this equation into human language. What it basically means is the following."}, {"start": 2175.0, "end": 2190.0, "text": " So the more visitations your parent had and the less times they visited you, but you have a strong prior, that means this edge will be highly likely to visit the next time."}, {"start": 2190.0, "end": 2200.0, "text": " So if we were visiting a lot of the other children of this parent, so that would mean that this numerator part would increase."}, {"start": 2200.0, "end": 2207.0, "text": " But we haven't been visiting this child, that means that this part would be low. So this one is low, this one is high, this will explode."}, {"start": 2207.0, "end": 2214.0, "text": " And then we have the prior, so if it's non-zero and will never be zero, that means eventually we'll want to explore this particular node."}, {"start": 2214.0, "end": 2221.0, "text": " So that's the exploration versus the exploitation tradeoff I was mentioning previously. Now you can see every single detail."}, {"start": 2221.0, "end": 2232.0, "text": " And this search control strategy initially prefers actions with high prior probability and low visit count, but asymptotically prefers actions with high action value."}, {"start": 2232.0, "end": 2240.0, "text": " So that's this one. So as I said, this will go to zero. And finally, you'll be just traversing the tree using the action value functions."}, {"start": 2240.0, "end": 2250.0, "text": " Okay. Optimization detail again, the leaf position is added to the queue for evaluation by the value network unless it has previously been evaluated."}, {"start": 2250.0, "end": 2258.0, "text": " So again, we'll just run the leaf node through the value functions only once and that's it, just a small optimization."}, {"start": 2258.0, "end": 2265.0, "text": " One more interesting thing here is this. So they have this concept of a virtual loss. And what it does is the following."}, {"start": 2265.0, "end": 2271.0, "text": " So let's say we have a root node and we traverse some path and we got to a leaf node."}, {"start": 2271.0, "end": 2276.0, "text": " And so because now we have to evaluate this node, right, so we have to pass it through the value network."}, {"start": 2276.0, "end": 2285.0, "text": " So the value network is on some GPU there and we have to do a rollout and that means we'll have to delegate that to some CPU."}, {"start": 2285.0, "end": 2293.0, "text": " So we have some CPU here and basically we'll have some delay before this is calculated, before the game is done."}, {"start": 2293.0, "end": 2304.0, "text": " And before this inference on the GPU is done. So in that time, what we want to do is we want to make sure that the other threads are not exploring this exact same path."}, {"start": 2304.0, "end": 2310.0, "text": " Because remember, Monte Carlo Tree Search has a bunch of simulations going on in parallel."}, {"start": 2310.0, "end": 2316.0, "text": " So there's a bunch of different threads we're trying to calculate and improve upon the estimates of this search tree."}, {"start": 2316.0, "end": 2320.0, "text": " And so we want to discourage them to visit the same trace as this one."}, {"start": 2320.0, "end": 2327.0, "text": " So what we'll do is we'll for each every edge. So these are the states and the connections are the edges."}, {"start": 2327.0, "end": 2337.0, "text": " So basically what we'll do is we'll increase the artificial increase the visitation counts by three, where three is this number of virtual laws."}, {"start": 2337.0, "end": 2353.0, "text": " They use number three and will also decrease the Monte Carlo estimate. So these W values, the cumulative estimates will decrease them by three, which will effectively do the following thing."}, {"start": 2353.0, "end": 2363.0, "text": " So as you can see, looking at this equation, the PUCT equation, because this will get bigger, that means that this term will get smaller."}, {"start": 2363.0, "end": 2371.0, "text": " So U will get smaller and also Q, because Q is calculated by averaging, just a second, so Q, this is Q."}, {"start": 2371.0, "end": 2377.0, "text": " You can see that that's how we calculate and because this part, the cumulative part is smaller, Q will be smaller."}, {"start": 2377.0, "end": 2381.0, "text": " So that means every single of these edges will have smaller probability."}, {"start": 2381.0, "end": 2388.0, "text": " And so the other parallel threads won't be visiting it until we finish up with this value inference and rollout."}, {"start": 2388.0, "end": 2397.0, "text": " Then we'll just kind of counteract this. So we'll add minus three, so we'll delete this and we'll add plus three here."}, {"start": 2397.0, "end": 2406.0, "text": " And we'll finally add the Z estimate, the actual estimate from the rollout, and we'll add the visitation count will be increased by one."}, {"start": 2406.0, "end": 2412.0, "text": " So finally, we have the exact state that we want to be in. So hopefully this was clear enough."}, {"start": 2412.0, "end": 2416.0, "text": " If not, please comment down in the comment section whether this was confusing."}, {"start": 2416.0, "end": 2425.0, "text": " Okay, that was the virtual part of the tree. So at the end of the simulation, the rollout statistics are updated in backward pass through each step,"}, {"start": 2425.0, "end": 2432.0, "text": " replacing the virtual losses by the actual outcome. So you can see we counteract the virtual loss, we increase the visitation count,"}, {"start": 2432.0, "end": 2439.0, "text": " we counteract the virtual loss, and we add the actual rollout outcome. So that's the whole trick."}, {"start": 2439.0, "end": 2447.0, "text": " Okay, this is how the Q is evaluated again. This is 0.5, so we'll have equal contribution coming from the value function,"}, {"start": 2447.0, "end": 2454.0, "text": " averaged over the number of visitations of that particular edge. Same goes for the rollouts, that's how we get the Q."}, {"start": 2454.0, "end": 2464.0, "text": " And that's it. Now, there is more details. Hopefully you find this interesting, because there is a lot of engineering here."}, {"start": 2464.0, "end": 2473.0, "text": " AlphaGo is not a new novel research per se, but the whole engineering pipeline and everything put together is awesome,"}, {"start": 2473.0, "end": 2479.0, "text": " and that's why they achieved the results they did. So I mentioned the prior calculations."}, {"start": 2479.0, "end": 2487.0, "text": " So once we have the leaf and we want to expand it, you basically feed it through an SL policy network."}, {"start": 2487.0, "end": 2496.0, "text": " But the thing is, again, SL policy is on some GPU, so until you get the actual priors, you'll have to wait."}, {"start": 2496.0, "end": 2505.0, "text": " And that's why they have this thing called the tree policy. And we never heard about this policy so far, so this is the fourth policy network."}, {"start": 2505.0, "end": 2510.0, "text": " They only mention it here. And what it does, it provides the placeholders for the priors."}, {"start": 2510.0, "end": 2518.0, "text": " So before we get the actual priors from the GPU, they just put some roughly good priors, not the best ones, so these ones will be higher quality."}, {"start": 2518.0, "end": 2524.0, "text": " So it's a similar thing to this virtual loss. So it's a placeholder before we get the actual results."}, {"start": 2524.0, "end": 2528.0, "text": " And you'll see this pattern repeating in this paper."}, {"start": 2528.0, "end": 2535.0, "text": " Okay. And finally, the priors are computed by the SL policy, and they use this beta to control the temperature."}, {"start": 2535.0, "end": 2543.0, "text": " That means you basically, you know what the temperature does to softmax, so the lower temperature will kind of make it sharper distribution."}, {"start": 2543.0, "end": 2546.0, "text": " So yeah, that's a minor, not that important detail."}, {"start": 2546.0, "end": 2552.0, "text": " Finally, at the end, so it selects the action with the maximum visit count."}, {"start": 2552.0, "end": 2559.0, "text": " And this is less sensitive to outliers than maximizing the action value function, value, okay?"}, {"start": 2559.0, "end": 2565.0, "text": " So basically, that means the following. So we have a route, and we did a bunch of simulations."}, {"start": 2565.0, "end": 2573.0, "text": " So now we have pretty decent statistics and much better approximations to the actual Q values."}, {"start": 2573.0, "end": 2579.0, "text": " And now we have some numbers here. Maybe this edge was visited 32 times. This one was visited only three times."}, {"start": 2579.0, "end": 2586.0, "text": " This one was visited 50 times. So we'll pick up this edge, and that's the action we'll play, and we'll end up with a new state."}, {"start": 2586.0, "end": 2594.0, "text": " And now maybe Lissedol will play the game, and he'll bring us to some other state, and then we'll do the Monte Carlo again."}, {"start": 2594.0, "end": 2600.0, "text": " Okay, that's how the game plays off. Okay?"}, {"start": 2600.0, "end": 2607.0, "text": " But again, some tricks. We want to reuse the tree at subsequent time steps. So that means the following."}, {"start": 2607.0, "end": 2613.0, "text": " So we were calculating this huge tree at this root state here, okay?"}, {"start": 2613.0, "end": 2626.0, "text": " And Lissedol decided to... and we decided to go here. And once we go here, we still have a bunch of simulations that went down and calculated the statistics for this part of the subtree."}, {"start": 2626.0, "end": 2634.0, "text": " We'll just throw away this part, but we'll still have some statistics here, and so we won't have to recalculate those from scratch."}, {"start": 2634.0, "end": 2643.0, "text": " Again, smaller optimization detail. It kind of helps you build up this picture of what it takes to actually make this thing work."}, {"start": 2643.0, "end": 2648.0, "text": " So it's one thing to just say, hey, we're using policy gradients, supervised learning, blah, blah, blah."}, {"start": 2648.0, "end": 2658.0, "text": " But when you actually see what it takes to make this thing work, there's a lot of details, a lot of distributed programming, software engineering, testing, trying out things, experimenting."}, {"start": 2658.0, "end": 2664.0, "text": " So, yeah, just keep that in mind if you don't already know it."}, {"start": 2664.0, "end": 2670.0, "text": " And finally, the match opponent version of the AlphaGo continues searching during the opponent's move."}, {"start": 2670.0, "end": 2680.0, "text": " So that means once we get into the... once Lissedol, for example, is... it's history, we're still calculating."}, {"start": 2680.0, "end": 2687.0, "text": " We're still trying to approximate a better approximation of this. So we're here. We're still building up the Monte Carlo tree search."}, {"start": 2687.0, "end": 2699.0, "text": " So wherever does Lissedol take us to some state, we'll have better approximations of the subtree here because we continued calculating the Monte Carlo... updating the Monte Carlo tree."}, {"start": 2699.0, "end": 2711.0, "text": " And, yeah, again, one more detail. It extends the search if the action maximizing visit count and the action maximizing action value disagree."}, {"start": 2711.0, "end": 2720.0, "text": " So if the Q value and the N value tell you to take different actions, so there is some discrepancy there and we want to improve it."}, {"start": 2720.0, "end": 2728.0, "text": " And so they just keep calculating until they agree. And then we know we have much better estimate and we're more certain that we'll win."}, {"start": 2728.0, "end": 2732.0, "text": " Okay. Those were the most important parts of the AlphaGo."}, {"start": 2732.0, "end": 2740.0, "text": " Now, I'll just wrap this up with a couple more details around the neural networks. And that's it."}, {"start": 2740.0, "end": 2747.0, "text": " We already heard a lot of details about this policy. So it's a linear softmax. That's why it's so fast, two microseconds."}, {"start": 2747.0, "end": 2755.0, "text": " And, again, it was trained on eight million positions. So the huge SL policy was trained on 30 million positions."}, {"start": 2755.0, "end": 2763.0, "text": " This one was trained on less data because it's smaller, less capacity, basically. But it's the same approach to training this one."}, {"start": 2763.0, "end": 2777.0, "text": " And there is some additional heuristics which I won't mention. So just keep in mind that, again, lots of details which go into this once you start really digging deep."}, {"start": 2777.0, "end": 2783.0, "text": " I want to mention symmetries. And what's the thing with symmetries? Well, because the board looks like this."}, {"start": 2783.0, "end": 2796.0, "text": " Let's say, just to mark this orientation like this. So we can have, you can imagine four different rotations you can perform. So maybe you can rotate this thing by 90 degrees and you'll end up in this layout."}, {"start": 2796.0, "end": 2804.0, "text": " And you can also have reflections. So you'll end up with eight different possibilities to feed this into a CNN."}, {"start": 2804.0, "end": 2814.0, "text": " And when they use the raw policy, the RL policy network to play the game, they do the following."}, {"start": 2814.0, "end": 2823.0, "text": " They take all of the eight configurations and they feed that into the policy network and they just average out all the probabilities across those eight configurations."}, {"start": 2823.0, "end": 2832.0, "text": " And they just get a better actually gameplay by doing that, better probabilities, better distributions over actions."}, {"start": 2832.0, "end": 2847.0, "text": " And yeah, just keep that in mind. And also the actual Monte Carlo tree search I was mentioning so far, what it does is makes use of an implicit symmetry ensemble that randomly selects the single rotation slash reflection for each evaluation."}, {"start": 2847.0, "end": 2862.0, "text": " So that means once you get to the leaf node, you'll sometimes take a random element from this group of symmetries and do the actual inference on top of that one."}, {"start": 2862.0, "end": 2877.0, "text": " And they just showed that this improves things. The reason is they actually augmented the data set using all of those eight different elements from that group. So that's the reason they're using it."}, {"start": 2877.0, "end": 2883.0, "text": " They get more data, thus they get better weights and yeah, they use it in the search as well."}, {"start": 2883.0, "end": 2892.0, "text": " So yeah, symmetries, if you didn't expect any symmetries, here they are. I know that Alpha Fold is also using some interesting symmetries."}, {"start": 2892.0, "end": 2901.0, "text": " The paper still hasn't hasn't come out, but I read some blogs and it's probably using some equivalent types of deploying models."}, {"start": 2901.0, "end": 2914.0, "text": " So we'll see that anyways. A bit about computation. I found this interesting. It takes 50 GPUs and you need to train this for three weeks to train the actual the SL policy network."}, {"start": 2914.0, "end": 2919.0, "text": " So that's a lot of compute and that's just the final network without any hyperparameter."}, {"start": 2919.0, "end": 2933.0, "text": " Then we have for the RL policy, they train it for one day on 50 GPUs and finally to train the value network, they have 50 GPUs for one week."}, {"start": 2933.0, "end": 2940.0, "text": " So that's more than a month to train the final configuration of this algorithm. Plus you have the Monte Carlo tree search during the inference."}, {"start": 2940.0, "end": 2944.0, "text": " It's a lot of compute that went into this. Yeah, just keep that in mind."}, {"start": 2944.0, "end": 2953.0, "text": " Okay, let me see if we have some interesting details here. I mentioned this already. So we have the pool of opponents for the RL policy."}, {"start": 2953.0, "end": 2961.0, "text": " So here is a small detail that's probably important. So I previously had only ZT here and that's not exactly correct."}, {"start": 2961.0, "end": 2968.0, "text": " So we're not using that simple version of the policy gradient algorithm. We're using something called Reinforce Policy Gradient."}, {"start": 2968.0, "end": 2978.0, "text": " Here we just, in order to reduce the variance and keep the same bias, we just subtract this thing called the baseline and they're just using the value function."}, {"start": 2978.0, "end": 2989.0, "text": " So basically everything else remains the same. So across every single game and every single step, we average the gradients according to this thing."}, {"start": 2989.0, "end": 3000.0, "text": " And you can treat this as an advantage. Basically, if you won and the value function was maybe 0.8, so that's plus one,"}, {"start": 3000.0, "end": 3008.0, "text": " that means you have a smaller update. So you want to make sure that that action goes up, but like by just a little bit."}, {"start": 3008.0, "end": 3016.0, "text": " So hopefully you have intuitive understanding why this is here. I won't get into the maths. It doesn't change."}, {"start": 3016.0, "end": 3023.0, "text": " It doesn't change the maths. The expectation remains the same. Thus the bias is unchanged. Only the variance is reduced here."}, {"start": 3023.0, "end": 3031.0, "text": " But it's the same thing as you intuitively. It's the same thing as you only had ZT. So if it's easier for you, just ignore the V portion."}, {"start": 3031.0, "end": 3039.0, "text": " I think that's pretty much it. Okay, I've covered everything. There is a lot of things that went into this."}, {"start": 3039.0, "end": 3047.0, "text": " Here are some of the hyperparameters I was using. The threshold was 40. The virtual loss, the part for the P-UCT algorithm,"}, {"start": 3047.0, "end": 3059.0, "text": " the mixing parameter, the temperature for the SL policy. A lot of hyperparameters took a lot of work from a team of people from DeepMind to create this thing."}, {"start": 3059.0, "end": 3066.0, "text": " So yeah, it's pretty awesome. So let me know if you found this video interesting. If you did, you know the drill. Hit the subscribe button."}, {"start": 3066.0, "end": 3074.0, "text": " Click the bell icon to get notified. And see you in the next video. Until next time, keep learning deep."}]