10.1 - Game AI: Heuristics, Difficulty, Performance

Recap

09.1 - Minimax gave us MinimaxMoveProvider with alpha-beta pruning and a depth cut-off that hands every non-terminal leaf to Evaluate(s) - which still returns 0. This lecture fills that method in for each course game, turns one AI into three difficulty levels, and makes it fast enough to answer within its time budget without freezing the console.

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

• Write an evaluation function for your game that is cheap, symmetric and always dominated by the win score.
• Explain the heuristics that matter for Connect Four, Tic-Tac-Two, Reversi, Gomoku and Nine Men's Morris.
• Build at least three difficulty levels from depth, random-move mixing, evaluation noise and a time budget.
• Use move ordering and iterative deepening to search deeper in the same time, and measure it in nodes per second.
• Run the AI off the UI thread with Task.Run and a CancellationToken, including an AI-vs-AI loop.

Demo code

Lecture demos: csharp-2026-fall

What makes a good evaluation function

Evaluate(s) is a guess of the minimax value of a position we are not going to search further. Four rules:

1. Same scale and sign as the utility. Positive is good for the AI, negative for the opponent, and Math.Abs(Evaluate(s)) must stay well below WinScore. A heuristic that can reach 1 000 000 will make the AI prefer "a nice position" over "a win".
2. Symmetric. Evaluating the same board for X and for O must give opposite numbers. The easiest way to guarantee that: compute mine - theirs for every feature.
3. Cheap. It runs at every leaf - millions of times. No LINQ, no string building, no allocation if you can help it.
4. Honest about what it does not know. A leaf with a threat the heuristic cannot see is the horizon effect. Deeper search fixes it; a cleverer heuristic only hides it.

Give the heuristic its own interface so the provider does not depend on the game:

// GameEngine/Ai/IEvaluator.cs
public interface IEvaluator
{
    // Score of the position for `me`, in (-MinimaxMoveProvider.WinScore, +WinScore)
    int Evaluate(GameState s, EGamePiece me);
}

N-in-a-row games: windows

Connect Four, Gomoku and the Plain 3×3 Tic-Tac-Two all use the same generic engine, and they share one heuristic: look at every window of WinLength consecutive cells (horizontal, vertical, both diagonals) and score it by how many of my pieces it holds - provided the opponent has none in it. A window with pieces of both colours can never become a line, so it is worth zero. Pieces in the middle columns take part in more windows, so they get a small bonus on top.

// GameEngine/Ai/NInARowEvaluator.cs
public class NInARowEvaluator : IEvaluator
{
    // indexed by number of own pieces in an otherwise empty window; tuned by hand
    private static readonly int[] WindowWeights = [0, 1, 10, 100, 1_000, 10_000, 100_000];
    private const int CentreBonus = 3;

    public int Evaluate(GameState s, EGamePiece me)
    {
        var board = s.Board;
        var (w, h, n) = (s.Config.BoardWidth, s.Config.BoardHeight, s.Config.WinLength);
        var wrap = s.Config.IsCylinder;
        var opp = me == EGamePiece.X ? EGamePiece.O : EGamePiece.X;
        var score = 0;

        for (var row = 0; row < h; row++)
        for (var col = 0; col < w; col++)
        for (var d = 0; d < 4; d++)
        {
            var (dr, dc) = d switch { 0 => (0, 1), 1 => (1, 0), 2 => (1, 1), _ => (1, -1) };
            var mine = 0;
            var theirs = 0;
            var inside = true;
            for (var i = 0; i < n; i++)
            {
                var r = row + i * dr;
                var c = col + i * dc;
                if (wrap) c = ((c % w) + w) % w;          // cylinder: columns wrap around
                if (r < 0 || r >= h || c < 0 || c >= w) { inside = false; break; }
                var piece = board[r][c];
                if (piece == me) mine++;
                else if (piece == opp) theirs++;
            }
            if (!inside) continue;
            if (theirs == 0) score += WindowWeights[mine];
            else if (mine == 0) score -= WindowWeights[theirs];
        }

        var centre = w / 2;
        for (var row = 0; row < h; row++)
        {
            if (board[row][centre] == me) score += CentreBonus;
            else if (board[row][centre] == opp) score -= CentreBonus;
        }
        return score;
    }
}

