Implementing a Go Engine in Rust with MCTS, RAVE, and Heuristic Rollouts

I recently found this page in a childhood notebook. My mother had pasted in two photographs: one of me pulling her into a game at home, and another of me listening to my Go teacher in class. I was five.

My rough translation of what I wrote is:

My mom enrolled me in Go class in 2010. It was my first extracurricular class. I liked Go more and more, and every time I came home I made my mom play a game with me. At first she could still beat me. Later, she could not keep up and I was always capturing her stones.

At the bottom, five-year-old me announced a more ambitious objective:

My goal is not only to occupy the golden corners and silver sides, but also to capture my opponent’s stones in battle!

I played regularly until I was fifteen or sixteen, then stopped playing consistently. I reached roughly amateur 1–2 dan. The loosest chess analogy would be around 2000 FIDE, although the ranking systems do not convert cleanly.

The strange thing is how little of the game feels gone. I can still see the corner shapes, approaches, invasions, and ways a group can live or die. Once you learn joseki that young, you do not remember them as a list of instructions. You see a shape and the continuations simply feel present.

I think education at that age does more than give you facts. It teaches you what thinking feels like. Go was one of the first formal systems through which I learned to:

• recognize a shape before I could fully explain it;
• hold a local fight and the whole board in mind at the same time;
• trade territory, influence, initiative, and uncertainty;
• know when to sacrifice something local for initiative elsewhere;
• accept that a move can be good without being immediately provable;
• build judgment from thousands of positions that are similar but never identical.

Go is surprisingly good at teaching lessons that outlive the game. I am writing this just after moving to San Francisco for the first time, a few days before starting at Neuralink, while AI is moving quickly enough to give plans an unusually short half-life. Two of the ten old maxims traditionally attributed to the Tang-dynasty player Wang Jixin feel especially relevant:

• 弃子争先: sacrifice a stone to gain initiative.
• 舍小就大: abandon the small and choose the large.

They are almost one rule in sequence. First decide what no longer deserves another move. Then spend the freedom it buys on the largest part of the board.

Fifteen years later, I wanted to take that intuition apart and make it explicit. Go gave me a reason to learn Rust, but the more interesting question became what computer Go looked like before neural networks supplied their own judgment.

Why build a classical engine?

What I find beautiful about classical Go engines is that they begin inside Go itself. Modern neural engines take methods from machine learning and apply them to Go as a domain. A classical engine asks how far we can get using:

• the rules of Go;
• statistical sampling;
• selective search;
• human knowledge about shape and sensible play.

That distinction is the point of this project. The engine plays legal 13×13 Go using an arena-allocated Monte Carlo tree, progressive widening, UCT with RAVE, and an explicit hand-written rollout policy. There is no learned policy network telling it which moves look human, and no learned value network telling it who is ahead.

Go is unusually beautiful terrain for that experiment. In chess, there are often only a handful of moves that appear remotely plausible. In Go, many moves remain possible, and their meaning may not become clear for a long time. The search space quickly exceeds what a person can calculate directly. That is why I think of Go as a game of imagination.

The rules are simple

For someone who has never played, the mechanical rules are much smaller than the game they create:

• Go is played on the intersections of a grid.
• Black moves first, then the players alternate placing one stone at a time.
• Stones do not move after they are placed.
• Directly adjacent stones of one color form a group.
• Empty intersections touching a group are its liberties.
• Filling an opposing group’s final liberty captures and removes the entire group.
• A move cannot be played on an occupied point or leave its own new group without liberties.
• The ko rule forbids an immediate recapture that recreates the previous position.
• Either player may pass, and two consecutive passes end the game.

The goal is to finish with more controlled area than your opponent. This engine uses Chinese area scoring, so a player receives one point for every stone on the board and every empty intersection surrounded only by that player’s stones. White receives 7.5 points of komi for moving second. The half point prevents a draw.

