Minimax использование уже оценен дерево. Где мой недостаток?

Question

Я только начал пытаться использовать алгоритм minimax/negamax, и я придумал идею, которая звучит хорошо для меня, но поскольку никто ее не использует, это может быть ошибочная логика.

Почему бы нам не сделать это:

Создайте три с глубиной = х, выяснить, какие перемещения сделать, и ждать нашего противника. После того, как он сделал свой ход, мы можем просто взять поддерево движений, которые мы уже оценили, и продолжать строить его глубже при использовании старых узлов. Мы могли бы использовать уже оцененные значения узлов и взвешивать их с новыми значениями из новых более глубоких узлов.

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

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

Answer 1

Я думаю, что вам здесь не хватает как минимаксные работы. Minimax перечисляет все возможности для заданной глубины D, затем присваивает оценку узлам (состояниям игры) в D и перемещает назад дерево, возвращает MAX или MIN узел на каждой глубине в зависимости от того, является ли я максимизацией игрока или минимизирующего игрока.

Ваше предложение сделать это сверху вниз означает, что вам нужно назначить оценку узлам на более мелкой глубине, что приведет к более низкой оценке.

Answer 2

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