В Russell and Norvig, третьем издании, они дают следующее определение минимаксного значения узла в дереве игры (нулевая сумма, полная информация, детерминированное).
Минимаксное значение узла — это полезность (для MAX) нахождения в соответствующем состоянии, предполагая, что оба игрока играют оптимально оттуда и до конца игры.
Единственное, что в их настройке игры полезность узла определяется только для терминальных узлов, так как же следует понимать полезность общего узла? Спасибо.
Утилита определена для нетерминальных узлов. Дело в том, что для терминальных узлов полезность оценивается некоторой внешней эвристикой (которую они называют ПОЛЕЗНОСТЬЮ), а для нетерминальных узлов полезность вычисляется по минимаксному алгоритму. Минимаксное значение (или полезность) нетерминального узла равно максимуму или минимуму минимаксных значений его потомков (в зависимости от того, чей это ход). Минимаксное значение корня будет полезностью результата, к которому вы придете, если и вы, и ваш противник будут делать оптимальные ходы с этого момента.
здесь есть проработанный пример, который должен прояснить ситуацию.
Каждый узел должен представлять состояние игры с заданным набором действий каждого игрока.
Полезность должна быть определена для каждого игрового состояния и, следовательно, для каждого узла. Он должен отображать, насколько благоприятно состояние игры для игрока.
Узлы минимаксного дерева вычисляются каждый второй слой. То есть я оцениваю состояние игры не сразу после своего хода, а после каждого хода, который делают мои противники.
Для игры вдвоем:
У меня есть Х возможных ходов.
Для каждого из моих X возможных ходов есть состояние игры. Нам не нужна полезность этих игровых состояний.
Для каждого из этих X игровых состояний у моего противника есть Y возможных ходов.
Для каждого из этих Y возможных ходов существует другое состояние игры. Нам нужны утилиты этих игровых состояний.
