Альфа-бета обрезка для минимакс - PullRequest
Новая
       95

Альфа-бета обрезка для минимакс

12 голосов
/ 25 октября 2011

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

Это мое понимание минимакса:

  1. Создание списка всех возможных ходов вплоть до предела глубины.

  2. Оцените, насколько благоприятно игровое поле для каждого узла в нижней части.

  3. Для каждого узла (начиная с нижнего уровня) оценка этого узла является наивысшей оценкой его детейесли слой макс.Если слой минимальный, оценка этого узла является наименьшей оценкой для его дочерних элементов.

  4. Выполните ход с наибольшим количеством баллов, если вы пытаетесь достичь максимума, или с наименьшимесли вы хотите минимальный балл.

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

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

Может ли кто-нибудь указать, что я ошибаюсь?Этот ответ ( Minimax, объясненный для идиота ) помог мне понять минимакс, но я не понимаю, как может помочь отсечение альфа-бета.

Спасибо.

Ответы [ 5 ]

15 голосов
/ 25 октября 2011

Чтобы понять альфа-бета, рассмотрим следующую ситуацию.Сейчас ход белых, белые пытаются максимизировать счет, черные пытаются минимизировать счет.

Белые оценивают ходы A, B и C и находят лучший результат 20 с C. Теперь рассмотрим, что происходит, когдаоценивая ход D:

Если белые выбирают ход D, нам нужно рассмотреть встречные ходы черных.На раннем этапе мы обнаруживаем, что черные могут захватить белую королеву, и это поддерево получает минимальный счет 5 из-за потерянной королевы.Тем не менее, мы не учли все встречные ходы черных.Стоит ли проверять отдых?Нет.

Нам все равно, могут ли черные получить оценку ниже 5, потому что ход белых "C" может сохранить счет до 20. Черные не выберут контр-ход с результатом выше 5, потому чтоон пытается свести к минимуму счет и уже нашел ход со счетом 5. Для белых ход C предпочтительнее, чем ход D, как только MIN для D (пока 5) опустится ниже уровня C (наверняка 20),Таким образом, мы «обрезаем» остальную часть дерева там, возвращаемся на уровень и оцениваем ходы белых E, F, G, H .... до конца.

Надеюсь, это поможет.

3 голосов
/ 29 июня 2014

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

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

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

Я написал подробное объяснение Alpha Beta Pruning, его псевдокода и нескольких улучшений: http://kartikkukreja.wordpress.com/2014/06/29/alphabetasearch/

1 голос
/ 25 октября 2011

Вот краткий ответ - вы можете узнать значение узла без вычисления точного значения всех его дочерних элементов.

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

1 голос
/ 25 октября 2011

(Очень) краткое объяснение mimimax :

  • Вы (оценщик позиции на доске) можете выбрать ход n.Вы пробуете все из них и даете позиции на доске оценщику (оппоненту).

    • Оппонент оценивает новые позиции на доске (для него, стороны противника) - рекурсивно делая по существу то же самоеВызов (его оппонент) оценщика, если не достигнута максимальная глубина или какое-либо другое условие и не вызван статический оценщик - и затем выбирает оценку максимум и отправляет оценки обратно вам.

  • Вы выбираете ход, который имеет минимум этих оценок.И эта оценка - это оценка доски, которую вы должны были оценить в начале.

(Очень) краткое объяснение α-β-обрезка :

  • Вы (оценщик позиции на доске) можете выбрать ход n.Вы попробуйте все из них один за другим и отдадите позиции на доске оценщику (оппоненту) - но вы также передаете свою текущую оценку (вашей доски).

    • Оппонент оценивает новую позицию на доске (для него, стороны противника) и отправляет оценку обратно вам.Но как он это делает?У него есть выбор игры m ходов.Он пробует их все и отдает новые позиции на доске (одну за другой) оценщику (своему противнику), а затем выбирает максимальную.
    • Важный шаг : Если какая-либо из тех оценок, которые он получит, больше, чем тот минимум, который вы ему дали, наверняка он в конечном итоге вернет оценочное значение, по крайней мере, такое большое (потому что он хочет увеличить ).И вы обязательно проигнорируете это значение (потому что вы хотите минимизировать ), чтобы он прекратил работу с досками, которые он еще не оценил.

  • Вы выбираете ход, который имеет минимум этих оценок.И эта оценка - это оценка доски, которую вы должны были оценить в начале.

1 голос
/ 25 октября 2011

Я думаю, что ваш вопрос намекает на неправильное понимание функции оценки

Если вы можете определить оценку узла, вам нужно знать оценку всех узлов на уровне ниже, чемузел (в моем понимании минимакса)

Я не совсем уверен, что вы имели в виду , но это звучит неправильно.Функция оценки (EF) обычно очень быстрая, оценка статического положения .Это означает, что нужно только взглянуть на одну позицию и вынести «вердикт».(IOW, вы не всегда оцениваете ветвь в n plys)

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

Теперь, например, в шахматах, обычно есть явное / скрытое отклонение от приведенного выше:

  • позиция может оцениваться по-разному в зависимости отигровой контекст (например, была ли точная позиция ранее во время игры; сколько ходов произошло без пешечных ходов / захватов, в пассивном режиме и с возможностью рокировки).Наиболее распространенная «хитрость» для решения этой проблемы заключается в том, чтобы фактически включить это состояние в «положение». 1

  • , для различных фазигра (начало, середина, конец);это оказывает определенное влияние на дизайн (как обращаться с кэшированными оценками при изменении EF? Как выполнить альфа / бета-обрезку, когда EF отличается для разных слоев?)

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

Я бы ссылался на онлайн-ресурсы, такие как:

1 точно так же, как условия 'check' / 'тупиковые', если они не являются специальными случаями вне оценкифункция в любом случае

...