PDF-лекции, страница 18

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

Например, дляшашек могут учитываться такие (статические) элементы конфигурации игры, как продвинутость иподвижность шашек, количество дамок, контроль ими центра и проч. По сути, статическая функциявычисляет эвристическую оценку шансов на выигрыш одного из игроков. Для определенности будемрассматривать задачу выигрыша игрока ПЛЮС и соответственно поиска достаточно хорошего егопервого хода от заданной конфигурации.Будем придерживаться общепринятого соглашения, по которому значение статическойоценочной функции тем больше, чем больше преимуществ имеет игрок ПЛЮС (над игроком МИНУС) воцениваемой позиции. Очень часто оценочная функция выбирается следующим образом: статическая оценочная функция положительна в позициях, где игрок ПЛЮС имеет преимущества; статическая оценочная функция отрицательна в конфигурациях, где МИНУС имеет преимущества; статическая оценочная функция близка к нулю в позициях, не дающих преимущества ни одному изигроков.Например, для шашек в качестве простейшей статической функции может быть взят перевес вколичестве шашек (и дамок) у игрока ПЛЮС.

Для игры «крестики-нолики» на фиксированном квадратевозможна такая статическая оценочная функция: +если P есть позиция выигрыша игрока ПЛЮСE(P) =  если P есть позиция выигрыша МИНУСа (NL+ +NC+ +ND+ )(NL +NC +ND) в остальных случаяхгде+  очень большое положительное число;  очень маленькое отрицательное число;NL+, NC+, ND+  соответственно число строк, столбцов и диагоналей, «открытых» для игрокаПЛЮС (т.е. где он еще может поставить три выигрышных крестика подряд),а NL, NC, ND  аналогичные числа для игрока МИНУС.На рис.3 приведены две игровые позиции (на квадрате 44) и соответствующие значения статическойоценочной функции.Рис.3а)OX XE (P) = 8 - 5 = 3б)OXXO XE (P) = 6 - 4 = 2Подчеркнем, что с помощью статической оценочной функции оцениваются толькоконцевые вершины дерева игры, для оценок же промежуточных вершин, как и начальнойвершины, используется минимаксный принцип, основанный на следующей простой идее.Если бы игроку ПЛЮС пришлось бы выбирать один из нескольких возможных ходов, то онвыбрал бы наиболее сильный ход, т.е.

ход, приводящий к позиции с наибольшей оценкой.58Аналогично, если бы игроку МИНУС пришлось бы выбирать ход, то он выбрал бы ход,приводящий к позиции с наименьшей оценкой.Сформулируем теперь сам минимаксный принцип:▪ ИЛИ-вершине дерева игры приписывается оценка, равная максимуму оценок ее дочерних вершин;▪ И-вершине игрового дерева приписывается оценка, равная минимуму оценок ее дочерних вершин.Минимаксный принцип положен в основу минимаксной процедуры, предназначенной дляопределения наилучшего (более точно, достаточно хорошего) хода игрока исходя из заданнойконфигурации игры S при фиксированной глубине поиска N в игровом дереве. Предполагается, чтоигрок ПЛЮС ходит первым (т.е. начальная вершина есть ИЛИ-вершина). Основные этапы этойпроцедуры таковы:1. Дерево игры строится (просматривается) одним из известных алгоритмов перебора (как правило,алгоритмом поиска вглубь) от исходной позиции S до глубины N;2.

Все концевые вершины полученного дерева, т.е. вершины, находящиеся на глубине N, оцениваются спомощью статической оценочной функции;3. В соответствии с минимаксным принципом вычисляются оценки всех остальных вершин: сначалавычисляются оценки вершин, родительских для концевых, затем родительских для этихродительских вершин и так далее; таким образом оценивание вершин происходит при движенииснизу вверх по дереву поиска  до тех пор, пока не будут оценены вершины, дочерние для начальнойвершины, т.е. для исходной конфигурации S;4. Среди вершин, дочерних к начальной, выбирается вершина с наибольшей оценкой: ход, который кней ведет, и есть искомый наилучший ход в игровой конфигурации S.Рис.4W0 + 3W4  0W 1 3W2 + 31-13W3 + 442W 5+ 3 W 6 + 0 W 7 + 13201-4На рис.4 показано применение минимаксной процедуры для дерева игры, построенного доглубины N=3.

