PadhaikoAll subjects

Problem Solving and Search (part 2: 2.5–2.8)

Artificial Intelligence (ENCT 351)

Open in the Padhaiko app

2.5 Informed Search: Best first search, greedy search, A* algorithm

Informed (heuristic) search uses problem-specific knowledge beyond the definition of the problem itself—in the form of an evaluation function and a heuristic function —to find solutions much more efficiently than blind search.

Definition

Heuristic and Best-First Search

Greedy Best-First Search

Search Algorithm

combines the cost spent so far with the estimated remaining cost:

where is the exact path cost from the start node to , and is the estimated cost from to the goal.

Theorem

Admissibility, Consistency, and Optimality of A*

  1. Admissibility: A heuristic is admissible if it never overestimates the true minimum cost to reach a goal:

If is admissible, tree-search is optimal.

  1. Consistency (Monotonicity): A heuristic is consistent if for every node and every successor generated by action ,

Every consistent heuristic is admissible (by induction along any path). If is consistent, graph-search is optimal, and is non-decreasing along any path.

AspectGreedy Best-First SearchA* Search
Evaluation function
Uses past cost ?NoYes
CompletenessIncomplete in tree search (complete in finite graph search)Complete (if branching finite and step costs )
OptimalityNot optimalOptimal (admissible for tree; consistent for graph)
Heuristic accuracyGuides fast, easily misledOptimally efficient (no other optimal algorithm expands fewer nodes)

2.6 Adversarial search: Minimax algorithm, alpha-beta pruning

In adversarial search (two-player, deterministic, turn-taking, zero-sum games such as chess or tic-tac-toe), the agent cannot simply plan a path to a goal because an opponent (MIN) actively works against the agent (MAX).

Formal Game Elements

A game is defined by: initial state , PLAYER(s), ACTIONS(s), RESULT(s, a), TERMINAL-TEST(s), and UTILITY(s, p) (assigning or numeric scores at terminal states).

Minimax Algorithm

MAX chooses the move maximizing the backed-up value, while MIN chooses the move minimizing it:

Alpha-Beta () Pruning

Because is too slow for real games (in chess, , ), alpha-beta pruning computes the exact same minimax value without exploring branches that cannot possibly affect the final decision.

Definition

Alpha and Beta Bounds

Pruning rule: Update at MAX nodes and at MIN nodes. Whenever (or equivalently at a MAX node, or at a MIN node), prune the remaining children of that node immediately.

Alpha-Beta Pruning pseudocodeText
function ALPHA-BETA-SEARCH(state):
    v = MAX-VALUE(state, -infinity, +infinity)
    return action with value v

function MAX-VALUE(state, alpha, beta):
    if TERMINAL-TEST(state): return UTILITY(state)
    v = -infinity
    for each a in ACTIONS(state):
        v = max(v, MIN-VALUE(RESULT(state, a), alpha, beta))
        if v >= beta: return v        // beta cutoff
        alpha = max(alpha, v)
    return v

function MIN-VALUE(state, alpha, beta):
    if TERMINAL-TEST(state): return UTILITY(state)
    v = +infinity
    for each a in ACTIONS(state):
        v = min(v, MAX-VALUE(RESULT(state, a), alpha, beta))
        if v <= alpha: return v       // alpha cutoff
        beta = min(beta, v)
    return v

2.7 Local search and optimization: Hill climbing, simulated annealing

When only the final state matters and the path to reach it is irrelevant (e.g., 8-queens placement, VLSI chip layout, timetable scheduling), local search operates on a single current state (or small set) and moves to neighbouring states using very little memory ().

Hill Climbing Search

Hill climbing (greedy local search) continually moves to a neighbour with a higher objective value (or lower cost) until no neighbour improves on the current state.

Variants and Limitations of Hill Climbing
ConceptExplanation
Steepest-ascent hill climbingEvaluates all neighbours and picks the best one; stops if none is better
Stochastic hill climbingPicks at random among uphill moves (probability can depend on steepness)
Random-restart hill climbingRuns hill climbing repeatedly from random initial states until a goal is found
Local maximaPeaks lower than the global maximum where all neighbours go downhill
RidgesNarrow sequences of local maxima difficult to traverse via axis-aligned single steps
PlateauxFlat regions (shoulder or flat local maximum) where all neighbours have equal value

Simulated Annealing

Inspired by metal annealing (heating then slowly cooling to reach a low-energy crystal), simulated annealing escapes local maxima by allowing occasional downhill (worse) moves with a probability that shrinks as temperature decreases.

Definition

Simulated Annealing Acceptance Rule

At step , pick a random neighbour of the current state , and compute (for maximization):

where is the current temperature from a cooling schedule (if minimizing cost, and worse moves have , accepted with ).

2.8 Evolutionary optimization: Genetic algorithm

A Genetic Algorithm (GA) is a stochastic beam-search variant inspired by biological evolution. Instead of keeping one state, it evolves a population of candidate states (individuals / chromosomes).

Definition

Genetic Algorithm Operators

  1. Encoding (Representation): Each candidate solution is encoded as a string (often binary bits or integer permutation), called a chromosome.
  2. Fitness function: Scores how good each individual is; higher fitness means higher chance of surviving and reproducing.
  3. Selection: Chooses parents from the current population in proportion to fitness (e.g., roulette-wheel selection, where , or tournament selection).
  4. Crossover (Recombination): Combines two parent chromosomes at one or more random crossover points to produce offspring sharing traits from both parents.
  5. Mutation: Flips a random gene/bit with a small mutation probability to maintain population diversity and prevent premature convergence to local optima.
