Главная » Алгоритмы, Игры » Атака дальнобойных фигур

0

Давней мечтой шахматных программистов является генерация взятий даль­нобойных фигур, не строя линии. Генерация взятий является самым кри­тичным по времени выполнения фрагментом программы. Дело в том, что больщинство позиций можно отсечь только взятиями, и даже не обязатель­но иметь весь список перемещений. Кроме того, взятия в форсированном поиске рассматриваются до конца. Генерация перемещений на глубине 20 намного больше влияет на скорость выполнения программы, чем на глуби­не 5. Для ускорения получения взятий существует много методик. Мы рас­смотрим только один старый и очень простой прием. Идея следующая: ос­новная масса перемещений после хода некоторой стороны не изменяется, за исключением некоторых ходов, связанных с последней ходившей фигу­рой. Например, если пешка пересекла линию ферзя, то ферзь уже не может бить по этой линии. Остальная масса перемещений осталась без изменений. Изменились только ходы пешки и ферзя, которому она перекрыла линию. Мы сейчас, для простоты, не будем рассматривать, как можно корректиро­вать перемещения всех фигур при ходе, а рассмотрим только дальнобойные фигуры. Введем некоторый массив, где будут представлены все фигуры на доске, независимо от цвета и веса. Их можно представить как ферзи без учета цвета. Даже если это пешка, мы ее будем рассматривать как ферзя, потому что она так же может перекрыть линию дальнобойной фигуре. Ферзь, как известно, объединяет в себе ходы всех дальнобойных фигур. Каждая клетка нашего нововведенного массива будет иметь 8 ссылок на ближайшие фигуры по всем лучам. Наш массив будет иметь размерность не 8 х 8, а 10 х 10. По краям находятся лишние описатели. Даже если по ли­нии фигуры нет, ссылка все равно будет указывать на некоторый элемент, а именно на ближайший за пределами доски. Если нам нужно убрать некото­рую фигуру, мы просто должны восстановить все перекрестные ссылки. Фигура справа, например, будет ссылаться на фигуру слева. Чтобы поста­вить фигуру в новое место, мы должны просканировать 8 лучей во всех на­правлениях до первой фигуры или до края доски и навести перекрестные ссылки. В действительности, нам нужно сканировать не 8 лучей, а 4. Когда мы нашли фигуру справа, она уже ссылается на фигуру слева, и ее искать и строить линию не нужно. Таким образом, при каждом ходе мы строим до­полнительно только 4 луча, но можем выбирать взятия дальнобойных фи­гур, не строя линии. Если это ладья, то нужно просто проверить ссылки по вертикали и горизонтали, не указывают ли они на фигуры противника. Об­ратите внимание, что если одна фигура бьет другую, то все остается без из­менений, и никаких лучей строить не нужно. Когда на глубине идет поиск одних взятий, это позволяет очень быстро вычислять результат размена дальнобойных фигур. При некоторой изощренной технике можно брать взятия с фронта. Мы просто просматриваем список фигур противника, на­чиная с самых ценных, и сразу видно, какие фигуры их бьют. Далее приве­ден пример кода, дающего возможность брать взятия дальнобойных фигур, не строя линий:

/*

*** Массив атаки ***

#include <string.h> typedef unsigned choir byte; //фигуры

typedef enum{EMPTY,KING,QUEEN,ROOK,BISHOP,KNIGHT,PAWN,OUT}; //цвета

typedef enum{CWHITE,CBLACK,COUT}; //клетка основного массива игры typedef struct{

byte piece,        //фигура

color, //ее цвет

pieceTablndex, //индекс в списке фигур isMove; //перемещалась ли фигура

}TSquare,*PSquare; /*

массив игры

поле 8*8 находится посередине по краям piece = OUT приращения при построении линии

*/

typedef TSquare TBoard[10*10]; /////////////// список фигур //////////// int PieceTab[32+l]; //элемент массива атаки typedef struct)

byte left, right, up, down, vl, vll, v2, v21;

}TVec,*PVec; /*

массив атаки

*/

