AI opponent

Three strategies behind a single function. The AI layer imports the engine and nothing else, and receives all randomness through an injected generator so its behaviour is reproducible in tests.

Types (src/ai/types.ts)

export type Difficulty = 'easy' | 'medium' | 'hard';

/** Returns a float in [0, 1). Injected so tests can seed it. */
export type Rng = () => number;

/** Picks a cell index for state.currentPlayer. Must return a legal move. */
export type MoveChooser = (state: GameState, rng: Rng) => number;

Every strategy is a MoveChooser. If a strategy is ever called on a finished game it throws — that is a caller bug, not something to paper over.

Easy (src/ai/random.ts)

Pick uniformly at random from availableMoves(state): moves[Math.floor(rng() * moves.length)]. Guard the upper edge so an rng() returning a value extremely close to 1 cannot index out of bounds.

Easy must be genuinely beatable. Do not add "but block an obvious loss" logic here — that is Medium.

Medium (src/ai/heuristic.ts)

A one-ply greedy player, evaluated in this fixed order:

1. Win now — if any legal move produces status === 'win' for the current player, play it.
2. Block — if any legal move would produce a win for the opponent were they to play it, occupy that cell.
3. Random — otherwise pick uniformly from the remaining legal moves.

Both lookups are done by calling applyMove on a trial state, never by pattern-matching the board. When several moves tie inside a step, choose randomly among them via rng so Medium does not feel robotic.

Medium is deliberately imperfect: it does not see forks, so a competent human beats it with the classic corner-corner opening. That is the intended experience.

Hard (src/ai/minimax.ts)

Full-depth minimax with alpha-beta pruning.

export function minimaxMove(state: GameState, rng: Rng): number;

Scoring, from the perspective of the player to move at the root:

Outcome	Score
Root player wins	10 - depth
Root player loses	depth - 10
Draw	0

depth is the number of plies from the root. Subtracting depth makes the AI prefer the fastest win and the slowest loss, which is what makes it feel sharp rather than merely correct.

Implementation requirements:

• Recursive search(state, depth, alpha, beta, maximizing) returning a number; the root collects scores per legal move.
• Alpha-beta cut-offs on both the maximising and minimising branches.
• The root gathers all moves sharing the best score and picks among them with rng. This keeps play optimal while varying the games — a fixed tie-break makes the AI repeat identical games and players notice immediately.
• Optional memoisation keyed by a board string plus side to move. With alpha-beta the worst case is already a few thousand nodes, so add a cache only if a benchmark shows it is needed.
• An empty board must still be answered within the performance budget below; a hard-coded opening book is not permitted, because the point of the exercise is the search.

Dispatch (src/ai/choose-move.ts)

export function chooseMove(state: GameState, difficulty: Difficulty, rng: Rng = Math.random): number;

Maps difficulty to strategy with an exhaustive switch whose default branch is a never-typed assertion, so adding a difficulty later fails to compile until it is handled.

Test requirements (src/ai/ai.test.ts)

Use a seeded RNG (a small deterministic LCG defined in the test file) so every assertion is reproducible.

• Each strategy returns a member of availableMoves(state) for a large sample of random positions.
• Each strategy throws when called on a finished game.
• Medium takes an immediate win when one exists, for all eight lines.
• Medium blocks an immediate opponent win when it has no win of its own.
• Medium prefers its own win over blocking when both are available.
• Hard never loses (X seat): exhaustively play every legal opponent reply sequence against the Hard AI moving first, and assert the result is always a win or a draw for the AI.
• Hard never loses (O seat): same, with the AI moving second.
• Hard versus Hard always draws, over at least 100 seeded games.
• Hard takes an immediate win in one when available, rather than a slower forced win.
• Hard blocks a fork: from X at 0 and 8 with O at 4, the AI as O plays an edge, never a corner.
• Hard's first move from an empty board completes within 100 ms on the CI machine.

For the exhaustive tests, enumerate opponent moves recursively rather than sampling. The full tree under an optimal player is small enough to finish in seconds.

Acceptance criteria

• src/ai/ imports only from src/engine/; it touches no DOM API and calls Math.random in no place other than the default parameter of chooseMove.
• All three strategies satisfy the MoveChooser type and always return a legal move.
• Easy is uniformly random over legal moves, verified by a chi-square-style distribution check over 10 000 seeded draws on an empty board.
• Medium wins when it can, blocks when it must, and prefers winning to blocking.
• The exhaustive never-lose test passes for the Hard AI in both the first and second seat.
• Hard versus Hard draws in 100 out of 100 seeded games.
• Hard chooses randomly among equally optimal moves, verified by observing more than one distinct first move across seeds.
• Alpha-beta pruning is present and the empty-board decision completes in under 100 ms.
• chooseMove handles every Difficulty through an exhaustive switch with a never default.
• Statement coverage of src/ai/ is at least 90%.
• npm run verify passes.