Reversi from scratch: one bracket scan, then a greedy vs minimax AI

Day 30 of my "build a small game a day, from nothing" run. Reversi (you might know it as Othello) looks like a board game about counting discs, but the entire rulebook is a single geometric idea — bracketing — and the fun is watching a naive AI lose to a smarter one that understands corners. About 130 lines of vanilla JS.

Play it (LOOK / UNDERSTAND / BUILD tabs) here: https://dev48v.infy.uk/game/day30-reversi.html

The whole game is one rule

The board is an 8×8 array of 0 (empty), 1 (you, dark) and 2 (the AI, light), starting with four discs in a diagonal cross. Dark moves first. On your turn you drop a disc on an empty square, but only if it brackets at least one straight line of the opponent's discs between the disc you just placed and another disc of your own already on the board. Every bracketed disc flips to your colour.

That's it. Legality and captures are the same computation, so I only wrote it once. To test one of the eight directions, step to the neighbour and walk over an unbroken run of opponent discs; the run counts only if it closes on one of your own discs:

function bracketDir(b, r, c, dr, dc, player){
  const opp = player === 1 ? 2 : 1;
  const line = [];
  let nr = r+dr, nc = c+dc;
  while (inB(nr,nc) && b[nr][nc] === opp){   // run of opponent discs
    line.push([nr,nc]); nr += dr; nc += dc;
  }
  // captures only if the run is non-empty AND closed by our disc
  if (line.length && inB(nr,nc) && b[nr][nc] === player) return line;
  return [];
}

The rule most people forget: one placement can bracket in several directions at once, and it flips the trapped discs in every one of them — not just the longest line. So I scan all eight rays from the square and concatenate every bracketed run into a single list. If that list is empty the move is illegal; otherwise it is exactly the set of discs that flip.

const DIRS = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];
function flipsFor(b, r, c, player){
  if (b[r][c] !== 0) return [];
  let flips = [];
  for (const [dr,dc] of DIRS)
    flips = flips.concat(bracketDir(b, r, c, dr, dc, player));
  return flips;                    // legal move  <=>  flips.length > 0
}

Sweep the board with flipsFor and you have every legal move for a side. Passing falls out naturally: if you have no legal move but your opponent does, your turn is skipped; when neither side can move the game ends and the higher disc count wins.

Greedy is a trap

The obvious AI plays whichever move flips the most discs. It is terrible. Early on the disc count barely matters and swings wildly, and grabbing a big flip usually shoves your discs to the frontier where they get re-flipped — and worse, it tends to open the squares next to a corner and hand the corner away. A corner disc can never be flipped (there is no square beyond it to close a bracket), so it is permanent and it anchors whole edges. Losing one is often losing the game.

So instead of counting discs I score positions with a weight matrix: corners are worth a fortune, the X- and C-squares beside them are poison, edges beat the bland centre.

const W = [
  [120,-20, 20,  5,  5, 20,-20,120],
  [-20,-40, -5, -5, -5, -5,-40,-20],
  [ 20, -5, 15,  3,  3, 15, -5, 20],
  [  5, -5,  3,  3,  3,  3, -5,  5],
  [  5, -5,  3,  3,  3,  3, -5,  5],
  [ 20, -5, 15,  3,  3, 15, -5, 20],
  [-20,-40, -5, -5, -5, -5,-40,-20],
  [120,-20, 20,  5,  5, 20,-20,120],
];

Looking ahead: minimax + alpha-beta

A one-move score is short-sighted, so the AI searches the game tree. Minimax assumes both sides play their best: the AI picks the move that maximises the score, expecting you to reply with the move that minimises it, alternating down to a fixed depth. Alpha-beta pruning tracks the best each side is already guaranteed and abandons a branch the instant it cannot change the decision — often a huge saving with no effect on the answer.

function minimax(b, depth, alpha, beta, toMove){
  const moves = legalMoves(b, toMove);
  if (!moves.length){                              // no move -> must pass
    if (!legalMoves(b, opponent(toMove)).length){  // both stuck: endgame
      const c = counts(b), d = c.ai - c.you;
      return d>0 ? 1e5+d : d<0 ? -1e5+d : 0;       // score by disc count
    }
    return minimax(b, depth, alpha, beta, opponent(toMove));  // pass
  }
  if (depth === 0) return evaluate(b);
  let best = toMove === AI ? -Infinity : Infinity;
  for (const m of moves){
    const v = minimax(applyMove(b,m,toMove), depth-1, alpha, beta, opponent(toMove));
    if (toMove === AI){ best = Math.max(best,v); alpha = Math.max(alpha,best); }
    else              { best = Math.min(best,v); beta  = Math.min(beta ,best); }
    if (beta <= alpha) break;                      // prune
  }
  return best;
}

Two details make it actually play well. Passes recurse with the same depth on the other side, so the search never miscounts a skipped turn. And a position where nobody can move is scored by the real disc difference (a big number), so the AI fights to win the endgame rather than just look pretty on the weight map. The evaluation also adds a mobility term — rewarding having more legal moves than the opponent — because keeping your opponent short of moves is half of good Reversi.

The takeaway

Depth trades strength for time: each extra ply multiplies the positions by the branching factor, which is exactly why alpha-beta earns its keep. I checked the engine against known positions — the opening board offers dark exactly four legal moves, a placement that brackets in two directions flips both lines at once, and minimax reliably grabs a corner whenever one is on offer.

Vanilla JS, no libraries, runs offline — flip Greedy to Minimax mid-game and watch the corners decide it. Tomorrow: Checkers — jump to capture, king your men on the back rank, and another minimax AI.