DeepMind's AlphaGo Zero and AlphaZero | RL paper explained
❤️ Become The AI Epiphany Patreon ❤️ ► https://www.patreon.com/theaiepiphany
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬

In this video I cover AlphaGo Zero (and AlphaZero), an agent that learned, through pure self-play and zero human knowledge, to beat all of the best human players and algorithms in Go, Chess, and Shogi.

You'll learn about:
✔️AlphaGo Zero (Mastering the game of go without human knowledge)
✔️AlphaZero (A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play)
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
✅ AlphaGo Zero paper: http://augmentingcognition.com/assets/Silver2017a.pdf
✅ AlphaZero paper: https://arxiv.org/abs/1712.01815
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 

⌚️ Timetable: 
00:00 - AlphaGo lineage of agents
02:35 - Comparing AlphaGo Zero with AlphaGo
06:50 - High-level explanation of AlphaGo Zero inner workings
10:20 - MCTS recap
12:00 - Training details and curves
15:10 - Architecture impact
17:30 - Knowledge acquired
20:55 - Results
22:05 - Discovering joseki
23:40 - Human domain knowledge in AlphaGo Zero
25:30 - Pipeline overview
28:40 - Self-play thread explained
31:55 - Further details (PUCT recap, etc.)
35:50 - AlphaZero (what's new?)

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
💰 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/
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬

#alphagozero #alphazero #deepmind
 What's up in this video? I'm going to cover the AlphaGo Zero paper or mastering the game of go without human knowledge And I also cover the AlphaZero paper I'll actually tell you some of the modifications that are needed to get this thing to AlphaZero level and Just a hint. It's a really small modification and basically reapplying this to chess and shogi as well So what's the trick with this paper? And hopefully already watched my previous video on AlphaGo if you haven't I strongly recommend you go ahead and watch it I'll link it somewhere here Basically, the main thing is they are not using human experts data anymore So they say it here here we introduce an algorithm based solely on reinforcement learning without human data Guidance or domain knowledge beyond game rules starting tabula rasa or blank slate in Latin our new program AlphaGo Zero Achieved super superhuman performance winning hundred to zero against the previously published champion defeating AlphaGo agent so a Small digression here if you're not familiar with this Basically AlphaGo is a lineage of agents even though they published these two papers or actually three and then later a mu zero There were a couple more iterations in between so it's kind of a spectrum and let me just kind of explain how that functions So the previous paper The AlphaGo paper was actually AlphaGo fan Because that's the model that defeated fan who we the European champion in go back in 2015 Then they had AlphaGo Lee Which defeated Lee Sedol back in 2016 And that's the the famous match where Lee Sedol lost 4 to 1 and that was the first time that An agent and like an algorithm could defeat the grandmaster in go and finally they built something called AlphaGo master Which basically won 60 to 0 Against all of the best grandmasters in go in 2017. I think and finally we're here AlphaGo zero which Yeah, which is basically that the best iteration so far in the only version that's not using human experts knowledge So going from here to here. It's a kind of a spectrum where the amount of the amount of compute like the both the efficiency of the algorithm was improved as well as the amount of Hard-coded data and heuristics was kind of slowly going down. So finally zero doesn't use the human data and Is much more efficient. So yeah, that's the paper will be reviewing in this in this video anyways So let me see what the differences are between this paper and the AlphaGo paper The first one is so first and foremost it is trained solely by self play RL at that means if you remember from the previous video that we won't be having these networks anymore So the SL policy is gone because this one was trained on the human experts data. The faster law policy is also gone So those were the two tasks that were Leveraging the human experts data and we're left with these two, but let's see what what else is different So second it uses only the black and white stones from the board as input features. So that means we're not using anything Additional heuristics and hand crafting of these these features. We're just using the raw board data And we just take a couple of those because we need some prehistory in order to play this game optimally And that's the only thing so we're basically using raw board data and that's it. No, no, no hand crafting No domain knowledge integrated there third. It uses a single neural network rather than separate policy and value networks So that means we're basically merging these two together So we'll be adding this will be combining somehow these two Into a single network and finally it uses a simpler tree search That relies upon the single neural network to value positions and sample moves without performing any montecarlo rollouts So again, if you remember from alpha go paper when we were doing the montecarlo tree search And we got to the leaf position So this is some state and we basically did two things one Was to pass the state into a value network. The second thing was to do a rollout Basically playing the game until the end with this fast rollout policy. So basically with this thing And we'd get some value then we'd Back Back propagate those two information so that both the value and the rollout outcome up the tree Basically, we don't have we don't have this anymore and that's the the new modification that they introduced So it's much simpler. So if you take a look at it This thing is so much simpler in every aspect. We don't have this we merge these two together and the MCTS algorithm is simpler so and we also achieve much better results. So that's quite impressive if you ask me Okay, hopefully you got some intuition of the differences between alpha go zero and alpha go so let's continue So let's see what the output from the network actually is. So basically it's a tuple we have the policy Vector and we get the value scalar Coming from the from the network. So the vector of move probabilities p represents the probability of selecting each move a Including the pass. So additionally if you take a look at the alpha go implementation I think they didn't have the the pass move So they just had the output vector of the policy vector was just 19 by 19 The output vector of the policy vector was just 19 by 19 flat flat vector. So basically 361 Dimensional vector and here we have uh, plus one for the pass move Additionally, we have the the value part of the network Combined together. So if you take a look how this looks like you basically have something like this This is some kind of a cnn and then we have Uh two streams coming off on top of this. So this thing is the policy part and then we have the the value network So this is our new model. Hopefully this is uh clear enough and additional detail is they're using Resonance instead of cnn's so previously in alpha go they were using plain old Convolutional neural networks now they're using resonance and hopefully you're all familiar with those so basically what resonance did is they uh, just kind of um added this residual connection which will be Which will add the feature maps from the previous layer on top of the process features And they show that by adding this small trick they can train much deeper Naprox and this was a one of the major points in the deep learning history So yeah, they they are now using resonance instead of cnn's pure cnn's Okay Okay, uh, let's slowly start digging into how the actual uh algorithm works and basically the I'll be stressing the differences with alpha go Many things overlap. So yeah Okay, so the main difference, uh in the training procedure is that they integrated the mcts directly into the training and they're not using it just for the uh During the play so basically this is how the network is trained. So you have a self-play game So take our our own agent. Uh, you take the The basically that's the uh, the network that has both the policy and the value and you just roll out the game until the end state Now this is the trick So in this state, uh, you you pass it into the network It outputs the probabilities and the so this is kind of the probability vector and the the value scalar So now instead of just picking the action directly from this output What I do is they uh Do the mcts over this state so this is Depicted here and they actually pick the action from this probability distribution, which is much better Prediction than the raw probability prediction from the directive from the network so Uh after just picking the action we get into a different state We again do the mcts and we roll out all of these Uh until the end and we're just saving this this tuple. So the data for each time step t is stored as state Policy, so that's the this vector here. We're storing this one and we're storing the outcome. So the basically the The end result basically either plus one if the player won or minus one if it lost So this is basically the main trick doing the mcts during the actual self-play once we have that what we do is we in order to train the The agent we do the following We take those tuples that we stored and we want to make sure that the output from the raw network So the policy vector that comes directly from the network Gets as close to the mcts policy as possible Secondly, we just regressed the value function so as to be really close to the final outcome of that particular game so Basically, here is the equation you can see We do a simple regression doing mean square error for the value function and we do the simple simple cross entropy loss here, so this has a minimum so the p vector is the probability coming from the raw network the pi is the Probability coming from the mcts and we want to make sure that the probability coming from the raw network is as close as possible To pi and that's the minimum of this function. So basically that's when we hit the entropy limit Before that we have the non zero k l divergence and once we get to To the same to once p becomes equal to pi we have zero k l and we converge to a minimum So basically that's why this thing Pushes p to be close to pi. Finally, the third term is just basically l2 regularization and And that's it. It's pretty simple. It's much simpler than alpha go And yeah, let's see what I see here So the neural network parameters theta are updated to maximize the similarity of the policy vector p To the search probabilities p pi and to minimize the error between the predicted winner V and the game winner z as for the montecarlo tree search a short recap how it works Basically, they're using the again the p uct algorithm. So the upper confidence bound for trees algorithm again Basically start from the root state and you pick the values so as to maximize this p uct score So the q value the action value function plus this u term which consists of which has this visitation term inside and priors and picking the highest ones they get to the leaf node and finally Uh in the case of alpha go zero, they don't have the uh, actually the expanding threshold which was around 40 In alpha go they just uh expand the network every single time so once you get to the leaf you just expand it and basically what it means is you you pass that state into the network and it will output the probability vector and the value and you'll be back propping that um, basically back upping the the value function up the tree and you'll be using the p as the priors for the next uh Nodes in the in the tree. So basically next time if one of the threads comes here, it will pick up one of those of these Children depending on the again on the p uct score So maybe come here it will again expand this one and that's how we actually build up this montecarlo tree search And hopefully that that was also already clear from the previous video So here just depicted that the value function is back propped back backed up, uh up the tree and they're updating the statistics both the visitation counts as well as the Basically the the montecarlo estimates Okay That's that's it That's it. And um, so they said here over the course of training 4.9 million games of self play were generated using 1600 simulations for each mcts which corresponds to approximately 0.4 second Thinking time per move. So that means when you're building up these trees during the the self play you do these you do 1600 of these simulations in order to build a tree and then you pick the The action that actually maximizes the visitation count in the root node They have some temperature coefficient, but we'll get to that a bit later. Basically, that's it Okay, let's continue And after doing this training Surprisingly the alpha goes zero outperform the alpha goalie after just 36 hours So you can see it here after just 36 hours Basically, it's already better than the agent that that has beaten at least it all back in 2016 And that's impressive And they said here the alpha goalie was actually trained over several months So a lot of compute went into this thing. So yeah, keep that in mind Alpha goes here. I use a single machine with four tpus Whereas alpha go Lee was distributed over many machines and used 48 tpus Alpha go zero defeated alpha go Lee 100 to zero So that's some serious performance that we got from this pure self-reinforced learning approach And that's amazing again. You can see the curves here the Dotted line here is the the lee method The the purple one is actually the same architecture as as the Alpha go zero but just using the human experts data and you can see it can't achieve the elo score As high as alpha go zero Okay looking at this curve here Uh, we're trying to see how good these networks both the alpha go zero as well this supervised learning network How good are they? predicting the actual moves that human experts will make and you can see that the supervised method is actually better here and that shouldn't surprise you because The goal for alpha go zero is not to be better at predicting human experts move It's to be the best agent the best player and that doesn't necessarily correlate with human play And we'll see that exactly happening a bit later where alpha go zero discover certain joseki's So those are some corner sequences in go they weren't discovered by by humans prior to this agent So that's that's awesome. Um, and we can see it here actually looking at the emcee of professional game outcomes, so the uh Of alpha go zero is much better at predicting the final outcome of the games than the supervised approach so that means if you're in a particular state and we just um, Basically pass it through the the network. It will be better at predicting the final outcome in those games played by humans than the sl Network. So yeah, this is actually more important than this chart keep that in mind Okay Aside from that they try to decouple the The the the contribution that came from the algorithm and what came from the actual architecture improvement because they're using resonance if you remember So looking at these charts here, um, the the leftmost This leftmost network is actually a dual Resnet meaning dual is because we have a single architecture that outputs both the policy as well as the value and here we have the Cep conf that's basically single network for both policy and for the value network So that's something alpha go used and it's using the simple cnn instead of resonant and you can see that the elo rating Uh goes up. So everything else is pretty much the same And we get a huge boost just from the architecture And these are the other combinations. So just using separate resonants and using dual architecture, but with cnn's Um similarly looking at the prediction accuracy of the human players This one is actually a bit worse by looking at the msc of the game. So just predict regressing the outcome This one is the best and finally this architecture gave them the best results. So that's what they're using um, okay um One more detail, uh, they say here this is partly due to improved computational efficiency But more importantly the dual objective regularizes the network to a common representation that supports multiple use cases So the idea here is the following so you have a cnn And since you're training the policy, so this is the policy vector here and this is the value scaler so when you just do your gradient update of your network for the To get closer to the mcts Um, uh probability vector you're updating these features, but these features are subsequently used by the value stream here and so basically whatever you do you're improving both the value and the policy and your You're basically figuring out the features which are Good for figuring out both the policy and the value and that helps that helps boost the performance Okay Uh, let's see some of the knowledge that this network learned during this training and In this chart what you can see in the top row here are some of these joseki as I mentioned and I don't know How to play go but I know enough to just kind of understand what's happening But if you're familiar with go, maybe this will be even more interesting for you Basically here you can see These are the joseki's that humans play and you can see that the alpha go zero actually reinvented these At some time during the training So this first joseki was discovered like maybe around 10 hour mark Then the second one was discovered. I don't know like maybe 15 hours and the last one was discovered Maybe around 36 hour mark And that's super fun and we'll later see how the frequency was increasing So at one point of the training it was heavily using one of these joseki's and then it kind of just ditched them away Because they were actually worse It found some better patterns and started using those in the second row What we can basically see are the joseki's which were the most frequent joseki's at that part of the training time frame So basically if you take a look at I don't know maybe this one so around the 48 hour mark It was heavily using this particular pattern and yeah, and finally the the last row tells you Basically shows you the games. So these are just so we take this Maybe three hour mark. We take the one particular self play game and we just Plotted here and you can see how it evolved So here it was it was playing really greedy and clustering all of the moves the black and the whites In the same region of the of the board and as the game progressed we came to these More subtle again. I'm not I don't understand go but I was after reading the paper. I understand this So basically here it's leading multiple battles battles distributed across the board and it's much better Player now after 70 hours than at the beginning So those were some of the knowledge that the alpha zero basically rediscovered and that's pretty damn impressive If you ask me Okay, let's continue and uh see what's up here Okay, so they say here ultimately alpha go zero preferred new joseki variants that were previously unknown I mentioned that already so that's pretty much fascinating. Uh, surprisingly this letter capture sequence Um is one of the first elements of go knowledge learned by humans But they were only understood by alpha go zero much later in training and that's cool because that suggests also that Uh, it's not constrained by any way by the human priors and knowledge So it actually discovered something that was obvious to humans much later But it also discovered some things that were not obvious to humans And that's awesome And they say here the humankind has accumulated go knowledge from millions of games played over thousands of years years collectively distilled into patterns Proverbs and books in the space of a few days starting tabula rasa. So blank slates totally random Alpha go zero was able to rediscover much of this go knowledge as well as novel strategies that provide New insights into the oldest of games and they're just romanticizing here a bit. Okay basically Uh, it's pretty awesome and looking at the charts. Uh, you can see that the Uh alpha go zero, uh Beats alpha go lee after just a couple of uh Days and then starts being better than this alpha go master version after 30 something days Again, uh some similar chart here Uh, basically this is the alpha go zero performance. This is the master the lead the the fan um Uh models and finally we have some commercial go programs which you can see are much worse than even the alpha go fan And then we have this, uh Basically open source go program which is even worse Finally this one is basically the the raw network performance So without using the mcts by just using the probabilities coming from the policy network, uh and playing using that one, uh, you get That much much lower elo score than using mcts. So search is really important for playing go efficiently. Okay That's it that was the high level overview I wanted to show you and now we'll get into some details But before that let me just show you those jiseki's I was mentioning. So here Um, so this is some jiseki. That's um, the humans play a lot So it's even has a name five three point press whatever and you can see the frequency here And similarly for other jiseki's and you can see for some patterns. So this like knight's move pincer the frequency Peaked here and then slowly decreased after 70 hours of training So that means it was discovering and ditching the patterns. So that's cool Um, this is the the the second chart shows you Um some of the jiseki's that was playing really often at one point of training So again here three by three invasion. It had a peak here. So it was playing this this Particular jiseki a lot at one point of time and so on and so forth So that's that's it Now let's dig into the details of the actual algorithm. Okay, so i've covered this part already This is a spectrum I was mentioning so they went from fan to lee to master and finally to alpha go zero Uh, and each time increasing the both the efficiency. So this one used 176 gpus Then the lee version I think used something around 47 tpus Then they had uh alpha go master which used even less hardware and finally alpha go zero actually uses only four tpus And it's much better as you saw than lee and and master and every version So far, um, and yeah, they say here Okay, so uh, basically They say it here. The primary contribution is to demonstrate that superhuman performance can be achieved without human domain knowledge We reiterated that already a couple of times To clarify this contribution we number the domain knowledge that alpha go zero uses explicitly or implicitly Either in its training procedure or its mcts These are the items of knowledge that would need to be replaced For alpha go zero to learn a different alternating markov game And this is the main point where basically after you just kind of Modify a couple of these you get to alpha zero and you can play both the chess and shogi as well as go And uh the most important parts here. So basically you will want to Um ditch the symmetry part So the rules of go are invariant under rotation and reflection this knowledge has been used in alpha go zero Both by augmenting the data set during training to include rotations and reflections of each position So if you remember from the alpha go video Basically each time you want to evaluate a position you take a random Uh element from the dihedral group that has eight elements So basically because you have two reflections and four rotations you get to eight elements and you were just using those and that will Make your data bigger and also They showed it improves the training So we'll have to uh expel that part because other games such as chess they don't have That symmetry as as inherent part of the game Okay Some details here. So the montecarlo tree search parameters some bayesian optimization was used To figure those out and this is a really important part So alpha goes your self-play training pipeline consists of three main components So the first thing is neural network parameters are continually optimized from recent self-play data That's the first part Uh and alpha go zero players are continually evaluated. That's the second part and thirdly the best performing player so far This alpha theta star is used to generate new self-play data and let us see how that exactly works so So, um, you basically have something like a replay buffer and I i'll draw it like this you have the Current best network and i'll just draw it like a box and we have a bunch of self-play games happening in parallel so how the actual framework works like is the following so We have this Network and that's the best agent so far and we're just taking data from the replay buffer And we are updating that network Next up every every thousand, um updates will be dumping a checkpoint Model and we'll be comparing that checkpoint model with the last previously stored best model So we have the this thing they call alpha theta star So that's the best agent and interesting fact is that this agent so let me draw it like a like a rectangle Basically, they use those weights in all of these self-play threads. So when I knew when one of these Self-playing threads finishes, uh, it will want to start over again So we'll just pull the best parameters here And it will be using that network weights to play the game and store it will be storing The tuples so we we mentioned so the s The pi and the outcome of the game so those tuples will be stored back in these in the storage So that's how the dynamics of the whole pipeline works um So I haven't finished this part. So once uh, we we dump the checkpoint What we want to do is we want to do evaluation and basically what they did is they play 400 games between this checkpoint and between the best model and whichever model wins. That's the the model will be using For all of the next self-play game. So the next self-play thread So if this one finishes and wants to start over again, it will just pull the the newest the best parameters And it will start playing the game So that's roughly how this thing works. And now let's Let's see some details they said here again the optimization process produces a new checkpoint every thousand training steps If the new player wins by a margin of over 55 Then it becomes the best player and is subsequently used for self-play generation and also becomes the baseline for subsequent comparisons So I mentioned that part already and it's playing 400 games To we are playing 400 games between the checkpoint and the best model in order to figure out whether it's statistically significantly Better than the whether the checkpoint is better than the best model so far Okay, so now that we have the best player, let's see how we can use those weights in order to play these self-play games So the best current player alpha theta star as selected by the evaluator is used to generate data In each iteration alpha theta star plays 25 000 games of self-play And it uses 1600 simulations of mcts to select each move. Okay Um, let me draw it here Basically, this is the self-play thread and it just fetches the the newest weights from the alpha theta star And they say here for the first 30 moves of each game the temperature is set to one This selects moves proportionally to their visit count in mcts ensures a diverse set of positions are encountered That means if this is the initial state of the self-play game, so that's the initial board state Uh, we play for the first 30 steps. So this is 30 Um, we play uh using proportional sampling. That means the following So if I just zoom in into this state, so this is some state state zero in this particular case and once we do the mcts And we find the probabilities we'll be using uh, we won't be doing a greedy sampling will be Uh, a greedy policy will just uh take the proportional sampling. So if we have something like this maybe uh Some distribution like this one. That means this action will be taken the most often because it has the highest probability So that's for the first 30 states and that ensures that we have some kind of because we're constantly using the same model This ensures we are having uh some uh diversity in the initial positions. Okay So that's the first part and then we start playing from this point on we start playing Uh greedy because the temperature goes to zero and that means uh, whatever that so that means this one will get transformed into this All of these will be zero. So that's zero. That's zero. This one will be one So we'll be picking the the highest probability always Okay So then they say the following additional exploration is achieved by adding dairy clay noise to the prior probabilities in the root node As zero so if we take certain state here Uh, and we zoom in again and before we even start building the mct mcts3 what they'll do is they'll add the Noise into the root priors themselves. So once the once we get the initial priors those will get uh by passing the the state into the um our Model into the network, uh, we'll modify these priors using the dairy clay noise which will ensure there is some randomization in how do we visit the uh, the how to explore the mcts3 and that will explore there will additionally enable us to have a diverse set of tuples which will be fed back into the storage into the replay buffer Which again is used by the currently best network to update its weights And that's that's pretty much it. Um Um, this is something you should know from previous video. Basically, we're storing statistics of visitation counts cumulative mc montecarlo estimates the action value function and the priors Okay uh here Puct we saw this one. So basically depending on the visitation counts the more you visit some state the smaller the u becomes and basically that means uh You depend on the action value function to decide whether you want to Uh pick that edge or not Okay Additional detail positions in the queue are evaluated by the neural network using a mini batch size of eight The search thread is locked until the validation completes So this is a bit different compared to the alpha go model because it used to use a synchronous policy here on the other hand What this means is basically on the gpu you have so this is a gpu You have the network and you just make a queue here um, and it has eight slots and basically you need to wait for the eight threads to reach the final the leaf node and to push it here and then We'll just you know in a single batch will produce the the priors as well as the values and then Only then will the those threads resume so they are kind of synchronous. So that's A detail that's that's new to alpha go zero Uh, they also they they continue using this virtual loss, which if you remember If we had some uh So this is the the root of the mcts. This is the leaf basically, uh the virtual loss will make sure that these visitation counts are So these are the states and the squiggly lines are the actions Uh, it will just uh, maybe do minus three on all of the states Uh for the visitation and that will reduce the u part of the key of the of the puct which means All of the other threads which are building up the mcts tree Will be less likely to take this exact route to the leaf node And that's that's the whole point because we're already exploring this one We just have this virtual loss thing which uh discourages other threads to explore the same path Okay, finally, um We're using exponentiated visit count Uh, basically, so this is the visitation counts and this is the temperature coefficient which we were mentioning. So the first 30 Moves are are being played Proportionally and then this temperature drops to zero which makes sure that we're just picking the highest probability action Okay Let's summarize this the principal difference Differences are that alpha goes zero does not use any rollouts It uses a single neural network instead of a separate policy and value networks Leaf nodes are always expanded so there is no threshold We don't have to wait until maybe 40 or something which was dynamically computed so that the gpus are not starving some optimization stuff And so we just expand it as soon as we encounter a leaf node We expand it and each search thread simply waits for the neural network evaluation. So it's synchronous Rather than performing evaluation and backup asynchronously And also there is no tree policy, which if you remember just I used to set up priors So when we get to a leaf node, we used to use the tree policy which will set some fast priors And we would send the leaf node onto gpu where the policy network SL policy would wait and it will it will do an inference and calculate the actual priors which will then get swapped here But here so but so this is basically a placeholder network and we don't have it anymore So much less details actually, it's it's an easier algorithm. We're just using reinforcement learning and we got better results Okay Hopefully you got something out of this and now I just want to make it Clear what the differences are between this model and the alpha zero. So that's just a small additional step if you ask me Um, I don't think there was anything significant that happened there Okay here here here is it basically? There's just a couple of differences And I don't quite understand the first one. So they say alpha zero instead estimates and optimizes the expected outcome Taking account of draws or potentially other outcomes. So this part bugs me because um the alpha goes zero estimates the value so the value function estimates between plus one and minus one which where plus one means This player is going to win and minus one means we are certain we're going to lose Um, and so i'm not quite sure what they mean by that If you know, please leave a comment down there and the second one is obvious So the rules of chess and shogi are asymmetric. So in general symmetries cannot be assumed So that's something I already mentioned We want to get rid of that of that of picking uh, like an element from the dihedral group one of those eight Reflections rotation combinations, so we just want to ditch that and uh, they showed that they won't hurt the performance at all So yeah, um A little bit but we can compensate by compute Okay And the third thing is in contrast alpha zero simply maintains a single neural network that is updated continually Rather than waiting for an iteration to complete Self play games are generated by using the latest parameters for this neural network omitting the valuation step And the selection of best player. So that means this time we have this network and instead of uh Doing these these periodic check pointing and comparing for the best model We are continuously using this same weights and we're updating them using the Replay buffer and the threads are just filling that buffer and we are just taking the data and we're continually updating this agent And when a new thread resumes so this one finishes and wants to start over again It will just fetch the newest the current the only pair of weights we are we are continually updating. Okay? So that's the third difference. So not a lot there and okay and um You can see the results Here basically on chess they compared against the stockfish That was the best engine at the time and you can see after Sometime it gets better than stockfish Finally, we have shroggy here in a small amount of time. The model gets better than shroggy, which is a japanese chess affectionately known as japanese chess and Finally we get better from alpha go zero after some training as well So what's interesting on these three charts if you ask me is this one so You can see how small the gap the elo gap here is and that just kind of indicates the amount of effort like decades of research of chess because chess was considered as the drosophila of AI because So many people so many researchers spent so much time researching it and so there are so many good heuristics in Good heuristics and a hand crafting that went into creating this stockfish engine that it was kind of hard to get much better than it So that's that's funny um, okay, the the only thing that's actually um, not so uh, Game agnostic is this so they are still adding the noise to the prior policy to ensure the exploration So directly noise I mentioned in the alpha go zero Um, and it's uh scaled in proportion to the typical number of legal moves for that game type So that's something that's game specific other than that. This is a pretty generic algorithm and yeah uh I think worth noticing here is that you have to train a single Instance a single agent for every specific game So that means this still doesn't generalize as much as we'd like it to so optimally you can train for alpha for go And then just kind of fine tune it for chess and it would be Uh really good, but that's not the case and you have to train it from scratch pretty much to the best of my knowledge um one thing worth noticing as well is that alpha zero searches just 80,000 positions per second in chess and 40,000 in shogi compared to 70 million for stockfish and 35 million for elmo So that just shows uh that this approach is much less brute force and these two the the elmo and stockfish Are much more similar to deep blue which used a brute force. Um algorithm to beat garry casparro back in 97 So they say arguably a more human-like approach to to search and to to playing the games and I agree um So that's that's pretty much everything you need to know from alpha zero paper once you know Uh once you understand the alpha go and alpha go zero so ditch the symmetries keep continually updating the agent Um, and then you just kind of map for the specific rules You can you kind of do some small adaptations you apply the same algorithm and as you can see after some training time You can get that you can achieve state of the art on all the three benchmarks That was it for this video If you have any feedback whatsoever on the things I could improve, please feel free to just comment down in the comment section And i'll read those and you know the drill just hit that subscribe button hit the bell icon to get notified and until next time Keep learning deep
[{"start": 0.0, "end": 5.34, "text": " What's up in this video? I'm going to cover the AlphaGo Zero paper or mastering the game of go without human knowledge"}, {"start": 5.34, "end": 7.7, "text": " And I also cover the AlphaZero paper"}, {"start": 7.7, "end": 14.6, "text": " I'll actually tell you some of the modifications that are needed to get this thing to AlphaZero level and"}, {"start": 15.46, "end": 20.34, "text": " Just a hint. It's a really small modification and basically reapplying this to chess and shogi as well"}, {"start": 20.6, "end": 22.76, "text": " So what's the trick with this paper?"}, {"start": 22.96, "end": 28.46, "text": " And hopefully already watched my previous video on AlphaGo if you haven't I strongly recommend you go ahead and watch it"}, {"start": 28.46, "end": 30.12, "text": " I'll link it somewhere here"}, {"start": 30.12, "end": 33.8, "text": " Basically, the main thing is they are not using human experts data anymore"}, {"start": 33.8, "end": 39.28, "text": " So they say it here here we introduce an algorithm based solely on reinforcement learning without human data"}, {"start": 39.6, "end": 47.2, "text": " Guidance or domain knowledge beyond game rules starting tabula rasa or blank slate in Latin our new program AlphaGo Zero"}, {"start": 47.84, "end": 55.94, "text": " Achieved super superhuman performance winning hundred to zero against the previously published champion defeating AlphaGo agent"}, {"start": 55.94, "end": 57.94, "text": " so a"}, {"start": 57.94, "end": 60.46, "text": " Small digression here if you're not familiar with this"}, {"start": 60.879999999999995, "end": 68.0, "text": " Basically AlphaGo is a lineage of agents even though they published these two papers or actually three and then later a mu zero"}, {"start": 68.67999999999999, "end": 76.36, "text": " There were a couple more iterations in between so it's kind of a spectrum and let me just kind of explain how that functions"}, {"start": 76.36, "end": 78.16, "text": " So the previous paper"}, {"start": 78.16, "end": 80.92, "text": " The AlphaGo paper was actually AlphaGo fan"}, {"start": 80.92, "end": 86.1, "text": " Because that's the model that defeated fan who we the European champion in go back in 2015"}, {"start": 86.1, "end": 88.1, "text": " Then they had AlphaGo Lee"}, {"start": 89.14, "end": 92.94, "text": " Which defeated Lee Sedol back in 2016"}, {"start": 93.58, "end": 99.9, "text": " And that's the the famous match where Lee Sedol lost 4 to 1 and that was the first time that"}, {"start": 100.46000000000001, "end": 109.3, "text": " An agent and like an algorithm could defeat the grandmaster in go and finally they built something called AlphaGo"}, {"start": 109.3, "end": 111.3, "text": " master"}, {"start": 111.3, "end": 114.3, "text": " Which basically won 60 to 0"}, {"start": 115.02, "end": 122.82, "text": " Against all of the best grandmasters in go in 2017. I think and finally we're here AlphaGo zero"}, {"start": 123.62, "end": 124.66, "text": " which"}, {"start": 124.66, "end": 130.74, "text": " Yeah, which is basically that the best iteration so far in the only version that's not using human experts"}, {"start": 131.46, "end": 132.66, "text": " knowledge"}, {"start": 132.66, "end": 138.1, "text": " So going from here to here. It's a kind of a spectrum where the amount of"}, {"start": 138.1, "end": 144.42, "text": " the amount of compute like the both the efficiency of the algorithm was improved as well as the amount of"}, {"start": 144.9, "end": 151.22, "text": " Hard-coded data and heuristics was kind of slowly going down. So finally zero doesn't use the human data and"}, {"start": 151.78, "end": 156.26, "text": " Is much more efficient. So yeah, that's the paper will be reviewing in this in this video"}, {"start": 157.06, "end": 159.06, "text": " anyways"}, {"start": 159.06, "end": 162.9, "text": " So let me see what the differences are between this paper and the AlphaGo paper"}, {"start": 163.38, "end": 166.82, "text": " The first one is so first and foremost it is trained solely by"}, {"start": 166.82, "end": 173.38, "text": " self play RL at that means if you remember from the previous video that we won't be having these networks anymore"}, {"start": 173.38, "end": 179.62, "text": " So the SL policy is gone because this one was trained on the human experts data. The faster law policy is also gone"}, {"start": 179.62, "end": 181.62, "text": " So those were the two tasks that were"}, {"start": 182.42, "end": 188.01999999999998, "text": " Leveraging the human experts data and we're left with these two, but let's see what what else is different"}, {"start": 188.01999999999998, "end": 193.78, "text": " So second it uses only the black and white stones from the board as input features. So that means we're not using anything"}, {"start": 193.78, "end": 199.14000000000001, "text": " Additional heuristics and hand crafting of these these features. We're just using the raw board data"}, {"start": 199.86, "end": 205.7, "text": " And we just take a couple of those because we need some prehistory in order to play this game optimally"}, {"start": 206.02, "end": 211.14, "text": " And that's the only thing so we're basically using raw board data and that's it. No, no, no hand crafting"}, {"start": 211.14, "end": 217.54, "text": " No domain knowledge integrated there third. It uses a single neural network rather than separate policy and value networks"}, {"start": 218.34, "end": 221.46, "text": " So that means we're basically merging these two together"}, {"start": 221.46, "end": 224.26000000000002, "text": " So we'll be adding this will be combining somehow these two"}, {"start": 225.06, "end": 229.22, "text": " Into a single network and finally it uses a simpler tree search"}, {"start": 229.38, "end": 236.18, "text": " That relies upon the single neural network to value positions and sample moves without performing any montecarlo rollouts"}, {"start": 236.66, "end": 242.5, "text": " So again, if you remember from alpha go paper when we were doing the montecarlo tree search"}, {"start": 242.82, "end": 244.82, "text": " And we got to the leaf position"}, {"start": 244.82, "end": 248.74, "text": " So this is some state and we basically did two things one"}, {"start": 248.74, "end": 253.70000000000002, "text": " Was to pass the state into a value network. The second thing was to do a rollout"}, {"start": 254.10000000000002, "end": 258.90000000000003, "text": " Basically playing the game until the end with this fast rollout policy. So basically with this thing"}, {"start": 259.62, "end": 262.5, "text": " And we'd get some value then we'd"}, {"start": 263.62, "end": 264.34000000000003, "text": " Back"}, {"start": 264.34000000000003, "end": 270.34000000000003, "text": " Back propagate those two information so that both the value and the rollout outcome up the tree"}, {"start": 270.66, "end": 275.78000000000003, "text": " Basically, we don't have we don't have this anymore and that's the the new modification that they introduced"}, {"start": 275.78, "end": 279.05999999999995, "text": " So it's much simpler. So if you take a look at it"}, {"start": 279.61999999999995, "end": 285.53999999999996, "text": " This thing is so much simpler in every aspect. We don't have this we merge these two together and the"}, {"start": 286.34, "end": 293.53999999999996, "text": " MCTS algorithm is simpler so and we also achieve much better results. So that's quite impressive if you ask me"}, {"start": 294.58, "end": 302.02, "text": " Okay, hopefully you got some intuition of the differences between alpha go zero and alpha go so let's continue"}, {"start": 302.02, "end": 308.41999999999996, "text": " So let's see what the output from the network actually is. So basically it's a tuple we have the policy"}, {"start": 309.38, "end": 311.62, "text": " Vector and we get the value scalar"}, {"start": 312.18, "end": 317.7, "text": " Coming from the from the network. So the vector of move probabilities p represents the probability of selecting each move a"}, {"start": 318.18, "end": 322.26, "text": " Including the pass. So additionally if you take a look at the alpha go implementation"}, {"start": 322.41999999999996, "end": 324.41999999999996, "text": " I think they didn't have the the pass move"}, {"start": 324.41999999999996, "end": 328.9, "text": " So they just had the output vector of the policy vector was just 19 by 19"}, {"start": 328.9, "end": 335.14, "text": " The output vector of the policy vector was just 19 by 19 flat flat vector. So basically 361"}, {"start": 337.46, "end": 342.73999999999995, "text": " Dimensional vector and here we have uh, plus one for the pass move"}, {"start": 344.17999999999995, "end": 347.21999999999997, "text": " Additionally, we have the the value part of the network"}, {"start": 347.85999999999996, "end": 352.73999999999995, "text": " Combined together. So if you take a look how this looks like you basically have something like this"}, {"start": 353.38, "end": 356.41999999999996, "text": " This is some kind of a cnn and then we have"}, {"start": 356.42, "end": 363.62, "text": " Uh two streams coming off on top of this. So this thing is the policy part and then we have the the value network"}, {"start": 363.62, "end": 369.78000000000003, "text": " So this is our new model. Hopefully this is uh clear enough and additional detail is they're using"}, {"start": 370.40000000000003, "end": 374.74, "text": " Resonance instead of cnn's so previously in alpha go they were using plain old"}, {"start": 375.28000000000003, "end": 379.46000000000004, "text": " Convolutional neural networks now they're using resonance and hopefully you're all familiar with those"}, {"start": 379.54, "end": 384.42, "text": " so basically what resonance did is they uh, just kind of um"}, {"start": 384.42, "end": 387.46000000000004, "text": " added this residual connection which will be"}, {"start": 388.26, "end": 392.98, "text": " Which will add the feature maps from the previous layer on top of the process features"}, {"start": 393.38, "end": 397.38, "text": " And they show that by adding this small trick they can train much deeper"}, {"start": 397.70000000000005, "end": 402.34000000000003, "text": " Naprox and this was a one of the major points in the deep learning history"}, {"start": 403.38, "end": 407.78000000000003, "text": " So yeah, they they are now using resonance instead of cnn's pure cnn's"}, {"start": 408.74, "end": 409.94, "text": " Okay"}, {"start": 409.94, "end": 415.78, "text": " Okay, uh, let's slowly start digging into how the actual uh algorithm works and basically the"}, {"start": 416.34, "end": 418.66, "text": " I'll be stressing the differences with alpha go"}, {"start": 419.3, "end": 421.3, "text": " Many things overlap. So yeah"}, {"start": 421.7, "end": 429.62, "text": " Okay, so the main difference, uh in the training procedure is that they integrated the mcts directly into the training and they're not using it just for the"}, {"start": 430.18, "end": 430.9, "text": " uh"}, {"start": 430.9, "end": 435.78, "text": " During the play so basically this is how the network is trained. So you have a self-play game"}, {"start": 436.26, "end": 438.82, "text": " So take our our own agent. Uh, you take the"}, {"start": 438.82, "end": 446.02, "text": " The basically that's the uh, the network that has both the policy and the value and you just roll out the game until the end state"}, {"start": 446.34, "end": 448.26, "text": " Now this is the trick"}, {"start": 448.26, "end": 451.14, "text": " So in this state, uh, you you pass it into the network"}, {"start": 451.14, "end": 457.46, "text": " It outputs the probabilities and the so this is kind of the probability vector and the the value scalar"}, {"start": 457.86, "end": 462.18, "text": " So now instead of just picking the action directly from this output"}, {"start": 462.98, "end": 464.98, "text": " What I do is they uh"}, {"start": 464.98, "end": 468.98, "text": " Do the mcts over this state so this is"}, {"start": 469.78000000000003, "end": 475.3, "text": " Depicted here and they actually pick the action from this probability distribution, which is much better"}, {"start": 475.86, "end": 479.94, "text": " Prediction than the raw probability prediction from the directive from the network"}, {"start": 480.74, "end": 481.54, "text": " so"}, {"start": 481.54, "end": 485.46000000000004, "text": " Uh after just picking the action we get into a different state"}, {"start": 485.86, "end": 489.46000000000004, "text": " We again do the mcts and we roll out all of these"}, {"start": 489.46, "end": 496.26, "text": " Uh until the end and we're just saving this this tuple. So the data for each time step t is stored as state"}, {"start": 496.9, "end": 503.53999999999996, "text": " Policy, so that's the this vector here. We're storing this one and we're storing the outcome. So the basically the"}, {"start": 504.26, "end": 509.14, "text": " The end result basically either plus one if the player won or minus one if it lost"}, {"start": 509.29999999999995, "end": 513.06, "text": " So this is basically the main trick doing the mcts during the actual self-play"}, {"start": 513.54, "end": 517.14, "text": " once we have that what we do is we in order to train the"}, {"start": 517.14, "end": 519.22, "text": " The agent we do the following"}, {"start": 520.26, "end": 526.74, "text": " We take those tuples that we stored and we want to make sure that the output from the raw network"}, {"start": 526.74, "end": 529.86, "text": " So the policy vector that comes directly from the network"}, {"start": 530.66, "end": 534.98, "text": " Gets as close to the mcts policy as possible"}, {"start": 535.46, "end": 542.5, "text": " Secondly, we just regressed the value function so as to be really close to the final outcome of that particular game"}, {"start": 543.06, "end": 545.06, "text": " so"}, {"start": 545.06, "end": 547.6999999999999, "text": " Basically, here is the equation you can see"}, {"start": 548.42, "end": 554.0999999999999, "text": " We do a simple regression doing mean square error for the value function and we do the"}, {"start": 555.14, "end": 560.42, "text": " simple simple cross entropy loss here, so this has a minimum so the p vector is the"}, {"start": 561.38, "end": 564.5, "text": " probability coming from the raw network the pi is the"}, {"start": 565.06, "end": 571.54, "text": " Probability coming from the mcts and we want to make sure that the probability coming from the raw network is as close as possible"}, {"start": 571.54, "end": 576.9, "text": " To pi and that's the minimum of this function. So basically that's when we hit the entropy limit"}, {"start": 577.38, "end": 581.4599999999999, "text": " Before that we have the non zero k l divergence and once we get to"}, {"start": 582.26, "end": 588.8199999999999, "text": " To the same to once p becomes equal to pi we have zero k l and we converge to a minimum"}, {"start": 589.62, "end": 592.0999999999999, "text": " So basically that's why this thing"}, {"start": 592.8199999999999, "end": 599.62, "text": " Pushes p to be close to pi. Finally, the third term is just basically l2 regularization and"}, {"start": 599.62, "end": 604.42, "text": " And that's it. It's pretty simple. It's much simpler than alpha go"}, {"start": 604.9, "end": 607.54, "text": " And yeah, let's see what I see here"}, {"start": 607.54, "end": 612.74, "text": " So the neural network parameters theta are updated to maximize the similarity of the policy vector p"}, {"start": 613.22, "end": 617.46, "text": " To the search probabilities p pi and to minimize the error between the predicted winner"}, {"start": 618.02, "end": 624.1, "text": " V and the game winner z as for the montecarlo tree search a short recap how it works"}, {"start": 624.1, "end": 631.0600000000001, "text": " Basically, they're using the again the p uct algorithm. So the upper confidence bound for trees algorithm again"}, {"start": 631.14, "end": 637.14, "text": " Basically start from the root state and you pick the values so as to maximize this p uct score"}, {"start": 637.3000000000001, "end": 645.22, "text": " So the q value the action value function plus this u term which consists of which has this visitation term inside and priors"}, {"start": 645.7, "end": 649.78, "text": " and picking the highest ones they get to the leaf node and finally"}, {"start": 649.78, "end": 656.74, "text": " Uh in the case of alpha go zero, they don't have the uh, actually the expanding threshold which was around 40"}, {"start": 657.06, "end": 660.66, "text": " In alpha go they just uh expand the network every single time"}, {"start": 660.98, "end": 667.78, "text": " so once you get to the leaf you just expand it and basically what it means is you you pass that state into the"}, {"start": 668.5799999999999, "end": 674.3399999999999, "text": " network and it will output the probability vector and the value and you'll be back propping that"}, {"start": 674.34, "end": 682.02, "text": " um, basically back upping the the value function up the tree and you'll be using the p as the priors for the"}, {"start": 682.58, "end": 683.94, "text": " next uh"}, {"start": 683.94, "end": 688.82, "text": " Nodes in the in the tree. So basically next time if one of the threads comes here, it will pick up"}, {"start": 689.46, "end": 691.46, "text": " one of those of these"}, {"start": 691.46, "end": 694.34, "text": " Children depending on the again on the p uct score"}, {"start": 694.58, "end": 701.22, "text": " So maybe come here it will again expand this one and that's how we actually build up this montecarlo tree search"}, {"start": 701.22, "end": 704.6600000000001, "text": " And hopefully that that was also already clear from the previous video"}, {"start": 704.74, "end": 709.0600000000001, "text": " So here just depicted that the value function is back propped"}, {"start": 709.7, "end": 716.1800000000001, "text": " back backed up, uh up the tree and they're updating the statistics both the visitation counts as well as the"}, {"start": 717.62, "end": 720.02, "text": " Basically the the montecarlo estimates"}, {"start": 721.14, "end": 722.26, "text": " Okay"}, {"start": 722.26, "end": 724.02, "text": " That's that's it"}, {"start": 724.02, "end": 727.5400000000001, "text": " That's it. And um, so they said here over the course of training"}, {"start": 727.54, "end": 731.4, "text": " 4.9 million games of self play were generated using"}, {"start": 732.48, "end": 738.4399999999999, "text": " 1600 simulations for each mcts which corresponds to approximately 0.4 second"}, {"start": 739.24, "end": 745.88, "text": " Thinking time per move. So that means when you're building up these trees during the the self play you do these you do"}, {"start": 746.64, "end": 750.28, "text": " 1600 of these simulations in order to build a tree and then you pick the"}, {"start": 751.24, "end": 754.92, "text": " The action that actually maximizes the visitation count in the root node"}, {"start": 754.92, "end": 758.8399999999999, "text": " They have some temperature coefficient, but we'll get to that a bit later. Basically, that's it"}, {"start": 759.56, "end": 761.56, "text": " Okay, let's continue"}, {"start": 762.28, "end": 764.1999999999999, "text": " And after doing this training"}, {"start": 764.76, "end": 769.64, "text": " Surprisingly the alpha goes zero outperform the alpha goalie after just 36 hours"}, {"start": 769.64, "end": 773.0799999999999, "text": " So you can see it here after just 36 hours"}, {"start": 773.64, "end": 779.64, "text": " Basically, it's already better than the agent that that has beaten at least it all back in 2016"}, {"start": 779.64, "end": 780.92, "text": " And that's impressive"}, {"start": 780.92, "end": 785.4799999999999, "text": " And they said here the alpha goalie was actually trained over several months"}, {"start": 785.4799999999999, "end": 789.16, "text": " So a lot of compute went into this thing. So yeah, keep that in mind"}, {"start": 790.04, "end": 793.64, "text": " Alpha goes here. I use a single machine with four tpus"}, {"start": 794.04, "end": 798.68, "text": " Whereas alpha go Lee was distributed over many machines and used 48 tpus"}, {"start": 799.4799999999999, "end": 802.92, "text": " Alpha go zero defeated alpha go Lee 100 to zero"}, {"start": 803.4, "end": 809.4, "text": " So that's some serious performance that we got from this pure self-reinforced learning approach"}, {"start": 809.4, "end": 813.16, "text": " And that's amazing again. You can see the curves here"}, {"start": 814.1999999999999, "end": 815.16, "text": " the"}, {"start": 815.16, "end": 817.88, "text": " Dotted line here is the the lee method"}, {"start": 818.6, "end": 821.18, "text": " The the purple one is actually the same architecture"}, {"start": 821.9599999999999, "end": 823.48, "text": " as as the"}, {"start": 823.48, "end": 828.92, "text": " Alpha go zero but just using the human experts data and you can see it can't achieve the elo score"}, {"start": 829.48, "end": 832.04, "text": " As high as alpha go zero"}, {"start": 833.0799999999999, "end": 835.0799999999999, "text": " Okay looking at this curve here"}, {"start": 835.08, "end": 842.6, "text": " Uh, we're trying to see how good these networks both the alpha go zero as well this supervised learning network"}, {"start": 842.84, "end": 844.84, "text": " How good are they?"}, {"start": 845.4000000000001, "end": 848.2, "text": " predicting the actual moves that human experts will make"}, {"start": 848.6, "end": 853.4000000000001, "text": " and you can see that the supervised method is actually better here and that shouldn't surprise you because"}, {"start": 854.2, "end": 858.6, "text": " The goal for alpha go zero is not to be better at predicting human experts move"}, {"start": 858.6800000000001, "end": 864.36, "text": " It's to be the best agent the best player and that doesn't necessarily correlate with human play"}, {"start": 864.36, "end": 869.72, "text": " And we'll see that exactly happening a bit later where alpha go zero discover certain joseki's"}, {"start": 869.88, "end": 874.76, "text": " So those are some corner sequences in go they weren't discovered by by humans prior to this agent"}, {"start": 875.32, "end": 878.52, "text": " So that's that's awesome. Um, and we can see it here actually"}, {"start": 879.4, "end": 880.76, "text": " looking at the"}, {"start": 880.76, "end": 884.6, "text": " emcee of professional game outcomes, so the uh"}, {"start": 885.32, "end": 890.44, "text": " Of alpha go zero is much better at predicting the final outcome of the games than the supervised approach"}, {"start": 890.44, "end": 894.44, "text": " so that means if you're in a particular state and we just um,"}, {"start": 895.32, "end": 903.08, "text": " Basically pass it through the the network. It will be better at predicting the final outcome in those games played by humans than the sl"}, {"start": 903.72, "end": 909.6400000000001, "text": " Network. So yeah, this is actually more important than this chart keep that in mind"}, {"start": 910.9200000000001, "end": 912.9200000000001, "text": " Okay"}, {"start": 913.32, "end": 916.44, "text": " Aside from that they try to decouple the"}, {"start": 916.44, "end": 924.5200000000001, "text": " The the the contribution that came from the algorithm and what came from the actual architecture improvement because they're using resonance if you remember"}, {"start": 925.32, "end": 928.6, "text": " So looking at these charts here, um, the the leftmost"}, {"start": 930.0400000000001, "end": 932.84, "text": " This leftmost network is actually a dual"}, {"start": 933.1600000000001, "end": 939.1600000000001, "text": " Resnet meaning dual is because we have a single architecture that outputs both the policy as well as the value"}, {"start": 939.72, "end": 941.0, "text": " and"}, {"start": 941.0, "end": 942.5200000000001, "text": " here we have the"}, {"start": 942.52, "end": 948.36, "text": " Cep conf that's basically single network for both policy and for the value network"}, {"start": 948.68, "end": 955.48, "text": " So that's something alpha go used and it's using the simple cnn instead of resonant and you can see that the elo rating"}, {"start": 955.88, "end": 958.36, "text": " Uh goes up. So everything else is pretty much the same"}, {"start": 959.24, "end": 961.98, "text": " And we get a huge boost just from the architecture"}, {"start": 962.84, "end": 968.04, "text": " And these are the other combinations. So just using separate resonants and using dual architecture, but with cnn's"}, {"start": 968.04, "end": 972.5999999999999, "text": " Um similarly looking at the prediction accuracy of the human players"}, {"start": 973.0, "end": 979.0, "text": " This one is actually a bit worse by looking at the msc of the game. So just predict regressing the outcome"}, {"start": 979.56, "end": 985.48, "text": " This one is the best and finally this architecture gave them the best results. So that's what they're using"}, {"start": 986.28, "end": 988.28, "text": " um, okay"}, {"start": 988.5999999999999, "end": 989.64, "text": " um"}, {"start": 989.64, "end": 994.52, "text": " One more detail, uh, they say here this is partly due to improved computational efficiency"}, {"start": 994.52, "end": 1001.88, "text": " But more importantly the dual objective regularizes the network to a common representation that supports multiple use cases"}, {"start": 1002.1999999999999, "end": 1005.0799999999999, "text": " So the idea here is the following so you have a cnn"}, {"start": 1006.04, "end": 1010.36, "text": " And since you're training the policy, so this is the policy vector here and this is the"}, {"start": 1011.0799999999999, "end": 1016.84, "text": " value scaler so when you just do your gradient update of your network for the"}, {"start": 1017.72, "end": 1019.72, "text": " To get closer to the mcts"}, {"start": 1019.72, "end": 1026.3600000000001, "text": " Um, uh probability vector you're updating these features, but these features are subsequently used"}, {"start": 1026.84, "end": 1028.76, "text": " by the value"}, {"start": 1028.76, "end": 1035.08, "text": " stream here and so basically whatever you do you're improving both the value and the policy and your"}, {"start": 1036.68, "end": 1039.0, "text": " You're basically figuring out the features which are"}, {"start": 1039.64, "end": 1045.4, "text": " Good for figuring out both the policy and the value and that helps that helps boost the performance"}, {"start": 1046.44, "end": 1047.56, "text": " Okay"}, {"start": 1047.56, "end": 1050.9199999999998, "text": " Uh, let's see some of the knowledge that this network learned"}, {"start": 1051.56, "end": 1053.08, "text": " during this"}, {"start": 1053.08, "end": 1055.08, "text": " training and"}, {"start": 1055.08, "end": 1061.56, "text": " In this chart what you can see in the top row here are some of these joseki as I mentioned and I don't know"}, {"start": 1061.56, "end": 1065.56, "text": " How to play go but I know enough to just kind of understand what's happening"}, {"start": 1065.72, "end": 1069.32, "text": " But if you're familiar with go, maybe this will be even more interesting for you"}, {"start": 1070.28, "end": 1072.12, "text": " Basically here you can see"}, {"start": 1072.12, "end": 1079.2399999999998, "text": " These are the joseki's that humans play and you can see that the alpha go zero actually reinvented these"}, {"start": 1080.28, "end": 1082.28, "text": " At some time during the training"}, {"start": 1082.36, "end": 1086.52, "text": " So this first joseki was discovered like maybe around 10 hour mark"}, {"start": 1086.9199999999998, "end": 1091.56, "text": " Then the second one was discovered. I don't know like maybe 15 hours and the last one was discovered"}, {"start": 1092.1999999999998, "end": 1094.1999999999998, "text": " Maybe around 36 hour mark"}, {"start": 1095.56, "end": 1099.56, "text": " And that's super fun and we'll later see how the frequency was increasing"}, {"start": 1099.56, "end": 1105.56, "text": " So at one point of the training it was heavily using one of these joseki's and then it kind of just ditched them away"}, {"start": 1105.6399999999999, "end": 1107.6399999999999, "text": " Because they were actually worse"}, {"start": 1108.04, "end": 1110.9199999999998, "text": " It found some better patterns and started using those"}, {"start": 1111.6399999999999, "end": 1113.3999999999999, "text": " in the second row"}, {"start": 1113.3999999999999, "end": 1119.72, "text": " What we can basically see are the joseki's which were the most frequent joseki's at that part of the training"}, {"start": 1120.52, "end": 1121.8799999999999, "text": " time frame"}, {"start": 1121.8799999999999, "end": 1126.76, "text": " So basically if you take a look at I don't know maybe this one so around the 48 hour mark"}, {"start": 1126.76, "end": 1129.56, "text": " It was heavily using this particular pattern"}, {"start": 1130.12, "end": 1134.6, "text": " and yeah, and finally the the last row tells you"}, {"start": 1135.48, "end": 1138.92, "text": " Basically shows you the games. So these are just so we take this"}, {"start": 1139.48, "end": 1144.28, "text": " Maybe three hour mark. We take the one particular self play game and we just"}, {"start": 1144.92, "end": 1147.56, "text": " Plotted here and you can see how it evolved"}, {"start": 1147.56, "end": 1152.84, "text": " So here it was it was playing really greedy and clustering all of the moves the black and the whites"}, {"start": 1152.84, "end": 1158.6, "text": " In the same region of the of the board and as the game progressed we came to these"}, {"start": 1159.3999999999999, "end": 1164.76, "text": " More subtle again. I'm not I don't understand go but I was after reading the paper. I understand this"}, {"start": 1164.76, "end": 1170.76, "text": " So basically here it's leading multiple battles battles distributed across the board and it's much better"}, {"start": 1171.8799999999999, "end": 1175.32, "text": " Player now after 70 hours than at the beginning"}, {"start": 1176.36, "end": 1182.1999999999998, "text": " So those were some of the knowledge that the alpha zero basically rediscovered and that's pretty damn impressive"}, {"start": 1182.2, "end": 1183.8, "text": " If you ask me"}, {"start": 1183.8, "end": 1188.04, "text": " Okay, let's continue and uh see what's up here"}, {"start": 1189.4, "end": 1195.0, "text": " Okay, so they say here ultimately alpha go zero preferred new joseki variants that were previously unknown"}, {"start": 1195.0800000000002, "end": 1201.16, "text": " I mentioned that already so that's pretty much fascinating. Uh, surprisingly this letter capture sequence"}, {"start": 1201.8, "end": 1206.1200000000001, "text": " Um is one of the first elements of go knowledge learned by humans"}, {"start": 1206.12, "end": 1213.4799999999998, "text": " But they were only understood by alpha go zero much later in training and that's cool because that suggests also that"}, {"start": 1213.8, "end": 1218.28, "text": " Uh, it's not constrained by any way by the human priors and knowledge"}, {"start": 1219.0, "end": 1223.3999999999999, "text": " So it actually discovered something that was obvious to humans much later"}, {"start": 1223.6399999999999, "end": 1226.4399999999998, "text": " But it also discovered some things that were not obvious to humans"}, {"start": 1227.32, "end": 1228.04, "text": " And that's awesome"}, {"start": 1228.04, "end": 1233.9599999999998, "text": " And they say here the humankind has accumulated go knowledge from millions of games played over thousands of years"}, {"start": 1233.96, "end": 1236.14, "text": " years collectively distilled into patterns"}, {"start": 1236.54, "end": 1242.46, "text": " Proverbs and books in the space of a few days starting tabula rasa. So blank slates totally random"}, {"start": 1242.78, "end": 1248.54, "text": " Alpha go zero was able to rediscover much of this go knowledge as well as novel strategies that provide"}, {"start": 1248.8600000000001, "end": 1254.46, "text": " New insights into the oldest of games and they're just romanticizing here a bit. Okay"}, {"start": 1255.74, "end": 1256.78, "text": " basically"}, {"start": 1256.78, "end": 1261.3400000000001, "text": " Uh, it's pretty awesome and looking at the charts. Uh, you can see that the"}, {"start": 1261.34, "end": 1263.34, "text": " Uh alpha go zero, uh"}, {"start": 1263.98, "end": 1267.1799999999998, "text": " Beats alpha go lee after just a couple of uh"}, {"start": 1267.8999999999999, "end": 1274.3799999999999, "text": " Days and then starts being better than this alpha go master version after 30 something days"}, {"start": 1275.4199999999998, "end": 1277.4199999999998, "text": " Again, uh some similar chart here"}, {"start": 1277.82, "end": 1284.06, "text": " Uh, basically this is the alpha go zero performance. This is the master the lead the the fan"}, {"start": 1284.78, "end": 1285.82, "text": " um"}, {"start": 1285.82, "end": 1292.9399999999998, "text": " Uh models and finally we have some commercial go programs which you can see are much worse than even the alpha go fan"}, {"start": 1293.26, "end": 1295.26, "text": " And then we have this, uh"}, {"start": 1295.5, "end": 1298.46, "text": " Basically open source go program which is even worse"}, {"start": 1300.22, "end": 1303.34, "text": " Finally this one is basically the the raw network performance"}, {"start": 1303.34, "end": 1310.9399999999998, "text": " So without using the mcts by just using the probabilities coming from the policy network, uh and playing using that one, uh, you get"}, {"start": 1310.94, "end": 1318.6200000000001, "text": " That much much lower elo score than using mcts. So search is really important for playing go efficiently. Okay"}, {"start": 1320.78, "end": 1326.7, "text": " That's it that was the high level overview I wanted to show you and now we'll get into some details"}, {"start": 1326.7, "end": 1330.94, "text": " But before that let me just show you those jiseki's I was mentioning. So here"}, {"start": 1331.5800000000002, "end": 1335.42, "text": " Um, so this is some jiseki. That's um, the humans play a lot"}, {"start": 1335.42, "end": 1340.46, "text": " So it's even has a name five three point press whatever and you can see the frequency here"}, {"start": 1340.46, "end": 1346.3, "text": " And similarly for other jiseki's and you can see for some patterns. So this like knight's move pincer"}, {"start": 1346.8600000000001, "end": 1348.7, "text": " the frequency"}, {"start": 1348.7, "end": 1352.7, "text": " Peaked here and then slowly decreased after 70 hours of training"}, {"start": 1353.3400000000001, "end": 1357.18, "text": " So that means it was discovering and ditching the patterns. So that's cool"}, {"start": 1357.74, "end": 1360.94, "text": " Um, this is the the the second chart shows you"}, {"start": 1361.58, "end": 1366.06, "text": " Um some of the jiseki's that was playing really often at one point of training"}, {"start": 1366.06, "end": 1370.7, "text": " So again here three by three invasion. It had a peak here. So it was playing this this"}, {"start": 1371.1, "end": 1375.6599999999999, "text": " Particular jiseki a lot at one point of time and so on and so forth"}, {"start": 1376.46, "end": 1378.46, "text": " So that's that's it"}, {"start": 1379.1, "end": 1385.4199999999998, "text": " Now let's dig into the details of the actual algorithm. Okay, so i've covered this part already"}, {"start": 1385.82, "end": 1392.1399999999999, "text": " This is a spectrum I was mentioning so they went from fan to lee to master and finally to alpha go zero"}, {"start": 1392.14, "end": 1396.5400000000002, "text": " Uh, and each time increasing the both the efficiency. So this one used"}, {"start": 1397.8000000000002, "end": 1399.8000000000002, "text": " 176 gpus"}, {"start": 1399.98, "end": 1404.5600000000002, "text": " Then the lee version I think used something around 47 tpus"}, {"start": 1405.8200000000002, "end": 1412.46, "text": " Then they had uh alpha go master which used even less hardware and finally alpha go zero actually uses only four tpus"}, {"start": 1412.5400000000002, "end": 1417.1000000000001, "text": " And it's much better as you saw than lee and and master and every version"}, {"start": 1417.8200000000002, "end": 1420.5400000000002, "text": " So far, um, and yeah, they say here"}, {"start": 1420.54, "end": 1423.04, "text": " Okay, so uh, basically"}, {"start": 1423.82, "end": 1431.02, "text": " They say it here. The primary contribution is to demonstrate that superhuman performance can be achieved without human domain knowledge"}, {"start": 1431.58, "end": 1434.1399999999999, "text": " We reiterated that already a couple of times"}, {"start": 1434.78, "end": 1441.18, "text": " To clarify this contribution we number the domain knowledge that alpha go zero uses explicitly or implicitly"}, {"start": 1441.5, "end": 1444.3799999999999, "text": " Either in its training procedure or its mcts"}, {"start": 1444.7, "end": 1447.74, "text": " These are the items of knowledge that would need to be replaced"}, {"start": 1447.74, "end": 1451.9, "text": " For alpha go zero to learn a different alternating markov game"}, {"start": 1452.46, "end": 1457.34, "text": " And this is the main point where basically after you just kind of"}, {"start": 1457.98, "end": 1463.42, "text": " Modify a couple of these you get to alpha zero and you can play both the chess and shogi as well as go"}, {"start": 1464.22, "end": 1469.02, "text": " And uh the most important parts here. So basically you will want to"}, {"start": 1469.82, "end": 1471.82, "text": " Um ditch the symmetry part"}, {"start": 1471.9, "end": 1476.94, "text": " So the rules of go are invariant under rotation and reflection this knowledge has been used in alpha go zero"}, {"start": 1476.94, "end": 1481.98, "text": " Both by augmenting the data set during training to include rotations and reflections of each position"}, {"start": 1481.98, "end": 1483.98, "text": " So if you remember from the alpha go video"}, {"start": 1484.22, "end": 1487.9, "text": " Basically each time you want to evaluate a position you take a random"}, {"start": 1488.78, "end": 1492.3, "text": " Uh element from the dihedral group that has eight elements"}, {"start": 1492.3, "end": 1499.98, "text": " So basically because you have two reflections and four rotations you get to eight elements and you were just using those and that will"}, {"start": 1500.38, "end": 1502.7, "text": " Make your data bigger and also"}, {"start": 1503.74, "end": 1505.74, "text": " They showed it improves the training"}, {"start": 1505.74, "end": 1511.34, "text": " So we'll have to uh expel that part because other games such as chess they don't have"}, {"start": 1511.66, "end": 1515.34, "text": " That symmetry as as inherent part of the game"}, {"start": 1516.46, "end": 1517.34, "text": " Okay"}, {"start": 1517.34, "end": 1523.26, "text": " Some details here. So the montecarlo tree search parameters some bayesian optimization was used"}, {"start": 1524.22, "end": 1527.74, "text": " To figure those out and this is a really important part"}, {"start": 1527.74, "end": 1532.14, "text": " So alpha goes your self-play training pipeline consists of three main components"}, {"start": 1532.14, "end": 1537.9, "text": " So the first thing is neural network parameters are continually optimized from recent self-play data"}, {"start": 1538.46, "end": 1540.46, "text": " That's the first part"}, {"start": 1540.46, "end": 1548.14, "text": " Uh and alpha go zero players are continually evaluated. That's the second part and thirdly the best performing player so far"}, {"start": 1548.5400000000002, "end": 1555.5, "text": " This alpha theta star is used to generate new self-play data and let us see how that exactly works"}, {"start": 1556.3000000000002, "end": 1557.74, "text": " so"}, {"start": 1557.74, "end": 1564.3, "text": " So, um, you basically have something like a replay buffer and I i'll draw it like this"}, {"start": 1565.1, "end": 1566.7, "text": " you have the"}, {"start": 1566.7, "end": 1572.54, "text": " Current best network and i'll just draw it like a box and we have a bunch of self-play games"}, {"start": 1573.34, "end": 1575.02, "text": " happening in parallel"}, {"start": 1575.02, "end": 1578.3, "text": " so how the actual framework works like is the following so"}, {"start": 1579.34, "end": 1580.86, "text": " We have this"}, {"start": 1580.86, "end": 1586.7, "text": " Network and that's the best agent so far and we're just taking data from the replay buffer"}, {"start": 1586.7, "end": 1588.7, "text": " And we are updating that network"}, {"start": 1589.66, "end": 1595.18, "text": " Next up every every thousand, um updates will be dumping a checkpoint"}, {"start": 1595.9, "end": 1601.9, "text": " Model and we'll be comparing that checkpoint model with the last previously stored best model"}, {"start": 1602.06, "end": 1605.9, "text": " So we have the this thing they call alpha theta star"}, {"start": 1606.3, "end": 1611.74, "text": " So that's the best agent and interesting fact is that this agent so let me draw it like a like a"}, {"start": 1612.44, "end": 1613.66, "text": " rectangle"}, {"start": 1613.66, "end": 1620.38, "text": " Basically, they use those weights in all of these self-play threads. So when I knew when one of these"}, {"start": 1621.26, "end": 1625.5800000000002, "text": " Self-playing threads finishes, uh, it will want to start over again"}, {"start": 1625.9, "end": 1628.22, "text": " So we'll just pull the best parameters here"}, {"start": 1628.6200000000001, "end": 1633.74, "text": " And it will be using that network weights to play the game and store it will be storing"}, {"start": 1634.14, "end": 1636.7, "text": " The tuples so we we mentioned so the s"}, {"start": 1636.7, "end": 1643.42, "text": " The pi and the outcome of the game so those tuples will be stored back in these in the storage"}, {"start": 1643.82, "end": 1646.22, "text": " So that's how the dynamics of the whole pipeline works"}, {"start": 1646.78, "end": 1647.82, "text": " um"}, {"start": 1647.82, "end": 1651.5, "text": " So I haven't finished this part. So once uh, we we dump the checkpoint"}, {"start": 1651.98, "end": 1657.42, "text": " What we want to do is we want to do evaluation and basically what they did is they play"}, {"start": 1657.42, "end": 1665.92, "text": " 400 games between this checkpoint and between the best model and whichever model wins. That's the the model will be using"}, {"start": 1666.88, "end": 1671.1200000000001, "text": " For all of the next self-play game. So the next self-play thread"}, {"start": 1671.28, "end": 1676.8000000000002, "text": " So if this one finishes and wants to start over again, it will just pull the the newest the best parameters"}, {"start": 1677.1200000000001, "end": 1679.1200000000001, "text": " And it will start playing the game"}, {"start": 1679.1200000000001, "end": 1682.3200000000002, "text": " So that's roughly how this thing works. And now let's"}, {"start": 1682.32, "end": 1689.36, "text": " Let's see some details they said here again the optimization process produces a new checkpoint every thousand training steps"}, {"start": 1689.6, "end": 1692.8, "text": " If the new player wins by a margin of over 55"}, {"start": 1694.3999999999999, "end": 1702.3999999999999, "text": " Then it becomes the best player and is subsequently used for self-play generation and also becomes the baseline for subsequent comparisons"}, {"start": 1703.36, "end": 1706.56, "text": " So I mentioned that part already and it's playing 400 games"}, {"start": 1706.56, "end": 1712.96, "text": " To we are playing 400 games between the checkpoint and the best model in order to figure out whether it's statistically"}, {"start": 1713.74, "end": 1715.12, "text": " significantly"}, {"start": 1715.12, "end": 1718.96, "text": " Better than the whether the checkpoint is better than the best model so far"}, {"start": 1719.04, "end": 1724.6399999999999, "text": " Okay, so now that we have the best player, let's see how we can use those weights in order to play these"}, {"start": 1725.1799999999998, "end": 1726.72, "text": " self-play games"}, {"start": 1726.72, "end": 1734.1599999999999, "text": " So the best current player alpha theta star as selected by the evaluator is used to generate data"}, {"start": 1734.16, "end": 1740.0, "text": " In each iteration alpha theta star plays 25 000 games of self-play"}, {"start": 1740.8000000000002, "end": 1745.68, "text": " And it uses 1600 simulations of mcts to select each move. Okay"}, {"start": 1746.16, "end": 1748.16, "text": " Um, let me draw it here"}, {"start": 1749.76, "end": 1756.96, "text": " Basically, this is the self-play thread and it just fetches the the newest weights from the alpha theta"}, {"start": 1757.52, "end": 1758.72, "text": " star"}, {"start": 1758.72, "end": 1764.24, "text": " And they say here for the first 30 moves of each game the temperature is set to one"}, {"start": 1764.88, "end": 1771.76, "text": " This selects moves proportionally to their visit count in mcts ensures a diverse set of positions are encountered"}, {"start": 1772.16, "end": 1777.04, "text": " That means if this is the initial state of the self-play game, so that's the initial board state"}, {"start": 1777.52, "end": 1780.8, "text": " Uh, we play for the first 30 steps. So this is 30"}, {"start": 1781.68, "end": 1785.92, "text": " Um, we play uh using proportional sampling. That means the following"}, {"start": 1785.92, "end": 1789.6000000000001, "text": " So if I just zoom in into this state, so this is some state"}, {"start": 1790.24, "end": 1794.5800000000002, "text": " state zero in this particular case and once we do the mcts"}, {"start": 1796.0, "end": 1802.8000000000002, "text": " And we find the probabilities we'll be using uh, we won't be doing a greedy sampling will be"}, {"start": 1803.2, "end": 1809.68, "text": " Uh, a greedy policy will just uh take the proportional sampling. So if we have something like this maybe"}, {"start": 1810.16, "end": 1812.0800000000002, "text": " uh"}, {"start": 1812.08, "end": 1818.98, "text": " Some distribution like this one. That means this action will be taken the most often because it has the highest probability"}, {"start": 1820.08, "end": 1826.1599999999999, "text": " So that's for the first 30 states and that ensures that we have some kind of because we're constantly using the same model"}, {"start": 1826.3999999999999, "end": 1831.52, "text": " This ensures we are having uh some uh diversity in the initial positions. Okay"}, {"start": 1832.24, "end": 1836.32, "text": " So that's the first part and then we start playing from this point on we start playing"}, {"start": 1836.32, "end": 1844.0, "text": " Uh greedy because the temperature goes to zero and that means uh, whatever that so that means this one will get transformed into this"}, {"start": 1844.96, "end": 1848.96, "text": " All of these will be zero. So that's zero. That's zero. This one will be one"}, {"start": 1849.04, "end": 1851.6799999999998, "text": " So we'll be picking the the highest probability always"}, {"start": 1852.32, "end": 1853.12, "text": " Okay"}, {"start": 1853.12, "end": 1859.6799999999998, "text": " So then they say the following additional exploration is achieved by adding dairy clay noise to the prior probabilities in the root node"}, {"start": 1859.76, "end": 1862.48, "text": " As zero so if we take certain state here"}, {"start": 1862.48, "end": 1867.6, "text": " Uh, and we zoom in again and before we even start building the mct"}, {"start": 1868.14, "end": 1870.96, "text": " mcts3 what they'll do is they'll add the"}, {"start": 1871.68, "end": 1876.64, "text": " Noise into the root priors themselves. So once the once we get the initial priors"}, {"start": 1877.3600000000001, "end": 1880.72, "text": " those will get uh by passing the the state into the"}, {"start": 1881.28, "end": 1882.56, "text": " um our"}, {"start": 1882.56, "end": 1886.96, "text": " Model into the network, uh, we'll modify these priors using the dairy clay noise"}, {"start": 1886.96, "end": 1892.56, "text": " which will ensure there is some randomization in how do we visit the uh,"}, {"start": 1892.64, "end": 1900.16, "text": " the how to explore the mcts3 and that will explore there will additionally enable us to have a diverse set of"}, {"start": 1900.22, "end": 1902.48, "text": " tuples which will be fed back into the"}, {"start": 1903.1000000000001, "end": 1904.24, "text": " storage"}, {"start": 1904.24, "end": 1906.24, "text": " into the replay buffer"}, {"start": 1906.24, "end": 1910.64, "text": " Which again is used by the currently best network to update its weights"}, {"start": 1911.6000000000001, "end": 1914.72, "text": " And that's that's pretty much it. Um"}, {"start": 1914.72, "end": 1920.88, "text": " Um, this is something you should know from previous video. Basically, we're storing statistics of visitation counts"}, {"start": 1921.42, "end": 1926.08, "text": " cumulative mc montecarlo estimates the action value function and the priors"}, {"start": 1926.8, "end": 1928.16, "text": " Okay"}, {"start": 1928.16, "end": 1929.68, "text": " uh here"}, {"start": 1929.68, "end": 1935.44, "text": " Puct we saw this one. So basically depending on the visitation counts the more you visit some state"}, {"start": 1936.08, "end": 1938.8, "text": " the smaller the u becomes and basically that means"}, {"start": 1939.28, "end": 1940.24, "text": " uh"}, {"start": 1940.24, "end": 1943.52, "text": " You depend on the action value function to decide whether you want to"}, {"start": 1943.52, "end": 1945.52, "text": " Uh pick that edge or not"}, {"start": 1946.56, "end": 1947.68, "text": " Okay"}, {"start": 1947.68, "end": 1952.8, "text": " Additional detail positions in the queue are evaluated by the neural network using a mini batch size of eight"}, {"start": 1953.04, "end": 1955.6, "text": " The search thread is locked until the validation completes"}, {"start": 1955.84, "end": 1962.48, "text": " So this is a bit different compared to the alpha go model because it used to use a synchronous policy here on the other hand"}, {"start": 1962.8, "end": 1966.8799999999999, "text": " What this means is basically on the gpu you have so this is a gpu"}, {"start": 1967.44, "end": 1970.24, "text": " You have the network and you just make a queue here"}, {"start": 1970.24, "end": 1977.76, "text": " um, and it has eight slots and basically you need to wait for the eight threads to"}, {"start": 1978.56, "end": 1983.04, "text": " reach the final the leaf node and to push it here and then"}, {"start": 1983.76, "end": 1989.92, "text": " We'll just you know in a single batch will produce the the priors as well as the values and then"}, {"start": 1990.32, "end": 1994.48, "text": " Only then will the those threads resume so they are kind of synchronous. So that's"}, {"start": 1995.1200000000001, "end": 1998.32, "text": " A detail that's that's new to alpha go zero"}, {"start": 1998.32, "end": 2003.36, "text": " Uh, they also they they continue using this virtual loss, which if you remember"}, {"start": 2004.32, "end": 2006.32, "text": " If we had some uh"}, {"start": 2007.04, "end": 2009.84, "text": " So this is the the root of the mcts. This is the leaf"}, {"start": 2010.3799999999999, "end": 2015.6, "text": " basically, uh the virtual loss will make sure that these visitation counts are"}, {"start": 2016.0, "end": 2018.8, "text": " So these are the states and the squiggly lines are the actions"}, {"start": 2019.28, "end": 2023.2, "text": " Uh, it will just uh, maybe do minus three on all of the states"}, {"start": 2023.2, "end": 2030.32, "text": " Uh for the visitation and that will reduce the u part of the key of the of the puct which means"}, {"start": 2031.2, "end": 2034.4, "text": " All of the other threads which are building up the mcts tree"}, {"start": 2035.2, "end": 2039.2, "text": " Will be less likely to take this exact route to the leaf node"}, {"start": 2039.3600000000001, "end": 2042.32, "text": " And that's that's the whole point because we're already exploring this one"}, {"start": 2042.64, "end": 2048.32, "text": " We just have this virtual loss thing which uh discourages other threads to explore the same path"}, {"start": 2049.52, "end": 2051.52, "text": " Okay, finally, um"}, {"start": 2051.52, "end": 2053.68, "text": " We're using exponentiated visit count"}, {"start": 2054.32, "end": 2060.48, "text": " Uh, basically, so this is the visitation counts and this is the temperature coefficient which we were mentioning. So the first 30"}, {"start": 2061.68, "end": 2063.68, "text": " Moves are are being played"}, {"start": 2063.98, "end": 2069.36, "text": " Proportionally and then this temperature drops to zero which makes sure that we're just picking the highest probability action"}, {"start": 2070.56, "end": 2071.6, "text": " Okay"}, {"start": 2071.6, "end": 2073.44, "text": " Let's summarize this"}, {"start": 2073.44, "end": 2075.36, "text": " the principal difference"}, {"start": 2075.36, "end": 2079.6, "text": " Differences are that alpha goes zero does not use any rollouts"}, {"start": 2079.6, "end": 2084.08, "text": " It uses a single neural network instead of a separate policy and value networks"}, {"start": 2084.72, "end": 2087.8399999999997, "text": " Leaf nodes are always expanded so there is no threshold"}, {"start": 2087.8399999999997, "end": 2095.7599999999998, "text": " We don't have to wait until maybe 40 or something which was dynamically computed so that the gpus are not starving some optimization stuff"}, {"start": 2097.04, "end": 2101.04, "text": " And so we just expand it as soon as we encounter a leaf node"}, {"start": 2101.04, "end": 2106.72, "text": " We expand it and each search thread simply waits for the neural network evaluation. So it's synchronous"}, {"start": 2106.72, "end": 2109.7799999999997, "text": " Rather than performing evaluation and backup asynchronously"}, {"start": 2111.2, "end": 2116.3999999999996, "text": " And also there is no tree policy, which if you remember just I used to set up priors"}, {"start": 2116.56, "end": 2121.8399999999997, "text": " So when we get to a leaf node, we used to use the tree policy which will set some fast priors"}, {"start": 2122.24, "end": 2126.3199999999997, "text": " And we would send the leaf node onto gpu where the policy network"}, {"start": 2126.72, "end": 2133.4399999999996, "text": " SL policy would wait and it will it will do an inference and calculate the actual priors which will then get swapped here"}, {"start": 2133.44, "end": 2139.28, "text": " But here so but so this is basically a placeholder network and we don't have it anymore"}, {"start": 2139.52, "end": 2145.2000000000003, "text": " So much less details actually, it's it's an easier algorithm. We're just using reinforcement learning and we got better results"}, {"start": 2147.04, "end": 2148.56, "text": " Okay"}, {"start": 2148.56, "end": 2151.84, "text": " Hopefully you got something out of this and now I just want to make it"}, {"start": 2152.48, "end": 2158.96, "text": " Clear what the differences are between this model and the alpha zero. So that's just a small additional step if you ask me"}, {"start": 2159.52, "end": 2162.7200000000003, "text": " Um, I don't think there was anything significant that happened there"}, {"start": 2162.72, "end": 2165.3599999999997, "text": " Okay here here here is it basically?"}, {"start": 2166.64, "end": 2168.64, "text": " There's just a couple of differences"}, {"start": 2168.8799999999997, "end": 2175.04, "text": " And I don't quite understand the first one. So they say alpha zero instead estimates and optimizes the expected outcome"}, {"start": 2175.6, "end": 2181.2, "text": " Taking account of draws or potentially other outcomes. So this part bugs me because um"}, {"start": 2182.16, "end": 2183.8399999999997, "text": " the alpha goes zero"}, {"start": 2183.8399999999997, "end": 2189.6, "text": " estimates the value so the value function estimates between plus one and minus one which where plus one means"}, {"start": 2189.6, "end": 2193.7599999999998, "text": " This player is going to win and minus one means we are certain we're going to lose"}, {"start": 2194.7999999999997, "end": 2198.08, "text": " Um, and so i'm not quite sure what they mean by that"}, {"start": 2198.08, "end": 2202.72, "text": " If you know, please leave a comment down there and the second one is obvious"}, {"start": 2202.72, "end": 2207.36, "text": " So the rules of chess and shogi are asymmetric. So in general symmetries cannot be assumed"}, {"start": 2207.36, "end": 2209.12, "text": " So that's something I already mentioned"}, {"start": 2209.12, "end": 2215.2, "text": " We want to get rid of that of that of picking uh, like an element from the dihedral group one of those eight"}, {"start": 2215.2, "end": 2222.96, "text": " Reflections rotation combinations, so we just want to ditch that and uh, they showed that they won't hurt the performance at all"}, {"start": 2223.68, "end": 2225.68, "text": " So yeah, um"}, {"start": 2226.16, "end": 2228.16, "text": " A little bit but we can compensate by compute"}, {"start": 2228.24, "end": 2229.04, "text": " Okay"}, {"start": 2229.04, "end": 2236.1, "text": " And the third thing is in contrast alpha zero simply maintains a single neural network that is updated continually"}, {"start": 2236.8799999999997, "end": 2239.04, "text": " Rather than waiting for an iteration to complete"}, {"start": 2239.04, "end": 2245.14, "text": " Self play games are generated by using the latest parameters for this neural network omitting the valuation step"}, {"start": 2245.54, "end": 2250.1, "text": " And the selection of best player. So that means this time we have this network"}, {"start": 2250.58, "end": 2252.34, "text": " and instead of uh"}, {"start": 2252.34, "end": 2256.74, "text": " Doing these these periodic check pointing and comparing for the best model"}, {"start": 2257.14, "end": 2260.98, "text": " We are continuously using this same weights and we're updating them"}, {"start": 2261.54, "end": 2263.22, "text": " using the"}, {"start": 2263.22, "end": 2270.5, "text": " Replay buffer and the threads are just filling that buffer and we are just taking the data and we're continually updating this agent"}, {"start": 2270.8199999999997, "end": 2275.2999999999997, "text": " And when a new thread resumes so this one finishes and wants to start over again"}, {"start": 2275.4599999999996, "end": 2281.4599999999996, "text": " It will just fetch the newest the current the only pair of weights we are we are continually updating. Okay?"}, {"start": 2282.02, "end": 2286.58, "text": " So that's the third difference. So not a lot there and okay and um"}, {"start": 2287.7, "end": 2289.7, "text": " You can see the results"}, {"start": 2289.7, "end": 2293.9399999999996, "text": " Here basically on chess they compared against the stockfish"}, {"start": 2294.02, "end": 2298.18, "text": " That was the best engine at the time and you can see after"}, {"start": 2298.98, "end": 2301.14, "text": " Sometime it gets better than stockfish"}, {"start": 2301.7799999999997, "end": 2307.8599999999997, "text": " Finally, we have shroggy here in a small amount of time. The model gets better than shroggy, which is a japanese chess"}, {"start": 2308.64, "end": 2310.98, "text": " affectionately known as japanese chess and"}, {"start": 2311.7799999999997, "end": 2314.98, "text": " Finally we get better from alpha go zero"}, {"start": 2315.7799999999997, "end": 2318.1, "text": " after some training as well"}, {"start": 2318.1, "end": 2321.62, "text": " So what's interesting on these three charts if you ask me is this one"}, {"start": 2322.18, "end": 2322.8199999999997, "text": " so"}, {"start": 2322.8199999999997, "end": 2329.86, "text": " You can see how small the gap the elo gap here is and that just kind of indicates the amount of effort"}, {"start": 2330.18, "end": 2335.38, "text": " like decades of research of chess because chess was considered as the drosophila of AI because"}, {"start": 2336.02, "end": 2340.1, "text": " So many people so many researchers spent so much time"}, {"start": 2340.8199999999997, "end": 2344.74, "text": " researching it and so there are so many good heuristics in"}, {"start": 2344.74, "end": 2352.9799999999996, "text": " Good heuristics and a hand crafting that went into creating this stockfish engine that it was kind of hard to get much better than it"}, {"start": 2353.8599999999997, "end": 2355.8599999999997, "text": " So that's that's funny"}, {"start": 2355.8599999999997, "end": 2359.9399999999996, "text": " um, okay, the the only thing that's actually um, not so uh,"}, {"start": 2360.4199999999996, "end": 2366.18, "text": " Game agnostic is this so they are still adding the noise to the prior policy to ensure the exploration"}, {"start": 2366.18, "end": 2368.74, "text": " So directly noise I mentioned in the alpha go zero"}, {"start": 2368.74, "end": 2375.06, "text": " Um, and it's uh scaled in proportion to the typical number of legal moves for that game type"}, {"start": 2375.3799999999997, "end": 2380.8199999999997, "text": " So that's something that's game specific other than that. This is a pretty generic algorithm and yeah"}, {"start": 2381.22, "end": 2382.18, "text": " uh"}, {"start": 2382.18, "end": 2385.62, "text": " I think worth noticing here is that you have to train a single"}, {"start": 2386.18, "end": 2388.74, "text": " Instance a single agent for every specific game"}, {"start": 2389.06, "end": 2396.02, "text": " So that means this still doesn't generalize as much as we'd like it to so optimally you can train for alpha for go"}, {"start": 2396.02, "end": 2399.38, "text": " And then just kind of fine tune it for chess and it would be"}, {"start": 2399.94, "end": 2404.2599999999998, "text": " Uh really good, but that's not the case and you have to train it from scratch pretty much"}, {"start": 2404.74, "end": 2406.74, "text": " to the best of my knowledge"}, {"start": 2406.74, "end": 2411.22, "text": " um one thing worth noticing as well is that alpha zero searches just"}, {"start": 2411.7599999999998, "end": 2420.92, "text": " 80,000 positions per second in chess and 40,000 in shogi compared to 70 million for stockfish and 35 million for elmo"}, {"start": 2420.92, "end": 2429.16, "text": " So that just shows uh that this approach is much less brute force and these two the the elmo and stockfish"}, {"start": 2429.88, "end": 2435.7200000000003, "text": " Are much more similar to deep blue which used a brute force. Um algorithm to beat garry casparro back in 97"}, {"start": 2436.6, "end": 2443.4, "text": " So they say arguably a more human-like approach to to search and to to playing the games and I agree"}, {"start": 2444.04, "end": 2445.48, "text": " um"}, {"start": 2445.48, "end": 2449.64, "text": " So that's that's pretty much everything you need to know from alpha zero paper once you know"}, {"start": 2449.64, "end": 2457.0, "text": " Uh once you understand the alpha go and alpha go zero so ditch the symmetries keep continually updating the agent"}, {"start": 2457.48, "end": 2460.92, "text": " Um, and then you just kind of map for the specific rules"}, {"start": 2460.92, "end": 2467.64, "text": " You can you kind of do some small adaptations you apply the same algorithm and as you can see after some training time"}, {"start": 2468.2799999999997, "end": 2472.12, "text": " You can get that you can achieve state of the art on all the three benchmarks"}, {"start": 2472.8399999999997, "end": 2474.44, "text": " That was it for this video"}, {"start": 2474.44, "end": 2480.36, "text": " If you have any feedback whatsoever on the things I could improve, please feel free to just comment down in the comment section"}, {"start": 2480.52, "end": 2487.0, "text": " And i'll read those and you know the drill just hit that subscribe button hit the bell icon to get notified and until next time"}, {"start": 2487.0, "end": 2504.04, "text": " Keep learning deep"}]