Monte Carlo Tree Search

01Judge a position by playing it out

The evaluation page scored a light-cycle position by counting the cells each bot reaches first, and the alpha-beta search of Minimax and Alpha-Beta used that number at its leaves. Ultimate Tic-Tac-Toe has no number like that. Counting won small boards misleads: Tom Alard, 2nd on CodinGame's Ultimate Tic-Tac-Toe leaderboard when he wrote about it in September 2026, notes that a player can be up two small boards to none "while having a completely lost position at the same time".^[1] And the very first move has 81 choices.

There's a way to judge a position that needs nothing but the rules. Finish the game from that position with random legal moves for both sides and see who wins. That finished game is a playout, also called a rollout. One playout says almost nothing. A thousand of them say something, because a position where X wins most random continuations usually leaves X more ways to win than O.

The simplest bot built on this gives every legal move the same number of playouts and plays the move with the best average result. That's flat Monte Carlo, named after the casino because the answer comes from random sampling.

Flat Monte Carlo has two problems. It spends as many playouts on B, which already looks worse, as on the two close contenders. And it judges each move against random replies: a move that loses to one particular answer still scores well when random play rarely finds that answer, while a real opponent finds it every time. The next section fixes the first problem; section 03 fixes the second.

02Spend playouts where they pay

Your bot gets as many playouts per turn as fit in the time limit, and every playout spent confirming that a bad move is bad is one not spent separating the two good ones. Choosing where the next playout goes is an old problem with a name: the multi-armed bandit. Picture a row of slot machines, each paying out with its own unknown chance. Every pull of an arm wins or loses, and you want as many wins as possible over many pulls, which means learning which machine is best while you play. In a search, each candidate move is an arm and each playout is a pull.

Two simple strategies show the trade-off. Greedy always pulls the arm with the best average so far, and can lock onto an arm that got lucky early. ε-greedy does the same but pulls a random arm a fixed share of the time (10% here), so it keeps checking the others, forever and at the same rate.

UCB1, from Auer, Cesa-Bianchi and Fischer, retries arms more selectively.^[2] It scores every arm by its average so far plus an exploration bonus and pulls the highest score. The bonus is large for an arm that has been tried rarely and shrinks each time the arm is tried, so a neglected arm gets an occasional retry until its average can be trusted.

In a search the arms are the moves from one position. The rule below picks which move gets the next playout, and it's the same rule the rest of this page uses.

In words: a move's score is its average result so far plus a bonus. The bonus shrinks as the move's own visits grow and creeps up slowly as the position's total N grows, so a move that stops being tried eventually gets tried again. c sets the exchange rate between a move's average and its uncertainty. A move with no visits yet is tried before any score is compared.

Auer and colleagues wrote the bonus as √(2 ln N ÷ visits), which is c = √2 ≈ 1.41 in this form, and proved that with rewards between 0 and 1 the regret of UCB1, the payout it loses by not always pulling the best arm, grows only with the logarithm of the number of pulls.^[2] The guarantee has to hold for any rewards between 0 and 1, and √2 is the value their proof uses. It says nothing about the best c for your game.

The lesson for a bot: tune c, and tune it for your own reward scale. The bonus is added to an average, so its effect depends on how far apart the averages are. Score playouts as 1, ½ and 0 and good and bad moves differ by fractions of a point; score them as 1, 0 and −1 and the same gaps are twice as wide, so the same c explores half as much. darkhorse64 told a player on the Ultimate Tic-Tac-Toe forum that "either 0,0.5,1 or -1,0,1 scoring are OK but you should modify accordingly your exploration parameter".^[3] Pick a scale, then measure c by playing versions of your bot against each other.

03Grow a tree, one playout at a time

Flat Monte Carlo judges your move by random replies. Suppose your move threatens to win and the opponent has exactly one reply that stops it. Random replies find that reply only now and then, so your move scores well, and a real opponent finds it every time. The fix is to give the opponent the same bandit treatment: at the position after your move, the opponent's replies are arms too, and the replies that work for the opponent get more playouts. Do that at every position the search reaches and you have a tree of bandits.

Kocsis and Szepesvári named this UCT, for UCB applied to trees.^[4] It's the classic form of Monte Carlo tree search (MCTS), a name that Browne and colleagues credit to Rémi Coulom's 2006 paper on his Go program Crazy Stone.^[5][6] A node in the tree is a position; its children are the positions one move later. Each node stores two numbers: its visit count, and its wins, scored for the player who made the move into it. Every iteration runs four phases, the names Chaslot and colleagues gave them:^[7]