The standard board is 19×19. I use 13×13 because the rules and strategic tensions are the same, while the games are shorter and the search space is less absurd for an interactive browser demonstration.

The engine knows rules, not Go

A legal-move generator can understand liberties, captures, ko, and scoring without possessing any Go judgment. It knows that a move can be played. It does not know whether the move is sane.

As I kept saying while building this, “the engine begins with no Go knowledge. We have to encode it.” The most obvious source is joseki, the locally studied corner sequences that generations of players have treated as producing reasonable outcomes for both sides.

Joseki are not proofs. They are accumulated human evidence. We are not claiming that these are the only lines that work, because no one has enumerated every position. We are saying that these lines have repeatedly survived expert play and study, so they give us priors about which branches deserve attention.

Those priors become less reliable as a sequence grows:

• The first approach to a corner may have an enormous history behind it.
• A common response may still have thousands of professional examples.
• Ten moves later, the position is more sensitive to ladders, nearby stones, and the rest of the board.
• Far enough down one branch, the evidence becomes sparse and strong players begin to disagree.

In my words, “joseki is very imprecise.” That imprecision is not a defect. It is what makes joseki useful here: a prior should direct search without pretending to settle the answer.

The history also shows how provisional human priors are. Shusaku’s kosumi became an iconic response to a low approach against a 3-4 stone in nineteenth-century Japanese Go. It later lost favor as shin-fuseki and komi changed the value of slow, stable play, then modern AI helped revive interest in it. The Nihon Ki-in’s account of Shusaku explains how the move fit a no-komi style built around stability; a separate Nihon Ki-in AI lecture notes that modern AI evaluates the kosumi very highly.

There are even cleaner cases of social judgment changing the tree. In 1996, Go Seigen criticized a particular K16 continuation that had become popular despite respectable results. It nearly disappeared from professional play afterward. A 2025 study of more than 118,000 professional games uses the episode to show how prestige and shared information shape Go theory.

For this engine, joseki should therefore be a soft prior:

• search known continuations earlier;
• give them more initial attention;
• never make unfamiliar moves illegal;
• let enough contrary evidence override tradition.

The 4-4 low approach is a useful concrete example. Sensei’s Library lists six pincer responses with approximate professional-game frequencies of 22%, 9%, 3%, 3%, 2%, and 1%. Those numbers are sensitive to the whole-board position and come from a historical game sample. They are not claims that the most common move is objectively best.

Choose a response to place it on the board. The first percentage is the archived frequency among all responses to the approach. The second renormalizes only across these six pincers. That second number is closer to what a pincer-specific prior would need: conditional on searching this family, where should the first simulations go?

The positions and historical frequencies are redrawn from Sensei’s Library’s 4-4 point low approach reference. The diagram is intentionally a reconstruction rather than a copy of the source image.

Why the obvious search explodes

Suppose a position has $b$ legal moves. A complete search to depth $d$ has roughly

leaf continuations before we account for transpositions or illegal sequences. On an empty 13×13 board, Black has 169 placements plus pass. Even a shallow tree becomes absurdly large.

The deeper problem is not only the number of branches. Go does not give us a simple, reliable hand-written evaluation function for cutting the tree off early. More lines are not automatically useful lines. My immediate reaction as a Go player was, “just because you have more lines does not mean they are good.”

Play a legal move and change the depth. The counter uses the current number of legal choices as a deliberately rough branching estimate; it is not pretending that every later position has exactly the same choices.

The rules crate stores a point as one small index rather than carrying an $(x,y)$ pair through every search node. A move is either a placement or pass, which Rust expresses directly as an enum:

pub struct Point(u16);

pub enum Move {
    Play(Point),
    Pass,
}

This is one of the parts of Rust I like already: the type describes every valid shape of a move, so there is no magic coordinate reserved to mean pass.

Random games as measurements

Flat Monte Carlo changes the question. Instead of proving the value of every continuation, choose a candidate move, finish many games using a cheap rollout policy, and average the results.

