Главная » Игры, Теория » Недействительное перемещение

0

Нулевой ход, или недействительное перемещение, используется в большин­стве современных программ. История его открытия довольно туманна. Та­кое впечатление, что он известен был всегда, но об этом открыто не гово­рили. Существовала тенденция сокрытия информации о шахматных про­граммах. Каждому казалось, что он открыл нечто уникальное, до чего никто не додумался, но потом постепенно становилось известно, что все исполь­зуют, в принципе, одни и те же методы. Так было и с нулевым ходом. Офи­циально его еще не существовало. Франц Морш услышал о нем в 1986 году в Германии на мировом первенстве среди шахматных программ, где Дон Бил участвовал с шахматной программой, использующей технику NullMove (Нулевой ход). Франц Морш использовал его в своей программе Fritz, ко­торая и по сей день входит в тройку сильнейших программ. Позже, когда о нем написали Donninger, Beal, Goetsch & Campbel, нулевой ход стал все­общим достоянием.

Нулевой ход позволяет очень просто и на сравнительно неплохом уровне организовать выборочный поиск в шахматной программе. Особенно хорошо он подходит для схем, где осуществляется предварительный осторожный стратегический расчет (чтобы программа хоть как-то шевелила фигурами), а затем включается на полную мощность счет одного материала с обрезкой неправдоподобных ветвей нулевым ходом. Таким образом, при некоторой технике программирования осуществляется расчет на 10 полуходов и более, включая взятия до конца. Усиливаются обычно строки с взятиями и шаха­ми. Такая программа просчитывает огромное количество позиций в секунду (оценочная функция у нее, собственно говоря, отсутствует) и производит очень хорошее впечатление в острых тактических ситуациях. Если человек применил беспорядочную тактику, то он пропал, будь он хоть сам Бобби Фишер. В соревнованиях с другими программами такая программа ведет себя превосходно, т. к. стратегический расчет у нее предварительный и очень осторожный, а дальнобойной проверке материала не нужно захваты­вать пространство доски. Основная слабость других шахматных программ в недостаточной позиционной оценке. Программа с подобной схемой избега­ет этих ошибок. Если у нее сорвался предварительный стратегический про­счет, и проверка материала его не одобрила, программа может просто на­чать двигать ладьей туда и обратно. Собственно говоря, она за пределами дебютных справочников не играет вовсе, пока противник не подставится. Несмотря на перечисленные недостатки, написать функцию, планирующую осторожную стратегическую игру для такой программы, очень непросто. Люди, как правило, восхищаются такими программами, но сами с ними не играют, а предпочитают что-нибудь поживее. Никому не интересно играть с вычислительным комбайном без малейшего признака фантазии.

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

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

Нулевой ход используется, как правило, для отсечения ветвей дерева без полного счета. Есть и другие использования нулевого хода (определение угрозы). Вместе с тем важно понимать, что нулевой ход является эвристи­кой, и использование его для отсечения ветвей дерева перебора возможно не во всех играх и требует особой осторожности. В шашках, например, его использование совершенно невозможно.

В чем состоит суть эвристики нулевого хода? Замечено, что в практически любой позиции в шахматах пропуск хода хуже, чем возможность сделать ход. Если у игрока есть ход, он может получить результат не хуже, чем если бы его у него не было. Исключения редки, и класс позиций, где право хода мешает, получил даже название — цуцванг. Например, в ситуации, где ферзь с королем ставят мат одинокому королю, цуцванг встречается чуть ли не на каждом ходу. Ферзь и король не нападают прямо на одинокого коро­ля, а вынуждают его двигаться навстречу гибели. Нулевой ход здесь не ра­ботает.

Как используется нулевой ход? У нас в каждом узле есть две величины — alpha и beta. Alpha — это наш максимум, достигнутый в результате счета, beta — максимум противника. Если мы в результате счета получили оценку больше или равную beta, то счет можно прекратить, т. к. он дальше не име­ет смысла. Когда перебор вернется в точку, где было достигнуто значение beta противника, результат все равно отвергается, т. к. он не больше макси­мума противника в этой точке. Данный алгоритм позволяет отсечь без ка­кой-либо погрешности ненужные ветви дерева перебора и получить резуль­тат такой же точности, как и полный перебор на данную глубину:

