Главная » Игры, Пример » Силовое решение – пример простой программы

0

Здесь мы рассмотрим пример простой программы, осуществляющей так на­зываемое силовое решение: полный перебор на 6 полуходов, выборочные продления и форсированные варианты с взятиями до конца. Такая про­грамма, конечно, не будет играть очень сильно, но уровень первого разряда ей обеспечен. При хорошей оценочной функции и дебютных справочниках, она может показать и лучший результат. Но это в сторону. Наша задача сейчас состоит в построении простейшей программы, а не в погоне за ре­зультатами. Данная программа использует alpha-beta алгоритм перебора, NegaScout и сортировку перемещений по значению. Взятия сортируются по принципу MW/LVA (наиболее ценная жертва — наименее ценный напа­дающий). Остальные перемещения сортируются в три списка по значению. Хеш-таблица не будет задействована. Наша программа и так должна сосчи­тать на 6 полуходов, а отвлекаться на второстепенные вещи мы пока не бу­дем.

Сердцевиной любой шахматной программы является alpha-beta перебор:

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

if(Depth == 0) return Evaluate(); Generate();

while(moveList && alpha < beta) {

MakeMove();

int score = -AlphaBeta(-beta,-alpha,Depth-1); UnMakeMove();

if(score > alpha) alpha = score;

}

return alpha;

}

Данный алгоритм является основным улучшением полного перебора (NegaMax). Он очень чувствителен к порядку ходов. При наилучшем поряд­ке ходов он рассмотритпозиций, где N — число позиций при полном переборе. Среднее количество перемещений в шахматах равно 40. Отсюда мы можем заключить, т. к. нам надо перебрать на 6 полуходов, то при наи­лучшем порядке ходов нам нужно будет рассмотреть 64 тыс. позиций.

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