For candidate $m$, let $R_i\in\{0, 0.5, 1\}$ be the loss, draw, or win produced by rollout $i$. Its estimated value is

The estimate is noisy. Its approximate standard error is

That number is not the objective value of the move. It estimates how the move performs when the rest of the game follows this particular rollout policy. Change the policy and you change the quantity being measured.

This board divides the selected budget evenly across every legal root move, including pass. The percentages are estimates from uniform-random continuations; the standard error beneath each move makes the lack of evidence explicit. On an empty board, 850 rollouts are only five samples per candidate.

Remember where the evidence was good

Flat Monte Carlo divides attention evenly. MCTS instead remembers which sampled lines look promising and spends more of the next budget there. One iteration has four phases:

1. Select a path through the existing tree.
2. Expand one legal move not yet represented by a child.
3. Simulate until two passes or a fixed rollout cap, then score the position.
4. Backpropagate its result through every node on the path.

The tree is not a proof of best play. It is a record of where the sampling process has accumulated evidence. The intuition finally clicked for me when I phrased it less formally: once one move starts producing strong results, spend more of the next budget down that branch, while still occasionally checking the alternatives.

Exploit, but keep exploring

The starting point for selection is the Upper Confidence Bound applied to Trees. For child $j$,

$W_j/N_j$ prefers moves whose sampled results have been good. The second term prefers moves with less evidence relative to their parent. $C$ controls the balance.

The engine adds two classical refinements to that score. The first is all-moves-as-first, usually called AMAF or RAVE. If a move appears later in a sampled continuation for the same player, it is weak evidence about what would have happened had we played that move immediately. The direct and AMAF estimates are blended as

where

The second is progressive bias. A normalized hand-written policy prior $P_j$ enters selection as $BP_j/(N_j+1)$. The complete score used by the tree is therefore

Both additions deliberately fade. RAVE matters most while direct evidence is scarce, and the policy bias shrinks with every child visit. An unvisited expanded child is selected before evaluating the finite formula, so the implementation never divides by zero. The final move is not the child with the largest temporary score; it is chosen randomly among the root children with the most direct visits.

This lab exposes the root of a full tree so the allocation is easy to see. It does not sample all 170 legal opening moves once. Progressive widening initially exposes one child and raises the limit approximately as $\lceil 0.55\sqrt{N+1}\rceil$. At the playable 512-iteration budget, that means only thirteen root moves enter the tree, leaving enough visits to compare them more than once. Change $C$ to alter the exploration pressure. The table reports direct visits, the direct mean, AMAF evidence and blend weight, exploration, progressive bias, and the final selection score; the same calculation is repeated below the root at every tree depth.

The search boundary keeps the experimental knobs explicit and reproducible:

pub struct SearchConfig {
    pub iterations: u32,
    pub exploration_constant: f64,
    pub progressive_bias: f64,
    pub rave_equivalence: f64,
    pub widening_constant: f64,
    pub widening_exponent: f64,
    pub rollout_cap: u16,
    pub rollout_policy: RolloutPolicy,
    pub seed: u64,
}

impl Default for SearchConfig {
    fn default() -> Self {
        Self {
            iterations: 1_000,
            exploration_constant: std::f64::consts::SQRT_2,
            progressive_bias: 8.0,
            rave_equivalence: 300.0,
            widening_constant: 0.55,
            widening_exponent: 0.5,
            rollout_cap: 512,
            rollout_policy: RolloutPolicy::Classical,
            seed: 1,
        }
    }
}

Those are the reusable library defaults. The playable browser search overrides them with $C=0.55$, a 220-ply rollout cap, and a choice of 256, 512, or 1,024 iterations. The UCT lab keeps $C$ adjustable and begins at $\sqrt 2$.

The seed matters as much as the rollout count: without it, two heuristic runs can differ because of random noise while looking like a meaningful algorithmic result.

A plausible Go heuristic can still be wrong

