09.1 - Game AI: Minimax and Alpha-Beta

Recap

In 03.2 - Game Engine Design we split the game into configuration, state and rules: GameBrain validates moves, applies them and detects wins and draws, and it knows nothing about who is asking. In 08.2 - Classical Code Patterns we put the persistence behind interfaces and let DI pick the implementation. The AI opponent slots into that same design: one more interface, one more implementation, no changes to the rules.

By the end of this lecture you should be able to:

• Explain what a game tree is, why we cannot build the whole tree for most games, and what MAX and MIN nodes mean.
• Write minimax (and its negamax twin) in C# on top of your existing GameBrain.
• Add alpha-beta pruning and explain why it returns exactly the same move as plain minimax.
• Cut the search off at a depth and hand the leaf to an evaluation function.
• Write deterministic xUnit tests that prove the AI takes wins, blocks losses and never cheats.

Demo code

Lecture demos: csharp-2026-fall

Level 0: a random opponent

The first option for an AI opponent is to just play random legal moves. Hey, at least it does something. Quick thinking shows that this has a lot of room for improvement - not all moves are equal. In a game of checkers, maybe a move that removes the opponent's piece(s) from the board should be ranked higher? Or a move that makes your piece a king. So we need some kind of function that lets us evaluate the different game states that result from a move and assign a numerical value to each. Typically this is called a heuristic function, and its values are often scaled to the range -1 to 1: -1 might be "player A wins", 1 is "player B wins".

And if we are able to try out all the possible moves one after another, then we only need the values -1 and 1 (and 0 for a draw). We can draw a path through the moves that leads us to victory, if such a path exists. Unfortunately this is not possible in most games.

Before any of that, let's make the random opponent real, because it fixes the shape everything else will use. Both a human at the console and the AI produce a move for a state, so they share one interface:

// GameEngine/IMoveProvider.cs
public interface IMoveProvider
{
    (int Row, int Col) GetMove(GameState state);
}

// Marker interface: lets the menu and DI list AI providers separately from human input.
public interface IGameAi : IMoveProvider;

// GameEngine/Ai/RandomAiMoveProvider.cs
public class RandomAiMoveProvider(GameBrain brain, Random? random = null) : IGameAi
{
    private readonly Random _random = random ?? new Random();
    public (int Row, int Col) GetMove(GameState state)
    {
        var moves = brain.GetLegalMoves(state);
        if (moves.Count == 0) throw new InvalidOperationException("No legal moves - the game should be over.");
        return moves[_random.Next(moves.Count)];
    }
}

The optional Random parameter is not decoration: a seeded Random is what makes the AI tests deterministic later. The game loop does not care which provider it holds - it picks playerX or playerO by state.NextMoveBy, calls GetMove, hands the result to brain.MakeMove and redraws. Hot-seat, human vs AI and AI vs AI are the same loop with different providers (a ConsoleHumanMoveProvider reads the keyboard behind the same interface); lecture 10.1 shows the AI-vs-AI version. Everything below is about replacing RandomAiMoveProvider with something that thinks.

Legal moves

The whole search rests on one method you already have from A2: GameBrain.GetLegalMoves. For the generic N-in-a-row engine it is a scan for empty cells; for Connect Four gravity means only the lowest empty cell of each column is legal, so the list has at most one entry per column. The AI never needs to know which - it just iterates the list.

// GameEngine/GameBrain.cs
public List<(int Row, int Col)> GetLegalMoves(GameState state)
{
    var moves = new List<(int Row, int Col)>();
    for (var row = 0; row < state.Config.BoardHeight; row++)
    for (var col = 0; col < state.Config.BoardWidth; col++)
        if (state.Board[row][col] == EGamePiece.Empty) moves.Add((row, col));
    return moves;
}

Nine Men's Morris (select, destination, capture) and the Tic-Tac-Two grid move do not fit (int Row, int Col). Make your move a small record with all the parts and let GetLegalMoves return the complete, already-validated list of those records. The search algorithms below do not change - only the type of the thing they iterate.

Perfect information, zero sum

All five course games share two properties that make minimax applicable:

• Perfect information - both players see the whole board. Nothing is hidden, nothing is random.
• Zero sum - whatever is good for me is exactly as bad for you. One number describes the position for both players.

