Алгоритмы игрового дерева и прогрессивное углубление: как аппроксимировать ответ, не доходя до листовых узлов?

Question

Я только что увидел эту лекцию MIT по игровым деревьям и алгоритмам MinMax, где обсуждалась обрезка альфа-бета и прогрессивное углубление.
https://www.youtube.com/watch?v=STjW3eH0Cik

Так что если я правильно понял прогрессирующее углубление, когда вы пытаетесь приблизить ответ на каждом уровне и попытаться углубиться в стороне листьев узлов в зависимости от срока вы имеете для вашего переезда. Важно иметь какой-то ответ в любой момент времени. Теперь, в 36:22 Профессор обсуждает случай, когда нам не хватает времени, и мы шли только до уровня (d-1), где d - глубина дерева. И затем он также предлагает, чтобы мы могли иметь временный ответ на каждом уровне по мере того, как мы спускаемся, поскольку мы должны иметь приблизительный ответ в любой момент времени.

Мой вопрос в том, как мы можем получить любой ответ, не обращаясь к узлам листа, потому что только на листовых узлах мы можем заключить, кто может выиграть игру. Подумайте об этом для игры tic-tac-toe. На (d-1) -м уровне нам не хватает информации, чтобы решить, будет ли эта серия движений до тех пор, пока этот узел в (d-1) не выиграет меня или не потеряет меня. На более высоких уровнях говорят (d-3), это еще больше размывается! Все возможно, когда мы идем вниз. Не так ли? Итак, если алгоритм решает вычислить до (d-1) -го уровня, тогда все эти параметры пути равны! Ничто не гарантирует победу, и ничто не гарантирует потерю на уровне (d-1), потому что, если я правильно понимаю победы и потери, можно рассчитать только на листовых узлах. Это так верно, особенно в чистом алгоритме MinMax.

Итак, как именно мы будем иметь «приблизительный ответ» на уровне (d-1) или сказать (d-5) уровень?

Answer 1

Я попытаюсь объяснить, что хорошо.
Контекст и факторы прогрессивного углубления
Мне нужно знать, что в реальной игре время, которое вы будете использовать, ограничено !!! (потому что пользовательский опыт и другие проблемы взаимодействия с человеком и компьютером или проблема/дизайн в вашей игре).
У вас есть игровое дерево и используйте разностный алгоритм для оптимизации, который перемещает все дерево. Но есть три проблемы:

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

Ответ всей проблемы - прогрессивное углубление: на текущем уровне вы вычисляете ответ и пытаетесь передать следующий уровень в дереве; но если у вас нет времени, вы готовы ответить на предыдущий уровень и получить его как ответ
Ответьте на свой вопрос
вы можете себе представить, что текущий уровень в вашем дереве - «последний уровень» (вы предположим) в игровом дереве, но вы получите лучшее решение, если вы перейдете на следующий уровень в дереве, а затем, если вы сможете перейти на следующий уровень: идите прямо сейчас! но вам нужно вычислить оптимальный ответ в текущем игровом дереве, потому что это «конечный уровень» в игровом дереве в качестве страхового полиса, если вы не закончите вычисление лучшего ответа на следующем уровне по временному ограничению.