Главная » Алгоритмы, Игры » Вращенный BitBoard

0

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

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

type squares = ( a8,b8,c8,d8,e8,f8,g8,h8, a 7, Ы, с 7, d7, e7, f’7, g7, h7, a6,b6,c6,d6,e6, f6,g6,h6, a5,b5,c5,d5,e5,f5,g5,h5, a4,b4,c4,d4,e4,f4,g4,h4, a3,b3,c3,d3,e3,f3,g3,h3, a2,b2,c2,d2,e2,f2,g2,h2, al,bl,cl,dl,el,fl,gl,hl ) ;

const

_ normal:array[0..63] of squares =

(

a8,b8,c8,d8,e8,f8,g8,h8, a7, b7, c7, d7, e7, f 7, g7, h7, a6,b6,c6,d6,e6,f6,g6,h6, a5,b5,c5,d5,e5,f5,g5,h5, a4,b4,c4,d4,e4,f4,g4,h4, a3,b3,c3,d3,e3,f3,g3,h3, a2, b2, c2, d2, e2, f 2, g2, h2, al,bl,cl,dl,el,fl,gl,hl );

_ flipped:array[0..63] of squares =

(

a8,a7,a6,a5,a4,a3,a2,al, Ь8,Ь7,Ьб,Ь5,Ь4,ЬЗ,Ь2,Ы, c8,c7,сб,c5,c4,сЗ,c2,cl, d8,d7,d6,d5,d4,d3,d2,dl, e8,e7,e6,e5,e4,e3,e2,el, f8,f7,f6,f5,f4,f3,f2,fl, g8,g7,g6,g5,g4,g3,g2,gl, h8,h7,h6,h5,h4,h3,h2,hl );

_ alh8:array[0..63] of squares =

(

a8, bl,c2,d3,e4,f5,g6,h7, a7,b8, cl,d2,e3,f4,g5,h6,

а6,Ь7,с8, dl,e2,f3,g4,h5, a5,b6,c7,d8, el,f2,g3,h4, a4,b5,c6,d7,e8, fl,g2,h3, a3,b4,c5,d6,e7,f8, gl,h2, a2,b3,c4,d5,e6,f7,g8, hi, al,b2,c3,d4,e5,f6,g7,h8 ) ;

_ a8hl:array[0..63] of squares =

(

a8,b7,c6,d5,e4,f3,g2,hl, a7,b6,c5,d4,e3,f2,gl, h8, a6,b5,c4,d3,e2,fl, g8,h7, a5,b4,c3,d2,el, f8,g7,h6, a4,b3,c2,dl, e8,f7,g6,h5, a3,b2,cl, d8,e7,f6,g5,h4, a2,bl, c8,d7,e6,f5,g4,h3, al, b8,c7,d6,e5,f4,g3,h2 ) ;

_ alh8mask:TArray64 =

(

1, 2,2,2,2,2,2,2, 1,1, 2,2,2,2,2,2, 1,1,1, 2,2,2,2,2, 1,1,1,1, 2,2,2,2, 1,1,1,1,1, 2,2,2, 1,1,1,1,1,1, 2,2, 1,1,1,1,1,1,1, 2, 1,1,1,1,1,1,1,1 ) ;

_ a8hlmask:TArray64 =

(

1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1, 2, 1,1,1,1,1,1, 2,2, 1,1,1,1,1, 2,2,2, 1,1,1,1, 2,2,2,2, 1,1,1, 2,2,2,2,2, 1,1, 2,2,2,2,2,2, 1, 2,2,2,2,2,2,2 ) ;

При перемещении фигуры функция MakeMove корректирует все четыре бито­вые плоскости. Плоскости alh8 и a8hl используются для диагональных ли­ний дальнобойных фигур. Они преобразуют диагонали в горизонтальную последовательность битов. Нужно только вычислить индекс фигуры в раз­вернутой плоскости и применить маску для этой линии. Для вычисления индекса используется массив перекодировки. Рассмотрим схематичный пример для иллюстрации принципа. Для битового представления позиции используем 64-битовый тип без знака:

П в GNU С — unsigned long long;

? в Visual С — unsigned        int64;

П в Delphi — int64.

Примечание

Delphi не имеет 64-разрядного типа без знака, но из-за дружественного компи­лятора Delphi тип int64 вполне можно использовать.