An obvious rollout improvement is to avoid self-atari. But as any strong Go player knows, self-atari is not synonymous with a mistake. Throw-ins, snapbacks, and forcing sequences often require it. When I first heard “avoid self-atari,” my reaction was: how else would you kill certain corner groups? A useful heuristic must remain a bias, not quietly rewrite the rules of good Go.

The engine therefore keeps two policies. UniformLegal is the control: every legal move has the same chance of being sampled. Classical assigns soft priors to moves a Go player would investigate first. Early in a game it favors vacant third- and fourth-line corners; after an opposing 4-4 move it recognizes the 3-3 invasion and the standard low and high approaches. During fighting it favors captures, atari, escapes from atari, local replies, connections, and hane-like shapes. It downweights empty triangles, filling one’s own eye, quiet edge moves, and non-capturing self-atari.

Progressive widening admits only a few candidates at first, then opens more branches as the node receives visits. Urgent captures and atari rescues enter a young tree before quiet moves. Progressive bias adds the policy prior to selection, but its influence decays as direct evidence accumulates. No legal move is deleted from the search space: first-line moves, second-line moves, self-atari, and pass all retain positive weight. The corner-pattern bonuses fade linearly, and all opening-region weights become neutral after forty moves. That is important because a second-line move can be nonsense on an empty board and mandatory in a fight.

Rollouts do not rescore the whole board on every ply. They always include urgent liberties and legal moves in the 3×3 neighborhood around the last move, add eight randomly sampled whole-board candidates, include pass, and sample among that bounded set using the explicit weights. This keeps local fighting coherent without preventing a tenuki elsewhere.

This makes the heuristics testable rather than decorative. I can run the same position, budget, and random seed under both policies and ask whether the extra Go knowledge actually helps. The joseki diagram above remains a reconstruction of historical human evidence; its six frequency values are not secretly used as an opening book. The search currently knows a small family of corner shapes, not full joseki sequences.

Play the current reference search

You play Black. The browser worker answers as White using the full Rust MCTS engine compiled to WebAssembly. It runs in sixteen-iteration batches so the page can stream analysis in the educational lab and cancel stale work when the board changes. After a played move, it re-roots an explored subtree when possible rather than automatically throwing the tree away. The playable board intentionally hides the dense candidate table; the UCT lab above exposes the same root statistics when I want to inspect them.

The demo uses Chinese-style area scoring, 7.5 komi, suicide forbidden, simple ko, and two passes to end the game. Positional superko, parallel search, opening databases, and neural networks remain outside this version. RAVE is part of the current classical search.

What neural networks supplied

Classical MCTS made sampling selective, but its rollouts still spent enormous effort on implausible Go. Learned policy networks supplied much better priors about where to search; learned value networks estimated positions without finishing every game. Neural search did not discard MCTS. It gave the tree far better judgment about which branches deserved computation and what their leaves meant.

Implementation note

The rules, browser renderer, search implementation, experiments, and site integration are built with AI assistance. My goal is not to claim that every line was handwritten. It is to understand the search well enough to explain the representation, the UCT equation, the four MCTS phases, and the limits of the resulting player.

Appendix: the Rust underneath the board

These are excerpts from the engine that powers the interactive boards, not separate pseudocode written for the article. They are the places where the statistical idea becomes a concrete program.

An arena instead of a recursive tree

A search node refers to its parent and children using small integer IDs. All nodes live in one growing vector:

#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct NodeId(usize);

pub struct Node {
    pub parent: Option<NodeId>,
    pub children: Vec<NodeId>,
    pub move_played: Option<Move>,
    pub position: Board,
    pub unexpanded_moves: Vec<Move>,
    pub policy_prior: f64,
    pub player_just_moved: Color,
    pub visits: u32,
    pub value_sum: f64,
    pub rave_visits: u32,
    pub rave_value_sum: f64,
}

pub struct Arena {
    nodes: Vec<Node>,
}

