Expectiminimax

Expectiminimax
Сорт	Алгоритм поиска
Худший вариант производительности	О ( б м н м ) {\displaystyle {\mathcal {O}}(b^{m}n^{m})} , где - число различных бросков игральных костей н {\displaystyle n}
Лучшая производительность	О ( б м ) {\displaystyle {\mathcal {O}}(b^{m})} , в случае, если все броски костей известны заранее

Вариация алгоритма минимакса

Алгоритм expectiminimax является разновидностью алгоритма minimax , используемого в системах искусственного интеллекта , которые играют в игры с нулевой суммой для двух игроков , такие как нарды , в которых результат зависит от комбинации мастерства игрока и случайных элементов, таких как броски костей. В дополнение к узлам «min» и «max» традиционного дерева minimax, этот вариант имеет узлы «chance» (« ход по природе »), которые принимают ожидаемое значение случайного события. ^[1] В терминах теории игр дерево expectiminimax является игровым деревом игры в экстенсивной форме с идеальной , но неполной информацией .

В традиционном методе минимакса уровни дерева чередуются от макс. до мин., пока не будет достигнут предел глубины дерева. В дереве ожиданий минимакса узлы «шанс» чередуются с узлами макс. и мин. Вместо того, чтобы брать макс. или мин. значений полезности своих потомков, узлы шанса берут средневзвешенное значение, причем вес является вероятностью достижения потомка. ^[1]

Чередование зависит от игры. Каждый «ход» игры оценивается как узел «макс» (представляющий ход игрока ИИ), узел «мин» (представляющий потенциально оптимальный ход противника) или узел «шанс» (представляющий случайный эффект или игрока). ^[1]

Например, рассмотрим игру, в которой каждый раунд состоит из одного броска кубика, а затем решений, принимаемых сначала игроком ИИ, а затем другим интеллектуальным противником. Порядок узлов в этой игре будет чередоваться между «шанс», «макс» и затем «мин». ^[1]

Псевдокод

Алгоритм expectiminimax является вариантом алгоритма minimax и был впервые предложен Дональдом Мичи в 1966 году. ^[2] Его псевдокод приведён ниже.

функция expectiminimax(node, depth) если node является конечным узлом или depth = 0 возвращает эвристическое значение node , если противник должен играть в node // Возвращаемое значение дочернего узла с минимальным значением пусть α := +∞ для каждого потомка узла α := min(α, expectiminimax(child, depth-1)) иначе если мы будем играть на узле // Возвращаемое значение дочернего узла с максимальным значением пусть α := -∞ для каждого потомка узла α := max(α, expectiminimax(child, depth-1)) иначе, если случайное событие в узле // Возвращает средневзвешенное значение всех значений дочерних узлов пусть α := 0 для каждого потомка узла α := α + (Вероятность[ребенок] × ожиданиеминимакс(ребенок, глубина-1)) возвращение α

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

Поиск Expectimax

Поиск Expectimax — это вариант, описанный в книге «Универсальный искусственный интеллект: последовательные решения, основанные на алгоритмической вероятности» (2005) Тома Эверитта и Маркуса Хаттера .

Альфа-бета обрезка

Брюс Баллард был первым, кто разработал технику, называемую *-minimax, которая позволяет выполнять альфа-бета-обрезку в деревьях expectiminimax. ^[3]^[4] Проблема с интеграцией альфа-бета-обрезки в алгоритм expectiminimax заключается в том, что оценки потомков узла-случайности могут превышать альфа- или бета-границу его родителя, даже если взвешенное значение каждого потомка не превышает ее. Однако можно ограничить оценки потомков узла-случайности и, следовательно, ограничить оценку узла CHANCE.

Если стандартный итеративный поиск собирается оценить th потомка случайного узла с равновероятными потомками, этот поиск вычислил оценки для дочерних узлов с 1 по . Предполагая наименьшую возможную оценку и наибольшую возможную оценку для каждого неисследованного потомка, границы оценки случайного узла следующие: $я$ $N$ $v_{1},v_{2},\ldots,v_{i-1}$ $i-1$ $L$ $U$

${\text{score}}\leq {\frac {1}{n}}\left((v_{1}+\ldots +v_{i-1})+v_{i}+U\times (ni)\right)$

