Главная arrow книги arrow Копия Глава 6. Поиск в условиях противодействия arrow Игры, которые включают элемент случайности
Игры, которые включают элемент случайности

Следующий этап состоит в том, чтобы понять, как следует принимать правильные решения. Безусловно, и в этом случае требуется найти такой ход, который ведет к наилучшей позиции. Однако результирующие позиции не имеют определенных минимаксных значений. Вместо этого существует возможность вычислить только ожидаемое значение, в котором ожидаемый результат устанавливается с учетом всех возможных выпадений жребия, которые могут произойти. Это приводит к обобщению минимаксного значения для детерминированных игр до ожидаемого минимаксного значения (expectiminimax value) для игр с узлами жеребьевки. Терминальные узлы и узлы МАХ и MIN (для которых известны результаты жеребьевки) применяются точно так же, как и прежде, а узлы жеребьевки оцениваются путем получения взвешенного среднего значений, полученных в результате всех возможных выпадений жребия, т.е. следующим образом:

где функция определения преемника для узла жеребьевки п просто дополняет состояние п каждым возможным выпадением жребия для формирования каждого преемника s, a P{s) — вероятность, с которой происходит выпадение жребия. Результаты вычисления этих уравнений могут резервироваться рекурсивно во всех узлах вплоть до корня дерева точно так же, как и в минимаксном алгоритме. Оставляем читателю проработку всех деталей этого алгоритма в качестве упражнения.