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

Question

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

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

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

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

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

Answer 1

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

Answer 2

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

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