Bitboard в программировании шахмат №2
23 Янв 2023 19:57 #121
10 урок - нахождение индекса младшего значащего бита и возвращение его координаты в шахматной нотации
program bbc;
{$APPTYPE CONSOLE}
uses
SysUtils,Windows,TypInfo;
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;
square_to_coordinates: array [0..63] of string = (
'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'
);
{/**********************************\
==================================
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;
// 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;
// get least significant 1st bit index
function get_ls1b_index(bb:U64):integer;
begin
// make sure bitboard is not 0
if bb<>0 then
// count trailing bits before LS1B
result:=count_bits((bb and (-bb))-1)
// return illegal index
else result:=-1;
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();
block:=4512464976740352;
print_bitboard(block);
square:=TBoard_squares(get_ls1b_index(block));
Write('get_ls1b_index:',get_ls1b_index(block));
Writeln(' coordinate:',square_to_coordinates[Ord(square)]);
set_bit(bitboard,square);
print_bitboard(bitboard);
Writeln('Нажмите <ENTER>, чтобы выйти ...');
Readln;
end.
Bitboard в программировании шахмат №2
24 Янв 2023 09:47 #122
Разобрался с 11 уроком - Bitboard CHESS ENGINE in C: populating OCCUPANCY sets to multiply them later by MAGIC NUMBERS.
Пока это все подготовка к реализации Magic Bitboards
В этом уроке описывается функция нызываемая - начальными занятиями (set_occupancy).
По сути это комбинация всех различных расположений фигур на линии атаки скользящей фигуры (ладьи, слона).
8/8/8/8/8/8/8/R7
Например при ладье на a1 и ее атаках по линиям A2-A7 и B1-G1 (края доски не учитываются), теоретически эти поля могут быть заняты другими фигурами в различных комбинациях. По сути мы имеем дело с 6 клетками по вертикали и 6 по горизонали.
6 клеток это число с 6 включенными битами, соответствует числу 63.
Правило умножения (основная формула комбинаторики)
Общее число N способов, которыми можно выбрать по одному элементу из каждой группы и расставить их в определенном порядке (то есть получить упорядоченную совокупность a,b,c,d), равно:
N=n1*n2*n3* ... nk
T.e. в нашел случае при ладье на a1
N=64*64=4096 различных комбинаций занятости этих линий.
В двоичном виде это число выглядит так
По сути пробегая в цикле от нуля до 4095 мы получим все эти различные комбинации перестановок
block:=mask_rook_attacks(a1);
print_bitboard(block);
for i:=0 to 4095 do begin
block:=mask_rook_attacks(a1);
bitboard:=set_occupancy(i,count_bits(block),block);
print_bitboard(bitboard);
Readln;
end;
Writeln('Нажмите <ENTER>, чтобы выйти ...');
Readln;
// make sure occupancy is on board
if (index and (1 shl count))>0 then
occupancy:=occupancy or (n shl integer(square_));
Index -это как раз число перестановок (в конкретном случае - 4096)
Т.е. пробигая по вариантам занятости for i:=0 to 4095 при условии - i and (1 shl count) мы находим установленный бит и и получаем конкретную занятость для i.
Короче вот реализация на Делфи
// set occupancies
//перебираем по очереди биты в attack_mask
function set_occupancy(index,bits_in_mask:integer;var attack_mask:U64):U64;
var
occupancy,n:U64;
count:integer;
square_:TBoard_squares;
begin
n:=1;
// occupancy map
occupancy:=0;
// loop over the range of bits within attack mask
for count:=0 to bits_in_mask-1 do begin
// get LS1B index of attacks mask
square_:=TBoard_squares(get_ls1b_index(attack_mask));
// pop LS1B in attack map
pop_bit(attack_mask,square_);
// make sure occupancy is on board
if (index and (n shl count))>0 then
occupancy:=occupancy or (n shl integer(square_));
end;
set_occupancy:=occupancy;
end;
Writeln('bishop_relevant_bits');
for square := a8 to h1 do begin
if (((integer(square) mod 8)=0) and (square > a8)) then Writeln('');
Write(count_bits(mask_bishop_attacks(square))); Write(' ');
end;
Writeln('');
Writeln('rook_relevant_bits');
for square := a8 to h1 do begin
if (((integer(square) mod 8)=0) and (square > a8)) then Writeln('');
Write(count_bits(mask_rook_attacks(square))); Write(' ');
end;
Writeln('');
Writeln('Нажмите <ENTER>, чтобы выйти ...');
Readln;
Bitboard в программировании шахмат №2
25 Янв 2023 05:11 #124
Уроки 13 и 14
13.Bitboard CHESS ENGINE in C: implementing pseudo RANDOM NUMBER generator using XORSHIFT32 algorithm
14.Bitboard CHESS ENGINE in C: generating MAGIC NUMBER candidates
Макс рассказывает как сгенерировать числа - кандитаты в магические числа.
По сути - это псевдослучайные числа.
И самое интересное, далее он расскажет, как их использовать в качестве магических чисел.
{/**********************************\
==================================
Random numbers
==================================
\**********************************/}
// generate 32-bit pseudo legal numbers
function get_random_U32_number():cardinal;
begin
// XOR shift algorithm
stateU32:=stateU32 xor (stateU32 shl 13);
stateU32:=stateU32 xor (stateU32 shr 17);
stateU32:=stateU32 xor (stateU32 shl 5);
get_random_U32_number:=stateU32;
end;
// generate 64-bit pseudo legal numbers
function get_random_U64_number():U64;
var
// define 4 random numbers
n1,n2,n3,n4:U64;
begin
n1:=0;n2:=0;n3:=0; n4:=0;
// init random numbers slicing 16 bits from MS1B side
n1:=n1 or (get_random_U32_number() and $FFFF);
n2:=n2 or (get_random_U32_number() and $FFFF);
n3:=n3 or (get_random_U32_number() and $FFFF);
n4:=n4 or (get_random_U32_number() and $FFFF);
// return random number
get_random_U64_number:=n1 or (n2 shl 16) or (n3 shl 32) or (n4 shl 48);
end;
// generate magic number candidate
function generate_magic_number():U64;
begin
result:=get_random_U64_number() and get_random_U64_number() and get_random_U64_number();
end;
Хотя эти числа всегда одни и те же, но раз это работает, то делаем так же.
Bitboard в программировании шахмат №2
27 Янв 2023 12:53 #126
Урок 15.Bitboard CHESS ENGINE in C: generating MAGIC NUMBERS via brute force trial and error method.
Разобрался с этим уроком - генерация магических чисел.
Попробую рассказать свое понимание этого.
Итак, какие исходные данные есть у нас.
1. Позиция дальнобойной фигуры (например ладья на a1)
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
);
2. Количество атакуемых клеток из этой позиции при отсутствии блокирующих фигур (края доски не учитываются)
(ладья на a1 атакует 6 клеток по горизонтали, 6 по вертикали: всего 12)
// rook relevant occupancy bit count for every square on board
rook_relevant_bits: array [0..63] of integer =(
12, 11, 11, 11, 11, 11, 11, 12,
11, 10, 10, 10, 10, 10, 10, 11,
11, 10, 10, 10, 10, 10, 10, 11,
11, 10, 10, 10, 10, 10, 10, 11,
11, 10, 10, 10, 10, 10, 10, 11,
11, 10, 10, 10, 10, 10, 10, 11,
11, 10, 10, 10, 10, 10, 10, 11,
12, 11, 11, 11, 11, 11, 11, 12
);
Производные от первоначальных данных
1.битбоард атаки (ладьи) этих 12 клеток
attack_mask:=mask_bishop_attacks(square)
2. Количество перестановок блокирующих фигур на атакуемых ладьей полях
occupancy_indicies:integer;
- 64*64
- 2 в степени 12
- 1 << 12
occupancy_indicies:=1 shl relevant_bits;
3.Комбинации занятости блокирующих фигур
occupancies:array[0..4095] of U64;
4.Самое важное это атаки с учетом блокирующих фигур
// init attack tables
attacks:array[0..4095] of U64;
Вроде бы все прекрасно - эти атаки нам и нужны в идеале.
Но есть одно большое НО.
Чтобы найти их в таблице array[0..4095], придется долго и упорно ее перелапачивать.
Умные люди решили проблему так -
Придумать такую хэш функция, чтобы с помощью простого ключа быстро находить нужные атаки в таблице.
Ключ, это и есть - магическое число с простыми манипуляциями с ним.
Это как подойти к реальной двери, глянуть на скважину замка, достать отмычку, туда сюда ее изогнуть на глаз и пробовать открыть замок.
Этот урок Макса, как раз и есть, описание способа, гнуть отмычку туда сюда , чтобы получить ключ.
Способ такой.
1.Создается массив
// init used attacks
used_attacks:array[0..4095] of U64;
Инициализируется 0.
FillChar(used_attacks, 4096*SizeOf(UInt64), n); - делфи
memset(used_attacks, 0ULL, sizeof(used_attacks)); - СИ
2.U64 magic_number - генерируем 64 битные случайные числа
3.Подставляем ключ в хэш функцию
magic_index := integer((occupancies[index] * magic_number) shr (64 - relevant_bits)); - делфи
int magic_index = (int)((occupancies[index] * magic_number) >> (64 - relevant_bits)); - Си
Пробуем полученный ключ - если уже был другой ключ, то это коллизия ( ключ выбрасываем)
Bitboard в программировании шахмат №2
27 Янв 2023 12:54 #127
На языке Си (Макс)
/**********************************\
==================================
Didactic
BITBOARD CHESS ENGINE
by
Code Monkey King
==================================
\**********************************/
// system headers
#include <stdio.h>
#include <string.h>
// define bitboard data type
#define U64 unsigned long long
// board squares
enum {
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
};
// sides to move (colors)
enum { white, black };
// bishop and rook
enum { rook, bishop };
// convert squares to coordinates
const char *square_to_coordinates[] = {
"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",
};
/**********************************\
==================================
Random numbers
==================================
\**********************************/
// pseudo random number state
unsigned int random_state = 1804289383;
// generate 32-bit pseudo legal numbers
unsigned int get_random_U32_number()
{
// get current state
unsigned int number = random_state;
// XOR shift algorithm
number ^= number << 13;
number ^= number >> 17;
number ^= number << 5;
// update random number state
random_state = number;
// return random number
return number;
}
// generate 64-bit pseudo legal numbers
U64 get_random_U64_number()
{
// define 4 random numbers
U64 n1, n2, n3, n4;
// init random numbers slicing 16 bits from MS1B side
n1 = (U64)(get_random_U32_number()) & 0xFFFF;
n2 = (U64)(get_random_U32_number()) & 0xFFFF;
n3 = (U64)(get_random_U32_number()) & 0xFFFF;
n4 = (U64)(get_random_U32_number()) & 0xFFFF;
// return random number
return n1 | (n2 << 16) | (n3 << 32) | (n4 << 48);
}
// generate magic number candidate
U64 generate_magic_number()
{
return get_random_U64_number() & get_random_U64_number() & get_random_U64_number();
}
/**********************************\
==================================
Bit manipulations
==================================
\**********************************/
// set/get/pop bit macros
#define set_bit(bitboard, square) (bitboard |= (1ULL << square))
#define get_bit(bitboard, square) (bitboard & (1ULL << square))
#define pop_bit(bitboard, square) (get_bit(bitboard, square) ? bitboard ^= (1ULL << square) : 0)
// count bits within a bitboard (Brian Kernighan's way)
static inline int count_bits(U64 bitboard)
{
// bit counter
int count = 0;
// consecutively reset least significant 1st bit
while (bitboard)
{
// increment count
count++;
// reset least significant 1st bit
bitboard &= bitboard - 1;
}
// return bit count
return count;
}
// get least significant 1st bit index
static inline int get_ls1b_index(U64 bitboard)
{
// make sure bitboard is not 0
if (bitboard)
{
// count trailing bits before LS1B
return count_bits((bitboard & -bitboard) - 1);
}
//otherwise
else
// return illegal index
return -1;
}
/**********************************\
==================================
Input & Output
==================================
\**********************************/
// print bitboard
void print_bitboard(U64 bitboard)
{
printf("\n");
// loop over board ranks
for (int rank = 0; rank < 8; rank++)
{
// loop over board files
for (int file = 0; file < 8; file++)
{
// convert file & rank into square index
int square = rank * 8 + file;
// print ranks
if (!file)
printf(" %d ", 8 - rank);
// print bit state (either 1 or 0)
printf(" %d", get_bit(bitboard, square) ? 1 : 0);
}
// print new line every rank
printf("\n");
}
// print board files
printf("\n a b c d e f g h\n\n");
// print bitboard as unsigned decimal number
printf(" Bitboard: %llud\n\n", bitboard);
}
/**********************************\
==================================
Attacks
==================================
\**********************************/
/*
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
const U64 not_a_file = 18374403900871474942ULL;
// not H file constant
const U64 not_h_file = 9187201950435737471ULL;
// not HG file constant
const U64 not_hg_file = 4557430888798830399ULL;
// not AB file constant
const U64 not_ab_file = 18229723555195321596ULL;
// bishop relevant occupancy bit count for every square on board
const int bishop_relevant_bits[64] = {
6, 5, 5, 5, 5, 5, 5, 6,
5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 7, 7, 7, 7, 5, 5,
5, 5, 7, 9, 9, 7, 5, 5,
5, 5, 7, 9, 9, 7, 5, 5,
5, 5, 7, 7, 7, 7, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5,
6, 5, 5, 5, 5, 5, 5, 6
};
// rook relevant occupancy bit count for every square on board
const int rook_relevant_bits[64] = {
12, 11, 11, 11, 11, 11, 11, 12,
11, 10, 10, 10, 10, 10, 10, 11,
11, 10, 10, 10, 10, 10, 10, 11,
11, 10, 10, 10, 10, 10, 10, 11,
11, 10, 10, 10, 10, 10, 10, 11,
11, 10, 10, 10, 10, 10, 10, 11,
11, 10, 10, 10, 10, 10, 10, 11,
12, 11, 11, 11, 11, 11, 11, 12
};
// rook magic numbers
U64 rook_magic_numbers[64] = {
0x8a80104000800020ULL,
0x140002000100040ULL,
0x2801880a0017001ULL,
0x100081001000420ULL,
0x200020010080420ULL,
0x3001c0002010008ULL,
0x8480008002000100ULL,
0x2080088004402900ULL,
0x800098204000ULL,
0x2024401000200040ULL,
0x100802000801000ULL,
0x120800800801000ULL,
0x208808088000400ULL,
0x2802200800400ULL,
0x2200800100020080ULL,
0x801000060821100ULL,
0x80044006422000ULL,
0x100808020004000ULL,
0x12108a0010204200ULL,
0x140848010000802ULL,
0x481828014002800ULL,
0x8094004002004100ULL,
0x4010040010010802ULL,
0x20008806104ULL,
0x100400080208000ULL,
0x2040002120081000ULL,
0x21200680100081ULL,
0x20100080080080ULL,
0x2000a00200410ULL,
0x20080800400ULL,
0x80088400100102ULL,
0x80004600042881ULL,
0x4040008040800020ULL,
0x440003000200801ULL,
0x4200011004500ULL,
0x188020010100100ULL,
0x14800401802800ULL,
0x2080040080800200ULL,
0x124080204001001ULL,
0x200046502000484ULL,
0x480400080088020ULL,
0x1000422010034000ULL,
0x30200100110040ULL,
0x100021010009ULL,
0x2002080100110004ULL,
0x202008004008002ULL,
0x20020004010100ULL,
0x2048440040820001ULL,
0x101002200408200ULL,
0x40802000401080ULL,
0x4008142004410100ULL,
0x2060820c0120200ULL,
0x1001004080100ULL,
0x20c020080040080ULL,
0x2935610830022400ULL,
0x44440041009200ULL,
0x280001040802101ULL,
0x2100190040002085ULL,
0x80c0084100102001ULL,
0x4024081001000421ULL,
0x20030a0244872ULL,
0x12001008414402ULL,
0x2006104900a0804ULL,
0x1004081002402ULL
};
// bishop magic numbers
U64 bishop_magic_numbers[64] = {
0x40040844404084ULL,
0x2004208a004208ULL,
0x10190041080202ULL,
0x108060845042010ULL,
0x581104180800210ULL,
0x2112080446200010ULL,
0x1080820820060210ULL,
0x3c0808410220200ULL,
0x4050404440404ULL,
0x21001420088ULL,
0x24d0080801082102ULL,
0x1020a0a020400ULL,
0x40308200402ULL,
0x4011002100800ULL,
0x401484104104005ULL,
0x801010402020200ULL,
0x400210c3880100ULL,
0x404022024108200ULL,
0x810018200204102ULL,
0x4002801a02003ULL,
0x85040820080400ULL,
0x810102c808880400ULL,
0xe900410884800ULL,
0x8002020480840102ULL,
0x220200865090201ULL,
0x2010100a02021202ULL,
0x152048408022401ULL,
0x20080002081110ULL,
0x4001001021004000ULL,
0x800040400a011002ULL,
0xe4004081011002ULL,
0x1c004001012080ULL,
0x8004200962a00220ULL,
0x8422100208500202ULL,
0x2000402200300c08ULL,
0x8646020080080080ULL,
0x80020a0200100808ULL,
0x2010004880111000ULL,
0x623000a080011400ULL,
0x42008c0340209202ULL,
0x209188240001000ULL,
0x400408a884001800ULL,
0x110400a6080400ULL,
0x1840060a44020800ULL,
0x90080104000041ULL,
0x201011000808101ULL,
0x1a2208080504f080ULL,
0x8012020600211212ULL,
0x500861011240000ULL,
0x180806108200800ULL,
0x4000020e01040044ULL,
0x300000261044000aULL,
0x802241102020002ULL,
0x20906061210001ULL,
0x5a84841004010310ULL,
0x4010801011c04ULL,
0xa010109502200ULL,
0x4a02012000ULL,
0x500201010098b028ULL,
0x8040002811040900ULL,
0x28000010020204ULL,
0x6000020202d0240ULL,
0x8918844842082200ULL,
0x4010011029020020ULL
};
// pawn attacks table [side][square]
U64 pawn_attacks[2][64];
// knight attacks table [square]
U64 knight_attacks[64];
// king attacks table [square]
U64 king_attacks[64];
// generate pawn attacks
U64 mask_pawn_attacks(int side, int square)
{
// result attacks bitboard
U64 attacks = 0ULL;
// piece bitboard
U64 bitboard = 0ULL;
// set piece on board
set_bit(bitboard, square);
// white pawns
if (!side)
{
// generate pawn attacks
if ((bitboard >> 7) & not_a_file) attacks |= (bitboard >> 7);
if ((bitboard >> 9) & not_h_file) attacks |= (bitboard >> 9);
}
// black pawns
else
{
// generate pawn attacks
if ((bitboard << 7) & not_h_file) attacks |= (bitboard << 7);
if ((bitboard << 9) & not_a_file) attacks |= (bitboard << 9);
}
// return attack map
return attacks;
}
// generate knight attacks
U64 mask_knight_attacks(int square)
{
// result attacks bitboard
U64 attacks = 0ULL;
// piece bitboard
U64 bitboard = 0ULL;
// set piece on board
set_bit(bitboard, square);
// generate knight attacks
if ((bitboard >> 17) & not_h_file) attacks |= (bitboard >> 17);
if ((bitboard >> 15) & not_a_file) attacks |= (bitboard >> 15);
if ((bitboard >> 10) & not_hg_file) attacks |= (bitboard >> 10);
if ((bitboard >> 6) & not_ab_file) attacks |= (bitboard >> 6);
if ((bitboard << 17) & not_a_file) attacks |= (bitboard << 17);
if ((bitboard << 15) & not_h_file) attacks |= (bitboard << 15);
if ((bitboard << 10) & not_ab_file) attacks |= (bitboard << 10);
if ((bitboard << 6) & not_hg_file) attacks |= (bitboard << 6);
// return attack map
return attacks;
}
// generate king attacks
U64 mask_king_attacks(int square)
{
// result attacks bitboard
U64 attacks = 0ULL;
// piece bitboard
U64 bitboard = 0ULL;
// set piece on board
set_bit(bitboard, square);
// generate king attacks
if (bitboard >> 8) attacks |= (bitboard >> 8);
if ((bitboard >> 9) & not_h_file) attacks |= (bitboard >> 9);
if ((bitboard >> 7) & not_a_file) attacks |= (bitboard >> 7);
if ((bitboard >> 1) & not_h_file) attacks |= (bitboard >> 1);
if (bitboard << 8) attacks |= (bitboard << 8);
if ((bitboard << 9) & not_a_file) attacks |= (bitboard << 9);
if ((bitboard << 7) & not_h_file) attacks |= (bitboard << 7);
if ((bitboard << 1) & not_a_file) attacks |= (bitboard << 1);
// return attack map
return attacks;
}
// mask bishop attacks
U64 mask_bishop_attacks(int square)
{
// result attacks bitboard
U64 attacks = 0ULL;
// init ranks & files
int r, f;
// init target rank & files
int tr = square / 8;
int tf = square % 8;
// mask relevant bishop occupancy bits
for (r = tr + 1, f = tf + 1; r <= 6 && f <= 6; r++, f++) attacks |= (1ULL << (r * 8 + f));
for (r = tr - 1, f = tf + 1; r >= 1 && f <= 6; r--, f++) attacks |= (1ULL << (r * 8 + f));
for (r = tr + 1, f = tf - 1; r <= 6 && f >= 1; r++, f--) attacks |= (1ULL << (r * 8 + f));
for (r = tr - 1, f = tf - 1; r >= 1 && f >= 1; r--, f--) attacks |= (1ULL << (r * 8 + f));
// return attack map
return attacks;
}
// mask rook attacks
U64 mask_rook_attacks(int square)
{
// result attacks bitboard
U64 attacks = 0ULL;
// init ranks & files
int r, f;
// init target rank & files
int tr = square / 8;
int tf = square % 8;
// mask relevant rook occupancy bits
for (r = tr + 1; r <= 6; r++) attacks |= (1ULL << (r * 8 + tf));
for (r = tr - 1; r >= 1; r--) attacks |= (1ULL << (r * 8 + tf));
for (f = tf + 1; f <= 6; f++) attacks |= (1ULL << (tr * 8 + f));
for (f = tf - 1; f >= 1; f--) attacks |= (1ULL << (tr * 8 + f));
// return attack map
return attacks;
}
// generate bishop attacks on the fly
U64 bishop_attacks_on_the_fly(int square, U64 block)
{
// result attacks bitboard
U64 attacks = 0ULL;
// init ranks & files
int r, f;
// init target rank & files
int tr = square / 8;
int tf = square % 8;
// generate bishop atacks
for (r = tr + 1, f = tf + 1; r <= 7 && f <= 7; r++, f++)
{
attacks |= (1ULL << (r * 8 + f));
if ((1ULL << (r * 8 + f)) & block) break;
}
for (r = tr - 1, f = tf + 1; r >= 0 && f <= 7; r--, f++)
{
attacks |= (1ULL << (r * 8 + f));
if ((1ULL << (r * 8 + f)) & block) break;
}
for (r = tr + 1, f = tf - 1; r <= 7 && f >= 0; r++, f--)
{
attacks |= (1ULL << (r * 8 + f));
if ((1ULL << (r * 8 + f)) & block) break;
}
for (r = tr - 1, f = tf - 1; r >= 0 && f >= 0; r--, f--)
{
attacks |= (1ULL << (r * 8 + f));
if ((1ULL << (r * 8 + f)) & block) break;
}
// return attack map
return attacks;
}
// generate rook attacks on the fly
U64 rook_attacks_on_the_fly(int square, U64 block)
{
// result attacks bitboard
U64 attacks = 0ULL;
// init ranks & files
int r, f;
// init target rank & files
int tr = square / 8;
int tf = square % 8;
// generate rook attacks
for (r = tr + 1; r <= 7; r++)
{
attacks |= (1ULL << (r * 8 + tf));
if ((1ULL << (r * 8 + tf)) & block) break;
}
for (r = tr - 1; r >= 0; r--)
{
attacks |= (1ULL << (r * 8 + tf));
if ((1ULL << (r * 8 + tf)) & block) break;
}
for (f = tf + 1; f <= 7; f++)
{
attacks |= (1ULL << (tr * 8 + f));
if ((1ULL << (tr * 8 + f)) & block) break;
}
for (f = tf - 1; f >= 0; f--)
{
attacks |= (1ULL << (tr * 8 + f));
if ((1ULL << (tr * 8 + f)) & block) break;
}
// return attack map
return attacks;
}
// init leaper pieces attacks
void init_leapers_attacks()
{
// loop over 64 board squares
for (int square = 0; square < 64; square++)
{
// 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);
}
}
// set occupancies
U64 set_occupancy(int index, int bits_in_mask, U64 attack_mask)
{
// occupancy map
U64 occupancy = 0ULL;
// loop over the range of bits within attack mask
for (int count = 0; count < bits_in_mask; count++)
{
// get LS1B index of attacks mask
int square = get_ls1b_index(attack_mask);
// pop LS1B in attack map
pop_bit(attack_mask, square);
// make sure occupancy is on board
if (index & (1 << count))
// populate occupancy map
occupancy |= (1ULL << square);
}
// return occupancy map
return occupancy;
}
/**********************************\
==================================
Magics
==================================
\**********************************/
// find appropriate magic number
U64 find_magic_number(int square, int relevant_bits, int bishop)
{
// init occupancies
U64 occupancies[4096];
// init attack tables
U64 attacks[4096];
// init used attacks
U64 used_attacks[4096];
// init attack mask for a current piece
U64 attack_mask = bishop ? mask_bishop_attacks(square) : mask_rook_attacks(square);
// init occupancy indicies
int occupancy_indicies = 1 << relevant_bits;
// loop over occupancy indicies
for (int index = 0; index < occupancy_indicies; index++)
{
// init occupancies
occupancies[index] = set_occupancy(index, relevant_bits, attack_mask);
// init attacks
attacks[index] = bishop ? bishop_attacks_on_the_fly(square, occupancies[index]) :
rook_attacks_on_the_fly(square, occupancies[index]);
}
// test magic numbers loop
for (int random_count = 0; random_count < 100000000; random_count++)
{
// generate magic number candidate
U64 magic_number = generate_magic_number();
// skip inappropriate magic numbers
if (count_bits((attack_mask * magic_number) & 0xFF00000000000000) < 6) continue;
// init used attacks
memset(used_attacks, 0ULL, sizeof(used_attacks));
// init index & fail flag
int index, fail;
// test magic index loop
for (index = 0, fail = 0; !fail && index < occupancy_indicies; index++)
{
// init magic index
int magic_index = (int)((occupancies[index] * magic_number) >> (64 - relevant_bits));
//printf("occupancies[%d] = %llud\n\n",index,occupancies[index]);
//printf("magic_index = %d\n\n", magic_index);
//printf("magic_number = %llud\n\n", magic_number);
//getchar();
// if magic index works
if (used_attacks[magic_index] == 0ULL)
// init used attacks
used_attacks[magic_index] = attacks[index];
// otherwise
else if (used_attacks[magic_index] != attacks[index])
// magic index doesn't work
fail = 1;
}
// if magic number works
if (!fail)
// return it
return magic_number;
}
// if magic number doesn't work
printf(" Magic number fails!\n");
return 0ULL;
}
// init magic numbers
void init_magic_numbers()
{
// loop over 64 board squares
for (int square = 0; square < 64; square++)
// init rook magic numbers
rook_magic_numbers[square] = find_magic_number(square, rook_relevant_bits[square], rook);
// loop over 64 board squares
for (int square = 0; square < 64; square++)
// init bishop magic numbers
bishop_magic_numbers[square] = find_magic_number(square, bishop_relevant_bits[square], bishop);
}
/**********************************\
==================================
Init all
==================================
\**********************************/
// init all variables
void init_all()
{
// init leaper pieces attacks
init_leapers_attacks();
// init magic numbers
init_magic_numbers();
}
/**********************************\
==================================
Main driver
==================================
\**********************************/
int main()
{
// init all
init_all();
return 0;
}
Делфи
program bbc;
{$APPTYPE CONSOLE}
uses
SysUtils,Windows,TypInfo;
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
);
// sides to move (colors)
TSide = (white, black);
// bishop and rook
Tbishop = (rook, bishop);
//Первый индекс обозначает номер строки в матрице, второй индекс – номер столбца
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;
// pseudo random number state
//cardinal - беззнаковое целое
stateU32:cardinal = 1804289383;
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_to_coordinates: array [0..63] of string = (
'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'
);
// bishop relevant occupancy bit count for every square on board
bishop_relevant_bits: array [0..63] of integer =(
6, 5, 5, 5, 5, 5, 5, 6,
5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 7, 7, 7, 7, 5, 5,
5, 5, 7, 9, 9, 7, 5, 5,
5, 5, 7, 9, 9, 7, 5, 5,
5, 5, 7, 7, 7, 7, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5,
6, 5, 5, 5, 5, 5, 5, 6
);
// rook relevant occupancy bit count for every square on board
rook_relevant_bits: array [0..63] of integer =(
12, 11, 11, 11, 11, 11, 11, 12,
11, 10, 10, 10, 10, 10, 10, 11,
11, 10, 10, 10, 10, 10, 10, 11,
11, 10, 10, 10, 10, 10, 10, 11,
11, 10, 10, 10, 10, 10, 10, 11,
11, 10, 10, 10, 10, 10, 10, 11,
11, 10, 10, 10, 10, 10, 10, 11,
12, 11, 11, 11, 11, 11, 11, 12
);
{/**********************************\
==================================
Random numbers
==================================
\**********************************/}
// generate 32-bit pseudo legal numbers
function get_random_U32_number():cardinal;
begin
// XOR shift algorithm
stateU32:=stateU32 xor (stateU32 shl 13);
stateU32:=stateU32 xor (stateU32 shr 17);
stateU32:=stateU32 xor (stateU32 shl 5);
get_random_U32_number:=stateU32;
end;
// generate 64-bit pseudo legal numbers
function get_random_U64_number():U64;
var
// define 4 random numbers
n1,n2,n3,n4:U64;
begin
n1:=0;n2:=0;n3:=0; n4:=0;
// init random numbers slicing 16 bits from MS1B side
n1:=(n1 or (get_random_U32_number())) and $FFFF;
n2:=(n2 or (get_random_U32_number())) and $FFFF;
n3:=(n3 or (get_random_U32_number())) and $FFFF;
n4:=(n4 or (get_random_U32_number())) and $FFFF;
// return random number
get_random_U64_number:=n1 or (n2 shl 16) or (n3 shl 32) or (n4 shl 48);
end;
// generate magic number candidate
function generate_magic_number():U64;
begin
result:=get_random_U64_number() and get_random_U64_number() and get_random_U64_number();
end;
{/**********************************\
==================================
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;
// 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;
// get least significant 1st bit index
function get_ls1b_index(bb:U64):integer;
begin
// make sure bitboard is not 0
if bb<>0 then
// count trailing bits before LS1B
result:=count_bits((bb and (-bb))-1)
// return illegal index
else result:=-1;
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;
// set occupancies
//перебираем по очереди биты в attack_mask
//испр. ошибка - было -var attack_mask:U64, стало-attack_mask:U64
function set_occupancy(index,bits_in_mask:integer;attack_mask:U64):U64;
var
occupancy,n:U64;
count:integer;
square_:TBoard_squares;
begin
n:=1;
// occupancy map
occupancy:=0;
// loop over the range of bits within attack mask
for count:=0 to bits_in_mask-1 do begin
// get LS1B index of attacks mask
square_:=TBoard_squares(get_ls1b_index(attack_mask));
// pop LS1B in attack map
pop_bit(attack_mask,square_);
// make sure occupancy is on board
if (index and (n shl count))>0 then
occupancy:=occupancy or (n shl integer(square_));
end;
set_occupancy:=occupancy;
end;
{/**********************************\
==================================
Magics
function rook_attacks_on_the_fly(square:TBoard_squares;blk:U64):U64;
==================================
\**********************************/}
// find appropriate magic number
function find_magic_number(square:TBoard_squares;relevant_bits:integer;bishop_flag:Tbishop):U64;
//function find_magic_number():U64;
var
// init occupancies
occupancies:array[0..4095] of U64;
// init attack tables
attacks:array[0..4095] of U64;
// init used attacks
used_attacks:array[0..4095] of U64;
n:Byte;
// init attack mask for a current piece
attack_mask:U64;
// init occupancy indicies
occupancy_indicies:integer;
magic_index:integer;
index,fail,random_count:integer;
magic_number:U64;
//memset
//https://metanit.com/c/tutorial/8.3.php?ysclid=ldc20xz850854644891
begin
attack_mask:=0;
// init attack mask for a current piece
if bishop_flag=bishop then attack_mask:=mask_bishop_attacks(square)
else attack_mask:=mask_rook_attacks(square);
// init occupancy indicies напр. ладья на a1 - rook_relevant_bits: array [ ] = 12
// 1 shl 12 = 4096
occupancy_indicies:=1 shl relevant_bits;
// loop over occupancy indicies
for index:=0 to occupancy_indicies-1 do begin
// init occupancies
occupancies[index] := set_occupancy(index,relevant_bits,attack_mask);
// init attacks
if bishop_flag=bishop then attacks[index]:= bishop_attacks_on_the_fly(square, occupancies[index])
else attacks[index]:= rook_attacks_on_the_fly(square, occupancies[index]);
end;
// test magic numbers loop
n:=0;
for random_count:= 0 to 100000000 do begin
// generate magic number candidate
magic_number := generate_magic_number();
// skip inappropriate magic numbers
if (count_bits((attack_mask * magic_number) and $FF00000000000000) < 6) then continue;
//http://www.delphibasics.ru/FillChar.php
// procedure FillChar ( var Buffer; FillCount : Integer; FillValue : Byte ) ;
{Процедура FillChar заполняет раздел памяти Buffer
тем же самым байтом или символом FillValue FillCount раз.
Это используется, преимущественно, для инициализирования массивов чисел.}
// Теперь заполняем массив used_attacks значением 0
// UInt64 - 8 байт
FillChar(used_attacks, 4096*SizeOf(UInt64), n);
fail := 0;
for index:=0 to occupancy_indicies-1 do begin
// init magic index
magic_index := integer((occupancies[index] * magic_number) shr (64 - relevant_bits));
{Writeln('occupancies[',index,'] = ',occupancies[index]);
Writeln('magic_index = ',magic_index);
Writeln('magic_number = ',magic_number);
Readln;}
// if magic index works
if (used_attacks[magic_index] = 0) then
// init used attacks
used_attacks[magic_index] := attacks[index]
// otherwise
else if (used_attacks[magic_index] <> attacks[index]) then begin
// magic index doesn't work
fail := 1;break;
end;
end;
// if magic number works
if (fail=0) then begin
// return it
result:=magic_number;
exit;
end;
end;
// if magic number doesn't work
Writeln(' Magic number fails! ');
result:=0;
end;
// init magic numbers
procedure init_magic_numbers();
var
tem64:U64;
temp32:integer;
begin
// loop over 64 board squares
for square := a8 to h1 do begin
tem64:=find_magic_number(square,rook_relevant_bits[integer(square)],rook);
Write('0x');Write(Format('%x',[tem64]));Write('ULL');
Writeln('');
//Write(tem64);
//Readln;
end;
Writeln('====================');
for square := a8 to h1 do begin
tem64:=find_magic_number(square,bishop_relevant_bits[integer(square)],bishop);
Write('0x');Write(Format('%x',[tem64]));Write('ULL');
Writeln('');
//Write(tem64);
//Readln;
end;
end;
{/**********************************\
==================================
Main driver
==================================
\**********************************/}
begin
//Переключение окна консоли на кодовую страницу CP1251 (Win-1251).
//Если после переключения русские буквы показываются неверно,
//следует открыть системное меню консольного окна - щелчком мыши в левом
//верхнем углу окна консоли. И выбрать:
//Свойства - закладка "Шрифт" - выбрать шрифт: "Lucida Console".
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
// ==================================
init_leapers_attacks();
init_magic_numbers();
Writeln('Нажмите <ENTER>, чтобы выйти ...');
Readln;
end.
{print_bitboard(get_random_U32_number());
print_bitboard(get_random_U32_number());
print_bitboard(get_random_U64_number());
print_bitboard(generate_magic_number());}
{Writeln('bishop_relevant_bits');
for square := a8 to h1 do begin
if (integer(square) mod 8)=0 then Writeln('');
Write(count_bits(mask_bishop_attacks(square))); Write(' ');
end;
Writeln('');
Writeln('rook_relevant_bits');
for square := a8 to h1 do begin
if (integer(square) mod 8)=0 then Writeln('');
Write(count_bits(mask_rook_attacks(square))); Write(' ');
end;
Writeln('');}
{ block:=4512464976740352;
print_bitboard(block);
square:=TBoard_squares(get_ls1b_index(block));
Write('get_ls1b_index:',integer(square));
Writeln(' coordinate:',square_to_coordinates[integer(square)]);
set_bit(bitboard,square);
print_bitboard(bitboard);}
//ZobristKey[i][j][z]=rd.nextLong()^(rd.nextLong()<<15)^(rd.nextLong()<<30)^(rd.nextLong()<<45)^(rd.nextLong()<<60);
//<< shl
Магические числа, полученные с помощью кода адаптированного на Делфи
Bitboard в программировании шахмат №2
27 Янв 2023 23:00 #128
Посмотрел 16 урок - Bitboard CHESS ENGINE in C: initializing SLIDER PIECES attack tables using PLAIN MAGIC BITBOARDS
К сожалению Макс перестал объснять, а просто пишет код.
Я тоже одновременно с ним пишу.
И да, в этом есть какая то магия, точно есть)))
// init slider piece's attack tables
procedure init_sliders_attacks(bishop_flag:Tbishop);
var
// init current mask
attack_mask:U64;
// init current occupancy variation
occupancy:U64;
// init relevant occupancy bit count
relevant_bits_count:integer;
// init occupancy indicies
occupancy_indicies:integer;
magic_index:integer;
index:integer;
begin
// loop over 64 board squares
for square := a8 to h1 do begin
// init bishop & rook masks
bishop_masks[square] := mask_bishop_attacks(square);
rook_masks[square] := mask_rook_attacks(square);
// init current mask
if bishop_flag=bishop then attack_mask:=bishop_masks[square]
else attack_mask:=rook_masks[square];
// init relevant occupancy bit count
relevant_bits_count := count_bits(attack_mask);
// init occupancy indicies
occupancy_indicies := 1 shl relevant_bits_count;
// loop over occupancy indicies
for index:=0 to occupancy_indicies-1 do begin
// bishop
if bishop_flag=bishop then begin
// init current occupancy variation
occupancy := set_occupancy(index, relevant_bits_count, attack_mask);
// init magic index
magic_index := integer((occupancy * bishop_magic_numbers[square]) shr (64 - bishop_relevant_bits[square]));
// init bishop attacks
bishop_attacks[square][magic_index] := bishop_attacks_on_the_fly(square, occupancy);
end
// rook
else begin
// init current occupancy variation
occupancy := set_occupancy(index, relevant_bits_count, attack_mask);
// init magic index
magic_index := integer((occupancy * rook_magic_numbers[square]) shr (64 - rook_relevant_bits[square]));
// init bishop attacks
rook_attacks[square][magic_index] := rook_attacks_on_the_fly(square, occupancy);
end;
end;
end;
end;
// get bishop attacks
function get_bishop_attacks(square:TBoard_squares;occupancy:U64):U64;
begin
occupancy:=occupancy and bishop_masks[square];
occupancy:=occupancy * bishop_magic_numbers[square];
occupancy:=occupancy shr (64 - bishop_relevant_bits[square]);
// return bishop attacks
result:=bishop_attacks[square][occupancy];
end;
// get rook attacks
function get_rook_attacks(square:TBoard_squares;occupancy:U64):U64;
begin
occupancy:=occupancy and rook_masks[square];
occupancy:=occupancy * rook_magic_numbers[square];
occupancy:=occupancy shr (64 - rook_relevant_bits[square]);
// return bishop attacks
result:=rook_attacks[square][occupancy];
end;
{/**********************************\
==================================
Init all
==================================
\**********************************/}
// init all variables
procedure init_all();
begin
// init leaper pieces attacks
init_leapers_attacks();
// init slider pieces attacks
init_sliders_attacks(bishop);
init_sliders_attacks(rook);
// init magic numbers
//init_magic_numbers();
end;
{/**********************************\
==================================
Main driver
==================================
\**********************************/}
begin
//Переключение окна консоли на кодовую страницу CP1251 (Win-1251).
//Если после переключения русские буквы показываются неверно,
//следует открыть системное меню консольного окна - щелчком мыши в левом
//верхнем углу окна консоли. И выбрать:
//Свойства - закладка "Шрифт" - выбрать шрифт: "Lucida Console".
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
// ==================================
// init all
init_all();
// set blocker pieces on board
set_bit(block, c5);
set_bit(block, f2);
set_bit(block, g7);
set_bit(block, b2);
set_bit(block, g5);
set_bit(block, e2);
set_bit(block, e7);
print_bitboard(block);
// print rook attacks
print_bitboard(get_rook_attacks(e5, block));
// print bishop attacks
print_bitboard(get_bishop_attacks(d4, block));
Writeln('Нажмите <ENTER>, чтобы выйти ...');
Readln;
end.
Надо бы докапаться до сути и понять как это работает.
Bitboard в программировании шахмат №2
28 Янв 2023 14:59 #129
Протестировал магические квадраты на задаче неприкосновенный король.
Конечно это достаточно условный тест с некоторыми допущениями.
Время складывается из работы основной тестируемой функции и условно постоянной величины, складывающейся из функции прорисовки, оценки позиции и т.д.
Но примем допущения, что эта величина одинакова для всех.
Еще в магических квадратах пришлось просчитывать дополнительно ходы черного короля с учетом шахов.
В общем результат при depth=8
Если есть числа, которые работают, то зачем искать другие другие числа.
Bitboard в программировании шахмат №2
31 Янв 2023 13:54 #130
Уроки
17.Bitboard CHESS ENGINE in C: defining BITBOARDS, OCCUPANCIES and helper variables
18.Bitboard CHESS ENGINE in C: printing CHESS BOARD position and game state variables
19.Bitboard CHESS ENGINE in C: parsing FEN string to initialize BITBOARDS, OCUUPANCIES & board state
20.Bitboard CHESS ENGINE in C: getting QUEEN ATTACKS by looking up bishop & rook attack tables
Пока, что каких-то особых секретов в этих уроках нет.
Но необходимо двигаться в ногу с Максом, иначе дальше двигаться будет невозможно.
Итак вкратце:
Атаки ферзя - объединяем атаки слона и ладьи
// get queen attacks
function get_queen_attacks(square:TBoard_squares;occupancy:U64):U64;
begin
result:=get_bishop_attacks(square,occupancy) or get_rook_attacks(square,occupancy);
end;
Позиция и вспомогательные переменные
uses
SysUtils,Windows,TypInfo;
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
);
// sides to move (colors)
TSide = (white, black, both);
// bishop and rook
Tbishop = (rook, bishop);
//Pawn
TPawn_attacks=array[TSide,TBoard_squares] of U64;
//прыгающие фигуры
TChip_attacks=array[TBoard_squares] of U64;
// encode pieces
Tencode_pieces=( P_, N_, B_, R_, Q_, K_, p, n, b, r, q, k);
{// castling rights binary encoding
рокеровка
/*
bin dec
0001 1 white king can castle to the king side
0010 2 white king can castle to the queen side
0100 4 black king can castle to the king side
1000 8 black king can castle to the queen side
examples
1111 both sides an castle both directions
1001 black king => queen side
white king => king side
*/}
Tcastling = (wk = 1, wq = 2, bk = 4, bq = 8 );
var
{/**********************************\
==================================
Chess board
==================================
\**********************************/
/*
WHITE PIECES
Pawns Knights Bishops
8 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0
7 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0
2 1 1 1 1 1 1 1 1 2 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 1 0 0 1 0 0
a b c d e f g h a b c d e f g h a b c d e f g h
Rooks Queens King
8 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0
7 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0
a b c d e f g h a b c d e f g h a b c d e f g h
BLACK PIECES
Pawns Knights Bishops
8 0 0 0 0 0 0 0 0 8 0 1 0 0 0 0 1 0 8 0 0 1 0 0 1 0 0
7 1 1 1 1 1 1 1 1 7 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
a b c d e f g h a b c d e f g h a b c d e f g h
Rooks Queens King
8 1 0 0 0 0 0 0 1 8 0 0 0 1 0 0 0 0 8 0 0 0 0 1 0 0 0
7 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
a b c d e f g h a b c d e f g h a b c d e f g h
}
// piece bitboards
bitboards_12:array[Tencode_pieces] of U64;
{
OCCUPANCIES
White occupancy Black occupancy All occupancies
8 0 0 0 0 0 0 0 0 8 1 1 1 1 1 1 1 1 8 1 1 1 1 1 1 1 1
7 0 0 0 0 0 0 0 0 7 1 1 1 1 1 1 1 1 7 1 1 1 1 1 1 1 1
6 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0
2 1 1 1 1 1 1 1 1 2 0 0 0 0 0 0 0 0 2 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1
}
// occupancy bitboards
occupancies_3:array[TSide] of U64;
// side to move
side:TSide = both;
// enpassant square
enpassantInt:integer=-1;
enpassant:TBoard_squares=a8;
// castling rights
castle:integer=0;
// ASCII pieces
ascii_pieces:array[0..11] of char = 'PNBRQKpnbrqk';
//===========================================
// piece bitboards
bitboards_12:array[Tencode_pieces] of U64; - битборды по типу и цвету для фигур
// occupancy bitboards
occupancies_3:array[TSide] of U64; - битбоарды белых, черных и всех фигур
// side to move
side:TSide = both; - белые, черные или все
// castling rights
castle:integer=0; - флаг рокеровки
bin dec
0001 1 white king can castle to the king side
0010 2 white king can castle to the queen side
0100 4 black king can castle to the king side
1000 8 black king can castle to the queen side
// enpassant square - флаг и поле (взятие на проходе)
enpassantInt:integer=-1;
enpassant:TBoard_squares=a8;//заведомо ложное поле
отладочная информация и визуализация (вывод досок в консоль, парсинг fen строки
// ASCII pieces
ascii_pieces:array[0..11] of char = 'PNBRQKpnbrqk';
{/**********************************\
==================================
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;
// print board
procedure print_board();
var
rank_,file_,sq:integer;
bb_piece:Tencode_pieces;
flag:boolean;
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(' ');
flag:=true;
// loop over all piece bitboards
for bb_piece := P_ to k do begin
if get_bit(bitboards_12[bb_piece],sq)>0 then begin
Write(ascii_pieces[integer(bb_piece)]);
flag:=false;
end;
end;
if flag then Write('.');
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('');
Write('side = ');
//Write(GetEnumName(TypeInfo(TSide), ord(TSide(integer(side)))));
//TSide = (white, black, both);
if side=white then Write('white');
if side=black then Write('black');
Writeln('');
Write('castle = ');
if (castle and integer(Tcastling(wk)))>0 then Write('K') else Write('-');
if (castle and integer(Tcastling(wq)))>0 then Write('Q') else Write('-');
if (castle and integer(Tcastling(bk)))>0 then Write('k') else Write('-');
if (castle and integer(Tcastling(bq)))>0 then Write('q') else Write('-');
Writeln('');
Write('enpassant = ');
if enpassantInt=-1 then Write('no') else begin
//enpassant:=TBoard_squares(enpassantInt);
Write(GetEnumName(TypeInfo(TBoard_squares), ord(enpassantInt)));
end;
Writeln('');
end;
// parse FEN string
function parse_fen(sfen:String):boolean;
var
// i,j - индекс массива
// len_fen - длина строки fen
// n64 - счетчик шахматных клеток (64 клетки)
// num - позиция символа в strN или strF
i,j,len_fen,n64,num:integer;
//строки для цифр из fen строки - strN, фигур - strF, единичного символа - s01
strN,strF,s01,strA:string;
bt:Byte;
bb_piece:Tencode_pieces;
begin
//если fen строка пустая, то ошибка fen строки
result:=false;
if sfen='' then exit;
// reset board position (bitboards)
bt:=0;
FillChar(bitboards_12, 12*SizeOf(UInt64), bt);
// reset occupancies (bitboards)
FillChar(occupancies_3, 3*SizeOf(UInt64), bt);
// reset game state variables
// side to move
side := black;
// enpassant square
enpassantInt:=-1;
enpassant:=a8;//заведомо ложное поле
// castling rights
castle:=0;
// инициализация строк для парсинга fen строки
strN:='12345678';
strF:='PNBRQKpnbrqk';
strA:='abcdefgh';
//определяем длину fen строки
len_fen:=length(sfen);
//сбрасываем счетчик
n64:=-1;
//перебираем символы fen строки
for i := 1 to len_fen 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 begin
num:=pos(' ',sfen);
sfen:=copy(sfen,num+1,len_fen-num);
for j := 1 to length(sfen) do begin
s01:=copy(sfen,j,1);
if s01=' ' then continue;
// side to move
if s01='w' then begin side := white; continue;end;
case Ord(sfen[j]) of
Ord('K'):begin castle:=castle or integer(wk);end;
Ord('Q'):begin castle:=castle or integer(wq);end;
Ord('k'):begin castle:=castle or integer(bk);end;
Ord('q'):begin castle:=castle or integer(bq);end;
end;
if (((sfen[j] >= 'a') and (sfen[j] <= 'h')) and ((sfen[j+1] = '3') or (sfen[j+1] = '6'))) then begin
enpassantInt:=pos(copy(sfen,j,1),strA)-1+8*(8-(pos(copy(sfen,j+1,1),strN)));
enpassant:=TBoard_squares(enpassantInt);
end;
// Writeln(sfen[j]);
end;
break;
end;
//увеличиваем счетчик шахматных клеток n64
// если num=0, значит символ s01 фигура
if num=0 then begin
Inc(n64);
// иначе цифра
end else begin
n64:=n64+num;
end;
//если клеток больше 64(0..63), то ошибка fen строки
if n64>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
//Tencode_pieces=( P_, N_, B_, R_, Q_, K_, p, n, b, r, q, k);
set_bit(bitboards_12[Tencode_pieces(num-1)],TBoard_squares(n64));
end;
end;//for
//если клеток не равно 64(0..63), то ошибка fen строки
if n64<>63 then exit;
//если королей не равно 1, то ошибка fen строки
if count_bits(bitboards_12[K_])<>1 then exit;
if count_bits(bitboards_12[k])<>1 then exit;
// loop over white pieces bitboardsoop over all piece bitboards
for bb_piece := P_ to K_ do
// populate white occupancy bitboard
occupancies_3[white] := occupancies_3[white] or bitboards_12[bb_piece];
// loop over black pieces bitboardsoop over all piece bitboards
for bb_piece := p to k do
// populate black occupancy bitboard
occupancies_3[black] := occupancies_3[black] or bitboards_12[bb_piece];
// init all occupancies
occupancies_3[both] := occupancies_3[both] or occupancies_3[white] or occupancies_3[black];
//парсинг завершен успешно
//print_board();
result:=true;
end;
Парсинг я взял свой с некоторыми правками.
Делать как у Макса не обязательно, все же Си отличается от делфи.
Bitboard в программировании шахмат №2
01 Фев 2023 08:13 #131
Урок 21.Bitboard CHESS ENGINE in C: implementing routine to find out whether SQUARE IS ATTACKED
Процедура для определения того, подвергается ли поле доски атаке.
На СИ конечно это все короче, но как есть
// is square current given attacked by the current given side
function is_square_attacked(square:TBoard_squares;sd:TSide):integer;
begin
// attacked by white pawns
if ((sd = white) and ((pawn_attacks[black][square] and bitboards_12[P_])>0)) then
begin
result:=1;exit;
end;
// attacked by black pawns
if ((sd = black) and ((pawn_attacks[white][square] and bitboards_12[p])>0)) then
begin
result:=1;exit;
end;
// attacked by knights
if ((sd = white) and ((knight_attacks[square] and bitboards_12[N_])>0)) then
begin
result:=1;exit;
end;
if ((sd = black) and ((knight_attacks[square] and bitboards_12[n])>0)) then
begin
result:=1;exit;
end;
// attacked by bishops
if ((sd = white) and ((get_bishop_attacks(square, occupancies_3[both]) and bitboards_12[B_])>0)) then
begin
result:=1;exit;
end;
if ((sd = black) and ((get_bishop_attacks(square, occupancies_3[both]) and bitboards_12[b])>0)) then
begin
result:=1;exit;
end;
// attacked by rooks
if ((sd = white) and ((get_rook_attacks(square, occupancies_3[both]) and bitboards_12[R_])>0)) then
begin
result:=1;exit;
end;
if ((sd = black) and ((get_rook_attacks(square, occupancies_3[both]) and bitboards_12[r])>0)) then
begin
result:=1;exit;
end;
// attacked by queens
if ((sd = white) and ((get_queen_attacks(square, occupancies_3[both]) and bitboards_12[Q_])>0)) then
begin
result:=1;exit;
end;
if ((sd = black) and ((get_queen_attacks(square, occupancies_3[both]) and bitboards_12[q])>0)) then
begin
result:=1;exit;
end;
// attacked by kings
if ((sd = white) and ((king_attacks[square] and bitboards_12[K_])>0)) then
begin
result:=1;exit;
end;
if ((sd = black) and ((king_attacks[square] and bitboards_12[k])>0)) then
begin
result:=1;exit;
end;
result:=0;
end;
// print attacked squares
procedure print_attacked_squares(sd:TSide);
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(' ');
// check whether current square is attacked or not
Write(is_square_attacked(TBoard_squares(sq),sd));
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('');
end;
if parse_fen('r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1 ')=false then Writeln('Ошибка FEN строки ...');
print_board();
print_attacked_squares(white);
Writeln('Нажмите <ENTER>, чтобы выйти ...');
Readln;
Вроде функция работает правильно.
Алгоритм такой:
Все ходы в шахматах (за исключением ходов пешек и рокировках) обладают очень интересным свойством.
Если фигура атакует из клетки A в клетку B, то если ее переместить в клетку В она всегда будет атаковать клетку А.
А из этого следует, что поставив на клетку В, которую мы хотим проверить, например слона он будет бить вражеского слона на клетке А тогда и только тогда, когда слон А бьет клетку В.
Аналогичная логика работает со всеми фигурами
Bitboard в программировании шахмат №2
01 Фев 2023 12:57 #132
Хотел обобщить шаги для создания шахматного движка на основе битбоард.
Итак.
1. Атаки прыгающих фигур (король,конь,пешка)
2. Атаки скользящих фигур (слон,ладья,ферзь)
3. Представление данных о позиции в памяти компа.
4. Интерфейс (взаимодействие с человеком) для наглядного представления работы движка.
5. Функции
- подсчет битов в числе
- нахождение первого установленного бита в числе
- проверка установлен ли бит в любой позиции числа
- сброс любого бита в числе
- нахождение для каждого поля доски всех атак на это поле со стороны фигур, принадлежащих белым или черным
Далее Макс, ну и я))) преступим к реализации генератора ходов, т.е. будем учить движок ходить по шахматным правилам.
На самом деле, это очень даже интересно.
А пока видео от Макса, как он проводил тесты скорости.
Bitboard в программировании шахмат №2
04 Фев 2023 07:17 #133
22.Bitboard CHESS ENGINE in C: writing GENERATE MOVES function skeleton (скелет GENERATE MOVES)
23.Bitboard CHESS ENGINE in C: generating QUIET PAWN moves (тихие ходы пешек)
24.Bitboard CHESS ENGINE in C: generating PAWN CAPTURE moves (ходы взятие пешек)
25.Bitboard CHESS ENGINE in C: generating CASTLING MOVES (рокеровка)
26.Bitboard CHESS ENGINE in C: generating SLIDER & LEAPER piece MOVES by attack tables lookup
(генерация ходов скользящих и прыгающих фигур с помощью таблиц атак)
Итак генератор ходов, если быть точным, то псевдо ходов, так сказал Макс в одном из комментариев.
Потому что король может пойти под шах, и этот момент будет отслеживаться в функции - сделать ход
Warning: Spoiler![ Click to expand ][ Click to hide ]
// generate all moves
procedure generate_moves();
var
piece :Tencode_pieces;
// define current piece's bitboard copy & it's attacks
attacks,bitboard,occupancies,enpassant_attacks,n1:U64;
// define source & target squares
source_square, target_square:TBoard_squares;
source_squareInt, target_squareInt,target_enpassantInt :integer;
begin
n1:=1;
// loop over all the bitboards
for piece := P_ to k do begin
// init piece bitboard copy
bitboard := bitboards_12[piece];
// generate white pawns & white king castling moves
if (side = white) then begin
Warning: Spoiler![ Click to expand ][ Click to hide ]
//
piece = P_
// pick up white pawn bitboards index
if (piece = P_) then begin
// loop over white pawns within white pawn bitboard
while bitboard>0 do begin
// init source square
source_square := TBoard_squares(get_ls1b_index(bitboard));
source_squareInt:=integer(source_square);
// init target square
target_square :=TBoard_squares(source_squareInt - 8);
target_squareInt:=integer(target_square);
// generate quite pawn moves
if((not(target_square < a8)) and (get_bit(occupancies_3[both], target_squareInt)=0)) then begin
// pawn promotion
if (source_square >= a7) and (source_square <= h7) then begin
Writeln('pawn promotion: ', square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt],'q');
Writeln('pawn promotion: ', square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt],'r');
Writeln('pawn promotion: ', square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt],'b');
Writeln('pawn promotion: ', square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt],'n');
end else begin
// one square ahead pawn move
Writeln('pawn push: ', square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt]);
// two squares ahead pawn move
//if ((source_square >= a2 && source_square <= h2) && !get_bit(occupancies[both], target_square - 8))
if ((source_square >= a2) and (source_square <= h2) and (get_bit(occupancies_3[both], target_squareInt-8)=0) ) then
Writeln('double pawn push: ', square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt - 8]);
end;//if
end;//if
// init pawn attacks bitboard
attacks := pawn_attacks[side][source_square] and occupancies_3[black];
// generate pawn captures
while attacks>0 do begin
// init target square
target_square := TBoard_squares(get_ls1b_index(attacks));
target_squareInt:=integer(target_square);
// pawn promotion
if (source_square >= a7) and (source_square <= h7) then begin
Writeln('pawn promotion capture: ', square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt],'q');
Writeln('pawn promotion capture: ', square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt],'r');
Writeln('pawn promotion capture: ', square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt],'b');
Writeln('pawn promotion capture: ', square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt],'n');
end else begin
// one square ahead pawn move
Writeln('pawn capture: ', square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt]);
end;
// pop ls1b of the pawn attacks
pop_bit(attacks, target_square);
end;//while attacks>0
// generate enpassant captures
if enpassantInt<>-1 then begin
// lookup pawn attacks and bitwise AND with enpassant square (bit)
enpassant_attacks := pawn_attacks[side][source_square] and (n1 shl enpassantInt);
if enpassant_attacks>0 then begin
// init enpassant capture target square
target_enpassantInt := get_ls1b_index(enpassant_attacks);
Writeln('pawn enpassant capture: ', square_to_coordinates[source_squareInt], square_to_coordinates[target_enpassantInt]);
end;
end;//if enpassantInt<>-1
// pop ls1b from piece bitboard copy
pop_bit(bitboard, source_square);
end;//while bitboard>0
end;//if piece = P_
//
piece = P_
Warning: Spoiler![ Click to expand ][ Click to hide ]
//
piece = K_
// castling moves
if (piece = K_) then begin
// king side castling is available
if (castle and integer(Tcastling(wk)))>0 then begin
// make sure square between king and king's rook are empty
if (get_bit(occupancies_3[both], integer(f1))=0) and (get_bit(occupancies_3[both], integer(g1))=0) then begin
// make sure king and the f1 squares are not under attacks
if (is_square_attacked(e1, black)=0) and (is_square_attacked(f1, black)=0) then
Writeln('castling move: e1g1');
end;
end;
// queen side castling is available
if (castle and integer(Tcastling(wq)))>0 then begin
// make sure square between king and queen's rook are empty
if (get_bit(occupancies_3[both], integer(b1))=0) and (get_bit(occupancies_3[both], integer(c1))=0) and (get_bit(occupancies_3[both], integer(d1))=0) then begin
// make sure king and the f1 squares are not under attacks
if (is_square_attacked(e1, black)=0) and (is_square_attacked(d1, black)=0) then
Writeln('castling move: e1c1');
end;
end;
end;//if piece = K_
//
piece = K_
end//if side = white
else begin
Warning: Spoiler![ Click to expand ][ Click to hide ]
//
piece = p
// pick up black pawn bitboards index
if (piece = p) then begin
// loop over black pawns within black pawn bitboard
while bitboard>0 do begin
// init source square
source_square := TBoard_squares(get_ls1b_index(bitboard));
source_squareInt:=integer(source_square);
// init target square
target_square :=TBoard_squares(source_squareInt + 8);
target_squareInt:=integer(target_square);
//
// generate quite pawn moves
if((not(target_square > h1)) and (get_bit(occupancies_3[both], target_squareInt)=0)) then begin
// pawn promotion
if (source_square >= a2) and (source_square <= h2) then begin
Writeln('pawn promotion: ', square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt],'q');
Writeln('pawn promotion: ', square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt],'r');
Writeln('pawn promotion: ', square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt],'b');
Writeln('pawn promotion: ', square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt],'n');
end else begin
// one square ahead pawn move
Writeln('pawn push: ', square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt]);
// two squares ahead pawn move
if ((source_square >= a7) and (source_square <= h7) and (get_bit(occupancies_3[both], target_squareInt+8)=0) ) then
Writeln('double pawn push: ', square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt + 8]);
end;//if
end;//if
//
// init pawn attacks bitboard
attacks := pawn_attacks[side][source_square] and occupancies_3[white];
// generate pawn captures
while attacks>0 do begin
// init target square
target_square := TBoard_squares(get_ls1b_index(attacks));
target_squareInt:=integer(target_square);
// pawn promotion
if (source_square >= a2) and (source_square <= h2) then begin
Writeln('pawn promotion capture: ', square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt],'q');
Writeln('pawn promotion capture: ', square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt],'r');
Writeln('pawn promotion capture: ', square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt],'b');
Writeln('pawn promotion capture: ', square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt],'n');
end else begin
// one square ahead pawn move
Writeln('pawn capture: ', square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt]);
end;
// pop ls1b of the pawn attacks
pop_bit(attacks, target_square);
end;//while attacks>0
//
// generate enpassant captures
if enpassantInt<>-1 then begin
// lookup pawn attacks and bitwise AND with enpassant square (bit)
enpassant_attacks := pawn_attacks[side][source_square] and (n1 shl enpassantInt);
if enpassant_attacks>0 then begin
// init enpassant capture target square
target_enpassantInt := get_ls1b_index(enpassant_attacks);
Writeln('pawn enpassant capture: ', square_to_coordinates[source_squareInt], square_to_coordinates[target_enpassantInt]);
end;
end;//if enpassantInt<>-1
//
// pop ls1b from piece bitboard copy
pop_bit(bitboard, source_square);
end;//while bitboard>0
end;//if piece = p
//
piece = p
Warning: Spoiler![ Click to expand ][ Click to hide ]
//
piece = k
// castling moves
if (piece = k) then begin
// king side castling is available
if (castle and integer(Tcastling(bk)))>0 then begin
// make sure square between king and king's rook are empty
if (get_bit(occupancies_3[both], integer(f8))=0) and (get_bit(occupancies_3[both], integer(g8))=0) then begin
// make sure king and the f1 squares are not under attacks
if (is_square_attacked(e8, white)=0) and (is_square_attacked(f8, white)=0) then
Writeln('castling move: e8g8');
end;
end;
// queen side castling is available
if (castle and integer(Tcastling(bq)))>0 then begin
// make sure square between king and queen's rook are empty
if (get_bit(occupancies_3[both], integer(b8))=0) and (get_bit(occupancies_3[both], integer(c8))=0) and (get_bit(occupancies_3[both], integer(d8))=0) then begin
// make sure king and the f1 squares are not under attacks
if (is_square_attacked(e8, white)=0) and (is_square_attacked(d8, white)=0) then
Writeln('castling move: e8c8');
end;
end;
end;//if piece = k
//
piece = k
end;//else - if (side = white)
//
Warning: Spoiler![ Click to expand ][ Click to hide ]
// genarate knight moves
if ((side = white) and (piece = N_)) or ((side = black) and (piece = n))then begin
// loop over source squares of piece bitboard copy
while bitboard>0 do begin
// init source square
source_square := TBoard_squares(get_ls1b_index(bitboard));
source_squareInt:=integer(source_square);
// init piece attacks in order to get set of target squares
attacks := knight_attacks[source_square] and (not(occupancies_3[side]));
while attacks>0 do begin
// init target square
target_square := TBoard_squares(get_ls1b_index(attacks));
target_squareInt:=integer(target_square);
// quite move
if get_bit(occupancies_3[both], target_squareInt)=0 then
Writeln('knight quiet move: ',square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt])
// capture move
else Writeln('knight capture: ',square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt]);
// pop ls1b of the pawn attacks
pop_bit(attacks, target_square);
end;
// pop ls1b from piece bitboard copy
pop_bit(bitboard, source_square);
end;
end;//knight
//
Warning: Spoiler![ Click to expand ][ Click to hide ]
// generate bishop moves
if ((side = white) and (piece = B_)) or ((side = black) and (piece = b))then begin
// loop over source squares of piece bitboard copy
while bitboard>0 do begin
// init source square
source_square := TBoard_squares(get_ls1b_index(bitboard));
source_squareInt:=integer(source_square);
// init piece attacks in order to get set of target squares
attacks := get_bishop_attacks(source_square, occupancies_3[both]) and (not(occupancies_3[side]));
while attacks>0 do begin
// init target square
target_square := TBoard_squares(get_ls1b_index(attacks));
target_squareInt:=integer(target_square);
// quite move
if get_bit(occupancies_3[both], target_squareInt)=0 then
Writeln('bishop quiet move: ',square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt])
// capture move
else Writeln('bishop capture: ',square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt]);
// pop ls1b of the pawn attacks
pop_bit(attacks, target_square);
end;
// pop ls1b from piece bitboard copy
pop_bit(bitboard, source_square);
end;
end;//bishop
//
Warning: Spoiler![ Click to expand ][ Click to hide ]
// generate rook moves
if ((side = white) and (piece = R_)) or ((side = black) and (piece = r))then begin
// loop over source squares of piece bitboard copy
while bitboard>0 do begin
// init source square
source_square := TBoard_squares(get_ls1b_index(bitboard));
source_squareInt:=integer(source_square);
// init piece attacks in order to get set of target squares
attacks := get_rook_attacks(source_square, occupancies_3[both]) and (not(occupancies_3[side]));
while attacks>0 do begin
// init target square
target_square := TBoard_squares(get_ls1b_index(attacks));
target_squareInt:=integer(target_square);
// quite move
if get_bit(occupancies_3[both], target_squareInt)=0 then
Writeln('rook quiet move: ',square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt])
// capture move
else Writeln('rook capture: ',square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt]);
// pop ls1b of the pawn attacks
pop_bit(attacks, target_square);
end;
// pop ls1b from piece bitboard copy
pop_bit(bitboard, source_square);
end;
end;//rook
//
Warning: Spoiler![ Click to expand ][ Click to hide ]
// generate queen moves
if ((side = white) and (piece = Q_)) or ((side = black) and (piece = q))then begin
// loop over source squares of piece bitboard copy
while bitboard>0 do begin
// init source square
source_square := TBoard_squares(get_ls1b_index(bitboard));
source_squareInt:=integer(source_square);
// init piece attacks in order to get set of target squares
attacks := get_queen_attacks(source_square, occupancies_3[both]) and (not(occupancies_3[side]));
while attacks>0 do begin
// init target square
target_square := TBoard_squares(get_ls1b_index(attacks));
target_squareInt:=integer(target_square);
// quite move
if get_bit(occupancies_3[both], target_squareInt)=0 then
Writeln('queen quiet move: ',square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt])
// capture move
else Writeln('queen capture: ',square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt]);
// pop ls1b of the pawn attacks
pop_bit(attacks, target_square);
end;
// pop ls1b from piece bitboard copy
pop_bit(bitboard, source_square);
end;
end;//queen
//
Warning: Spoiler![ Click to expand ][ Click to hide ]
// generate king moves
if ((side = white) and (piece = K_)) or ((side = black) and (piece = k))then begin
// loop over source squares of piece bitboard copy
while bitboard>0 do begin
// init source square
source_square := TBoard_squares(get_ls1b_index(bitboard));
source_squareInt:=integer(source_square);
// init piece attacks in order to get set of target squares
attacks := king_attacks[source_square] and (not(occupancies_3[side]));
while attacks>0 do begin
// init target square
target_square := TBoard_squares(get_ls1b_index(attacks));
target_squareInt:=integer(target_square);
// quite move
if get_bit(occupancies_3[both], target_squareInt)=0 then
Writeln('king quiet move: ',square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt])
// capture move
else Writeln('king capture: ',square_to_coordinates[source_squareInt], square_to_coordinates[target_squareInt]);
// pop ls1b of the pawn attacks
pop_bit(attacks, target_square);
end;
// pop ls1b from piece bitboard copy
pop_bit(bitboard, source_square);
end;
end;//king
end;//for
end;
r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1
Для этой позиции должно быть 48 ходов
Warning: Spoiler![ Click to expand ][ Click to hide ]
8 r . . . k . . r
7 p . p p q p b .
6 b n . . p n p .
5 . . . P N . . .
4 . p . . P . . .
3 . . N . . Q . p
2 P P P B B P P P
1 R . . . K . . R
Bitboard в программировании шахмат №2
04 Фев 2023 07:31 #134
Гдето я прочитал, что наибольшее количество легальных ходов в шахматной позиции составляет 218 ходов.
Но на вскидку не нашел эту позицию.
Какая она, эта позиция?
Мне оч даже любопытно.
Bitboard в программировании шахмат №2
04 Фев 2023 09:11 #136
alexlaw wrote:
Гдето я прочитал, что наибольшее количество легальных ходов в шахматной позиции составляет 218 ходов.
Но на вскидку не нашел эту позицию.
Какая она, эта позиция?
Мне оч даже любопытно.
Да что-то такое было... Но это дикость
Надо видимо пешек наставить на 7ю с кучей взятий и т.д.
0001 1 white king can castle to the king side
0010 2 white king can castle to the queen side
0100 4 black king can castle to the king side
1000 8 black king can castle to the queen side
examples
1111 both sides an castle both directions
1001 black king => queen side
white king => king side
Попробовал списки делфи для хранения, добавления и печати списков ходов.
Warning: Spoiler![ Click to expand ][ Click to hide ]
type
//указатель на структуру данных
moves = ^move_list;
//элемент односвязного списка
move_list = record
//ходы
move:array[0..255] of integer;
// move count
count:integer;
//указатель на следующий элемент
next_move:moves;
end;
var
add_move:moves;
Не уверен, что это лучший вариант.
Но вроде работает.
Warning: Spoiler![ Click to expand ][ Click to hide ]
Bitboard в программировании шахмат №2
06 Фев 2023 08:30 #139
alexlaw wrote:
1. Атаки прыгающих фигур (король,конь,пешка)
2. Атаки скользящих фигур (слон,ладья,ферзь)
3. Представление данных о позиции в памяти компа.
4. Интерфейс (взаимодействие с человеком) для наглядного представления работы движка.
5. Функции
- подсчет битов в числе
- нахождение первого установленного бита в числе
- проверка установлен ли бит в любой позиции числа
- сброс любого бита в числе
- нахождение для каждого поля доски всех атак на это поле со стороны фигур, принадлежащих белым или черным
6. Генератор ходов
7. Сохранять и восстанавливать состояние текущей позиции (или отменять ход) после применения функции сделать ход (MAKE MOVE)
Мне кажется, что реализация "отменить ход" - сложнее, чем сохранить позицию с флагами и затем восстановить.
Есть интереснаяфункция memcpy (СИ).
В делфи тоже она есть - Move
Я не знал об этом.
Операция "@" - это получение адреса объекта. Операция "^" - получение
объекта по его адресу (под объектом я понимаю тут всё, что может занимать
память, а не только то, что называют объектом в ООП). Теперь разберёмся,
что такое нетипизированный параметр. Это такой параметр, что при вызове
функции надо указать некий объект, а реально функции будет передан
адрес этого объекта. Таким образом, функция Move фактически получает два адреса,
хотя формально ей передаются два объекта, и она копирует байты из одного
адреса в другой. Следовательно, на входе нам нужно передать в неё объекты,
которые располагаются по тем адресам, которые нас интересуют
Move(Source,Dest[j],Count);
Move(Source^,Dest^[j],Count);
Както так
31.Bitboard CHESS ENGINE in C: preserving & restoring BOARD STATE aka COPY/MAKE approach
// preserve board state
procedure copy_board();
begin
Move(bitboards_12[P_],bitboards_12_copy[P_],96);
Move(occupancies_3[white],occupancies_3_copy[white],24);
Move((@add_move^.move[0])^,(@add_move_copy^.move[0])^,256*SizeOf(integer));
Move((@add_move^.count)^,(@add_move_copy^.count)^,SizeOf(integer));
side_copy:=side;
enpassantInt_copy:=enpassantInt;
enpassant_copy:=enpassant;
castle_copy:=castle;
end;
// restore board state
procedure take_back();
begin
Move(bitboards_12_copy[P_],bitboards_12[P_],96);
Move(occupancies_3_copy[white],occupancies_3[white],24);
Move((@add_move_copy^.move[0])^,(@add_move^.move[0])^,256*SizeOf(integer));
Move((@add_move_copy^.count)^,(@add_move^.count)^,SizeOf(integer));
side:=side_copy;
enpassantInt:=enpassantInt_copy;
enpassant:=enpassant_copy;
castle:=castle_copy;
end;
Я кстати не знаю почему Макс не сохраняет ходы с флагами, а только доски.
Дальше у него идут уроки по MAKE MOVE (сделать ход)
Bitboard в программировании шахмат №2
06 Фев 2023 11:58 #140
alexlaw wrote:
Есть интереснаяфункция memcpy (СИ).
В делфи тоже она есть - Move
Я не знал об этом.
Это не совсем одно и то же...
Move это C-аналог memmove, а не memcpy
Аналог memcpy это CopyMemory вроде (еще Copy есть, но это тоже немного другое)
Разница довольно тонкая, но в Дельфи надо отдельно разбираться с особенностями. Может там и без разницы, не знаю.
В С там все понятно.
Но в любом случае это очень низкоуровневые операции. Для Дельфи и объектов плохо рекомендовано.
Получить облом в виде порчи памяти или утечек оной очень легко.
Bitboard в программировании шахмат №2
06 Фев 2023 13:14 #141
Сразу задался вопросом, правильно или нет использовать функцию Move или реализовывать как то по другому.
Ответ на цитатуVladimirovich wrote:
Аналог memcpy это CopyMemory вроде
нашел.
При вызове CopyMemory Delphi вызывает не API-функцию с таким именем, а свою, исходный код которой можно найти в Windows.pas:
procedure CopyMemory(Destination: Pointer; Source: Pointer; Length: DWORD);
begin
Move(Source^, Destination^, Length);
end;
Еще провел тест
init_all();
if parse_fen('N7/8/2K5/8/8/8/8/7k w - - 0 1')=false then Writeln('Ошибка FEN строки ...');
New(add_move);New(add_move_copy);
generate_moves();
print_move_list();
copy_board();
print_move_list();
N7/8/2K5/8/8/8/8/7k w - - 0 1
Warning: Spoiler![ Click to expand ][ Click to hide ]
Исходную память не нарушил, хотя почему назвали Move, не понятно
Для меня важно, чтобы не вылезла какая нибудь трудноуловимая ошибка.
Но вроде все работает, как задумал Макс, только в реализации делфи.
Будем двигаться дальше вместе с Максом
Bitboard в программировании шахмат №2
06 Фев 2023 13:23 #142
alexlaw wrote:
Для меня важно, чтобы не вылезла какая нибудь трудноуловимая ошибка.
Это возникнет, если адреса или Count нарушить
Если нет, то все хорошо. Иначе будет больно
P.S. Главная разница в том, что изначальная memcpy в С вообще ничего не проверяет, в отличие от memmove.
Поэтому она быстрее.
Понятно, что поздние реализации много чего накрутили поверх, так что надо смотреть конкретно в каждом случае
Bitboard в программировании шахмат №2
07 Фев 2023 09:41 #143
32.Bitboard CHESS ENGINE in C: implementing MAKE MOVE function (moving pieces)
Скелет функции - MAKE MOVE
Мне нравится, что Макс дает инфу по чуть.
Не спешит сразу все.
Короче можно уже подвигать фигурами.
Warning: Spoiler![ Click to expand ][ Click to hide ]
Warning: Spoiler![ Click to expand ][ Click to hide ]
==================================
\**********************************/
}
// make move on chess board
function make_move(move:integer;move_flag:TMove_types):integer;
var
source_squareInt,target_squareInt,pieceInt,promotedInt:integer;
capture,double_push,enpass,castling:integer;
begin
// quite moves
if (move_flag = all_moves) then begin
// preserve board state
copy_board();
// parse move
source_squareInt:=get_source(move,get_move_source);
target_squareInt:=get_source(move,get_move_target);
pieceInt:=get_source(move,get_move_piece);
promotedInt:=get_source(move,get_move_promoted);
capture:=get_source(move,get_move_capture);
double_push:=get_source(move,get_move_doubl);
enpass:=get_source(move,get_move_enpassan);
castling:=get_source(move,get_move_castling);
// move piece
pop_bit(bitboards_12[Tencode_pieces(pieceInt)], TBoard_squares(source_squareInt));
set_bit(bitboards_12[Tencode_pieces(pieceInt)], TBoard_squares(target_squareInt));
// capture moves
end else begin
end;
end;
Warning: Spoiler![ Click to expand ][ Click to hide ]
==================================
\**********************************/}var
i:integer;
begin
//Переключение окна консоли на кодовую страницу CP1251 (Win-1251).
//Если после переключения русские буквы показываются неверно,
//следует открыть системное меню консольного окна - щелчком мыши в левом
//верхнем углу окна консоли. И выбрать:
//Свойства - закладка "Шрифт" - выбрать шрифт: "Lucida Console".
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
// SetConsoleOutputCP(CP_UTF8);
// ==================================
// init all
init_all();
if parse_fen('r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1 ')=false then Writeln('Ошибка FEN строки ...');
//выделение памяти для нового списка ходов
New(add_move);New(add_move_copy);
generate_moves();
for i := 0 to add_move^.count-1 do begin
// preserve board state
copy_board();
Write(i+1,':');
print_move(add_move^.move);
print_board();
Readln;
clrscr();
// make move
make_move(add_move^.move,all_moves);
Write(i+1,':');
Writeln('');
print_board();
Readln;
clrscr();
// take back
take_back();
end;
print_board();
Writeln('Нажмите <ENTER>, чтобы выйти ...');
Readln;
end.
Bitboard в программировании шахмат №2
07 Фев 2023 20:39 #145
33.Bitboard CHESS ENGINE in C: implementing MAKE MOVE function (handling captures)
(ходы взятия)
34.Bitboard CHESS ENGINE in C: implementing MAKE MOVE function (handling pawn promotions)
(превращение пешек)
35.Bitboard CHESS ENGINE in C: implementing MAKE MOVE function (handling enpassant moves)
(взятие на проходе)
36.Bitboard CHESS ENGINE in C: implementing MAKE MOVE function (handling double pawn pushes)
(установка битого поля)
37.Bitboard CHESS ENGINE in C: implementing MAKE MOVE function (handling castling moves)
(рокеровка)
38.Bitboard CHESS ENGINE in C: implementing MAKE MOVE function (updating castling rights)
(обновление флагов рокеровки)
39.Bitboard CHESS ENGINE in C: implementing MAKE MOVE function (updating occupancy bitboards)
(массивы занятости - белые, черные, все фигуры)
40.Bitboard CHESS ENGINE in C: implementing MAKE MOVE function (checking whether the king is in check)
(проверка на легальность хода - король под ударом или нет)
Узнал много нового.
Результат 40 уроков
Last Edit: 08 Фев 2023 06:52 by Vladimirovich. Reason: unused zip removed
Bitboard в программировании шахмат №2
09 Фев 2023 21:13 #146
К сожалению я не смог адаптировать код СИ
// perft driver
static inline void perft_driver(int depth)
{
// reccursion escape condition
if (depth == 0)
{
// increment nodes count (count reached positions)
nodes++;
return;
}
// create move list instance
moves move_list[1];
// generate moves
generate_moves(move_list);
// loop over generated moves
for (int move_count = 0; move_count < move_list->count; move_count++)
{
// preserve board state
copy_board();
// make move
if (!make_move(move_list->moves[move_count], all_moves))
// skip to the next move
continue;
// call perft driver recursively
perft_driver(depth - 1);
// take back
take_back();
}
}
Т.е. могу сохранить одну позицию с флагами.
Когда больше одной позиции то позиции, точнее ходы теряются.
Пришлось делать заплатки в виде стека.
В итоге тест perft не прошел.
Причем только в одной тестовой позиции и на глубине больше 5
8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - -
Warning: Spoiler![ Click to expand ][ Click to hide ]
В других позициях прошел
Warning: Spoiler![ Click to expand ][ Click to hide ]
Прогнал через профайлер
Warning: Spoiler![ Click to expand ][ Click to hide ]
Bitboard в программировании шахмат №2
10 Фев 2023 13:40 #150
Итак начал вырисовываться план.
1. Находим из предыдущей таблицы наименьшую разницу в ходах
- b4a4 - 745667
- b4a4 - 745500
Разница 167 ходов
2. Обрезаем программно все другие ходы
- if ((depth=6) and (j<>5))then continue; Делфи
- if ((depth==6) & (move_count != 5)) continue; Си
3. Делаем проверку (сначала depth=5)
- выводим на глубине 1 - ходы короля
Делфи
if ((depth = 1) and (Tencode_pieces(get_source(add_move^.move[j],get_move_piece))=K_)) then begin
old_nodes := nodes - cummulative_nodes;
cummulative_nodes:=nodes;
Writeln('move_test:',square_to_coordinates[integer(get_source(add_move^.move[j],get_move_source))],
square_to_coordinates[integer(get_source(add_move^.move[j],get_move_target))],
promoted_pieces[get_source(add_move^.move[j],get_move_promoted)],' nodes:',old_nodes);
end;//test