IsCylinder is the Connect Four extension flag - add public bool IsCylinder { get; init; } to the body of your GameConfiguration record if it is not already there. The double modulo keeps negative columns (from the down-left diagonal) inside the board. Your configuration validation must already guarantee WinLength ≤ BoardWidth, otherwise a wrapped window would visit the same cell twice.

Notice what the method does not do: no LINQ, no list of windows, no allocation at all. A Windows() iterator that yields coordinate arrays reads nicer and costs one allocation per window - millions per second. Write the readable one first if you like, keep the loop version in the hot path.

Per-game heuristics

The window idea transfers; the features do not. What follows is what your evaluation should count for each game. Weights are starting points - tune them by letting two AIs with different weights play each other.

Tic-Tac-Two

• Lines inside the movable grid only. A three-in-a-row outside the grid is not a win, so windows must be restricted to the current grid position. Reuse the window scan with the grid's top-left corner and size as bounds.
• Grid mobility. After the unlock threshold, count how many of the grid's legal destinations would put one of my lines inside it (or take one of the opponent's out). Even a small bonus per such destination makes the AI use the grid move instead of ignoring it.
• Pieces in hand. Before the unlock, having pieces left to place is flexibility; after it, a piece already on the board can be moved, so the difference matters less.
• The branching factor jumps once grid and piece moves unlock. Expect to lower the depth for the Classic and Big presets and keep the Plain 3×3 preset for tests.

Reversi / Othello

Counting discs is the worst heuristic in Reversi until the last few moves - a big disc lead in the middle game usually means fewer legal moves. Use:

• Corners. A corner disc can never be flipped. Weight it like ten ordinary discs. Cells next to a corner (the X-square diagonally and the C-squares orthogonally) are negative while the corner is empty because they hand the corner to the opponent.
• Mobility. myMoves - theirMoves, using your existing GetLegalMoves for both colours. Expensive, but the strongest single feature.
• Stability. Discs that cannot be flipped any more (corners and edge runs anchored to a corner). A full stability check is heavy; the positional table below approximates it.
• Parity. Having the last move in a region (and in the game) is worth a little; in the endgame switch to disc count and search to the end.
• Walls (your blocked-cells extension) are simply cells with weight 0 that flanking cannot pass through - the rules handle that, the heuristic ignores them.

A positional weight table for 8×8 is the classic starting point. Nobody serialises it, so int[,] is fine here:

// GameEngine/Ai/ReversiEvaluator.cs (excerpt)
private static readonly int[,] Weights8 =
{
    { 100, -20,  10,   5,   5,  10, -20, 100 },
    { -20, -50,  -2,  -2,  -2,  -2, -50, -20 },
    {  10,  -2,   1,   1,   1,   1,  -2,  10 },
    {   5,  -2,   1,   0,   0,   1,  -2,   5 },
    {   5,  -2,   1,   0,   0,   1,  -2,   5 },
    {  10,  -2,   1,   1,   1,   1,  -2,  10 },
    { -20, -50,  -2,  -2,  -2,  -2, -50, -20 },
    { 100, -20,  10,   5,   5,  10, -20, 100 },
};

Evaluate is then the sum of Weights8[r, c] over my discs minus the same over the opponent's, plus about 5 * (myMoves - theirMoves). Board size is configurable in your version (even, 4-16, rectangles allowed), so generate the table from the rule instead of hard-coding it: corners 100, X-squares -50, C-squares -20, other edge cells 10, interior 1, walls 0.

Gomoku

Windows of five are too coarse for Gomoku; what wins is shape. Count, per player:

• Open four (.XXXX.): unstoppable, worth almost a win.
• Closed four (OXXXX.): must be answered immediately.
• Open three (.XXX.): becomes an open four next move.
• Closed three, open two: small change.

