Imagine you were planning a cross -country road
trip, and I don't just mean plugging a destination
into your phone and taking the main highways.
Right, that would be too easy. Yeah, exactly.
I mean, you decide for some completely wild reason
that you are going to map out absolutely every
single possible route, like every dirt road,
every wrong turn, every scenic bypass, every
single time you could possibly pull over for
gas or coffee or... You know, just stretch your
legs. I mean, it sounds completely exhausting
just thinking about it. You'd never actually
leave the driveway. You really wouldn't. Now
imagine doing that, but the map of those choices
is so unimaginably massive that the number of
possible routes is actually larger than the number
of atoms in the observable universe. Oh, wow.
Yeah. You are trying to find the single best
pass to your destination, but you literally cannot
see the whole map. It is physically impossible
to draw it all out. Which perfectly frames the
exact problem computer scientists faced when
trying to get machines to play highly complex
board games. The game tree, which is simply the
mathematical map of all possible moves and counter
moves in a game, it can become unfathomably huge.
And that impossible map is our mission for today's
Deep Dive. We are taking a stack of fascinating
sources, primarily centered around the Wikipedia
foundational document for a concept called Monte
Carlo Tree Search, or MCPA. Right, a very famous
algorithm. We are going to figure out the mathematical
magic trick that allowed machines to conquer
the most complex games in human history, like
the ancient board game Go, without needing...
explicit step -by -step human theories to do
it. It is an incredible story. And, you know,
while we are talking about artificial intelligence
and board games, the underlying mechanics here
are profound for anyone listening. Yeah, it's
bigger than games. Exactly. This isn't just about
AI playing games. It's about the fundamental
principles of decision making under severe uncertainty.
It's about how you or a machine can confidently
choose a path when you can't possibly know where
every single path leads. OK, let's unpack this.
To really understand how modern AI navigates
that impossible complexity, we first need to
establish why traditional computing hit a brick
wall. Like, people might remember that IBM's
Deep Blue Beat world chess champion, Garry Kasparov,
back in 1997. Right, a huge moment. So why did
it take another two decades for a computer to
master Go? Well, it comes down to something called
the branching factor. In chess, on any given
turn, you have an average of maybe 35 possible
valid moves. OK, 35. But in Go, you are placing
stones on a massive 19 by 19 grid. So the average
branching factor is around 250. Oh, wow. So every
single turn, the map of choices splits into 250
new paths. And then each of those splits into
250 more. Exactly. The game tree explodes exponentially.
In chess, early AI could use brute force to look
several moves ahead and then use a static evaluation
function. What does that mean exactly? Static
evaluation. It essentially looked at the board
and said, you know, I have more valuable pieces
than you, so I must be winning. But Go is so
fluid and abstract that a single stone placed
on turn 10 might quietly determine the outcome
of a massive battle on turn 150. Right. You cannot
easily evaluate who is winning just by looking
at a static board state. You have to play it
out. But we just established that playing it
out perfectly is impossible because there are
more paths than atoms in the universe. So how
did scientists solve a problem that is literally
too big to calculate? By entirely giving up on
calculating it perfectly, actually, and relying
on statistics instead. And the foundation for
that goes all the way back to the 1940s with
something called the Monte Carlo method. The
1940s. So this predates modern computers by quite
a bit. It does. The core idea of the Monte Carlo
method is to use random sampling to solve deterministic
problems that are just too difficult to solve
with traditional equations. OK, give me an example
of that. Think about it like this. If you have
a weirdly shaped pond and you want to know its
exact surface area, you could try to do incredibly
complex calculus. Or... You could draw the square
around the pond, throw 10 ,000 darts randomly
into that square, and just count the percentage
of darts that land in the water versus the dirt.
Oh, I see. You throw enough random darts, the
statistical average gives you a highly accurate
answer without doing any of the heavy math. Exactly.
That makes sense. But if they figured that out
in the 40s, why did it take so long to apply
it to games? Because applying it to sequential
decision making like a game required a conceptual
leap. and frankly, more computing power. The
sources point to 1987 as a major breakthrough.
A researcher named Bruce Abramson wrote his PhD
thesis combining traditional game search methods
with an expected outcome model. Meaning, instead
of the computer trying to statically judge if
a board position was good or bad, it just started
throwing darts. Precisely. Abramson said, What
if, from this current position, the computer
just plays out the rest of the game completely
randomly to the very end and sees who wins? He
tested it on tic -tac -toe, Othello, and even
chess. Wow. Then, in 1992, another researcher,
B. Brugman, applied this specifically to a go
-playing program. Which eventually led to Remy
Coulom officially coining the trim Monte Carlo
tree search in 2006. Yeah. And this foundational
concept, what they call pure Monte Carlo game
search, wild to visualize. It really is. It's
essentially like trying to decide the best opening
move in a game by cloning yourself 10 ,000 times,
having all those clones run out and make completely
random moves until someone wins or loses, and
then simply picking the initial move that resulted
in the most surviving clones. That is a highly
entertaining but actually structurally accurate
way to visualize pure Monte Carlo search. I have
to push back here though. Is it really that simple?
just chaotic randomness until a pattern emerges.
Because human strategy is so complex, it feels
like there has to be a catch. Well, the catch
is computational time. But mathematically, the
brilliance of pure Monte Carlo search is that
for games with a finite number of moves and a
finite length, like the board filling game Hex,
for example, it genuinely works. Really? Just
pure randomness. Yeah. As the number of random
simulations approaches infinity, the algorithm
naturally converges to optimal play. It eventually
finds the perfect move without needing to understand
the strategy of the game at all. It just knows
the mechanical rules of how pieces move, and
the law of large numbers does the rest. Okay,
so cloning yourself 10 ,000 times sounds great
in theory when you're writing a research paper.
But you... Sitting at a computer or playing a
game don't have infinite time. Right, you don't.
Do you have a few seconds before the turn clock
runs out? So how does a computer actually organize
this chaotic simulation process efficiently?
So it isn't just wasting time sprinting down
terrible paths. It requires a highly specific
architecture. The algorithm needs a structure
to build out its game tree smartly, prioritizing
the paths that actually show promise. This is
the anatomy of a decision within MCTS. There
are four distinct steps to a single round. Let's
walk through those steps. I think a scout analogy
works perfectly here for you listening. Imagine
you are an explorer trying to find treasure in
a massive, uncharted forest. Step one of the
algorithm is called selection. Selection, yes.
This is your scout walking down the path from
base camp that you have already partially mapped
out. You use a specific mathematical formula
to walk past the trees, choosing the most promising
route until you reach the very edge of your known
map. In computer science, that edge is called
a leaf node. And once that scout reaches the
leaf node, the frontier of the known map, the
algorithm moves to step two, which is expansion.
Expansion is the scout taking out a machete and
hacking through the brush to find just one new
clearing. You add one new potential move, one
new node to your map. Then comes step three,
simulation, which is sometimes called play out
or roll out. Right, and this is where the original
Monte Carlo magic happens. Yes, this is where
you tell your scout to just start sprinting wildly
in a completely random direction. Just completely
in the dark. Exactly. No machete, no map, just
run until you either find the treasure, hit a
wall, or fall into a pit. The computer plays
the game out using purely random moves until
a win, loss, or draw is reached. Which leads
to the fourth, and arguably the most crucial
step. Backpropagation. Backpropagation is the
scout running all the way back to base camp,
following the exact path they just took to tell
the boss the results of that wild sprint. They
update the data on a map. Yeah. Selection, expansion,
simulation, backpropagation over and over, thousands
of times a second. What's fascinating here is
how that backpropagation step mathematically
shapes the growth of the tree. Let's look at
how the scoreboard actually updates. Imagine
the computer is playing a two -player game. black
pieces versus white pieces. During backpropagation,
the computer tracks the ratio of wins to total
playouts for every single intersection or node
along that path. Now, if the white player loses
that random simulation, every single node along
the path increments its total simulation count.
The visits go up by one, but only the black nodes
get credited with a win. Wait, so even if white
is the one who played a specific move on that
path, Because white ultimately lost the simulation,
black gets the point on the scoreboard for its
own proceeding move. Precisely. You are keeping
score from the perspective of the player who
just moved. This brilliant little accounting
trick ensures that during the selection phase,
each player's choices naturally expand toward
the most promising moves for that specific player.
As a result, the tree grows asymmetrically. Oh,
that makes so much sense. It doesn't waste precious
time fully mapping out the terrible, obviously
losing moves. It naturally burrows deeper and
deeper into the lines of play where both players
are making strong, highly contested choices.
Exactly. It focuses the computing power exactly
where the battle is actually happening. But wait.
If backpropagation is constantly updating the
scoreboard and telling the scout where the gold
is, how does the algorithm decide whether to
keep mining that known gold vein or to go look
for a completely different, maybe bigger gold
vein in a different part of the forest? Now we
are hitting on the ultimate dilemma in computer
science and frankly in human psychology. Explanation
versus exploitation. This is one of the most
relatable concepts in the source material. Think
about it like going out to dinner. Exploitation
is deciding to go to that taco place down the
street because you have been there ten times
and you know it's a solid nine out of ten. You
have the data. It's a safe bet. Right. You know
what you're getting. But exploration on the other
hand is trying the brand new sushi spot that
just opened across town. It might be a transcendent
10 out of 10, but it also might give you terrible
food poisoning. You have absolutely no data.
So how does a machine solve human FOMO, the fear
of missing out? This raises an important question,
and it's one that researchers Levante Caxis and
Saba Shepesvary solved in 2006. Building off
earlier work from 2002 regarding Markov decision
processes, they introduced a mathematical formula
called UCT, which stands for Upper Confidence
Bounds Applied to Trees. UCT is essentially the
mathematical core for FOMO. I love that. Break
the UCT math down for us. How does it balance
the tacos and the sushi? So, the UCT formula
assigns a numerical score to every possible next
move, and the computer always picks the move
with the highest score. The formula is essentially
two halves added together. The first half is
the exploitation component. It simply looks at
the average win ratio of the move. If a move
wins a lot, this number is high. It aggressively
rewards going to the taco place. Okay, simple
enough. But if it only did that, it would just
find one good move and never look at anything
else. Exactly, which is why the second half of
the formula is the exploration component. This
part is a fraction. The numerator, the top number,
is based on the total number of times the parent
node has been visited. The denominator, the bottom
number, is the number of times this specific
child node has been visited. So if the computer
has run 100 simulations through the main base
cam, but has only sent a scout down this one
specific new path, twice. Then you have a large
number divided by a very small number, which
creates a massive result. As the total number
of simulations grows, the exploration value of
those unvisited, neglected nodes gets artificially
inflated. Mathematically, the unknown sushi place
starts screaming louder and louder until its
score actually eclipses the safe taco place,
and the algorithm is practically forced to send
a scout to go try it. That's so cool! Yeah, it
forces the computer to periodically double -check
its blind spots. That is absolutely brilliant.
It mathematically guarantees that the system
won't just get stuck in a comfortable rut. It
inherently values curiosity. And armed with this
UCT formula, Monte Carlo Tree Search basically
took over the gaming world. The milestones from
the sources are incredible. They really are.
In 2008, a program called MoGo reached master
level in 9x9 Go. By 2012, a program called Zen
beat an amateur in the full 19 by 19 game. And
the absolute pinnacle arrived in 2016. DeepMind
developed AlphaGo, which combined this UCT -guided
Monte Carlo tree search with deep neural networks.
Like, the big match. Yes. AlphaGo played a five
-game match against Lee Sedol, one of the greatest
professional Go players in human history, and
defeated him four to one. It was widely considered
a watershed moment in artificial intelligence.
Because the advantages of MCTS are perfectly
suited for it. It doesn't need an explicit evaluation
function. It handles massive branching factors
beautifully because it grows east and west. and
it can be stopped at any time to just yield the
best move it has found so far. But here's where
it gets really interesting. You just mentioned
AlphaGo beat Leicital 4 to 1, which means Leicital,
a human brain, won game four. He did. Wait. If
AlphaGo is this omniscient AI that evaluates
millions of futures a second and uses perfect
UCT math to balance exploration and exploitation,
how on earth did a human beat it? What happened
in game four? You are pointing out the Achilles
heel of Monte Carlo tree search. In the field,
we call them trap states. Trap states. Yeah.
Remember how we said the algorithm's greatest
strength is its asymmetrical growth. It focuses
its computing power only on the promising paths
and heavily prunes away the sequences it deems
less relevant or statistically losing. Right.
It ignores the bad moves to save time. But what
if a move looks superficially bad statistically?
It loses 99 % of the random rollouts. But it
actually sets up a devastating, highly subtle,
long -term trap 20 moves later. Oh, no way. Because
MCTS stops exploring paths that initially look
poor, a deeply subtle trap laid by a genius level
human can fall completely off the algorithm's
search radar. Oh. So it literally engineers its
own tunnel vision. AlphaGo looked at Lee Siedel's
incredibly weird setup moving game. for, ran
a few simulations, said, you know, statistically,
this looks like a weak line of play. I'm going
to ignore it and go mine my gold vein over here.
Exactly. And by the time the trap was finally
sprung, dozens of moves later, it was too late
for the computer to recover. Right. It confidently
pruned the very branch that held its own defeat.
Wow. So to fix these trap states and to deal
with the massive computational time required
to run millions of games, software engineers
had to figure out ways to supercharge MCTS. They
had to speed run the algorithm without ruining
the mechanics that made it special in the first
place. And the sources outlined several major
improvements engineers developed to do just that.
One of the primary shifts was moving from light
play -outs to heavy play -outs. Light play -outs
being the original concept, right? Like completely
random moves, sprints in the dark. Yes. Heavy
play -outs, on the other hand, apply heuristics,
human rules of thumb, to influence the choices
during the random sprint. Like prioritizing the
last good reply heuristic, or teaching the simulation
to recognize specific, known patterns of stones
and gurney go and react to them. But hold on,
I have to step in here. Aren't we just cheating
at that point? How so? If the entire beauty of
this system was that the machine learns on its
own from pure unadulterated randomness without
human bias, doesn't injecting expert human knowledge
back into the simulations defeat the whole purpose?
If we connect this to the bigger picture, it
reveals a genuinely fascinating paradox mentioned
in the research. You would logically think that
forcing the AI to play perfect expert human moves
during its simulations would make its overall
strategy stronger. Yeah, of course. But it turns
out playing sub -optimally during those random
simulations actually sometimes makes a Monte
Carlo tree search program play stronger overall.
Wait, making mistakes on purpose makes it better.
Yes. The AI desperately needs a little bit of
error to remain flexible. If you inject too much
expert human knowledge and make the simulations
too rigid and too perfect, the algorithm ironically
loses the ability to discover those weird, unpredictable
paths that human experts haven't thought of.
It needs the noise. It needs the chaos to find
the brilliant exceptions to the rule. That is
incredible. The flaw is the feature. Exactly.
And to speed the computations up even more, researchers
implemented techniques like RAV rapid action
value estimation. What's that? It's basically
a fur cut. If placing a piece in a certain spot
is a really good idea later in a random simulation,
the algorithm assumes it might be a good idea
to play it right now. It updates the value of
that move across the whole tree, regardless of
the exact sequence of prior moves. Oh, that makes
sense. It's all about extracting the absolute
maximum amount of actionable information from
every single random sprint. Right. And of course,
the most brute force way to supercharge this
is parallelization running multiple computing
threads at once. But that presents its own mechanical
nightmare. Because if you have multiple scouts
running through the forest, how do they all share
the same map? The source material lists leaf,
root, and tree parallelization. But how does
that actually work without breaking the system?
Well, think about tree parallelization, where
multiple processors are trying to build and update
the exact same game tree simultaneously. Imagine
four of your scouts running back to base cam
and all trying to draw on the exact same physical
piece of paper at the same time. That would be
a mess. They're going to bump hands, scribble
over each other's lines, and completely ruin
the map. Exactly. In computer science, to prevent
processors from overwriting each other's data,
you have to use mutex's mutual exclusion locks.
One processor essentially locks the data node,
updates it, and unlocks it before the next one
can touch it. But if they're constantly locking
the map, everyone else has to stand around waiting
to draw, which completely defeats the purpose
of being fast. Which is why alternatives like
route parallelization are so popular. Instead
of sharing one map, you just build completely
separate base camps. You let four different processors
build their own completely independent trees,
and at the end of the time limit, they all just
vote on the best opening move. No shared map,
no clashing hands. So what does this all mean?
We started this deep dive with the impossible
task of mapping a cross -country trip where the
potential routes outnumber the atoms in the universe.
A truly impossible task. We looked at a problem
that brute force and human calculation could
never solve. And what we found is that Monte
Carlo tree search takes the overwhelmingly infinite
and makes it solvable. Not through perfect godlike
knowledge of the whole map, but through structured
bounded exploration. It uses just a little bit
of randomness guided by the elegant math of what
works, constantly balancing the safety of the
gold it knows against the potential of the wild
frontier it hasn't explored yet. It truly is
a profound mechanism for navigating the unknown.
And the sources specifically note that MCTS is
increasingly being used in applications outside
of games, which leaves us with a highly provocative
thought to consider. Love those. Let's hear it.
If an algorithm can beautifully balance exploitation
and exploration to navigate the near infinite
futures of a go board, could we one day use MCTS
style simulations to map out the consequences
of our own massive global societal decisions?
Are we as a society stuck exploiting the comfortable
paths we already know? And is it time we purposely
injected a little UCT exploration into our own
lives to find the better future that might be
hidden right off our current radar? To purposely
wander off the known map, just see what's out
there. I love that. Thank you for joining us
on this deep dive. As always, keep questioning
the map and stay endlessly curious.