Search, Game Playing and Rational Agents

GATE CS has no Artificial Intelligence section at all. This chapter opens Unit 10 with the Turing test and the rational-agent framing of what AI even means, state-space search (uninformed and informed/heuristic), and adversarial game-playing search (min-max, alpha-beta pruning) — the classical, foundational core of AI before any learning is involved.

The Turing Test and the Rational Agent Approach

The Turing test asks whether a human interrogator, conversing via text with an unseen human and an unseen machine, can reliably tell which is which — passing it is a BEHAVIOURAL criterion for intelligence (acting indistinguishably from a human), and its historical importance is in reframing 'can machines think?' (a question about internal experience, hard to operationalise) into 'can machines DO what a thinking entity does?' (a question about observable behaviour). The rational agent approach, which modern AI actually organises itself around, defines an agent by a PERFORMANCE MEASURE it should maximise, given its PERCEPTS (what it has sensed) and PRIOR KNOWLEDGE, choosing the ACTION that is expected to do best — this is a broader, more general criterion than the Turing test, since it applies to any agent (a thermostat, a self-driving car, a chess program) whether or not human-like conversation is even relevant to its task.

Game Playing: Min-Max and Alpha-Beta Pruning

Min-max models a two-player, zero-sum, perfect-information game as a tree of alternating moves: the MAX player picks the move leading to the child with the HIGHEST value, the MIN player picks the move leading to the child with the LOWEST value, and values propagate up from leaf (terminal-state) evaluations — this correctly models an adversarial opponent who always plays to minimise MAX's outcome, in contrast to an algorithm that merely assumed the opponent's moves at random. Alpha-beta pruning computes the EXACT SAME min-max value while skipping large parts of the tree that provably cannot affect the final decision: alpha is the best value MAX can guarantee so far along the current path, beta the best value MIN can guarantee — once a node's value is found to be worse than what the opponent could already force elsewhere (beta ≤ alpha), the rest of that node's children are pruned WITHOUT EXPLORING THEM, since no matter what they evaluate to, a rational opponent would never let the game reach that node in the first place.

⚠️ Alpha-beta pruning changes running time, never the answer
A common misreading is that alpha-beta trades correctness for speed. It does not: alpha-beta ALWAYS returns exactly the same move min-max would have returned given the same evaluation function and search depth — the pruned branches are provably irrelevant to the final decision, never merely 'probably safe to skip'. Its practical value is purely computational: with a good move ORDERING (trying the most promising moves first), it can search roughly twice as deep as plain min-max in the same time, which is what makes it the standard rather than an approximation used only when time is short.

A Worked Alpha-Beta Example and When Search Alone Is Not Enough

  • Tracing alpha-beta by hand: process children left to right; at a MAX node, update alpha to the best child value found so far; at a MIN node, update beta similarly; the moment a MIN node's current beta drops to or below its ANCESTOR MAX node's alpha, stop exploring that MIN node's remaining children (a beta cutoff) — and symmetrically, a MAX node's alpha rising to or above its ancestor MIN node's beta triggers an alpha cutoff.
  • Chess is a real game where the state space is so vast that even perfect search machinery is not enough on its own — depth-limited search combined with a hand-crafted or learned EVALUATION FUNCTION (estimating a non-terminal position's value without exhaustively searching to the game's actual end) is what real chess engines use, which is exactly the practical bridge between this classical search chapter and the neural-network-based evaluation approaches modern engines also draw on, covered in this unit's own artificial-neural-network chapter.

