Expectiminimax алгоритм является изменением минимаксного алгоритма для использования в искусственном интеллекте системах , которые играют два-плеер с нулевой суммой игры, такие как нарды , в которых результат зависит от сочетания мастерства и игрока случайных элементов , таких как кости рулоны . В дополнение к узлам «min» и «max» традиционного минимаксного дерева этот вариант имеет узлы «случайности» (« движение по природе »), которые принимают ожидаемое значение возникновения случайного события. [1] В теории игр терминов, expectiminimax дерево игры дерево из развернутой формы игры изСовершенная , но неполная информация .
Класс | Алгоритм поиска |
---|---|
Наихудшая производительность | , где количество различных бросков костей |
Лучшая производительность | , если все броски костей известны заранее |
В традиционном минимаксном методе уровни дерева чередуются от максимального к минимальному, пока не будет достигнута граница глубины дерева. В дереве expectiminimax «случайные» узлы чередуются с максимальными и минимальными узлами. Вместо того, чтобы брать максимальные или минимальные значения полезности своих дочерних узлов, случайные узлы принимают средневзвешенное значение, причем весовой коэффициент является вероятностью достижения дочернего элемента. [1]
Чередование зависит от игры. Каждый «ход» игры оценивается как «максимальный» узел (представляющий ход ИИ-игрока), «минимальный» узел (представляющий ход потенциально оптимального оппонента) или узел «шанс» (представляющий случайный эффект или игрок). [1]
Например, рассмотрим игру, в которой каждый раунд состоит из одного броска кубика, а затем решения принимаются сначала ИИ-игроком, а затем другим умным противником. Порядок узлов в этой игре будет чередоваться: «шанс», «максимум» и затем «минимум». [1]
Псевдокод
Алгоритм expectiminimax является вариантом алгоритма минимакса и был впервые предложен Дональдом Мичи в 1966 году. [2] Его псевдокод приведен ниже.
функция expectiminimax (узел, глубина), если узел является конечным узлом или глубина = 0, возвращает эвристическое значение узла, если противник должен играть на узле // Возвращаемое значение дочернего узла с минимальным значением пусть α: = + ∞ для каждого потомка узла α: = min (α, expectiminimax (ребенок, глубина-1)) иначе, если мы будем играть на узле // Возвращаемое значение дочернего узла с максимальным значением пусть α: = -∞ для каждого потомка узла α: = max (α, expectiminimax (ребенок, глубина-1)) иначе, если случайное событие на узле // Возвращаем средневзвешенное значение значений всех дочерних узлов пусть α: = 0 для каждого потомка узла α: = α + (Вероятность [ребенок] × ожидаемый минимум (ребенок, глубина-1)) вернуть α
Обратите внимание, что для случайных узлов должна быть известная вероятность достижения каждого дочернего элемента. (Для большинства азартных игр дочерние узлы будут иметь одинаковый вес, что означает, что возвращаемое значение может быть просто средним всех дочерних значений.)