Введение
Алгоритм expectiminimax — это вариация алгоритма minimax, предназначенная для использования в системах искусственного интеллекта, играющих в двухместные игры с нулевой суммой, такие как нарды, где исход зависит от сочетания мастерства игрока и случайных факторов, таких как броски костей. В дополнение к узлам "min" и "max" традиционного дерева minimax, этот вариант имеет узлы "шанс" ("ход природы"), которые вычисляют ожидаемое значение случайного события. В терминах теории игр, дерево expectiminimax представляет собой дерево игры в форме расширенной игры с совершенной, но неполной информацией. В традиционном методе minimax уровни дерева чередуются между max и min до достижения заданной глубины. В дереве expectiminimax узлы "шанс" чередуются с узлами max и min. Вместо выбора максимального или минимального значения полезности у дочерних узлов, узлы "шанс" вычисляют средневзвешенное значение, где вес соответствует вероятности достижения этого дочернего узла. Его псевдокод приведен ниже.
if node is a terminal node or depth = 0
return the heuristic value of node
if the adversary is to play at node
// Return value of minimum valued child node
let α := +∞
foreach child of node
α := min(α, expectiminimax(child, depth 1))
else if we are to play at node
// Return value of maximum valued child node
let α := ∞
foreach child of node
α := max(α, expectiminimax(child, depth 1))
else if random event at node
// Return weighted average of all child nodes' values
let α := 0
foreach child of node
α := α + (Probability[child] × expectiminimax(child, depth 1))
return α
Note that for random nodes, there must be a known probability of reaching each child. (For most games of chance, child nodes will be equally weighted, which means the return value can simply be the average of all child values.)
function expectiminimax(node, depth)
if node is a terminal node or depth = 0
return the heuristic value of node
if the adversary is to play at node
// Return value of minimum valued child node
let α := +∞
foreach child of node
α := min(α, expectiminimax(child, depth - 1))
else if we are to play at node
// Return value of maximum valued child node
let α := -∞
foreach child of node
α := max(α, expectiminimax(child, depth - 1))
else if random event at node
// Return weighted average of all child nodes' values
let α := 0
foreach child of node
α := α + (Probability[child] × expectiminimax(child, depth - 1))
return α
if node is a terminal node or depth = 0
return the heuristic value of node
if the adversary is to play at node
// Return value of minimum valued child node
let α := +∞
foreach child of node
α := min(α, expectiminimax(child, depth 1))
else if we are to play at node
// Return value of maximum valued child node
let α := ∞
foreach child of node
α := max(α, expectiminimax(child, depth 1))
else if random event at node
// Return weighted average of all child nodes' values
let α := 0
foreach child of node
α := α + (Probability[child] × expectiminimax(child, depth 1))
return α
Note that for random nodes, there must be a known probability of reaching each child. (For most games of chance, child nodes will be equally weighted, which means the return value can simply be the average of all child values.)
Обратите внимание, что для случайных узлов должна быть известна вероятность достижения каждого дочернего узла. (Для большинства игр со случайностью дочерние узлы будут иметь равные веса, что означает, что возвращаемое значение может быть просто средним значением всех дочерних узлов.)
if node is a terminal node or depth = 0
return the heuristic value of node
if the adversary is to play at node
// Return value of minimum valued child node
let α := +∞
foreach child of node
α := min(α, expectiminimax(child, depth 1))
else if we are to play at node
// Return value of maximum valued child node
let α := ∞
foreach child of node
α := max(α, expectiminimax(child, depth 1))
else if random event at node
// Return weighted average of all child nodes' values
let α := 0
foreach child of node
α := α + (Probability[child] × expectiminimax(child, depth 1))
return α
Note that for random nodes, there must be a known probability of reaching each child. (For most games of chance, child nodes will be equally weighted, which means the return value can simply be the average of all child values.)
Поиск Expectimax
Поиск Expectimax — это вариант, описанный в книге «Универсальный искусственный интеллект: последовательные решения на основе алгоритмической вероятности» (2005) Тома Эверитта и Маркуса Хаттера.