The number that matters most when planning the search is the branching factor b (legal moves per position) and the depth d (plies to the end of the game). The tree has roughly b^d leaves.

Game (preset)	Typical b	Game length (plies)	Whole tree feasible?
Tic-Tac-Two, Plain 3×3 (= tic-tac-toe)	9 → 1	≤ 9	Yes, 9! = 362 880 leaves at most
Tic-Tac-Two, Classic 5×5	25 → ~10, grows after unlock (grid + piece moves)	open-ended	No
Connect Four, Classic 7×6	≤ 7	≤ 42	No, ~4.5 × 10^12 positions
Reversi / Othello 8×8	~10	≤ 60	No
Gomoku 15×15	~200 (20-40 with candidate pruning)	≤ 225	No
Nine Men's Morris	~24 placing, 5-30 moving	open-ended	No

Tic-tac-toe has 9 possible moves in the first ply, then the opponent has 8, and so on. So we end up with 9! or fewer combinations - just 362 880 terminal board positions. Easy to calculate to the end. There are even books printed with them (Tic-Tac-Tome):

For chess it is over 10^40 nodes. We cannot construct that game tree in reality - we would run out of memory and time. Your game sits between those two extremes, which is exactly why the rest of this lecture exists.

Game tree

A (partial) tree of tic-tac-toe:

One player tries to reach a +1 end state (MAX) and the opponent a -1 end state (MIN).

In a normal search problem, the optimal solution would be a sequence of actions leading to a goal state - a terminal state that is a win. In adversarial search, MIN has something to say about it. MAX therefore must find a contingent strategy, which specifies MAX's move in the initial state, then MAX's moves in the states resulting from every possible response by MIN, then MAX's moves in the states resulting from every possible response by MIN to those moves, and so on.

An optimal strategy leads to outcomes at least as good as any other strategy when one is playing an infallible opponent.

Minimax

A two-move tree (triangles pointing up are MAX nodes, pointing down are MIN nodes).

Given a game tree, the optimal strategy can be determined from the minimax value of each node, MINIMAX(n). The minimax value of a node is the utility (for MAX) of being in the corresponding state, assuming that both players play optimally from there to the end of the game. Obviously, the minimax value of a terminal state is just its utility function. Furthermore, given a choice, MAX prefers to move to a state of maximum value, whereas MIN prefers a state of minimum value.

This definition of optimal play for MAX assumes that MIN also plays optimally - it maximises the worst-case outcome for MAX.

Terminal test and utility

The textbook's TERMINAL-TEST and UTILITY are methods you wrote weeks ago. Reuse them; do not write a second win detector inside the AI. The utility is from the AI's point of view and uses a large constant so that no heuristic (lecture 10.1) can ever outweigh a real win. Adding the remaining depth makes a win in 2 plies score higher than a win in 6 - otherwise the AI sees "I win eventually" everywhere and dawdles.

// GameEngine/Ai/MinimaxMoveProvider.cs (part 1)
public class MinimaxMoveProvider(GameBrain brain, int maxDepth, Random? random = null) : IGameAi
{
    public const int WinScore = 1_000_000;

    private readonly Random _random = random ?? new Random();
    private EGamePiece _aiPiece = EGamePiece.Empty;

    public int NodesVisited { get; private set; }

    private static EGamePiece Opponent(EGamePiece piece)
        => piece == EGamePiece.X ? EGamePiece.O : EGamePiece.X;

    // null = not terminal, keep searching
    private int? TerminalScore(GameState s, int depth)
    {
        if (brain.CheckWin(s, _aiPiece)) return WinScore + depth;
        if (brain.CheckWin(s, Opponent(_aiPiece))) return -WinScore - depth;
        if (brain.IsDraw(s)) return 0;
        return null;
    }