int AlphaBeta(int alpha,int beta, int depth) {

//закончилась глубина?

//вернем оценку узла

if( depth <= 0) return Evaluate();

//список ходов

PMove move = Generate();

while(move) {

MakeMove(move); //сделали ход int tmp = -ALphaBeta(-beta,-alpha,depth-1); UnMakeMove(move); //восстановили позицию //если результат улучшает alpha, //увеличим ее

if(tmp > alpha) alpha = tmp;

//если максимум противника,

//дальше продолжать нет смысла

if(alpha >= beta) return alpha; //или beta

//следующий ход из списка

move = move->next;

)

//вернем наш максимум return alpha;

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

int AlphaBeta(int alpha,int beta, int depth) {

//закончилась глубина? //вернем оценку узла if( depth <= 0) return Evaluate (); //null move

if(-ALphaBeta(-beta,-alpha,depth-1) >= beta)

return beta; //список ходов PMove move = Generate ();

while(move) {

MakeMove(move); //сделали ход int tmp = -ALphaBeta(-beta,-alpha, depth-1); UnMakeMove(move); //восстановили позицию //если результат улучшает alpha – //увелим ее

if(tmp > alpha) alpha = tmp;

//если сравнялись с максимумом противника

//дальше продолжать нет смысла

if(alpha >= beta) return alpha; //или beta

//следующий ход из списка

move = move->next;

}

//вернем наш максимум return alpha;

}

Выигрыш по скорости мы здесь вряд ли получим, т. к. используем нулевой ход на глубину depth-1. Вводят некоторую величину, именуемую коэффици­ентом затухания R, и выполняют нулевой ход на сокращенную глубину. Так как пропуск хода в шахматах является очень серьезным преимуществом для противника, то эвристика все равно работает. Ускорение получается очень существенное. Если нулевой ход не сработал, то мы все равно перебирали на меньшую глубину, и задержка незначительная. Если сработал — целая ветвь подрезана! Вот пример кода:

#define R 2

int AlphaBeta(int alpha,int beta, int depth) {

//закончилась глубина? //вернем оценку узла if( depth <= 0) return Evaluate(); //null move

if(-ALphaBeta(-beta,-alpha,depth-l-R) >= beta)

return beta; //список ходов PMove move = Generate();

while(move) {

MakeMove(move); //сделали ход

int tmp = -ALphaBeta(-beta,-alpha,depth-1);

UnMakeMove(move); //восстановили позицию

//если результат улучшает alpha,

//увеличим

if(tmp > alpha) alpha = tmp;

//если сравнялись с максимумом противника

//дальше продолжать нет смысла

if(alpha >= beta) return alpha; //или beta

//следующий ход из списка

move = move->next;

}

//вернем наш максимум return alpha;

}

Нулевой ход можно еще усовершенствовать. Совершенно не обязательно перебирать с полным окном, чтобы увидеть, больше результат, чем beta, или нет. Можно использовать нулевое окно:

//null move

if(-ALphaBeta(-beta,-(beta-1),depth-l-R) >= beta) return beta;

Коэффициент затухания R, обычно равный двум, позволяет получить при­емлемое качество счета. При счете на большую глубину (больше 6) можно использовать R, равный 3 или 4.

Нулевой ход может вносить погрешность и в строках, не связанных с цуц- ванг-позициями. Если обвалить напряженную строку нулевым ходом с уменьшенной глубиной просчета, это может вызвать ошибку.

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

?    Ход в данную позицию не должен быть шахом. Он и так вернет отрица­тельный ответ, нет необходимости его вызывать.

?    Этот ход не должен быть взятием. Это верно, по крайней мере, до неко­торой глубины. Взятия можно и не учитывать. Это момент тонкой инди­видуальной настройки.

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

Текущая статическая оценка узла должна быть, как минимум, равна значе­нию beta. Это условие статического поиска. Узел, удовлетворяющий выше­перечисленным условиям, можно на большой глубине отсечь и без нулевого хода. Получится простейший вариант выборочного поиска. Нулевой ход выступает теперь в качестве дополнительного проверочного условия. На­сколько текущая оценка должна быть больше beta? Существует понятие по­ля роста (margin). Его величина либо равна нулю, либо максимальному стратегическому приросту. Для нулевого хода это, как правило, 0. Величина, равная максимальному стратегическому приросту, повысит точность вычис­ления, но существенно замедлит скорость.

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

if ( UnCheck         &&

moveNotCapture       &&

!isExtensiens        &&

score – margin >= beta && ply >= 4   &&

-ALphaBeta(-beta,-alpha,depth-l-R) >= beta) return beta;

Здесь соблюдается следующий порядок условий:

1)  если не шах;

