псевдокод для алгоритма minmax

Question

Я хочу получить псевдокод для алгоритма minmax. Мне нужно сделать 2 функции, def maxAgent (gameState, глубина) и minAgent. Есть ли какое-нибудь тело, у которого есть правильный и легкий псевдокод для этого.

Answer 1

Два игрока, A и B, играют по очереди.

Нам дана функция подсчета f, которая оценивает данную позицию доски, P. Большие значения f (P) лучше для A и хуже для B (т. Е. F (P) является оценкой того, насколько «хорош» P для А без дальнейших заглядываний).

Рассмотрим позицию на доске P.

Если P является листовым узлом (т.е. P является выигрышной позицией или мы смотрели так далеко вперед, как нам хочется), то мы возвращаем f (P) в качестве оценки для этого узла.

В противном случае P не является листовым узлом и имеет дочерние элементы C1, ..., Cn. Мы рекурсивно вычисляем баллы для детей, давая S1, ..., Sn.

Если A играет в P, то счет для P будет максимальным {S1, ..., Sn}, поскольку A всегда будет играть, чтобы максимизировать свое преимущество.

Если B играет в P, то счет для P составляет min {S1, ..., Sn}, поскольку B всегда будет играть, чтобы минимизировать преимущество A.

Этого должно быть достаточно, чтобы превратиться в код.

После того, как вы это сделаете, взгляните на альфа-бета-обрезку, которая должна (радикально) уменьшить количество запросов, которые вам нужно сделать. Сокращение альфа-беты основано на идее, что, если A выводит, что B может играть, чтобы сделать максимальное преимущество A равным M, то нет никакого смысла рассматривать любое поддерево, чей счет больше, чем M, поскольку B никогда не допустит A такой опции!

Answer 2

Алгоритм minmax пытается максимизировать счет для игрока A и минимизировать счет для игрока B. Учитывая узел, вы можете найти конечный результат оптимальной игры, взяв максимум (для A) или min (для B) изоценка для последующих узлов.

Предполагая, что конечные узлы имеют назначенного победителя (1 для A, -1 для B), в то время как все другие узлы имеют счет 0. Вы можете затем вычислить окончательный результат победы для A с помощью чего-то вроде

  getMaxScore(node) {
    score = node.score;
    for each child node 
       score = max(score, getMaxScore(node))  
    next

    return score;
  }

Это основной алгоритм.Вы можете замкнуть оценку, как только счет станет равным 1, тогда у вас будет известный выигрыш для A.

Алгоритм такой же, как для B, getMinScore, только вы используете функцию min, и еслизамыкание, ищите -1. ​​