Scan every line in the four directions once, run-length encode it, and classify each run by whether its ends are empty, blocked or the board edge. Weight roughly 10 000 / 1 000 / 100 / 10, and count the opponent's shapes with a slightly higher weight - defence first.

The overline rule changes both the win test and the heuristic: with "exactly N" a run of six is not a win, so a run of five bounded by an own piece must be scored as nothing, and an open four that would become an overline is not open. With free-style, N-or-more wins and none of that applies. Read the flag from the configuration in one place.

On a 15×15 board the raw branching factor is over 200. Candidate moves - only cells within distance 2 of an existing piece - cut it to 20-40 and are the difference between depth 2 and depth 5. Put that filter into the AI's move generation, not into GetLegalMoves (a human is still allowed to play in the corner).

Nine Men's Morris

The board is a graph of 24 points with adjacency and mill lists, and the game has three phases. Weight by phase:

• Piece difference - (myOnBoard + myInHand) - (theirs), the dominant term everywhere.
• Mills - closed mills, and potential mills: two own pieces on a mill line with the third point empty. In the placing phase potential mills matter more than closed ones.
• Mobility - legal moves in the moving phase; a player with zero mobility has lost, so weight blocked opponent pieces heavily. In the flying phase mobility is meaningless.
• Game phase - store it in the state or derive it from pieces in hand and on board; pick the weight set by phase. A double mill (one piece shuttling between two mills) is rare and decisive - give it its own bonus.

Because moves are multi-step, a move record carries source, destination and capture; the search does not care, the undo (below) does.

Difficulty levels

A5 requires at least three levels. Four dials, combine as you like:

Dial	Easy	Medium	Hard	What it does
Search depth	1-2	3-4	as deep as the budget allows	The obvious one; depth 1 with a good heuristic is already not trivial
Random-move chance	30 %	5 %	0 %	Occasionally plays a random legal move - visibly "makes mistakes"
Evaluation noise	±50	±10	0	Adds jitter to Evaluate, so the AI mis-ranks close positions
Time budget	0.2 s	1 s	4 s	With iterative deepening the depth adapts to the position

// GameEngine/Ai/AiDifficulty.cs
public record AiDifficulty(
    string Name,
    int MaxDepth,
    double RandomMoveChance,
    int EvaluationNoise,
    TimeSpan TimeBudget)
{
    public static readonly AiDifficulty Easy = new("Easy", 2, 0.30, 50, TimeSpan.FromMilliseconds(200));
    public static readonly AiDifficulty Medium = new("Medium", 4, 0.05, 10, TimeSpan.FromSeconds(1));
    public static readonly AiDifficulty Hard = new("Hard", 12, 0.0, 0, TimeSpan.FromSeconds(4));

    public static IReadOnlyList<AiDifficulty> All => [Easy, Medium, Hard];
}

The provider takes the difficulty and the evaluator instead of a bare depth. Random-move mixing happens at the root; noise happens at the leaves:

// GameEngine/Ai/MinimaxMoveProvider.cs (revised constructor and leaf)
public class MinimaxMoveProvider(
    GameBrain brain,
    IEvaluator evaluator,
    AiDifficulty difficulty,
    Random? random = null) : IGameAi
{
    private readonly Random _random = random ?? new Random();
    private EGamePiece _aiPiece = EGamePiece.Empty;

    public int NodesVisited { get; private set; }
    public int DepthReached { get; private set; }

    protected virtual int Evaluate(GameState s)
    {
        var score = evaluator.Evaluate(s, _aiPiece);
        return difficulty.EvaluationNoise == 0
            ? score
            : score + _random.Next(-difficulty.EvaluationNoise, difficulty.EvaluationNoise + 1);
    }

    public (int Row, int Col) GetMove(GameState state)
    {
        _aiPiece = state.NextMoveBy;
        var moves = brain.GetLegalMoves(state);
        if (moves.Count == 0) throw new InvalidOperationException("No legal moves - the game should be over.");
        if (_random.NextDouble() < difficulty.RandomMoveChance) return moves[_random.Next(moves.Count)];
        return SearchWithTimeBudget(state, moves);
    }
    // ... AlphaBeta from lecture 09.1, SearchWithTimeBudget below
}

