Intel_Nils (526801), страница 30
Текст из файла (страница 30)
В случае «И/ИЛИ» деревьев можно выбрать также стратегию поэтапного перебора, описанную в гл. 3. При ее использовании необходимое пространство в памяти машины периодически очищается в результате отбрасывания некоторых из поисковых «И/ИЛИ» деревьев. Можно, например, определить, какое нз потенциальных деревьев решения внутри дерева перебора имеет наибольшую оцениваемую стоимость. Тогда можно периодически отбрасывать некоторое число наиболее «дорогих» потенциальных деревьев решения (с риском, конечно, что отброшенное дерево окажется верхней частью истинного дерева минимальной стоимости).
Если наш метод предполагается использовать для перебора на «И/ИЛИ» графах (а не на «И/ИЛИ» деревьях), то в алгоритме следует произвести более важные изменения. При этом необходимо принять во внимание соображения, упомянутые в разд. 5.4. 5,11. МИНИМАКСНАЯ ПРОЦЕДУРА ПРИ ПЕРЕБОРЕ НА ИГРОВЫХ ДЕРЕВЬЯХ В гл, 4 мы видели, что игровые деревья можно представлять в виде «И/ИЛИ» деревьев. Пользуясь этим, мы пытаемся доказать, что игрок ПЛЮС может выиграть из некоторого начального положения игры.
Тогда те позиции, которые возникают после хода игрока ПЛЮС, представляются «ИЛИ» вершинами, а позиции, возникающие после хода игрока МИНУС, представляются «И» вершинами. Мы примем, что ПЛЮС ходит первым и ходы ПЛЮСА и МИНУСА чередуются. Следовательно, дочерними для «И» вершин будут «ИЛИ» вершины, и обратно. В соответствии с принятым предположением мы будем считать, что начальной вершиной является «И» вершина. Заключительная вершина соответствует любой позиции, про которую известно,что она является выигрышной для игрока ПЛЮС. (Определение заключительной вершины должно быть изменено, если цель поиска состоит в доказательстве того, что ПЛЮС может добиться б.!1.
Минимакеная процедура при переборе на игровых дедевьях МЗ ничьей, исходя из заданной позиции, или что ПЛЮС в данной позиции не может проиграть.) Для многих простых игр (а также и для окончаний более сложных игр) можно применить перебор на «И/ИЛИ» деревьях, поскольку тогда доказательство выигрыша (или ничьей) можно найти, не строя больших деревьев перебора.
Тогда дерево решения, доказывающее выигрыш (или ничью), дает полную игровую стратегию для игрока ПЛЮС. Примерами простых игр, в которых перебор на «И/ИЛИ» деревьях до получения ответа представляется реально осуществимым, являются игра Гранди яз предыдущей главы, тик-так-ту (крестики-нолики), различные варианты игры ним и некоторые шахматные и шашечные эндшпили. Грубую оценку размеров дерева игры для тик-так-ту, например, можно получить, заметив, что начальная вершина имеет 9 дочерних вершин, каждая из которых в свою очередь имеет по 8 дочерних вершин и т.
д., что приводит к 9! = 362 880 вершинам в нижней части этого дерева. Однако многие пути обрываются на заключительных вершинах более высоких уровней, и, кроме того, значительного уменьшения размеров дерева можно достичь, если принять во внимание симметрии. В случае более сложных игр, таких, как полная игра в шахматы или шашки, о переборе до конца на «И/ИЛИ» деревьях не может быть и речи. Число вершин в полном игровом дереве для шашек было оценено величиной 10'о, а для шахмат— !О'хо.
(Чтобы построить полное дерево для шашек, понадобилось бы около 10м столетий, даже если предположить, что каждая дочерняя вершина образуется за '/з наносекунды.) Процедуры упорядоченного перебора не настолько уменьшают фактор ветвления, чтобы что-то существенно изменилось. Следовательно, мы должны смириться с тем, что для сложных игр перебор до конца невозможен, т. е. следует отказаться от мысли доказать, что можно достичь выигрыша или ничьей (исключая, возможно, эндшпили). Вместо этого при переборе на игровых деревьях можно было бы стремиться найти просто «хороший» первый ход. Мы могли бы сделать этот ход, подождать ответа противника и вновь осуществить перебор с тем, чтобы найти «хороший» ход из новой позиции. Перебор должен производиться так же, как обычный перебор на «И/ИЛИ» графах.
Можно воспользоваться либо методом полного перебора, либо перебором в глубину, либо методами упорядоченного перебора, однако условия окончания теперь необходимо изменить. Можно указать несколько искусственных условий окончания, основанных на таких факторах, как ограничение времени перебора, ограничение объема памяти или глубины самой глубокой концевой вершины в дереве поиска. К тому же в шахматах, например, не оканчивают 1ач Гм Д Методы поиска при сведении задач к подзадачам перебора, если любая из концевых вершин представляет «живую» позицию, например позицию, в которой нет непосредственно выгодного размена.
После того как перебор будет закончен, мы должны извлечь из дерева перебора оценку «лучшего» первого хода. Эту оценку можно получить, применив к концевым вершинам дерева перебора статическую оценочную 4ункцию. Оценочная функция измеряет «достоинства» позиции, отвечающей концевой вершине, и основана она на различных элементах позиции, которые, как полагают, влияют на ее достоинства. Например, в шашках такими полезными элементами являются относительная продвинутость своих шашек, контроль центра доски, контроль центра доски дамками и т. д. При анализе игровых деревьев обычно принимается соглашение, по которому в игровых позициях, где ПЛЮС имеет преимущество, оценочная функция положительна, а для позиций, где преимущество за игроком МИНУС, оценочная функция отрицательна.
Значения вблизи нуля соответствуют игровым позициям, не дающим преимущества ни одному из игроков. Хороший первый ход можно найти с помощью минимаксной процедур»с Мы предполагаем, что если бы игроку ПЛЮС пришлось выбирать между концевыми вершинами, то он выбрал бы ту из иих, которая имеет наибольшую оценку. Следовательно, вершине (типа «И»), являющейся родительской для концевых вершин типа «ИЛИ», приписывается обращенная величина Ьасйеб-пр ча!пе), равная максимуму оценок концевых вершин. другой стороны, если бы между концевыми вершинами пришлось' выбирать игроку МИНУС, то он, вероятно, предпочел бы выбрать такую вершину, которая имела бы наименьшую оценку (т.
е. самую отрицательную), Следовательно, вершине (типа «ИЛИ»), являющейся 'родительской для концевых «И» вершин, приписывается обращенная величина„равная минимуму оценок концевых вершин. После того как всем родительским вершинам концевых вершин приписаны обращенные ~величины, этот процесс «прослеживания в обратном направлении» переносится на уровень выше при условии, что ПЛЮС выбирает вершину с наибольшей обращенной' величиной, а МИНУС вЂ” с наименьшей обращенной величиной. Такое прослеживание в обратном направлении продолжается с уровня на уровень до тех пор, пока, наконец, обращенные величины не будут приписаны всем вершинам, являющимся дочерними для начальной вершины. Мы предполагаем, что если первый ход должен делать игрок ПЛЮС (т.
е. дочерними для начальной вершины являются «ИЛИ» вершины), то ои должен выбрать'в качестве своего первого хода ход, соответствующий дочерней вершине с наибольшим значением этой обращенной величины. ДМ. Минимакснан лрояедура лри лергдоре на игровых дереввик 155 Польза всей этой процедуры связана с тем, что величины, полученные в результате прослеживания оценок в обратном направлении, для вершин, непосредственно следующих за начальной, считаются более надежными мерами относительного достоинства соответствующих позиций, чем те величины, которые можно было бы получить прямым применением оценочной функции к этим позициям.
В конце концов эти обращенные величины будут основаны на «просмотре вперед» по дереву игры, и поэтому они зависят от особенностей, возникающих ближе к концу игры. Проиллюстрируем минимаксный метод на простом примере, использующем игру тик-так-ту. Предположим, что ПЛЮС ставит крестики (Х), а МИНУС ставит нолики (0), и пусть первым ходит ПЛЮС. Мы будем производить полный перебор до тех пор, пока не будут построены все вершины на уровне 2, а затем применим статическую оценочную функцию к позициям, соответствующим этим вершинам.
Пусть наша оценочная функция е(р) позиции р задается следующим образом: Если р не является позицией выигрыша, то е(р) =(число полных строк, столбцов или диагоналей, все еще открытых для игрока ПЛЮС) — (число полных строк, столбцов илн диагоналей, все еще открытых для игрока МИНУС). Если позиция р выигрышна для игрока ПЛЮС, то е(р) = оо (символ со означает очень большое положительное число).
Если позиция р выигрышна для игрока МИНУС, то е(р) = — оо. х, то е(р) =6 — 4=2. Прн Таким образом, если р есть построении дочерних позиций мы будем учитывать симметрии, Так, все позйции х х х х мы будем считать идентичными. (В начале игры фактор ветвления в игре тик-так-ту мал из-за симметрий, а в конце игры он мал нз-за небольшого числа незаполненных клеток.) На рис. 6.!О изображено дерево, построенное прн переборе до глубины 2. Под концевыми вершинами показаны их стати ческие оценки, а величины, полученные в результате прослеживания в обратном направлении, обведены кружком, Поскольку 1 О Ю 3 Ф О М ! О ! Ю 'О СЪ ! Ъ 3 М 1 Ю Ф 3 ~й Р > $й д Ф аВ о ы к о И З в 3 й Ф а И3 Д12.
Альфа-бета процедура 157 позициб имеет обращенную величину с наибольшим значением,она выбирается как первый хад. (Кстати, оказывается, что это лучший первый ход для игрока ПЛЮС.) Предположим теперь, что ПЛЮС делает этот ход, и МИНУС отвечает позицией и, (Плахой хад для бедного игрока МИНУС, который, видимо, не пользуется хорошей стратегией перебора.) Далее ПЛЮС осуществляет перебор на глубину 2 (отправляясь ат позиции н ), чта приводит к дереву пе- ребора, изображенному на рис.
5.11. ПЛЮС делает наилучший ход, а МИНУС делает ход, благодаря которому ан избегает немедленного поражения„. в результате получается позиция О н . Затем ПЛЮС снова осуществляет перебор, что привоя .дит к дереву, изображенному на рис. 5.12.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
