Деревья MinMax - когда Min может выиграть в два этапа - PullRequest
Новая
       39

Деревья MinMax - когда Min может выиграть в два этапа

4 голосов
/ 26 ноября 2011

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

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

Давайте попробуем упростить пример (показанный в изящном ASCII-стиле), где варианты - Left и Right.Предположим, что дерево слишком большое, чтобы пройти весь путь до конечных состояний, поэтому промежуточные значения рассчитываются на основе эвристической функции (помеченной * ниже).-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 в состоянии (a) для оценки + 20

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

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

(отредактировано для уточнения)

Ответы [ 2 ]

3 голосов
/ 22 декабря 2011

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

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

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

0 голосов
/ 19 декабря 2011

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

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

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

...