typedef struct _TItem ( int f; //фигура int x,y; //ее координаты

struct _TItem *next; //следующий элемент списка }TItem, *PItem;

Два списка, для верхних фигур и для нижних, задаются при инициализации:

PItem _upFList, _botFList;

Рассмотрим некоторые необходимые константы. Массив игры мы опреде­лим как символьный массив 8×8. Фигуры представим числами по порядку: король — 1, ферзь — 2 и т. д. Каждая клетка в массиве игры должна хра­нить также информацию о цвете фигуры: белые — 128, черные — 64. Обра­тите внимание на некоторую битовую хитрость. Максимальное число клет­ки массива (символьное без знака) составляет 255. Вот десятичные значе­ния, когда соответствующий бит установлен в 1:

номер бита     76543210

десятичное число 128 64 32 16 8 4 2 1

Таким образом, коды фигур уместятся у нас в первых трех битах. Цвет мы обозначим битами 7 и 6. Дополнительно нам потребуется информация о том, перемещалась ли фигура. Под этот флаг выделим третий бит. Это тре­буется для правильной генерации рокировок. Как вы помните, рокировку делать нельзя, если король или ладья хоть раз ходили. А они вполне могут походить и вернуться. Вот список констант, на основании сказанного:

#define KING 1 #define QUEEN 2 #define ROOK 3 #define BISHOP 4 #define KNIGHT 5 #define PAWN 6 #define MOVE 8 #define BLACK 64 #define WHITE 128

#define COLOR(f) ((f) & (BLACK | WHITE)) //цвет фигур #define FIGURE(f) ((f) & 7)   //код фигуры

#define IS_MOVE(f) ((f) & MOVE) //перемещалась ли фигура?

//выход за пределы доски

#define OutBoard(х,у) ((unsigned)(х) >= 8 || (unsigned)(у) >= 8) Определим также вес фигур:

#define W_PAWN 1000 #define W_BISHOP (3*W_PAWN) #define W_KNIGHT W_BISHOP #define W_ROOK (5*W_PAWN) #define W_QUEEN (9*W_PAWN) #define INFINITY (10*W_QUEEN) #define W_KING INFINITY

Для вычисления веса фигуры по ее коду объявим массив перекодировки:

static int _wf[7] = {0,W_KING,W_QUEEN,W_ROOK,W_BISHOP,W_KNIGHT,W_PAWN};

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

unsigned char _pos[8][8]; //позиция

static int _upFColor; //цвет верхних фигур

static TItem data[20]; //буфер памяти

PItem p = &data[0]; //указатель на первый элемент

//все клетки доски

_upFList = _botFList = NULL; //обнулим списки фигур for (int n = PAWN; n >= KING; n—)

for(int у = 0; у < 8; y++) for(int x = 0; x < 8; x++) {

int f = _pos[y][x];

if(!f || FIGURE(f) != n) continue;

p->x = x;

p->y = y;

p->f = fr­it (COLOR (f) == _upFColor) {

//вставка в начало списка верхних фигур p->next = _upFList; _upFList = р; }else{

//вставка в начало списка нижних фигур p->next = _botFList; _botFList = р;

}

р++; //указатель на следующий элемент буфера

)

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

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

static unsigned char pos[8][8] =

{

{ROOK116|BLAK, KNIGHT116|BLACK, BISHOP116|BLAK, QUEEN 116 I BLACK, KING|BLACK,

BISHOP I BLACK, KNIGHT|BLACK,ROOK|BLACK}; { . ..} //и так все фигуры } ;

Фигуры в левой половине доски помечаются дополнительным флагом 16. Это их отличает от фигур того же цвета в правой половине доски. Черные вверху, белые — внизу. Перед тем как написать функцию счета, представим основную схему нашей программы. Осуществляется полный перебор на глубину 6 с выборочным продлением шахов. Когда глубина становится рав­ной нулю или превышает максимально допустимую, вызывается функция форсированного поиска, рассматривающая только взятия до конца. Мы ис­пользуем алгоритм NegaScout и амортизацию отказов. Схема программы примерно следующая:

//оценка позиции

int Evaluate() {

{…} //подсчитаем оценку

//лучше это делать пошагово

}

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

?    для короля в начале игры таблица задавала приоритет его горизонтали и углов, в конце игры — приоритет центра;

?    для королевы позиционная оценка заключалась в штрафе от расстояния до короля противника;

?    для коней — приоритет центра;

D для слонов — приоритет центра и ключевых диагоналей;

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

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

?    пока ферзь противника на доске, можно попытаться сохранить пешеч­ный экран короля;

?    можно давать премии для X-ray атаки (одна дальнобойная фигура стоит позади другой);

?    можно давать штрафы зависающим фигурам;

?    можно оценивать потенциальное давление на короля;

?    можно содействовать ладьям после дебюта занять открытые вертикали и давать небольшой штраф в зависимости от расстояния до враждебного короля.

Для первой программы не нужно гнаться за сложной оценочной функцией, можно ограничиться таблицами средних значений для каждой фигуры (см. главу 2). Написание хорошей оценочной функции — сложная задача, тре­бующая шахматных знаний и долгого времени. Готовых рецептов здесь нет. Можно воспользоваться и простейшей оценкой, одной для всех фигур, но следует учесть, что для хорошей игры с такой оценкой нужен более глубо­кий просчет и развитая (я бы даже сказал, интеллектуальная) система выбо­рочных продлений. В данной программе мы продлеваем только шахи. Код приведен в следующем листинге:

//форсированный вариант

int Quies(int alpha, int beta, int ply) {

int score = Evaluate(); //оценка текущего узла int res = -INFINITY, //результат просчета

tmp;

//повышаем alpha статической оценкой if(score > res) res = score; if(res > alpha) alpha = res; if(alpha >= beta) return alpha; //все взятия в отсортированном порядке PMove move = GenerateAndSortCaptures();

while(moveList) {

//если съели короля, дальше не считаем //возвращаемая оценка с поправкой на глубину, //чтобы не оттягивать мат if(eatKing) return INFINITY-ply; MakeMove();

tmp = -Quies(-beta,-alpha,ply+1); UnMakeMove(); if(tmp > res) res = tmp; if(res > alpha) alpha = res; if(alpha >= beta) return alpha;

}

return res;

}

//основной поиск

int Search(int alpha, int beta, int Depth, PMove bestMove, int ply) {

//выборочные продления при шахе if(InCheck()) Depth++; Depth—;

//если исчерпана глубина счета или превысили //максимальную глубину, вернем //результат форсированного поиска if(Depth <=0 II ply > MAX_PLY) return Quies(alpha,beta); int res = -INFINITY, //результат счета tmp;

//все перемещения в отсортированном порядке PMove move = GenerateAndSortAllMoves(); while(moveList) (

if(eatKing) tmp = INFINITY-ply; else{ // NegaScout

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

tmp = -Search(-(alpha+1),-alpha,Depth,NULL,ply+1); if(tmp > alpha && tmp < beta)

tmp = -Search(-beta,-tmp,Depth,NULL,ply+1); UnMakeMove(); //восстановили позицию

}

if(tmp > res) res = tmp;

if(res > alpha) {

alpha = res; //вернули лучший ход при первом вызове

if(bestMove) memcpy(bestMove,move,sizeof(TMove));

}

if(alpha >= beta) return alpha;

//проверка на пат //если перемещался только король, //и на следующем ходу его съели, //и он не под шахом в данной позиции, //результат равен 0: ничья if(moveOnlyKing && !inCheck() && res == -(INFINITY-(ply+1))

)

res = 0;

return res; //вернем всегда результат отсечки

}

///////////////// первый вызов /////////////// TMove bestMove; //сюда запишется найденный ход

//инициализируем списки фигур и глобальные переменные { … }

Search(-INFINITY,INFINITY,6,SbestMove,0); /////////////// end //////////////////////////

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

//характеристика хода

typedef enum{ S_MOVE. //простое перемещение S_l, //рокировка

S_2   //взятие пещкой через битое поле

} TMoveDesc; typedef struct _TMove{ int f; //фигура int xl,yl; //откуда пошла int x2,y2; //куда пошла

TMoveDesc moveDesc; //характеристика хода struct _TMove *next; //следующий элемент списка

}

Функция, делающая ход на доске, может выглядеть как:

void MakeMove(PItem item, //элемент списка фигур PMove move //описатель хода

)

{

switch(move->moveDesc) {

case S_MOVE: //простое перемещение {

int newF = move->f | MOVE;//фигура на новом месте

//с флагом перемещения //если пешка дошла до последней горизонтали, //превратится в ферзя

if (FIGURE (move->f) == PAWN && (move->v2==7 || move->y2=0) )

newF = (move->f S (~7)) | QUEEN | MOVE; //изменения в позиции

_pos[move->yl][move->xl] = 0;    //убрали фигуру

_j?os[move->y2][move->x2] = newF;//поставили фигуру //изменения в списке фигур item->x = move->x2; item->y = move->y2; item->f = newF; (break; case S_1:{

//рокировка {…}

(break; case S_2:{

//взятие пешкой через битое поле (…)

}

} //switch

}

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

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

Литература:

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

По теме:

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