Мы выбираем тип без знака по двум причинам. Во-первых, если установлен единственный знаковый бит (с номером 63 — самый старший), то число должно быть не 0.

typedef unsigned long long 164; 164 foo;

foo = (164)1 « 63;

if( foo) {

}

Некоторые компиляторы могут неоднозначно толковать эту ситуацию. Во- вторых, при типе без знака любой компилятор использует логический сдвиг, а не арифметический.

Пример:

typedef unsigned long long 164; 164 foo = ((164)1 « 63) » 63;

Мы сдвинули 1 влево на 63, а потом результат сдвинули вправо на 63. Если тип будет со знаком:

typedef long long 164;

164 foo = ((164)1 « 63) » 63;

В результате мы получим не 1, а 0 * FFFFFFFFFFFFFFFF. Вместо логиче­ского сдвига компилятор применил арифметический, и старший знаковый бит не сдвигается, а расширяется. Компилятор Delphi корректно обрабаты­вает оба случая, и его вполне можно использовать для BitBoard.

Есть еще один неприятный момент в программировании 64-разрядного BitBoard. Дело в том, что хотя тип данных и 64-разрядный, но процессоры, преимущественно, остаются 32-разрядными, и может понадобиться много инструкций для обработки некоторых команд. Так для Intel-процессоров нет команды прямого сдвига пары регистров. Компилятор может довольно эффективно сдвигать 64-битовое число на фиксированное количество би­тов, но сдвиг на непостоянное значение, в зависимости от компилятора и полноты обрабатываемой ситуации, для простой инструкции может вылить­ся в дополнительную операцию сравнения (GNU С) или даже в подпро­грамму и несколько операций сравнения (Delphi). Поэтому нужно избегать сдвига на непостоянное значение.

Для осуществления BitBoard следует познакомиться с некоторыми выраже­ниями:

?     (b AND —b) оставляет самый младший бит;

?     (b AND (b-1)) сбрасывает самый младший бит;

?     (b XOR (b— 1)) устанавливает в 1 все нулевые биты справа и оставляет самый правый ненулевой бит.

Пример кода для BitBoard:

Туре

164 = int64; TBitBoard = record case byte of 1:(bc64:164);

2:(bc32:array[0..1] of LongWord); 3:(bcl6:array[0..3] of word); 4:(bc8:array[0..7] of byte) end;

TBitRec = record

tolndex,fromIndex,maskY:array[0..63] of byte; board:TBitBoard; end;

Var

ByteFirstBitNumber:array[0..128] of byte; ByteRotate:array[0..255] of byte; Normal,F1ipped,A1H8,A8H1:TBitRec;

procedure BitBoardlnit; type squares = ( a8,b8,c8,d8,e8,f8,g8,h8, a7,b7,c7,d7,e7,f7,g7,h7, a6,b6,c6,d6,e6,f6,g6,h6, a5,b5,c5,d5,e5,f5,g5,h5,

a4,b4,c4,d4,e4,f4,g4,h4, аЗ,ЬЗ,c3,d3,еЗ,f3,g3,h3, а2, Ь2, с2, d2, е2, f 2, д2, h2, al,bl,cl,dl,el,fl, gl,hl ) ;

TArray64 = array[0..63] of byte; const

_ normal:array[0..63] of squares =

(

a8,b8,c8,d8,e8,f8,g8,h8, a7, Ы, c7, d7, el, f7, g7, h7, а6,Ь6, c6, d6, e6, f6, g6, h6, a5,b5,c5,d5,e5,f5,g5,h5, a4,b4,c4,d4,e4,f4,g4,h4, аЗ,ЬЗ,сЗ,d3,еЗ, f3, дЗ, h3, a2, Ь2, c2, d2, e2, f2, g2, h2, al,bl,cl,dl,el,fl,gl,hl ) ;

_ flipped:array[0..63] of squares =

(

a8,a7,a6,a5,a4,a3,a2,al, Ь8,Ь7,Ь6,Ь5,Ь4,ЬЗ,Ь2,Ь1, c8, c7, сб, c5, c4,сЗ,c2,cl, d8,d7,d6,d5,d4,d3,d2,dl, e8,e7,еб,e5,e4,еЗ,e2,el, f8,f7,f6,f5,f4,f3,f2,fl, g8,g7,g6,g5,g4,g3,g2,gl, h8,h7,h6,h5,h4,h3,h2,hl ) ;

_ alh8:array[0..63] of squares =

