Обрезка альфа-бета для Minimax

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

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

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

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

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

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

Спасибо.

Ответ 1

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

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

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

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

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

Ответ 2

Вам не нужно оценивать все поддерева node, чтобы определить его значение. Alpha Beta Pruning использует две динамически вычисляемые границы alpha и beta для привязки значений, которые могут принимать узлы.

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

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

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

Ответ 3

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

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

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

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

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

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

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

Я бы назвал онлайн-ресурсы вроде:

Теория программирования компьютерных шахмат

<суб > ¹ так же, как условия проверки /'stalemate', если они не являются специальными, обходимыми вне оценочной функции в любом случае Суб >

Ответ 4

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

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

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

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

Ответ 5

Здесь короткий ответ - вы можете узнать значение node, не вычисляя точное значение всех своих детей.

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