    // Filled in lecture 50. With 0 the AI only sees wins and losses inside its horizon.
    protected virtual int Evaluate(GameState s) => 0;

Apply / undo versus clone

Minimax needs to "try a move and look". Two ways to do that:

• Clone the state, apply the move to the copy, recurse, throw the copy away. Simple, impossible to get wrong, allocates one board per node.
• Apply and undo on a single state: make the move, recurse, take it back. No allocations, but every rule that changes the board (flips in Reversi, captures in Nine Men's Morris) needs a matching undo.

Start with cloning. It is correct on day one, and lecture 10.1 shows when and how to switch. The clone must be deep for the jagged board - copying the outer array only would give both states the same rows, and the search would silently corrupt the real game.

// GameEngine/GameState.cs
public class GameState
{
    // Id, Board, NextMoveBy, Config, Moves, CreatedAtUtc as defined in lecture 03.2

    public GameState Clone()
    {
        var board = new EGamePiece[Board.Length][];
        for (var row = 0; row < Board.Length; row++)
        {
            board[row] = (EGamePiece[])Board[row].Clone(); // enum row: a shallow row copy is a deep copy
        }

        return new GameState
        {
            Id = Id,
            Board = board,
            NextMoveBy = NextMoveBy,
            Config = Config,          // immutable record, safe to share
            Moves = [.. Moves],
            CreatedAtUtc = CreatedAtUtc,
        };
    }
}

Copying Moves keeps the search and the save file in agreement on history, but for long games it is the most expensive line in the method - lecture 10.1 shows a lighter search state when profiling says so.

Minimax in C#

depth is the number of plies still allowed. The textbook counts up and compares with a maximum; counting down is the same thing with one fewer parameter.

    // MinimaxMoveProvider (part 2)
    public int Minimax(GameState s, int depth, bool maximizing)
    {
        NodesVisited++;
        if (TerminalScore(s, depth) is { } terminal) return terminal;
        if (depth == 0) return Evaluate(s);

        var best = maximizing ? int.MinValue : int.MaxValue;
        foreach (var (row, col) in brain.GetLegalMoves(s))
        {
            var child = s.Clone();
            brain.MakeMove(child, row, col);
            var score = Minimax(child, depth - 1, !maximizing);
            best = maximizing ? Math.Max(best, score) : Math.Min(best, score);
        }
        return best;
    }

Read it against the algorithm image above: the terminal test, the "for each action" loop, MAX taking the maximum, MIN taking the minimum. maximizing is true when it is the AI's turn in state s, because the utility is from the AI's point of view.

Negamax: the same thing with one branch fewer

Because the game is zero sum, "MIN minimises my score" equals "MIN maximises its own score, which is the negative of mine". So every node can maximise, provided we negate the value coming back from the child. colour is +1 when the AI is to move and -1 otherwise.

    private const int Infinity = 10_000_000;   // never negate int.MinValue

    public int Negamax(GameState s, int depth, int colour)
    {
        NodesVisited++;
        if (TerminalScore(s, depth) is { } terminal) return colour * terminal;
        if (depth == 0) return colour * Evaluate(s);

        var best = -Infinity;
        foreach (var (row, col) in brain.GetLegalMoves(s))
        {
            var child = s.Clone();
            brain.MakeMove(child, row, col);
            best = Math.Max(best, -Negamax(child, depth - 1, -colour));
        }
        return best;
    }

Both forms visit the same nodes and return the same root move. Pick one and stick to it; mixing them is the classic sign-error bug.

Alpha-Beta pruning

Minimax visits every node in the tree down to the depth limit. Most of them cannot change the answer. Alpha-beta pruning notices that and skips them.

• (a) The first leaf below B has the value 3. Hence B, which is a MIN node, has a value of at most 3.
• (b) The second leaf below B has a value of 12; MIN would avoid this move, so the value of B is still at most 3.
• (c) The third leaf below B has a value of 8; we have seen all of B's successor states, so the value of B is exactly 3. Now we can infer that the value of the root is at least 3, because MAX has a choice worth 3 at the root.
• (d) The first leaf below C has the value 2. Hence C, which is a MIN node, has a value of at most 2. But we know that B is worth 3, so MAX would never choose C. Therefore there is no point in looking at the other successor states of C. This is an example of alpha-beta pruning.
• (e) The first leaf below D has the value 14, so D is worth at most 14. This is still higher than MAX's best alternative (i.e. 3), so we need to keep exploring D's successor states. Notice also that we now have bounds on all of the successors of the root, so the root's value is also at most 14.
• (f) The second successor of D is worth 5, so again we need to keep exploring. The third successor is worth 2, so now D is worth exactly 2. MAX's decision at the root is to move to B, giving a value of 3.

The same tree, with the pruned subtree dashed:

Alpha-Beta pruning algorithm

α = the value of the best (i.e. highest-value) choice we have found so far at any choice point along the path for MAX. β = the value of the best (i.e. lowest-value) choice we have found so far at any choice point along the path for MIN.

The window [alpha, beta] is "the range of values the players above us still care about". As soon as a node finds a value outside that window, the rest of its children are irrelevant.

    // MinimaxMoveProvider (part 3)
    public int AlphaBeta(GameState s, int depth, int alpha, int beta, bool maximizing)
    {
        NodesVisited++;
        if (TerminalScore(s, depth) is { } terminal) return terminal;
        if (depth == 0) return Evaluate(s);

        if (maximizing)
        {
            var best = int.MinValue;
            foreach (var (row, col) in brain.GetLegalMoves(s))
            {
                var child = s.Clone();
                brain.MakeMove(child, row, col);
                best = Math.Max(best, AlphaBeta(child, depth - 1, alpha, beta, false));
                alpha = Math.Max(alpha, best);
                if (beta <= alpha) break;   // MIN above us already has something ≤ alpha: prune
            }
            return best;
        }
        else
        {
            var best = int.MaxValue;
            foreach (var (row, col) in brain.GetLegalMoves(s))
            {
                var child = s.Clone();
                brain.MakeMove(child, row, col);
                best = Math.Min(best, AlphaBeta(child, depth - 1, alpha, beta, true));
                beta = Math.Min(beta, best);
                if (beta <= alpha) break;   // MAX above us already has something ≥ beta: prune
            }
            return best;
        }
    }

Compared with Minimax the only additions are the two window parameters, one line updating the window, and one break. Alpha-beta never changes the value at the root - it is the same search with the provably useless parts skipped. If your alpha-beta AI plays differently from your minimax AI at the same depth (ties aside), one of them is wrong.

Choosing the root move

The recursive functions return a value; the interface wants a move. The root is a MAX node that also remembers which child produced the best value. Ties are broken with the seeded Random, so the AI does not always open in the top-left corner and the tests stay reproducible. Keep the full window at the root: passing bestScore as alpha prunes a little more, but then equal-valued moves come back as bounds and the tie list is wrong.

    // MinimaxMoveProvider (part 4)
    public (int Row, int Col) GetMove(GameState state)
    {
        _aiPiece = state.NextMoveBy;
        NodesVisited = 0;
        var moves = brain.GetLegalMoves(state);
        if (moves.Count == 0) throw new InvalidOperationException("No legal moves - the game should be over.");

        var bestScore = int.MinValue;
        List<(int Row, int Col)> bestMoves = [];
        foreach (var (row, col) in moves)
        {
            var child = state.Clone();
            brain.MakeMove(child, row, col);
            var score = AlphaBeta(child, maxDepth - 1, int.MinValue, int.MaxValue, maximizing: false);

            if (score > bestScore) { bestScore = score; bestMoves = [(row, col)]; }
            else if (score == bestScore) bestMoves.Add((row, col));
        }
        return bestMoves[_random.Next(bestMoves.Count)];
    }
}

Cutting off search

Apply a cut-off at a certain depth (and evaluate the board state). Instead of terminal-test and utility function:

if CUTOFF-TEST(state, depth) then return HEURISTIC(state)

Decrement (or increment and compare) the depth on every recursive call, but check the terminal states first - a won position at the depth limit is still a won position. In the code above that is the order of the two if lines at the top of AlphaBeta.

With Evaluate returning 0, the AI at depth 4 plays perfectly whenever a forced win or loss is within 4 plies and otherwise picks a random move among the "equal" ones. That already blocks and takes immediate wins, which is what the tests below check. Making the non-terminal leaves meaningful - counting open lines, corners, mills - is the job of 10.1 - Heuristics & Difficulty.

Complexity

• Minimax visits O(b^d) nodes. Connect Four at depth 8: 7^8 ≈ 5.7 million clones - a second or two.
• Alpha-beta with perfect move ordering visits O(b^(d/2)): the same 8 plies cost about 7^4 ≈ 2400 nodes. With random ordering expect roughly O(b^(3d/4)).
• The practical reading: good move ordering doubles the depth you can afford in the same time. Lecture 10.1 covers ordering, iterative deepening and time budgets. Memory is only O(b·d) - the tree is never stored, just the current path.

Print NodesVisited after every AI move while you develop. It is the single most useful number for seeing whether pruning actually works.

Testing the AI

AI tests are mandatory in A5 and they are cheap: build a small position, ask for a move, assert. Use the smallest preset that has the property you test - the Plain 3×3 Tic-Tac-Two, Connect3 5×4 or Mini 6×6 Reversi - and keep the depth low so the whole suite runs in well under a second.

// Tests/Ai/MinimaxMoveProviderTests.cs
public class MinimaxMoveProviderTests
{
    private readonly GameBrain _brain = new();

