Optimise the engine for AI search throughput

[Smartitect]

When running this code at the core of a stochastic search algorithm such as Monte Carlo Tree Search, it would be good to squeeze more performance of the core "move" method. Could the performance of the Board class be improved by use of other libraries such as:

• Numpy arrays and matrices, and making use of native methods to move and merge tiles?
• Storing the core Board as a byte array?

[Smartitect]

Expanded scope from the September 2026 project review. This issue now tracks the performance work.

Title: Optimise the engine for AI search throughput

If the engine is to be driven by a search algorithm (A*, BFS, MCTS), move evaluation
throughput is the binding constraint. The current implementation is written for clarity,
not speed.

Known costs

• Every tile is a Tile object; a board is 16 heap allocations plus a nested list.
• Moves mutate in place, so search has to deep-copy boards to explore alternatives —
  export_state() / re-Board() round-trips on every node.
• Each move runs two passes (__scooch_* then __go_*_1) over the grid.
• add_random_tiles probes random coordinates rather than sampling free cells
  (see add_random_tiles() hangs when n exceeds the number of free cells #8).

Directions worth evaluating

• Represent the board as a flat tuple of ints, or a 64-bit bitboard (4 bits per cell) —
  the standard approach for fast 2048 engines, and it makes states hashable for
  transposition tables.
• Precomputed row-move lookup tables: 65,536 entries covering every possible row, making
  a move four table lookups.
• Immutable moves returning a new board, removing copy overhead from search.

Process

Do not start until #10 is merged. The test suite is what makes this safe — the whole
point is to change the representation without changing behaviour.

Establish a benchmark (moves/second) before optimising, and report before/after.

Depends on: #10.

[Smartitect]

Plan: what to optimise, and what to try first

Everything below was measured in the dev container on this branch, not estimated. Baseline is the engine as it stands today (after #8, #14 and #20), playing random rollouts to a dead board.

Baseline: 195,000 moves/sec, 1,658 games/sec, single core.

Where the time goes

cProfile over 200 games, by self time:

Function	Share of self time	Why
get_empty_cells	highest single cost	called twice per move — once by can_move, once by add_random_tiles — and rebuilds a list each time
add_random_tiles	second	random.sample plus the list above
the four __go_*_1	~a third combined	one Python call per cell, per move
Tile.get_value	446,916 calls in 200 games	an attribute read behind a method call, per cell, per move

Nothing here is a mistake; it is the cost of a board made of 16 heap objects behind method calls.

What a search actually pays

Rollout throughput is the headline number, but a search's real unit is copy a position and try a move, because it explores alternatives from the same node:

	per node	nodes/sec
Current engine (export_state + Board() + make_move)	3.10 µs	322,000
Bitboard prototype (no copy needed — a board is an int)	0.31 µs	3,187,000

10x, and the interesting half is why: with the board as a single immutable int, there is no copy to make. export_state() / re-Board() round trips disappear from the search rather than getting faster.

Measured options

Each of these was built and benchmarked on the same workload. The bitboard prototype was validated against the current engine first — 120,000 moves across 30,000 random boards, 0 differences in resulting grid, score, moved flag or can_move verdict — because a speed number from a wrong engine is worthless.

Option	moves/sec	games/sec	vs baseline	Code change
Baseline (CPython 3.12)	195,000	1,658	1.0x	—
Run it on PyPy	393,000	3,342	2.0x	none at all
Bitboard + row lookup tables	408,000	3,440	2.1x	rewrite of the engine internals
Batched numpy, 8,192 boards at once	687,000	5,793	3.5x	new batch API alongside Board
Bitboard on PyPy	981,000	8,281	5.0x	rewrite, plus a second interpreter
Baseline across 8 processes	903,000	—	4.8x	none — rollouts are independent

Two results worth calling out because they contradict the obvious guess:

• PyPy needs a fair warm-up before it is judged. On a short run it looked slower than CPython (175k vs 189k). Over 6,000 games it is twice as fast. Any benchmark of this engine has to warm up first or it will mislead.
• The single-board bitboard rewrite only buys 2.1x end to end, despite being 10x faster per move. The Python interpreter overhead around the move — random.choice, the loop, the function calls — is what dominates a rollout, not the move itself. That is the single most important finding here: rewriting the representation alone does not get you an order of magnitude.

Recommended sequence

1. Land a benchmark harness first. Nothing else is meaningful without one, and the numbers above came from throwaway scripts. It needs: fixed-seed rollouts, a warm-up phase, moves/sec and games/sec, and the per-node copy+move figure. Cheap, and it makes every later claim checkable.

2. Take the free 2x: support PyPy. No code change, so the whole specification suite proves it still works. The cost is operational, not technical — pygame wheels for PyPy are the sticking point, so this probably means the engine and the search run on PyPy, the UIs stay on CPython. Worth confirming that before committing to it.

3. Then the representation, as Board's internals. Board as a 64-bit int, four 16-bit rows, one nibble per cell holding the exponent; moves as four table lookups over a precomputed 65,536-entry table, with a bit-trick transpose for up/down. Keep Board's public methods exactly as they are, so all three UIs and the whole specification suite carry over untouched. This is where the 10x per-node win lives, which is what a search actually spends its time on.

4. Only then consider batching. A vectorised batch API is a different shape of thing — rollout(board, n) returning n results rather than one move at a time — and it only pays off if the search is restructured to ask for many rollouts at once. MCTS can, but that is a search-side decision, so it should follow a working search rather than precede it.

Parallelism across cores (4.8x on 8 cores, no code change) composes with all of the above and belongs to whatever drives the search, not to the engine.

Constraints found while prototyping

• A nibble caps the maximum tile at 32,768. Exponent 16 does not fit in 4 bits, so a 32768+32768 merge cannot be represented. Real 2048 can reach 65,536. Either accept the cap and document it, or use 5 bits per cell (a 80-bit board, which loses the single-word advantage in Python anyway). Worth a decision before the rewrite, not during it.
• The merge-once rule needs re-checking. The has_merged guard on Tile never changes a move's outcome #20 removed the has_merged flag because the current move loop makes it redundant. Table-driven moves enforce it differently — the table encodes the rule directly — so it stays correct, but the specification in features/symmetry.feature is what proves that, and it must stay green.
• Board's public surface is load-bearing. Three front-ends and the whole suite use make_move, can_move, export_state, get_max_tile, score, merge_count, and the web layer reads board.grid directly. The rewrite should keep every one of them, and grid is the one that will hurt — it exposes Tile objects. Either keep a Tile-shaped view for compatibility or change the web layer to use export_state, which would be the tidier fix.
• Scores from before 4-tile spawn probability is 20%, standard 2048 uses 10% #14 are not comparable with anything measured now: the spawn rate changed from 20% to 10%. Current baseline for random play is a median score of 1024 over 113 moves.

How to know it worked

The target is the per-node figure, not the rollout figure, because that is what a search pays: copy-and-move under 0.5 µs, against 3.10 µs today. Rollout throughput above 1M moves/sec on one core is the secondary goal, and the combination of a table-driven engine on PyPy already reaches it in prototype.

Correctness is not negotiable in any of this, and the tools are already in place: the 75-scenario suite, plus the differential harness that replays complete games step by step against the previous engine — that one found nothing when has_merged was removed, which is exactly what made that change safe. Any representation change should be held to the same bar: identical grid, score, merge count and moved flag, on every move of hundreds of complete games, before the old implementation is deleted.

[Smartitect]

Evaluation: where the speed is, and what to do first

Measured on the dev container (8 logical cores, apparently about 4 physical ones), using a mid-game position. The prototypes were throwaway scripts and are not in the repo.

Where the time goes

• The search does about 19,000 rollouts a second. In the 0.5 s it gets per move, it builds a tree of about 450 nodes, 10 levels deep.
• About 99% of the time is spent in rollouts, split between add_random_tiles and the move loops in engine.py. Walking the tree and UCB1 scoring cost almost nothing.

So any gain has to come from making rollouts faster or more numerous.

1. Faster rollouts: the board representation (the original question in this issue)

Engine	Rollouts/s	vs today
Current Board	19k	1×
numpy, a single 4×4 board	0.6k–2.4k	slower
Bitboard (whole board in one 64-bit integer) in pure Python	25k	1.3×
numpy, N×4×4 stack of boards stepped together	39k–113k	2–6×
Bitboard compiled with Numba	875k	~46×

• numpy as the representation for Board itself: no. Each numpy call carries a few microseconds of fixed overhead, and a 16-cell board can't pay that back. Byte arrays and pure-Python bitboards barely help either, because Python's per-step overhead is the cost.

• Batched numpy is a real option. Every step of the game can be written as whole-array operations on an N×4×4 stack: moves through views (flipped, transposed, or both), sliding by a stable sort, merging by three comparisons of neighbouring columns, or a 65,536-entry row lookup table, and a vectorised spawn. The performance limits:

  • It levels off at about 6× (113k/s at N≈1,000–10,000) and falls at 100k as the arrays outgrow the CPU cache.
  • Batching the 50 rollouts at each node reaches only about 3×.
  • Larger batches mean restructuring the search into batched MCTS.
  • The same array code could run on a GPU via CuPy or JAX; this is untested.

• A compiled loop wins by a wide margin. A bitboard with row and column lookup tables, compiled with Numba, gives about 46× for rollouts. Once rollouts are that cheap, the Python tree code becomes the bottleneck, so the whole search should see roughly 10–20×.

• Behaviour check: every prototype was compared with Board. The numpy move functions match make_move exactly, in grid and score, on about 430 random boards in all four directions. The mean rollout scores agree: 211.8 for the engine, 211.7–211.8 for the prototypes.

• Recommended shape: leave Board as it is for the UIs and specs. Add a separate compiled rollout routine that only the search uses, pinned to Board by an equivalence spec: random boards, all four directions, the same resulting grid and score. Its costs:

  • a numba and llvmlite dependency;
  • a few seconds of compilation on first use, reduced by caching;
  • a seed passed into the compiled code, because it has its own random number generator.

  Rust via PyO3 would be as fast, but it needs a Rust toolchain in the dev container and a different package build setup.

2. More cores: parallel search

Approach	Rollouts/s	vs today
Threads (the GIL lets only one thread run Python at a time)	19k	1×
Process pool, 4 workers, one tree each ("root parallelism")	68k	3.6×
Process pool, 8 workers	91k	4.8×

• Root parallelism fits the design as it is. search.py runs unchanged in each worker, and the root visit counts are added up. The pool belongs inside MctsPlayer, as a workers setting or as a separate registered player, and the existing close() shuts it down. It should start workers with "spawn" rather than "fork", because it runs under uvicorn. Two browser games at once would compete for the same cores.
• Returns diminish. Eight 0.5 s trees give a better-averaged answer, but they are still shallow. They are not one 4 s tree. How much play improves needs a benchmark.
• Free-threaded Python (3.13t/3.14t) is installable through uv. A shared tree would still need locking or "virtual loss", and numpy and pygame support for free-threading is still patchy. Worth revisiting later.

3. Distributed workers connected by messaging or an API

• Not worth it for choosing moves. The per-move exchange is cheap: 16 small integers out and a 4-entry visit count back, one LAN round trip in a 0.5 s budget. The cost is everything around it:

  • finding workers and handling ones that die;
  • timing out slow workers visibly, because the contract doesn't allow silent fallbacks;
  • deployment, plus a Redis or NATS service or a new API;
  • specs that can't run a cluster.

  Splitting rollouts themselves across machines fails outright: with a fast engine, a batch of 50 rollouts takes about 57 µs, less than one round trip. A compiled engine on one core (~46×) beats several machines of root parallelism (~5× each).

• It does fit benchmarking. Playing hundreds of complete games to compare settings is fully independent work. A local process pool covers this first. Messaging (or Ray) is only worth adding if that becomes too slow.

4. Improving the MCTS algorithm itself

These are hypotheses until a benchmark exists. Parameter changes count as retuning and need numbers.

1. Scale the reward before the exploration term uses it. exploration=20 is compared with raw score differences, which grow from tens early on to thousands late in the game. So the search explores less and less as the game goes on, just when positions get hard.
2. Reuse the tree between moves. The part of the tree for the move actually played and the tile that actually spawned has already been searched. Today it is discarded every move.
3. Create spawn children only when needed. Every visited spawn node builds up to 30 children up front, most of which are never visited.
4. Re-measure rollouts_per_node=50. It is why the tree is only about 10 levels deep, and the trade-off changes once rollouts are cheap.
5. Replace random rollouts with something smarter: a guided rollout policy or a heuristic evaluation (empty cells, monotonicity, merge potential). The strongest published 2048 AIs use expectimax on bitboards, which would make a natural fifth player.
6. Merge identical positions. The same position can be reached by different move orders; a transposition table would search it once.

---

Proposed priority order

1. A benchmark runner. It plays N seeded games per player or setting across a local process pool and reports the score and max-tile distribution. Every later step needs it to show an improvement, and the specs deliberately cannot.
2. A compiled rollout routine (this issue). A Numba bitboard, pinned to Board by equivalence specs, with Board unchanged for the UIs. About 46× for rollouts and 10–20× for the whole search.
3. Cheap algorithm fixes, each benchmarked: reward scaling, tree reuse, and creating spawn children only when needed.
4. Local root-parallel search in MctsPlayer: about 3.6–4.8× more on top.
5. Retuning and stronger evaluation: rollouts_per_node, rollout policy, and perhaps an expectimax player. These need the numbers from step 1.
6. Distributed workers: only for benchmark sweeps, and only if one machine proves too slow. Not for choosing moves.

Alternative to step 2 if a compiler dependency is unwelcome: batched numpy rollouts at about 3× (a batch of 50 per node), or up to about 6× with batched MCTS.