Как алгоритм минимакса может быть более оптимистичным?

Question

Minimax, похоже, отлично справляется с тем, чтобы не проиграть, но это очень фаталистично, если предположить, что противник не допустит ошибку. Конечно, многие игры решаются на ничью, но нужно играть за «максимально возможное стремление к победе, не рискуя проиграть», даже если нет принудительных побед. То есть, если два дерева с одинаковым (вытянутым) конечным положением, которым придается оптимальное воспроизведение, как можно настроить алгоритм, чтобы предпочесть тот, который, скорее всего, выиграет, если противник сделает субоптимальное движение или сделает противника более вероятно, ускорится?

Используя простой пример Tic-Tac-Toe, более сильный игрок часто стремился устанавливать вилки и тем самым гарантировать победы. Несмотря на то, что противник мог видеть такой трюк и останавливать его заранее, они с большей вероятностью пропустят это, чем если бы вы просто положили два Xs в пустую строку и надеетесь, что они на мгновение забудут, в какую игру они играют. Точно так же сильный игрок будет стремиться начинать в центре или, возможно, в углу, но в простом минимаксном нет никакой причины (так как вы все равно можете заставить ничью) не выбрать краевой квадрат.

Answer 1

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

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

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

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

Answer 2

Как насчет настройки «мин» узлов?

В обычном минимаксном при оценке позиции для противника оценка является минимальной оценкой для каждого из его ходов. Включение некоторого оптимизма (из pax «max» игрока в поиск может быть выполнено с использованием другой функции, чем минимум. Некоторые вещи, которые могут быть опробованы:

-Использование второй худший счет

-при смесь между минимальным и средним (или медианы)

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