${\text{score}}\geq {\frac {1}{n}}\left((v_{1}+\ldots +v_{i-1})+v_{i}+L\times (ni)\right)$

Если при оценке узла шанса заданы альфа и/или бета-границы, эти границы можно использовать для прекращения поиска потомка th. Вышеприведенные уравнения можно переставить, чтобы найти новое значение альфа и бета, которое остановит поиск, если это приведет к тому, что узел шанса превысит свои собственные альфа и бета-границы: $я$

$\alpha _{i}=N\times \alpha -\left(v_{1}+\ldots +v_{i-1}\right)+U\times (ni)$

$\beta _{i}=N\times \beta -\left(v_{1}+\ldots +v_{i-1}\right)+L\times (ni)$

Псевдокод для расширения expectiminimax с отказоустойчивым альфа-бета-отсечением таким образом выглядит следующим образом :

функция *-minimax(node, depth, α, β) если узел является конечным узлом или глубина = 0 возвращает эвристическое значение узла если узел является максимальным или минимальным узлом возвращает минимаксное значение узла пусть N = numSuccessors(node) // Вычисление α, β для детей пусть A = N * (α - U) + U пусть B = N * (β - L) + L пусть сумма = 0 для каждого потомка узла // Ограничить дочерние элементы α, β допустимым диапазоном пусть AX = max(A, L) пусть BX = min(B, U) // Поиск потомка с новыми предельными значениями пусть оценка = *-минимакс(ребенок, глубина - 1, AX, BX) // Проверка условий отсечки α, β если оценка <= A, вернуть α , если оценка >= B , вернуть β сумма += оценка // Настроить α, β для следующего потомка А += У - в В += Л - в // Отсечки не произошло, вернуть счет сумма возврата / N

Эта техника является одним из семейства вариантов алгоритмов, которые могут ограничить поиск узла CHANCE и его потомков на основе сбора нижних и верхних границ потомков во время поиска. Другие техники, которые могут предложить преимущества производительности, включают зондирование каждого потомка с помощью эвристики для установления минимума или максимума перед выполнением полного поиска по каждому потомку и т. д.

Смотрите также

Ссылки

^ abcd Рассел, Стюарт Джонатан; Норвиг, Питер; Дэвис, Эрнест (2010). Искусственный интеллект: современный подход . Prentice Hall. стр. 177– 178. ISBN 978-0-13-604259-4.
^ Мичи, Д. (1966). «Игровые автоматы и игровые автоматы для обучения». Достижения в программировании и нечисловых вычислениях . С. 183–200 . doi :10.1016/B978-0-08-011356-2.50011-2. ISBN 978-0-08-011356-2.
^ Баллард, Брюс В. (сентябрь 1983 г.). «Процедура поиска *-минимакс для деревьев, содержащих случайные узлы». Искусственный интеллект . 21 (3): 327– 350. doi :10.1016/S0004-3702(83)80015-0.
^ Хаук, Томас; Буро, Майкл; Шеффер, Джонатан (2006). «Повторное открытие *-Minimax Search». Компьютеры и игры . Конспект лекций по информатике. Том 3846. С. 35–50 . doi :10.1007/11674399_3. ISBN 978-3-540-32488-1.

[RussellNorvig2009-1] Рассел, Стюарт Джонатан; Норвиг, Питер; Дэвис, Эрнест (2010). Искусственный интеллект: современный подход . Prentice Hall. стр. 177– 178. ISBN 978-0-13-604259-4.

[2] Мичи, Д. (1966). «Игровые автоматы и игровые автоматы для обучения». Достижения в программировании и нечисловых вычислениях . С. 183–200 . doi :10.1016/B978-0-08-011356-2.50011-2. ISBN 978-0-08-011356-2.

[3] Баллард, Брюс В. (сентябрь 1983 г.). «Процедура поиска *-минимакс для деревьев, содержащих случайные узлы». Искусственный интеллект . 21 (3): 327– 350. doi :10.1016/S0004-3702(83)80015-0.

[4] Хаук, Томас; Буро, Майкл; Шеффер, Джонатан (2006). «Повторное открытие *-Minimax Search». Компьютеры и игры . Конспект лекций по информатике. Том 3846. С. 35–50 . doi :10.1007/11674399_3. ISBN 978-3-540-32488-1.