Главная » Алгоритмы, Игры » Сортировка взятий (MVV/LVA)

0

Это очень важная тема для шахмат. Взятия — это ходы, дающие наиболее значительное приращение оценки. Для ускорения alpha-beta поиска они должны рассматриваться первыми. Во многих позициях не обязательно ге­нерировать все перемещения, достаточно рассмотреть взятия, и они уже вы­зовут отсечку за beta. В шахматах есть еще статический поиск, где взятия рассматриваются до конца. Эта тема будет рассмотрена позже, пока лишь мы должны знать, что для статического поиска порядок ходов имеет наи­важнейшее значение, иначе это вызовет взрыв дерева поиска, и программа будет считать недопустимо долго. Мы уже рассматривали alpha-beta и пом­ним, что этот алгоритм работает принципиально быстрее при наилучшем порядке ходов. Если N — число позиций, которые программа должна рас­смотреть при полном переборе (N равно W в степени D, где W — пример­ное количество ходов в одной позиции, D — глубина просчета), то alpha-

beta с наилучшим упорядочиванием ходов рассмотрит л/Т/ позиций. Ско­рость счета зависит от мощности процессора, порядка ходов, задержки про­граммы в каждой позиции. Задержка обуславливается многими факторами, главный из которых — генератор ходов. Если бы мы написали программу, которая не задерживалась бы в одной позиции (т. е. генератор ходов был бы совмещенным с функцией счета), мы повысили бы количество рассматри­ваемых в секунду позиций. Может, нет смысла сортировать перемещения? Давайте рассмотрим следующий пример. Допустим, мы считаем на 8 полу­ходов, и среднее количество ходов в одной позиции равно 40. Допустим, наша программа с сортировкой ходов рассматривает 100 тыс., а без сорти­ровки — 2 млн позиций в секунду.

При наилучшем порядке ходов медленная программа с сортировкой будет считать достаточно быстро, т. к. размер дерева перебора качественно мень­ше. Заметьте, что alpha-beta с наихудшим порядком ходов переберет столько же позиций, сколько и полный переборщик. Это значит, что программа в реальном времени не сможет сосчитать на 8 полуходов при наихудшем по­рядке перемещений. Чтобы сосчитать за 65 секунд на 8 полуходов, она должна в секунду рассматривать примерно 100 млрд позиций в секунду. Даже DeepBlue не обладает подобной мощью. Но что такое 8 полуходов? Считать надо значительно дальше. Хотя задержка в каждой позиции и влия­ет на скорость, тем не менее порядок ходов намного важнее.

Упорядочивая перемещения, можно просчитать только до некоторой глуби­ны, а если учесть, что идеальный порядок ходов недостижим, полный пере­бор на 10 полуходов выглядит вообще довольно проблематичным. Чтобы считать на такую глубину, нужно применять методы подрезки дерева пере­бора. В шахматах, чтобы программа играла на мастерском уровне, нужна глубина перебора 10—12 полуходов, как минимум. Дальше считается не все (об этом позднее). Нужно достичь невозможного.

Итак, мы убедились, что сортировка перемещений важна, особенно сорти­ровка взятий. В форсированных вариантах сортировка взятий имеет прин­ципиальное значение. Как же осуществляется сортировка взятий? Первыми должны идти наиболее ценные взятия. Например, сначала взятия ферзя, потом ладьи, потом слона и коня, потом пешек. Если взяли короля — ко­нец просчета. Причем, замечено, что потенциально лучше те взятия, когда наименее ценная фигура пытается захватить наиболее ценную. Например для взятий ферзя: сначала будут рассмотрены пешка—ферзь, потом слон(конь)—ферзь, ладья—ферзь, ферзь—ферзь, король—ферзь. Этот алго­ритм называется MW/LVA (наиболее ценная жертва — наименее ценный нападающий). Как же его осуществить на практике? У нас уже есть ини­циализированные списки фигур по убыванию веса фигур, причем код фигу­ры косвенным образом характеризует вес фигуры. Сначала в списке идет король (1), потом — ферзь (2), потом — ладьи (3), потом — кони (4), по­том — слоны (5), потом — пешки (6). В генераторе ходов используется мас­сив связных списков по коду фигуры. Взятия вставляются в начало каждого списка. В списке пешек, например, первым будет вставлено взятие король- пешка (наихудшее). Потом его вытеснит ферзь—пешка, и т. д. После про­верки всех взятий просматриваются все списки, начиная с наибольших взя­тий. Вот код, иллюстрирующий сказанное:

//списки взятий

PMove eatList[7] = {0,0,0,0,0,0,0}; //буфер для описателей взятий TMove data[300];

PMove ptr = &data[0]; //первый свободный описатель //возвращает 1, если выход за пределы доски

#define OutBoard(х,у) ((unsigned) (х) >= 8 I I (unsigned) (у) >= 8)

//просматриваем список наших фигур

PItem item = whiteList; //наши фигуры белые

while(item) {

int f = pos[item->y][item->x]; //фигура

switch(FIGURE(f)) {

case QUEEN:{

static int addXQueen[8] =  {1,-1,1,-1,1,-1,0,0};

static int addYQueen[8] =  {1,-1,-1,1,0,0,1,-1};

for(n = 0; n < 8; n++) {

fx = item->x + addXQueen[n]; fy = item->y + addYQueen[n];

while(!OutBoard(fx,fу)) {

eatF = pos[fy][fx];

if(!eatF) {

fx += addXQueen[n]; fy += addYQueen[n]; continue;

}

if(COLOR(eatF) != BLACK) break; //не съели ли короля?

if(FIGURE(eatF) == KING) return INFINITY-ply;

//заполним описатель ptr->x = fx;

{ … } //все поля описателя перемещения //вставим в начало списка ptr->next = eatList[FIGURE(eatF)]; eatList[FIGURE(eatF)] = ptr; ptr++; //следующий свободный описатель break; (//while (//for (break; case BISHOP:{ //. . . (break;

case … //все фигуры }//switch

item = item->next;//следующая фигура (//while

//просмотрим все взятия, начиная с наибольших

for(п = QUEEN; n <= PAWN; п++) {

(…) //необходимая инициализация переменных MakeMove(…);

score = -AlphaBeta(-beta,-alpha,…); UnMakeMove(…);

{…} //обработка результата просчета

(

Данный код требует некоторого пояснения. Массив eatList содержит нача­ла списков взятий. Номер списка в массиве соответствует коду взятой фигу­ры. Массив data используется в качестве буфера памяти для организации связных списков. Это стековая переменная, и собственно элементы списков содержатся в буфере. В данном примере генерация взятий объединена с функцией счета, нет отдельной функции генерации перемещений. Буфер data, таким образом, располагается в стеке функции счета alpha-beta. После поиска взятий и помещения их в списки в отсортированном порядке эти списки просматриваются, начиная с наибольших взятий, и сразу рекурсив­но вызывается функция AlphaBeta для расчета данного перемещения. Гене­рацию взятий можно выполнить и в виде отдельной функции. Тогда полу­ченные списки надо соединить, начало одного с концом другого. Макрос OutBoard возвращает 1, если есть выход за пределы доски. Для уменьшения операций сравнения знаковый тип приводится к беззнаковому. Здесь не­большая хитрость двоичной арифметики: если —1 со знаком привести к без­знаковому, то получится число, явно большее, чем 7 — максимальный до­пустимый индекс. В качестве примера приводятся только перемещения ферзя. Массивы addXQueen и addYQueen содержат приращения при движении ферзя по лучу с номером п. Это, конечно, самый простой способ получения перемещений.

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

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

Литература:

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

По теме:

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