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

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.