Some videos for understanding Monte Carlo Tree Search
When I want to learn a new concept, I tend to look at multiple sources to see it from a variety of perspectives.
The videos shared in this article will help you to connect the dots in your own way.
It’s important that you seek inspiration rather than instruction if you aim to understand these concepts.
You will learn much better through inspired trial and error — especially if it leads to you self deriving your own algorithms or formulas.
Monte Carlo Methods
Named after the home of the world’s most exclusive casino, Monte Carlo methods use randomness to solve a wide variety of problems.
LeiosOS: What is Monte Carlo
Patrick Boyle: What is the Monte Carlo method? | Monte Carlo Simulation in Finance
For a GUI project, I used Monte Carlo methods to make a fairly convincing graph depicting stock prices. I added a bias using the Golden Ratio applied to the last time period, which somehow made it look a lot like a real stock graph.
Khan Academy: Monte Carlo Simulation to Answer LeBron’s Question
For those with an affinity to basketball, I’ve included this last video on Monte Carlo methods
Brownian Motion
Ever wondered why you keep walking past the same tree when you get lost?
Brownian motion holds the answer.
FuseSchool — Global Education: What Is Brownian Motion?
Markov Chain and Markov Chain Monte Carlo
Bonus Round: Iterative Deepening
It would be a crime to not introduce you to iterative deepening.
In a nutshell, it uses a depth-limited depth-first search and iteratively increases the depth limit.
Paradoxically this has the same algorithmic complexity as a depth-first search limited to the depth of the shortest path, but without you ever needing to know the shortest length beforehand.
Grasping this concept might give you more insight into tree search algorithms and how to come up with your own. For example, how about combining iterative deepening with random-walks?
Monte Carlo Tree Search
No videos. Instead, I ask you. How would you use randomness to solve a tree search problem?
Try it out yourself.
For inspiration I’ve defined a few problems you can solve with MCTS:
- Dominoes AI: it’s a simple game that’s easy to code and has few branching points.
- Blackjack AI
- Roulette wheel AI: this does not initially seem appropriate. But think about this one for a minute, and you’ll see it’s actually quite perfect. For extra credit, draw a graph of the odds of each turn and see if you can draw any conclusions for it, or ways to improve on your algorithm.