(

a8, bl,c2,d3,e4,f5,g6,h7, a7,b8, cl,d2,e3,f4,g5,h6, a6,b7,c8, dl,e2,f3,g4,h5, a5,b6,c7,d8, el,f2,g3,h4, a4,b5,c6,d7,e8, fl,g2,h3, a3,b4,c5,d6,e7,f8, gl,h2, a2,b3,c4,d5,e6,f7,g8, hi, al,b2,c3,d4,e5,f6,g7,h8 ) ;

_ a8hl:array[0..63] of squares =

(

a8,b7,c6,d5,e4,f3,g2,hl, a7,b6,c5,d4,e3,f2,gl, h8, a6,b5,c4,d3,e2,f1, g8,h7, a5,b4,c3,d2,el, f8,g7,h6, a4,b3,c2,dl, e8,f7,g6,h5, a3,b2,cl, d8,e7,f6,g5,h4, a2,bl, c8,d7,e6,f5,g4,h3, al, b8, c7, d6,e5,f4,g3,h2 );

_ alh8mask:TArray64 =

(

1, 2,2,2,2,2,2,2, 1,1, 2,2,2,2,2,2, 1,1,1, 2,2,2,2,2, 1,1,1,1, 2,2,2,2, 1,1,1,1,1, 2,2,2, 1,1,1,1,1,1, 2,2, 1,1,1,1,1,1,1, 2, 1,1,1,1,1,1,1,1 ) ;

_ a8hlmask:TArray64 =

(

1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1, 2, 1,1,1,1,1,1, 2,2, 1,1,1,1,1, 2,2,2, 1,1,1,1, 2,2,2,2, 1,1,1, 2,2,2,2,2, 1,1, 2,2,2,2,2,2, 1, 2,2,2,2,2,2,2 ) ;

function RotByte(b:byte):byte; var N:integer; ret:byte; begin

ret := 0;

for N := 0 to 7 do if (b and (1 shl N)) <> 0 then

ret := ret or (1 shl (7-N)); RotByte := ret; end;

function Mask(var data:TArray64; index:integer):byte; var

X, Y,value:integer; ret:byte; begin

ret := 0; Y := index div 8; value := data[index]; for X := 0 to 7 do begin

if data[Y*8+X] = value then ret := ret or (1 shl X);

end;

Mask := ret; end;

procedure FillMaskKingAndKnight; const

addXKnight:array[0..7] of integer = (1,1,-1,-1,2,-2,2,-2); addYKnight:array[0..7] of integer = (2,-2,2,-2,1,1,-1,-1); addXKing:array[0..7] of integer = (1,-1,1,-1,1,-1,0,0); addYKing:array[0..7] of integer = (1,-1,-1,1,0,0,1,-1); var

X,Y,N,newX,newY:integer; begin

for Y := 0 to 7 do for X := 0 to 7 do begin

MaskKnight[Y*8+X].bc64 := 0; MaskKing[Y*8+X].bc64 := 0; for N := 0 to 7 do begin

newX := X + addXKnight[N]; newY := Y + addYKnight[N]; if word(newX or newY) < 8 then with MaskKnight[Y*8+X] do

be8[newY] := bc8[newY] or (byte(l) shl newX); newX := X + addXKing[N]; newY := Y + addYKing[N]; if word(newX or newY) < 8 then with MaskKing[Y*8+X] do

be8[newY] := bc8[newY] or (byte(l) shl newX);

end; end; end;{function}

var

N:integer; b:byte; begin {main}

for b := 0 to 255 do

ByteRotate[b] := RotByte(b);

for N := 0 to 7 do

ByteFirstBitNumber[1 shl N] := N; with normal do begin for N := 0 to 63 do begin

toIndex[N] := byte(_ normal[N]);

fromIndex[N] := byte(     normal[N]) ;

maskY[N] := $FF; end;

board.bc64 := 0; end;

with Flipped do begin for N := 0 to 63 do begin

fromIndex[N] := byte(     flipped[N]);

tolndex[byte(_ flipped[N])] := N;

maskY[N] := $FF; end;

board.bc64 := 0; end;

with A1H8 do begin for N := 0 to 63 do begin

fromlndex[N] := byte(     alh8[N]);

tolndex[byte(_ alh8[N])] := N;

maskY[N] :=Mask(_ alh8mask,N);

end;

board.bc64 := 0; end;

with A8H1 do begin for N := 0 to 63 do begin

