How Reversi AI works

This page describes the engine that runs on this site, not engines in general. Everything below is in the code that ships to your browser, and every position and number on this page is computed from the game library when the page is built.

Start here: why counting discs is the wrong idea

This is the single most useful thing to understand about Othello, for a programmer and for a player.

The obvious way to score a position is to count discs. It is also close to worthless. Below is a real position from a game between two copies of this engine at its Intermediate level. Black has 20 discs, white has 9. Black looks like it is running away with it.

abcdefgh

12345678

That game ended 22 to 42, to white. Black's big lead was not an advantage, it was a symptom. Owning lots of discs in the midgame usually means owning lots of discs on the edge of the empty space, and every one of those is a disc your opponent can flip and a square you have handed them to play on.

Look at what the position actually says once you stop counting. White, to move, has 10 legal moves. Black, if it were black's turn, would have 15. White has more room, fewer exposed discs and no commitment. That is what winning looks like at this stage, and it is why this engine weights raw disc count at exactly zero for the whole opening and midgame, and only starts caring about it in the last twenty squares.

The board as four numbers

A move generator that loops over 64 squares, and then loops outward in eight directions from each one, is easy to write and far too slow to search with. Real engines use a bitboard: the 64 squares stored as 64 bits, one bit per square, with a separate set of bits for black and for white.

Once the board is bits, whole-board questions become arithmetic. "Which squares are empty" is one bitwise operation. "Which of my discs sit next to an empty square" is a shift in each of eight directions and an AND. Finding every legal move for a player, all of them at once, takes a fixed handful of shifts and masks rather than a nested loop.

This engine splits each side into two 32-bit halves rather than using one 64-bit number, because JavaScript's fast integer operations work on 32 bits. A position is therefore four plain numbers, passed by value, and the search allocates no memory at all once it is running. That matters more than it sounds: garbage collection in the middle of a search is what makes a browser engine stutter.

Searching: negamax with alpha-beta

The search itself is negamax, which is minimax written the short way. Minimax says: I pick the move that maximises my score, assuming you then pick the move that minimises it. Negamax notices that your score is just my score with the sign flipped, so one function can handle both sides by negating the value it gets back from each child position.

On its own that means visiting every position in the tree, which explodes. A typical Othello midgame position has around ten legal moves, so looking eight moves ahead is on the order of a hundred million positions.

Alpha-beta pruning is the fix. While searching, the engine carries two numbers: the best score it has already guaranteed for itself (alpha) and the best score the opponent has already guaranteed (beta). If a branch is proved worse than something already in hand, the rest of that branch cannot change the final answer, so it is abandoned unexamined. The answer is identical to a full search; the work is not.

Move ordering, which is where the speed comes from

Alpha-beta only prunes well when good moves are tried first. Perfectly ordered, it examines roughly the square root of the tree. Badly ordered, it barely helps at all. So before searching a position's moves, this engine sorts them:

• Whatever the transposition table said was best here last time goes first.
• Then corners, because a corner can never be flipped and is almost always strong. Why corners matter.
• Then, when the branch is deep enough to be worth the cost, moves are ranked by how few replies they leave the opponent. Taking away the opponent's options is a better guide than any fixed table of square values.
• In shallow branches, where counting replies costs more than it saves, a fixed table of square values is used instead. Corners score 100, X-squares score minus 50.

Iterative deepening

The engine does not pick a depth and search it. It searches one move ahead, then two, then three, keeping the best answer from the last completed pass. When the clock runs out, there is always a finished answer in hand rather than a half-explored one.

This sounds wasteful and is not. Each pass fills the transposition table with good move suggestions, so the next pass is ordered far better and runs much faster than it would have alone. The shallow passes pay for themselves.

The transposition table

Positions repeat. Playing d3 then c4 reaches the same board as c4 then d3, and in a deep search the same position turns up thousands of times by different routes. A transposition table is a large cache that remembers what a position was worth and which move was best there.

This one holds 524,288 entries in flat typed arrays, allocated once and reused for the life of the page. Two details are worth calling out because they are easy to get wrong:

• The full position is stored, not only its hash. Two different boards can land in the same slot. If the engine trusted the slot without checking, it could report a proved endgame result that is simply false. Storing the four position words and comparing them makes a collision detectable.
• Entries carry a generation stamp. Each new search bumps a counter, and an entry is only believed if its stamp matches. That starts every search from a clean slate without clearing megabytes of memory, and it is what keeps the same position always producing the same move.

What the evaluation actually measures

When the search stops early, something has to put a number on the position. This engine combines six things, weighted by how far through the game it is.

The weights change three times during a game, on the count of empty squares. With more than 44 empty it uses opening weights, where mobility dominates. From 44 down to 21 empty it uses midgame weights, where stability starts to matter more. At 20 empty and below it uses endgame weights, where stability and parity dominate and, for the first time, disc count is given any weight at all.

The exact endgame solver

Everything above is guessing, carefully. The endgame is not.

Once few enough squares are empty, the engine stops evaluating and searches to the very end of the game. There is nothing to estimate: it returns the true final disc difference, so the move it plays is provably the best one. This is the same kind of search, on a much smaller scale, that was used to solve Othello outright in 2023.

Two economies make it affordable. First, proving who wins is much cheaper than proving by how much, so the engine proves the outcome first and only spends leftover time on the exact margin. Second, with seven or fewer squares left it drops the move generator and the sorting altogether and simply tries each remaining empty square in turn, best regions first. Nearly the whole search tree lives in those last few plies, and down there the bookkeeping costs more than it saves.

There is also a bound that saves a great deal of work. If your opponent already holds discs that can never be flipped, your best possible final margin is capped, and if that cap is no better than a result already in hand, the entire branch can be skipped. That reasoning only holds when more discs is the goal, so it is switched off in anti-Othello, where a large disc count is a liability.

Making a computer play badly on purpose

Building a strong engine is a solved problem. Building a beatable one is the harder design job, because search depth is a terrible dial. Two engines sharing an evaluation and separated by three plies are not "one slightly better": the deeper one wins almost every game, because in Othello a single bad move in sixty decides the result.

So the four levels here differ in how they choose as much as in how deep they look.

Beginner's mistakes are the ones new players actually make, which is the point. A level that plays randomly feels like a broken program; a level that misses corners feels like a person.

Notice that even the weakest levels play a solved ending straight. A proved finish is the one part of the game a deliberately weak setting can be trusted with, and it is the only way a lower level ever reports an exact result.

Where it runs

The search runs in a Web Worker, a separate thread from the page, so the board stays responsive while the computer thinks. If workers are unavailable it falls back to running inline. Either way nothing is sent anywhere: the whole engine is in your browser, and your game never leaves your device.

It is also deterministic. The same position, the same difficulty and the same seed always produce the same move, with the "random" numbers derived from the position itself. That is what makes the engine testable, and this one is tested with self-play matches between levels rather than with guesses about which is stronger.

How this compares to a serious engine

Honestly: it is much weaker, and deliberately so. It has a fixed budget of well under a second and has to run on a phone.

The strongest free Othello program is Edax, by Richard Delorme, which searches vastly deeper and uses an evaluation built from patterns learned over millions of positions rather than six hand-weighted terms. Before Edax, Logistello, by Michael Buro, beat world champion Takeshi Murakami 6-0 in 1997 and ended human superiority in Othello for good. A modified Edax is what proved the whole game a draw in 2023.

The structure, though, is the same in all three: bitboards, negamax with alpha-beta, good move ordering, a transposition table, iterative deepening and an exact endgame solver. What separates them is the quality of the evaluation and the number of positions per second.