Intel_Nils (526801), страница 31
Текст из файла (страница 31)
Некоторые из концевых вершин этого дерева (например, вершина А) представляют позиции, в которых МИНУС выигрывает, и поэтому онн имеют оценку — оо. Проследив этн оценки в обратном направлении, мы видим, что наилучшим ходом для игрока ПЛЮС является здесь тот единственный ход, который позволяет ему избежать немед.ленного поражения. Теперь даже МИНУС может видеть„что ПЛЮС должен выиграть при следующем своем ходе, и потому он с достоинством уступает. ЛЛ2. АЛЬФА-БЕТА ПРОЦЕДУРА В только что описанной процедуре перебора процесс построения дерева перебора полностью отделен от процесса аценни позиции. Только после того, как заканчивается построение дерева, начинается оценка позиций.
Оказывается, что такое разделение приводит к весьма неэффективной стратегии. Можно добиться существенного снижения необходимого объема перебора (инагда на несколько порядков), если аценивание концевых вершин и вычисление обращенных величин вести одновременно с построением дерева. Рассмотрим дерево перебора, изображенное на рис. 5.12 '(последний этап нашего перебора в игре тик-так-ту). Предположим, что концевая вершина оценивается, нан только ана построена. Тогда после построения и оценки вершины А нет > Ю ы о Х о й М ж О х Ой З и а ы рэо Гк Д Методы иоиска ари сведении задач к подзадачам никакого смысла строить (и оценивать) вершины В, С и Р. В самом деле, так как в распоряжении игрока МИНУС имеется позиция А и он ничего не может ей предпочесть, то ясно, что он выберет именно А. Тогда можно приписать вершине, предшествующей А, обращенную величину — оо и продолжать перебор, сэкономив поисковые усилия, связанные с построением и оценкой вершин В, С и Р. (Заметим, что эта экономия была бы даже еще значительнее, если бы перебор производился Предо и Фщ аеаа аиа -— итиееьиаи атеииаи чина--т О Ф ФФФФФ~ а-а ! а-а- -т Р ис.
о.тд Часть дерева первого этапа игры тик-так-ту. до большей глубины, поскольку не нужно было бы строить ни одну из вершин, следующую за В, С и Р.) Важно отметить, что тот факт, что вершины В, С и Р не строятся, никак не может повлиять на ход, который окажется для игрока ПЛЮС наилучшим первым ходом. В этом примере экономия затрат на перебор связана с тем, что позиция А выигрышна для игрока МИНУС. Однако экономии такого же типа можно добиться даже и тогда, когда ни одна из позиций дерева перебора не является выигрышной ни для игрока ПЛЮС, ни для игрока МИНУС. Рассмотрим дерево для игры тик-так-ту, изображенное на рис.
5.10. Часть этого дерева воспроизведена на рис. 5.13. Предположим, что производится перебор на заданную глубину, и как только строится некоторая концевая вершина, вычисляется ее статическая оценка. Предположим также, что, как только позиции может быть приписана обращенная величина, эта величина 161 б,12. Альфа-бета процедура сразу )ке вычисляется. Теперь рассмотрим ситуацию, возникающу|о на том этапе перебора в глубину, когда уже построены вершина А и ее дочерние вершины, но еще не построена вершина В. Для вершины А обращенная величина равна — 1. Сейчас начальной вершине можно приписать предварительную обращенную величину (ПОВ), равную — 1. В зависимости от обращенных величин других дочерних вершин начальной вершины окончательная обращенная величина начальной вершины может стать больше этой предварительной величины — 1, но не может стать меньше.
Продолжим процесс поиска в глубину до момента, когда строятся вершина В и первая из ее дочерних вершин, т. е. С. Вершине С присваивается статическая величина — 1. Вершине В можно присвоить предварительную обращенную величину (ПОВ), равную — 1. В зависимости от статических величин остальных дочерних вершин вершины В окончательная обра щенная величина вершины В может стать меньше — 1, но не может стать больше.
Заметим, что окончательная обращенная величина вершины В не может поэтому превысить ПОВ начальной вершины и, следовательно, можно прервать перебор ниже вершины В. Можно быть уверенным в том, что вершина В не окажется предпочтительнее вершины А. Это уменьшение затрат на перебор достигается благодаря прослеживанию предварительных обращенных величин. В общем' случае, как только дочерним вершинам некоторой вершины приписаны обращенные величины, следует пересмотреть ПОВ этой вершины. Следует учесть, что 1) ПОВ «И» вершин (включая начальную вершину) не может уменьшаться. 2) ПОВ «ИЛИ» вершин не может увеличиваться. Учитывая эти замечания, сформулируем следующие правила прерывания перебора: а) Перебор можно прервать ниже любой «ИЛИ» вершины, ПОВ которой не больше, чем ПОВ любой предшествующей ей вершины «И» (включая начальную вершину).
Этой вершине «ИЛИ» затем можно присвоить ее ПОВ в качестве окончательной обращенной величины '). б) Перебор может быть прерван ниже любой «И» вершины, ПОВ которой не меньше, чем ПОВ любой предшествующей ей «ИЛИ» вершины. Этой «И» вершине затем можно присвоить ее ПОВ в качестве окончательной обращенной величины. ') заметим, что вта обращенная величина может не быть «истинной» для своей вершины, но она является той грииипей, которая приводит к правильному вычислению предвврительиой обращенной величины для предшествующей вершины.
1 + И + 1 ! о Е' М ! П ф 3 + ! 4- о + о $ ~Й 6 Е аф Ф.. ~,1 с 3В с а о 1 + я + -> + :ч + Ю + + ./. 3 Ф й Й о Я ~6 д й Б.И Эффективность перебора при альфа-бета процедуре 1ВЗ В процессе поиска ПОВ вычисляются следующим образом: 1) ПОВ для «И» вершины (включая начальную вершину) полагается равной наибольшей из имеющихся в данный момент обращенных величин ее дочерних вершин.
2) ПОВ для вершины «ИЛИ» полагается равной наименьшей из имеющихся в данный момент обращенных величин ее дочерних вершин. Обычно ПОВ для «И» вершин называют альфа-величинами, а ПОВ для «ИЛИ» вершин называют бета-величинами. Если перебор прерывается в соответутвии с правилом (а), то говорят, что имеет место альфа-отсечение, а если в соответствии с правилом (б), то говорят, что имеет место бета-отсечение. Весь процесс прослеживания ПОВ и осуществления отсечений, когда это возможно, обычно называют альфа-бета процедурой. Про цедура заканчивается, когда всем дочерним вершинам для начальной ~вершины приписаны окончательные обращенные величины.
Тогда наилучшим первым ходом будет ход, приводящий к дочерней вершине с наибольшей обращенной величиной. Заметим, что такая процедура всегда приводит к тому же наилучшему первому ходу, что и простой минимаксный метод той же глубины. Единственное отличие состоит в том, что альфа-бета процедура, как правило, находит этот наилучший первый ход после перебора намного меньшего объема. Применение альфа-бета процедуры иллюстрируется на дереве, изображенном на рис. 5.14. Это дерево перебора, построенное на глубину 6. (Для удобства «И»,вершины изображены квадратиками, а вершины «ИЛИ» — кружками.) Концевые вершины имеют указанные статические значения.
Предположим, что мы ведем перебор с использованием альфа-бета процедуры. (Мы опять договариваемся строить в первую очередь вершины, расположенные слева.) Поддерево, получающееся в результате альфа-бета процедуры, выделено жирными линиями. Отсеченные вершины зачеркнуты. Заметим, что пришлось оценить только 18 из первоначальных 41 вершин. Читатель может на этом примере проконтролировать свое понимание смысла альфа-бета процедуры, попробовав повторить перебор. 5.13.
ЭФФЕКТИВНОСТЬ ПЕРЕБОРА ПРИ АЛЬФА-БЕТА ПРОЦЕДУРЕ Для того чтобы можно было произвести отсечения, по нрайией мере часть дерева перебора должна быть построена до максимальной глубины, поскольку предварительные обращенные ~величины должны основываться на статических значениях концевых вершин. Поэтому при использовании альфа-бета процедуры обычно прибегают к той или иной разновидности перебора в глубину. Число отсечений, возможных в процессе перебора, зависит от степени, в которой первые предварительные 164 Гл.
б. Методы поиска при сведении задач к подзадачам величины аппроксимируют окончательные обращенные величины. Окончательная обращенная величина для начальной вершины совпадает со статическим значением одной нз концевых вершин. Если эту вершину можно достичь первой при переборе в глубину, то число отсечений будет максимальным. При максимальном числе отсечений требуется строить и оценивать минимальное число концевых вершин.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