fromlndex[N] := byte(     a8hl[N]);

tolndex[byte(_ a8hl[N])] := N;

maskY[N] :=Mask(_ a8hlmask,N);

end;

board.bc64 := 0; end;

FillMaskKingAndKnight; end;

function BitNumber(var b:TBitBoard):integer; begin

with b do begin

if bc32[0] <> 0 then begin


if Ьс16[0] <> 0 then begin

if Ьс8[0] <> 0 then BitNumber := ByteFirstBitNumber[bc8[0]]

else BitNumber := ByteFirstBitNumber[bc8[1]] + 8; end else begin

if bc8[2] <> 0 then BitNumber := ByteFirstBitNumber[bc8[2]] +

16

else BitNumber := ByteFirstBitNumber[bc8[3]] + 24; end; end else begin

if bcl6[2] <> 0 then begin

if bc8[4] <> 0 then BitNumber := ByteFirstBitNumber[bc8[4]] +

32

else BitNumber := ByteFirstBitNumber[bc8[5]] + 40; end else begin

if bc8[6] <> 0 then BitNumber := ByteFirstBitNumber[bc8[6]] +

48

else BitNumber := ByteFirstBitNumber[bc8[7]] + 56; end;

end; end; end;{function}

procedure GetMoves(var rec:TBitRec; squareN:integer; var

moves:TBitBoard);

var

X,Y,index,N:integer; line,my,leftBits,rightBits:byte; begin

with rec do begin

index := tolndex[squareN]; X := index and 7; Y := index shr 3; my := byte(1) shl X;

line := board.bc8[Y] and not my and maskY[index]; rightBits := line and (my xor (my-1)); leftBits := line and not rightBits; if leftBits <> 0 then begin

N := fromlndex[ ByteFirstBitNumber! leftBits and -leftBits] + (Y shl 3)]; with moves do

bc8[N shr 3] := bc8[N shr 3] or (byte(l) shl (N and 7)); end;

if rightBits <> 0 then begin

rightBits := ByteRotate[rightBits];

N := fromIndex[ (7-ByteFirstBitNumber[ rightBits and -rightBits]) + (Y shl 3)];

with moves do

bc8 [N shr 3] := bc8 [N shr 3] or (byte(l) shl (N and 7) ) ; end; end; end;

procedure BishopAttack(squareN:integer; var moves:TBitBoard); begin

moves.bc64 := 0; GetMoves(A1H8,squareN,moves); GetMoves(A8H1,squareN,moves); end;

procedure RookAttack(squareN:integer; var moves:TBitBoard); begin

moves.bc64 := 0; GetMoves(Normal,squareN,moves); GetMoves(Flipped,squareN,moves); end;

Если мы получим маску для всех фигур, атакованных слоном, то, применив эту маску с операцией поразрядного AND к фигурам противника, мы полу­чим все фигуры противника, которые бьет данный слон:

BishopAttack(from,moves);

moves := moves and All[xside]; {выделили фигуры противника}

while moves <> 0 do

begin

item = moves and -moves; {первая атакованная фигура} to := BitNumber (TBitBoard (item) )'; LinkMove(from,to);

moves := moves and (moves-1); //очистили младший бит end;

Можно получить также все простые перемещения. Если у нас есть маска для фигур слева на линии и фигур справа на линии, то нетрудно получить простые перемещения. Они лежат посередине между этими масками. Вот фрагмент функции GetMoves с простыми перемещениями дальнобойных фигур:

index := tolndex[fSource]; X := index and 7; Y ;= index shr 3; my := byte(1) shl X;

line := board.bc8[Y] and not my and maskY[index]; rightBits := line and (my xor (my-1)); leftBits := line and not rightBits; rightBits := ByteRotate[rightBits] ;

leftMask := (leftBits xor (leftBits-1)) and not(leftBits and – leftBits);

rightMask := (rightBits xor (rightBits-1)) and not(rightBits and – rightBits);

moves := leftMask and ByteRotate[rightMask] and not my and maskY[index];

Данный код только иллюстрирует принцип и не оптимизирован. Для нор­мальной и транспонированной плоскости не нужны битовые маски. Лиш­ние промежуточные вызовы функций тоже непозволительная роскошь и т. д.

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

var

Pieces:array[pKing..pPawn] of TBitBoard; All:array[cWhite..cBlack] of TBitBoard;

Литература:

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

По теме:

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