Bitboard в программировании шахмат №2
11 Дек 2022 09:37 #92
Vladimirovich wrote:
Вот тут всевозможные операции для битбордов через битовые же операции
Когда я размышлял об этом, то склонился к варианту формирования 64 битного числа повернутого битбоарда всех фигур на доске одновременно с формированием битборда с нормальным расположением бит.
//0-KING, 1-QUEEN, 2-ROOK, 3-BISHOP, 4-KNIGHT, 5-PAWN
//массивы фигур
WPieceArray: array [0..5] of UInt64 = (0,0,0,0,0,0);
BPieceArray: array [0..5] of UInt64 = (0,0,0,0,0,0);
//Белые и черные фигуры в одном 64 битном числе
WhitePieceU64:UInt64 = 0;
BlackPieceU64:UInt64 = 0;
//все фигуры в одном 64 битном числе
AllPieceU64:UInt64 = 0;
//Белые и черные фигуры в одном 64 битном числе
//в повернутом на 90 битбоарде
WhitePieceU64R90:UInt64 = 0;
BlackPieceU64R90:UInt64 = 0;
//все фигуры в одном 64 битном числе
//в повернутом на 90 битбоарде
AllPieceU64R90:UInt64 = 0;
//функция парсинга fen строки в массивы фигур WPiece, BPiece
//0-KING, 1-QUEEN, 2-ROOK, 3-BISHOP, 4-KNIGHT, 5-PAWN
function FenToU64(sfen:String):boolean;
var
// i - индекс массива
// k - длина строки fen
// n - счетчик шахматных клеток (64 клетки)
// num - позиция символа в strN или strF
i,k,n,num:integer;
//строки для цифр из fen строки - strN, фигур - strF, единичного символа - s01
strN,strF,s01:string;
//массивы фигур
WPieceNew: array [0..5] of UInt64;
BPieceNew: array [0..5] of UInt64;
begin
//если fen строка пустая, то ошибка fen строки
result:=false;
if sfen='' then exit;
// инициализация строк для парсинга fen строки
strN:='12345678';
strF:='KQRBNPkqrbnp';
//инициализация локальных массивов фигур
for i := 0 to 5 do begin
WPieceNew[i]:=0;
BPieceNew[i]:=0;
end;
WhitePieceU64:=0;
BlackPieceU64:=0;
WhitePieceU64R90:=0;
BlackPieceU64R90:=0;
//определяем длину fen строки
k:=length(sfen);
//сбрасываем счетчик
n:=-1;
//перебираем символы fen строки
for i := 1 to k do begin
//берем один символ fen строки на позиции i
//возвращает подстроку строки sfen начинающуюся с индекса i длиной 1 символ
s01:=copy(sfen,i,1);
//возвр. позицию символа s01 в строке strN, если нет символа, то 0
//сначала проверяем s01 - это цифра?
num:=pos(s01,strN);
//continue прерывает только выполнение текущей итерации,
//текущего выполнения тела цикла
//и передает управление на следующую итерацию.
if s01='/' then continue;
//если пробел заканчиваем парсинг
if s01=' ' then break;
//увеличиваем счетчик шахматных клеток n
// если num=0, значит символ s01 фигура
if num=0 then begin
n:=n+1;
// иначе цифра
end else begin
n:=n+num;
end;
//если клеток больше 64(0..63), то ошибка fen строки
if n>63 then exit;
//проверяем s01 - это символ фигуры?
num:=pos(s01,strF);
//если num - это не допустимый символ, то ошибка fen строки
if ((num=0) and (pos(s01,strN)=0))then exit;
//заносим фигуры в массивы
if num>0 then begin
if num<7 then begin
WPieceNew[num-1]:=WPieceNew[num-1] or MaskOneBit[n];
//белые фигуры в одно 64 битное число
WhitePieceU64:=WhitePieceU64 or WPieceNew[num-1];
WhitePieceU64R90:=WhitePieceU64R90 or MaskOneBit[RotatePos(n,90)];
end else begin
BPieceNew[num-7]:=BPieceNew[num-7] or MaskOneBit[n];
//черные фигуры в одно 64 битное число
BlackPieceU64:=BlackPieceU64 or BPieceNew[num-7];
BlackPieceU64R90:=BlackPieceU64R90 or MaskOneBit[RotatePos(n,90)];
end;
end;
end;//for
//если клеток не равно 64(0..63), то ошибка fen строки
if n<>63 then exit;
//если королей не равно 1, то ошибка fen строки
if CountBitsInt64(WPieceNew[0])<>1 then exit;
{
ShowMessage('Белый король на поле - ' +
IntToStr(SeniorBit(WPieceNew[0],WPieceNew[0] shr 32)-1) +' '+ IntToStr(JuniorBit(WPieceNew[0],WPieceNew[0] shr 32)));
}
if CountBitsInt64(BPieceNew[0])<>1 then exit;
// заполняем глобальные массивы фигур WPiece,BPiece
for i := 0 to 5 do begin
WPieceArray[i]:=WPieceNew[i];
BPieceArray[i]:=BPieceNew[i];
end;
//все фигуры в одно 64 битное число
AllPieceU64:=WhitePieceU64 or BlackPieceU64;
AllPieceU64R90:=WhitePieceU64R90 or BlackPieceU64R90;
//ShowMessage('парсинг завершен успешно');
//парсинг завершен успешно
result:=true;
end;
WhitePieceU64R90:=WhitePieceU64R90 or MaskOneBit[RotatePos(n,90)];
BlackPieceU64R90:=BlackPieceU64R90 or MaskOneBit[RotatePos(n,90)];
AllPieceU64R90:=WhitePieceU64R90 or BlackPieceU64R90;
a:=n and 7;//0..7 горизонталь (буквы)
b:=n shr 3;//0..7 вертикаль (цифры)
best:=ABS(a-a0)+ABS(b-b0);
if (KnightAttak[n] and WPieceArray[1])>0 then best:= best+2;
if best>=max then begin
j:=n;
max:=best;
end;
Bitboard в программировании шахмат №2
16 Дек 2022 19:10 #97
alexlaw wrote:
Вот этот алгоритм реализовал за черного короля
За белого ферзя задача оказалась не так проста.
Сам по себе ход ферзя нельзя оценить без последующего хода черного короля.
Отсюда следует, что нужно просчитать позицию на некоторую глубину и на этой глубине сделать оценку.
И тут на сцену выходит один из столпов шахматного программирования - алгоритм мини-макс.
Именно для задачи неприкосновенный король есть еще один путь - совершенно простой, но трудоемкий.
Путь такой - создать массив [64],[64] , где первый индекс - позиция белого ферзя, второй индекс - позиция черного короля, в ячейке будет находится ход ферзя.
Как заполнить программно такой массив?
Любые идеи приветствуются.
Bitboard в программировании шахмат №2
18 Дек 2022 08:52 #98
У меня появился план для заполнения таблицы - непрекосновенный король.
Создать шахматную игру в формате PGN.
Затем написать небольшую прогу для перегона PGN в таблицу.
Вот PGN для мата короля в ближайшем углу к белому королю.
Мат в 12 ходов.
Теперь нужно перегнать короля из дальнего угла в ближний.
По идее нужно 11 ходов
Q7/8/2K5/8/8/8/8/7k w - - 0 1
Справедливо это или нет?
Не более 11 ходов.
Надо быть очень хорошим шахматистом, чтобы загнать короля в противоположный угол за 11 ходов.
Bitboard в программировании шахмат №2
18 Дек 2022 23:42 #101
Человек намного быстрее ставит мат, ходов в 5-6. 1.Фа2 отсекаем короля потом идем королем напротив Крd5-e4-f3 и ставим мат. Во втором случае 1.Фg6 и т.п..
Очевидно алгоритм не оптимален.
Bitboard в программировании шахмат №2
20 Дек 2022 20:31 #104
alexlaw wrote:
У меня появился план для заполнения таблицы - непрекосновенный король.
Создать шахматную игру в формате PGN.
Затем написать небольшую прогу для перегона PGN в таблицу.
Суть - если есть файл test.txt, он подгружается в прогу.
Этот файл и есть таблица ходов ферзя.
Если файла нет он создастся.
Загружается файл PGN - king.pgn
Он имеет такой вид
Затем кликаем по игровому полю.
Файл PGN проигрывается и заполняется таблица, которая затем сохраняется в файл - test.txt
Затем можно перезапустить прогу с другим PGN и таблица дополнится.
В PGN должен быть один вариант без ветвлений. (Проверка не производится)
Возможны еще улучшения проги.
Например в таблицу сразу могут быть добавлены все ходы в данное поле из других клеток.
В общем считаю я справился с задачей "неприкосновенный король".
Далее вернусь к основной теме.
Bitboard в программировании шахмат №2
11 Янв 2023 20:52 #105
Размышляя над эффективностью какого либо алгоритма, конечно встает вопрос, как именно оценить эффективность.
Разумеется есть много путей и методов оценки.
Так вот, пока я решил оценивать - засечками времени.
Если оценивать какой то очень короткий кусок кода, то лучше в тактах процессора.
Если несколько функций, то лучше с помощью профайлера.
Для начала я буду оценивать расчет атак и ходов только дальнобойных фигур.
На самом деле от принципа расчета этих атак будет зависть скорость работы программы.
Кстати, задача о неприкосновенном короле как нельзя лучше подходит для выбора принципа расчета этих атак.
Функция засечек времени
//Start, Stop: cardinal;
//Elapsed: cardinal;
//засекли начало выполнения операции
// GetTickCount - uses Windows
//Start:=GetTickCount;
//засекли окончание выполнения операции
//Stop:=GetTickCount;
//время в миллисекундах
//Elapsed:=Stop-Start;
//TimeCount(Elapsed);
procedure TimeCount(Ms : cardinal);
var
H, M, S : Integer;
begin
//Время, выраженное в миллисекундах. 40 часов 3 минуты 2 секунды и 100 миллисекунд.
//Ms := 40 * 60 * 60 * 1000 + 3 * 60 * 1000 + 2 * 1000 + 100;
//Часы.
H := Ms div (60 * 60 * 1000);
Ms := Ms mod (60 * 60 * 1000); //Остаток.
//Минуты.
M := Ms div (60 * 1000);
Ms := Ms mod (60 * 1000); //Остаток.
//Секунды.
S := Ms div 1000;
//Миллисекунды.
Ms := Ms mod 1000; //Остаток.
//uses Dialogs,SysUtils,
//ShowMessage
//Ответ.
ShowMessage(
'Время:'
+ #13#10'Часы: ' + IntToStr(H)
+ #13#10'Минуты: ' + IntToStr(M)
+ #13#10'Секунды: ' + IntToStr(S)
+ #13#10'Миллисекунды: ' + IntToStr(Ms) );
end;
Второй важный момент.
Нужен эталон, т.е. проверка правильности работы алгоритма.
Таким эталоном я считаю прогу - Quick Perft by H.G. Muller написанной на СИ
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
/***************************************************************************/
/* Move generator based on separate Slider/Leaper/Pawn tables . */
/***************************************************************************/
#define FAKE 3
#define MAXTIM 0
#if MAXTIM
/* For detailed timings (MAXTIM=20) we need assembly routine to read TSC */
#define TIME(A) times[A] += rdtsc()-3;
int times[MAXTIM];
char *(names[MAXTIM])={"pintest", "contact", "castle", "ep-capt", "capture",
"pawns", "leapers", "sliders", "filter", "king ",
"do ", "undo ", "recapt.", "", "", "", "", "total "};
#else
#define TIME(A)
#endif
/* Zobris key layout */
#define Zobrist(A,B) (*(long long int *) (Zob[(A)-WHITE] + (B)))
#define XSIZE (8*1024)
union _bucket
{
struct { // one 32-byte entry
unsigned long long int Signature1;
unsigned long long int Signature2;
unsigned long long int longCount;
unsigned long long int Dummy;
} l;
struct { // two packed 16-byte entries
unsigned long long int Signature[2];
unsigned int Count[2];
unsigned int Extension[2];
} s;
} *Hash, ExtraHash[XSIZE];
/* capture codes */
#define C_ORTH 1
#define C_DIAG 2
#define C_KNIGHT 4
#define C_SIDE 8
#define C_FORW 0x10
#define C_FDIAG 0x20
#define C_BACKW 0x40
#define C_BDIAG 0x80
#define C_FERZ (C_FDIAG|C_BDIAG)
#define C_WAZIR (C_SIDE|C_FORW|C_BACKW)
#define C_KING (C_FERZ|C_WAZIR)
#define C_BISHOP (C_FERZ|C_DIAG)
#define C_ROOK (C_WAZIR|C_ORTH)
#define C_PPAWN (C_FDIAG)
#define C_MPAWN (C_BDIAG)
#define C_QUEEN (C_BISHOP|C_ROOK)
#define C_CONTACT (C_KING|C_KNIGHT)
#define C_DISTANT (C_ORTH|C_DIAG)
/* board codes (32 per side: each 16 Pieces, 16 Pawns) */
#define WHITE 0x20
#define BLACK 0x40
#define COLOR (BLACK|WHITE)
#define GUARD (COLOR|0x80)
#define DUMMY (WHITE-1+0x80)
#define PAWNS 0x10
#define NPCE (2*WHITE)
#define KING 7
#define QUEEN 6
#define ROOK 5
#define BISHOP 4
#define KNIGHT 3
/* overlays that interleave other piece info in pos[] */
#define kind (pc+1)
#define cstl (pc+1+NPCE)
#define pos (pc+1+NPCE*2)
#define code (pc+1+NPCE*3)
/* Piece counts hidden in the unused Pawn section, indexed by color */
#define LastKnight (code-4)
#define FirstSlider (code-3)
#define FirstPawn (code-2)
#define PUSH(A,B) stack[msp++] = (A)+(B);
/* offset overlays to allow negative array subscripts */
/* and avoid cache collisions of these heavily used arrays */
#define board (brd+1) /* 12 x 16 board: dbl guard band */
#define capt_code (brd+1+0xBC+0x77) /* piece type that can reach this*/
#define delta_vec ((char *) brd+1+0xBC+0xEF+0x77) /* step to bridge certain vector */
int rseed = 87105015;
unsigned long long int accept[30], reject[30], miss[30];
char *Zob[2*NPCE];
unsigned char
pc[NPCE*4+1], /* piece list, equivalenced with various piece info */
brd[0xBC+2*0xEF+1], /* contains play bord and 2 delta boards */
CasRights, /* one bit per castling, clear if allowed */
HashFlag,
/* piece-number assignment of first row, and piece types */
array[] = {12, 1, 14, 11, 0, 15, 2, 13,
5, 3, 4, 6, 7, 4, 3, 5},
capts[] = {0, C_PPAWN, C_MPAWN, C_KNIGHT, C_BISHOP,
C_ROOK, C_QUEEN, C_KING};
char
noUnder = 0,
queen_dir[] = {1, -1, 16, -16, 15, -15, 17, -17},
king_rose[] = {1,17,16,15,-1,-17,-16,-15},
knight_rose[] = {18,33,31,14,-18,-33,-31,-14};
char buf[80];
char Keys[1040];
int path[100];
int stack[1024], msp, ep1, ep2, Kmoves, Promo, Split, epSqr, HashSize, HashSection;
unsigned long long int HashKey=8729767686LL, HighKey=1234567890LL, count, epcnt, xcnt, ckcnt, cascnt, promcnt, nodecount; /* stats */
FILE *f;
clock_t ttt[30];
void board_init(char *b)
{ /* make an empty board surrounded by guard band of uncapturable pieces */
int i;
for(i= -1; i<0xBC; i++) b[i] = (i-0x22)&0x88 ? GUARD : DUMMY;
}
void delta_init()
{ /* fill 0x88-style attack tables, with capture codes and vectors */
int i, j, k, m, y;
/* contact captures (cannot be blocked) */
capt_code[ 15] = capt_code[ 17] = C_FDIAG;
capt_code[-15] = capt_code[-17] = C_BDIAG;
capt_code[ 1] = capt_code[ -1] = C_SIDE;
capt_code[ 16] = C_FORW;
capt_code[-16] = C_BACKW;
for(i=0; i<8; i++)
{ /* in all directions */
capt_code[knight_rose[i]] = C_KNIGHT;
delta_vec[knight_rose[i]] = knight_rose[i];
/* distant captures (can be blocked) */
k = queen_dir[i];
m = i<4 ? C_ORTH : C_DIAG;
y = 0;
for(j=0; j<7; j++)
{ /* scan along ray */
delta_vec[y+=k] = k;
/* note that first is contact */
if(j) capt_code[y] = m;
}
}
}
void piece_init(void)
{ /* initialize piece list to initial setup */
int i, j, k;
/* initalize piece type and position, in initial setup */
for(i=0; i<8; i++)
{ kind[array[i]+WHITE] =
kind[array[i]] = array[i+8];
kind[i+PAWNS] = 1;
kind[i+PAWNS+WHITE] = 2;
pos[array[i]] = i+0x22;
pos[array[i]+WHITE] = i+0x92;
pos[i+PAWNS] = i+0x32;
pos[i+PAWNS+WHITE] = i+0x82;
}
/* set capture codes for each piece */
for(i=0; i<NPCE; i++) code[i] = capts[kind[i]];
/* set castling spoilers (King and both original Rooks) */
cstl[0] = WHITE;
cstl[12] = WHITE>>2;
cstl[13] = WHITE>>4;
cstl[0 +WHITE] = BLACK;
cstl[12+WHITE] = BLACK>>2;
cstl[13+WHITE] = BLACK>>4;
/* piece counts (can change when we compactify lists, or promote) */
LastKnight[WHITE] = 2;
FirstSlider[WHITE] = 11;
FirstPawn[WHITE] = 16;
LastKnight[BLACK] = 2+WHITE;
FirstSlider[BLACK] = 11+WHITE;
FirstPawn[BLACK] = 16+WHITE;
Zob[DUMMY-WHITE] = Keys-0x22;
}
void setup(void)
{ /* put pieces on the board according to the piece list */
int i, j, k;
for(i=0; i<WHITE-8; i++)
{ if(pos[i] ) board[pos[i]] = WHITE + i;
if(pos[i+WHITE]) board[pos[i+WHITE]] = BLACK + i;
}
}
char asc[] = ".+pnbrqkxxxxxxxx.P*NBRQKXXXXXXXX";
void pboard(char *b, int n, int bin)
{ /* print board of n x n, in hex (bin=1) or ascii */
int i, j, k;
for(i=n-1; i>=0; i--)
{
for(j=0; j<n; j++)
if(bin) printf(" %2x", b[16*i+j]&0xFF);
else printf(" %c", (b[16*i+j]&0xFF)==GUARD ? '-' :
asc[kind[(b[16*i+j]&0x7F)-WHITE]+((b[16*i+j]&WHITE)>>1)]);
printf("\n");
}
printf("\n");
}
int checker(int col)
{
int i;
for(i=0; i<8; i++) {
int v = king_rose[i];
int x = pos[col-WHITE] + v;
int piece = board[x];
if((piece & COLOR) == (col^COLOR)) {
if(code[piece-WHITE] & capt_code[-v]) return x;
}
v = knight_rose[i];
x = pos[col-WHITE] + v;
piece = board[x];
if((piece & COLOR) == (col^COLOR)) {
if(code[piece-WHITE] & capt_code[-v]) return x;
}
}
return 0;
}
#ifndef FEN
int ReadFEN(char *FEN)
{
int row, file, Piece, i, cc, col, nr;
char c, *p;
/* remove all pieces */
for(i=0; i<NPCE; i++) pos[i] = cstl[i] = 0;
FirstSlider[WHITE] = 0x10;
FirstSlider[BLACK] = 0x30;
LastKnight[WHITE] = 0x00;
LastKnight[BLACK] = 0x20;
FirstPawn[WHITE] = 0x18;
FirstPawn[BLACK] = 0x38;
CasRights = 0;
p = FEN;
for(row=7; row>=0; row--)
{ /* read one row of the FEN */
file = 0;
do{
c = *p++;
if(c>='1' && c<='8') { file += c - '0'; }
else
{
col = WHITE;
if(c >= 'a') { c += 'A'-'a'; col = BLACK; }
Piece = BISHOP; cc = 0;
switch(c)
{
case 'K':
if(pos[col-WHITE] > 0) return -1; /* two kings illegal */
Piece = KING;
nr = col-WHITE;
if(0x20*row == 7*(col-WHITE) && file == 4) cc = (col|col>>2|col>>4);
break;
case 'R': Piece--;
if(0x20*row == 7*(col-WHITE))
{ /* only Rooks on a1, h1, a8, h8 get castling spoiler */
if(file == 0) cc = col>>2;
if(file == 7) cc = col>>4;
}
case 'Q': Piece += 2;
case 'B':
if(--FirstSlider[col] <= LastKnight[col]) return(-2);
nr = FirstSlider[col];
break;
case 'P':
if(--FirstPawn[col] < col-WHITE+16) return(-4);
nr = FirstPawn[col];
Piece = col>>5;
break;
case 'N':
if(FirstSlider[col] <= ++LastKnight[col]) return(-3);
nr = LastKnight[col];
Piece = KNIGHT;
break;
default: return -15;
}
pos[nr] = ((file + 16*row) & 0x77) + 0x22;
kind[nr] = Piece;
code[nr] = capts[Piece];
Zob[nr] = Keys + 128*Piece + (col&BLACK)/8 - 0x22;
cstl[nr] = cc;
CasRights |= cc; /* remember K & R on original location */
file++;
}
} while(file < 8);
if(file > 8) return -11;
if(file == 8)
{ c = *p++;
if(row > 0 && c != '/') return(-10); /* bad format */
if(row==0 && c != ' ') return -11;
}
}
if(pos[0] == 0 || pos[WHITE] == 0) return -5; /* missing king */
/* now do castle rights and side to move */
cstl[DUMMY-WHITE]=0;
cc = 0;
while(c = *p++)
{
if(c>='0' && c<='9') continue; /* ignore move counts */
if(c>='a' && c<='h') /* might be e.p. square */
{ if(*p == '3' || *p == '6')
{
epSqr = 0x22 + (*p - '1')*16 + (c - 'a');
p++;
continue;
} else if(c != 'b') continue;
}
switch(c)
{
case 'K': cc |= 0x22; break;
case 'Q': cc |= 0x28; break;
case 'k': cc |= 0x44; break;
case 'q': cc |= 0x50; break;
case 'w': col = WHITE; break;
case 'b': col = BLACK; break;
case ' ':
case '-': break;
default: return -12;
}
}
CasRights = (cc & CasRights) ^ 0x7E;
return col;
}
#endif
void move_gen(int color, int lastply, int d)
{
int i, j, k, p, v, x, z, y, r, m, h;
int savsp, mask, new, forward, rank, prank, xcolor, ep_flag;
int in_check=0, checker= -1, check_dir = 20;
int pstack[12], ppos[12], psp=0, first_move=msp;
/* Some general preparation */
k = pos[color-WHITE]; /* position of my King */
forward = 48- color; /* forward step */
rank = 0x58 - (forward>>1); /* 4th/5th rank */
prank = 0xD0 - 5*(color>>1); /* 2nd/7th rank */
ep_flag = lastply>>24&0xFF;
ep1 = ep2 = msp; Promo = 0;
/* Pintest, starting from possible pinners in enemy slider list */
/* if aiming at King & 1 piece of us in between, park this piece */
/* on pin stack for rest of move generation, after generating its */
/* moves along the pin line. */
for(p=FirstSlider[COLOR-color]; p<COLOR-WHITE+16-color; p++)
{ /* run through enemy slider list */
j = pos[p]; /* enemy slider */
if(j==0) continue; /* currently captured */
if(capt_code[j-k]&code[p]&C_DISTANT)
{ /* slider aimed at our king */
v = delta_vec[j-k];
x = k; /* trace ray from our King */
while((m=board[x+=v]) == DUMMY);
if(x==j)
{ /* distant check detected */
in_check += 2;
checker = j;
check_dir = v;
} else
if(m&color)
{ /* first on ray from King is ours */
y = x;
while(board[y+=v] == DUMMY);
if(y==j)
{ /* our piece at x is pinned! */
/* remove from piece list */
/* and put on pin stack */
m -= WHITE;
ppos[psp] = pos[m];
pos[m] = 0;
pstack[psp++] = m;
z = x<<8;
if(kind[m]<3)
{ /* flag promotions */
if(!((prank^x)&0xF0)) z |= 0xA1000000;
y = x + forward;
if(!(v&7)) /* Pawn along file */
{ /* generate non-captures */
if(!(board[y]&COLOR))
{ PUSH(z,y)
y += forward;Promo++;
if(!(board[y]&COLOR | (rank^y)&0xF0))
PUSH(z,y|y<<24)
}
} else
{ /* diagonal pin */
/* try capture pinner */
if(y+1==j) { Promo++; PUSH(z,y+1) }
if(y-1==j) { Promo++; PUSH(z,y-1) }
}
} else
if(code[m]&capt_code[j-k]&C_DISTANT)
{ /* slider moves along pin ray */
y = x;
do{ /* moves upto capt. pinner*/
y += v;
PUSH(z,y)
} while(y != j);
y = x;
while((y-=v) != k)
{ /* moves towards King */
PUSH(z,y)
}
}
}
}
}
}
/* all pinned pieces are now removed from lists */
/* all their remaining legal moves are generated*/
/* all distant checks are detected */
/* determine if opponent's move put us in contact check */
y = lastply&0xFF;
if(capt_code[k-y] & code[board[y]-WHITE] & C_CONTACT)
{ checker = y; in_check++;
check_dir = delta_vec[checker-k];
}
/* determine how to proceed based on check situation */
if(in_check)
{ /* purge moves with pinned pieces if in check */
msp = first_move;
if(in_check > 2) goto King_Moves; /* double check */
if(checker == ep_flag) { ep1 = msp; goto ep_Captures; }
goto Regular_Moves;
}
/* generate castlings */
ep1 = msp;
if(!(color&CasRights))
{
if(!(board[k+1]^DUMMY|board[k+2]^DUMMY|
CasRights&color>>4))
PUSH(k<<8,k+2+0xB0000000+0x3000000)
if(!(board[k-1]^DUMMY|board[k-2]^DUMMY|board[k-3]^DUMMY|
CasRights&color>>2))
PUSH(k<<8,k-2+0xB0000000-0x4000000)
}
/* generate e.p. captures (at most two) */
/* branches are almost always take, e.p. capture is rare */
ep_Captures:
mask = color | PAWNS;
x = ep_flag+1;
if((board[x]&mask)==mask) PUSH(x<<8,ep_flag^0x10|0xA0000000);
x = ep_flag-1;
if((board[x]&mask)==mask) PUSH(x<<8,ep_flag^0x10|0xA0000000);
ep2 = msp;
/* On contact check only King retreat or capture helps */
/* Use in that case specialized recapture generator */
Regular_Moves:
if(in_check & 1)
{
xcolor = color^COLOR;
/* check for pawns, through 2 squares on board */
m = color | PAWNS;
z = x = checker; y = x - forward;
if(!((prank^y)&0xF0)) Promo++,z |= 0xA1000000;
if((board[y+1]&m)==m && pos[board[y+1]-WHITE]) PUSH(y+1<<8,z)
if((board[y-1]&m)==m && pos[board[y-1]-WHITE]) PUSH(y-1<<8,z)
for(p=LastKnight[color]; p>color-WHITE; p--)
{
k = pos[p];
if(k==0) continue;
m = code[p];
i = capt_code[k-x];
if(i&m) PUSH(k<<8,x)
}
for(p=color-WHITE+15; p>=FirstSlider[color]; p--)
{
k = pos[p];
if(k==0) continue;
m = code[p];
i = capt_code[k-x];
if(i&m)
{
v = delta_vec[k-x];
y = x;
while(board[y+=v]==DUMMY);
if(y==k) PUSH(k<<8,x)
}
}
} else
/* Basic move generator for generating all moves */
{
/* First do pawns, from pawn list hanging from list head */
mask = color|0x80; /* matches own color, empty square, or guard */
for(p=FirstPawn[color]; p<color-WHITE+PAWNS+8; p++)
{
x = pos[p]; z = x<<8;
if(x==0) continue;
/* flag promotions */
if(!((prank^x)&0xF0)) Promo++,z |= 0xA1000000;
/* capture moves */
y = x + forward;
if(!(board[y-1]&mask)) PUSH(z,y-1)
if(!(board[y+1]&mask)) PUSH(z,y+1)
/* non-capture moves */
if(!(board[y]&COLOR))
{ PUSH(z,y)
y += forward;
if(!(board[y]&COLOR | (rank^y)&0xF0))
PUSH(z,y|y<<24) /* e.p. flag */
}
}
/* Next do Knights */
for(p=LastKnight[color]; p>color-WHITE; p--)
{
x = pos[p]; z = x<<8;
if(x==0) continue;
/* always 8 direction, unroll loop to avoid branches */
if(!(board[x+14]&color)) PUSH(z,x+14)
if(!(board[x+31]&color)) PUSH(z,x+31)
if(!(board[x+33]&color)) PUSH(z,x+33)
if(!(board[x+18]&color)) PUSH(z,x+18)
if(!(board[x-14]&color)) PUSH(z,x-14)
if(!(board[x-31]&color)) PUSH(z,x-31)
if(!(board[x-33]&color)) PUSH(z,x-33)
if(!(board[x-18]&color)) PUSH(z,x-18)
}
/* now do sliding pieces */
/* for each ray, do ray scan, and goto next ray when blocked */
for(p=color-WHITE+15; p>=FirstSlider[color]; p--)
{
x = pos[p]; z = x<<8;
if(x==0) continue;
if(kind[p]-3&2)
{ /* scan 4 rook rays for R and Q */
y = x;
do{ if(!((h=board[y+=1 ])&color)) PUSH(z,y) } while(!(h&COLOR));
y = x;
do{ if(!((h=board[y-=1 ])&color)) PUSH(z,y) } while(!(h&COLOR));
y = x;
do{ if(!((h=board[y+=16])&color)) PUSH(z,y) } while(!(h&COLOR));
y = x;
do{ if(!((h=board[y-=16])&color)) PUSH(z,y) } while(!(h&COLOR));
}
if(kind[p]-3&1)
{ /* scan 4 bishop rays for B and Q */
y = x;
do{ if(!((h=board[y+=15])&color)) PUSH(z,y) } while(!(h&COLOR));
y = x;
do{ if(!((h=board[y-=15])&color)) PUSH(z,y) } while(!(h&COLOR));
y = x;
do{ if(!((h=board[y+=17])&color)) PUSH(z,y) } while(!(h&COLOR));
y = x;
do{ if(!((h=board[y-=17])&color)) PUSH(z,y) } while(!(h&COLOR));
}
}
/* remove moves that don't solve distant check by */
/* capturing checker or interposing on check ray */
if(in_check)
for(i=first_move; i<msp; i++) /* go through all moves */
{
if(delta_vec[(j=stack[i]&0xFF)-k] != check_dir)
stack[i--] = stack[--msp];
else
{ /* on check ray, could block or capture checker*/
x = k;
do{
x += check_dir;
if(x==j) break;
} while(x != checker);
if(x!=j) { stack[i--] = stack[--msp]; }
}
}
}
/* Generate moves with the always present King */
King_Moves:
x = pos[color-WHITE]; z = x<<8;
Kmoves = msp;
/* always 8 direction, unroll loop to avoid branches */
if(!(board[x+1 ]&color)) PUSH(z,x+1)
if(!(board[x+17]&color)) PUSH(z,x+17)
if(!(board[x+16]&color)) PUSH(z,x+16)
if(!(board[x+15]&color)) PUSH(z,x+15)
if(!(board[x-1 ]&color)) PUSH(z,x-1)
if(!(board[x-17]&color)) PUSH(z,x-17)
if(!(board[x-16]&color)) PUSH(z,x-16)
if(!(board[x-15]&color)) PUSH(z,x-15)
/* Put pieces that were parked onto pin stack back in lists */
while(psp>0)
{ /* pop pinned piece and link in old place it remembers*/
m = pstack[--psp];
pos[m] = ppos[psp];
}
}
#if 1
int move_count(int color, int lastply, int d)
{
int i, j, k, p, v, x, z, y, r, m, h;
int savsp, mask, new, forward, rank, prank, xcolor, ep_flag;
int in_check=0, checker= -1, check_dir = 20;
int pstack[12], ppos[12], psp=0, first_move=msp, myCount=0;
/* Some general preparation */
k = pos[color-WHITE]; /* position of my King */
forward = 48- color; /* forward step */
rank = 0x58 - (forward>>1); /* 4th/5th rank */
prank = 0xD0 - 5*(color>>1); /* 2nd/7th rank */
ep_flag = lastply>>24&0xFF;
/* Pintest, starting from possible pinners in enemy slider list */
/* if aiming at King & 1 piece of us in between, park this piece */
/* on pin stack for rest of move generation, after generating its */
/* moves along the pin line. */
for(p=FirstSlider[COLOR-color]; p<COLOR-WHITE+16-color; p++)
{ /* run through enemy slider list */
j = pos[p]; /* enemy slider */
if(j==0) continue; /* currently captured */
if(capt_code[j-k]&code[p]&C_DISTANT)
{ /* slider aimed at our king */
v = delta_vec[j-k];
x = k; /* trace ray from our King */
while((m=board[x+=v]) == DUMMY);
if(x==j)
{ /* distant check detected */
in_check += 2;
checker = j;
check_dir = v;
} else
if(m&color)
{ /* first on ray from King is ours */
y = x;
while(board[y+=v] == DUMMY);
if(y==j)
{ /* our piece at x is pinned! */
/* remove from piece list */
/* and put on pin stack */
m -= WHITE;
ppos[psp] = pos[m];
pos[m] = 0;
pstack[psp++] = m;
z = x<<8;
if(kind[m]<3)
{ /* flag promotions */
if(!((prank^x)&0xF0)) {
z |= 0xA1000000;
y = x + forward;
if(!(v&7)) /* Pawn along file */
{ /* generate non-captures */
if(!(board[y]&COLOR))
{ PUSH(z,y)
y += forward;
if(!(board[y]&COLOR | (rank^y)&0xF0))
PUSH(z,y)
}
} else
{ /* diagonal pin */
/* try capture pinner */
if(y+1==j) PUSH(z,y+1)
if(y-1==j) PUSH(z,y-1)
}
} else {
y = x + forward;
if(!(v&7)) /* Pawn along file */
{ /* generate non-captures */
if(!(board[y]&COLOR))
{ myCount++;
y += forward;
myCount += !(board[y]&COLOR | (rank^y)&0xF0);
}
} else
{ /* diagonal pin */
/* try capture pinner */
myCount += (y+1==j);
myCount += (y-1==j);
}
}
} else
if(code[m]&capt_code[j-k]&C_DISTANT)
{ /* slider moves along pin ray */
y = x;
do{ /* moves upto capt. pinner*/
y += v;
myCount++;
} while(y != j);
y = x;
while((y-=v) != k)
{ /* moves towards King */
myCount++;
}
}
}
}
}
}
/* all pinned pieces are now removed from lists */
/* all their remaining legal moves are generated*/
/* all distant checks are detected */
/* determine if opponent's move put us in contact check */
y = lastply&0xFF;
if(capt_code[k-y] & code[board[y]-WHITE] & C_CONTACT)
{ checker = y; in_check++;
check_dir = delta_vec[checker-k];
}
/* determine how to proceed based on check situation */
if(in_check)
{ /* purge moves with pinned pieces if in check */
msp = first_move; myCount = 0;
if(in_check > 2) goto King_Moves2; /* double check */
if(checker == ep_flag) goto ep_Captures_in_Check;
goto Regular_Moves_in_Check;
}
/* generate castlings */
if(!(color&CasRights))
{
if(!(board[k+1]^DUMMY|board[k+2]^DUMMY|
CasRights&color>>4))
PUSH(k<<8,k+2+0xB0000000+0x3000000)
if(!(board[k-1]^DUMMY|board[k-2]^DUMMY|board[k-3]^DUMMY|
CasRights&color>>2))
PUSH(k<<8,k-2+0xB0000000-0x4000000)
}
/* generate e.p. captures (at most two) */
/* branches are almost always take, e.p. capture is rare */
ep_Captures2:
mask = color | PAWNS;
x = ep_flag+1;
if((board[x]&mask)==mask) PUSH(x<<8,ep_flag^0x10|0xA0000000);
x = ep_flag-1;
if((board[x]&mask)==mask) PUSH(x<<8,ep_flag^0x10|0xA0000000);
ep2 = msp;
/* On contact check only King retreat or capture helps */
/* Use in that case specialized recapture generator */
Regular_Moves2:
/* Basic move generator for generating all moves */
{
/* First do pawns, from pawn list hanging from list head */
mask = color|0x80; /* matches own color, empty square, or guard */
for(p=FirstPawn[color]; p<color-WHITE+PAWNS+8; p++)
{
x = pos[p]; z = x<<8;
if(x==0) continue;
/* flag promotions */
if(!((prank^x)&0xF0)) {
z |= 0xA1000000;
/* capture moves */
y = x + forward;
if(!(board[y-1]&mask)) PUSH(z,y-1)
if(!(board[y+1]&mask)) PUSH(z,y+1)
/* non-capture moves (no double-push if promotion!) */
if(!(board[y]&COLOR)) PUSH(z,y)
} else {
/* capture moves */
y = x + forward;
myCount += !(board[y-1]&mask);
myCount += !(board[y+1]&mask);
/* non-capture moves */
if(!(board[y]&COLOR))
{ myCount++;
y += forward;
myCount += !(board[y]&COLOR | (rank^y)&0xF0);
}
}
}
/* Next do Knights */
for(p=LastKnight[color]; p>color-WHITE; p--)
{
x = pos[p]; z = x<<8;
if(x==0) continue;
/* always 8 direction, unroll loop to avoid branches */
myCount += !(board[x+14]&color);
myCount += !(board[x+31]&color);
myCount += !(board[x+33]&color);
myCount += !(board[x+18]&color);
myCount += !(board[x-14]&color);
myCount += !(board[x-31]&color);
myCount += !(board[x-33]&color);
myCount += !(board[x-18]&color);
}
/* now do sliding pieces */
/* for each ray, do ray scan, and goto next ray when blocked */
for(p=color-WHITE+15; p>=FirstSlider[color]; p--)
{
x = pos[p]; z = x<<8;
if(x==0) continue;
if(kind[p]-3&2)
{ /* scan 4 rook rays for R and Q */
register int h, y;
y = x; while((h=board[y+=1 ]) == DUMMY) myCount++; myCount += !(board[y]&color);
y = x; while((h=board[y-=1 ]) == DUMMY) myCount++; myCount += !(board[y]&color);
y = x; while((h=board[y+=16]) == DUMMY) myCount++; myCount += !(board[y]&color);
y = x; while((h=board[y-=16]) == DUMMY) myCount++; myCount += !(board[y]&color);
}
if(kind[p]-3&1)
{ /* scan 4 bishop rays for B and Q */
register int h, y;
y = x; while((h=board[y+=15]) == DUMMY) myCount++; myCount += !(board[y]&color);
y = x; while((h=board[y-=15]) == DUMMY) myCount++; myCount += !(board[y]&color);
y = x; while((h=board[y+=17]) == DUMMY) myCount++; myCount += !(board[y]&color);
y = x; while((h=board[y-=17]) == DUMMY) myCount++; myCount += !(board[y]&color);
}
}
}
goto King_Moves2;
/* generate e.p. captures (at most two) */
/* branches are almost always take, e.p. capture is rare */
ep_Captures_in_Check:
mask = color | PAWNS;
x = ep_flag+1;
if((board[x]&mask)==mask) PUSH(x<<8,ep_flag^0x10|0xA0000000);
x = ep_flag-1;
if((board[x]&mask)==mask) PUSH(x<<8,ep_flag^0x10|0xA0000000);
/* On contact check only King retreat or capture helps */
/* Use in that case specialized recapture generator */
Regular_Moves_in_Check:
if(in_check & 1)
{
xcolor = color^COLOR;
/* check for pawns, through 2 squares on board */
m = color | PAWNS;
z = x = checker; y = x - forward;
if(!((prank^y)&0xF0)) {
z |= 0xA1000000;
if((board[y+1]&m)==m && pos[board[y+1]-WHITE]) PUSH(y+1<<8,z)
if((board[y-1]&m)==m && pos[board[y-1]-WHITE]) PUSH(y-1<<8,z)
} else {
myCount += (board[y+1]&m)==m && pos[board[y+1]-WHITE];
myCount += (board[y-1]&m)==m && pos[board[y-1]-WHITE];
}
for(p=LastKnight[color]; p>color-WHITE; p--)
{
k = pos[p];
if(k==0) continue;
m = code[p];
i = capt_code[k-x];
myCount += (i&m) != 0;
}
for(p=color-WHITE+15; p>=FirstSlider[color]; p--)
{
k = pos[p];
if(k==0) continue;
m = code[p];
i = capt_code[k-x];
if(i&m)
{
v = delta_vec[k-x];
y = x;
while(board[y+=v]==DUMMY);
myCount += (y==k);
}
}
} else
/* Basic move generator for generating all moves */
{
/* First do pawns, from pawn list hanging from list head */
mask = color|0x80; /* matches own color, empty square, or guard */
for(p=FirstPawn[color]; p<color-WHITE+PAWNS+8; p++)
{
x = pos[p]; z = x<<8;
if(x==0) continue;
/* flag promotions */
if(!((prank^x)&0xF0)) Promo++,z |= 0xA1000000;
/* capture moves */
y = x + forward;
if(!(board[y-1]&mask)) PUSH(z,y-1)
if(!(board[y+1]&mask)) PUSH(z,y+1)
/* non-capture moves */
if(!(board[y]&COLOR))
{ PUSH(z,y)
y += forward;
if(!(board[y]&COLOR | (rank^y)&0xF0))
PUSH(z,y) /* forget e.p. flag */
}
}
/* Next do Knights */
for(p=LastKnight[color]; p>color-WHITE; p--)
{
x = pos[p]; z = x<<8;
if(x==0) continue;
/* always 8 direction, unroll loop to avoid branches */
if(!(board[x+14]&color)) PUSH(z,x+14)
if(!(board[x+31]&color)) PUSH(z,x+31)
if(!(board[x+33]&color)) PUSH(z,x+33)
if(!(board[x+18]&color)) PUSH(z,x+18)
if(!(board[x-14]&color)) PUSH(z,x-14)
if(!(board[x-31]&color)) PUSH(z,x-31)
if(!(board[x-33]&color)) PUSH(z,x-33)
if(!(board[x-18]&color)) PUSH(z,x-18)
}
/* now do sliding pieces */
/* for each ray, do ray scan, and goto next ray when blocked */
for(p=color-WHITE+15; p>=FirstSlider[color]; p--)
{
x = pos[p]; z = x<<8;
if(x==0) continue;
if(kind[p]-3&2)
{ /* scan 4 rook rays for R and Q */
y = x;
do{ if(!((h=board[y+=1 ])&color)) PUSH(z,y) } while(!(h&COLOR));
y = x;
do{ if(!((h=board[y-=1 ])&color)) PUSH(z,y) } while(!(h&COLOR));
y = x;
do{ if(!((h=board[y+=16])&color)) PUSH(z,y) } while(!(h&COLOR));
y = x;
do{ if(!((h=board[y-=16])&color)) PUSH(z,y) } while(!(h&COLOR));
}
if(kind[p]-3&1)
{ /* scan 4 bishop rays for B and Q */
y = x;
do{ if(!((h=board[y+=15])&color)) PUSH(z,y) } while(!(h&COLOR));
y = x;
do{ if(!((h=board[y-=15])&color)) PUSH(z,y) } while(!(h&COLOR));
y = x;
do{ if(!((h=board[y+=17])&color)) PUSH(z,y) } while(!(h&COLOR));
y = x;
do{ if(!((h=board[y-=17])&color)) PUSH(z,y) } while(!(h&COLOR));
}
}
/* remove moves that don't solve distant check by */
/* capturing checker or interposing on check ray */
if(in_check)
for(i=first_move; i<msp; i++) /* go through all moves */
{
if(delta_vec[(j=stack[i]&0xFF)-k] != check_dir)
stack[i--] = stack[--msp];
else
{ /* on check ray, could block or capture checker*/
x = k;
do{
x += check_dir;
if(x==j) break;
} while(x != checker);
if(x!=j) { stack[i--] = stack[--msp]; }
}
}
}
/* Generate moves with the always present King */
King_Moves2:
x = pos[color-WHITE]; z = x<<8;
Kmoves = msp;
/* always 8 direction, unroll loop to avoid branches */
if(!(board[x+1 ]&color)) PUSH(z,x+1)
if(!(board[x+17]&color)) PUSH(z,x+17)
if(!(board[x+16]&color)) PUSH(z,x+16)
if(!(board[x+15]&color)) PUSH(z,x+15)
if(!(board[x-1 ]&color)) PUSH(z,x-1)
if(!(board[x-17]&color)) PUSH(z,x-17)
if(!(board[x-16]&color)) PUSH(z,x-16)
if(!(board[x-15]&color)) PUSH(z,x-15)
/* Put pieces that were parked onto pin stack back in lists */
while(psp>0)
{ /* pop pinned piece and link in old place it remembers*/
m = pstack[--psp];
pos[m] = ppos[psp];
}
return myCount;
}
#endif
int capturable(int color, int x)
{ /* do full check for captures on square x by all opponen't pieces */
int i, j, k, v, y, m, p;
/* check for pawns, through 2 squares on board */
v = color - 48; m = color | PAWNS;
if((board[x+v+1]&m)==m) return 1;
if((board[x+v-1]&m)==m) return 2;
for(p=LastKnight[color]; p>=color-WHITE; p--)
{
k = pos[p];
if(k==0) continue;
m = code[p];
i = capt_code[k-x];
if(i&m) return p+256;
}
for(p=color-WHITE+15; p>=FirstSlider[color]; p--)
{
k = pos[p];
if(k==0) continue;
m = code[p];
i = capt_code[k-x];
if(i&m)
{
v = delta_vec[k-x];
y = x;
while(board[y+=v]==DUMMY);
if(y==k) return p+512;
}
}
return 0;
}
void leaf_perft(int color, int lastply, int depth, int d)
{ /* recursive perft, with in-lined make/unmake */
int i, j, k, m, x, y, v, h, p, oldpiece, store, myCount;
int first_move, piece, victim, pred, succ, from, to, capt, mode,
pcnr, vicnr, in_check=0, checker= -1, check_dir = 20, legal;
int SavRights = CasRights, lep1, lep2, lkm, flag;
unsigned long long int ocnt=count, SavCnt;
union _bucket *Bucket;
TIME(17)
first_move = msp; /* new area on move stack */
legal = 0;
count += move_count(color, lastply, d); /* bulk count, but generate moves that need legality checking */
for(i = first_move; i<msp; i++) /* go through all moves */
{
/* fetch move from move stack */
from = (stack[i]>>8)&0xFF;
to = capt = stack[i]&0xFF;
mode = (unsigned int)stack[i]>>24;
piece = board[from];
if(mode)
{ /* e.p. or castling, usually skipped */
/* e.p.:shift capture square one rank */
if(mode == 0xA0) capt ^= 0x10; else
if(mode == 0xA1)
{ /* Promotion. Shuffle piece list :( */
oldpiece = piece; pos[piece-WHITE]=0;
/* set up for new Queen first */
piece = --FirstSlider[color]+WHITE;
kind[piece-WHITE] = QUEEN;
code[piece-WHITE] = C_QUEEN;
Zob[piece-WHITE] = Keys + 128*QUEEN + (color&BLACK)/8 - 0x22;
pos[piece-WHITE] = from;
}else
{ /* castling, determine Rook move */
j = mode - 0xB0 + from;
h = from+to >> 1;
/* abort if Rook in check */
if(capturable(color^COLOR, h)) continue;
/* move Rook */
board[h] = board[j];
board[j] = DUMMY;
pos[board[h]-WHITE] = h;
}
}
victim = board[capt];
CasRights |= cstl[piece-WHITE] | cstl[victim-WHITE];
minor:
/* perform move, in piece list and on board */
/* update board position */
board[capt] = board[from] = DUMMY;
board[to] = piece;
/* update piece location in piece list */
pos[piece-WHITE] = to;
/* remove captured piece from piece list */
pos[victim-WHITE] = 0;
count += !capturable(color^COLOR, pos[color-WHITE]);
/* retract move */
/* restore piece list */
pos[piece-WHITE] = from;
pos[victim-WHITE] = capt;
/* restore board */
board[to] = DUMMY; /* restore board */
board[capt] = victim;
board[from] = piece;
if((unsigned int) stack[i]>=0xA1000000) /* was castling or prom */
{ if(mode==0xA1)
{
if(noUnder) {
FirstSlider[color]++;
piece =oldpiece;
pos[piece-WHITE] = from;
board[from] = piece;
} else
if(--kind[piece-WHITE] >= KNIGHT)
{
if(kind[piece-WHITE] == KNIGHT)
{ /* Knight must be put in Knight list */
FirstSlider[color]++;
piece = ++LastKnight[color]+WHITE;
pos[piece-WHITE] = from;
kind[piece-WHITE] = KNIGHT;
Zob[piece-WHITE] = Keys + 128*KNIGHT
+ (color&BLACK)/8 - 0x22;
} else Zob[piece-WHITE] -= 128;
code[piece-WHITE] = capts[kind[piece-WHITE]];
goto minor; /* try minor promotion */
} else
{ /* All promotions tried, demote to Pawn again */
kind[piece-WHITE] = QUEEN; /* put Q back for hash store */
piece = oldpiece; LastKnight[color]--;
pos[piece-WHITE] = from;
board[from] = piece;
}
} else
{ /* undo Rook move */
board[j] = board[h];
board[h] = DUMMY;
pos[board[j]-WHITE] = j;
}
}
CasRights = SavRights;
}
msp = first_move; /* throw away moves */
}
void perft(int color, int lastply, int depth, int d)
{ /* recursive perft, with in-lined make/unmake */
int i, j, k, m, x, y, v, h, p, oldpiece, store;
int first_move, piece, victim, pred, succ, from, to, capt, mode,
pcnr, vicnr, in_check=0, checker= -1, check_dir = 20, legal;
int SavRights = CasRights, lep1, lep2, lkm, flag, Index;
unsigned long long int ocnt=count, OldKey = HashKey, OldHKey = HighKey, SavCnt;
union _bucket *Bucket;
TIME(17)
first_move = msp; /* new area on move stack */
legal = 0;
move_gen(color, lastply, d); /* generate moves */
nodecount++;
lep1 = ep1; lep2 = ep2; lkm = Kmoves; flag = depth == 1 && !Promo;
if(flag)
count += Kmoves - first_move - ep2 + ep1; /* bulk count */
for(i = flag ? ep1 : first_move; i<msp; i++) /* go through all moves */
{
if(i == lep2 & flag) { i = lkm; if(i >= msp) break; }
/* fetch move from move stack */
from = (stack[i]>>8)&0xFF;
to = capt = stack[i]&0xFF;
mode = (unsigned int)stack[i]>>24;
path[d] = stack[i];
piece = board[from];
Index = 0;
if(mode)
{ /* e.p. or castling, usually skipped */
/* e.p.:shift capture square one rank */
if(mode < 0xA0)
{ if(((board[to+1]^piece) & (COLOR|PAWNS)) == COLOR ||
((board[to-1]^piece) & (COLOR|PAWNS)) == COLOR)
Index = mode * 76265;
} else
if(mode == 0xA0) capt ^= 0x10; else
if(mode == 0xA1)
{ /* Promotion. Shuffle piece list :( */
oldpiece = piece; pos[piece-WHITE]=0;
/* set up for new Queen first */
piece = --FirstSlider[color]+WHITE;
kind[piece-WHITE] = QUEEN;
code[piece-WHITE] = C_QUEEN;
Zob[piece-WHITE] = Keys + 128*QUEEN + (color&BLACK)/8 - 0x22;
pos[piece-WHITE] = from;
HashKey ^= Zobrist(piece, from) ^ Zobrist(oldpiece, from);
HighKey ^= Zobrist(piece, from+8) ^ Zobrist(oldpiece, from+8);
Index += 14457159; /* prevent hits by non-promotion moves */
}else
{ /* castling, determine Rook move */
j = mode - 0xB0 + from;
h = from+to >> 1;
/* abort if Rook in check */
if(capturable(color^COLOR, h)) continue;
/* move Rook */
board[h] = board[j];
board[j] = DUMMY;
pos[board[h]-WHITE] = h;
HashKey ^= Zobrist(board[h],h) ^ Zobrist(board[h],j);
HighKey ^= Zobrist(board[h],h+8) ^ Zobrist(board[h],j+8);
}
}
victim = board[capt];
CasRights |= cstl[piece-WHITE] | cstl[victim-WHITE];
if(depth==1)
{ if(piece != color && mode < 0xA0)
{ count++; goto quick; }
} else if(HashFlag)
{
SavCnt = count;
HashKey ^= Zobrist(piece,from) /* key update for normal move */
^ Zobrist(piece,to)
^ Zobrist(victim,capt);
HighKey ^= Zobrist(piece,from+8) /* key update for normal move */
^ Zobrist(piece,to+8)
^ Zobrist(victim,capt+8);
Index += (CasRights << 4) +color*919581;
if(depth>2) {
path[d] = stack[i];
if(depth > 7) { // the count will not fit in 32 bits
if(depth > 9) {
int i = HashSection, j = depth-9;
while(j--) i >>= 1;
Bucket = Hash + (Index + ((int) HashKey) & i) + 7 * HashSection + i;
} else
Bucket = Hash + (Index + ((int) HashKey) & HashSection) + (depth-3) * HashSection;
if(Bucket->l.Signature1 == HighKey && Bucket->l.Signature2 == HashKey)
{ count += Bucket->l.longCount; accept[depth]++;
goto quick;
}
reject[depth]++;
goto minor;
}
Bucket = Hash + (Index + ((int) HashKey) & HashSection) + (depth-3) * HashSection;
} else Bucket = ExtraHash + (Index + ((int) HashKey) & XSIZE-1);
store = (HashKey>>32) & 1;
if(Bucket->s.Signature[store] == HighKey && (Bucket->s.Extension[store] ^ (HashKey>>32)) < 2)
{ count += Bucket->s.Count[store]; accept[depth]++;
Bucket->s.Extension[store] &= ~1;
Bucket->s.Extension[store^1] |= 1;
goto quick;
}
if(Bucket->s.Signature[store^1] == HighKey && (Bucket->s.Extension[store^1] ^ (HashKey>>32)) < 2)
{ count += Bucket->s.Count[store^1]; accept[depth]++;
Bucket->s.Extension[store^1] &= ~1;
Bucket->s.Extension[store] |= 1;
goto quick;
}
reject[depth]++; // miss;
if(Bucket->s.Extension[store^1] & 1) store ^= 1;
}
minor:
/* perform move, in piece list and on board */
/* update board position */
board[capt] = board[from] = DUMMY;
board[to] = piece;
/* update piece location in piece list */
pos[piece-WHITE] = to;
/* remove captured piece from piece list */
pos[victim-WHITE] = 0;
if((piece != color && mode != 0xA0) ||
!capturable(color^COLOR, pos[color-WHITE]))
{
/* recursion or count end leaf */
if(depth == 2) leaf_perft(COLOR-color, stack[i], depth-1, d+1);
else perft(COLOR-color, stack[i], depth-1, d+1);
if(HashFlag)
{
if(depth > 7) { //large entry
Bucket->l.Signature1 = HighKey;
Bucket->l.Signature2 = HashKey;
Bucket->l.longCount = count - SavCnt;
} else { // packed entry
Bucket->s.Signature[store] = HighKey;
Bucket->s.Extension[store] = (HashKey>>32) & ~1; // erase low bit
Bucket->s.Count[store] = count - SavCnt;
}
}
}
/* retract move */
/* restore piece list */
pos[piece-WHITE] = from;
pos[victim-WHITE] = capt;
/* restore board */
board[to] = DUMMY; /* restore board */
board[capt] = victim;
board[from] = piece;
quick:
if((unsigned int) stack[i]>=0xA1000000) /* was castling or prom */
{ if(mode==0xA1)
{
if(noUnder) {
FirstSlider[color]++;
piece =oldpiece;
pos[piece-WHITE] = from;
board[from] = piece;
} else
if(--kind[piece-WHITE] >= KNIGHT)
{
HashKey ^= Zobrist(piece, to);
HighKey ^= Zobrist(piece, to+8);
if(kind[piece-WHITE] == KNIGHT)
{ /* Knight must be put in Knight list */
FirstSlider[color]++;
piece = ++LastKnight[color]+WHITE;
pos[piece-WHITE] = from;
kind[piece-WHITE] = KNIGHT;
Zob[piece-WHITE] = Keys + 128*KNIGHT
+ (color&BLACK)/8 - 0x22;
} else Zob[piece-WHITE] -= 128;
code[piece-WHITE] = capts[kind[piece-WHITE]];
HashKey ^= Zobrist(piece, to);
HighKey ^= Zobrist(piece, to+8);
goto minor; /* try minor promotion */
} else
{ /* All promotions tried, demote to Pawn again */
kind[piece-WHITE] = QUEEN; /* put Q back for hash store */
piece = oldpiece; LastKnight[color]--;
pos[piece-WHITE] = from;
board[from] = piece;
}
} else
{ /* undo Rook move */
board[j] = board[h];
board[h] = DUMMY;
pos[board[j]-WHITE] = j;
}
}
HashKey = OldKey;
HighKey = OldHKey;
CasRights = SavRights;
}
msp = first_move; /* throw away moves */
/* For split perft uncomment the following line */
if(d <= Split && d > 1)
{
int i; clock_t t = clock();
sprintf(buf, "%10lld", count-ocnt);
printf("%d. ", d);
fprintf(f, "%d. ", d);
for(i=1; i<d; i++) {
printf("%c%c%c%c ",
'a'+(path[i]-0x2222>> 8&7),
'1'+(path[i]-0x2222>>12&7),
'a'+(path[i]-0x2222 &7),
'1'+(path[i]-0x2222>> 4&7) );
fprintf(f, "%c%c%c%c ",
'a'+(path[i]-0x2222>> 8&7),
'1'+(path[i]-0x2222>>12&7),
'a'+(path[i]-0x2222 &7),
'1'+(path[i]-0x2222>> 4&7) );
}
printf("moves = %s (%6.3f sec)\n", buf, (t - ttt[d])*(1./CLOCKS_PER_SEC));
fprintf(f, "moves = %s (%6.3f sec)\n", buf, (t - ttt[d])*(1./CLOCKS_PER_SEC)); fflush(f);
ttt[d] = t;
}
}
char *FEN = "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w QKqk",
*Fritz = "r3r1k1/1pq2pp1/2p2n2/1PNn4/2QN2b1/6P1/3RPP2/2R3KB b - -";
int Dep = 6;
int main(int argc, char **argv)
{
int i, j, k, Col;
clock_t t;
double sumx=0, sumx2=0, tot=0;
if(argc > 1 && !strcmp(argv[1], "-u")) {
argc--; argv++; noUnder = 1;
}
if(argc > 1 && sscanf(argv[1], "%d", &Dep)==1 && Dep > 0)
{ argc--; argv++; } else
{ printf("Usage is: perft <depth> [H<hash size>] [-<split depth>] [<FEN string>]\n");
printf(" <hash size> = 20 gives you 2^20 = 1M entries (16MB)\n");
exit(0);
}
if(argc > 1 && argv[1][0] == 'H' && sscanf(argv[1]+1, "%d", &HashSize) == 1)
{ HashSection = (1<<HashSize-3) - 1; HashSize = (1<<HashSize) - 2;
Hash = (union _bucket *) calloc(HashSize+4, sizeof(union _bucket) );
Hash = (union _bucket *) (((int)Hash) + 63 & ~63);
printf("Hash-table size = %x, Starts at %x,section = %x\n", HashSize+1, Hash, HashSection);
HashFlag++;
for(i=128; i<1040; i++) Keys[i] = rand()>>6;
argc--; argv++;
}
if(argc > 1 && argv[1][0] == '-' && sscanf(argv[1]+1, "%d", &Split) == 1)
{ argc--; argv++; } else Split = 0;
if(argc > 1) FEN = argv[1];
delta_init();
piece_init();
board_init(board);
Col = ReadFEN(FEN);
setup();
pboard(board, 12, 0);
if(Col < 0)
{ printf("Bad FEN '%s', error code = %d\n", FEN, Col); exit(0); }
printf("Quick Perft by H.G. Muller\n");
printf("Perft mode: ");
if(HashFlag) printf("Hash-table size = %d%cB",
(HashSize+2) >> (HashSize<64*1024 ? 6: 16),
HashSize<64*1024 ? 'k' : 'M' );
else printf("No hashing");
printf(", bulk counting in horizon nodes\n\n");
f = fopen("log.txt", "a");
fprintf(f, "perft %d -%d\n", Dep, Split);
for(i=1; i<=Dep; i++)
{
int n;
int lastPly = ((epSqr^16)<<24) + checker(Col);
t = clock();
count = epcnt = xcnt = ckcnt = cascnt = promcnt = 0;
for(j=0; j<10; j++) accept[j] = reject[j] = 0, ttt[j] = t;
if(i == 1) leaf_perft(Col, lastPly, i, 1); else
perft(Col, lastPly, i, 1);
t = clock()-t;
sprintf(buf, "%12lld", count);
printf("perft(%2d)= %s (%6.3f sec)\n", i, buf, t*(1./CLOCKS_PER_SEC));
}
fclose(f);
}
Я чуть подретактиров для задачи неприкосновенный король, чтобы исключить ходы белого короля
Bitboard в программировании шахмат №2
14 Янв 2023 14:20 #106
Сегодня наконец то попробовал инструмент оценки скорости расчета атак дальнобойных фигур.
Позицию использовал, как в задаче неприкосновенный король.
Q7/8/2K5/8/8/8/8/7k w - - - 0 1
Т.е. белый король не участвуют в расчетах perft.
Итак за базовый вариант взял расчет атак сдвигом бит в разные стороны.
Метод который я в основном использовал - метод лучей.
Даёт почти на минуту худший показатель.
В обоих случаях идёт расчет минимакс на глубину - 8.
На этой глубине perft=23 414 475.
Ну в общем то ясно, нужно использовать метод вращающихся досок.
Даже самому интересно, насколько вырастет скорость.
Я в этом просто уверен.
Bitboard в программировании шахмат №2
16 Янв 2023 11:26 #107
Как известно, в русскоязычном сегменте, не так много видео о шахматном программировании.
И не для всех английский родной.
Попадаются интересные ролики.
У меня встал вопрос перевода аудио дорожки на русский язык.
Конечно я его решил, ну и конечно с танцами с бубном.
Кто нибудь задавался этим вопросом?
Если задавался, то какое решение нашел?
Bitboard в программировании шахмат №2
16 Янв 2023 11:37 #108
Кстати еще попробовал для задачи неприкосновенный король эмпирическую оценку позиции, но прога не может заматавать без моей помощи(((
чтобы заматавать надо вручную менять глубину перебора.
Bitboard в программировании шахмат №2
17 Янв 2023 07:41 #109
Перевел еще одно видео, только не знаю кому-то это интересно или нет.
В общем то у этого товарища целая серия уроков.
В общем то не плохо объясняет.
Еще у меня вопрос, открывается ли предыдущее видео у вас или нет.
У меня написано - Playback error.
Что скажете о качестве голосового движка, озвучивающий перевод?
В общем то я искал нормальное объяснение вращающихся досок, может быть дальше он об этом расскажет. Незнаю.
Bitboard в программировании шахмат №2
17 Янв 2023 07:54 #111
Еще вопрос.
При переводе видео, создается два файла, собственно видео в mp4 и аудио в mp3.
Длительность воспроизведения у них разная, обычно звуковая дорожка немного длиннее.
Чтобы наложить звук на видео, видео нужно немного замедлить.
На вскидку не нашел нормального бесплатного видеоредактора, с возможность замедления видео.
На телефоне у меня есть такой, но гонять туда сюда файлы - не айс.
Что можете посоветовать?
Bitboard в программировании шахмат №2
18 Янв 2023 19:16 #113
Вопрос к модераторам.
Можно ли на этой площадке выкладывать уроки вышеуказанного товарища в переводе на русский язык по алгоритму, который я описал.
Уроки интересные.
Причем начиная с нуля можно написать неплохой движок , ну или по крайне мере понять как это работает.
Может быть кому-то это будет полезно.
Кстати, можно код писать непосредственно на телефоне.
Вот есть компилятор на 4 пда. Компилятор
Bitboard в программировании шахмат №2
19 Янв 2023 05:55 #114
alexlaw wrote:
Можно ли на этой площадке выкладывать уроки вышеуказанного товарища в переводе на русский язык по алгоритму, который я описал.
А что значит выкладывать?
Давать ссылки с свой канал ютюба с переделанным видео? Это сам ютюб, думаю, пресечет быстро и здесь будут черные квадраты.
Заливать непосредственно сюда? Только в виде исключения и в теории, но массово заливать по ряду причин нет.
Bitboard в программировании шахмат №2
20 Янв 2023 11:12 #115
Лучшее, что может быть при изучении материала,это практика.
Поэтому слушая и вникая в уроки maksimKorzh я решил адаптировать практические занятия (написание кода) к среде Делфи.
Урок №2.
program bbc;
{$APPTYPE CONSOLE}
uses
SysUtils,Windows;
type
U64 = UInt64;
TBoard_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,
a3, b3, c3, d3, e3, f3, g3, h3,
a2, b2, c2, d2, e2, f2, g2, h2,
a1, b1, c1, d1, e1, f1, g1, h1
);
var
bitboard:U64=0;
//square:TBoard_squares;
// set/get/pop
function get_bit(bb:U64;const sq:integer):integer;
begin
get_bit:=(bb shr sq) and 1;
end;
procedure set_bit(var bb:U64;const sq:TBoard_squares);
begin
bb:=bb or ($8000000000000000 shr (63-Ord(sq)));
end;
procedure pop_bit(var bb:U64;const sq:TBoard_squares);
begin
if get_bit(bb,Ord(sq))>0 then bb:=bb xor ($8000000000000000 shr (63-Ord(sq)));
end;
// print bitboard
procedure print_bitboard(bb:U64);
var
rank_,file_,sq:integer;
begin
Writeln('');
// loop over board ranks
for rank_ := 0 to 7 do begin
// loop over board files
for file_ := 0 to 7 do begin
// convert file & rank into square index
sq:=rank_*8 + file_;
//// print ranks
if file_ = 0 then begin
Write(8 - rank_);Write(' ');
end;
Write(' ');
// print bit state (either 1 or 0)
Write(get_bit(bb,sq));
end;
// print new line every rank
Writeln('');
end;
// print new line
Writeln('');
// print board files
Writeln(' a b c d e f g h');
Writeln('');
// print bitboard as unsigned decimal number
Write('bitboard = ',bb);
Writeln('');
end;
{/**********************************\
==================================
Main driver
==================================
\**********************************/}
begin
//Переключение окна консоли на кодовую страницу CP1251 (Win-1251).
//Если после переключения русские буквы показываются неверно,
//следует открыть системное меню консольного окна - щелчком мыши в левом
//верхнем углу окна консоли. И выбрать:
//Свойства - закладка "Шрифт" - выбрать шрифт: "Lucida Console".
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
// ==================================
bitboard:=$8000000000000000;//$ - шестнадцатеричное представление числа
print_bitboard(bitboard);
// setting some bits
set_bit(bitboard,a4);set_bit(bitboard,b4);
print_bitboard(bitboard);
bitboard:=$FFFFFFFFFFFFFFFF;
print_bitboard(bitboard);
// reset bit
pop_bit(bitboard,a4); pop_bit(bitboard,b4);pop_bit(bitboard,c4); pop_bit(bitboard,d4);
print_bitboard(bitboard);
Writeln('Нажмите <ENTER>, чтобы выйти ...');
Readln;
end.
Bitboard в программировании шахмат №2
20 Янв 2023 14:12 #116
Уроки 3 и 4 и 5
Таблица атак пешек,коня и корля
program bbc;
{$APPTYPE CONSOLE}
uses
SysUtils,Windows;
type
U64 = UInt64;
TBoard_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,
a3, b3, c3, d3, e3, f3, g3, h3,
a2, b2, c2, d2, e2, f2, g2, h2,
a1, b1, c1, d1, e1, f1, g1, h1
);
TSide = (white, black);
//Первый индекс обозначает номер строки в матрице, второй индекс – номер столбца
TPawn_attacks=array[TSide,TBoard_squares] of U64;
TChip_attacks=array[TBoard_squares] of U64;
var
bitboard:U64=0;
// pawn attacks table [side][square]
pawn_attacks:TPawn_attacks;
// knight attacks table [square]
knight_attacks:TChip_attacks;
// king attacks table [square]
king_attacks:TChip_attacks;
const
{/*
not A file
8 0 1 1 1 1 1 1 1
7 0 1 1 1 1 1 1 1
6 0 1 1 1 1 1 1 1
5 0 1 1 1 1 1 1 1
4 0 1 1 1 1 1 1 1
3 0 1 1 1 1 1 1 1
2 0 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1
a b c d e f g h
not H file
8 1 1 1 1 1 1 1 0
7 1 1 1 1 1 1 1 0
6 1 1 1 1 1 1 1 0
5 1 1 1 1 1 1 1 0
4 1 1 1 1 1 1 1 0
3 1 1 1 1 1 1 1 0
2 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 0
a b c d e f g h
not HG file
8 1 1 1 1 1 1 0 0
7 1 1 1 1 1 1 0 0
6 1 1 1 1 1 1 0 0
5 1 1 1 1 1 1 0 0
4 1 1 1 1 1 1 0 0
3 1 1 1 1 1 1 0 0
2 1 1 1 1 1 1 0 0
1 1 1 1 1 1 1 0 0
a b c d e f g h
not AB file
8 0 0 1 1 1 1 1 1
7 0 0 1 1 1 1 1 1
6 0 0 1 1 1 1 1 1
5 0 0 1 1 1 1 1 1
4 0 0 1 1 1 1 1 1
3 0 0 1 1 1 1 1 1
2 0 0 1 1 1 1 1 1
1 0 0 1 1 1 1 1 1
a b c d e f g h
*/}
// not A file constant
not_a_file:U64 = $FEFEFEFEFEFEFEFE;//18374403900871474942;
// not H file constant
not_h_file:U64 = $7F7F7F7F7F7F7F7F;//9187201950435737471;
// not HG file constant
not_hg_file:U64 =$3F3F3F3F3F3F3F3F;//4557430888798830399;
// not AB file constant
not_ab_file:U64 =$FCFCFCFCFCFCFCFC;//18229723555195321596;
//square:TBoard_squares;
{/**********************************\
==================================
Bit manipulations
==================================
\**********************************/}
// set/get/pop
function get_bit(bb:U64;const sq:integer):integer;
begin
get_bit:=(bb shr sq) and 1;
end;
procedure set_bit(var bb:U64;const sq:TBoard_squares);
begin
bb:=bb or ($8000000000000000 shr (63-Ord(sq)));
end;
procedure pop_bit(var bb:U64;const sq:TBoard_squares);
begin
if get_bit(bb,Ord(sq))>0 then bb:=bb xor ($8000000000000000 shr (63-Ord(sq)));
end;
{/**********************************\
==================================
Input & Output
==================================
\**********************************/}
// print bitboard
procedure print_bitboard(bb:U64);
var
rank_,file_,sq:integer;
begin
Writeln('');
// loop over board ranks
for rank_ := 0 to 7 do begin
// loop over board files
for file_ := 0 to 7 do begin
// convert file & rank into square index
sq:=rank_*8 + file_;
//// print ranks
if file_ = 0 then begin
Write(8 - rank_);Write(' ');
end;
Write(' ');
// print bit state (either 1 or 0)
Write(get_bit(bb,sq));
end;
// print new line every rank
Writeln('');
end;
// print new line
Writeln('');
// print board files
Writeln(' a b c d e f g h');
Writeln('');
// print bitboard as unsigned decimal number
Write('bitboard = ',bb);
Writeln('');
end;
{/**********************************\
==================================
Attacks
==================================
\**********************************/}
// generate pawn attacks
function mask_pawn_attacks(side:TSide;square:TBoard_squares):U64;
var
attacks,bitboard:U64;
begin
// result attacks bitboard
attacks := 0;
// piece bitboard
bitboard := 0;
// set piece on board
set_bit(bitboard, square);
// white pawns
if (side=white) then begin
if ((bitboard shr 7) and not_a_file)>0 then attacks:=attacks or (bitboard shr 7);
if ((bitboard shr 9) and not_h_file)>0 then attacks:=attacks or (bitboard shr 9);
end
// black pawns
else begin
if ((bitboard shl 7) and not_h_file)>0 then attacks:=attacks or (bitboard shl 7);
if ((bitboard shl 9) and not_a_file)>0 then attacks:=attacks or (bitboard shl 9);
end;
// return attack map
mask_pawn_attacks:=attacks;
end;
// generate knight attacks
function mask_knight_attacks(square:TBoard_squares):U64;
var
attacks,bitboard:U64;
begin
// result attacks bitboard
attacks := 0;
// piece bitboard
bitboard := 0;
// set piece on board
set_bit(bitboard, square);
// generate knight attacks
if ((bitboard shr 17) and not_h_file)>0 then attacks:=attacks or (bitboard shr 17);
if ((bitboard shr 15) and not_a_file)>0 then attacks:=attacks or (bitboard shr 15);
if ((bitboard shr 10) and not_hg_file)>0 then attacks:=attacks or (bitboard shr 10);
if ((bitboard shr 6) and not_ab_file)>0 then attacks:=attacks or (bitboard shr 6);
if ((bitboard shl 17) and not_a_file)>0 then attacks:=attacks or (bitboard shl 17);
if ((bitboard shl 15) and not_h_file)>0 then attacks:=attacks or (bitboard shl 15);
if ((bitboard shl 10) and not_ab_file)>0 then attacks:=attacks or (bitboard shl 10);
if ((bitboard shl 6) and not_hg_file)>0 then attacks:=attacks or (bitboard shl 6);
// return attack map
mask_knight_attacks:=attacks;
end;
// generate king attacks
function mask_king_attacks(square:TBoard_squares):U64;
var
attacks,bitboard:U64;
begin
// result attacks bitboard
attacks := 0;
// piece bitboard
bitboard := 0;
// set piece on board
set_bit(bitboard, square);
// generate king attacks
if (bitboard shr 8)>0 then attacks:=attacks or (bitboard shr 8);
if ((bitboard shr 9) and not_h_file)>0 then attacks:=attacks or (bitboard shr 9);
if ((bitboard shr 1) and not_h_file)>0 then attacks:=attacks or (bitboard shr 1);
if ((bitboard shr 7) and not_a_file)>0 then attacks:=attacks or (bitboard shr 7);
if (bitboard shl 8)>0 then attacks:=attacks or (bitboard shl 8);
if ((bitboard shl 9) and not_a_file)>0 then attacks:=attacks or (bitboard shl 9);
if ((bitboard shl 1) and not_a_file)>0 then attacks:=attacks or (bitboard shl 1);
if ((bitboard shl 7) and not_h_file)>0 then attacks:=attacks or (bitboard shl 7);
// return attack map
mask_king_attacks:=attacks;
end;
// init leaper pieces attacks
procedure init_leapers_attacks();
var
square:TBoard_squares;
begin
// loop over 64 board squares
for square := a8 to h1 do begin
// init pawn attacks
pawn_attacks[white][square] := mask_pawn_attacks(white,square);
pawn_attacks[black][square] := mask_pawn_attacks(black,square);
// init knight attacks
knight_attacks[square] := mask_knight_attacks(square);
// init king attacks
king_attacks[square] := mask_king_attacks(square);
end;
end;
{/**********************************\
==================================
Main driver
==================================
\**********************************/}
begin
//Переключение окна консоли на кодовую страницу CP1251 (Win-1251).
//Если после переключения русские буквы показываются неверно,
//следует открыть системное меню консольного окна - щелчком мыши в левом
//верхнем углу окна консоли. И выбрать:
//Свойства - закладка "Шрифт" - выбрать шрифт: "Lucida Console".
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
// ==================================
init_leapers_attacks();
print_bitboard(king_attacks[d5]);
Writeln('Нажмите <ENTER>, чтобы выйти ...');
Readln;
end.
Следующие уроки посвящены атакам дальнобойных фигур.
Идея реализованная данным товарищем - нахождение атак дальнобойных фигур с помощью магических чисел.
У меня расчеты атак прыгющих фигур (пешек,коня и короля) берутся непосредственно из таблицы
Bitboard в программировании шахмат №2
23 Янв 2023 11:30 #117
Уроки 6, 7 атаки слона и ладьи до края доски (края не включены)
Урок 8 атаки слона и ладьи с учетом блокирующих фигур.
program bbc;
{$APPTYPE CONSOLE}
uses
SysUtils,Windows;
type
U64 = UInt64;
TBoard_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,
a3, b3, c3, d3, e3, f3, g3, h3,
a2, b2, c2, d2, e2, f2, g2, h2,
a1, b1, c1, d1, e1, f1, g1, h1
);
TSide = (white, black);
//Первый индекс обозначает номер строки в матрице, второй индекс – номер столбца
TPawn_attacks=array[TSide,TBoard_squares] of U64;
TChip_attacks=array[TBoard_squares] of U64;
var
bitboard:U64=0;
block:U64=0;
// pawn attacks table [side][square]
pawn_attacks:TPawn_attacks;
// knight attacks table [square]
knight_attacks:TChip_attacks;
// king attacks table [square]
king_attacks:TChip_attacks;
//square:TBoard_squares;
const
{/*
not A file
8 0 1 1 1 1 1 1 1
7 0 1 1 1 1 1 1 1
6 0 1 1 1 1 1 1 1
5 0 1 1 1 1 1 1 1
4 0 1 1 1 1 1 1 1
3 0 1 1 1 1 1 1 1
2 0 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1
a b c d e f g h
not H file
8 1 1 1 1 1 1 1 0
7 1 1 1 1 1 1 1 0
6 1 1 1 1 1 1 1 0
5 1 1 1 1 1 1 1 0
4 1 1 1 1 1 1 1 0
3 1 1 1 1 1 1 1 0
2 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 0
a b c d e f g h
not HG file
8 1 1 1 1 1 1 0 0
7 1 1 1 1 1 1 0 0
6 1 1 1 1 1 1 0 0
5 1 1 1 1 1 1 0 0
4 1 1 1 1 1 1 0 0
3 1 1 1 1 1 1 0 0
2 1 1 1 1 1 1 0 0
1 1 1 1 1 1 1 0 0
a b c d e f g h
not AB file
8 0 0 1 1 1 1 1 1
7 0 0 1 1 1 1 1 1
6 0 0 1 1 1 1 1 1
5 0 0 1 1 1 1 1 1
4 0 0 1 1 1 1 1 1
3 0 0 1 1 1 1 1 1
2 0 0 1 1 1 1 1 1
1 0 0 1 1 1 1 1 1
a b c d e f g h
*/}
// not A file constant
not_a_file:U64 = $FEFEFEFEFEFEFEFE;//18374403900871474942;
// not H file constant
not_h_file:U64 = $7F7F7F7F7F7F7F7F;//9187201950435737471;
// not HG file constant
not_hg_file:U64 =$3F3F3F3F3F3F3F3F;//4557430888798830399;
// not AB file constant
not_ab_file:U64 =$FCFCFCFCFCFCFCFC;//18229723555195321596;
{/**********************************\
==================================
Bit manipulations
==================================
\**********************************/}
// set/get/pop
function get_bit(bb:U64;const sq:integer):integer;
begin
get_bit:=(bb shr sq) and 1;
end;
procedure set_bit(var bb:U64;const sq:TBoard_squares);
begin
bb:=bb or ($8000000000000000 shr (63-Ord(sq)));
end;
procedure pop_bit(var bb:U64;const sq:TBoard_squares);
begin
if get_bit(bb,Ord(sq))>0 then bb:=bb xor ($8000000000000000 shr (63-Ord(sq)));
end;
{/**********************************\
==================================
Input & Output
==================================
\**********************************/}
// print bitboard
procedure print_bitboard(bb:U64);
var
rank_,file_,sq:integer;
begin
Writeln('');
// loop over board ranks
for rank_ := 0 to 7 do begin
// loop over board files
for file_ := 0 to 7 do begin
// convert file & rank into square index
sq:=rank_*8 + file_;
//// print ranks
if file_ = 0 then begin
Write(8 - rank_);Write(' ');
end;
Write(' ');
// print bit state (either 1 or 0)
Write(get_bit(bb,sq));
end;
// print new line every rank
Writeln('');
end;
// print new line
Writeln('');
// print board files
Writeln(' a b c d e f g h');
Writeln('');
// print bitboard as unsigned decimal number
Write('bitboard = ',bb);
Writeln('');
end;
{/**********************************\
==================================
Attacks
==================================
\**********************************/}
// generate pawn attacks
function mask_pawn_attacks(side:TSide;square:TBoard_squares):U64;
var
attacks,bitboard:U64;
begin
// result attacks bitboard
attacks := 0;
// piece bitboard
bitboard := 0;
// set piece on board
set_bit(bitboard, square);
// white pawns
if (side=white) then begin
if ((bitboard shr 7) and not_a_file)>0 then attacks:=attacks or (bitboard shr 7);
if ((bitboard shr 9) and not_h_file)>0 then attacks:=attacks or (bitboard shr 9);
end
// black pawns
else begin
if ((bitboard shl 7) and not_h_file)>0 then attacks:=attacks or (bitboard shl 7);
if ((bitboard shl 9) and not_a_file)>0 then attacks:=attacks or (bitboard shl 9);
end;
// return attack map
mask_pawn_attacks:=attacks;
end;
// generate knight attacks
function mask_knight_attacks(square:TBoard_squares):U64;
var
attacks,bitboard:U64;
begin
// result attacks bitboard
attacks := 0;
// piece bitboard
bitboard := 0;
// set piece on board
set_bit(bitboard, square);
// generate knight attacks
if ((bitboard shr 17) and not_h_file)>0 then attacks:=attacks or (bitboard shr 17);
if ((bitboard shr 15) and not_a_file)>0 then attacks:=attacks or (bitboard shr 15);
if ((bitboard shr 10) and not_hg_file)>0 then attacks:=attacks or (bitboard shr 10);
if ((bitboard shr 6) and not_ab_file)>0 then attacks:=attacks or (bitboard shr 6);
if ((bitboard shl 17) and not_a_file)>0 then attacks:=attacks or (bitboard shl 17);
if ((bitboard shl 15) and not_h_file)>0 then attacks:=attacks or (bitboard shl 15);
if ((bitboard shl 10) and not_ab_file)>0 then attacks:=attacks or (bitboard shl 10);
if ((bitboard shl 6) and not_hg_file)>0 then attacks:=attacks or (bitboard shl 6);
// return attack map
mask_knight_attacks:=attacks;
end;
// generate king attacks
function mask_king_attacks(square:TBoard_squares):U64;
var
attacks,bitboard:U64;
begin
// result attacks bitboard
attacks := 0;
// piece bitboard
bitboard := 0;
// set piece on board
set_bit(bitboard, square);
// generate king attacks
if (bitboard shr 8)>0 then attacks:=attacks or (bitboard shr 8);
if ((bitboard shr 9) and not_h_file)>0 then attacks:=attacks or (bitboard shr 9);
if ((bitboard shr 1) and not_h_file)>0 then attacks:=attacks or (bitboard shr 1);
if ((bitboard shr 7) and not_a_file)>0 then attacks:=attacks or (bitboard shr 7);
if (bitboard shl 8)>0 then attacks:=attacks or (bitboard shl 8);
if ((bitboard shl 9) and not_a_file)>0 then attacks:=attacks or (bitboard shl 9);
if ((bitboard shl 1) and not_a_file)>0 then attacks:=attacks or (bitboard shl 1);
if ((bitboard shl 7) and not_h_file)>0 then attacks:=attacks or (bitboard shl 7);
// return attack map
mask_king_attacks:=attacks;
end;
//урок 6-masking relevant bishop occupancy bits to form a key for MAGIC BITBOARDS
// mask bishop attacks
function mask_bishop_attacks(square:TBoard_squares):U64;
var
attacks,n:U64;
r,f,tr,tf:integer;
begin
n:=1;
// result attacks bitboard
attacks := 0;
// init target rank & files
tr := Ord(square) div 8;//целочисленное деление
tf := Ord(square) mod 8;//остаток от деления
// mask relevant bishop occupancy bits
f:=tf+1;
for r:=tr+1 to 6 do begin
if f>6 then break;
attacks := attacks or (n shl (r*8+f));
Inc(f);
end;
f:=tf+1;
for r:=tr-1 downto 1 do begin
if f>6 then break;
attacks := attacks or (n shl (r*8+f));
Inc(f);
end;
f:=tf-1;
for r:=tr+1 to 6 do begin
if f<1 then break;
attacks := attacks or (n shl (r*8+f));
Dec(f);
end;
f:=tf-1;
for r:=tr-1 downto 1 do begin
if f<1 then break;
attacks := attacks or (n shl (r*8+f));
Dec(f);
end;
// return attack map
mask_bishop_attacks:=attacks;
end;
//урок 7-masking relevant ROOK OCCUPANCY BITS to form a key for MAGIC BITBOARDS
// mask rook attacks
function mask_rook_attacks(square:TBoard_squares):U64;
var
attacks,n:U64;
r,f,tr,tf:integer;
begin
n:=1;
// result attacks bitboard
attacks := 0;
// init target rank & files
tr := Ord(square) div 8;//целочисленное деление
tf := Ord(square) mod 8;//остаток от деления
// mask relevant bishop occupancy bits
for r:=tr+1 to 6 do attacks := attacks or (n shl (r*8+tf));
for r:=tr-1 downto 1 do attacks := attacks or (n shl (r*8+tf));
for f:=tf+1 to 6 do attacks := attacks or (n shl (tr*8+f));
for f:=tf-1 downto 1 do attacks := attacks or (n shl (tr*8+f));
// return attack map
mask_rook_attacks:=attacks;
end;
//урок 8-generating SLIDER PIECES ATTACKS on the fly for MAGIC BITBOARD purposes
// generate bishop attacks on the fly
function bishop_attacks_on_the_fly(square:TBoard_squares;blk:U64):U64;
var
attacks,n:U64;
r,f,tr,tf:integer;
begin
n:=1;
// result attacks bitboard
attacks := 0;
// init target rank & files
tr := Ord(square) div 8;//целочисленное деление
tf := Ord(square) mod 8;//остаток от деления
// generate bishop atacks
f:=tf+1;
for r:=tr+1 to 7 do begin
if f>7 then break;
attacks := attacks or (n shl (r*8+f));
if ((n shl (r*8+f)) and blk)>0 then break;
Inc(f);
end;
f:=tf+1;
for r:=tr-1 downto 0 do begin
if f>7 then break;
attacks := attacks or (n shl (r*8+f));
if ((n shl (r*8+f)) and blk)>0 then break;
Inc(f);
end;
f:=tf-1;
for r:=tr+1 to 7 do begin
if f<0 then break;
attacks := attacks or (n shl (r*8+f));
if ((n shl (r*8+f)) and blk)>0 then break;
Dec(f);
end;
f:=tf-1;
for r:=tr-1 downto 0 do begin
if f<0 then break;
attacks := attacks or (n shl (r*8+f));
if ((n shl (r*8+f)) and blk)>0 then break;
Dec(f);
end;
// return attack map
bishop_attacks_on_the_fly:=attacks;
end;
// generate rook attacks on the fly
function rook_attacks_on_the_fly(square:TBoard_squares;blk:U64):U64;
var
attacks,n:U64;
r,f,tr,tf:integer;
begin
n:=1;
// result attacks bitboard
attacks := 0;
// init target rank & files
tr := Ord(square) div 8;//целочисленное деление
tf := Ord(square) mod 8;//остаток от деления
// generate rook attacks
for r:=tr+1 to 7 do begin
attacks := attacks or (n shl (r*8+tf));
if ((n shl (r*8+tf)) and blk)>0 then break;
end;
for r:=tr-1 downto 0 do begin
attacks := attacks or (n shl (r*8+tf));
if ((n shl (r*8+tf)) and blk)>0 then break;
end;
for f:=tf+1 to 7 do begin
attacks := attacks or (n shl (tr*8+f));
if ((n shl (tr*8+f)) and blk)>0 then break;
end;
for f:=tf-1 downto 0 do begin
attacks := attacks or (n shl (tr*8+f));
if ((n shl (tr*8+f)) and blk)>0 then break;
end;
// return attack map
rook_attacks_on_the_fly:=attacks;
end;
// init leaper pieces attacks
procedure init_leapers_attacks();
var
square:TBoard_squares;
begin
// loop over 64 board squares
for square := a8 to h1 do begin
//урок 3-generating pre-calculated PAWN ATTACK tables
// init pawn attacks
pawn_attacks[white][square] := mask_pawn_attacks(white,square);
pawn_attacks[black][square] := mask_pawn_attacks(black,square);
//урок 4-generating pre-calculated KNIGHT ATTACK table
// init knight attacks
knight_attacks[square] := mask_knight_attacks(square);
//урок 5-generating pre-calculated KING ATTACK tables
// init king attacks
king_attacks[square] := mask_king_attacks(square);
end;
end;
{/**********************************\
==================================
Main driver
==================================
\**********************************/}
begin
//Переключение окна консоли на кодовую страницу CP1251 (Win-1251).
//Если после переключения русские буквы показываются неверно,
//следует открыть системное меню консольного окна - щелчком мыши в левом
//верхнем углу окна консоли. И выбрать:
//Свойства - закладка "Шрифт" - выбрать шрифт: "Lucida Console".
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
// ==================================
init_leapers_attacks();
set_bit(block,b5);set_bit(block,f3);set_bit(block,g5); set_bit(block,f7);
print_bitboard(rook_attacks_on_the_fly(c5,block));
Writeln('Нажмите <ENTER>, чтобы выйти ...');
Readln;
end.
Освоенные уроки
2. Bitboard CHESS ENGINE in C: creating comfortable conditions for development
3. Bitboard CHESS ENGINE in C: generating pre-calculated PAWN ATTACK tables
4. Bitboard CHESS ENGINE in C: generating pre-calculated KNIGHT ATTACK table
5. Bitboard CHESS ENGINE in C: generating pre-calculated KING ATTACK tables
6. Bitboard CHESS ENGINE in C: masking relevant bishop occupancy bits to form a key for MAGIC BITBOARDS
7. Bitboard CHESS ENGINE in C: masking relevant ROOK OCCUPANCY BITS to form a key for MAGIC BITBOARDS
8. Bitboard CHESS ENGINE in C: generating SLIDER PIECES ATTACKS on the fly for MAGIC BITBOARD purposes
Bitboard в программировании шахмат №2
23 Янв 2023 13:48 #118
Сегодня узнал что-то новое и важное для себя. из урока - №9 - implementing BIT COUNT routine (Brian Kernighan's way).
А именно - Алгоритм Брайана Кернигана для подсчета установленных бит в целом числе.
Супер алгоритм.
Реализация на Делфи
// count bits within a bitboard (Brian Kernighan's way)
function count_bits(bb:U64):integer;
var
count:integer;
begin
// bit counter
count := 0;
// consecutively reset least significant 1st bit
while bb>0
do begin
// increment count
Inc(count);
// reset least significant 1st bit
bb := bb and (bb - 1);
end;
count_bits:=count;
end;
Bitboard в программировании шахмат №2
23 Янв 2023 14:18 #119
Странно.
Этот алгоритм работает в два раза медленне, чем я ожидал.
У меня такая реализация подсчета битов
//Подсчет количества установленных бит в integer
function CountBits(const Value: integer): integer;
asm
mov ECX,EAX
xor EAX,EAX
test ECX,ECX
jz @@ending
@@counting:
shr ECX,1
adc EAX,0
test ECX,ECX
jnz @@counting
@@ending:
end;
//Подсчет количества установленных бит в Int64
function CountBitsInt64(const integer64:UInt64):integer;
begin
result:=CountBits(integer64)+CountBits(integer64 shr 32);
end;
Bitboard в программировании шахмат №2
23 Янв 2023 17:50 #120
В принципе Алгоритм Брайана Кернигана работает не плохо, в случае, когда число установленных бит не велико.
Пример - установлен самый старший бит - $8000000000000000.
В данном случаи он работает в 2 раза быстрее, чем тот, который использовал я.
Поэтому оставлю его.
Замеры делал так
function RDTSC: UInt64;
{
rdtsc (англ. Read Time Stamp Counter) — ассемблерная инструкция
для платформ x86 и x86_64, читающая счётчик TSC (Time Stamp Counter)
и возвращающая в регистрах EDX:EAX 64-битное количество тактов
с момента последнего сброса процессора.
}
//t1,t2:UInt64;
//t1:=RDTSC;
//t2:=RDTSC-t1;
//ShowMessage(IntToStr(t2));
asm
rdtsc
end;
print_bitboard($8000000000000000);
t1:=RDTSC;
count_bits($8000000000000000);
t2:=RDTSC-t1;
Writeln('count_bits = ',count_bits($8000000000000000));
Writeln('Brian Kernighan s way - ',t2);
t1:=RDTSC;
CountBitsInt64($8000000000000000);
t2:=RDTSC-t1;
Writeln('count_bits = ',CountBitsInt64($8000000000000000));
Writeln('CountBitsInt64 - ',t2);
Writeln('Нажмите <ENTER>, чтобы выйти ...');
Readln;
