Monte Carlo tree search
How do I choose a move when I cannot say what a good position looks like?
Plays thousands of random games from each candidate move and favours the moves that won most, growing a tree where the results look promising.
Monte Carlo tree search needs no evaluation function. It judges a move by experiment: play the game to the end with random moves, many times, and count the wins.
Pure random sampling wastes effort on bad moves, so the samples are steered. Each round walks down a growing tree and, at every position, picks the move that balances two things: a good win rate so far (exploitation) and few tries so far (exploration). The usual rule is UCT: win rate plus c times the square root of ln N over n.
Because it only needs the rules, it works where scoring a position by hand is hard. Because it samples, it is random, and its strength grows with the number of games it is allowed.
Loading the demo…
Connect Four with Monte Carlo selected. Slide the number of random games per move and see how the AI’s play changes.
- 01Selection: from the root, keep stepping to the child with the highest UCT value until you reach a position that still has untried moves.
- 02Expansion: add one new child for one of those untried moves.
- 03Simulation: from the new position, play random moves until the game ends.
- 04Backpropagation: add the result (win, draw or loss) to every position on the path back to the root.
- 05Repeat for the allotted number of games, then play the move at the root that was visited most.
function mcts(root, iterations):
for i in 1..iterations:
node = root
while is_fully_expanded(node) and not game_over(node):
node = argmax over c in children(node) of
c.wins / c.visits + C * sqrt(ln(node.visits) / c.visits)
if not game_over(node): node = add_child(node, random untried move)
result = random_playout(node.position)
for n from node up to root:
n.visits += 1
n.wins += result_for(n)
return argmax over c in children(root) of c.visitsN is the number of random games, which you choose. Strength rises slowly with it, and the search can be stopped at any moment with a usable answer.
- No evaluation function to design or tune.
- Can be stopped at any time and still return a move.
- Copes with games that have many moves per turn.
- Random playouts can miss a tactic that a shallow search sees at once.
- The answer changes from run to run.
- A strong move needs many games, so it can be slower than a well-ordered alpha-beta.
- 01OthelloOne of five opponents. With no evaluation to tune, it is a useful check on the hand-made one.
- 02Connect FourJudges each column by how often random games that start with it end in a win.