Главная » Игры, Теория » Форсированные варианты

0

По окончании полного перебора поиск может быть продолжен в форсиро­ванном варианте, который, в сущности, является конечной стадией выбо­рочного поиска. Основное его назначение — дать примерную оценку пози­ции горизонта. Какие ходы являются форсированными? В самом простей­шем случае это взятия. Взятия в шахматах дают самый большой прирост оценки (существенно больше, чем стратегическая оценка), и поэтому рас­смотрение взятий в глубине поиска сглаживает до некоторой степени эф­фект горизонта. Взятия являются также ходами, требующими немедленной реакции. В шахматах бывают очень длинные размены, которые программа должна рассматривать до конца. Если программа считает на 8 полуходов и рассматривает все размены в конце, уровень ее игры будет значительно вы­ше. Кроме взятий, и другие ходы могут являться форсированными. Напри­мер, шахи. Шах является, в сущности, видом атаки. Атака может быть на пешку, на ферзя, а в случае шаха — на короля. Шах является особым ходом в шахматах. Игра при шахе как бы замирает, и сама ситуация требует более глубокого просчета. Шахи в очень сильной степени влияют на эффект гори­зонта. Если форсированные варианты не рассматривают шахи, их оценка является уж очень приблизительной. В некоторых случаях и этого бывает достаточно. Если программа считает глубоко и имеет развитую систему вы­борочных продлений полного перебора, то на некоторой глубине ей может оказаться достаточно самой приблизительной оценки горизонта. Существу­ют два основных подхода к этой проблеме:

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

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

Все упирается в основную проблему программирования игр методом пере­бора. Считать надо очень глубоко, а очень глубоко считать невозможно. Есть различные подходы к решению этой проблемы. Основная задача со­стоит в выделении лучших ходов и более глубокого их просчета при помо­щи выборочных продлений или в форсированных вариантах. Разберем про­стейший форсированный вариант, рассматривающий только взятия до кон­ца:

int Quies(int alpha, int beta) {

int val = Evaluate(); //статическая оценка текущей позиции if(val > alpha) alpha = val;

PMove move = GenerateCaptures(); //все взятия

while( move && alpha < beta) {

MakeMove();

val = -Queis(-beta,-alpha); UnMakeMove();

if(val > alpha)alpha = val;

}

return alpha;

}

Рассмотрим приведенный код подробнее. В сущности, это обычный alpha- beta поиск, только вместо всех перемещений генерируются взятия, и alpha повышается текущей оценкой. Глубина поиска не ограничена. Взятия огра­ничены количеством фигур на доске, и они будут рассмотрены до конца. Так как мы предусматриваем только взятия и повышаем alpha текущей оценкой, такой поиск будет выполняться значительно быстрее, чем полный широтный поиск. Почему мы повышаем alpha? Дело в том, что рассматри­ваются не все перемещения, а только взятия. Если взятие ведет к ухудше­нию оценки, программа не делает его. Вместо остальных перемещений ис­пользуется текущая оценка данной позиции. Мы исходим из предположе­ния, что программа нашла бы ход, не ухудшающий текущую оценку, если бы все перемещения были предусмотрены. Если рассматривать данный узел с точки зрения предыдущего узла, из которого был сделан ход противника, то в нем оценкой после перемещения занижается максимум (beta). Напри­мер, взяли коня — наш максимум ограничивается текущей оценкой плюс оценка хода (вес коня). Таким образом, если смотреть из преузла, максимум ограничивается взятой фигурой, и программа не выясняет все комбинации, а только возможность взятия данного коня. Говоря другими словами, фор­сированный поиск взятий рассматривает только перемещения, которые за­хватывают. Взятие коня может повлечь за собой некоторую комбинацию, приводящую к еще большему выигрышу материала. Программа этого не увидит. Она исходит из предположения, что раз черные взяли коня, и ход белых, они всегда найдут ответ, не приводящий к дальнейшей потере мате­риала. Это приблизительно, но на большой глубине нет другого выхода. Или мы не считаем ничего, или считаем упрощенно.