Genetic Algorithm cycleText
Initialize population P of k random chromosomes
Repeat until stopping criterion (target fitness or max generations):
    Evaluate fitness f(x) for every individual x in P
    New population P_new = empty
    Repeat k times (or k/2 pairs):
        Select two parents x, y from P based on fitness
        With crossover rate p_c: recombine x, y at crossover point -> child(ren)
        With small mutation rate p_m: randomly alter gene(s) in child
        Add child to P_new
    P = P_new
Return fittest individual found
AspectSimulated AnnealingGenetic Algorithm
States trackedSingle current statePopulation of states
Key operatorsRandom neighbour + temperature Selection, crossover, mutation
Exploration mechanismUphill/downhill jumps controlled by Recombination of building blocks + mutation
Memory for individuals

Worked Out Examples

Example 2.4

2.4 (8 marks)

Find the optimal path from to using Graph (). Directed edge costs are: , , , , , , . Heuristic values are .

Start at : Frontier . Expand :

  • : , .
  • : , .

Frontier .

Expand lowest : ():

  • via : , .

Frontier .

Tie at (expand before , or —check first): Expanding () generates:

  • via : (cheaper than , but was already expanded? Note: let us check consistency at : ; at : is FALSE! is admissible but not consistent!).
  • via : , .
  • via : , .

Because is not consistent (), with reopening updates to !

Expand (): updates to , . Expand (): reaches with , . Expand (): all remaining frontier nodes have , so is optimal!

Answer:

Optimal path: with minimum total cost .

Example 2.5

2.5 (8 marks)

Evaluate a 2-ply game tree where the root is MAX () with three MIN children (). Leaf values under are ; under are ; under are . Trace left-to-right alpha-beta pruning and state which leaves are pruned.

Explore MIN node with :

  • Leaf : .
  • Leaf : .
  • Leaf : .

returns to MAX root , so .

Explore MIN node with :

  • First leaf is : , so .
  • Now : alpha cutoff! MIN node can return at most , which MAX root will never pick over . Leaves and under are pruned. returns ; remains .

Explore MIN node with :

  • First leaf : (, continue).
  • Second leaf : (, continue).
  • Third leaf : .

returns . Root MAX chooses (move to ).

Answer:

Root minimax value (MAX chooses ). Leaves and under MIN node are pruned by an alpha cutoff.

Example 2.6

2.6 (6 marks)

In a maximization problem using simulated annealing, the current state has value and a randomly chosen neighbour has value . Calculate the acceptance probability of moving to this worse neighbour when temperature is (a) and (b) .

Compute the change in value:

At high temperature :

At low temperature :

Answer:

Acceptance probability is () at , dropping to () at .

Exercises

Exercise: Informed Search, Adversarial Search, and Local Optimization

Question 1

Define admissible and consistent heuristics. Prove briefly why graph search can be suboptimal if is admissible but not consistent, or explain how consistency guarantees optimality.

Definitions: is admissible if for all (never overestimates true cost to goal). is consistent if for every edge and .

Why consistency guarantees graph-search optimality: Along any path, , so never decreases. Thus, whenever pops a node for expansion, the optimal path to has already been found, so no suboptimal goal can ever be popped before the optimal goal.

Answer:

An admissible heuristic never overestimates ; a consistent heuristic satisfies the triangle inequality , making non-decreasing along paths and ensuring the first expansion of any node (including the goal) is via its optimal path.

Question 2

Trace search from to on a graph with edges , , , , , and consistent heuristic . Find the optimal path and total cost.

Expand (): Frontier .

Expand ():

  • via : , update to .
  • via : .

Frontier .

Expand ():

  • via : , update to .

Expand (): goal reached!

Answer:

Optimal path: with total cost .

Question 3

In a 2-ply game tree, root MAX () has two MIN children and . Under are leaves ; under are leaves . Apply alpha-beta pruning left-to-right, find the root minimax value, and state whether any leaf is pruned.

Node (MIN) with : evaluates () and (), returning . Root MAX updates .

Node (MIN) with : evaluates first leaf . Now , triggering an alpha cutoff. Leaf is pruned. returns .

Root : .

Answer:

Root minimax value (MAX picks ). Leaf under is pruned.

Question 4

Explain local maxima, ridges, and plateaux in hill climbing. In simulated annealing, if a worse move reduces objective value by units at temperature , what is its acceptance probability?

Hill-climbing traps: A local maximum is a peak better than all immediate neighbours but worse than the global optimum. A ridge is a rising crest not aligned with single-step moves, forcing zig-zagging or stalling. A plateau is a flat region where neighbours have equal value, leaving no uphill direction.

Simulated annealing calculation: Here and :

Answer:

Local maxima, ridges, and plateaux trap pure hill climbing because no single move improves the score. With and , simulated annealing accepts the worse move with probability .

Question 5

Describe the steps and operators of a Genetic Algorithm. If four chromosomes have fitness values , compute the roulette-wheel selection probability of the fittest and least-fit chromosome.

GA operators: Representation (chromosome encoding), fitness evaluation, selection (favouring fitter parents), crossover (recombining parent substrings), and mutation (random bit/gene flip to preserve diversity).

Selection probabilities: Total fitness .

  • Fittest chromosome (): ().
  • Least-fit chromosome (): ().
Answer:

GA cycles through fitness evaluation, selection, crossover, and mutation. With total fitness , the fittest chromosome has selection probability () and the least-fit has ().

← Problem Solving and Search (part 1: 2.1–2.4)Knowledge Representation and Probabilistic Reasoning →