минимакс: что происходит, если мин играет не оптимально

Question

В описании минимаксного алгоритма говорится, что оба игрока должны играть оптимально, чтобы алгоритм был оптимальным. Интуитивно понятно. Но если кто-то конкретизирует или доказывает, что происходит, если мин играет неоптимально?

ТНХ

Answer 1

Определение «оптимального» заключается в том, что вы играете так, чтобы минимизировать «оценку» (или то, что вы измеряете) оптимального ответа оппонента, который определяется игрой, которая минимизирует оценку вашего оптимального ответа и т. .

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

Один из способов выяснить, что является оптимальным, - применить грубую силу ко всему дереву игры. Для менее чем тривиальных задач вы можете использовать альфа-бета-поиск, который гарантирует оптимальный поиск без необходимости поиска по всему дереву. Если ваше дерево все еще слишком сложное, вам нужна эвристика, которая оценивает оценку «позиции» и останавливается на определенной глубине.

Это было понятно?

Answer 2

У меня были проблемы с этим точным вопросом.

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

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

С альфа-бета - допустим, последовательность проигрышных ходов, сопровождаемых убийственным ходом, фактически находится в дереве - но в этом случае альфа и бета действуют как оконный фильтр «a

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

повтор полоскания.