Минимакс использует уже оцененное дерево.В чем мой изъян?

Question

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

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

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

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

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

Answer 1

Я думаю, чего вам здесь не хватает, так это как минимакс работает.Minimax перечисляет все возможности на заданной глубине D, затем присваивает оценку узлам (состояниям игры) на D и, двигаясь обратно вверх по дереву, возвращает МАКСИМАЛЬНЫЙ или МИНИМАЛЬНЫЙ узел на каждой глубине в зависимости от того, являюсь ли я максимизирующим игроком или минимизирующим игроком.

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

Answer 2

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