impl Arena {
    pub fn insert(&mut self, node: Node) -> NodeId {
        let id = NodeId::new(self.nodes.len());
        self.nodes.push(node);
        id
    }
}

This representation avoids a web of recursively owned and mutably shared Rust objects. NodeId(17) means “the node at index 17,” and that identity stays stable as the vector grows. The arena owns every node exactly once, while links between nodes are ordinary copyable values.

One complete MCTS iteration

The four phases are visible in one function:

pub fn run_iteration(&mut self) -> IterationTrace {
    let mut path = self.select_path();
    let selected = *path.last().expect("a search path always contains the root");
    if !self.arena.get(selected).position.is_terminal()
        && !self.arena.get(selected).unexpanded_moves.is_empty()
    {
        let child = self.expand(selected);
        path.push(child);
    }

    let leaf = *path.last().expect("a search path always contains the root");
    let simulation = rollout(
        &self.arena.get(leaf).position,
        self.config.rollout_policy,
        self.config.rollout_cap,
        &mut self.rng,
    );

    let trajectory = self.trajectory(&path, &simulation.trajectory);
    self.backpropagate(&path, simulation.outcome, &trajectory);
    IterationTrace {
        path,
        outcome: simulation.outcome,
    }
}

select_path follows UCT through nodes that already exist. expand adds one legal move when progressive widening permits it. rollout samples until the game ends or the cap is reached and returns the move trajectory. backpropagate increments direct visits and value only for nodes on the selected path, then records separate AMAF evidence for relevant siblings. Keeping those counters distinct is what lets RAVE share information without pretending the sibling was actually visited.

The backpropagation code stores every result from the perspective of the player who just moved at that node:

fn backpropagate(
    &mut self,
    path: &[NodeId],
    outcome: Outcome,
    trajectory: &[(Color, Move)],
) {
    for &id in path.iter().rev() {
        let node = self.arena.get_mut(id);
        node.visits += 1;
        node.value_sum +=
            f64::from(outcome.reward_for(node.player_just_moved));
    }

    for (depth, &id) in path.iter().enumerate() {
        let mover = self.arena.get(id).position.to_move();
        let children = self.arena.get(id).children.clone();
        if children.is_empty() {
            continue;
        }
        let mut seen = [false; BOARD_POINTS + 1];
        for &(color, candidate) in trajectory.iter().skip(depth) {
            if color == mover && !matches!(candidate, Move::Pass) {
                seen[move_index(candidate)] = true;
            }
        }
        let reward = f64::from(outcome.reward_for(mover));
        for child in children {
            let candidate = self
                .arena
                .get(child)
                .move_played
                .expect("a child has an incoming move");
            if seen[move_index(candidate)] {
                let child = self.arena.get_mut(child);
                child.rave_visits += 1;
                child.rave_value_sum += reward;
            }
        }
    }
}

The perspective detail prevents a subtle error. A win for Black cannot be added as a win from White’s perspective merely because both nodes lie on the same path. The per-node seen set also ensures that a coordinate captured and replayed during one simulation contributes only one AMAF sample at that ancestor.

Turning Go judgment into sampling probabilities

The classical rollout does not assign one final score to every legal move. It assigns a positive weight $w(s,m)$ to each move in its bounded candidate set, then samples according to

where $\mathcal C(s)$ is the current legal candidate set. The base weight is a product of small, explicit judgments:

Capture, rescue, and atari bonuses are then applied with a small floor so an urgent tactical move can overcome an early edge penalty. Eye filling and non-capturing self-atari remain ordinary multipliers below one.

The implementation is deliberately legible:

