Главная » Алгоритмы, Игры » Списки фигур

0

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

1)   король;

2)   ферзь;

3)   ладьи;

4)   слоны и кони;

5)   пешки.

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

typedef struct     TItem{

int x,y;             //координаты фигуры

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

}TItem,*PItem;

Списки инициализируются один раз перед началом счета и постоянно об­новляются при переборе. Если некоторая фигура переместилась, это должно быть отражено в элементе списка, если фигура съедена, элемент списка должен быть временно удален. Для удаления элементов списков можно вве­сти вспомогательный массив, где в элементе, соответствующем фигуре, со­держится ссылка на указатель элемента списка для данной фигуры. На­пример:

unsigned char pos[8][8]; //доска с фигурами

PItem* ptrPos[8][8]; //ссылки на указатели PItem whiteList;    //список белых фигур

PItem blackList;  //список черных фигур

Используя ссылки на указатели, можно легко удалить нужный элемент из связного списка и восстановить его затем. Например, белого ферзя съели в клетке [4:4].

PItem* р = ptrPos[4][4]; ptrPos[4][4] = 0; PItem saveP = (*p);

(*p) = (*p)->next; {       }

Если нужно восстановить элемент списка:

saveP->next = (*р) ; (*р) = saveP; ptrPos[4][4] = р;

Это, в общем-то, тривиальные операции со связными списками. Рассмот­рим инициализацию связных списков:

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

tdefine FIGURE(f) ((f) S 7)      //возвращает код фигуры

#define COLOR(f) ((f) S (BLACK | WHITE)) //возвращает цвет фигуры

//вспомогательные списки белых по коду фигуры PItem wList[7] = {0,0,0,0,0,0,0};

PItem* pWList[7] = {&wList[0],&wList[1],SwList[2],SwList[3], SwList[4],SwList[5],SwList[6]};

//черных

PItem bList[7] = {0,0,0,0,0,0,0};

PItem* pBList[7] = {SbList[0],SbList[1],SbList[2],SbList[3],

SbList[4],SbList[5],SbList[6]}; static TItem data[40]; //буфер памяти под элементы списков int count = 0;

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

int f = pos [y] [x] ; if(!f) continue;

PItem p = data[count];

count++;

p->x = x;

p->y = y;

p->next = 0;

if(COLOR(f) == WHITE) {

*pWList[FIGURE(f)] = p; pWList[FIGURE(f)] = sp->next; }else{

*pBList[FIGURE(f)] = p; pBList[FIGURE(f)] = Sp->next;

}

}

//соединяем концы подсписков с началом предыдущих for(int п = 5; n >= 1; п—)

{

*pWList[n] = wList[n+1]; *pBList[n] = bList[n+1];

}

whiteList = wList[KING]; blackList = bList[KING];

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

rnemset(ptrPos,0,sizeof(ptrPos)); PItem* pp = SwhiteList;

while(*pp) {

ptrPos[(*pp)->y][(*pp)->x] = pp; pp = &(*pp)->next;

}

pp = SblackList;

while(*pp) {

ptrPos[(*pp)->y][(*pp)->x] = pp; pp = &(*pp)->next;

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

whiteList = blackList = 0;

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(FIGURE(f) != n) continue; PItem p = data[count++]; p->x = x; p->y = y;

if(COLOR(f) == WHITE) {

p->next = whiteList; whiteList = p; )else{

p->next = blackList; blackList = p;

}

}

}

являются очень эффективным средством для оптимизации генерации перемещений. Схему со списками можно упростить до предела. Инициализированные списки фигур хранятся в массиве SquareData. Мак­симальное их количество 32, т. к. фигур у противников по 16. Массив игры для счета содержит не фигуры, а номера описателей фигур в массиве SquareData или указатели на них. Описатель перемещения получается со­всем простым:

TMove = record

Nl,N2:byte; {откуда, куда пошла фигура}

end;

{массив игры}

pos:array[0..16*16-1] of byte;

Поле 8×8 находится в центре массива, а края заполнены флагом перепол­нения в виде десятичного числа 32. Каждый байт массива игры содержит вариант:

?    0 — нет фигуры;

?    2 — флаг выхода за пределы поля;

?    0..31 — номер элемента списка фигур.

Остаются свободными два старших бита в байте. Их можно использовать для выбора цвета: 64 — черная фигура, 128 — белая.

Элемент списка фигур содержит следующую информацию:

TSquare = record

N:integer;       {координата фигуры}

F:integer;      {сама фигура}

enable:boolean; {если false, фигура съедена} isMove:boolean; {фигура перемещалась хоть один раз} end;

Чтобы перебрать все свои фигуры, нужно просто просмотреть список своих фигур. После инициализации фигуры белых в массиве SquareData будут располагаться так: King, Queen, Rook, Rook, Bishop, Bishop, Knight, Knight, Pawn. Фигуры можно просмотреть хоть по убыванию весов, хоть по возрас­танию.

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

Если взяли какую-то фигуру, на доске в ее клетке запишем 0, а в элементе списка фигур сбросим флаг enable, чтобы для парных фигур не было по­вторной генерации перемещений.

Функция MakeMove, когда делается ход, может заполнить некоторую вспомо­гательную структуру, содержащую всю информацию для восстановления позиции с помощью функции UnMakeMove. Единственная сложность обстоит с флагом isMove, перемещалась ли фигура. Но если мы имеем строку игры, эту трудность можно обойти. Хочется отметить, что представление данных в шахматах является довольно сложной задачей, и до сих пор единственно верного решения не существует.

Литература:

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

По теме:

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