No neural nets, no tree: inside a Go engine that plays 40,000 games per second

In December 2012 — three years before AlphaGo — I wrote a Go AI in C++ called FoolGo. It has no neural networks, no opening book, no hand-crafted evaluation function. Just Monte Carlo tree search with UCB1, and enough systems engineering that it simulates about 40,000 complete games of Go per second — benchmarked on my 2014 MacBook Air.

It never got past beginner strength on 9×9, and I've always been upfront about that. Most of the repo's stars actually arrived after AlphaGo beat Lee Sedol in 2016: once the whole world wanted to know how Go AI worked, people came looking for the pre-intuition machinery in readable form — what the field ran on before neural networks learned to feel a board. This post is a tour of the engineering that makes vanilla MCTS fast — because for vanilla MCTS, fast is the only thing there is.

Why throughput is the whole game

Pure MCTS has no way to evaluate a Go position directly. To judge a candidate move, it plays random games from that position all the way to the end, and counts wins. Strength is roughly a function of how many of these playouts you can afford per move. There's no clever prior to save you — the engine is its simulation throughput. So every design decision below is about the same thing: making "play a full random game of Go" as close to free as possible.

Board size fixed at compile time

Everything in FoolGo is templated on the board length:

template<BoardLen BOARD_LEN>
class FullBoard { /* ... */ };

A 9×9 engine and a 19×19 engine are different types, compiled separately. That sounds like C++ showing off, but the payoff is concrete: every array in the hot path — the board, the chain structures, the hash tables of the hasher — has a size known at compile time. No std::vector growth, no heap allocation during search, no pointer chasing where an array index will do.

Stones as disjoint sets, in flat arrays

In Go, stones of the same color that touch form a string, and the string — not the stone — is the unit of life and death: the moment a string's last liberty (adjacent empty point) is filled, the whole string is captured and removed from the board at once.

Watch what a single move can do:

Before the move, black has two strings — and they are not equal. The pair at c4–c5 shares five liberties as one unit; the lone stone at e5 has been squeezed down to exactly one. In Go terms it is in atari: one White move from being eaten. Connecting at d5 is the rescue — and notice that this single placement fuses two strings and the new stone into one four-stone string with five liberties. Count the rings on the right: the arithmetic isn't additive. Merging liberty sets means deduplicating them — a detail that will matter shortly — and enemy stones don't count: White's four stones block four of what would otherwise be nine. The rescue cost White too: its d4–e4 string just lost one of its own liberties. Push any string's count to zero and it gets eaten — captured and removed from the board at once. A stone has four neighbors, so a single placement can fuse up to four strings (plus the new stone) into one.

And that's the disjoint-set view of the same event — before, two sets; after, one:

before:   set A: head = c5,  stones: c4 → c5,  c5 → c5
                 liberties {b4, b5, c3, c6, d5}
          set B: head = e5,  stones: e5 → e5
                 liberties {d5}

play d5:  union(A, B, d5)

after:    set A: head = c5,  stones: c4 → c5,  c5 → c5,  d5 → c5,  e5 → c5
                 liberties {b4, b5, c3, c6, d6}

Each stone points straight at its set's head, so find is a single array read. The price shows up at merge time: the absorbed side's stones get repointed to the surviving head — and MergeLists chooses sides by size, relabeling the smaller list into the larger (the classic union-by-size trick that keeps total relabeling cheap). So the freshly played stone, a list of one, never wins the election: here d5 and then e5 are repointed into the c4–c5 pair's head. And the liberty sets OR together, minus the point just filled, plus the new stone's own empty neighbors. Hold that picture; the code below is nothing more than this, made fast.

Now count what the engine must answer on every move of every simulated game:

• Which string does this neighbor belong to? — find
• Did my move drop that enemy string's liberties to zero? If so, remove all of its stones, immediately — an aggregate query plus member enumeration
• Is my move suicide? — the same query, pointed at my own string
• Did my move connect friendly strings? Merge them — union

