Sampling / stochastic · 6 min read
Monte Carlo Tree Search
Many random futures, keep the best run. Many random safe rollouts within the tick limit; keep the run that reaches the exit soonest.
Why this category
Sampling / stochastic. Grow random trees or roll out simulated futures instead of exhaustively expanding every state.
How it explores
Exploring: 2 of 31 states checked
Why this category
Monte Carlo Tree Search is filed under Sampling / stochastic. This demo uses a lightweight spirit of the idea: simulate many random futures among safe neighbours and keep the best complete (or most progressive) run, rather than expanding every space-time state like Breadth-First Search.
It shares the Sampling bucket with RRT / RRT* because structure comes from rollouts, not an exhaustive frontier.
How it picks the next move
Run a fixed number of rollouts from the entrance. Each rollout picks uniformly among safe orthogonal neighbours until the exit, a dead end, or maxTicks. Score a success by fewest ticks; score a failure by how close the last cell got to the exit.
Return the best scoring path. The animation explores the cells visited on that winning rollout.
What it stores after a fail
Only the shared "x,y,phase" death calendar persists. Rollout trees are discarded after each attempt.
A larger blacklist shrinks the random options, so later Monte Carlo Tree Search attempts are biased away from phases that already killed you — without learning an explicit value function like Q-Learning.
More sampling / stochastic
Try it live
Run this algorithm on a built-in level, or paint your own grid and guards.