Что я не понимаю в алгоритме минимакса

Question

У меня вопрос по поводу минимаксного алгоритма.

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

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

Так как, если другой игрок делает другой ход, мой шанс на выигрыш намного меньше ...

Извините, мне трудно выразить, что я имею в виду по этому вопросу. Но как я тут ошибаюсь?

Answer 1

Обычный способ решить эту проблему - вернуться назад с нижних слоев дерева. Давайте сначала проверим самые нижние четыре листа (часть 10-20-15-20). Игрок 2 может выбрать из них, если игра когда-либо попадет туда, поэтому P2 выберет меньшие , т.е. 10 и 15. Затем мы можем обрезать 10-20-15-20 ветвей дерева и замените их на 10 (для самых левых двух листов) и 15 (для самых правых двух). Точно так же мы можем обрезать пару -100 - 50 в середине и заменить их на -100 (не на 50, как вы, потому что на этом уровне ход игрока 2, и он выберет меньший результат), -200 - - 100 пар с -200 и тд. Так что, для меня, похоже, вы берете максимум в каждой точке ветвления вместо чередования между максимумом и минимумом.

Answer 2

алгоритм предполагает, что и вы, и второй игрок хотят выиграть, и всегда будут выбирать лучший ход. таким образом, в дереве вопроса - как я уже сказал в комментарии, последний ход (делает второй игрок) слева, а не справа. это приводит к тому, что целое правильное поддерево становится недостойным для первого игрока, и алгоритм minmax выберет следующий путь (а не как описано в вопросе): left->left->right->left

это верно, алгоритм «дает вам меньше шансов на выигрыш», это из-за того, что есть второй игрок, который тоже хочет выиграть!

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

Answer 3

Вы должны чередовать взятие минимума и максимума.Если вы хотите взять 50, то есть максимум 30 и 50, тогда вы должны были выбрать -100 на один уровень ниже с правой стороны и т. Д. Вот почему алгоритм называется минимаксным.