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

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.