Games, Search and AI Agents

Games as search

A two-player board game can be drawn as a game tree: the current position at the root, every legal move as a branch, and every possible reply below that, down to positions where the game is over.

Noughts and crosses can be solved by brute force: with perfect play it is always a draw. For chess and Go, the tree is far too big, so programs must search cleverly and stop early.

Minimax

In minimax, one player, MAX, wants the score high and the other, MIN, wants it low. Scores at the ends of the tree are passed back up: at MAX's turns take the highest child, at MIN's turns the lowest. The value at the root is the best result MAX can guarantee against a perfect opponent.

Minimax assumes the opponent always replies with their best move. It never hopes for a mistake, which is exactly what makes it safe.

Alpha-beta pruning

Much of the tree never needs to be looked at. Alpha-beta pruning keeps track of the best score each player is already sure of. As soon as one reply shows that a move is worse than an option already found, the rest of that move's replies are skipped: the opponent would never let the game go that way.

Alpha-beta always gives exactly the same answer as minimax. With the best moves examined first it searches roughly the square root of the number of positions, which, for the same time, lets a program look about twice as many moves ahead.

Evaluation functions and Deep Blue

A chess program cannot search to the end of the game, so it searches a few moves ahead and then scores each position with an evaluation function: material (a queen is worth about 9 pawns), safety of the king, control of the centre, and so on.

In 1997 IBM's Deep Blue beat world champion Garry Kasparov 3½–2½. It used alpha-beta search on custom chips that examined about 200 million positions per second, with an evaluation function tuned by grandmasters. Its strength came from search, not from learning, which is why Go, where good evaluation functions were much harder to write by hand, held out for another nineteen years.

Monte Carlo tree search

Monte Carlo tree search (MCTS) builds the tree gradually, spending effort where it matters. Each of thousands of iterations has four phases:

1. Selection: walk down the tree, at each node picking a child that balances a high win rate against having been tried less (the UCB idea from Lesson 13.1).
2. Expansion: add a new child node for an untried move.
3. Simulation: play the game out from there to the end, quickly, with random or simple moves.
4. Backpropagation: pass the result back up the path, updating each node's win count.

The most-visited move at the root is played. No evaluation function is needed, only the rules and a lot of quick games.

AlphaGo and AlphaZero

In March 2016 DeepMind's AlphaGo beat Lee Sedol, one of the strongest Go players in the world, by four games to one. Its 37th move in game two, a move almost no human would play, was later judged to be brilliant. AlphaGo combined MCTS with two neural networks:

• a policy network that suggests promising moves, so the search looks at good moves first;
• a value network that judges who is winning, so simulations can stop early.

It first learned from human games, then improved by playing against itself. In 2017 AlphaZero threw the human games away: given only the rules, it learned chess, shogi and Go purely by self-play, and within 24 hours of training was superhuman at all three.

Self-play is a loop that improves itself: search with the current networks makes better moves than the networks alone, the networks are trained to predict those better moves and the winners of the games, and the improved networks make the next search stronger still.

AI agents

An AI agent is a system that pursues a goal over many steps, choosing actions, observing the results and deciding what to do next. Modern agents put a large language model at the centre of a loop:

