↑↓ move · ↵ open · esc close

← All projects/Algorithms and games

Othello

Outflank and flip your opponent’s discs, against an AI you can switch between minimax, alpha-beta, Monte Carlo tree search and simpler players. Written first in Python, rebuilt for this page in TypeScript.

StatusShipped
Original versionPython
On this siteTypeScriptCanvasMinimaxAlpha-betaMonte Carlo
Live demo

The first version of this game and its AI was written in Python. Python does not run in a browser, so the board you can play here is a TypeScript rewrite of the same ideas. Pick any of the five opponents below.

Rules
  1. 01The board is 8 by 8. Black starts with two discs each in the centre, and black always moves first.
  2. 02On your turn you place one disc on an empty square so that it traps at least one straight line of enemy discs (across, down or diagonally) between the new disc and another of yours.
  3. 03Every trapped disc flips to your colour. A move that flips nothing is not allowed.
  4. 04If you have no legal move you pass. When neither player can move, usually because the board is full, the player with more discs wins.
  5. 05Corners can never be flipped, which is why the squares next to them are dangerous to take early.
Algorithms
  • 01
    Minimax →O(b^d)

    Searches every legal move to a fixed depth, assuming each side picks what is best for itself, and backs the scores up the tree.

    Steps
    1. Generate every legal move and play it.
    2. Repeat from the new position for the other side, until the depth is reached or the game ends.
    3. Score the leaves with the evaluation, then on the way back up take the highest score on the AI’s turns and the lowest on yours.
    4. Play the move whose branch scored highest.
  • 02
    Alpha-beta pruning →O(b^(d/2)) best case

    Minimax that stops exploring a branch as soon as it is proven worse than one already found. It returns the same move, usually after far fewer positions.

    Steps
    1. Carry two bounds down the tree: alpha, the best the AI can already force, and beta, the best you can already force.
    2. If a branch’s score crosses the other side’s bound, nobody would ever steer the game there, so skip its remaining moves.
    3. Try the best-looking moves first (corners before edges) so that bounds tighten early and more branches are skipped.
  • 03
    Monte Carlo tree search →O(iterations × game length)

    Needs no evaluation function. It plays many random games from each candidate move and keeps statistics on which ones win.

    Steps
    1. Selection: walk down the tree choosing the child with the best balance of win rate and how rarely it has been tried (UCT).
    2. Expansion: add one new move to the tree.
    3. Simulation: finish the game with random moves.
    4. Back-propagation: add the result to every position on the path. Repeat thousands of times, then play the most visited move.
  • 04
    Greedy and random baselinesO(b)

    Greedy plays the move that looks best one step ahead; random plays anything legal. They show how much the deeper searches actually add.

Algorithm pages
Minimax →Alpha-beta pruning →Monte Carlo tree search →Greedy and random baselines →

Each of these has a page of its own, with the steps, the cost and the other places it is used.

How it works
  • 01The AI treats the game as a tree: every legal move leads to a position, and from each of those the other side has its own moves. The opponent menu changes how much of that tree it looks at, and how it judges what it finds.
  • 02Othello is rarely won by counting discs early on. The evaluation therefore rewards what lasts: corners and edges, plus mobility, the number of moves you have compared to the number your opponent has. The disc count only matters near the end.
  • 03Press “Compare the algorithms here” in the middle of a game to run the four searching players on the same position and see which move each one picks and how many positions it needed.
More in this category
Algorithms and games

Pathfinding

Five grid search algorithms side by side on walls you draw. The search […]

TypeScriptA*+1
Algorithms and games

Tic-tac-toe

A tic-tac-toe opponent that cannot be beaten, built on minimax with […]

TypeScriptMinimax+1
Algorithms and games

HEX

The connection game with no draws, against an AI whose search […]

TypeScriptCanvas+1