Ожидамиминимакс

Ожидамиминимакс
Сорт	Алгоритм поиска
Худшая производительность	, где это количество различных бросков игральной кости
Лучшая производительность	, если все броски кубиков известны заранее

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

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

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

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

Псевдокод

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

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 α

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

Ожидаемый поиск

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

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

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

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

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

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

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

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

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

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

function *-minimax(node, depth, α, β)
    if node is a terminal node or depth = 0
        return the heuristic value of node
    if node is a max or min node
        return the minimax value of the node
    let N = numSuccessors(node)
    // Compute α, β for children
    let A = N * (α - U) + U
    let B = N * (β - L) + L
    let sum = 0
    foreach child of node
        // Limit child α, β to a valid range
        let AX = max(A, L)
        let BX = min(B, U)
        // Search the child with new cutoff values
        let score = *-minimax(child, depth - 1, AX, BX)
        // Check for α, β cutoff conditions
        if score <= A
            return α
        if score >= B
            return β
        sum += score
        // Adjust α, β for the next child
        A += U - v
        B += L - v
    // No cutoff occurred, return score
    return sum / N

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

См. также

Ссылки

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

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

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

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

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

[1]

[2]

[3]

[4]