Взятия в генераторе перемещений должны быть обязательно отсортированы. Например, по принципу "наиболее ценная жертва — наименее ценный на­падающий" (MW/LVA). Без сортировки взятий форсированный вариант существенно замедлит выполнение программы и приведет к более сокра­щенному полному широтному поиску, что недопустимо. Если форсирован­ный вариант рассматривает только взятия, то основное его назначение — дать приблизительную оценку позиции горизонта, и выполняться он должен очень быстро. Может возникнуть искушение не считать все взятия, а давать еще более приблизительную оценку позиции горизонта. Например, если текущая оценка меньше alpha на ладью, то взятие пешки вряд ли имеет смысл. Существует алгоритм SEE, рассматривающий только победившие или равные взятия. Например, сочетание ферзь—пешка не будет рассмотре­но. Очень может оказаться, что пешка не защищена, и такой алгоритм дает ошибку. Основная ставка делается на то, что форсированный вариант в лю­бом случае ошибается, а если мы сосчитали уже достаточно глубоко, можно ограничиться совсем приблизительной оценкой позиции горизонта. Здесь есть масса возможностей для эксперимента. Мое мнение, что к SEE надо подходить очень осторожно. Отвергать, как несущественное, взятие пешки можно на достаточно большой глубине, а взятие ладьи — тем более. В це­лом, SEE вполне работоспособный алгоритм.

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

int Quies(int alpha, int beta) {

if(inCheck) return AlphaBeta(1,alpha,beta); //полный поиск int val = Evaluate(); //статическая оценка текущей позиции if(val > alpha) alpha = val;

PMove move = GenerateCaptures(); //все взятия

while( move && alpha < beta) {

MakeMove();

val = -Queis(-beta,-alpha);

UnMakeMove() ;

if(val > alpha)alpha = val;

}

return alpha;

}

Если король под шахом, вызывается функция полного широтного поиска. Несмотря на простоту примера, в нем видна одна тонкость: не повышая alpha под шахом, мы делаем предположение, что результат расчета может увеличить его, и не хотим мешать этому. Для всех ходов, кроме шаха, огра­ничиваем максимум результатом сделанного хода. Минимум неизвестен, он выявится в результате просчета. Для шахов не ограничиваем максимум. Та­ким образом в миниатюре демонстрируется основной принцип выборочного поиска. Лучшие ходы надо просчитывать глубже. Так как отсечение выпол­няется статической оценкой, результат не точен, просто мы позволяем луч­шим ходам подрасти. Какие ходы являются лучшими — отдельный вопрос. На данной глубине просчета мы полагаем, что лучшими являются шахи, и не ограничиваем их максимум. Повышение alpha в нашем узле — это то же самое, что и понижение beta после сделанного хода в преузле. Продление шахов в статическом поиске резко улучшает чутье программы на безопас­ность короля и может в некоторых случаях найти глубокий форсированный мат. Также результат разменов получается более точный. Обратите еще раз внимание, что у нас продлеваются только шахи. Взятия не продлеваются. Наша функция считает взятия как ходы, дающие наибольший прирост оценки. Можно обсчитывать и все ходы, но счет резко замедлится. В случае продления только шахов, счет тоже значительно замедляется. Мы усиливаем форсированные варианты за счет сокращения полного широтного поиска, что недопустимо. Какой же выход? Есть один испытанный прием. В форси­рованном варианте глубина просмотра шахов делается более гибкой. Изна­чально она равна, допустим, 2. Это значит, что на первых двух полуходах форсированного варианта программа обнаружит все шахи. При каждом ша­хе глубина может увеличиваться на 1 (до разумного предела, например, до 30 полуходов). Если на шах есть единственный ответ, то глубину просмотра можно увеличить на 2. Это позволяет программе найти глубокие тактиче­ские выпады, анализируя минимальное количество позиций. Такая схема требует изощренного программирования. С возрастанием мощности про­цессоров возрастает глубина полного перебора. В пределах полного перебо­ра шахи тоже могут расширяться, но несколько другим образом. Не будем забывать, что полный перебор экспоненциален, а основное назначение форсированного варианта — приблизительная оценка позиции горизонта.

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

Литература:

Корнилов Е. Н.  Программирование шахмат и других логических игр. — СПб.: БХВ-Петербург, 2005. – 272 е.: ил.

По теме:

  • Комментарии