fn analyzed_move_weight(
    board: &Board,
    point: Point,
    analysis: go_rules::MoveAnalysis,
) -> f64 {
    let opening_ply = board.move_number().max(board.occupied_points() as u16);
    let mut weight = opening_region_weight(opening_ply, point.x(), point.y());
    if is_open_corner_move(board, point) {
        weight *= faded_multiplier(opening_ply, OPEN_CORNER_MULTIPLIER);
    } else if is_corner_approach_or_invasion(board, point) {
        weight *= faded_multiplier(opening_ply, APPROACH_MULTIPLIER);
    }
    weight *= local_pattern_weight(board, point);
    weight *= reply_distance_weight(board, point);

    if analysis.captures > 0 {
        weight = weight.max(1.0) * CAPTURE_MULTIPLIER
            * (analysis.captures as f64).sqrt();
    }
    if analysis.rescues_atari {
        weight = weight.max(1.0) * ATARI_RESCUE_MULTIPLIER;
    }
    if analysis.atari_targets > 0 {
        weight = weight.max(0.5) * ATARI_MULTIPLIER
            * (analysis.atari_targets as f64).sqrt();
    }
    if board.is_simple_eye(point, board.to_move()) && analysis.captures == 0 {
        weight *= EYE_FILL_MULTIPLIER;
    }
    if analysis.self_atari && analysis.captures == 0 {
        weight *= SELF_ATARI_MULTIPLIER;
    }
    weight
}

The square root gives diminishing returns to larger captures. Capturing four stones is favored over capturing one, but not by a factor of four. The self-atari multiplier is small rather than zero, which is how the program preserves throw-ins and other intentional sacrifices.

These numbers are hypotheses, not truths about Go. Their advantage over a learned model is that each one can be removed and tested. The useful comparison is not whether the heuristic sounds plausible. It is whether it wins more games than uniform random rollouts at the same search budget.

Why a tiny rollout count is mostly noise

For bounded results $R_i\in[0,1]$, Hoeffding’s inequality gives

Solving for an error radius at confidence $1-\delta$ gives

This bound is conservative, but it makes the basic problem obvious. Five random rollouts tell us almost nothing. MCTS does not magically remove that noise. It spends more of a fixed budget on branches whose early evidence is promising while the UCT exploration term keeps neglected alternatives alive.

A soft joseki prior

The next extension is to let known corner moves begin with a small amount of virtual evidence. If human knowledge supplies prior value $p_j$ for move $j$ and $\kappa$ is the equivalent number of virtual games, its prior-adjusted estimate would be

At the beginning, the prior matters. As the real visit count $N_j$ grows, observed results dominate it. This is the mathematical version of how I want joseki to behave: search familiar continuations earlier, but let the tree disagree with tradition.

What the current evidence says

The opening prior is not just present in a tie-breaker. It affects which move is expanded, enters selection through progressive bias, and shapes rollout sampling. RAVE adds a different kind of early evidence: it shares the result of moves that actually occurred later in the same simulation. Neither term participates directly in the final choice, which remains the most-visited root child.

I test this across fixed seeds rather than keeping one flattering screenshot. With the browser’s normal budget of 512 iterations, all twenty tested empty-board seeds chose a third- or fourth-line corner. After Black played a 4-4 point, all twenty responses were in a set declared in advance: another open corner, a 3-3 invasion, or a low or high approach. At the same iteration budget, the classical policy produced a plausible opening in 20 of 20 seeds, compared with 2 of 20 for uniform legal rollouts. Across forty small tactical searches, the classical policy chose the required capture or atari rescue 38 times, compared with once for uniform rollouts.

Those are regression tests for obvious failure modes, not a rank certificate. The engine still has no life-and-death solver, ladder reader, transposition table, full-board influence evaluator, or learned value estimate. Its rollouts remain noisy, and 512 iterations are tiny for Go. The result is now recognizably classical Go search rather than dressed-up randomness, but it is not strong by modern standards.

A full historical joseki prior would be a separate experiment. It could add virtual evidence from documented frequencies, but it would need to condition on the whole board and fade with both depth and direct visits. I have not implemented that database, and the interactive reconstruction should not be mistaken for one.

I started this project to understand MCTS and learn Rust. I did not expect it to bring me back to the same rule I learned on a Go board: 舍小就大. Abandon the small and choose the large.