The menu shows AiDifficulty.All by name, the saved game stores the chosen name for each AI player, and the console and web apps both reconstruct the provider from it. That is the "add a difficulty level" live change a TA may ask for: one more static field.

Move ordering

Alpha-beta prunes most when the best move is tried first. Two cheap orderings:

• Centre first. In N-in-a-row games the middle columns are usually best. Sort the legal moves by distance from the centre column before the loop.
• Killer moves. A move that caused a cut-off at a given depth is likely to cause one again in a sibling subtree. Remember one per depth and try it first if it is legal here.

    private readonly (int Row, int Col)?[] _killers = new (int Row, int Col)?[64];

    private List<(int Row, int Col)> OrderedMoves(GameState s, int depth)
    {
        var moves = brain.GetLegalMoves(s);
        var centre = s.Config.BoardWidth / 2;
        moves.Sort((a, b) => Math.Abs(a.Col - centre).CompareTo(Math.Abs(b.Col - centre)));

        if (_killers[depth] is { } killer && moves.Remove(killer)) moves.Insert(0, killer);
        return moves;
    }

    // inside AlphaBeta, at the cut-off:
    //   if (beta <= alpha) { _killers[depth] = (row, col); break; }

Reversi orders corners first, then edges; Nine Men's Morris orders mill-closing moves first. Measure NodesVisited before and after - ordering that does not reduce it is just slower.

Iterative deepening with a time budget

A fixed depth is either too slow in the opening (many moves) or too shallow in the endgame (few moves). Iterative deepening searches depth 1, then 2, then 3, and stops when the budget is used up, keeping the best move from the last completed depth. The shallower searches are nearly free - each depth costs roughly b times the previous one - and they also seed the killer moves for the next iteration.

    private Stopwatch _clock = new();
    private bool _outOfTime;

    private (int Row, int Col) SearchWithTimeBudget(GameState state, List<(int Row, int Col)> moves)
    {
        _clock = Stopwatch.StartNew();
        _outOfTime = false;
        NodesVisited = 0;
        var best = moves[0];

        for (var depth = 1; depth <= difficulty.MaxDepth; depth++)
        {
            var (move, score, completed) = SearchRoot(state, moves, depth);
            if (!completed) break;                          // discard the partial iteration
            best = move;
            DepthReached = depth;
            if (Math.Abs(score) >= WinScore) break;          // forced result found, deeper is pointless
        }
        return best;
    }

    // called every node; checking the clock every 1024 nodes keeps it cheap
    private bool TimeIsUp()
    {
        if ((NodesVisited & 1023) == 0 && _clock.Elapsed > difficulty.TimeBudget) _outOfTime = true;
        return _outOfTime;
    }

SearchRoot is the root loop from lecture 09.1 returning (move, score, !_outOfTime), and AlphaBeta gets one extra line after NodesVisited++: if (TimeIsUp()) return 0;. The returned 0 is garbage, which is exactly why the whole iteration is thrown away. With the budget in place MaxDepth becomes a ceiling, not a target - Hard can say 12 and simply reach whatever the laptop manages.

Transposition table (bonus)

Different move orders often reach the same position. A transposition table remembers positions already evaluated at a given depth so the second visit is a dictionary lookup. The key is the board plus the side to move; a string key is slow but obvious, and it is what you will replace with Zobrist hashing if you go further.

    private readonly Dictionary<string, (int Depth, int Score)> _table = [];

    private static string Key(GameState s)
    {
        var chars = new char[s.Config.BoardWidth * s.Config.BoardHeight + 1];
        var i = 0;
        foreach (var row in s.Board)
        foreach (var cell in row)
            chars[i++] = cell switch { EGamePiece.X => 'X', EGamePiece.O => 'O', _ => '.' };
        chars[i] = s.NextMoveBy == EGamePiece.X ? 'x' : 'o';
        return new string(chars);
    }

    // in AlphaBeta, after the terminal test:
    //   var key = Key(s);
    //   if (_table.TryGetValue(key, out var hit) && hit.Depth >= depth) return hit.Score;
    //   ... search ...
    //   if (alpha < best && best < beta) _table[key] = (depth, best);   // store exact scores only

