CSE330-ECA Artificial Intelligence Assignment 01 Brief 2025

Question 2: Pursuit-Evasion Game (7.5 points)

(a) Terminal Node Values in the Game Tree 

In this turn-based game, Pursuer (P) and Evader (E) take turns moving. The game ends when both land on the same node. The terminal payoff for the pursuer is minus the number of moves taken to reach the evader (Li, Qian, Li, & Li, 2025). 

We are given a partial game tree. Terminal nodes are states where P = E (i.e., they have caught the evader). These should be marked with the negative depth (number of moves) at which the capture happens. For example: 

• (b, d) → (e, d) → (e, c) → (d, c) → (d, d) would have a value of -4. 

Each path's terminal value depends on the number of total moves made until capture.

(b) Inference About Internal Node Values 

At internal nodes, we can only deduce partial bounds: 

• Use inequalities if terminal values aren't yet reached.
• For instance, if a path is guaranteed to take at least 4 moves to reach a terminal node, we write "≥ -4" next to it.

 If one terminal node below it has a value of -5 and no better options are possible, the internal node should take that. 

(c) Names of Nodes Beneath Question Marks 

Each "?" represents an unexplored branch. These should be replaced with the state (P, E) reached by the next move. For instance: 

• From (e, c), if E moves to node "f," the new node is (e, f).
• Replace each "?" with the appropriate new (P, E) state. 

(d) Deriving Bounds Using Shortest Paths 

The shortest path from P to E can be used to set a lower bound on the number of turns required for capture. Since both take alternating moves: 

• Suppose P is at node x and E is at node y.
• Let dist(x, y) be the shortest path between them.
• Minimum number of moves needed to catch the evader: 2 × floor(dist / 2) (because E moves after P). 

Using this principle, if the shortest distance between P and E is 6: 

• Minimum total moves = 6 (assuming no mistakes by E).
• So the value is ≥ -6. 

Apply this to each leaf node derived in (c). 

(e) Pruning the Game Tree with Bounds 

Once you have bounds on all terminal values: 

• If a leaf node provides a value worse than a previously found better result (e.g., if pursuing always takes 5 turns or more, but we found a 3-turn capture elsewhere), cross out the less optimal path.
• Circle any "?" that need not be expanded because their best-case result is already inferior (Elberfeld, Kammer, & Meintrup, 2025). 

This is similar to alpha-beta pruning in minimax trees. Any branch whose worst-case value is already worse than the best-known option is unnecessary to evaluate.