TwiddleLab / Artificial Intelligence / Search, Games and Plans
Monte Carlo: Play Random Games
What you will learn
- A random playout (rollout) finishes the game with random moves for both sides.
- Play many of them for each move and count the share of wins: the win rate. The highest bar is usually a good move.
- A few games jump around; many games average out (the law of large numbers). More playouts, stronger bot.
- This way of estimating with random samples is called Monte Carlo. It needs no strategy and no scoring rule.
How the lesson goes
Go has too many moves for minimax, and good scoring rules are hard to write. What if you just played random games to the end?
X to move. Bet: which move wins the most games if both sides then play completely at random?
Take one move and play random games from it.
Play 1 to watch a game. Then 10, then 100. Watch the bar.
Now give every move 100 random games and pick the best.
The violet part is the share of games X won.
Bottom left blocks O's diagonal, so O can't win at once, and X keeps chances to win. After the other moves a random O often finds the diagonal. The bot knows none of this: it only counts results.
This is called Monte Carlo search.
A random playout (or rollout) finishes the game at random. The share of playouts a move wins is its win rate. Using many random samples to estimate something is called Monte Carlo, after the casino.
A move won 62 of its 100 random games. What is its win rate?
62 wins out of 100 games is 62 / 100 = 0.62, or 62%. With 50 games it would be wins / 50 instead.
How many random games does the bot need?
Set the games per move, then rerun 5 times. Find a number where every rerun picks the best move.
Each win rate is an average of random results. Few games give a noisy average that jumps between reruns. Many games give a steady one: the law of large numbers. Then the best move wins every time.
Game: play against Monte Carlo bots.
First a bot with 10 random games per move: beat it. Then one with 300: don't lose.
A careless bot tried some moves more than others. Which move should it play?
Look at the win rate and at how many games it is based on.
A win rate from a single game is pure luck: it could just as well be 0%. 68 wins out of 100 games is a reliable estimate. A good Monte Carlo bot gives every move enough games before it trusts the numbers.
Same trick, new problem: estimate pi with random darts.
Throw darts at random. Count how many land inside the quarter circle.
Previous lesson: Alpha-Beta: Skip What Doesn't Matter · Next lesson: Planning: From Goal to Steps · Part of the course: Search, Games and Plans
Lessons are interactive and need JavaScript. Turn it on to play them.