1. Selection. Start at the root, the position you're deciding. While the current node has children, pick one with the UCB1 score, computed for the player whose turn it is there, and step down.
2. Expansion. At a node with no children, add its children to the tree (this page adds them all at once, on the node's second visit) and step into one of them.
3. Simulation. Play a random playout from there to the end of the game. None of the playout's positions are added to the tree.
4. Backpropagation. Walk back up the path to the root. Add 1 to each node's visits, and add the result to its wins from the point of view of the player who moved into that node: 1 for a win, ½ for a draw, 0 for a loss.

The tree gains one visited node per iteration, mostly under the moves that look best for whoever is to move, so the search reads the promising lines deepest. Because each node scores results for the player who moved into it, the same UCB1 rule picks X's best moves at X's nodes and O's best moves at O's nodes. And the search can stop after any iteration and still answer, which Coulom notes is "convenient for time management".^[6]

When time runs out, play the root move with the most visits, which the survey by Browne and colleagues lists as the "robust child".^[5] An average can be high by luck after a few visits. A visit count is high only if the move kept winning the UCB1 comparison as its visits grew, so it's the search's considered answer.

04UCT for tic-tac-toe in code

These complete programs implement the four phases for plain 3×3 tic-tac-toe. Each player's marks are one 9-bit number, with bit k set when that player owns cell k, so "which cells are free" is a single expression; Fast Bots builds the same trick for Ultimate Tic-Tac-Toe's small boards. The tree is one array of nodes, and a node's children sit next to each other in it, so a node stores only where its first child is and how many there are.

The harness checks the two claims in the comment at the top. First, with 2,000 iterations per move and c = 1.0, the search plays 1,000 games in each seat against a player that picks uniformly random moves: it wins 991 and draws 9 as X, wins 911 and draws 89 as O, and loses none. Second, it lists every position reachable from the empty board, solves each one exactly with plain minimax, and keeps the 1,686 positions where exactly one move wins. The search plays that move in all 1,686. Both programs print the same numbers, because they use the same random number generator and walk the tree in the same order.

// UCT (Monte Carlo tree search that picks moves with UCB1) playing tic-tac-toe.
// The harness in main() checks the page's two claims: from the empty board the search never
// loses to a random player, and it finds the winning move whenever exactly one move wins.
#include <algorithm>
#include <array>
#include <bit>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <set>
#include <vector>

// Cells 0..8 row by row. Each player's marks are a 9-bit mask: bit k set = owns cell k.
constexpr std::uint16_t FULL_BOARD = 0x1FF;
constexpr std::array<std::uint16_t, 8> LINES = {0x007, 0x038, 0x1C0, 0x049, 0x092, 0x124, 0x111, 0x054};
constexpr int PLAYING = 0, X_WINS = 1, O_WINS = 2, DRAW = 3;

struct Board {
    std::array<std::uint16_t, 2> marks{};  // marks[0] is X, marks[1] is O
    int toMove = 0;                        // 0 when X is to move

    std::uint16_t freeCells() const { return ~(marks[0] | marks[1]) & FULL_BOARD; }
    void play(int cell) { marks[toMove] |= 1 << cell; toMove ^= 1; }
    int result() const {
        for (int player = 0; player < 2; ++player)
            for (std::uint16_t line : LINES)
                if ((marks[player] & line) == line) return player == 0 ? X_WINS : O_WINS;
        return freeCells() == 0 ? DRAW : PLAYING;
    }
};

// xorshift64: tiny and fast, plenty for random playouts. Same numbers as the Rust version.
struct Rng {
    std::uint64_t state;
    explicit Rng(std::uint64_t seed) : state(seed | 1) {}  // a zero state would stay zero
    std::uint64_t next() { state ^= state << 13; state ^= state >> 7; state ^= state << 17; return state; }
    // Uniform in 0..count-1: the top 32 bits scaled by count, no division.
    int below(int count) { return static_cast<int>(((next() >> 32) * static_cast<std::uint64_t>(count)) >> 32); }
};

// Random moves until the game ends; returns the result.
int randomPlayout(Board board, Rng& rng) {
    while (board.result() == PLAYING) {
        std::uint16_t free = board.freeCells();
        for (int skip = rng.below(std::popcount(free)); skip > 0; --skip) free &= free - 1;  // drop lower free cells
        board.play(std::countr_zero(free));
    }
    return board.result();
}

struct Node {
    int cell = -1;        // the move that led to this node
    int firstChild = -1;  // a node's children sit next to each other in the node array
    int childCount = 0;
    int visits = 0;
    double wins = 0;      // results for the player who played `cell`: win 1, draw 0.5, loss 0
};

class Search {
public:
    Search(double exploration, std::uint64_t seed) : exploration(exploration), rng(seed) {}

    // Runs `iterations` iterations from `root` and returns the most visited move.
    int bestMove(const Board& root, int iterations) {
        nodes.clear();
        nodes.push_back(Node{});
        for (int i = 0; i < iterations; ++i) iterate(root);
        const Node& top = nodes[0];
        int best = -1, mostVisits = -1;
        for (int child = top.firstChild; child < top.firstChild + top.childCount; ++child)
            if (nodes[child].visits > mostVisits) { mostVisits = nodes[child].visits; best = nodes[child].cell; }
        return best;
    }

private:
    std::vector<Node> nodes;
    double exploration;
    Rng rng;

    void iterate(const Board& root) {
        Board board = root;
        std::array<int, 10> path{};  // the root plus at most nine moves
        int length = 0, current = 0;
        path[length++] = current;
        // 1. Selection: follow UCB1 down through nodes that already have children.
        while (nodes[current].childCount > 0) {
            current = select(current);
            board.play(nodes[current].cell);
            path[length++] = current;
        }
        // 2. Expansion: a node reached for the second time gets all its children; step into one.
        if (board.result() == PLAYING && (nodes[current].visits > 0 || current == 0)) {
            expand(current, board);
            current = nodes[current].firstChild;  // the children are shuffled, so this one is random
            board.play(nodes[current].cell);
            path[length++] = current;
        }
        // 3. Simulation: a random playout scores the new position.
        const int mover = board.toMove ^ 1;  // who played the last move on the path
        const int outcome = randomPlayout(board, rng);
        double reward = outcome == DRAW ? 0.5 : outcome == mover + 1 ? 1.0 : 0.0;
        // 4. Backpropagation: each node on the path scores the result for its own mover.
        for (int i = length - 1; i >= 0; --i) {
            nodes[path[i]].visits += 1;
            nodes[path[i]].wins += reward;
            reward = 1.0 - reward;  // one level up, the other player moved
        }
    }

    // UCB1: average result plus a bonus that shrinks as a child collects visits.
    int select(int parent) const {
        const Node& node = nodes[parent];
        const double logVisits = std::log(static_cast<double>(node.visits));
        int best = node.firstChild;
        double bestScore = -1.0;
        for (int child = node.firstChild; child < node.firstChild + node.childCount; ++child) {
            const Node& candidate = nodes[child];
            if (candidate.visits == 0) return child;  // try every move once before comparing
            const double score = candidate.wins / candidate.visits
                + exploration * std::sqrt(logVisits / candidate.visits);
            if (score > bestScore) { bestScore = score; best = child; }
        }
        return best;
    }

    // Adds one child per legal move, in random order so ties don't favour low cells.
    void expand(int parent, const Board& board) {
        std::array<int, 9> cells{};
        int count = 0;
        for (std::uint16_t free = board.freeCells(); free != 0; free &= free - 1) cells[count++] = std::countr_zero(free);
        for (int i = count - 1; i > 0; --i) std::swap(cells[i], cells[rng.below(i + 1)]);
        nodes[parent].firstChild = static_cast<int>(nodes.size());
        nodes[parent].childCount = count;
        for (int i = 0; i < count; ++i) { Node child; child.cell = cells[i]; nodes.push_back(child); }
    }
};

// ---------------------------------------------------------------- test harness
// Exact value for the side to move by plain minimax: 1 win, 0 draw, -1 loss.
int solve(const Board& board) {
    const int outcome = board.result();
    if (outcome == DRAW) return 0;
    if (outcome != PLAYING) return -1;  // the previous move won
    int best = -1;
    for (std::uint16_t free = board.freeCells(); free != 0; free &= free - 1) {
        Board next = board;
        next.play(std::countr_zero(free));
        best = std::max(best, -solve(next));
    }
    return best;
}

// Every position reachable from the empty board where the game is still on.
void collect(const Board& board, std::set<std::uint32_t>& seen, std::vector<Board>& out) {
    if (board.result() != PLAYING) return;
    if (!seen.insert(board.marks[0] << 9 | board.marks[1]).second) return;
    out.push_back(board);
    for (std::uint16_t free = board.freeCells(); free != 0; free &= free - 1) {
        Board next = board;
        next.play(std::countr_zero(free));
        collect(next, seen, out);
    }
}

int main() {
    constexpr int ITERATIONS = 2000;
    constexpr double EXPLORATION = 1.0;
    Search search(EXPLORATION, 2026);
    Rng randomPlayer(7);
    // Claim 1: 1,000 games in each seat against uniformly random moves, no losses.
    for (int searchSeat = 0; searchSeat < 2; ++searchSeat) {
        int wins = 0, draws = 0, losses = 0;
        for (int game = 0; game < 1000; ++game) {
            Board board;
            while (board.result() == PLAYING) {
                std::uint16_t free = board.freeCells();
                if (board.toMove == searchSeat) { board.play(search.bestMove(board, ITERATIONS)); continue; }
                for (int skip = randomPlayer.below(std::popcount(free)); skip > 0; --skip) free &= free - 1;
                board.play(std::countr_zero(free));
            }
            const int outcome = board.result();
            if (outcome == DRAW) ++draws; else if (outcome == searchSeat + 1) ++wins; else ++losses;
        }
        std::printf("search as %c: %d wins, %d draws, %d losses\n", searchSeat == 0 ? 'X' : 'O', wins, draws, losses);
        if (losses != 0) return 1;
    }
    // Claim 2: in every reachable position where exactly one move wins, the search plays it.
    std::set<std::uint32_t> seen;
    std::vector<Board> positions;
    collect(Board{}, seen, positions);
    int tested = 0, found = 0;
    for (const Board& board : positions) {
        std::vector<int> winning;
        for (std::uint16_t free = board.freeCells(); free != 0; free &= free - 1) {
            Board next = board;
            next.play(std::countr_zero(free));
            if (solve(next) == -1) winning.push_back(std::countr_zero(free));  // the opponent is lost
        }
        if (winning.size() != 1) continue;
        ++tested;
        if (search.bestMove(board, ITERATIONS) == winning[0]) ++found;
    }
    std::printf("positions with exactly one winning move: %d, found by the search: %d\n", tested, found);
    return found == tested ? 0 : 1;
}

// UCT (Monte Carlo tree search that picks moves with UCB1) playing tic-tac-toe.
// The harness in main() checks the page's two claims: from the empty board the search never
// loses to a random player, and it finds the winning move whenever exactly one move wins.
use std::collections::HashSet;

// Cells 0..8 row by row. Each player's marks are a 9-bit mask: bit k set = owns cell k.
const FULL_BOARD: u16 = 0x1FF;
const LINES: [u16; 8] = [0x007, 0x038, 0x1C0, 0x049, 0x092, 0x124, 0x111, 0x054];
const PLAYING: u8 = 0;
const X_WINS: u8 = 1;
const O_WINS: u8 = 2;
const DRAW: u8 = 3;

#[derive(Clone, Copy, Default)]
struct Board {
    marks: [u16; 2], // marks[0] is X, marks[1] is O
    to_move: usize,  // 0 when X is to move
}

impl Board {
    fn free_cells(&self) -> u16 { !(self.marks[0] | self.marks[1]) & FULL_BOARD }
    fn play(&mut self, cell: u32) { self.marks[self.to_move] |= 1 << cell; self.to_move ^= 1; }
    fn result(&self) -> u8 {
        for player in 0..2 {
            for &line in &LINES {
                if self.marks[player] & line == line { return if player == 0 { X_WINS } else { O_WINS }; }
            }
        }
        if self.free_cells() == 0 { DRAW } else { PLAYING }
    }
}

// xorshift64: tiny and fast, plenty for random playouts. Same numbers as the C++ version.
struct Rng { state: u64 }

impl Rng {
    fn new(seed: u64) -> Rng { Rng { state: seed | 1 } } // a zero state would stay zero
    fn next(&mut self) -> u64 { self.state ^= self.state << 13; self.state ^= self.state >> 7; self.state ^= self.state << 17; self.state }
    // Uniform in 0..count: the top 32 bits scaled by count, no division.
    fn below(&mut self, count: u32) -> u32 { (((self.next() >> 32) * count as u64) >> 32) as u32 }
}

// Random moves until the game ends; returns the result.
fn random_playout(mut board: Board, rng: &mut Rng) -> u8 {
    while board.result() == PLAYING {
        let mut free = board.free_cells();
        for _ in 0..rng.below(free.count_ones()) { free &= free - 1; } // drop lower free cells
        board.play(free.trailing_zeros());
    }
    board.result()
}

#[derive(Clone, Copy)]
struct Node {
    cell: u32,          // the move that led to this node
    first_child: usize, // a node's children sit next to each other in the node array
    child_count: usize,
    visits: u32,
    wins: f64,          // results for the player who played `cell`: win 1, draw 0.5, loss 0
}

impl Node {
    fn new(cell: u32) -> Node { Node { cell, first_child: 0, child_count: 0, visits: 0, wins: 0.0 } }
}

struct Search { nodes: Vec<Node>, exploration: f64, rng: Rng }

impl Search {
    fn new(exploration: f64, seed: u64) -> Search { Search { nodes: Vec::new(), exploration, rng: Rng::new(seed) } }

    // Runs `iterations` iterations from `root` and returns the most visited move.
    fn best_move(&mut self, root: &Board, iterations: u32) -> u32 {
        self.nodes.clear();
        self.nodes.push(Node::new(9));
        for _ in 0..iterations { self.iterate(root); }
        let top = self.nodes[0];
        let children = &self.nodes[top.first_child..top.first_child + top.child_count];
        let mut best = children[0];
        for child in children { if child.visits > best.visits { best = *child; } }
        best.cell
    }

    fn iterate(&mut self, root: &Board) {
        let mut board = *root;
        let mut path = [0usize; 10]; // the root plus at most nine moves
        let (mut length, mut current) = (1, 0);
        // 1. Selection: follow UCB1 down through nodes that already have children.
        while self.nodes[current].child_count > 0 {
            current = self.select(current);
            board.play(self.nodes[current].cell);
            path[length] = current;
            length += 1;
        }
        // 2. Expansion: a node reached for the second time gets all its children; step into one.
        if board.result() == PLAYING && (self.nodes[current].visits > 0 || current == 0) {
            self.expand(current, &board);
            current = self.nodes[current].first_child; // the children are shuffled, so this one is random
            board.play(self.nodes[current].cell);
            path[length] = current;
            length += 1;
        }
        // 3. Simulation: a random playout scores the new position.
        let mover = board.to_move ^ 1; // who played the last move on the path
        let outcome = random_playout(board, &mut self.rng);
        let mut reward = if outcome == DRAW { 0.5 } else if outcome as usize == mover + 1 { 1.0 } else { 0.0 };
        // 4. Backpropagation: each node on the path scores the result for its own mover.
        for &id in path[..length].iter().rev() {
            self.nodes[id].visits += 1;
            self.nodes[id].wins += reward;
            reward = 1.0 - reward; // one level up, the other player moved
        }
    }

    // UCB1: average result plus a bonus that shrinks as a child collects visits.
    fn select(&self, parent: usize) -> usize {
        let node = self.nodes[parent];
        let log_visits = (node.visits as f64).ln();
        let (mut best, mut best_score) = (node.first_child, -1.0);
        for child in node.first_child..node.first_child + node.child_count {
            let candidate = self.nodes[child];
            if candidate.visits == 0 { return child; } // try every move once before comparing
            let score = candidate.wins / candidate.visits as f64
                + self.exploration * (log_visits / candidate.visits as f64).sqrt();
            if score > best_score { best_score = score; best = child; }
        }
        best
    }

    // Adds one child per legal move, in random order so ties don't favour low cells.
    fn expand(&mut self, parent: usize, board: &Board) {
        let mut cells = [0u32; 9];
        let mut count = 0;
        let mut free = board.free_cells();
        while free != 0 { cells[count] = free.trailing_zeros(); count += 1; free &= free - 1; }
        for i in (1..count).rev() { let j = self.rng.below(i as u32 + 1) as usize; cells.swap(i, j); }
        self.nodes[parent].first_child = self.nodes.len();
        self.nodes[parent].child_count = count;
        for &cell in &cells[..count] { self.nodes.push(Node::new(cell)); }
    }
}

// ---------------------------------------------------------------- test harness
// Exact value for the side to move by plain minimax: 1 win, 0 draw, -1 loss.
fn solve(board: &Board) -> i32 {
    let outcome = board.result();
    if outcome == DRAW { return 0; }
    if outcome != PLAYING { return -1; } // the previous move won
    let mut best = -1;
    let mut free = board.free_cells();
    while free != 0 {
        let mut next = *board;
        next.play(free.trailing_zeros());
        best = best.max(-solve(&next));
        free &= free - 1;
    }
    best
}

// Every position reachable from the empty board where the game is still on.
fn collect(board: &Board, seen: &mut HashSet<u32>, out: &mut Vec<Board>) {
    if board.result() != PLAYING { return; }
    if !seen.insert((board.marks[0] as u32) << 9 | board.marks[1] as u32) { return; }
    out.push(*board);
    let mut free = board.free_cells();
    while free != 0 {
        let mut next = *board;
        next.play(free.trailing_zeros());
        collect(&next, seen, out);
        free &= free - 1;
    }
}

fn main() {
    const ITERATIONS: u32 = 2000;
    const EXPLORATION: f64 = 1.0;
    let mut search = Search::new(EXPLORATION, 2026);
    let mut random_player = Rng::new(7);
    // Claim 1: 1,000 games in each seat against uniformly random moves, no losses.
    for search_seat in 0..2 {
        let (mut wins, mut draws, mut losses) = (0, 0, 0);
        for _ in 0..1000 {
            let mut board = Board::default();
            while board.result() == PLAYING {
                let mut free = board.free_cells();
                if board.to_move == search_seat { let cell = search.best_move(&board, ITERATIONS); board.play(cell); continue; }
                for _ in 0..random_player.below(free.count_ones()) { free &= free - 1; }
                board.play(free.trailing_zeros());
            }
            let outcome = board.result();
            if outcome == DRAW { draws += 1; } else if outcome as usize == search_seat + 1 { wins += 1; } else { losses += 1; }
        }
        println!("search as {}: {} wins, {} draws, {} losses", if search_seat == 0 { 'X' } else { 'O' }, wins, draws, losses);
        assert_eq!(losses, 0);
    }
    // Claim 2: in every reachable position where exactly one move wins, the search plays it.
    let mut seen = HashSet::new();
    let mut positions = Vec::new();
    collect(&Board::default(), &mut seen, &mut positions);
    let (mut tested, mut found) = (0, 0);
    for board in &positions {
        let mut winning = Vec::new();
        let mut free = board.free_cells();
        while free != 0 {
            let mut next = *board;
            next.play(free.trailing_zeros());
            if solve(&next) == -1 { winning.push(free.trailing_zeros()); } // the opponent is lost
            free &= free - 1;
        }
        if winning.len() != 1 { continue; }
        tested += 1;
        if search.best_move(board, ITERATIONS) == winning[0] { found += 1; }
    }
    println!("positions with exactly one winning move: {}, found by the search: {}", tested, found);
    assert_eq!(found, tested);
}

Change ITERATIONS to 500 and the harness fails: the search loses 2 of its 1,000 games as O. With so few iterations the tree under some replies is still shallow, and random playouts misjudge those positions. More iterations fix it here, and Fast Bots shows where more iterations come from.

05Tune it for Ultimate Tic-Tac-Toe

Ultimate Tic-Tac-Toe is nine tic-tac-toe boards in a 3×3 grid. The cell you play inside a small board sends your opponent to the matching small board: play the top-right cell of any board, and your opponent must play in the top-right board. A small board closes when someone wins it or it fills up, and being sent to a closed board gives a free choice of any open board. Three won small boards in a line win the game; if every board closes without one, the player with more won boards wins, and equal counts draw. On CodinGame each player gets 1,000 ms for its first move and 100 ms for every move after that.^[8]

Plain UCT plays this game, and the players who climbed with it describe the same handful of changes in the game's forum thread and in their write-ups.

The exploration constant. jacek, who reached Legend with a Java bot, lists "fine-tuning exploration constant (it's generally much less than typical sqrt(2))". Di_Masta found that √2 − 1 ≈ 0.41 took his bot to 1st in Gold; after switching to rewards of 1, ½ and 0 and a few more hours of tuning, 0.5 put it 80th in Legend.^[3] Treat those values as starting points. Each is one bot's best setting, found with its own playouts and its own speed.

Playouts that take a win. Uniformly random playouts walk past wins. A cheap fix: in every playout, if the side to move can win the game at once, it does. jacek lists the "1-ply search win check during expansion and during playouts" among the changes behind his Legend bot.^[3] A decisive move check costs a few table lookups per playout move with the tables from Fast Bots.

A solver. Random playouts are noisy exactly where it hurts most, near the end, where one move can win most playouts and still lose by force. Winands, Björnsson and Saito show a Lines of Action position where five seconds of MCTS chose a move that won 67.2% of its simulations but loses by force in 8 plies, over a move that wins by force in 7 and scored 48.2%.^[9] Their MCTS-solver marks positions whose result is certain. A position is a proven win for the player to move if any move leads to a proven win, and a proven loss only when every move does; proven results go up the tree, the search stops spending playouts on them, and the bot never plays a proven loss. In Lines of Action their solver version beat plain MCTS in 65% of games. jacek lists a solver too.^[3]

Tree reuse. After you move and the opponent replies, the subtree under that pair of moves is still correct. Tree reuse keeps it, so the next search starts with thousands of visits already spent. Magus kept his tree between turns and allocated 5,000,000 nodes during the 1,000 ms first turn. RoboStac calls reuse "a very small increase in bot strength" and advises getting plain MCTS working first.^[3] The author's lab measured a larger gain for its own bot, in the next section.

The opening. As X, play the centre cell of the centre board. Tom Alard calls it "the only good move" for X's first move, and jacek says almost every Legend bot uses it.^[1][3]

Speed. More iterations make a stronger bot. Magus reached Legend in 2018 with about 25,000 playouts on his second turn; reCurse, answering a Gold player in 2019, wrote that the top of Legend "goes more towards 100k+".^[3] Tom Alard puts the reach of this design at "about top 50" on the leaderboard; the top bots he describes put a small neural network inside their search.^[1]

06From Gold to Legend with search

Each change above is a claim to test with games before you keep it. The author's lab rebuilt its Ultimate Tic-Tac-Toe bot around them in October 2026 and measured the main choices.

That record is one lab's pair of bots. It shows the lab's search beating the lab's network 64 games to 0; it doesn't show that search beats networks in this game. The strongest Ultimate Tic-Tac-Toe bots Tom Alard describes, his own and MrSubZero's, put a small neural network inside a search.^[1]

If a search does the thinking, where is the skill, and shouldn't every MCTS bot play the same? Both of the lab's bots ran MCTS, and one sat in Gold while the other reached Legend. They differ in everything this page has listed: how fast the simulator runs, the exploration constant, what the playouts do, the solver, tree reuse, how the turn's time is spent, and the hundreds of test games behind each setting. The algorithm's name is the same for every bot that uses it; the settings and the speed that decide its strength are yours to get right.

07When both players move at once

In Ultimate Tic-Tac-Toe the players take turns. In many CodinGame games they don't: both bots send their commands for the turn and the referee applies them together. Mad Pod Racing works this way. A tree that takes the two players' moves one after the other assumes the second player saw the first player's move before choosing, and in a simultaneous turn nobody does.

The smallest simultaneous game shows the problem. Purple and green each pick rock, paper or scissors at the same moment. In this version a win pays 1 with rock, 2 with paper and 3 with scissors, and the loser pays the winner, so the game is zero-sum. The table holds purple's payoff for each pair of picks.

Search this with an ordinary sequential tree, where purple moves and then green replies, and the tree assumes green sees purple's pick. Every purple move is then worth its worst case: rock −2 (green answers paper), paper −3 (scissors), scissors −1 (rock). The tree plays scissors every time, and a green bot that always plays rock beats it every round.

The right answer is a mixed strategy, a fixed chance for each move, and the target is an equilibrium: a mix for each player such that neither can gain by changing only its own. In a two-player zero-sum game, playing your equilibrium mix guarantees the game's value on average, whatever the opponent does.

The standard fix keeps one tree of game states but gives each player its own bandit at every node. Purple's UCB1 picks among purple's moves, green's among green's, each scored only by its own results, and the pair of picks decides which child state comes next. Tak, Lanctot and Winands call this decoupled UCT (DUCT), first used in the general game-playing program CadiaPlayer.^[11][12] The widget runs decoupled UCT at one node: both players pick at once, one random playout decides the round, and each learns only whether its own pick won.

The widget measures how far the players' mixes are from the equilibrium as the distance: how much a player who knew each mix could gain by playing the best answer to it, added up for both mixes, in the table's payoff units. Zero means both mixes are at the equilibrium.

The second rule in the widget, regret matching, comes with a guarantee. For each move it keeps a regret: how much more you'd have scored by playing that move every round so far than with the moves you actually played. Each round it plays each move with probability proportional to its positive regret, and uniformly when no regret is positive. That is the unconditional form of regret matching in Hart and Mas-Colell's paper, and their Theorem B states that it is universally consistent: in the long run your average payoff is at least as good as if you had always played any one move.^[13]

Lisý, Kovařík, Lanctot and Bošanský proved what that buys a search. When both players pick their moves with a rule of this kind, every move keeps getting tried, and each node passes up the average of all its results, simultaneous-move MCTS eventually converges to an approximate equilibrium of the entire game tree.^[14] Decoupled UCB1 has no such guarantee: they cite a one-move game, from Shafiei, Sturtevant and Schaeffer, in which it does not converge to the equilibrium.

The widget's regret matching learns only from its own playouts, so it estimates what the moves it didn't play would have earned, and it picks a uniformly random move 10% of the time, as the version Lisý and colleagues analyse does. The distance it still has at 100,000 rounds is noise from learning one playout at a time, and it keeps shrinking. Run the widget's code for ten million rounds and regret matching ends between 0.004 and 0.016 on the five seeds, while UCB1 stays between 0.12 and 0.30. Exploration can leave a floor of its own: in Lisý and colleagues' test games, regret matching converged to the equilibrium mixed with its uniform exploration. In this game it doesn't: the 10% of random picks alone would hold the mixes 0.13 away, and regret matching ends far closer, so its own picks make up for them.

A contest bot needs to beat the bots in its league, though, and decoupled searches still win CodinGame contests. MSz won the Summer Challenge 2024 with "a variation of DUCT, mostly fully decoupled, which is called Smitsimax here", and wrote that "the fully decoupled DUCT is fragile and exploitable, but I supposed that the budget is too small for a more fancy algorithm".^[15] bowwowforeach won the Summer Challenge 2025 with decoupled UCT, and frictionless won the Winter Challenge 2026 with a multi-tree search he also calls Smitsimax.^[16][17] With a few thousand iterations a turn, a rule that converges in the long run can still be far off, as the widget's 1,000-round curves show, and an exploitable mix only costs points against an opponent that exploits it.

MSz's sentence joins two different designs. In decoupled UCT a node is one game state, with one child per pair of moves and a separate bandit for each player inside it. Smitsimax, as MSmits described it for Coders Strike Back, gives every agent its own tree over its own moves only: four trees for four racing pods.^[18] Each iteration, every tree picks a move for its pod and the turn is simulated with all the picks together; then each pod's result goes back up its own tree. Because the other pods pick different moves on different iterations, "a node on this tree can correspond to many possible gamestates", in MSmits's words. It needs no child per pair of moves, and it only works when each agent's legal moves don't depend on what the others choose.

08Pitfalls

Playing the highest average. A move with a handful of lucky playouts can top the averages. Play the most visited move, or a proven win when the solver has one.

Copying c from a paper. The constant depends on the form of the bonus and on your reward scale, and the published "standard" values disagree by a factor of √2. Measure it with games between versions of your bot.

Putting playout positions in the tree. Only the node where selection stops gets children. RoboStac's advice to a player who was creating too many nodes: the moves in the random playout "shouldn't be using the tree or using nodes as this will be very slow and use too much memory".^[3]

Allocating inside the search. Allocate the node pool once, on the long first turn, and reuse it; allocation in the loop makes a turn's length unpredictable. Fast Bots covers it.

Tuning on a few games. The lab's constant comparisons above used 200 to 400 games each, and the c = 0.6 against 0.7 interval still ran from .44 to .58. Measuring Bot Strength works out how many games a decision needs.

A sequential tree for a simultaneous game. It assumes the opponent sees your move and steers you toward one predictable move. Use decoupled statistics or a tree per agent.

09What's next

Evolution and Beam Search takes on games where a move is a pair of numbers: a racing pod's steering angle and thrust in Mad Pod Racing. A tree over every angle and thrust is enormous. A short plan for the next few turns, improved by random changes inside the turn budget and carried over from turn to turn, is not.

10Sources

Widget readouts are computed in the page from the rules and seeds shown; they are not measurements of any CodinGame bot. Lab numbers come from the author's records, named in their source note.

1. Tom Alard, 2026. Fighting for #1 in the Ultimate Tic-Tac-Toe Arena, blog post of September 20, 2026, written while 2nd on the leaderboard. Why counting won small boards misleads, where random-playout MCTS tops out, the centre opening, and the network-inside-search designs of the top bots.
2. Peter Auer, Nicolò Cesa-Bianchi and Paul Fischer, 2002. Finite-time Analysis of the Multiarmed Bandit Problem, Machine Learning 47(2–3). UCB1 (Figure 1) and its regret bound, logarithmic in the number of plays, for any rewards in [0, 1] (Theorem 1).
3. CodinGame forum, 2018–2026. Ultimate Tic Tac Toe [Puzzle discussion], thread 22616. Players' reports quoted here: Magus #33 and #36 (2018: Legend at about 25,000 playouts, nodes allocated on the first turn, the tree kept between turns), reCurse #76 (2019: 100,000+ playouts at the top), darkhorse64 #88 (2020: reward scale and the constant), Di_Masta #103 (2020: constants of √2 − 1 and 0.5), jacek #150 (2023: solver, tuned constant, tree reuse, win checks in playouts), RoboStac #162 (2023: tree reuse as a small gain), jacek #195 (2024: the centre opening).
4. Levente Kocsis and Csaba Szepesvári, 2006. Bandit based Monte-Carlo Planning, ECML 2006. UCT: a separate UCB1 bandit at every node of the tree, the bonus written as 2C_p√(ln t/s), and negated values at the opponent's nodes.
5. Cameron Browne, Edward Powley, Daniel Whitehouse, Simon Lucas, Peter Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis and Simon Colton, 2012. A Survey of Monte Carlo Tree Search Methods, IEEE Transactions on Computational Intelligence and AI in Games 4(1), doi:10.1109/TCIAIG.2012.2186810. Coulom naming MCTS (Table 1), the bonus written as 2C_p√(2 ln n/n_j), and the most visited root child as the move to play.
6. Rémi Coulom, 2006. Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search, Computers and Games 2006. Crazy Stone's tree of random games, grown one node per simulation, and the search being anytime.
7. Guillaume Chaslot, Sander Bakkes, Istvan Szita and Pieter Spronck, 2008. Monte-Carlo Tree Search: A New Framework for Game AI, AIIDE 2008. The four named phases: selection, expansion, simulation and backpropagation.
8. CodinGame, 2025. game-ultimate-tictactoe, the official referee and statement (commit 30656ef). The rules summarized here and the time limits: 1,000 ms for each player's first move, 100 ms per move after that.
9. Mark H. M. Winands, Yngvi Björnsson and Jahn-Takeshi Saito, 2008. Monte-Carlo Tree Search Solver, Computers and Games 2008. Proven wins and losses inside the tree, the Lines of Action position where plain MCTS preferred a forced loss, and the solver version's 65% score against plain MCTS.
10. Author's lab records, 2026 (private repository): games/tictactoe/README.md (the MCTS bot, its tuning table and local matches), games/tictactoe/bots/baseline/ (the first bot), and experiments/live-submissions/tic-tac-toe/submitted.jsonl and rankings.jsonl (the submission, its Gold ranking and its promotion on October 29, 2026).
11. Mandy J. W. Tak, Marc Lanctot and Mark H. M. Winands, 2014. Monte Carlo Tree Search Variants for Simultaneous Move Games, IEEE CIG 2014. Decoupled UCT defined (Section III.A), its first use in general game playing, and its overall results despite its theoretical shortcomings.
12. Yngvi Björnsson and Hilmar Finnsson, 2009. CadiaPlayer: A Simulation-Based General Game Player, IEEE Transactions on Computational Intelligence and AI in Games 1(1). A separate model for every player, each choosing that player's moves by UCT.
13. Sergiu Hart and Andreu Mas-Colell, 2000. A Simple Adaptive Procedure Leading to Correlated Equilibrium, Econometrica 68(5), doi:10.1111/1468-0262.00153. Regret matching, including the unconditional form that plays each move in proportion to its positive regret and is universally consistent (Section 4, Theorem B).
14. Viliam Lisý, Vojtěch Kovařík, Marc Lanctot and Branislav Bošanský, 2013. Convergence of Monte Carlo Tree Search in Simultaneous Move Games, Advances in Neural Information Processing Systems 26. Simultaneous-move MCTS whose selection rule is Hannan consistent and keeps exploring, with nodes passing up their mean result, converges to an approximate subgame-perfect equilibrium (Theorem 4.11, Section 5.1); regret matching with uniform exploration, converging in their test games to the equilibrium mixed with that exploration (Section 5.2); UCB's failure to converge in a one-stage game, credited to Shafiei, Sturtevant and Schaeffer (2009).
15. MSz, 2024. Summer Challenge 2024 feedback and strategies, post #37. The winner's search, "a variation of DUCT, mostly fully decoupled", and why he chose it.
16. bowwowforeach, 2025. Summer Challenge 2025 post-mortem, post #13. The winner's search: decoupled UCT with a hand-written evaluation.
17. frictionless, 2026. Winter Challenge 2026 feedback and strategies, post #14. The winner's search: multi-tree MCTS with one tree per snake, which he also calls Smitsimax.
18. MSmits, online by July 2019. Smitsimax, tech.io playground, read from the Internet Archive's October 2024 copy (the original address now redirects). One tree per agent over its own moves, nodes that stand for many game states, the condition on legal moves, and the pointer to CadiaPlayer.