Деревья МинМакс - когда Мин может выиграть в два шага

Итак, я экспериментировал с деревьями minmax, чтобы создать простого компьютерного игрока в настольной игре для двух человек. Я понимаю основы алгоритма, но есть случай, который ускользает от моего мозга, наполненного индейкой ... что происходит, когда MIN может выиграть в два этапа?

Например, предположим, что игра типа connect4 / tic-tac-toe, в которой только один из двух игроков может владеть квадратом. Как сделать так, чтобы MAX занимал квадрат исключительно для того, чтобы MIN не попал в квадрат?

Давайте попробуем упрощенный пример (показанный изящным рисунком ASCII), где варианты - «Левый» и «Правый». Предположим, что дерево слишком велико, чтобы пройти весь путь до конечных состояний, поэтому промежуточные значения вычисляются на основе эвристической функции (отмеченной * ниже). -INF - это конечное состояние, в котором MIN побеждает.

                MAX (a)             
                /   \
               A     B
              /       \
           MIN (b)    MIN (c)     
           /  \       /  \
          A    B     A    B
         /     |     |     \
      -INF    *5    *22    *20

MIN выберет действие A в состоянии (b) со счетом -INF
MIN выберет действие B в состоянии (c) со счетом +20
MAX выберет действие B в состояние (а) на сумму +20 баллов

Проблема - конечно же - в том, что если MAX выберет B, то MIN выполнит действие A (поскольку этот квадрат все еще доступен), и, таким образом, MIN победит. Мне нужно получить MAX, чтобы понять значение выбора действия A в состоянии (a), чтобы MIN не получил -INF на следующем ходу.

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

(Отредактировано для пояснения)


artificial-intelligence minmax
person Christian    schedule 26.11.2011    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Каждый узел в минимаксном дереве - это полное игровое состояние. Когда игрок выбирает действие, игра переходит в это состояние, ограничивая действия обоих игроков (нет возможности выбрать другое действие из другой ветви). Итак, в вашем примере, если в состоянии (a) игрок Макс выбирает действие B, игра теперь находится в состоянии C. Единственные два варианта выбора для минимального игрока в этот момент - A (22) и B (20). Глубина дерева не имеет значения; максимальные и минимальные игроки всегда выбирают наилучшее действие из текущего состояния игры.

Для игры в крестики-нолики каждое состояние должно быть полноценной доской (конечно, возможно). Например, первым уровнем будет каждое возможное место, где X мог бы разместить свой маркер. Тогда каждый дочерний элемент этих состояний будет каждым возможным местом, которое O может разместить с учетом родительского состояния (где размещен X) и т. Д.

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

person Felix    schedule 21.12.2011

arrow_upward
0
arrow_downward

Если подумать, проблема в эвристической функции. Как вы говорите, если MAX выбирает B в состоянии (a),

MIN выполнит действие A (поскольку этот квадрат все еще доступен), и, таким образом, MIN победит.

но на дереве вы отмечаете это * 22, а не -Inf, как должно быть (MIN выигрывает).

person seviyor    schedule 19.12.2011
comment
Я не понимаю одного: если MAX выбирает A в состоянии (a), MIN разрешено выбирать A в состоянии (b) (как вы сказали, A является позицией, она больше недоступна). - person seviyor; 19.12.2011