Поиск лучшего узла ( BNS ), первоначально известный как поиск нечеткого дерева игры , представляет собой алгоритм минимаксного поиска , разработанный в 2011 году. Идея состоит в том, что знание о том, что одно поддерево относительно лучше, чем некоторые (или все) другие (и), могут распространяться раньше, чем абсолютное значение минимакса для этого поддерева. Затем повторяющийся поиск сужается до тех пор, пока конкретный узел не окажется относительно лучшим.
Сначала необходимо сделать начальное предположение о минимаксном значении, возможно, на основе статистической информации, полученной в другом месте. Затем BNS вызывает поиск, который сообщает, меньше или больше минимакс поддерева , чем предположение. Он изменяет предполагаемое значение до тех пор, пока альфа и бета не станут достаточно близкими или только одно поддерево не позволит минимаксное значение больше, чем текущее предположение. Эти результаты аналогичны, соответственно, эвристическим стратегиям поиска «доказать лучшее» и «опровергнуть остальные».
Результатом поиска является узел (перемещение), поддерево которого содержит минимаксное значение и границу этого значения, но не само минимаксное значение. [1] Эксперименты со случайными деревьями показали, что это самый эффективный минимаксный алгоритм. [ нужна ссылка ]
Приведенную выше функцию nextGuess по умолчанию можно заменить на функцию, использующую статистическую информацию для повышения производительности.
Поиск по дереву с помощью Murphy Sampling [2] является расширением поиска лучших узлов для недетерминированных настроек.