typedef TVec TVecPos[10*10]; ////////////// GLOBAL VAR //////////// static TVecPos _pos;

удаляет элемент с индексом start из массива атаки

void RemoveVec(int start) {

PVec item;

item = &_pos[start]; _pos[item->right].left = item->left; _pos[item->left].right = item->right; _pos[item->up].down = item->down; _j>os[item->down].up = item->up; _pos[item->vl].vll = item->vll; _pos[item->vll].vl = item->vl; _pos[item->v2].v21 = item->v21; _pos[item->v21],v2 = item->v2; }//function

вставляет элемент с индексом N на старое место

************************************************** j

void BackVec(int start, PVec item) {

_pos[item->right].left = start; _pos[item->left].right = start; _j?os [item->down] .up = start; _pos[item->up].down = start; _pos[item->v2].v21 = start; _pos[item->v21].v2 = start; _pos[item->vl].vll = start; _pos[item->vll].vl = start; _pos[start] = (*item) ; }//function

вставляет элемент с индексом start в _pos

void InsertVec(int start, TBoard gamePos) {

TVec item; int N;

//сканируем все лучи и связываем ссылки ///// горизонтальные лучи ////////// N = start+1;

while(gamePos[N].piece == 0) N++;

item, right = N;

item.left = _pos[N].left;

lllllllllll вертикальные лучи 111111111111111 N = start-10;

while(gamePos[N].piece == 0) N-=10; item.up = N;

item.down = _pos[N].down;

N = start-9;

while(gamePos[N].piece == 0) N-=9;

item.v2 = N;

item.v21 = _pos[N].v21;

N = start-lb-

while (gamePos [N] .piece == 0) N-=11; item.vl = N; item.vll = _pos[N].vll; BackVec(start,Sitem); (//function

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

void InitAttack(TBoard gamePos) {

/*

0123456789 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 */

int n,k;

memset (_pos, 0,sizeof(TVecPos)); {/////////// восходящие (/) диагонали

static int sourceV[] = {10,20,30,40,50,60,70,80,90,

91,92,93,94,95,96,97,98, 100};

static int destV[] = {1,2, 3, 4, 5, 6, 7, 8, 9,

19,29,39,49,59,69,79,89, 100};

for(n = 0; sourceV[n] != 100; n++) {

_pos[ sourceV[n] ],v2 = destV[n]; _pos[ destV[n] ].v21 = sourceV[n];

}

}///////////// end /////////////////// {///////////// нисходящие (\) диагонали ///////// static int sourceN[] = {80,70,60,50,40,30,20,10,0,

1, 2, 3, 4, 5, 6, 7, 8, 100}; static int destN[] = {91,92,93,94,95,96,97,98,99,

89,79,69,59,49,39,29,19, 100};

for(n = 0; sourceNfn] != 100; n++) {

_pos[ sourceN[n] ].vll = destN[n]; _pos[ destN[n] ].vl = sourceN[n];

}

}////////// end /////// //// вертикали I III I

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

_pos[n].down = n + 90; _pos[n+90].up = n;

}

1111 горизонтали 111111

for(n = 10; n <= 80; n+=10) {

_pos[n].right = n + 9; _pos[n+9].left = n;

}

//вставим фигуры for(n = 0; n < 100; n++)

if(gamePos[n].piece != EMPTY && gamePos[n].piece != OUT) InsertVec(n,gamePos); }//function /*

обнуляет основной массив игры и устанавливает флаги по краям

*/

void ClearMainPos(TBoard board) {

int x,y;

memset(board,0,sizeof(TBoard));

for(у =0; у < 10; у++) for(x = 0; х < 10; х++)

if (у == 0 | | у = 9 || х == 0 || х = 9) {

PSquare р;

р = &board[y*10 + х]; p->piece = OUT; p->color = COUT;

}

TBoard board; int main (void)

TVec item; ClearMainPos(board); InitAttack(board); InsertVec(44,board); item = _pos[44]; RemoveVec (44) ; BackVec(44,&item) ; return 0;

Литература:

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

По теме:

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