Лучший поиск узлов

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

Сначала необходимо сделать первоначальное предположение о минимаксном значении, возможно, на основе статистической информации, полученной где-то еще. Затем BNS вызывает поиск, который определяет, меньше или больше минимакс поддерева предполагаемого значения. Он изменяет предполагаемое значение до тех пор, пока альфа и бета не окажутся достаточно близки или только одно поддерево не позволит минимаксному значению превышать текущее предположение. Эти результаты аналогичны соответственно стратегиям эвристического поиска «доказать лучшее» и «опровергнуть остальное».

Результатом поиска является узел (перемещение), поддерево которого содержит минимаксное значение и границу этого значения, но не само минимаксное значение. ^{[ 1 ]} Эксперименты со случайными деревьями показывают, что это наиболее эффективный минимаксный алгоритм. ^{[ нужна ссылка ]}

Псевдокод

function nextGuess(α, β, subtreeCount) is
    return α + (β − α) × (subtreeCount − 1) / subtreeCount


function bns(node, α, β) is
    subtreeCount := number of children of node

    do
        test := nextGuess(α, β, subtreeCount)
        betterCount := 0
        for each child of node do
            bestVal := −alphabeta(child, −test, −(test − 1))
            if bestVal ≥ test then
                betterCount := betterCount + 1
                bestNode := child
        (update number of sub-trees that exceeds separation test value)
        (update alpha-beta range)
    while not (β − α < 2 or betterCount = 1)

    return bestNode

по умолчанию Приведенную выше функцию nextGuess можно заменить функцией, которая использует статистическую информацию для повышения производительности.

Обобщение

Поиск деревьев с помощью выборки Мерфи ^{[ 2 ]} является расширением поиска лучшего узла для недетерминированных настроек.

Внешние ссылки

нечеткие минимаксные алгоритмы

Ссылки

^ Рутко, Дмитрий (2011). «Нечеткий алгоритм поиска в дереве игры со статистической и аналитической оценкой» (PDF) . Научные труды, Латвийский университет . 770 : 90–111 . Проверено 5 ноября 2022 г.
^ Кауфманн, Эмили; Кулен, Воутер; Гаривье, Орельен (2018). «Последовательный тест наименьшего среднего: от выборки Томпсона до выборки Мерфи». arXiv : 1806.00973 [ stat.ML ].

[1] Рутко, Дмитрий (2011). «Нечеткий алгоритм поиска в дереве игры со статистической и аналитической оценкой» (PDF) . Научные труды, Латвийский университет . 770 : 90–111 . Проверено 5 ноября 2022 г.

[2] Кауфманн, Эмили; Кулен, Воутер; Гаривье, Орельен (2018). «Последовательный тест наименьшего среднего: от выборки Томпсона до выборки Мерфи». arXiv : 1806.00973 [ stat.ML ].

[ 1 ]

[ 2 ]