Лекция: Альфа-бета алгоритм.

Программа, разработанная в соответствии с принципом минимакса предусматривает систематический пе­ребор в режиме поиска в глубину всех позиций в дереве поиска, вплоть до заключи­тельных, и вычисление статических оценок для всех заключительных позиций этого дерева. Но обычно не требуется выполнять всю эту работу для того, чтобы правильно вычислить минимаксное значение корневой позиции. В соответствии с этим можно применить более экономичный алгоритм поиска. Усовершенствование этого алгорит­ма может быть основано на такой идее: предположим, что имеются два альтернатив­ных хода; после того как стало полностью ясно, что один из них хуже другого, больше. не требуется знать, насколько именно он хуже, чтобы принять правильное решение. Например, такой принцип можно использовать для сокращения объема по­иска в дереве, показанном на рис. 10.24. В данном случае процесс поиска осуществля­ется, как описано ниже.

1. Начать с позиции а.

2. Перейти вниз к позиции b.

3. Перейти вниз к позиции d.

4. Выбрать максимальное значение для одного из преемников d, что приводит к

получению V (d) = 4.

5. Выполнить возврат к позиции, а затем спуститься вниз к позиции е.

6. Рассмотреть первого преемника е, значение которого равно 5. В данный момент для игрока МАХ (который должен сделать ход в позиции е) гарантировано, по меньшей мере, значение 5 в позиции е, если даже не учитывать того, что из позиции еисходят другие (возможно лучшие) альтернативы. Эта оценка является достаточной для игрока MIN, чтобы понять, что в узле b альтернатива е хуже, чем d, даже не зная точного значения е.

На этом основании можно пренебречь вторым преемником позиции е и присвоить позиции е ориентировочное значение 5. Но такая замена точного значения приблизительным не влияет на расчетное значение b и, следовательно, на значение а.

На этой идее основан знаменитый альфа-бета-алгоритм(называемый также алгоритмом альфа-бета-отсечения), применяемый для эффективной реализации принципа минимакса. На рис. 10.25. показано действие альфа-бета-алгоритма на примере дерева, приведенного на рис. 10.24. Как показано на рис. 10.25., некоторые из зафиксированных значений являются приблизительными. Но, несмотря на такую замену точных значений приблизительными, дерево содержит достаточно информации для точного определения значения корневого узла. В примере, показанном на рис. 10.25., применение альфа-бета-алгоритма позволяет сократить сложность поиска с восьми статических оценок (как было первоначально на рис. 10.24.) до пяти статических оценок.

аХод игрока МАХ

b cХод игрока MIN

d e f gХод игрока

МАХ

Статические оценки

Рис. 10.25. Дерево, nриведенное на рис. 10.24., поиск в котором осуществляется с по­мощью альфа-бета-алгоритма. При этом поиске отсекаются узлы, обозначенные штриховыми линиями, поэтому общий объем поиска уменьшается. В результате некоторые из зафиксированных значении становятся неточными (в частности, это характерно для узлов с, е, см рис. 10.24). Но, несмотря на такое снижение точности, дерево содержит достаточно информации для правильного определения значения корневого узла и поиска основного варианта.

Как было указано выше, основная идея альфа-бета-отсечения состоит в том, чтобы найти «достаточно хороший» ход (не обязательно лучший), который вполне подходит для принятия правильного решения. Эту идею можно формализовать, наложив два ограничения на зафиксированное значение позиции, которые обычно обозначаются как Alphaи Beta. Эти ограничения имеют следующее значение: Alpha — это мини­мальное значение, достижение которого уже гарантировано для игрока МАХ, а Beta ­максимальное значение, которого может надеяться достичь игрок МАХ. Если позиция рассматривается с точки зрения игрока MIN, то Beta — это наихудшее значение для MIN, достижение которого гарантировано для игрока MIN. Поэтому фактическое зна­чение (которое должно быть найдено) лежит в пределах от Alpha до Beta. Если ока­залось, что некоторая позиция имеет значение, лежащее за пределами интервала Alpha-Beta, то этого достаточно, чтобы определить, что данная позиция не относится к основному варианту, даже не зная точного значения этой позиции. Точное значе­ние позиции необходимо знать только в том случае, если оно находится между Alpha и Beta.

Альфа-бета-интервал может стать более узким (но ни в коем случае не более ши­роким!) при больших по глубине рекурсивных вызовах альфа-бета-процедуры. Из-за сужения интервалов количество приближенных оценок увеличивается и поэтому отсечение поддеревьев в дереве ста­новится все более интенсивным. В связи с этим возникает интересный вопрос:

«Какой объем работы позволяет сэкономить альфа-бета-алгоритм по сравнению с про­граммой исчерпывающего поиска по принципу минимакса?» Эффективность поиска с использованием альфа-бета-алгоритма зависит оттого, в каком порядке происходит перебор позиций. Выгоднее всего в первую очередь рассматривать самые сильные ходы для каждого из игроков. Можно легко показать на примерах, что если порядок перебора окажется неудачным, то альфа-бета-­процедуре потребуется перебрать все позиции, рассматриваемые при исчерпывающем минимаксном поиске. Это означает, что в худшем случае альфа-бета-алгоритм не имеет преимуществ над исчерпывающим поиском по принципу минимакса. Но если порядок является благоприятным, экономия усилий может оказаться весьма значи­тельной. Предположим, что N — количество заключительных позиций поиска, ста­тически оцениваемых с помощью исчерпывающего минимаксного алгоритма. Было доказано, что в наилучшем случае, когда вначале всегда рассматривается самый сильный ход, альфа-бета-алгоритм требует статической оценки лишь √N позиций.

Добавим к этому, что данный результат подтвержден на практике при проведении шахматных турниров. На соревнованиях шахматной программе обычно дается опре­деленное количество времени для вычисления следующего хода в игре, а глубина, на которую программа может выполнить поиск, зависит от этого количества времени. В наилучшем случае альфа-бета-алгоритм оказался способным выполнять поиск на глубину, в два раза большую по сравнению с исчерпывающим минимаксным поис­ком. Эксперименты показали, что одна и та же функция оценки, применяемая набольшей глубине дерева, обычно позволяет обеспечить более сильную игру.

Результаты экономии усилий при использовании альфа-бета-алгоритма можно также выразить в терминах эффективного коэффициента ветвления(среднего ко­личества ветвей, отходящих от каждого внутреннего узла) дерева поиска. Предполо­жим, что дерево игры имеет единообразный коэффициент ветвления b. В результате отсечения альфа-бета-алгоритм требует поиска лишь в некоторых из ветвей, что фак­тически приводит к уменьшению коэффициента ветвления. В наилучшем случае та­кое сокращение находится в пределах от b до √b. В программах игры в шахматы фактический коэффициент ветвления в результате альфа-бета-отсечения становится приблизительно равным 6 по сравнению с общим количеством допустимых ходов, примерно равным 30. Менее оптимистические оценки этого результата показывают, что в шахматах, даже при использовании альфа-бета-алгоритма, углубление поиска на 1 полуход (ход одной из сторон) приводит к увеличению количества заключитель­ных позиций поиска примерно в 6 раз.