    // "X", "O" and "." per cell; X to move
    private static GameState Position(params string[] rows)
    {
        var config = new GameConfiguration("Test 3x3", rows[0].Length, rows.Length, 3);
        var board = rows
            .Select(r => r.Select(ch => ch switch { 'X' => EGamePiece.X, 'O' => EGamePiece.O, _ => EGamePiece.Empty }).ToArray())
            .ToArray();
        return new GameState { Config = config, Board = board, NextMoveBy = EGamePiece.X };
    }

    [Fact]
    public void TakesTheImmediateWin()
    {
        var state = Position(
            "XX.",
            "OO.",
            "...");
        var ai = new MinimaxMoveProvider(_brain, maxDepth: 2, new Random(1));
        Assert.Equal((0, 2), ai.GetMove(state));
    }

    [Fact]
    public void BlocksTheImmediateLoss()
    {
        var state = Position(
            "OO.",
            "X..",
            "..X");
        var ai = new MinimaxMoveProvider(_brain, maxDepth: 2, new Random(1));
        Assert.Equal((0, 2), ai.GetMove(state));
    }

    [Theory]
    [InlineData(1)]
    [InlineData(4)]
    public void ReturnsOnlyLegalMoves(int depth)
    {
        var state = Position("XO.", ".X.", "O..");
        var ai = new MinimaxMoveProvider(_brain, depth, new Random(7));
        Assert.Contains(ai.GetMove(state), _brain.GetLegalMoves(state));
    }