Концевые вершины не имеют имен, они обозначены своими оценками  значениямистатической оценочной функции. Числовые индексы имен остальных вершин показывают порядок, вкотором эти вершины строились алгоритмом перебора вглубь. Рядом с этими вершинами находятся ихминимаксные оценки, полученные при движении в обратном (по отношению к построению дерева)направлении. Таким образом, наилучший ход – первый из двух возможных.На рассматриваемом игровом дереве выделена ветвь (последовательность ходов игроков),представляющая так называемую минимаксно-оптимальную игру, при которой каждый из игроковвсегда выбирает наилучший для себя ход. Заметим, что оценки всех вершин этой ветви деревасовпадают, и оценка начальной вершины равна оценке концевой вершины этой ветви.В принципе статическую оценочную функцию можно было бы применить и к промежуточнымвершинам, и на основе этих оценок осуществить выбор наилучшего первого хода, например, сразувыбрать ход, максимизирующий значение статической оценочной функции среди вершин, дочерних кисходной.

Однако считается, что оценки, полученные с помощью минимаксной процедуры, есть болеенадежные меры относительного достоинства промежуточных вершин, чем оценки, полученные прямымприменением статической оценочной функции. Действительно, минимаксные оценки основаны напросмотре игры вперед и учитывают разные особенности, которые могут возникнуть в последующем, вто время как простое применение оценочной функции учитывает лишь свойства позиции как таковой.Это отличие статических и минимаксных оценок существенно для «активных», динамичных позицийигры (например, в шашках и шахматах к ним относятся конфигурации, в которых возникает угроза59взятия одной или нескольких фигур). В случае же так называемых «пассивных», спокойных позицийстатическая оценка может мало отличаться от оценки по минимаксному принципу.Альфа-бета процедураМинимаксная процедура организована таким образом, что процесс построения частичногодерева игры отделен от процесса оценивания вершин.

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

В основе сокращения поиска лежит достаточно очевидноесоображение: если есть два варианта хода одного игрока, то худший в ряде случаев можно сразуотбросить, не выясняя, насколько в точности он хуже.Рассмотрим сначала идею работы альфа-бета процедуры на примере игрового дерева,приведенного на рис.19. Дерево игры строится до глубины N=3 алгоритмом перебора вглубь. Причемсразу, как это становится возможным, вычисляются не только статические оценки концевых вершин, нои предварительные минимаксные оценки промежуточных вершин. Предварительная оценкаопределяется соответственно как минимум или максимум уже известных к настоящему моменту оценокдочерних вершин.

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

Эти листья оценены статической функцией, и вершина W2+ получила точную минимакснуюоценку 3, а вершина W1  предварительную оценку 3. Далее при построении и раскрытии вершины W3+статическая оценка первой ее дочерней вершины дает величину 4, которая становится предварительнойоценкой самой вершины W3+. Эта предварительная оценка будет потом, после построения второй еедочерней вершины, пересчитана. Причем согласно минимаксному принципу оценка может толькоувеличиться (поскольку подсчитывается как максимум оценок дочерних вершин), но даже если онаувеличится, это не повлияет на оценку вершины W1, поскольку последняя при уточнении поминимаксному принципу может только уменьшаться (так как равна минимуму оценок дочернихвершин). Следовательно, можно пренебречь второй дочерней вершиной для W3+, не строить и неоценивать ее, поскольку уточнение оценки вершины W3+ не повлияет на оценку вершины W1. Такоесокращение поиска в игровом дереве называется отсечением ветвей.Рис.5+ 3W0W4 3W1 3W2+ 31-13W3+ 44W5+ 332Продолжим для нашего примера процесс поиска в глубину с одновременным вычислениемпредварительных (и точных, где это возможно) оценок вершин вплоть до момента, когда построены ужевершины W4 , W5+ и две дочерних последней, которые оцениваются статической функцией.

Исходя изоценки первой дочерней вершины начальная вершина W0+, соответствующая исходной позиции игры, кэтому моменту уже предварительно оценена величиной 3. Вершина W5+ получила точную минимакснуюоценку 3, а ее родительская W4 получила пока только предварительную оценку 3. Эта предварительнаяоценка вершины W4может быть уточнена в дальнейшем, и в соответствии с минимаксным принципомвозможно только ее уменьшение, но это уменьшение не повлияет на оценку вершины W0+, посколькупоследняя, опять же согласно минимаксному принципу, может только увеличиваться. Таким образом,построение дерева можно прервать ниже вершины W4, отсекая целиком выходящие из нее вторую итретью ветви (и оставляя ее оценку предварительной).60На этом построение игрового дерева заканчивается, полученный результат  лучший первый ход тот же самый, что и при минимаксной процедуре.