2)   если не взятие;

3)   если узел не расширяется;

4)   если текущая оценка узла и поле роста больше beta;

5)   если не первые 4 узла в строке;

6)   если результат нулевого хода больше или равен beta.

Чужно отметить, что margin = о незначительно увеличивает время счета, а тактическая прочность повышается существенно. Проверка обычно осуще­ствляется из преузла. Код, реализующий эти действия, такой:

MakeMove(move);

score = MakeScore(move); //оценка после хода check = InCheck(move); //объявляет ли ход шах :.f( !check &&      //ход не объявляет шах

moveNotCapture && //не взятие score <= alpha && //не улучшает alpha

)

{

//do null move

}

3 преузле дополнительно может использоваться следующее условие: I’. если наш король не под шахом.

Для нулевого хода это условие не является обязательным, т. к. он и сам то­чен, и достаточно условий простого статического поиска. Если смотреть из греузла, то

score + margin <= alpha означает то же самое, что

эсоге — margin >= beta

кз следующего узла. Почему предпочтительнее выполнять отсечку в преуз­ле? Так эффективнее (не нужно напрасно вызывать функцию AlphaBeta), кроме того, есть возможность проверять состояние преузла. Если некоторые ходы были продлены, то желательно иметь точный ответ на них. Это уже больше относится к выборочному статическому поиску. Для продления только шахов статической оценкой это выглядит примерно так:

int AlphaBeta(…) {

{ . . . }

PMove move = GenerateAllMoves(); while(move)

{

score = MakeScore;

if(king_is_not_in_check &&    //если наш король не под шахом

move_does_not_opponent_king && //если ход не объявляет шах score <= alpha)    //не улучшаем alpha

return alpha;

MakeMove();

//реальное вычисление

(…)

UnMakeMove();

}

return alpha;

}

Для нулевого хода такое двойное продление не обязательно. Достаточно пе­речисленных ранее условий. Хочется отметить еще раз, что нулевой ход ра­ботает и без соответствия отсекаемого узла каким-либо условиям, но в на­пряженных позициях он постоянно будет ошибаться.

Нулевой ход можно использовать для определения угрозы. Это делается до­вольно редко. Если мы после хода попробовали ход на уменьшенную глу­бину (R очень большой), и результат говорит о том, что при пропуске хода мы выигрываем материал, то данный узел можно расширить. Чтобы таких расширений было немного, в качестве функции нулевого хода можно ис­пользовать только форсированный поиск материала с нулевым окном. Он выполнится довЬльно быстро. Если этот поиск показал выигрыш материала (только ходившей фигурой), глубину счета данного узла можно не умень­шать. В этом случае нулевой ход (форсированный вариант) работает как детектор атаки. Атака определяется только для ходившей фигуры, может ли эта фигура немедленно что-то выиграть в результате размена. Нулевой ход, таким образом, не отсекает ветви дерева, а наоборот, служит для расшире­ния. Если depth не сокращается при атаке, это существенно увеличивает силу игры программы. Такие узлы обрабатываются довольно быстро, т. к. легальных ходов немного. Нужно понимать, что все это довольно условно.

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

При использовании нулевого хода нужно учесть, что его можно применять один раз в строке. Иначе поиск выродится в процесс с максимально воз­можным коэффициентом затухания R. Некоторые программы применяют нулевой ход дважды. Я не нашел, что это эффективнее. Все это — тонкая индивидуальная настройка программы. Вот пример, где использование ну­левого хода ограничено одним разом в строке:

#define R 2

int AlphaBeta(int alpha,int beta, int depth, bool doNullMove) {

//закончилась глубина?

//вернем оценку узла

if( depth <= 0) return Evaluate О;

//null move

//если не делали нулевой ход раньше if( !doNullMove   &&

-ALphaBeta(-beta,-alpha,depth-l-R,true) >= beta

)

return beta; //список ходов PMove move = Generate();

while(move) {

MakeMove(move); //сделали ход

int tmp = -ALphaBeta(-beta,-alpha,depth-1,doNullMove); UnMakeMove(move); //восстановили позицию //если результат улучшает alpha – //увелим ее

if(tmp > alpha) alpha = tmp;

//если сравнялись с максимумом противника

//дальше продолжать нет смысла

if(alpha >= beta) return alpha; //или beta

//следующий ход из списка

move = move->next;

//вернем наш максимум return alpha;

}

Литература:

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

По теме:

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