    [Fact]
    public void SameSeedGivesSameMove()
    {
        var first = new MinimaxMoveProvider(_brain, maxDepth: 2, new Random(42)).GetMove(Position("...", "...", "..."));
        var second = new MinimaxMoveProvider(_brain, maxDepth: 2, new Random(42)).GetMove(Position("...", "...", "..."));
        Assert.Equal(first, second);
    }
}

The first two are the tests the TA will look for. The third proves the AI never returns an occupied cell or a full column no matter the depth. The fourth is why Random is injected: without a seed, a tie on an empty board is a coin flip and the test would sometimes fail. A fifth worth adding once you have both: Minimax and AlphaBeta must return the same value for the same position and depth - it catches the sign errors and off-by-one window bugs that pruning tends to introduce. None of this touches ConsoleUI: MinimaxMoveProvider lives in GameEngine (or a sibling GameAi library), takes a GameBrain and a GameState and returns a tuple - the same contract the WebApp will call in A6.

Timing assertions

"Answers within 5 seconds at the highest level" is an A5 requirement, but a Stopwatch assertion in the unit tests will be flaky on a loaded laptop or CI runner. Measure it, write the numbers into the README, and if you keep a timing test give it a generous bound and mark it with a trait so it can be skipped.

Self preparation QA

1. Why does minimax need both a MAX and a MIN level? — Because the opponent chooses too: MAX must plan for the opponent's best reply, not for the reply MAX would like.
2. What are the terminal test and the utility function in your project? — GameBrain.CheckWin / IsDraw and a large constant (plus remaining depth) from the AI's point of view.
3. What is the difference between minimax and negamax? — Negamax uses the zero-sum property to always maximise, negating the child's value; the moves chosen are identical.
4. What do alpha and beta mean? — Alpha is the best value MAX is already guaranteed on the current path, beta the best value MIN is guaranteed; a child whose value falls outside the window cannot change the result.
5. Can alpha-beta return a different move than minimax at the same depth? — No (apart from tie-breaking); it visits fewer nodes but computes exactly the same values.
6. Why must GameState.Clone() copy each row of the jagged array? — Copying only the outer array shares the row arrays, so the search would mutate the real game's board.
7. Why inject Random into the AI? — So ties are broken reproducibly and the tests are deterministic.
8. Why must the terminal test run before the depth cut-off? — A won position at the depth limit must return the win score, not the heuristic.