1. Think: given the goal and everything so far, the model decides on the next step.
2. Act: it calls a tool, such as a web search, a code runner, a file editor or a calculator (Level 11's function calling).
3. Observe: the program runs the tool and adds the result to the context.
4. Repeat until the goal is reached, or a step limit is hit.

This reason and act pattern was named ReAct in 2022. Agents add memory (notes and retrieval, beyond the context window), planning (breaking a goal into steps), and sometimes several agents working together, one planning and others carrying out parts. Coding agents that read a codebase, edit files and run the tests are one of the most widely used kinds.

Keeping agents safe and useful

An agent's mistakes do not stay in a chat window: it can delete files, spend money or send messages. And errors compound: if each step succeeds 95% of the time, a 20-step task with no checking succeeds only 0.95²⁰ ≈ 36% of the time.

Agents are evaluated on realistic tasks, such as fixing real bugs from open-source projects, checked automatically by running the project's tests.

Hands-on: search and an agent loop

Minimax and alpha-beta on noughts and crosses

O has taken a corner and X the centre. Both searches find X's best move; count how many positions each one looks at.

WINS = [(0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6), (1, 4, 7), (2, 5, 8), (0, 4, 8), (2, 4, 6)]

def winner(b):
    for i, j, k in WINS:
        if b[i] != " " and b[i] == b[j] == b[k]:
            return b[i]
    return None

def minimax(b, player, counter):
    counter[0] += 1
    w = winner(b)
    if w:
        return 1 if w == "X" else -1
    if " " not in b:
        return 0
    scores = []
    for i in range(9):
        if b[i] == " ":
            b[i] = player
            scores.append(minimax(b, "O" if player == "X" else "X", counter))
            b[i] = " "
    return max(scores) if player == "X" else min(scores)

def alphabeta(b, player, alpha, beta, counter):
    counter[0] += 1
    w = winner(b)
    if w:
        return 1 if w == "X" else -1
    if " " not in b:
        return 0
    for i in range(9):
        if b[i] == " ":
            b[i] = player
            v = alphabeta(b, "O" if player == "X" else "X", alpha, beta, counter)
            b[i] = " "
            if player == "X":
                alpha = max(alpha, v)
            else:
                beta = min(beta, v)
            if alpha >= beta:
                break                           # the opponent will never allow this line: prune
    return alpha if player == "X" else beta

board = list("O   X    ")                       # O took a corner, X the centre; X to move
for name, search in [("minimax", lambda b, p, c: minimax(b, p, c)),
                     ("alpha-beta", lambda b, p, c: alphabeta(b, p, -2, 2, c))]:
    counter = [0]
    best_move, best = None, -2
    for i in range(9):
        if board[i] == " ":
            board[i] = "X"
            v = search(board, "O", counter)
            board[i] = " "
            if v > best:
                best_move, best = i, v
    print(f"{name:10}: best move for X is square {best_move}, value {best}, positions searched {counter[0]:,}")

Same answer, about a fifth of the work. A value of 0 means a draw with perfect play.

The agent loop

The loop below is the real structure of an agent. The "model" is a stand-in that follows a fixed plan, so that you can see the loop itself; in a real agent that function sends the conversation to a language model.

FACTS = {"days in a week": 7, "hours in a day": 24, "minutes in an hour": 60}

def lookup(topic):
    return FACTS.get(topic, "not found")

def calculator(a, op, b):
    if op == "+":
        return a + b
    if op == "*":
        return a * b
    return "error: unknown operation"

TOOLS = {"lookup": lookup, "calculator": calculator}

def stand_in_model(question, history):
    # A real agent asks a language model what to do next, given everything so far.
    seen = [result for _, result in history]
    plan = [("lookup", ("days in a week",)), ("lookup", ("hours in a day",)),
            ("calculator", (seen[0] if seen else 0, "*", seen[1] if len(seen) > 1 else 0)),
            ("lookup", ("minutes in an hour",)),
            ("calculator", (seen[2] if len(seen) > 2 else 0, "*", seen[3] if len(seen) > 3 else 0))]
    if len(seen) < len(plan):
        return plan[len(seen)]
    return ("answer", (f"There are {seen[-1]:,} minutes in a week.",))

question = "How many minutes are there in a week?"
history = []
for step in range(1, 11):                         # a hard limit, so a confused agent cannot loop forever
    action, args = stand_in_model(question, history)
    if action == "answer":
        print(f"step {step}: ANSWER {args[0]}")
        break
    result = TOOLS[action](*args)                 # the program, not the model, runs the tool
    history.append(((action, args), result))
    print(f"step {step}: {action}({', '.join(map(repr, args))}) -> {result}")

Try this

1. Start the noughts and crosses search from an empty board, with X to move. How many positions does each search visit?
2. Add a tool to the agent, such as convert(value, from_unit, to_unit), and change the plan to answer "How many seconds are there in a day?"

Level check

• Draw a game tree, and explain why chess and Go cannot be searched completely
• Apply minimax to a small tree
• Explain how alpha-beta pruning saves work without changing the answer
• Explain the role of an evaluation function, and how Deep Blue won
• Describe the four phases of Monte Carlo tree search
• Explain how AlphaGo and AlphaZero combine search, neural networks and self-play
• Describe the think, act, observe loop of an AI agent
• Explain the risks of agents and the safeguards against them

Key terms you must be able to define

Game tree

A tree of positions in which each branch is a legal move.

Minimax

Choosing moves by assuming one player maximises and the other minimises the score.

Alpha-beta pruning

Skipping branches that cannot change the minimax result.

Evaluation function

A score estimating how good a position is, used when the search stops early.

Monte Carlo tree search

Building a game tree by repeated selection, expansion, simulation and backpropagation.

Policy network

A network that suggests promising moves for a position.

Value network

A network that estimates who is winning from a position.

Self-play

Learning a game by playing against copies of yourself.

AI agent

A system that pursues a goal over many steps by choosing actions and observing their results.

ReAct

The pattern of an agent alternating reasoning steps with tool actions and observations.

Sandbox

An isolated environment in which an agent's actions cannot harm anything outside.

Least privilege

Giving an agent only the permissions its task needs.

Flashcards

Go further: notes for future AI engineers

Why search plus learning beats either alone

A policy network alone plays quick, intuitive moves but can be fooled by tactics; search alone needs an impossibly good evaluation function. Together, the network tells the search where to look and how to judge a position, and the search corrects the network's mistakes. The same idea now appears in language models that reason before answering: generating and checking several lines of reasoning is a kind of search guided by a learned model.

Agents and the reliability equation

If a task needs n steps and each succeeds with probability p, the chance of finishing with no mistakes is pⁿ. Raising p from 0.95 to 0.99 lifts a 20-step success rate from 36% to 82%. That is why agent builders care so much about checking each step, retrying failed ones and recovering from errors: an agent that notices and fixes its own mistakes behaves as if p were much higher.

Misconceptions to avoid