Key takeaways

  • The Turing test is a behavioural criterion for intelligence; the rational agent framing (maximise a performance measure given percepts and knowledge) is broader and is what modern AI actually organises around.
  • A* with an admissible heuristic (never overestimating) is guaranteed to find the optimal solution.
  • Min-max propagates alternating best/worst values up a game tree; alpha-beta prunes provably-irrelevant branches, returning the exact same answer faster.
  • Alpha-beta pruning changes running time, never the final decision — good move ordering roughly doubles the depth searchable in the same time.
  • Real games like chess combine depth-limited search with an evaluation function, since the true state space is too vast to search exhaustively.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

  1. The rational agent framing, compared to the Turing test, is a broader criterion because:

    1. It applies to any agent maximising a performance measure, whether or not human-like conversation is relevant
    2. It requires the agent to pass a text conversation test
    3. It only applies to chess-playing programs
    4. It is identical to the Turing test in every way
    Show answer

    Answer: A — It applies to any agent maximising a performance measure, whether or not human-like conversation is relevant

    A thermostat or a self-driving car can be a rational agent without ever needing to hold a human-like conversation, which is exactly why this criterion applies far more broadly than the Turing test's conversational framing.

  2. A heuristic h(n) that is 'admissible' means:

    1. It never overestimates the true remaining cost to the goal
    2. It always overestimates the true remaining cost
    3. It ignores the goal state entirely
    4. It is always exactly zero
    Show answer

    Answer: A — It never overestimates the true remaining cost to the goal

    Admissibility (h(n) ≤ true remaining cost, always) is exactly the condition needed for A* to be guaranteed optimal, since it prevents the search from ever being falsely optimistic about a worse path.

  3. In min-max search, the MIN player chooses the move leading to:

    1. The child with the lowest value
    2. The child with the highest value
    3. A randomly chosen child
    4. No child at all
    Show answer

    Answer: A — The child with the lowest value

    MIN is modelled as the adversary who always plays to minimise MAX's eventual outcome, so MIN always picks whichever move leads to the lowest value among its children.

  4. Alpha-beta pruning, compared to plain min-max, is best described as:

    1. Returning exactly the same move, faster, by skipping provably irrelevant branches
    2. Returning a different, approximate move to save time
    3. Only usable in single-player games
    4. Ignoring the opponent's moves entirely
    Show answer

    Answer: A — Returning exactly the same move, faster, by skipping provably irrelevant branches

    Alpha-beta's pruned branches are provably irrelevant to the final decision given the same evaluation function and depth, so it always returns exactly what plain min-max would, just computed faster.

  5. Real chess engines cannot search the full game tree to the actual end of the game chiefly because:

    1. The state space is far too vast for exhaustive search, so a depth-limited search plus an evaluation function is used instead
    2. Chess has no terminal states at all
    3. Min-max cannot be applied to chess
    4. Alpha-beta pruning is illegal in chess
    Show answer

    Answer: A — The state space is far too vast for exhaustive search, so a depth-limited search plus an evaluation function is used instead

    Chess's branching factor and game length make exhaustive search computationally infeasible, so engines search only a bounded depth and estimate non-terminal positions' value with an evaluation function instead of searching all the way to a real game-ending state.

  6. Which of the following are true of uninformed (blind) search compared to informed (heuristic) search? (More than one option may be correct.)

    1. Uninformed search uses only the problem's structure, not an estimate of remaining cost
    2. Breadth-first search is a standard uninformed search algorithm
    3. A* is a standard uninformed search algorithm
    4. Informed search can use a heuristic to guide which node to expand next
    Show answer

    Answer: A — Uninformed search uses only the problem's structure, not an estimate of remaining cost; B — Breadth-first search is a standard uninformed search algorithm; D — Informed search can use a heuristic to guide which node to expand next

    A* is the standard example of INFORMED search, using f(n) = g(n) + h(n); BFS is the standard uninformed example, using only the tree's shallowest-first structure with no cost estimate at all.

  7. In A* search, name the function f(n) = g(n) + h(n), where g(n) is the actual cost so far and h(n) is the estimated remaining cost.

    Numerical answer — type the value.

    Show answer

    Answer: evaluation function

    f(n) is A's evaluation function, combining the known cost so far with an estimate of what remains — when h is admissible, this combination is exactly what guarantees A finds the optimal path.

  8. A greedy best-first search, compared to A*, decides which node to expand next using:

    1. The heuristic estimate h(n) alone, ignoring the actual cost incurred so far
    2. Only g(n), the actual cost so far
    3. No information at all
    4. A random coin flip
    Show answer

    Answer: A — The heuristic estimate h(n) alone, ignoring the actual cost incurred so far

    Greedy best-first search expands the node that looks closest to the goal by h(n) alone, which can lead it astray down a path with a low estimate but a high actual cost — exactly the shortfall A*'s f(n) = g(n) + h(n) is designed to fix.