Store only values that were not the result of a cut-off - a pruned node's value is a bound, not the truth. Clear the table per GetMove, or it grows without limit. This is a bonus-point item in the syllabus; do the heuristic and the difficulty levels first.

Performance

Measure before you optimise

Stopwatch around GetMove, plus NodesVisited, gives the number you want to track:

var sw = Stopwatch.StartNew();
var move = ai.GetMove(state);
sw.Stop();
Console.WriteLine($"depth {ai.DepthReached}, {ai.NodesVisited} nodes in {sw.ElapsedMilliseconds} ms " +
                  $"= {ai.NodesVisited / Math.Max(sw.Elapsed.TotalSeconds, 0.001):N0} nodes/s");

For where the time goes use Rider's profiler (run configuration → "Profile with dotTrace", or the Dynamic Program Analysis hints that appear while you run). Expect Clone(), GetLegalMoves and Evaluate at the top. Do not guess; the answer is different for every game.

Typical numbers with the plain cloning implementation from lecture 09.1 on a laptop, roughly what one second buys:

Game	Branching factor	Nodes per second	Depth in ~1 s
Tic-Tac-Two, Plain 3×3	≤ 9	~1 M	full game (9)
Connect Four 7×6	≤ 7	0.5-1 M	8-10
Reversi 8×8	~10	100-300 k (move generation is the cost)	5-7
Gomoku 15×15, all cells	~200	~200 k	2-3
Gomoku 15×15, candidate moves	20-40	~200 k	4-6
Nine Men's Morris	5-30	~300 k	5-8

If you are an order of magnitude below these, profile. If you are above, write the numbers into the README - A5 asks for them.

Allocations

Every Clone() allocates BoardHeight + 1 arrays plus the Moves list; at a million nodes per second that is a lot of garbage collection. In order of effort:

• Do not clone Moves in the search. Give the AI a lighter search state, or keep Moves out of the clone and append it only for the root move you actually play.
• Reuse buffers. GetLegalMoves returning a fresh List<T> per node can take a caller-provided list and Clear() it. The evaluator above already allocates nothing.
• Span<T> and stackalloc for small temporary arrays (a window of 4-6 cells, a line of 15 cells) put them on the stack. Mentioned so you recognise them; not required.

Structs, classes, arrays and LINQ

• (int Row, int Col) is a value tuple - a struct, no allocation. A record struct Move(int Row, int Col) is the same with a name; a record class Move would allocate per move. Keep moves small and struct-shaped.
• GameState stays a class: it is shared, mutated and persisted. Only the search wants a lean value-like copy.
• Jagged arrays [][] are what JSON can serialise; indexing them is fast enough. Do not convert to [,] in the AI "for speed" - the copying costs more than you save.
• LINQ is for tests, UI and repositories. In Evaluate, GetLegalMoves and CheckWin a Where(...).Count() allocates an enumerator and a closure at every node. Write the loop.

Cloning strategies versus make/undo

Strategy	Allocation per node	Bug risk	Good for
Full Clone()	board + history	none	all games, first version
Clone without history	board only	none	all games, easy win
Make / undo	zero	every rule needs an undo	N-in-a-row games, Tic-Tac-Two
Make / undo with undo record	one small struct	captures and flips must be recorded	Reversi, Nine Men's Morris

For the N-in-a-row engine undo is three lines, and the search becomes MakeMove, recurse, UndoMove on one shared state:

