= Solution
Include all four positions and a turn marker:
$$
s=(p,q,z_1,z_2,\tau),\qquad\tau\in\{\mathrm{R},\mathrm{M}\}.
$$
The initial marker is $\mathrm{R}$. There are at most $2n^8$ such states before terminal compression. The two robots form one maximizing team in the <adversarial search> representation. At an R state their actions are joint legal moves, including waiting, with deterministic successor positions and marker M. At an M state the monster outcome is a pair of legal cardinal moves, producing marker R.
Check termination initially and after each simultaneous pair of moves. A state is a failure if $\{p,q\}\cap\{z_1,z_2\}\ne\varnothing$. Otherwise it is a success if $p=q$. \b[Collision takes priority over meeting], so meeting on an occupied room fails. A safe meeting ends immediately, before a further monster response. Room swaps without a shared position at a checked boundary are neither capture nor meeting.
The monsters move randomly, so their nodes are \b[chance nodes], not minimizing decisions. Under independent uniform legal moves, if monster $j$ currently has $d_j$ available destinations, each joint outcome has <probability> $1/(d_1d_2)$. If several commands produce the same state, add their <probabilities>. This specifies a stochastic <game tree>, equivalently a <Markov decision process> for the robot team. Uniform legal moves and independent monsters are explicit boundary/joint-law conventions; uniform attempted directions with blocked moves staying put is another convention, with different boundary <transition probabilities> but the same search method. For the one-cell grid, a monster with no legal move stays; all four initial positions then coincide and the instance immediately fails.
Back to article page
