All projects

Game AI / search

Othello search engine and pruning ablation

An Othello engine in Java with four search shortcuts stacked together. It searches 15.5× fewer positions than plain alpha-beta search, yet loses to it in timed games; I measured why.

Stack
Java 8, Alpha-beta / PVS, Transposition table, Multi-ProbCut, Optuna

15.5×

fewer positions searched than plain alpha-beta

same depth, 24 midgame positions

4.45

moves considered per position, down from 11.8

median over 24 positions

42%

score against plain alpha-beta at equal time

60 games: 23 wins, 32 losses, 5 draws

An excerpt from a recorded game. Each move shows the square the engine chose and how many positions it searched, compared with plain alpha-beta on the same position.

Overview

Problem

A game engine looks ahead through possible moves, and the positions multiply with every move. Engines use shortcuts to skip parts of that search. I wanted to measure what each shortcut actually saves in an Othello engine, and whether searching less turns into winning more.

Approach

  • The Java engine starts from alpha-beta search, which skips moves that cannot change the result, and adds three more shortcuts: principal variation search, which checks the most promising move first; a transposition table, a memory of positions already evaluated; and multi-ProbCut, which predicts which lines are not worth searching.
  • Positions are scored on 20 features, such as corner control, mobility and stable discs, with weights tuned automatically.
  • Each version, adding one shortcut at a time, searched the same 24 midgame positions to a fixed depth; versions then played 60-game matches with equal time per move.

Results

With every shortcut on, the engine searched 15.5× fewer positions than plain alpha-beta and ran 13.4× faster. It considered about 4.45 moves per position instead of 11.8. Yet in timed matches it lost, scoring 42% against plain alpha-beta.

The measurements explain why. A bug in the position memory stored some partial results as final ones, so the search was correct on only 14 of 24 test positions; fixing it restored all 24. Multi-ProbCut's settings were also too aggressive, so it often cut lines that mattered.

What I built

  1. Built an Othello engine in Java on alpha-beta search with three further shortcuts: principal variation search, a transposition table that remembers positions, and multi-ProbCut.
  2. Wrote a 20-feature scoring function (corners, mobility, disc stability) with separate weights for the opening, middle and end of the game.
  3. Measured each shortcut on its own and found a bug in the position memory: the search was correct on 14 of 24 test positions, and on all 24 once fixed.

Results in detail

A left-to-right search tree. A rust chain runs through the middle as the principal variation, green circles mark expanded nodes, and grey boxes on dashed edges stand in for pruned subtrees.
Figure 1. One real search, drawn node by node. The engine’s main line is highlighted, and each faded node stands for a whole branch it chose to skip.
A log-scale line chart with five series over 24 positions; the fully optimised series in rust sits well below the others, with a bar summary beside it.
Figure 2. Positions searched on each of 24 midgame test positions as shortcuts are added one by one. The scale is logarithmic because the counts differ by up to 100×.

Does the pruning make it stronger, not just faster?

all-on vs each earlier configuration · 100 ms per move · 60 games each · 6 random opening plies

score for the all-on search (win = 1, draw = 0.5)

vs plain alpha-beta23W 32L 5D · n=60 · depth reached 9.5 vs 7.5
42% [31, 55]
vs PVS17W 40L 3D · n=60 · depth reached 9.9 vs 7.7
31% [21, 43]
vs PVS + TT19W 36L 5D · n=60 · depth reached 9.8 vs 8.2
36% [25, 48]
vs PVS + multi-ProbCut29W 30L 1D · n=60 · depth reached 10.0 vs 8.4
49% [37, 61]

The all-on search reaches +1.9 more ply per move and still loses ground to PVS, PVS + TT: the depth it buys is not worth what multi-ProbCut gets wrong.

The control points at multi-ProbCut: against PVS + multi-ProbCut, the one opponent that also runs it, the result is level (49%, interval [37, 61]). Every loss is to an opponent that does not run it.

Intervals are 95% Wilson on the score. A bar whose interval crosses "even" is not a result, it is a coin flip with this many games.

Colours alternate so each configuration plays both sides of every opening. Depth reached is the mean completed iterative-deepening depth per move.

Figure 3. Results of 60-game matches at equal time per move: the full engine against each simpler version. It scores below 50% against every one.
On the left, a diagram of a search node whose three children all fail low, with the true upper bound contrasted against the exact value the code stores. On the right, paired bars comparing the shipped table against the corrected one.
Figure 4. A bug found while measuring: the position memory stored some partial results as final. As shipped, the search was right on 14 of 24 positions; fixing it restored all 24.
A finished Othello board, almost entirely filled, beside the final disc counts.
Figure 5. The final position of the recorded game. Both sides used the same engine, so it shows the search at work, not its strength.
An Othello board with one square ringed in rust, beside a table of search statistics.
Figure 6. The most expensive search of the recorded game, with the number of positions it examined and the time it took.

