Для получения точных решений в играх используется алгоритм минимакса (см. листинг 6.1), а для условного планирования обычно применяются две его модификации. Во-первых, узлы МАХ и MIN могут быть преобразованы в узлы OR и AND. Интуитивно кажется очевидным, что в плане требуется предпринимать некоторые действия в каждом достигнутом в нем состоянии, но должны учитываться все результаты предпринятого действия. Во-вторых, алгоритм должен возвращать условный план, а не просто отдельный ход. В узле OR план состоит в выборе действия, за которым следует то, что должно произойти. А в узле AND план представляет собой вложенный ряд этапов "if—then—else" с определением субпланов для каждого результата; проверки в этих этапах возвращают полные описания состояния.

Формально говоря, определенное нами пространство поиска представляет собой граф AND-OR. В главе 7 графы AND—OR рассматривались в контексте пропозиционального вывода на основе хорновских выражений, а в этой главе ветвями являются действия, а не этапы логического вывода, но алгоритм остается тем же самым. В листинге 12.4 приведен рекурсивный алгоритм поиска в глубину, предназначенный для поиска в графе AND—OR.

Одной из ключевых особенностей этого алгоритма является тот способ, с помощью которого он справляется с циклами, часто возникающими в задачах недетерминированного планирования (например, если какое-то действие иногда не имеет результата или если может быть исправлен нежелательный результат). Если текущее состояние идентично одному из состояний в пути от корня, то алгоритм выполняет возврат с индикатором неудачи. Это не означает, что нет решения, достижимого из текущего состояния; просто такая ситуация свидетельствует о том, что если есть нециклическое решение, оно должно быть достижимым из более раннего воплощения текущего состояния, поэтому его новое воплощение может быть отброшено. С помощью этой проверки можно гарантировать, что алгоритм завершит свою работу в любом конечном пространстве состояний, поскольку каждый путь должен достигнуть цели, тупика или повторяющегося состояния. Обратите внимание на то, что в алгоритме не осуществляется проверка, не является ли текущее состояние повторением какого-то состояния в каком-то другом пути от корня; этот вопрос исследуется в упр. 12.15.