At 40,000 games per second, a couple hundred moves per game, that's millions of move-executions per second, each running several of these queries. They all have to be near-O(1).

This is the union-find problem wearing a Go costume — with two extra requirements the textbook version doesn't have: each set needs cheap member enumeration (to delete a captured string from the board) and a cheap aggregate statistic (the liberty count that decides capture and suicide). FoolGo's ChainSet answers all of it with two flat arrays — one node per board point, one list record per potential chain:

struct Node {
  PositionIndex next_, list_head_;
} nodes_[BoardLenSquare<BOARD_LEN>()];

struct List {
  PositionIndex tail_, len_;
  BitSet<BOARD_LEN> air_set_;
  AirCount air_count_;
} lists_[BoardLenSquare<BOARD_LEN>()];

list_head_ is the find pointer — every stone knows its string's representative. The next_ chain makes members enumerable without searching the board — that's the capture-removal path. And the per-list air_set_/air_count_ are the aggregates that answer capture and suicide checks in constant time. Merging two strings is a list splice plus head-pointer updates — index arithmetic on preallocated arrays, no allocation, no tree balancing.

Liberties as bitsets

The expensive bookkeeping is the liberties themselves ("airs" in FoolGo's vocabulary): every placed stone changes the liberties of all its neighbors. FoolGo stores each string's liberties as a bitset over board points. When strings merge, their liberty sets merge with a bitwise OR; counting is a popcount. Some of the hottest bookkeeping in the engine compiles down to word-sized bit operations.

Here is the connection at d5 again, seen through the bitsets:

                    b4 b5 c3 c6 d5 d6      (75 more bits, all 0)
pair {c4,c5}         1  1  1  1  1  0
lone {e5}            0  0  0  0  1  0
new  {d5}            0  0  0  0  0  1

OR                   1  1  1  1  1  1
clear d5 (filled)    1  1  1  1  0  1     popcount → 5

Three ORs, one bit-clear, one popcount. There is no deduplication logic anywhere: d5, a liberty of both black strings, is simply the same bit twice, and OR-ing makes the duplicate vanish by construction. On a 9×9 board the whole set fits in two machine words, so "merge three strings and recount the result's liberties" costs a handful of CPU instructions.

Anatomy of a move

All of that bookkeeping exists to make one operation cheap: actually playing a move. Here is FoolGo's real pipeline, from full_board.h.

First, is the move even legal? IsSuicide looks at the four neighbors of the empty point — and at nothing else:

for each of the 4 neighbors:
    empty?                                 → not suicide (instant liberty)
    friendly string with ≥ 2 liberties?    → not suicide (joins a string that still breathes)
    enemy string with exactly 1 liberty?   → not suicide (the move captures it, freeing space)
none of the above                          → suicide

Four array reads. No board scan, no trial placement — every clause is answered by a per-string air_count_ that the merge machinery has been keeping current all along. The friendly clause needs ≥ 2 because the new stone fills one of that string's liberties on arrival; the enemy clause is the elegant one — a move onto your last-looking point is perfectly legal if it kills the surrounder first.

Here are the clauses on the board:

In the left position, e5 fails every clause: no empty neighbor, no friendly string to join, no enemy string at one liberty — suicide, illegal. Add a single black stone at d3 (middle) and the three-stone white string d4–d5–e4 falls to its last liberty: the same point now passes the kill clause. Play it (right) and the pipeline below runs — the string is eaten first, RemoveChain walking its cyclic list, so by the time the black stone lands it has two liberties: points it just vacated.

Then, play it. PlayBasicMove runs the same four-neighbor scan once more, now with consequences, in a very deliberate order:

1. Captures first. Any enemy neighbor string down to its last liberty is eaten on the spot: RemoveChain walks its cyclic list and clears the stones — and the newly emptied point next door is immediately recorded as a liberty of the stone about to be placed. The new stone breathes into the space it just vacated.
2. Place the stone, and clear its point's bit from every adjacent string's liberty bitset — friend and enemy alike.
3. Merge. AddPiece creates the one-stone set and union-by-size folds it together with its friendly neighbors — the disjoint-set dance from earlier.
4. Suicide cleanup. If, after all that, the just-built string has zero liberties, it is removed by the very same RemoveChain — suicide isn't a special case, it's a capture whose victim is yourself.

Every step is either a four-neighbor loop or an operation on the structures above — nothing touches the other 76 points of the board. That locality, times forty thousand games a second, is the entire performance story.

There is no tree

The textbook picture of MCTS is a tree of nodes with parent/child pointers. FoolGo doesn't build one. Instead, every game state maps to a 64-bit Zobrist hash, and node statistics live in a flat hash table:

struct StaySelfHasher {
  std::size_t operator()(HashKey hash_key) const {
    return hash_key;   // the key is already a hash — don't hash a hash
  }
};

std::unordered_map<HashKey, NodeRecord, StaySelfHasher> node_record_map_;

(StaySelfHasher is my favorite two lines in the repo: the key is a Zobrist hash, which is already uniformly distributed, so the map's hasher is the identity function.)

This is a transposition table, and it quietly upgrades the search from a tree to a DAG: two different move orders reaching the same position share one node and one set of statistics, for free. Whenever different move orders transpose to the same hashed state, that's not a micro-optimization — it's extra effective simulations without simulating.

Zobrist hashing, incrementally

Recomputing a position's hash from scratch would cost O(board area) per move. Zobrist hashing makes it O(changed stones): XOR out what left, XOR in what arrived.

HashKey GetHash(const FullBoard<BOARD_LEN> &b) const;              // full
HashKey GetHash(HashKey hash, const BoardDifference &chng) const;  // incremental

The scheme is beautifully dumb. At startup, generate one random 64-bit number for every (point, state) pair — FoolGo's table is literally board_hash_[81][3] — plus numbers for the side to move and for each possible ko point. A position's hash is the XOR of the numbers matching its current contents. Everything rests on one property: XOR is its own inverse, so XOR-ing the same number twice removes it. "Update" and "undo" are the same operation, and a move's hash cost is proportional to what the move changed:

h' = h ^ Z[d5][EMPTY]      // d5 stops being empty...
       ^ Z[d5][BLACK]      // ...and becomes black
       ^ Z[BLACK] ^ Z[WHITE]   // turn marker: XOR out "Black to move", XOR in "White to move"
       // plus one pair of XORs per captured stone, if any

The turn-marker pair is there because whose move it is is part of the position. Look back at the diagram: with Black to move, e5 gets rescued; with White to move, e5 gets eaten — opposite fates, identical stones. If those two states hashed the same, the transposition table would merge them and their statistics would be garbage. So exactly one of two random "to move" numbers is always XOR-ed into the hash, and each move swaps them. Our connection at d5 thus touches four numbers; a capture would touch two more per removed stone. Nothing else on the board is looked at — which is what lets forty thousand games per second afford a fresh hash after every single move.

The hasher also carries a table for the ko point (ko_hash_, plus a no-ko number), and the reason is subtle. After a ko capture, one point is temporarily illegal to play. Two boards with identical stones but different ko status therefore have different legal moves — and if they hashed the same, the transposition table would happily merge them into one node, letting statistics gathered in one position answer questions about the other. Getting ko into the hash is the kind of detail that costs you an afternoon of debugging exactly once.

UCB1, verbatim

The selection policy is the classic formula, and the code is honest about it:

float Ucb(const NodeRecord &node_record, int visited_count_sum) {
  return node_record.GetAverageProfit()
      + sqrt(2 * log(visited_count_sum) / node_record.GetVisitedTime());
}

Average observed value plus an optimism bonus that shrinks as a node gets visited: exploitation plus exploration in one line. Here it is with numbers — three candidate moves, a thousand playouts spent so far:

parent visits N = 1000          2·ln N ≈ 13.8

move   visits n   avg profit   bonus √(2·ln N / n)    UCB
A         700        0.52             0.14            0.66
B         250        0.46             0.24            0.70
C          50        0.38             0.53            0.91   ← next playout goes here

The next simulation goes to C — the move with the worst observed average. That's not a bug; the bonus is uncertainty made numeric. After only 50 samples, the search cannot yet distinguish a bad move from an unlucky one, so C's claim on the budget is still large. If C keeps disappointing, its average stays low while its bonus shrinks like √(ln N / n), and the playouts drift back to A, whose higher mean now stands on 700 samples. Spend where confidence is thinnest, harvest where confidence is strongest — the formula does both without a single special case. Everything else in the search exists to make evaluating it cheap, millions of times.

Multithreading by mutual avoidance

FoolGo searches on multiple CPU threads sharing the one transposition table (a mutex guards it). The interesting choice is how threads avoid redundant work: rather than implementing virtual loss — the standard trick of temporarily penalizing a node while a thread explores it — FoolGo simply forbids a thread from descending into a node a peer is currently exploring. Here's what that means at the node we just scored:

thread 1 arrives:  UCB says C (0.91) → descends into C, marks it in-progress
thread 2 arrives:  UCB says C — but C is taken → settles for B (0.70)
thread 3 arrives:  C and B both taken → gets pushed to A (0.66)
threads return:    marks cleared, statistics updated, selection sees fresh numbers

Thread 2 wanted C — the policy's actual choice — and got the runner-up; thread 3 got third-best. That's the distortion: under contention, the search behaves as if the top candidates were briefly invisible. Virtual loss is the gentler version of the same idea — a temporary penalty instead of a wall, so a favorite whose lead is big enough can still absorb several threads at once. FoolGo's wall is cruder. But it's a few lines, it can't deadlock, and it was enough to scale a hobby engine across the cores of a laptop.

How the grown-ups solved the same problems

FoolGo's choices get more interesting next to the famous open-source engines that came after it — Leela Zero (2017, the community AlphaGo-Zero reproduction) and KataGo (one of today's strongest open-source Go engines) — and the ones that came before it: GNU Go (whose board code dates to the 1990s), Pachi, and libego (Łukasz Lew's minimalist MCTS library). I went digging through their codebases to compare notes on the same subproblems.

One skeleton, five engines

Five engines, written independently across more than two decades, landed on the same core data structure — flat arrays over board points, a circular linked list threading each string's stones, one stone as the representative. The names barely differ: GNU Go (1990s) has string_number[] and next_stone[], Pachi has group_at[] and groupnext_at[], FoolGo has list_head_ and next_, Leela Zero has m_parent[] and m_next[], KataGo has chain_head[] and next_in_chain[]. There is no lineage here — the problem shape forces the answer — and GNU Go's comment from the 1990s could caption them all: "the stones in a string are linked together in a cyclic list." Five engines, two decades, one skeleton.

Six ways to count a breath

The chain skeleton converged; liberty bookkeeping went six different ways:

• GNU Go keeps an exact count plus the full list of liberty coordinates (string_libs[].list[]) — a classical engine wants to reason about specific liberties, not just count them.
• Pachi caps the list at ten, refilled lazily — its own comment admits libs "is only LOWER BOUND for the number of real liberties!!!" Playouts rarely need more than "is this 0, 1, or 2."
• libego never dedupes at all: pseudo-liberties plus algebra. Its Chain stores the count, sum, and sum of squares of its pseudo-liberty vertices — a chain is in atari exactly when count · Σx² = (Σx)², and the atari point is sum ÷ count.
• FoolGo: the exact set as a bitset — merge is OR, dedup by construction.
• Leela Zero: exact scalar counts, paid for with a dedup walk at merge time (plus a pseudo-liberty helper for rough checks).
• KataGo: exact scalar counts, incremental, with bound-estimating shortcuts.

Same invariant, six answers — ranked, roughly, by how much each engine wants to know about its liberties versus merely count them.

Three clauses, rediscovered

Playing a move converged even harder than the data structures. FoolGo's three-clause suicide test — empty neighbor: no; friendly with two-plus liberties: no; enemy with exactly one: no — turns out to be structurally identical in Leela Zero's is_suicide and KataGo's isSuicide: the same three clauses, in the same order — independent rediscovery, because the test is simply the minimal correct answer the rules allow. There is no fourth clause to invent: a move survives by gaining a liberty directly, joining something that outlives it, or making room by killing. Leela Zero merely bolts a pseudo-liberty fast path onto the front (if (count_pliberties(i)) return false; — any adjacent empty point settles it immediately). The real differences live at the edges. Pachi caches, for every point, how many of its neighbors are black, white, or off-board — immediate_liberty_count is just 4 minus those counts — so the commonest clause is answered without visiting the neighbors at all. And GNU Go plays moves reversibly: every board mutation is pushed onto a change stack (its comments report 20–30 entries per typical move) so the classical engine can read out a line and take it all back on a single board — whereas the playout engines, FoolGo included, never undo anything: they copy the board and let the copy die with the game.

The wall, the tax, and no locks at all

Parallel search reads as generations of one lineage — though not a chronological one. Fuego, the strong open MCTS engine of FoolGo's own era, had already gone further than everyone: a fully lock-free multithreaded tree search (Enzenberger & Müller, 2009) — three years before FoolGo's global mutex. Its source rewards reading even now: each thread allocates nodes from its own pre-allocated array and links them to the parent only once fully initialized; if several threads expand the same node, the last writer wins and the others' work — including value updates already made — is knowingly thrown away. Correctness traded against ever waiting. Every node field is volatile, virtual loss is already there (m_virtualLossCount), and the in-code docs cite the exact chapters of the Intel manual whose memory-ordering guarantees the whole scheme leans on. The fool was not early; he was simple. Within the lineage of the simple: FoolGo's forbid-peers rule (2012) is the blunt ancestor, Leela Zero (2017) does it properly with textbook virtual_loss() / virtual_loss_undo() folded into node evaluations, and KataGo is the industrial endpoint — virtual loss as a tunable (numVirtualLossesPerThread, an atomic counter per node), over a sharded node table with a mutex pool and fully atomic stats structs.

From tree to graph

The part that surprised me most. Leela Zero, for all its strength, uses a literal pointer tree and does not merge transpositions; there's even a comment in uct_select_child about counting parent visits manually "to avoid issues with transpositions." But in v1.11.0 (March 2022), KataGo shipped what its release notes call "a new stronger MCTS implementation that operates on a graph rather than a tree" — transposed move orders recombined into shared nodes, keyed by hash in a sharded node table. Which is, architecturally, what FoolGo's unordered_map<HashKey, NodeRecord> was doing in 2012.

Before I take a bow: KataGo's author also wrote a first-principles document explaining that naively applying tree-MCTS statistics to a DAG — exactly what FoolGo does — is unsound: shared nodes break the running-statistics formulation in subtle ways, and doing it correctly (plus handling ko and superko) is the actual hard part. So no, my hobby engine did not do graph search before KataGo. It wandered into the right building ten years early, without knowing why the floor needed reinforcing. KataGo's contribution was the reinforcement.

What it adds up to — and where it stops

Flat arrays, bitwise liberty tracking, incremental hashing, a pointer-free "tree," and threads that stay out of each other's way: 40,000 games per second on a laptop from 2014.

And yet: beginner strength. That plateau is the honest lesson of the repo. Uniformly random playouts are a terrible evaluation function, and no amount of throughput fixes their bias — stronger engines of that era spent their effort on playout policy, and then 2016 arrived and neural networks replaced blind rollouts with intuition. AlphaGo kept the tree search; it swapped out exactly the part FoolGo had made fast.

The repo is github.com/chncwang/FoolGo — readable on purpose, PRs welcome, and still, I'd argue, one of the clearer ways to see what game-tree search looks like with the covers off.

---

These days I build ClinTrialFinder, an AI-powered clinical-trial matcher, and write about building it at chncwang.substack.com.