Technical details

The full list of measured results behind this project.

Show all 10 measurements
MeasurementValue
nodes per second37k nodes/s
effective branching factor at depth 54.45 with everything on, against 11.80 unpruned (median of N(d)^(1/d) over 24 positions)
depth reached in 2000 ms12 ply median (range 7-16). Nominal: this is the deepest completed iterative-deepening iteration, and multi-ProbCut prunes hard enough that a nominal depth-16 search here is not an exhaustive depth-16 search
pruning percentage99.40% of the depth-6 tree never visited
node reduction, all optimisations vs plain alpha-beta15.5x fewer nodes, 13.4x faster
evaluation functioncoin parity, corner control, corner adjacency (one- and two-square), mobility (own, opponent, normalised difference) and disc stability, 20 features in all, with a separate weight vector per game stage (early / mid / end) tuned offline with Optuna
root value matches exact alpha-beta (depth 8, 24 positions)transposition table as shipped 14/24; with the bound classified correctly 24/24, for 12% more nodes; all optimisations on 4/24
node reduction over the recorded game, at the depth it was played (depth 6)6.9x fewer nodes over all 60 searched plies (median 2.7x per move, range 0.93x-25.9x). This is a different measurement from the 15.5x ablation figure, which is depth 8 over a separate 24-position set; the two are not interchangeable.
strength at equal time42% vs plain alpha-beta (23W 32L 5D); 31% vs PVS (17W 40L 3D); 36% vs PVS + TT (19W 36L 5D); 49% vs PVS + multi-ProbCut (29W 30L 1D)
leaf evaluations at the heuristic's clamp66.3% of leaf evaluations return the +/-63.99 limit

Limitations (11)
  • The clip's bottom strip reports a depth-6 re-search of the recorded game, where the full configuration visits 6.9x fewer nodes than plain alpha-beta over the game and 7.0x across the moves shown. That is not the 15.5x headline, which comes from the depth-8 ablation over a different 24-position set. Deeper searches and midgame-only positions both favour the pruning more; the endgame plies in this game favour it much less (down to 0.93x, where the optimised search visits slightly more nodes than plain alpha-beta).
  • "Depth reached in 2000 ms" is a nominal iterative-deepening depth. With multi-ProbCut on, the search is not even monotone in depth: at depth 9 it visits fewer nodes than at depth 8 on 7 of 24 positions. Read the depth number as "how deep the iteration counter got", not as an exhaustive search.
  • The agent's multi-ProbCut parameters are hardcoded to the same values at every height (OthelloAgent.java:206-209: d=2/3, t=2.0/2.2, a=1, b=0, s=1.5) rather than fitted by regression as the technique requires. That gives a cut margin of about 3 evaluation points on a function whose range is +/-64, which is why the speculative cuts fire so often and change the answer so often.
  • The shipped transposition table caches upper-bound results as exact values (OthelloAgent.java:537 and :605). Measured effect: the search returns exact alpha-beta's root value on only 14 of 24 positions at depth 8. This is a defect in the code under test, reported here rather than fixed; the project's sources were not edited.
  • The ablation runs an instrumented port of the agent's search (portfolio/othello/java), not the shipped OthelloAgent class, because the shipped search is private and time-driven and cannot be run at a fixed depth without editing it. Exactly what was checked: unpruned minimax, alpha-beta, PVS and PVS+TT return identical root values and identical best moves at depth 4 on the first four positions; PVS matches alpha-beta on root value and best move on all 24 positions at depth 8; and PVS+TT with the bound classified correctly matches alpha-beta's root value on all 24. That is what exact search must do, but the port is still a port, not the class that plays.
  • The port drops the shipped agent's wall-clock guards (TIME_BUFFER_*), its aspiration windows and its endgame exact-solve branch. Those matter under a real clock and are absent from these numbers.
  • 66% of leaf evaluations return the evaluation's +/-63.99 clamp, so at these depths a large share of leaves are indistinguishable to the search. This is a real weakness of the evaluation function, not a measurement artefact.
  • Wall-clock figures are a single run on one machine (Apple M4, Zulu JDK 8, single thread) after a JIT warm-up pass. Node counts are exact and deterministic; times are not.
  • The recorded game is a mirror match: both sides run the same fully optimised search. It demonstrates the search, it does not measure strength.
  • Strength was measured only between these five configurations. The library ships no graded reference opponents (only RandomAgent), so there is no external rating anchor.
  • The 24 positions come from random legal play to ply 24, not from human or engine games, so they are representative of arbitrary midgames rather than of strong play.