Главная » Алгоритмы, Игры » Устаревший метод выборочного поиска

0

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

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

int ALphaBeta(int alpha, int beta, int ply …) {

mainScore = Evaluate(); //оценка узла (статическая) isCheck = inCheckO; //под шахом ли наш король Generate();

while(moveList) {

MakeMove();

nextScore = Evaluate();//оценка после хода nextCheck = inCheckO; //ход объявляет шах? //взятие?

movelsCapture = nextScore – mainScore >= wPawn; if( !isCheck && //наш король не под шахом !nextCheck && //ход не объявляет шах !movelsCapture && //ход не взятие !pawnMovesRank_7_or_2 && //не аванс пешки nextScore + margin + threat <= alpha

)

{

tmp = alpha; //подрезали )else{ //вычисление

tmp = -ALphaBeta(-beta,-alpha,ply+1,…);

}

UnMakeMove();

if(tmp > alpha) alpha = tmp; if(alpha >= beta) break;

)

Если не было шаха нашему королю, и ход не шах, не взятие, не ход пешки на предпоследнюю горизонталь, и

nextScore + margin + threat <= alpha,

где margin — поле роста оценки, threat — поле угрозы, то подрезаем целую ветвь.

Поле роста обычно изменяется от 0 до максимального стратегического при­роста. Можно поле роста делать различным, в зависимости от глубины. Если мы в двух последних узлах, и поле роста равно полпешки, то можно подрезать без поля угрозы (Futility pruning). Если мы в четырех последних узлах, и поле роста — величина королевы, то тоже можно подрезать без по­ля угрозы или сократить глубину поиска (Razoring). Как определить поле угрозы?

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

int ThreatDetect(int alpha,int beta, int square, int player,int opponent)

{

score = Evaluate(player); if(score > alpha) alpha = score; if(alpha >= beta) return alpha; GenerateAllCapture(player);//список взятий while(moveList) (

if( square != 0 &&

move->square <> square) continue; MakeMove(move);

score = -ThreatDetect(-beta,-alpha,0,

opponent,player); UnMakeMove(move); if (score > alpha) alpha = score; if (alpha >= beta) break;

}

Данный вариант работает как нулевой ход, но при первом вызове рассмат­ривает ходы только одной фигуры. Вариант функции с таким определением угрозы будет выглядеть подобно следующему:

int ALphaBeta(int alpha, int beta, int ply,

int player, //цвет наших фигур int opponent) //противника

{

mainScore = Evaluate(player); //оценка узла (статическая) isCheck = inCheck(player); //под шахом ли наш король Generate(player); //список перемещений

while(moveList) {

MakeMove(move);

nextScore = Evaluate(player);//оценка после хода nextCheck = inCheck(opponent); //ход объявляет шах? //взятие?

movelsCapture = nextScore – mainScore >= wPawn; if( !isCheck && //наш король не под шахом !nextCheck && //ход не объявляет шах !movelsCapture && //ход не взятие !pawnMovesRank_7_or_2 && //не аванс пешки nextScore + margin <= alpha && //последняя ходившая фигура не может //немедленно выиграть материал ThreatDetect(alpha,alpha+1, move->square, player,opponent) <= alpha

)

{

tmp = alpha; //подрезали )else{

//вычисление

tmp = -ALphaBeta(-beta,-alpha,ply+1, opponent,player) ;

)

UnMakeMove(move);

if(tmp > alpha) alpha = tmp;

if(alpha >= beta) break;

1

return alpha;

}

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

Литература:

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

По теме:

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