Понимание определения минимаксного значения

Question

В третьем издании Рассел и Норвиг, они дают следующее определение минимаксного значения узла в игровом дереве (с нулевой суммой, совершенная информация, детерминированный)

Минимаксное значениеузел - это утилита (для МАКСА), которая находится в соответствующем состоянии, , предполагая, что оба игрока играют оптимально оттуда до конца игры.

Единственное, чточто при настройке игры полезность узла определяется только для терминальных узлов, так как же следует понимать полезность общего узла?Благодарю.

Answer 1

Каждый узел должен представлять игровое состояние, учитывая набор действий каждого игрока.

Утилита должна быть определена для каждого игрового состояния и, следовательно, для каждого узла.Он должен представлять, насколько благоприятно игровое состояние для игрока.

Узлы минимаксного дерева вычисляются для каждого следующего слоя .То есть я не оцениваю состояние игры сразу после своего хода, но вместо этого после каждого раза, когда мой противник (и) делает ход.

Для игры с двумя игроками:

У меня есть X возможных ходов.

Для каждого из моих X возможных ходов существует игровое состояние.Нам не нужна утилита этих игровых состояний.

Для каждого из этих X игровых состояний у моего оппонента есть Y возможных ходов.

Для каждого из этих Y возможных ходов существует другое игровое состояние.Нам нужны утилиты этих игровых состояний.

Answer 2

Утилита определена для нетерминальных узлов.Дело в том, что для терминальных узлов полезность оценивается некоторой внешней эвристикой (которую они называют UTILITY), но для нетерминальных узлов полезность вычисляется по минимаксному алгоритму.Минимаксное значение (или полезность) нетерминального узла - это либо максимум, либо минимум минимаксных значений его дочерних элементов (в зависимости от того, чье это движение).Минимаксное значение корня будет полезностью результата, к которому вы придете, если и вы, и ваш оппонент с этого момента сделаете оптимальные ходы.

Есть отработанный пример здесь это должно прояснить ситуацию.