Using MuZero's Tree Search To Find Optimal Tic-Tac-Toe Strategy in a Spreadsheet
Channel: Kevin Lubick
Date: 2022-06-11

A video that explores how the MuZero algorithm combines aspects of Reinforcement Learning and Monte Carlo Tree Search to play efficiently. The animations in the video make use of a spreadsheet which acts as a worked example of the calculations involved in the algorithm. Formulas discussed include Upper Confidence Bounds (for Trees, also called UCB or UCT).

MuZero Tree Search Spreadsheet:
 - https://bit.ly/MuZeroSheetCopy (if you want to mess with the values yourself)
 - https://bit.ly/MuZeroSheetView (if you just want to inspect)

Playlist implementing other neural networks in a spreadsheet:
 - https://www.youtube.com/playlist?list=PLDs5gxU1J5CIt5kIiQLC3RBOAKnUAo412

Reinforcement Learning explained by MIT:
 - https://www.youtube.com/watch?v=-WbN61qtTGQ

MuZero Paper and psuedocode:
 - https://arxiv.org/pdf/1911.08265
 - https://arxiv.org/src/1911.08265v2/anc/pseudocode.py

MuZero talk from one of the authors, Julian Schrittwieser:
 - https://www.youtube.com/watch?v=L0A86LmH7Yw
 - Slides https://drive.google.com/file/d/1nwRRQ3uWXDqX6eth4cHi96OYJ2wuW2Af/edit

Monte Carlo Tree Search Visualization by Vinícius Garcia
 - https://www.youtube.com/watch?v=ghhznqBoESY
 - https://vgarciasc.github.io/mcts-viz/

Other Articles on Reinforcement Learning
 - https://medium.com/applied-data-science/how-to-train-ai-agents-to-play-multiplayer-games-using-self-play-deep-reinforcement-learning-247d0b440717
 - https://dev.to/satwikkansal/a-gentle-introduction-to-reinforcement-learning-75h

Other Articles/Videos on Monte Carlo Tree Search (MCTS)
 - https://towardsdatascience.com/monte-carlo-tree-search-158a917a8baa
 - http://jeffbradberry.com/posts/2015/09/intro-to-monte-carlo-tree-search/
 - https://medium.com/@quasimik/monte-carlo-tree-search-applied-to-letterpress-34f41c86e238
 - Animation by J O https://www.youtube.com/watch?v=QH9h-XSi5nw

Reinforcement Learning and RTS games by Edan Meyer
 - https://www.youtube.com/watch?v=jzdodD3mX_o

Image Credits:
 - https://twitter.com/demishassabis/status/692430224382902272/photo/1
 - https://www.deepmind.com/research/highlighted-research/alphago

Narration by James K. Script and visualizations by Kaylee L.

0:00 - Why is MuZero important?
1:05 - Outline/Overview
1:50 - MuZero's three neural networks
3:11 - Key Vocabulary Terms - state, reward, policy, action, value
4:50 - Assumptions for Tree Search Example
5:18 - What will Tree Search find? (The best action)
5:38 - Tree Search Setup
6:55 - Tree Search Begins: Selection, Expansion & Evaluation, Tree Update
11:37 - Upper Confidence Bound (UCB) Formula Explained
14:12 - First Winning Move Discovered!
15:03 - Tree Search Value Explained
18:45 - Using Tree Search Results to Form Policy and Select Action
20:30 - Collecting Training Data
22:16 - Unrolling Representation, Dynamics, and Prediction Networks for Training
24:26 - Playing Better with trained Neural Networks
26:13 - Recap

Special Thanks to
 - Robbie Close and Pat Berard for excellent feedback on initial drafts

P.S. I was wondering where the UCB constant 19652 came from. I emailed the primary author and got the following response:
"19652 was found using automatic hyperparameter optimization. The exact value is not critical i.e. 19000 or 20000 would work just as well."
I looked more closely Appendix C (Hyperparameters) and see they did this tuning for AlphaZero and just used the same UCB constants for MuZero.