// GameEngine/GameBrain.cs
public void UndoMove(GameState state, int row, int col)
{
    state.Board[row][col] = EGamePiece.Empty;
    state.Moves.RemoveAt(state.Moves.Count - 1);
    state.NextMoveBy = state.NextMoveBy == EGamePiece.X ? EGamePiece.O : EGamePiece.X;
}

Reversi must also un-flip the discs it flipped, so MakeMove returns (or pushes) the list of flipped cells; Nine Men's Morris returns the captured point and the previous phase. Write a test that asserts MakeMove followed by UndoMove restores the exact board - it is the test that will save you an evening.

Keeping the UI responsive

A 4-second search on the UI thread means a console that does not react to keys and, in A6, a web request that just hangs. Run the search on the thread pool and give it a cancellation token that fires on the time budget or on a key press. The details of async/await and cancellation are in 10.2 - async/await; this is the shape you need now.

// ConsoleUI/GameRunner.cs
public async Task<(int Row, int Col)> ThinkAsync(IMoveProvider ai, GameState state, CancellationToken ct)
{
    var thinking = Task.Run(() => ai.GetMove(state), ct);
    while (!thinking.IsCompleted)
    {
        Console.Write(".");
        await Task.Delay(200, ct);
        if (Console.KeyAvailable && Console.ReadKey(true).Key == ConsoleKey.Escape)
        {
            throw new OperationCanceledException("Player interrupted the AI.");
        }
    }
    return await thinking;
}

Task.Run only stops waiting; the search itself keeps running until it checks the token. Give the provider a CancellationToken (constructor or a GetMove(state, ct) overload) and call ct.ThrowIfCancellationRequested() in the same place TimeIsUp() runs. In the web app the token comes from the request and the time budget from the difficulty - same code.

The AI-vs-AI loop is the human loop with a delay, so people can watch it:

public async Task RunAiVsAiAsync(GameState state, IMoveProvider x, IMoveProvider o, CancellationToken ct)
{
    while (!IsGameOver(state))
    {
        var provider = state.NextMoveBy == EGamePiece.X ? x : o;
        var (row, col) = await ThinkAsync(provider, state, ct);
        brain.MakeMove(state, row, col);
        Draw(state);
        await Task.Delay(300, ct);
    }
}

private bool IsGameOver(GameState s)
    => brain.CheckWin(s, EGamePiece.X) || brain.CheckWin(s, EGamePiece.O) || brain.IsDraw(s);

Two AIs with different difficulties, or the same difficulty with different weights, playing a hundred games in a loop with Task.Delay removed is also the cheapest way to tune your heuristic: change one weight, count the wins.

Web is stateless

In A6 an AI move is one POST: load the game, compute the move within the budget, save, redirect. Nothing waits between requests, so the time budget must suit a browser (a few seconds) and the search must stop on the request's CancellationToken. Design the provider for that now and the web port is one registration line.

Self preparation QA

1. Why must the evaluation function never reach the win score? — A heuristic that can exceed the utility makes the AI prefer a "nice" position over an actual win, or ignore an actual loss.
2. What does a window-based heuristic count? — Every run of WinLength cells; windows containing only my pieces score positively by count, only the opponent's negatively, mixed windows zero.
3. Why is disc count a bad heuristic in the Reversi middle game? — More discs usually means fewer legal moves; corners, mobility and stability predict the result better until the endgame.
4. Which four dials make a difficulty level? — Search depth, random-move chance, evaluation noise, time budget (with iterative deepening).
5. What does iterative deepening keep when the budget runs out? — The best move from the last fully completed depth; the partial iteration is discarded.
6. Why does move ordering matter for alpha-beta? — Pruning depends on finding a good move early; perfect ordering reduces the nodes from b^d towards b^(d/2).
7. What is the risk of make/undo versus cloning? — Every rule that changes the board needs an exact undo (flips, captures, phase); cloning cannot be wrong but allocates per node.
8. What does Task.Run do and what does it not do? — It moves the search off the calling thread so the UI stays responsive; it does not stop the search - only a checked CancellationToken does.