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

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.