Past exam of the computer science course of the University of Oxford / 2023 / Artificial intelligence / 1

Let $V$ be the traversable squares and $H\subseteq V$ the exits. Sample the state space at the end of each complete round, so a live state is $s=(r,f)\in V\times V$ with $r\ne f$. The given starting positions specify the initial state. The board and exits are fixed problem data, rather than changing components of the state space.

The rabbit has at most five actions: stay or move to one of its traversable orthogonally adjacent squares. A search transition model first applies that action, giving $r^{\prime }$, and immediately checks for capture at $r^{\prime }=f$. Otherwise hold $r^{\prime }$ fixed and apply the fox rule twice, checking for capture after each step. A capture is terminal failure; it must not be overlooked merely because the fox could subsequently move elsewhere. A surviving successor is $(r^{\prime },f^{\prime \prime })$. Equivalently, omit actions whose complete-round outcome is capture.

The goal test is the rabbit is on an exit after surviving the fox's entire turn: $r^{\prime }\in H$ and no capture occurred in that round. Merely entering an exit before the fox moves is insufficient. Each surviving search transition model step has cost one when minimizing rounds.

Only legal moves are considered when applying the stated horizontal preference: try a legal horizontal step that reduces horizontal separation, otherwise a legal vertical step that reduces vertical separation, otherwise stay. If a blocked preferred direction is instead interpreted as forcing a stay immediately, the counterexamples below and all completeness and optimality conclusions remain valid.

Write $F=|V|\le mn$. The ordered position pairs give at most $F^2$ states, or $F(F-1)$ live states after excluding capture. Thus the usual Big O notation estimate is $O(m^2{n}^2)$. An additional terminal-failure marker changes this by only one.

For $k$ distinguishable foxes, retain $(r,f_1,\dots ,f_k)$. Different foxes may share a square; none may share the rabbit's square in a live state. There are at most $F(F-1{)}^k$ live position tuples, giving $O((mn{)}^{k+1})$. These counts describe possible encodings; obstacles, starting positions and the fixed fox rule can make the reachable state space much smaller.

The branching factor of the search tree is at most five, so through depth $d$ it has at mostnodes in Big O notation. With no depth bound, the search tree can be infinite, despite the finite state space: tree search retains different action histories even when they end at the same position pair.

For a concrete repeating history, use a two-row, three-column board, indexed from zero, with the sole obstacle $(0,1)$, rabbit at $(0,2)$ and fox at $(0,0)$. Repeated rabbit stays leave the fox blocked horizontally with no vertical separation to reduce. Hence the same live state can repeat forever. An exit at $(1,2)$ is nevertheless safely reachable in one round.

Breadth-first tree search is complete and optimal for minimizing rounds. If a successful escape has finite length $d$, there are only finitely many nodes at depths below $d$, since the branching factor is at most five. Breadth-first tree search therefore reaches a shallowest successful node after finite work, even if other branches continue forever.

It is an optimal search algorithm because every search transition model step costs one round, so minimum depth is exactly the desired minimum number of rounds. The goal test must be applied to the surviving complete-round successor. Here a complete search algorithm guarantees finding an escape when one exists; it need not terminate on every unsolvable instance.

For incompleteness, use the two-row, three-column board from part (c), with exit $(1,2)$. If stay is the first action explored, depth-first tree search follows the repeating state forever. Moving the rabbit down instead survives the round: under legal horizontal-then-vertical movement the fox moves to $(1,0)$ and then $(1,1)$, leaving the rabbit safely at the exit. Thus a one-round escape exists but is never reached in this action order.

For nonoptimality, use an unobstructed one-row board with columns $0,\dots ,6$, initial fox column $0$, initial rabbit column $4$, and exits at columns $3$ and $6$. Moving left once escapes at column $3$ with the fox at column $2$. Moving right twice escapes at column $6$ with successive fox positions $2,4$. A depth-first tree search that explores the latter route first returns two rounds although one suffices. This counterexample supplies an actual returned, suboptimal escape independently of the infinite-branch example.

Ignore the fox and obstacles when estimating the remaining number of rabbit moves. Define the heuristic functionThis is Manhattan distance to the nearest exit, a relaxation heuristic. Assume at least one exit; with none the instance is immediately unsolvable. The estimate is generally nonconstant and is not the perfect escape cost: obstacles can force detours, while pursuit can make an apparently nearby exit unreachable.

To prove it is a consistent heuristic, consider a surviving one-round transition from $(r,f)$ to $(r^{\prime },f^{\prime })$. Let $e^{\prime }$ attain the minimum defining $h(r^{\prime },f^{\prime })$. The triangle inequality for Manhattan distance and the rabbit's move bound giveEvery successful terminal state has $h=0$. This proves consistency with unit round costs; summing the inequality along any successful route also proves that it is an admissible heuristic. Failed transitions need no successor estimate because they are discarded.

Breadth-first tree search remains complete but is not optimal for maximizing the bonus. Completeness depends on the finite branching factor and a finite successful depth, not on the objective used to compare escapes.

Use the one-row, seven-square example from part (e). The one-round escape at column $3$ leaves the fox at column $2$, so its graph distance to the exit, and hence the bonus, is $1$. The two-round escape at column $6$ leaves the fox at column $4$, giving bonus $2$. The earliest successful node therefore has bonus $1$ when bonus $2$ is achievable. Breadth-first tree search orders by rounds rather than terminal graph distance.

Breadth-first tree search is complete and is still not bonus-optimal. Fix any deterministic rule for choosing among equally short fox routes; the completeness argument again uses only the finite branching factor. The unobstructed corridor of part (g) has unique shortest paths, so its fox moves are exactly the same under the new strategy. The one-round bonus is $1$ and the two-round bonus is $2$, proving nonoptimality without any tie-breaking ambiguity.

If there is no route between fox and rabbit, the printed shortest-path rule needs a convention; letting the fox stay supplies a natural extension. The completeness argument is unchanged, and the counterexample above uses only connected squares. When the fox and rabbit initially belong to the same connected component of a graph, the shortest-path pursuit distance bound also makes every surviving branch finite. That additional property does not make the first escape maximize its bonus.

Let $d_t$ be the graph distance between fox and rabbit after round $t$, with $d_0$ their initial graph distance. Initial reachability makes $d_0$ finite, and ordinary moves preserve membership in their common connected component of a graph. After the rabbit's next move, the triangle inequality gives intermediate separation at most $d_t+1$. If that separation is at most two, the fox catches the rabbit that round. Otherwise the fox takes two steps along a shortest path, leavingThus a successful surviving history has at most $d_0-1$ rounds; if it does not escape by then, the next round captures it. The shortest-path pursuit distance bound excludes infinite live branches, even when the rabbit stays. Together with the finite branching factor, it makes the whole relevant search tree finite, so depth-first tree search eventually finds an escape whenever one exists.

For nonoptimality, take the corridor of part (g) and let depth-first tree search try left first. It immediately returns the one-round escape with bonus $1$, whereas trying right twice earns $2$. The decreasing separation proves termination, not optimality of the first returned escape.