Главная » Игры, Теория » Выборочные продления Краткая характеристика расширений

0

В полном широтном поиске, который мы рассматривали, глубина поиска задавалась при первом вызове рекурсивной функции и уменьшалась в каж­дом узле на 1. Таким образом, мы осуществляли полный перебор на неко­торую фиксированную глубину. Мы рассмотрели также устройство форси­рованного варианта, который вызывался при Depth = 0 и сглаживал эффект горизонта. Форсированный вариант просчитывал дальше наиболее сильные перемещения и давал приблизительную оценку позиции горизонта. Допус­тим, что при минимальном размере дерева перебора, т. е. при оптимальном порядке перемещений, для углубления счета на глубину N+1 нам необхо­димо рассмотреть в 20 раз больше позиций, чем при счете на глубину N. Это довольно приблизительно, но нам для рассуждений нужно отталкивать­ся от каких-то величин. Существует мнение, что увеличение глубины счета на один полуход повышает силу игры программы на разряд. Может, не сто­ит ломать голову над разными ухищрениями, а просто подождать, пока процессоры станут мощнее в 20 раз. Мы сможем считать на 9 полуходов, потом еще в 20 раз — мы сосчитаем на 10 полуходов. Бывают тактические последовательности, которые программа должна просчитывать значительно глубже. Например, если на доске существует форсированная угроза королю, то может потребоваться считать на 14 полуходов. Гроссмейстеры просчиты­вают некоторые варианты на 20 и более полуходов. Вряд ли мощность про­цессоров когда-либо возрастет до такого уровня, да и программы желатель­но писать сейчас, а не через 10 лет. Человек, когда просчитывает некоторые варианты, руководствуется множеством критериев, зависящих от его опыта. Он может просчитать ситуацию очень глубоко, проанализировав при этом минимальное количество позиций. Несмотря на то, что моделировать мыш­ление шахматиста мы не можем, существуют некоторые строки игры, про­счет которых можно продолжить по совершенно формальным признакам. Возникла простая идея — не сокращать глубину просмотра при некоторых ходах. Мы можем считать на 6 полуходов, но некоторые варианты будут рассмотрены значительно глубже. При каких же ходах не сокращается глу­бина счета? Если мы говорим о шахматах, то это, прежде всего, шах. При шахе игра как бы замирает и требует от противника немедленного ответа. Замедление счета при этом тоже минимальное, т. к. число легальных ходов под шахом ограничено, и узел будет обсчитан очень быстро. Продление все­го лишь шахов резко увеличивает силу игры программы. Считая на 6 полу­ходов, она способна обнаружить глубокие форсированные маты и другие комбинации, основанные на угрозе королю и приводящие к выигрышу ма­териала. Пример функции счета, продлевающей шахи:

#define MAX_PLY 20

int AlphaBeta(int color, int Depth, int ply, int alpha, int beta) {

if(Depth == 0 I| ply > MAX_PLY) return Quies(color,alpha,beta);

if(InCheck()) Depth++; //если шах, глубину не уменьшаем Depth—;

PMove move = GenerateAllMoves();

while(move && alpha < beta) {

MakeMove(move);

int tmp = -AlphaBeta(color==BLACK?WHITE:BLACK, Depth, ply+1 -beta, -alpha);

UnMakeMove(move);

if(tmp > alpha) alpha = tmp;

move = move->next;

} //while return alpha;

} //function

Функция inCheck играет роль детектора шахов. В данном примере введена новая переменная — ply. Это абсолютная глубина счета. При первом вызове она равна 0 и увеличивается на 1 в каждом узле. Depth уже только косвенно отражает глубину счета. Если ply превысит некоторое предельное значение (в нашем примере оно ограничено константой max_ply), то поиск завершит­ся и продолжится уже в форсированных вариантах. Продление шахов делает программу намного сильнее. Нужно отметить, что шах — это абсолютно безопасное продление. Сами правила игры подразумевают, что на шах дол­жен быть дан немедленный ответ, иначе конец игре. Общее положение тео­рии игр гласит, что ходы, дающие приращение в узле намного больше, чем другие в этом узле, нужно просчитывать глубже. Это аксиома. Вопрос в том, какие ходы считать лучшими. Для шахмат — это, бесспорно, взятия. Взятия дают приращение оценки намного больше, чем другие ходы, приращение которых ограничено стратегическим приростом. Насчет продления взятий существует множество мнений. Продление всех взятий, кроме того, приве­дет к взрыву дерева перебора и программной аварии. Взятие не всегда тре­бует немедленного ответа, правдоподобность ответа на взятие значительно ниже, чем на шах. К решению этой проблемы можно подойти различными путями. Например, взятия продлеваются до некоторой глубины, а дальше — только шахи. Мы должны просчитывать дальше лучшие ходы, но ход, луч­ший для глубины 2, не всегда является лучшим для глубины 10. На глубине 10 можно уже не уточнять вопрос, будет ли точно выиграна пешка, или программе это только кажется. Некоторые программы расширяют взятия в зависимости от глубины и захваченной области. Например, можно восполь­зоваться массивом, где индекс соответствует ply данной глубины. Если ход в данную позицию больше или равен значению элемента таблицы с данным индексом, мы расширяем узел.

static int ext[] =

{pawn,pawn,pawn,pawn,pawn,pawn,bishop,rook,queen,INFINITY,….};

Еще раз хочется подчеркнуть, что расширять взятия уместно в пределах полного перебора. Приведем стандартную схему расширений:

?    в случае шаха;

D если произошел размен фигуры;

?    если пешка пошла на предпоследнюю горизонталь.

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

Литература:

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

По теме:

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