= Solution
The <game tree> alternates \b[MAX nodes for joint robot choices and CHANCE nodes for joint monster outcomes]. An interior MAX node has at most $25$ children; an interior CHANCE node at most $4^2=16$. A terminal safe meeting has <utility> one and capture has <utility> zero. With no specified preference for speed, the objective is to maximize the <probability> of eventual safe meeting.
Use \b[<expectimax>]: maximize at MAX nodes and take the <expected value> at CHANCE nodes. For nonterminal states, its finite-horizon backup is
$$
V_{t+1}(s)=
\begin{cases}
\displaystyle\max_a V_t(T(s,a)),&\tau=\mathrm R,\\[3pt]
\displaystyle\sum_{s'}P(s'\mid s)V_t(s'),&\tau=\mathrm M.
\end{cases}
$$
Here the horizon counts half-turns, terminal values stay fixed at zero or one, and $V_0$ is zero at nonterminal states. This computes the best chance of success within the horizon. Maximizing the worst monster outcome would solve a different problem from the stipulated random movement.
Because waiting and movement cycles can repeat states, the infinite <game tree> need not terminate. For the unbounded objective, use <value iteration> on the finite state <graph>, starting from terminal-success indicators as above: $V_t$ increases to the optimal eventual-success <probability>. A reachability-policy method or sufficiently long finite-horizon policies can extract the actions; arbitrary tie choices in the limiting equations must not select a policy that waits forever instead of realizing the value. Alternatively impose an explicit finite horizon and use depth-limited <expectimax>, stating that changed objective. No method guarantees success with <probability> one from every initial configuration.
Back to article page
