Ключевое слово
27 | 01 | 2023
Новости Библиотеки
Шахматы Онлайн
Welcome, Guest
Username: Password: Remember me

TOPIC: Bitboard в программировании шахмат №2

Bitboard в программировании шахмат №2 11 Дек 2022 06:32 #91

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 99851
  • Thank you received: 1817
  • Karma: 101
alexlaw wrote:
В принципе биты повернуть в 64 битном числе оказалось не сложно.

Вот тут всевозможные операции для битбордов через битовые же операции

www.chessprogramming.org/Flipping_Mirroring_and_Rotating
Каждому - своё.

Bitboard в программировании шахмат №2 11 Дек 2022 09:37 #92

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Жилец
  • Posts: 67
  • Karma: 0
Vladimirovich wrote:
Вот тут всевозможные операции для битбордов через битовые же операции

Когда я размышлял об этом, то склонился к варианту формирования 64 битного числа повернутого битбоарда всех фигур на доске одновременно с формированием битборда с нормальным расположением бит.
//0-KING, 1-QUEEN, 2-ROOK, 3-BISHOP, 4-KNIGHT, 5-PAWN
  //массивы фигур
  WPieceArray: array [0..5]  of  UInt64 = (0,0,0,0,0,0);
  BPieceArray: array [0..5]  of  UInt64 = (0,0,0,0,0,0);
  //Белые и черные фигуры в одном 64 битном числе
  WhitePieceU64:UInt64 = 0;
  BlackPieceU64:UInt64 = 0;
  //все фигуры в одном 64 битном числе
  AllPieceU64:UInt64 = 0;
  //Белые и черные фигуры в одном 64 битном числе
  //в повернутом на 90 битбоарде
  WhitePieceU64R90:UInt64 = 0;
  BlackPieceU64R90:UInt64 = 0;
  //все фигуры в одном 64 битном числе
  //в повернутом на 90 битбоарде
  AllPieceU64R90:UInt64 = 0;
//функция парсинга fen строки в массивы фигур WPiece, BPiece
//0-KING, 1-QUEEN, 2-ROOK, 3-BISHOP, 4-KNIGHT, 5-PAWN
function FenToU64(sfen:String):boolean;
var
// i - индекс массива
// k - длина строки fen
// n - счетчик шахматных клеток (64 клетки)
// num - позиция символа в strN или strF
i,k,n,num:integer;
//строки для цифр из fen строки -  strN, фигур - strF, единичного символа - s01
strN,strF,s01:string;
//массивы фигур
 WPieceNew: array [0..5]  of  UInt64;
 BPieceNew: array [0..5]  of  UInt64;
begin
//если fen строка пустая, то ошибка fen строки
result:=false;
 if sfen='' then exit;
// инициализация строк для парсинга fen строки
 strN:='12345678';
 strF:='KQRBNPkqrbnp';
//инициализация локальных массивов фигур
   for i := 0 to 5 do  begin
    WPieceNew[i]:=0;
    BPieceNew[i]:=0;
   end;
  WhitePieceU64:=0;
  BlackPieceU64:=0;
  WhitePieceU64R90:=0;
  BlackPieceU64R90:=0;
//определяем длину fen строки
   k:=length(sfen);
//сбрасываем счетчик
   n:=-1;
//перебираем символы fen строки
      for i := 1 to k do begin
      //берем один символ  fen строки на позиции i
      //возвращает подстроку строки sfen начинающуюся с индекса i длиной 1 символ
         s01:=copy(sfen,i,1);
      //возвр. позицию символа s01 в строке strN, если нет символа, то 0
      //сначала проверяем s01 - это цифра?
         num:=pos(s01,strN);
      //continue прерывает только выполнение текущей итерации,
      //текущего выполнения тела цикла
      //и передает управление на следующую итерацию.
         if s01='/' then continue;
      //если пробел заканчиваем парсинг   
         if s01=' ' then break;
      //увеличиваем счетчик шахматных клеток n
      // если num=0, значит символ s01 фигура
         if num=0 then begin
              n:=n+1;
      // иначе цифра
         end else begin
              n:=n+num;
         end;
      //если клеток больше 64(0..63), то ошибка fen строки
         if n>63 then exit;
      //проверяем s01 - это символ фигуры?
          num:=pos(s01,strF);
      //если num - это не допустимый символ,  то ошибка fen строки
          if ((num=0) and (pos(s01,strN)=0))then exit;
      //заносим фигуры в массивы    
          if num>0 then begin
            if num<7 then begin
               WPieceNew[num-1]:=WPieceNew[num-1] or MaskOneBit[n];
               //белые фигуры в одно 64 битное число
               WhitePieceU64:=WhitePieceU64 or WPieceNew[num-1];
WhitePieceU64R90:=WhitePieceU64R90 or MaskOneBit[RotatePos(n,90)];
            end else begin
               BPieceNew[num-7]:=BPieceNew[num-7] or MaskOneBit[n];
               //черные фигуры в одно 64 битное число
               BlackPieceU64:=BlackPieceU64 or BPieceNew[num-7];
BlackPieceU64R90:=BlackPieceU64R90 or MaskOneBit[RotatePos(n,90)];
            end;
          end;
      end;//for
//если клеток не равно 64(0..63), то ошибка fen строки
  if n<>63 then exit;
//если королей не равно 1, то ошибка fen строки
  if CountBitsInt64(WPieceNew[0])<>1 then exit;
  {
ShowMessage('Белый король на поле - ' +
IntToStr(SeniorBit(WPieceNew[0],WPieceNew[0] shr 32)-1) +' '+ IntToStr(JuniorBit(WPieceNew[0],WPieceNew[0] shr 32)));
  }
  if CountBitsInt64(BPieceNew[0])<>1 then exit;
// заполняем глобальные массивы фигур WPiece,BPiece
   for i := 0 to 5 do  begin
    WPieceArray[i]:=WPieceNew[i];
    BPieceArray[i]:=BPieceNew[i];
   end;
   //все фигуры в одно 64 битное число
   AllPieceU64:=WhitePieceU64 or BlackPieceU64;
   AllPieceU64R90:=WhitePieceU64R90 or BlackPieceU64R90;
//ShowMessage('парсинг завершен успешно');
//парсинг завершен успешно
  result:=true;
end;

WhitePieceU64R90:=WhitePieceU64R90 or MaskOneBit[RotatePos(n,90)];
BlackPieceU64R90:=BlackPieceU64R90 or MaskOneBit[RotatePos(n,90)];
AllPieceU64R90:=WhitePieceU64R90 or BlackPieceU64R90;
Last Edit: 11 Дек 2022 09:39 by alexlaw.

Bitboard в программировании шахмат №2 12 Дек 2022 08:45 #93

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Жилец
  • Posts: 67
  • Karma: 0
alexlaw wrote:
Расстояние определяется проще
Пример h1 - Pos:=63;-черный король
00111111 and 00000111 = 111; 50 and 7 = 7
00111111 shr 3 = 111; 50 shr 3 = 7
с6 - Pos:=18;
18 and 7 = 2
18 shr 3 = 2
A8 - a=0,b=0 H1 - a=7,b=7
a:=Pos and 7;//0..7 горизонталь (буквы)
b:=Pos shr 3;//0..7 вертикаль (цифры)
Расстояние между h1 и c6
(7-2)+(7-2)=10!

Вот этот алгоритм реализовал за черного короля



Чтобы восстановить позицию после нескольких ходов

17.jpg


18.jpg
Last Edit: 12 Дек 2022 09:11 by Vladimirovich.

Bitboard в программировании шахмат №2 12 Дек 2022 09:12 #94

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 99851
  • Thank you received: 1817
  • Karma: 101
Прошу не добавлять EXE, пусть и в архивах.
Каждому - своё.

Bitboard в программировании шахмат №2 12 Дек 2022 09:13 #95

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Жилец
  • Posts: 67
  • Karma: 0
Vladimirovich wrote:
Прошу не добавлять EXE, пусть и в архивах.
Понял
Файл в моем облаке

Черным королем управляет простой алгоритм, описание выше

19.jpg
Last Edit: 12 Дек 2022 12:05 by alexlaw.

Bitboard в программировании шахмат №2 14 Дек 2022 12:14 #96

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Жилец
  • Posts: 67
  • Karma: 0
Чуть поизголялся.
В алгоритм за черного короля добавил +2 балла за то, что король при ходе будет находится от ферзя на расстоянии хода коня.

The untouchable king-02.zip
a:=n and 7;//0..7 горизонталь (буквы)
b:=n shr 3;//0..7 вертикаль (цифры)
best:=ABS(a-a0)+ABS(b-b0);
if (KnightAttak[n] and WPieceArray[1])>0 then best:= best+2;
if best>=max then begin
j:=n;
max:=best;
end;
Last Edit: 14 Дек 2022 21:33 by alexlaw.

Bitboard в программировании шахмат №2 16 Дек 2022 19:10 #97

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Жилец
  • Posts: 67
  • Karma: 0
alexlaw wrote:
Вот этот алгоритм реализовал за черного короля
За белого ферзя задача оказалась не так проста.
Сам по себе ход ферзя нельзя оценить без последующего хода черного короля.
Отсюда следует, что нужно просчитать позицию на некоторую глубину и на этой глубине сделать оценку.
И тут на сцену выходит один из столпов шахматного программирования - алгоритм мини-макс.

origin.gif


Именно для задачи неприкосновенный король есть еще один путь - совершенно простой, но трудоемкий.
Путь такой - создать массив [64],[64] , где первый индекс - позиция белого ферзя, второй индекс - позиция черного короля, в ячейке будет находится ход ферзя.
Как заполнить программно такой массив?
Любые идеи приветствуются.

king1.gif
Last Edit: 17 Дек 2022 21:16 by alexlaw.

Bitboard в программировании шахмат №2 18 Дек 2022 08:52 #98

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Жилец
  • Posts: 67
  • Karma: 0
У меня появился план для заполнения таблицы - непрекосновенный король.
Создать шахматную игру в формате PGN.
Затем написать небольшую прогу для перегона PGN в таблицу.
Вот PGN для мата короля в ближайшем углу к белому королю.
Мат в 12 ходов.


Теперь нужно перегнать короля из дальнего угла в ближний.
По идее нужно 11 ходов








Q7/8/2K5/8/8/8/8/7k w - - 0 1

Справедливо это или нет?
Не более 11 ходов.
Надо быть очень хорошим шахматистом, чтобы загнать короля в противоположный угол за 11 ходов.
Last Edit: 18 Дек 2022 12:40 by alexlaw.

Bitboard в программировании шахмат №2 18 Дек 2022 16:20 #99

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Жилец
  • Posts: 67
  • Karma: 0
12 ходов


Q7/8/2K5/8/8/8/8/7k w - - 0 1

Анализ
Last Edit: 18 Дек 2022 17:19 by alexlaw.

Bitboard в программировании шахмат №2 18 Дек 2022 23:17 #100

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Жилец
  • Posts: 67
  • Karma: 0
Решение есть


Bitboard в программировании шахмат №2 18 Дек 2022 23:42 #101

  • Ruslan73
  • Ruslan73's Avatar
  • OFFLINE
  • Администратор
  • Posts: 32671
  • Thank you received: 647
  • Karma: 50
Человек намного быстрее ставит мат, ходов в 5-6. 1.Фа2 отсекаем короля потом идем королем напротив Крd5-e4-f3 и ставим мат. Во втором случае 1.Фg6 и т.п..
Очевидно алгоритм не оптимален.
Свободу Джулиану Ассанжу!

Bitboard в программировании шахмат №2 19 Дек 2022 05:10 #102

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Жилец
  • Posts: 67
  • Karma: 0
Ruslan73 wrote:
потом идем королем напротив Крd5-e4-f3
По условию задачи, "непрекосновенный король".
Королем ходить нельзя.

Bitboard в программировании шахмат №2 19 Дек 2022 06:34 #103

  • Ruslan73
  • Ruslan73's Avatar
  • OFFLINE
  • Администратор
  • Posts: 32671
  • Thank you received: 647
  • Karma: 50
Думал, Вы уже процедуру матования пишете. Не очень понимаю практический смысл сей задачи что королём ходить нельзя.
Свободу Джулиану Ассанжу!

Bitboard в программировании шахмат №2 20 Дек 2022 20:31 #104

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Жилец
  • Posts: 67
  • Karma: 0
alexlaw wrote:
У меня появился план для заполнения таблицы - непрекосновенный король.
Создать шахматную игру в формате PGN.
Затем написать небольшую прогу для перегона PGN в таблицу.
В принципе прогу набросал

20.jpg


Файлы пректа

Суть - если есть файл test.txt, он подгружается в прогу.
Этот файл и есть таблица ходов ферзя.
Если файла нет он создастся.
Загружается файл PGN - king.pgn
Он имеет такой вид
[Event "?"]
[Site "?"]
[Date "????.??.??"]
[Round "?"]
[White "?"]
[Black "?"]
[Result "1-0"]
[SetUp "1"]
[FEN "Q7/8/2K5/8/8/8/8/7k w - - 0 1"]

1. Qa1+ Kg2 2. Qe1 Kf3 3. Qd2 Ke4 4. Qc3 Kf4 5. Qd3 Ke5 6. Qc4 Kf5 7. Qd4 Kg5 8.
Qe4 Kh5 9. Qf4 Kg6 10. Qe5 Kh6 11. Qf5 Kg7 12. Qe6 Kh8 13. Qe7 Kg8 14. Qe5 Kh7
15. Qf6 Kg8 16. Qh6 Kf7 17. Qg5 Kf8 18. Qg6 Ke7 19. Qf5 Ke8 20. Qd7+ Kf8 21. Qh7
Ke8 22. Qg7 Kd8 23. Qf8# 1-0

Затем кликаем по игровому полю.
Файл PGN проигрывается и заполняется таблица, которая затем сохраняется в файл - test.txt

Затем можно перезапустить прогу с другим PGN и таблица дополнится.
В PGN должен быть один вариант без ветвлений. (Проверка не производится)
Возможны еще улучшения проги.
Например в таблицу сразу могут быть добавлены все ходы в данное поле из других клеток.
В общем считаю я справился с задачей "неприкосновенный король".
Далее вернусь к основной теме.

Bitboard в программировании шахмат №2 11 Янв 2023 20:52 #105

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Жилец
  • Posts: 67
  • Karma: 0
Размышляя над эффективностью какого либо алгоритма, конечно встает вопрос, как именно оценить эффективность.
Разумеется есть много путей и методов оценки.
Так вот, пока я решил оценивать - засечками времени.
Если оценивать какой то очень короткий кусок кода, то лучше в тактах процессора.
Если несколько функций, то лучше с помощью профайлера.
Для начала я буду оценивать расчет атак и ходов только дальнобойных фигур.
На самом деле от принципа расчета этих атак будет зависть скорость работы программы.
Кстати, задача о неприкосновенном короле как нельзя лучше подходит для выбора принципа расчета этих атак.
Функция засечек времени
//Start, Stop: cardinal;
//Elapsed: cardinal;
//засекли начало выполнения операции
// GetTickCount -  uses Windows
//Start:=GetTickCount;
//засекли окончание выполнения операции
//Stop:=GetTickCount;
//время в миллисекундах
//Elapsed:=Stop-Start;
//TimeCount(Elapsed);
procedure TimeCount(Ms : cardinal);
var
  H, M, S : Integer;
begin
  //Время, выраженное в миллисекундах. 40 часов 3 минуты 2 секунды и 100 миллисекунд.
  //Ms := 40 * 60 * 60 * 1000 + 3 * 60 * 1000 + 2 * 1000 + 100;
  //Часы.
  H := Ms div (60 * 60 * 1000);
  Ms := Ms mod (60 * 60 * 1000); //Остаток.
  //Минуты.
  M := Ms div (60 * 1000);
  Ms := Ms mod (60 * 1000); //Остаток.
  //Секунды.
  S := Ms div 1000;
  //Миллисекунды.
  Ms := Ms mod 1000; //Остаток.
  //uses Dialogs,SysUtils,
  //ShowMessage 
  //Ответ.
 ShowMessage(
    'Время:'
    + #13#10'Часы: ' + IntToStr(H)
    + #13#10'Минуты: ' + IntToStr(M)
    + #13#10'Секунды: ' + IntToStr(S)
    + #13#10'Миллисекунды: ' + IntToStr(Ms) );
end;

Второй важный момент.
Нужен эталон, т.е. проверка правильности работы алгоритма.
Таким эталоном я считаю прогу - Quick Perft by H.G. Muller написанной на СИ
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/***************************************************************************/
/* Move generator based on separate Slider/Leaper/Pawn tables .            */
/***************************************************************************/

#define FAKE 3
#define MAXTIM 0
#if MAXTIM
/* For detailed timings (MAXTIM=20) we need assembly routine to read TSC */
#define TIME(A) times[A] += rdtsc()-3;

int times[MAXTIM];
char *(names[MAXTIM])={"pintest", "contact", "castle", "ep-capt", "capture",
                "pawns", "leapers", "sliders", "filter", "king   ",
                "do    ", "undo   ", "recapt.", "", "", "", "", "total  "};
#else
#define TIME(A)
#endif

/* Zobris key layout */
#define Zobrist(A,B) (*(long long int *) (Zob[(A)-WHITE] + (B)))
#define XSIZE (8*1024)
union _bucket
{
  struct { // one 32-byte entry
    unsigned long long int Signature1;
    unsigned long long int Signature2;
    unsigned long long int longCount;
    unsigned long long int Dummy;
  } l;
  struct { // two packed 16-byte entries
    unsigned long long int Signature[2];
    unsigned int Count[2];
    unsigned int Extension[2];
  } s;
} *Hash, ExtraHash[XSIZE];

/* capture codes */
#define C_ORTH    1
#define C_DIAG    2
#define C_KNIGHT  4
#define C_SIDE    8
#define C_FORW    0x10
#define C_FDIAG   0x20
#define C_BACKW   0x40
#define C_BDIAG   0x80
#define C_FERZ    (C_FDIAG|C_BDIAG)
#define C_WAZIR   (C_SIDE|C_FORW|C_BACKW)
#define C_KING    (C_FERZ|C_WAZIR)
#define C_BISHOP  (C_FERZ|C_DIAG)
#define C_ROOK    (C_WAZIR|C_ORTH)
#define C_PPAWN   (C_FDIAG)
#define C_MPAWN   (C_BDIAG)
#define C_QUEEN   (C_BISHOP|C_ROOK)
#define C_CONTACT (C_KING|C_KNIGHT)
#define C_DISTANT (C_ORTH|C_DIAG)

/* board codes (32 per side: each 16 Pieces, 16 Pawns) */
#define WHITE  0x20
#define BLACK  0x40
#define COLOR  (BLACK|WHITE)
#define GUARD  (COLOR|0x80)
#define DUMMY  (WHITE-1+0x80)
#define PAWNS  0x10

#define NPCE    (2*WHITE)

#define KING   7
#define QUEEN  6
#define ROOK   5
#define BISHOP 4
#define KNIGHT 3

/* overlays that interleave other piece info in pos[] */
#define kind (pc+1)
#define cstl (pc+1+NPCE)
#define pos  (pc+1+NPCE*2)
#define code (pc+1+NPCE*3)

/* Piece counts hidden in the unused Pawn section, indexed by color */
#define LastKnight  (code-4)
#define FirstSlider (code-3)
#define FirstPawn   (code-2)

#define PUSH(A,B) stack[msp++] = (A)+(B);

/* offset overlays to allow negative array subscripts      */
/* and avoid cache collisions of these heavily used arrays */
#define board      (brd+1)                /* 12 x 16 board: dbl guard band */
#define capt_code  (brd+1+0xBC+0x77)      /* piece type that can reach this*/
#define delta_vec  ((char *) brd+1+0xBC+0xEF+0x77) /* step to bridge certain vector */

int rseed = 87105015;
unsigned long long int accept[30], reject[30], miss[30];
char *Zob[2*NPCE];
unsigned char
        pc[NPCE*4+1], /* piece list, equivalenced with various piece info  */
        brd[0xBC+2*0xEF+1],      /* contains play bord and 2 delta boards  */
        CasRights,               /* one bit per castling, clear if allowed */
        HashFlag,

        /* piece-number assignment of first row, and piece types */
        array[] = {12, 1, 14, 11, 0, 15, 2, 13,
                   5, 3, 4, 6, 7, 4, 3, 5},
        capts[] = {0, C_PPAWN, C_MPAWN, C_KNIGHT, C_BISHOP,
                      C_ROOK, C_QUEEN, C_KING};
char
        noUnder = 0,
        queen_dir[]   = {1, -1, 16, -16, 15, -15, 17, -17},
        king_rose[]   = {1,17,16,15,-1,-17,-16,-15},
        knight_rose[] = {18,33,31,14,-18,-33,-31,-14};
char buf[80];

char Keys[1040];
int path[100];
int stack[1024], msp, ep1, ep2, Kmoves, Promo, Split, epSqr, HashSize, HashSection;
unsigned long long int HashKey=8729767686LL, HighKey=1234567890LL, count, epcnt, xcnt, ckcnt, cascnt, promcnt, nodecount; /* stats */
FILE *f;
clock_t ttt[30];

void board_init(char *b)
{ /* make an empty board surrounded by guard band of uncapturable pieces */
        int i;

        for(i= -1; i<0xBC; i++) b[i] = (i-0x22)&0x88 ? GUARD : DUMMY;
}

void delta_init()
{   /* fill 0x88-style attack tables, with capture codes and vectors */
        int i, j, k, m, y;

        /* contact captures (cannot be blocked) */
        capt_code[ 15] = capt_code[ 17] = C_FDIAG;
        capt_code[-15] = capt_code[-17] = C_BDIAG;
        capt_code[  1] = capt_code[ -1] = C_SIDE;
        capt_code[ 16] = C_FORW;
        capt_code[-16] = C_BACKW;

        for(i=0; i<8; i++)
        {   /* in all directions */
            capt_code[knight_rose[i]] = C_KNIGHT;
            delta_vec[knight_rose[i]] = knight_rose[i];
            /* distant captures (can be blocked) */
            k = queen_dir[i];
            m = i<4 ? C_ORTH : C_DIAG;
            y = 0;  
            for(j=0; j<7; j++)
            {   /* scan along ray */
                delta_vec[y+=k] = k;
                /* note that first is contact */
                if(j) capt_code[y] = m;
            }
        }

}

void piece_init(void)
{   /* initialize piece list to initial setup */
        int i, j, k;

    /* initalize piece type and position, in initial setup */
        for(i=0; i<8; i++)
        {   kind[array[i]+WHITE] =
            kind[array[i]] = array[i+8];
            kind[i+PAWNS]       = 1;
            kind[i+PAWNS+WHITE] = 2;
            pos[array[i]]       = i+0x22;
            pos[array[i]+WHITE] = i+0x92;
            pos[i+PAWNS]       = i+0x32;
            pos[i+PAWNS+WHITE] = i+0x82;
        }

    /* set capture codes for each piece */
        for(i=0; i<NPCE; i++) code[i] = capts[kind[i]];

    /* set castling spoilers (King and both original Rooks) */
        cstl[0]        = WHITE;
        cstl[12]       = WHITE>>2;
        cstl[13]       = WHITE>>4;
        cstl[0 +WHITE] = BLACK;
        cstl[12+WHITE] = BLACK>>2;
        cstl[13+WHITE] = BLACK>>4;

    /* piece counts (can change when we compactify lists, or promote) */
        LastKnight[WHITE]  =  2;
        FirstSlider[WHITE] = 11;
        FirstPawn[WHITE]   = 16;
        LastKnight[BLACK]  =  2+WHITE;
        FirstSlider[BLACK] = 11+WHITE;
        FirstPawn[BLACK]   = 16+WHITE;

        Zob[DUMMY-WHITE] = Keys-0x22;
}

void setup(void)
{   /* put pieces on the board according to the piece list */
        int i, j, k;

        for(i=0; i<WHITE-8; i++)
        {   if(pos[i]      ) board[pos[i]]       = WHITE + i;
            if(pos[i+WHITE]) board[pos[i+WHITE]] = BLACK + i;
        }
}

char asc[] = ".+pnbrqkxxxxxxxx.P*NBRQKXXXXXXXX";

void pboard(char *b, int n, int bin)
{   /* print board of n x n, in hex (bin=1) or ascii */
    int i, j, k;

    for(i=n-1; i>=0; i--)
    {
        for(j=0; j<n; j++)
            if(bin) printf(" %2x", b[16*i+j]&0xFF);
            else    printf(" %c", (b[16*i+j]&0xFF)==GUARD ? '-' :
                    asc[kind[(b[16*i+j]&0x7F)-WHITE]+((b[16*i+j]&WHITE)>>1)]);
        printf("\n");
    }
    printf("\n");
}

int checker(int col)
{
    int i;
    for(i=0; i<8; i++) {
        int v = king_rose[i];
        int x = pos[col-WHITE] + v;
        int piece = board[x];
        if((piece & COLOR) == (col^COLOR)) {
            if(code[piece-WHITE] & capt_code[-v]) return x;
        }
        v = knight_rose[i];
        x = pos[col-WHITE] + v;
        piece = board[x];
        if((piece & COLOR) == (col^COLOR)) {
            if(code[piece-WHITE] & capt_code[-v]) return x;
        }
    }
    return 0;
}

#ifndef FEN
int ReadFEN(char *FEN)
{
    int row, file, Piece, i, cc, col, nr;
    char c, *p;

    /* remove all pieces */
    for(i=0; i<NPCE; i++) pos[i] = cstl[i] = 0;
    FirstSlider[WHITE] = 0x10;
    FirstSlider[BLACK] = 0x30;
    LastKnight[WHITE]  = 0x00;
    LastKnight[BLACK]  = 0x20;
    FirstPawn[WHITE]   = 0x18;
    FirstPawn[BLACK]   = 0x38;
    CasRights = 0;

    p = FEN;
    for(row=7; row>=0; row--)
    {   /* read one row of the FEN */
        file = 0;
        do{
          c = *p++;

          if(c>='1' && c<='8') { file += c - '0'; }
          else
          {
            col = WHITE;
            if(c >= 'a') { c += 'A'-'a'; col = BLACK; }
            Piece = BISHOP; cc = 0;
            switch(c)
            {
            case 'K':
                if(pos[col-WHITE] > 0) return -1;   /* two kings illegal */
                Piece = KING;
                nr = col-WHITE;
                if(0x20*row == 7*(col-WHITE) && file == 4) cc = (col|col>>2|col>>4);

                break;
            case 'R': Piece--;
                if(0x20*row == 7*(col-WHITE))
                {    /* only Rooks on a1, h1, a8, h8 get castling spoiler */
                     if(file == 0) cc = col>>2;
                     if(file == 7) cc = col>>4;
                }
            case 'Q': Piece += 2;
            case 'B': 
                if(--FirstSlider[col] <= LastKnight[col]) return(-2);
                nr = FirstSlider[col];
                break;
            case 'P': 
                if(--FirstPawn[col] < col-WHITE+16) return(-4);
                nr = FirstPawn[col];
                Piece = col>>5;
                break;
            case 'N': 
                if(FirstSlider[col] <= ++LastKnight[col]) return(-3);
                nr = LastKnight[col];
                Piece = KNIGHT;
                break;
            default: return -15;
            }
            pos[nr] = ((file +  16*row) & 0x77) + 0x22;
            kind[nr] = Piece;
            code[nr] = capts[Piece];
            Zob[nr]  = Keys + 128*Piece + (col&BLACK)/8 - 0x22;
            cstl[nr] = cc;
            CasRights |= cc;       /* remember K & R on original location */
            file++;

          }
        } while(file < 8);
        if(file >  8) return -11;
        if(file == 8)
        {   c = *p++;
            if(row > 0 && c != '/') return(-10); /* bad format */
            if(row==0  && c != ' ') return -11;
        }
    }
    if(pos[0] == 0 || pos[WHITE] == 0) return -5; /* missing king */

    /* now do castle rights and side to move */
    cstl[DUMMY-WHITE]=0;
    cc = 0;
    while(c = *p++)
    {
        if(c>='0' && c<='9') continue; /* ignore move counts */
        if(c>='a' && c<='h') /* might be e.p. square */
        {    if(*p == '3' || *p == '6')
             {
                 epSqr = 0x22 + (*p - '1')*16 + (c - 'a'); 
                 p++;
                 continue;
             } else if(c != 'b') continue;
        }
        switch(c)
        {
        case 'K': cc |= 0x22; break;
        case 'Q': cc |= 0x28; break;
        case 'k': cc |= 0x44; break;
        case 'q': cc |= 0x50; break;
        case 'w': col = WHITE; break;
        case 'b': col = BLACK; break;
        case ' ':
        case '-': break;
        default: return -12;
        }
    }
    CasRights = (cc & CasRights) ^ 0x7E;
    return col;
}

#endif


void move_gen(int color, int lastply, int d)
{
    int i, j, k, p, v, x, z, y, r, m, h;
    int savsp, mask, new, forward, rank, prank, xcolor, ep_flag;
    int in_check=0, checker= -1, check_dir = 20;
    int pstack[12], ppos[12], psp=0, first_move=msp;

    /* Some general preparation */
        k = pos[color-WHITE];           /* position of my King */
        forward = 48- color;            /* forward step */
        rank = 0x58 - (forward>>1);     /* 4th/5th rank */
        prank = 0xD0 - 5*(color>>1);    /* 2nd/7th rank */
        ep_flag = lastply>>24&0xFF;
        ep1 = ep2 = msp; Promo = 0;

    /* Pintest, starting from possible pinners in enemy slider list   */
    /* if aiming at King & 1 piece of us in between, park this piece  */
    /* on pin stack for rest of move generation, after generating its */
    /* moves along the pin line.                                      */
        for(p=FirstSlider[COLOR-color]; p<COLOR-WHITE+16-color; p++)
        {   /* run through enemy slider list */
            j = pos[p]; /* enemy slider */
            if(j==0) continue;  /* currently captured */
            if(capt_code[j-k]&code[p]&C_DISTANT)
            {   /* slider aimed at our king */
                v = delta_vec[j-k];
                x = k;     /* trace ray from our King */
                while((m=board[x+=v]) == DUMMY);
                if(x==j)
                {   /* distant check detected         */
                    in_check += 2;
                    checker = j;
                    check_dir = v;
                } else
                if(m&color)
                {   /* first on ray from King is ours */
                    y = x;
                    while(board[y+=v] == DUMMY);
                    if(y==j)
                    {   /* our piece at x is pinned!  */
                        /* remove from piece list     */
                        /* and put on pin stack       */
                        m -= WHITE;
                        ppos[psp] = pos[m];
                        pos[m] = 0;
                        pstack[psp++] = m;
                        z = x<<8;

                        if(kind[m]<3)
                        {   /* flag promotions */
                            if(!((prank^x)&0xF0)) z |= 0xA1000000;
                            y = x + forward; 
                            if(!(v&7)) /* Pawn along file */
                            {   /* generate non-captures  */
                                if(!(board[y]&COLOR))
                                {   PUSH(z,y)
                                    y += forward;Promo++;
                                    if(!(board[y]&COLOR | (rank^y)&0xF0))
                                        PUSH(z,y|y<<24)
                                }
                            } else
                            {   /* diagonal pin       */
                                /* try capture pinner */
                                if(y+1==j) { Promo++; PUSH(z,y+1) }
                                if(y-1==j) { Promo++; PUSH(z,y-1) }
                            }
                        } else
                        if(code[m]&capt_code[j-k]&C_DISTANT)
                        {   /* slider moves along pin ray */
                            y = x;
                            do{ /* moves upto capt. pinner*/
                                y += v;
                                PUSH(z,y)
                            } while(y != j);
                            y = x;
                            while((y-=v) != k)
                            {   /* moves towards King     */
                                PUSH(z,y)
                            }
                        }
                    }
                }
            }
        }

        /* all pinned pieces are now removed from lists */
        /* all their remaining legal moves are generated*/
        /* all distant checks are detected              */

    /* determine if opponent's move put us in contact check */
        y = lastply&0xFF;
        if(capt_code[k-y] & code[board[y]-WHITE] & C_CONTACT)
        {   checker = y; in_check++;
            check_dir = delta_vec[checker-k];
        }

    /* determine how to proceed based on check situation    */
        if(in_check)
        {   /* purge moves with pinned pieces if in check   */
            msp = first_move;

            if(in_check > 2) goto King_Moves; /* double check */
            if(checker == ep_flag) { ep1 = msp; goto ep_Captures; }
            goto Regular_Moves;
        }
    /* generate castlings */
        ep1 = msp;
        if(!(color&CasRights))
        {
            if(!(board[k+1]^DUMMY|board[k+2]^DUMMY|
                 CasRights&color>>4))
                PUSH(k<<8,k+2+0xB0000000+0x3000000)
            if(!(board[k-1]^DUMMY|board[k-2]^DUMMY|board[k-3]^DUMMY|
                 CasRights&color>>2))
                PUSH(k<<8,k-2+0xB0000000-0x4000000)
        }

    /* generate e.p. captures (at most two)                  */
    /* branches are almost always take, e.p. capture is rare */
    ep_Captures:
        mask = color | PAWNS;

        x = ep_flag+1;
        if((board[x]&mask)==mask) PUSH(x<<8,ep_flag^0x10|0xA0000000);

        x = ep_flag-1;
        if((board[x]&mask)==mask) PUSH(x<<8,ep_flag^0x10|0xA0000000);
        ep2 = msp;

    /* On contact check only King retreat or capture helps   */
    /* Use in that case specialized recapture generator      */
    Regular_Moves:
      if(in_check & 1)
      {
        xcolor = color^COLOR;
        /* check for pawns, through 2 squares on board */
        m = color | PAWNS;
        z = x = checker; y = x - forward;
        
        if(!((prank^y)&0xF0)) Promo++,z |= 0xA1000000;
        if((board[y+1]&m)==m && pos[board[y+1]-WHITE]) PUSH(y+1<<8,z)
        if((board[y-1]&m)==m && pos[board[y-1]-WHITE]) PUSH(y-1<<8,z)

        for(p=LastKnight[color]; p>color-WHITE; p--)
        {
            k = pos[p];
            if(k==0) continue;
            m = code[p];
            i = capt_code[k-x];
            if(i&m) PUSH(k<<8,x)
        }

        for(p=color-WHITE+15; p>=FirstSlider[color]; p--)
        {
            k = pos[p];
            if(k==0) continue;
            m = code[p];
            i = capt_code[k-x];
            if(i&m)
            {
                v = delta_vec[k-x];
                y = x;
                while(board[y+=v]==DUMMY);
                if(y==k) PUSH(k<<8,x)
            }
        }

      } else
    /* Basic move generator for generating all moves */
      {
        /* First do pawns, from pawn list hanging from list head    */

        mask = color|0x80;  /* matches own color, empty square, or guard  */

        for(p=FirstPawn[color]; p<color-WHITE+PAWNS+8; p++)
        {
            x = pos[p]; z = x<<8;
            if(x==0) continue;

            /* flag promotions */
            if(!((prank^x)&0xF0)) Promo++,z |= 0xA1000000;

            /* capture moves */
            y = x + forward;
            if(!(board[y-1]&mask)) PUSH(z,y-1)
            if(!(board[y+1]&mask)) PUSH(z,y+1)
            
            /* non-capture moves */
            if(!(board[y]&COLOR))
            {   PUSH(z,y)
                y += forward;
                if(!(board[y]&COLOR | (rank^y)&0xF0))
                    PUSH(z,y|y<<24)        /* e.p. flag */
            }
        }

        /* Next do Knights */

        for(p=LastKnight[color]; p>color-WHITE; p--)
        {
            x = pos[p]; z = x<<8;
            if(x==0) continue;

            /* always 8 direction, unroll loop to avoid branches */
            if(!(board[x+14]&color)) PUSH(z,x+14)
            if(!(board[x+31]&color)) PUSH(z,x+31)
            if(!(board[x+33]&color)) PUSH(z,x+33)
            if(!(board[x+18]&color)) PUSH(z,x+18)
            if(!(board[x-14]&color)) PUSH(z,x-14)
            if(!(board[x-31]&color)) PUSH(z,x-31)
            if(!(board[x-33]&color)) PUSH(z,x-33)
            if(!(board[x-18]&color)) PUSH(z,x-18)
        }

        /* now do sliding pieces */
        /* for each ray, do ray scan, and goto next ray when blocked */

        for(p=color-WHITE+15; p>=FirstSlider[color]; p--)
        {   
          x = pos[p]; z = x<<8;
          if(x==0) continue;

          if(kind[p]-3&2)
          { /* scan 4 rook rays for R and Q */
            y = x;
            do{ if(!((h=board[y+=1 ])&color)) PUSH(z,y) } while(!(h&COLOR));
            y = x;
            do{ if(!((h=board[y-=1 ])&color)) PUSH(z,y) } while(!(h&COLOR));
            y = x;
            do{ if(!((h=board[y+=16])&color)) PUSH(z,y) } while(!(h&COLOR));
            y = x;
            do{ if(!((h=board[y-=16])&color)) PUSH(z,y) } while(!(h&COLOR));
          }
          if(kind[p]-3&1)
          { /* scan 4 bishop rays for B and Q */
            y = x;
            do{ if(!((h=board[y+=15])&color)) PUSH(z,y) } while(!(h&COLOR));
            y = x;
            do{ if(!((h=board[y-=15])&color)) PUSH(z,y) } while(!(h&COLOR));
            y = x;
            do{ if(!((h=board[y+=17])&color)) PUSH(z,y) } while(!(h&COLOR));
            y = x;
            do{ if(!((h=board[y-=17])&color)) PUSH(z,y) } while(!(h&COLOR));
          }
        }

    /* remove moves that don't solve distant check by          */
    /* capturing checker or interposing on check ray           */
        if(in_check)
        for(i=first_move; i<msp; i++)  /* go through all moves */
        {
            if(delta_vec[(j=stack[i]&0xFF)-k] != check_dir)
                stack[i--] = stack[--msp];
            else
            {   /* on check ray, could block or capture checker*/
                x = k;
                do{
                    x += check_dir;
                    if(x==j) break;
                } while(x != checker);
               if(x!=j) {  stack[i--] = stack[--msp]; }
            }
        }
      }

    /* Generate moves with the always present King */
    King_Moves:
        x = pos[color-WHITE]; z = x<<8;
        Kmoves = msp;

        /* always 8 direction, unroll loop to avoid branches */
        if(!(board[x+1 ]&color)) PUSH(z,x+1)
        if(!(board[x+17]&color)) PUSH(z,x+17)
        if(!(board[x+16]&color)) PUSH(z,x+16)
        if(!(board[x+15]&color)) PUSH(z,x+15)
        if(!(board[x-1 ]&color)) PUSH(z,x-1)
        if(!(board[x-17]&color)) PUSH(z,x-17)
        if(!(board[x-16]&color)) PUSH(z,x-16)
        if(!(board[x-15]&color)) PUSH(z,x-15)

    /* Put pieces that were parked onto pin stack back in lists */
       while(psp>0)
        {   /* pop pinned piece and link in old place it remembers*/
            m = pstack[--psp];
            pos[m] = ppos[psp];
        }

}

#if 1
int move_count(int color, int lastply, int d)
{
    int i, j, k, p, v, x, z, y, r, m, h;
    int savsp, mask, new, forward, rank, prank, xcolor, ep_flag;
    int in_check=0, checker= -1, check_dir = 20;
    int pstack[12], ppos[12], psp=0, first_move=msp, myCount=0;

    /* Some general preparation */
        k = pos[color-WHITE];           /* position of my King */
        forward = 48- color;            /* forward step */
        rank = 0x58 - (forward>>1);     /* 4th/5th rank */
        prank = 0xD0 - 5*(color>>1);    /* 2nd/7th rank */
        ep_flag = lastply>>24&0xFF;

    /* Pintest, starting from possible pinners in enemy slider list   */
    /* if aiming at King & 1 piece of us in between, park this piece  */
    /* on pin stack for rest of move generation, after generating its */
    /* moves along the pin line.                                      */
        for(p=FirstSlider[COLOR-color]; p<COLOR-WHITE+16-color; p++)
        {   /* run through enemy slider list */
            j = pos[p]; /* enemy slider */
            if(j==0) continue;  /* currently captured */
            if(capt_code[j-k]&code[p]&C_DISTANT)
            {   /* slider aimed at our king */
                v = delta_vec[j-k];
                x = k;     /* trace ray from our King */
                while((m=board[x+=v]) == DUMMY);
                if(x==j)
                {   /* distant check detected         */
                    in_check += 2;
                    checker = j;
                    check_dir = v;
                } else
                if(m&color)
                {   /* first on ray from King is ours */
                    y = x;
                    while(board[y+=v] == DUMMY);
                    if(y==j)
                    {   /* our piece at x is pinned!  */
                        /* remove from piece list     */
                        /* and put on pin stack       */
                        m -= WHITE;
                        ppos[psp] = pos[m];
                        pos[m] = 0;
                        pstack[psp++] = m;
                        z = x<<8;

                        if(kind[m]<3)
                        {   /* flag promotions */
                           if(!((prank^x)&0xF0)) {
			      z |= 0xA1000000;
                              y = x + forward; 
                              if(!(v&7)) /* Pawn along file */
                              { /* generate non-captures  */
                                if(!(board[y]&COLOR))
                                {   PUSH(z,y)
                                    y += forward;
                                    if(!(board[y]&COLOR | (rank^y)&0xF0))
                                        PUSH(z,y)
                                }
                              } else
                              { /* diagonal pin       */
                                /* try capture pinner */
                                if(y+1==j) PUSH(z,y+1)
                                if(y-1==j) PUSH(z,y-1)
                              }
                           } else {
                              y = x + forward; 
                              if(!(v&7)) /* Pawn along file */
                              { /* generate non-captures  */
                                if(!(board[y]&COLOR))
                                {   myCount++;
                                    y += forward;
                                    myCount += !(board[y]&COLOR | (rank^y)&0xF0);
                                }
                              } else
                              { /* diagonal pin       */
                                /* try capture pinner */
                                myCount += (y+1==j);
                                myCount += (y-1==j);
                              }
                           }
                        } else
                        if(code[m]&capt_code[j-k]&C_DISTANT)
                        {   /* slider moves along pin ray */
                            y = x;
                            do{ /* moves upto capt. pinner*/
                                y += v;
                                myCount++;
                            } while(y != j);
                            y = x;
                            while((y-=v) != k)
                            {   /* moves towards King     */
                                myCount++;
                            }
                        }
                    }
                }
            }
        }

        /* all pinned pieces are now removed from lists */
        /* all their remaining legal moves are generated*/
        /* all distant checks are detected              */

    /* determine if opponent's move put us in contact check */
        y = lastply&0xFF;
        if(capt_code[k-y] & code[board[y]-WHITE] & C_CONTACT)
        {   checker = y; in_check++;
            check_dir = delta_vec[checker-k];
        }

    /* determine how to proceed based on check situation    */
        if(in_check)
        {   /* purge moves with pinned pieces if in check   */
            msp = first_move; myCount = 0;

            if(in_check > 2) goto King_Moves2; /* double check */
            if(checker == ep_flag) goto ep_Captures_in_Check;
            goto Regular_Moves_in_Check;
        }
    /* generate castlings */
        if(!(color&CasRights))
        {
            if(!(board[k+1]^DUMMY|board[k+2]^DUMMY|
                 CasRights&color>>4))
                PUSH(k<<8,k+2+0xB0000000+0x3000000)
            if(!(board[k-1]^DUMMY|board[k-2]^DUMMY|board[k-3]^DUMMY|
                 CasRights&color>>2))
                PUSH(k<<8,k-2+0xB0000000-0x4000000)
        }

    /* generate e.p. captures (at most two)                  */
    /* branches are almost always take, e.p. capture is rare */
    ep_Captures2:
        mask = color | PAWNS;

        x = ep_flag+1;
        if((board[x]&mask)==mask) PUSH(x<<8,ep_flag^0x10|0xA0000000);

        x = ep_flag-1;
        if((board[x]&mask)==mask) PUSH(x<<8,ep_flag^0x10|0xA0000000);
        ep2 = msp;

    /* On contact check only King retreat or capture helps   */
    /* Use in that case specialized recapture generator      */
    Regular_Moves2:
    /* Basic move generator for generating all moves */
      {
        /* First do pawns, from pawn list hanging from list head    */

        mask = color|0x80;  /* matches own color, empty square, or guard  */

        for(p=FirstPawn[color]; p<color-WHITE+PAWNS+8; p++)
        {
          x = pos[p]; z = x<<8;
          if(x==0) continue;

            /* flag promotions */
          if(!((prank^x)&0xF0)) {
            z |= 0xA1000000;

            /* capture moves */
            y = x + forward;
            if(!(board[y-1]&mask)) PUSH(z,y-1)
            if(!(board[y+1]&mask)) PUSH(z,y+1)
            
            /* non-capture moves (no double-push if promotion!) */
            if(!(board[y]&COLOR)) PUSH(z,y)
          } else {
            /* capture moves */
            y = x + forward;
            myCount += !(board[y-1]&mask);
            myCount += !(board[y+1]&mask);
            
            /* non-capture moves */
            if(!(board[y]&COLOR))
            {   myCount++;
                y += forward;
                myCount += !(board[y]&COLOR | (rank^y)&0xF0);
            }
          }
        }

        /* Next do Knights */

        for(p=LastKnight[color]; p>color-WHITE; p--)
        {
            x = pos[p]; z = x<<8;
            if(x==0) continue;

            /* always 8 direction, unroll loop to avoid branches */
            myCount += !(board[x+14]&color);
            myCount += !(board[x+31]&color);
            myCount += !(board[x+33]&color);
            myCount += !(board[x+18]&color);
            myCount += !(board[x-14]&color);
            myCount += !(board[x-31]&color);
            myCount += !(board[x-33]&color);
            myCount += !(board[x-18]&color);
        }

        /* now do sliding pieces */
        /* for each ray, do ray scan, and goto next ray when blocked */

        for(p=color-WHITE+15; p>=FirstSlider[color]; p--)
        {   
          x = pos[p]; z = x<<8;
          if(x==0) continue;

          if(kind[p]-3&2)
          { /* scan 4 rook rays for R and Q */
            register int h, y;
            y = x; while((h=board[y+=1 ]) == DUMMY) myCount++; myCount += !(board[y]&color);
            y = x; while((h=board[y-=1 ]) == DUMMY) myCount++; myCount += !(board[y]&color);
            y = x; while((h=board[y+=16]) == DUMMY) myCount++; myCount += !(board[y]&color);
            y = x; while((h=board[y-=16]) == DUMMY) myCount++; myCount += !(board[y]&color);
          }
          if(kind[p]-3&1)
          { /* scan 4 bishop rays for B and Q */
            register int h, y;
            y = x; while((h=board[y+=15]) == DUMMY) myCount++; myCount += !(board[y]&color);
            y = x; while((h=board[y-=15]) == DUMMY) myCount++; myCount += !(board[y]&color);
            y = x; while((h=board[y+=17]) == DUMMY) myCount++; myCount += !(board[y]&color);
            y = x; while((h=board[y-=17]) == DUMMY) myCount++; myCount += !(board[y]&color);
          }
        }
      }
      goto King_Moves2;

    /* generate e.p. captures (at most two)                  */
    /* branches are almost always take, e.p. capture is rare */
    ep_Captures_in_Check:
        mask = color | PAWNS;

        x = ep_flag+1;
        if((board[x]&mask)==mask) PUSH(x<<8,ep_flag^0x10|0xA0000000);

        x = ep_flag-1;
        if((board[x]&mask)==mask) PUSH(x<<8,ep_flag^0x10|0xA0000000);

    /* On contact check only King retreat or capture helps   */
    /* Use in that case specialized recapture generator      */
    Regular_Moves_in_Check:
      if(in_check & 1)
      {
        xcolor = color^COLOR;
        /* check for pawns, through 2 squares on board */
        m = color | PAWNS;
        z = x = checker; y = x - forward;
        
        if(!((prank^y)&0xF0)) {
          z |= 0xA1000000;
          if((board[y+1]&m)==m && pos[board[y+1]-WHITE]) PUSH(y+1<<8,z)
          if((board[y-1]&m)==m && pos[board[y-1]-WHITE]) PUSH(y-1<<8,z)
        } else {
          myCount += (board[y+1]&m)==m && pos[board[y+1]-WHITE];
          myCount += (board[y-1]&m)==m && pos[board[y-1]-WHITE];
        }

        for(p=LastKnight[color]; p>color-WHITE; p--)
        {
            k = pos[p];
            if(k==0) continue;
            m = code[p];
            i = capt_code[k-x];
            myCount += (i&m) != 0;
        }

        for(p=color-WHITE+15; p>=FirstSlider[color]; p--)
        {
            k = pos[p];
            if(k==0) continue;
            m = code[p];
            i = capt_code[k-x];
            if(i&m)
            {
                v = delta_vec[k-x];
                y = x;
                while(board[y+=v]==DUMMY);
                myCount += (y==k);
            }
        }

      } else
    /* Basic move generator for generating all moves */
      {
        /* First do pawns, from pawn list hanging from list head    */

        mask = color|0x80;  /* matches own color, empty square, or guard  */

        for(p=FirstPawn[color]; p<color-WHITE+PAWNS+8; p++)
        {
            x = pos[p]; z = x<<8;
            if(x==0) continue;

            /* flag promotions */
            if(!((prank^x)&0xF0)) Promo++,z |= 0xA1000000;

            /* capture moves */
            y = x + forward;
            if(!(board[y-1]&mask)) PUSH(z,y-1)
            if(!(board[y+1]&mask)) PUSH(z,y+1)
            
            /* non-capture moves */
            if(!(board[y]&COLOR))
            {   PUSH(z,y)
                y += forward;
                if(!(board[y]&COLOR | (rank^y)&0xF0))
                    PUSH(z,y)        /* forget e.p. flag */
            }
        }

        /* Next do Knights */

        for(p=LastKnight[color]; p>color-WHITE; p--)
        {
            x = pos[p]; z = x<<8;
            if(x==0) continue;

            /* always 8 direction, unroll loop to avoid branches */
            if(!(board[x+14]&color)) PUSH(z,x+14)
            if(!(board[x+31]&color)) PUSH(z,x+31)
            if(!(board[x+33]&color)) PUSH(z,x+33)
            if(!(board[x+18]&color)) PUSH(z,x+18)
            if(!(board[x-14]&color)) PUSH(z,x-14)
            if(!(board[x-31]&color)) PUSH(z,x-31)
            if(!(board[x-33]&color)) PUSH(z,x-33)
            if(!(board[x-18]&color)) PUSH(z,x-18)
        }

        /* now do sliding pieces */
        /* for each ray, do ray scan, and goto next ray when blocked */

        for(p=color-WHITE+15; p>=FirstSlider[color]; p--)
        {   
          x = pos[p]; z = x<<8;
          if(x==0) continue;

          if(kind[p]-3&2)
          { /* scan 4 rook rays for R and Q */
            y = x;
            do{ if(!((h=board[y+=1 ])&color)) PUSH(z,y) } while(!(h&COLOR));
            y = x;
            do{ if(!((h=board[y-=1 ])&color)) PUSH(z,y) } while(!(h&COLOR));
            y = x;
            do{ if(!((h=board[y+=16])&color)) PUSH(z,y) } while(!(h&COLOR));
            y = x;
            do{ if(!((h=board[y-=16])&color)) PUSH(z,y) } while(!(h&COLOR));
          }
          if(kind[p]-3&1)
          { /* scan 4 bishop rays for B and Q */
            y = x;
            do{ if(!((h=board[y+=15])&color)) PUSH(z,y) } while(!(h&COLOR));
            y = x;
            do{ if(!((h=board[y-=15])&color)) PUSH(z,y) } while(!(h&COLOR));
            y = x;
            do{ if(!((h=board[y+=17])&color)) PUSH(z,y) } while(!(h&COLOR));
            y = x;
            do{ if(!((h=board[y-=17])&color)) PUSH(z,y) } while(!(h&COLOR));
          }
        }

    /* remove moves that don't solve distant check by          */
    /* capturing checker or interposing on check ray           */
        if(in_check)
        for(i=first_move; i<msp; i++)  /* go through all moves */
        {
            if(delta_vec[(j=stack[i]&0xFF)-k] != check_dir)
                stack[i--] = stack[--msp];
            else
            {   /* on check ray, could block or capture checker*/
                x = k;
                do{
                    x += check_dir;
                    if(x==j) break;
                } while(x != checker);
               if(x!=j) {  stack[i--] = stack[--msp]; }
            }
        }
      }

    /* Generate moves with the always present King */
    King_Moves2:
        x = pos[color-WHITE]; z = x<<8;
        Kmoves = msp;

        /* always 8 direction, unroll loop to avoid branches */
        if(!(board[x+1 ]&color)) PUSH(z,x+1)
        if(!(board[x+17]&color)) PUSH(z,x+17)
        if(!(board[x+16]&color)) PUSH(z,x+16)
        if(!(board[x+15]&color)) PUSH(z,x+15)
        if(!(board[x-1 ]&color)) PUSH(z,x-1)
        if(!(board[x-17]&color)) PUSH(z,x-17)
        if(!(board[x-16]&color)) PUSH(z,x-16)
        if(!(board[x-15]&color)) PUSH(z,x-15)

    /* Put pieces that were parked onto pin stack back in lists */
       while(psp>0)
        {   /* pop pinned piece and link in old place it remembers*/
            m = pstack[--psp];
            pos[m] = ppos[psp];
        }
      return myCount;
}
#endif

int capturable(int color, int x)
{   /* do full check for captures on square x by all opponen't pieces */
    int i, j, k, v, y, m, p;

    /* check for pawns, through 2 squares on board */
    v = color - 48; m = color | PAWNS;
    if((board[x+v+1]&m)==m) return 1; 
    if((board[x+v-1]&m)==m) return 2;

    for(p=LastKnight[color]; p>=color-WHITE; p--)
    {
        k = pos[p];
        if(k==0) continue;
        m = code[p];
        i = capt_code[k-x];
        if(i&m) return p+256;
    }

    for(p=color-WHITE+15; p>=FirstSlider[color]; p--)
    {
        k = pos[p];
        if(k==0) continue;
        m = code[p];
        i = capt_code[k-x];
        if(i&m)
        {
            v = delta_vec[k-x];
            y = x;
            while(board[y+=v]==DUMMY);
            if(y==k) return p+512;
        }
    }

    return 0;
}

void leaf_perft(int color, int lastply, int depth, int d)
{   /* recursive perft, with in-lined make/unmake */
    int i, j, k, m, x, y, v, h, p, oldpiece, store, myCount;
    int first_move, piece, victim, pred, succ, from, to, capt, mode,
        pcnr, vicnr, in_check=0, checker= -1, check_dir = 20, legal;
    int SavRights = CasRights, lep1, lep2, lkm, flag;
    unsigned long long int ocnt=count, SavCnt;
    union _bucket *Bucket;

    TIME(17)
    first_move = msp; /* new area on move stack */
    legal = 0;
    count += move_count(color, lastply, d); /* bulk count, but generate moves that need legality checking */

    for(i = first_move; i<msp; i++)  /* go through all moves */
    {
      /* fetch move from move stack */
        from = (stack[i]>>8)&0xFF;
        to = capt = stack[i]&0xFF;
        mode = (unsigned int)stack[i]>>24;
        piece  = board[from];

        if(mode)
        {   /* e.p. or castling, usually skipped  */
            /* e.p.:shift capture square one rank */
            if(mode == 0xA0) capt ^= 0x10; else
            if(mode == 0xA1)
            {   /* Promotion. Shuffle piece list :( */
                oldpiece = piece; pos[piece-WHITE]=0;
                /* set up for new Queen first */
                piece = --FirstSlider[color]+WHITE;
                kind[piece-WHITE] = QUEEN;
                code[piece-WHITE] = C_QUEEN;
                Zob[piece-WHITE]  = Keys + 128*QUEEN + (color&BLACK)/8 - 0x22;
                pos[piece-WHITE]  = from;
            }else
            {   /* castling, determine Rook move  */
                j = mode - 0xB0 + from;
                h = from+to >> 1;
                /* abort if Rook in check         */
                if(capturable(color^COLOR, h)) continue;
                /* move Rook                      */
                board[h] = board[j];
                board[j] = DUMMY;
                pos[board[h]-WHITE] = h;
            }
        }

        victim = board[capt];
        CasRights |= cstl[piece-WHITE] | cstl[victim-WHITE];

minor:
      /* perform move, in piece list and on board */
        /* update board position */
        board[capt] = board[from] = DUMMY;
        board[to] = piece;

        /* update piece location in piece list    */
        pos[piece-WHITE] = to;


        /* remove captured piece from piece list  */
        pos[victim-WHITE] = 0;

        count += !capturable(color^COLOR, pos[color-WHITE]);
      /* retract move */

        /* restore piece list */
        pos[piece-WHITE] = from;
        pos[victim-WHITE] = capt;

        /* restore board */
        board[to] = DUMMY;      /* restore board  */
        board[capt] = victim;
        board[from] = piece;

        if((unsigned int) stack[i]>=0xA1000000)   /* was castling or prom */
        {   if(mode==0xA1)
            {
                if(noUnder) {
                    FirstSlider[color]++;
                    piece =oldpiece;
                    pos[piece-WHITE] = from;
                    board[from] = piece;
                } else
                if(--kind[piece-WHITE] >= KNIGHT)
                {
                    if(kind[piece-WHITE] == KNIGHT)
                    {   /* Knight must be put in Knight list */
                        FirstSlider[color]++;
                        piece = ++LastKnight[color]+WHITE;
                        pos[piece-WHITE]  = from;
                        kind[piece-WHITE] = KNIGHT;
                        Zob[piece-WHITE]  = Keys + 128*KNIGHT
                                                 + (color&BLACK)/8 - 0x22;
                    } else Zob[piece-WHITE] -= 128;
                    code[piece-WHITE] = capts[kind[piece-WHITE]];
                    goto minor; /* try minor promotion */
                } else
                {   /* All promotions tried, demote to Pawn again */
                    kind[piece-WHITE] = QUEEN; /* put Q back for hash store */
                    piece = oldpiece; LastKnight[color]--;
                    pos[piece-WHITE] = from;
                    board[from] = piece;
                }
            } else
            {   /* undo Rook move */
                board[j] = board[h];
                board[h] = DUMMY;
                pos[board[j]-WHITE] = j;
            }
        }

        CasRights = SavRights;

    }

    msp = first_move; /* throw away moves */
}

void perft(int color, int lastply, int depth, int d)
{   /* recursive perft, with in-lined make/unmake */
    int i, j, k, m, x, y, v, h, p, oldpiece, store;
    int first_move, piece, victim, pred, succ, from, to, capt, mode,
        pcnr, vicnr, in_check=0, checker= -1, check_dir = 20, legal;
    int SavRights = CasRights, lep1, lep2, lkm, flag, Index;
    unsigned long long int ocnt=count, OldKey = HashKey, OldHKey = HighKey, SavCnt;
    union _bucket *Bucket;

    TIME(17)
    first_move = msp; /* new area on move stack */
    legal = 0;
    move_gen(color, lastply, d); /* generate moves */
    nodecount++;
    lep1 = ep1; lep2 = ep2; lkm = Kmoves; flag = depth == 1 && !Promo;

    if(flag)
        count += Kmoves - first_move - ep2 + ep1; /* bulk count */

    for(i = flag ? ep1 : first_move; i<msp; i++)  /* go through all moves */
    {
        if(i == lep2 & flag) { i = lkm; if(i >= msp) break; }

      /* fetch move from move stack */
        from = (stack[i]>>8)&0xFF;
        to = capt = stack[i]&0xFF;
        mode = (unsigned int)stack[i]>>24;
path[d] = stack[i];
        piece  = board[from];

        Index = 0;
        if(mode)
        {   /* e.p. or castling, usually skipped  */
            /* e.p.:shift capture square one rank */
            if(mode < 0xA0)
            {   if(((board[to+1]^piece) & (COLOR|PAWNS)) == COLOR ||
                   ((board[to-1]^piece) & (COLOR|PAWNS)) == COLOR)
                    Index = mode * 76265;
            } else
            if(mode == 0xA0) capt ^= 0x10; else
            if(mode == 0xA1)
            {   /* Promotion. Shuffle piece list :( */
                oldpiece = piece; pos[piece-WHITE]=0;
                /* set up for new Queen first */
                piece = --FirstSlider[color]+WHITE;
                kind[piece-WHITE] = QUEEN;
                code[piece-WHITE] = C_QUEEN;
                Zob[piece-WHITE]  = Keys + 128*QUEEN + (color&BLACK)/8 - 0x22;
                pos[piece-WHITE]  = from;
                HashKey ^= Zobrist(piece, from) ^ Zobrist(oldpiece, from);
                HighKey ^= Zobrist(piece, from+8) ^ Zobrist(oldpiece, from+8);
                Index += 14457159; /* prevent hits by non-promotion moves */
            }else
            {   /* castling, determine Rook move  */
                j = mode - 0xB0 + from;
                h = from+to >> 1;
                /* abort if Rook in check         */
                if(capturable(color^COLOR, h)) continue;
                /* move Rook                      */
                board[h] = board[j];
                board[j] = DUMMY;
                pos[board[h]-WHITE] = h;
                HashKey ^= Zobrist(board[h],h) ^ Zobrist(board[h],j);
                HighKey ^= Zobrist(board[h],h+8) ^ Zobrist(board[h],j+8);
            }
        }

        victim = board[capt];
        CasRights |= cstl[piece-WHITE] | cstl[victim-WHITE];

        if(depth==1)
        {   if(piece != color && mode < 0xA0)
            {   count++; goto quick; }
        } else if(HashFlag)
        {
            SavCnt = count;
            HashKey ^= Zobrist(piece,from)  /* key update for normal move */
                     ^ Zobrist(piece,to)
                     ^ Zobrist(victim,capt);
            HighKey ^= Zobrist(piece,from+8)  /* key update for normal move */
                     ^ Zobrist(piece,to+8)
                     ^ Zobrist(victim,capt+8);
            Index += (CasRights << 4) +color*919581;
            if(depth>2) {
              path[d] = stack[i];
              if(depth > 7) { // the count will not fit in 32 bits
                 if(depth > 9) {
                   int i = HashSection, j = depth-9;
                   while(j--) i >>= 1;
                   Bucket =      Hash + (Index + ((int) HashKey) & i) + 7 * HashSection + i;
                 } else
                   Bucket =      Hash + (Index + ((int) HashKey) & HashSection) + (depth-3) * HashSection;
                 if(Bucket->l.Signature1 == HighKey && Bucket->l.Signature2 == HashKey)
                 {   count += Bucket->l.longCount; accept[depth]++;
                     goto quick;
                 }
                 reject[depth]++;
                 goto minor;
              }
                   Bucket =      Hash + (Index + ((int) HashKey) & HashSection) + (depth-3) * HashSection;
            } else Bucket = ExtraHash + (Index + ((int) HashKey) & XSIZE-1);

            store = (HashKey>>32) & 1;
            if(Bucket->s.Signature[store] == HighKey && (Bucket->s.Extension[store] ^ (HashKey>>32)) < 2)
             {   count += Bucket->s.Count[store]; accept[depth]++;
                Bucket->s.Extension[store] &= ~1;
                Bucket->s.Extension[store^1] |= 1;
                goto quick;
             }
            if(Bucket->s.Signature[store^1] == HighKey && (Bucket->s.Extension[store^1] ^ (HashKey>>32)) < 2)
            {   count += Bucket->s.Count[store^1]; accept[depth]++;
                Bucket->s.Extension[store^1] &= ~1;
                Bucket->s.Extension[store] |= 1;
                goto quick;
            }
            reject[depth]++; // miss;
            if(Bucket->s.Extension[store^1] & 1) store ^= 1;
        }
minor:
      /* perform move, in piece list and on board */
        /* update board position */
        board[capt] = board[from] = DUMMY;
        board[to] = piece;

        /* update piece location in piece list    */
        pos[piece-WHITE] = to;


        /* remove captured piece from piece list  */
        pos[victim-WHITE] = 0;

        if((piece != color && mode != 0xA0) ||
                 !capturable(color^COLOR, pos[color-WHITE]))
        {
      /* recursion or count end leaf */
                if(depth == 2) leaf_perft(COLOR-color, stack[i], depth-1, d+1);
                else perft(COLOR-color, stack[i], depth-1, d+1);
                if(HashFlag)
                {
                    if(depth > 7) { //large entry
                        Bucket->l.Signature1 = HighKey;
                        Bucket->l.Signature2 = HashKey;
                        Bucket->l.longCount  = count - SavCnt;
                    } else { // packed entry
                        Bucket->s.Signature[store] = HighKey;
                        Bucket->s.Extension[store] = (HashKey>>32) & ~1; // erase low bit
                        Bucket->s.Count[store]     = count - SavCnt;
                    }
                }
        }
      /* retract move */

        /* restore piece list */
        pos[piece-WHITE] = from;
        pos[victim-WHITE] = capt;

        /* restore board */
        board[to] = DUMMY;      /* restore board  */
        board[capt] = victim;
        board[from] = piece;

quick:
        if((unsigned int) stack[i]>=0xA1000000)   /* was castling or prom */
        {   if(mode==0xA1)
            {
                if(noUnder) {
                    FirstSlider[color]++;
                    piece =oldpiece;
                    pos[piece-WHITE] = from;
                    board[from] = piece;
                } else
                if(--kind[piece-WHITE] >= KNIGHT)
                {
                    HashKey ^= Zobrist(piece, to);
                    HighKey ^= Zobrist(piece, to+8);
                    if(kind[piece-WHITE] == KNIGHT)
                    {   /* Knight must be put in Knight list */
                        FirstSlider[color]++;
                        piece = ++LastKnight[color]+WHITE;
                        pos[piece-WHITE]  = from;
                        kind[piece-WHITE] = KNIGHT;
                        Zob[piece-WHITE]  = Keys + 128*KNIGHT
                                                 + (color&BLACK)/8 - 0x22;
                    } else Zob[piece-WHITE] -= 128;
                    code[piece-WHITE] = capts[kind[piece-WHITE]];
                    HashKey ^= Zobrist(piece, to);
                    HighKey ^= Zobrist(piece, to+8);
                    goto minor; /* try minor promotion */
                } else
                {   /* All promotions tried, demote to Pawn again */
                    kind[piece-WHITE] = QUEEN; /* put Q back for hash store */
                    piece = oldpiece; LastKnight[color]--;
                    pos[piece-WHITE] = from;
                    board[from] = piece;
                }
            } else
            {   /* undo Rook move */
                board[j] = board[h];
                board[h] = DUMMY;
                pos[board[j]-WHITE] = j;
            }
        }

        HashKey = OldKey;
        HighKey = OldHKey;
        CasRights = SavRights;

    }

    msp = first_move; /* throw away moves */

    /* For split perft uncomment the following line */
    if(d <= Split && d > 1)
    {
        int i; clock_t t = clock();
        sprintf(buf, "%10lld", count-ocnt);
        printf("%d. ", d);
        fprintf(f, "%d. ", d);
        for(i=1; i<d; i++) {
                   printf("%c%c%c%c ",
                   'a'+(path[i]-0x2222>> 8&7),
                   '1'+(path[i]-0x2222>>12&7),
                   'a'+(path[i]-0x2222    &7),
                   '1'+(path[i]-0x2222>> 4&7) );
                   fprintf(f, "%c%c%c%c ",
                   'a'+(path[i]-0x2222>> 8&7),
                   '1'+(path[i]-0x2222>>12&7),
                   'a'+(path[i]-0x2222    &7),
                   '1'+(path[i]-0x2222>> 4&7) );
        }
        printf("moves = %s (%6.3f sec)\n", buf, (t - ttt[d])*(1./CLOCKS_PER_SEC));
        fprintf(f, "moves = %s (%6.3f sec)\n", buf, (t - ttt[d])*(1./CLOCKS_PER_SEC)); fflush(f);
        ttt[d] = t;
    }
}

char *FEN = "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w QKqk",
     *Fritz = "r3r1k1/1pq2pp1/2p2n2/1PNn4/2QN2b1/6P1/3RPP2/2R3KB b - -";
int Dep = 6;       

int main(int argc, char **argv)
{
    int i, j, k, Col;
    clock_t t;
    double sumx=0, sumx2=0, tot=0;

    if(argc > 1 && !strcmp(argv[1], "-u")) {
	argc--; argv++; noUnder = 1;
    }

    if(argc > 1 && sscanf(argv[1], "%d", &Dep)==1 && Dep > 0)
    {   argc--; argv++; } else
    {   printf("Usage is: perft <depth> [H<hash size>] [-<split depth>] [<FEN string>]\n");
        printf("          <hash size> = 20 gives you 2^20 = 1M entries (16MB)\n");
        exit(0);
    }


    if(argc > 1 && argv[1][0] == 'H' && sscanf(argv[1]+1, "%d", &HashSize) == 1)
    {    HashSection = (1<<HashSize-3) - 1; HashSize = (1<<HashSize) - 2;
         Hash = (union _bucket *) calloc(HashSize+4, sizeof(union _bucket) );
         Hash = (union _bucket *) (((int)Hash) + 63 & ~63);
         printf("Hash-table size = %x, Starts at %x,section = %x\n", HashSize+1, Hash, HashSection);
         HashFlag++;
         for(i=128; i<1040; i++) Keys[i] = rand()>>6;
         argc--; argv++;
    }

    if(argc > 1 && argv[1][0] == '-' && sscanf(argv[1]+1, "%d", &Split) == 1)
    {    argc--; argv++; } else Split = 0;

    if(argc > 1) FEN = argv[1];

    delta_init();

    piece_init();

    board_init(board);

    Col = ReadFEN(FEN);

    setup();
                                          
    pboard(board, 12, 0);

    if(Col < 0)
    { printf("Bad FEN '%s', error code = %d\n", FEN, Col); exit(0); }

    printf("Quick Perft by H.G. Muller\n");
    printf("Perft mode: ");
    if(HashFlag) printf("Hash-table size = %d%cB",
                 (HashSize+2) >> (HashSize<64*1024 ? 6: 16),
                 HashSize<64*1024 ? 'k' : 'M' );
    else         printf("No hashing");
    printf(", bulk counting in horizon nodes\n\n");
    f = fopen("log.txt", "a");
    fprintf(f, "perft %d -%d\n", Dep, Split);

    for(i=1; i<=Dep; i++)
    {
	int n;
        int lastPly = ((epSqr^16)<<24) + checker(Col);
        t = clock();
        count = epcnt = xcnt = ckcnt = cascnt = promcnt = 0;
        for(j=0; j<10; j++) accept[j] = reject[j] = 0, ttt[j] = t;
        if(i == 1) leaf_perft(Col, lastPly, i, 1); else
        perft(Col, lastPly, i, 1);
        t = clock()-t;
        sprintf(buf, "%12lld", count);
        printf("perft(%2d)= %s (%6.3f sec)\n", i, buf, t*(1./CLOCKS_PER_SEC));
    }
    fclose(f);

}

Я чуть подретактиров для задачи неприкосновенный король, чтобы исключить ходы белого короля

21.jpg


22.jpg


Вот что получилось

25.jpg


Значит ход мыслей правильный
BenyaChessBase-long_range_piece.zip

Это всего лишь подготовка инструментов для решения задачи.

Еще важный момент, который необходимо понять - это АльфаБета отсечение
Last Edit: 16 Янв 2023 04:03 by alexlaw.

Bitboard в программировании шахмат №2 14 Янв 2023 14:20 #106

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Жилец
  • Posts: 67
  • Karma: 0
Сегодня наконец то попробовал инструмент оценки скорости расчета атак дальнобойных фигур.
Позицию использовал, как в задаче неприкосновенный король.







Q7/8/2K5/8/8/8/8/7k w - - - 0 1
Т.е. белый король не участвуют в расчетах perft.
Итак за базовый вариант взял расчет атак сдвигом бит в разные стороны.

27.jpg

Метод который я в основном использовал - метод лучей.
Даёт почти на минуту худший показатель.

28.jpg



В обоих случаях идёт расчет минимакс на глубину - 8.
На этой глубине perft=23 414 475.
Ну в общем то ясно, нужно использовать метод вращающихся досок.
Даже самому интересно, насколько вырастет скорость.
Я в этом просто уверен.
Last Edit: 15 Янв 2023 09:40 by alexlaw.

Bitboard в программировании шахмат №2 16 Янв 2023 11:26 #107

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Жилец
  • Posts: 67
  • Karma: 0
Как известно, в русскоязычном сегменте, не так много видео о шахматном программировании.
И не для всех английский родной.
Попадаются интересные ролики.
У меня встал вопрос перевода аудио дорожки на русский язык.
Конечно я его решил, ну и конечно с танцами с бубном.
Кто нибудь задавался этим вопросом?
Если задавался, то какое решение нашел?

Пример перевода
Last Edit: 16 Янв 2023 13:25 by alexlaw.

Bitboard в программировании шахмат №2 16 Янв 2023 11:37 #108

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Жилец
  • Posts: 67
  • Karma: 0
Кстати еще попробовал для задачи неприкосновенный король эмпирическую оценку позиции, но прога не может заматавать без моей помощи(((
чтобы заматавать надо вручную менять глубину перебора.

Случайно добавил exe
Теперь zip из облака
Last Edit: 16 Янв 2023 14:20 by alexlaw.

Bitboard в программировании шахмат №2 17 Янв 2023 07:41 #109

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Жилец
  • Posts: 67
  • Karma: 0
Перевел еще одно видео, только не знаю кому-то это интересно или нет.
В общем то у этого товарища целая серия уроков.
В общем то не плохо объясняет.
Еще у меня вопрос, открывается ли предыдущее видео у вас или нет.
У меня написано - Playback error.
Что скажете о качестве голосового движка, озвучивающий перевод?
В общем то я искал нормальное объяснение вращающихся досок, может быть дальше он об этом расскажет. Незнаю.

Bitboard в программировании шахмат №2 17 Янв 2023 07:42 #110

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 99851
  • Thank you received: 1817
  • Karma: 101
alexlaw wrote:
Еще у меня вопрос, открывается ли предыдущее видео у вас или нет.
У меня написано - Playback error.
Открывается
Каждому - своё.

Bitboard в программировании шахмат №2 17 Янв 2023 07:54 #111

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Жилец
  • Posts: 67
  • Karma: 0
Еще вопрос.
При переводе видео, создается два файла, собственно видео в mp4 и аудио в mp3.
Длительность воспроизведения у них разная, обычно звуковая дорожка немного длиннее.
Чтобы наложить звук на видео, видео нужно немного замедлить.
На вскидку не нашел нормального бесплатного видеоредактора, с возможность замедления видео.
На телефоне у меня есть такой, но гонять туда сюда файлы - не айс.
Что можете посоветовать?

Bitboard в программировании шахмат №2 17 Янв 2023 09:33 #112

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Жилец
  • Posts: 67
  • Karma: 0
Алгоритм перевода видео.
1. Найти видео на YouTube
2. Скачать видео с YouTube - ru.savefrom.net/
3. Скачать субтитры на русском - .srt и английском - .txt - downsub.com/
Отредактировать субтитры
4. Преобразовать субтитры (Кодировка UTF-16LE) в аудиофайл - Balabolka (MP3)(balabolka.site/balabolka.htm)
TTS Milena - cloud.mail.ru/public/t4Aj/3bSjDjeKz (zip)

29.jpg


5. Скорее всего замедлить видео, чтобы время совпадало с аудио.(www.shotcut.org/download/) и
Наложить аудио на видео.(Удалить старую аудио дорожку)

Уроки по программированию шахмат - www.youtube.com/playlist?list=PLmN0neTso...8ZIylk74JpwfiWNI76Cs

Если кто нибудь поучавствует в переводе, было бы замечательно.
Last Edit: 17 Янв 2023 14:25 by alexlaw.

Bitboard в программировании шахмат №2 18 Янв 2023 19:16 #113

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Жилец
  • Posts: 67
  • Karma: 0
Вопрос к модераторам.
Можно ли на этой площадке выкладывать уроки вышеуказанного товарища в переводе на русский язык по алгоритму, который я описал.
Уроки интересные.
Причем начиная с нуля можно написать неплохой движок , ну или по крайне мере понять как это работает.
Может быть кому-то это будет полезно.
Кстати, можно код писать непосредственно на телефоне.
Вот есть компилятор на 4 пда.
Компилятор

Bitboard в программировании шахмат №2 19 Янв 2023 05:55 #114

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 99851
  • Thank you received: 1817
  • Karma: 101
alexlaw wrote:
Можно ли на этой площадке выкладывать уроки вышеуказанного товарища в переводе на русский язык по алгоритму, который я описал.
А что значит выкладывать?

Давать ссылки с свой канал ютюба с переделанным видео? Это сам ютюб, думаю, пресечет быстро и здесь будут черные квадраты.
Заливать непосредственно сюда? Только в виде исключения и в теории, но массово заливать по ряду причин нет.

И если честно, то зачем? Там и так все понятно :)
Каждому - своё.

Bitboard в программировании шахмат №2 20 Янв 2023 11:12 #115

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Жилец
  • Posts: 67
  • Karma: 0
Лучшее, что может быть при изучении материала,это практика.
Поэтому слушая и вникая в уроки maksimKorzh я решил адаптировать практические занятия (написание кода) к среде Делфи.
Урок №2.
program bbc;

{$APPTYPE CONSOLE}

uses
  SysUtils,Windows;
type
    U64 = UInt64;
    TBoard_squares = (
    a8, b8, c8, d8, e8, f8, g8, h8,
    a7, b7, c7, d7, e7, f7, g7, h7,
    a6, b6, c6, d6, e6, f6, g6, h6,
    a5, b5, c5, d5, e5, f5, g5, h5,
    a4, b4, c4, d4, e4, f4, g4, h4,
    a3, b3, c3, d3, e3, f3, g3, h3,
    a2, b2, c2, d2, e2, f2, g2, h2,
    a1, b1, c1, d1, e1, f1, g1, h1
    );
var
 bitboard:U64=0;
//square:TBoard_squares;
// set/get/pop
function get_bit(bb:U64;const sq:integer):integer;
begin
get_bit:=(bb shr sq) and 1;
end;
procedure set_bit(var bb:U64;const sq:TBoard_squares);
begin
bb:=bb or ($8000000000000000 shr (63-Ord(sq)));
end;
procedure pop_bit(var bb:U64;const sq:TBoard_squares);
begin
if get_bit(bb,Ord(sq))>0 then bb:=bb xor ($8000000000000000 shr (63-Ord(sq)));
end;
// print bitboard
procedure print_bitboard(bb:U64);
var
rank_,file_,sq:integer;
begin
Writeln('');
  // loop over board ranks
  for rank_ := 0 to 7 do  begin
        // loop over board files
        for file_ := 0 to 7 do  begin
           // convert file & rank into square index
           sq:=rank_*8 + file_;
           //// print ranks
           if file_ = 0 then begin
           Write(8 - rank_);Write(' ');
           end;
           Write(' ');
           // print bit state (either 1 or 0)
           Write(get_bit(bb,sq));
        end;
        // print new line every rank
        Writeln('');
  end;
  // print new line
  Writeln('');
  // print board files
  Writeln('   a b c d e f g h');
  Writeln('');
  // print bitboard as unsigned decimal number
  Write('bitboard = ',bb);
  Writeln('');
end;
{/**********************************\
 ==================================
 
             Main driver
 
 ==================================
\**********************************/}
 begin
  //Переключение окна консоли на кодовую страницу CP1251 (Win-1251).
  //Если после переключения русские буквы показываются неверно,
  //следует открыть системное меню консольного окна - щелчком мыши в левом
  //верхнем углу окна консоли. И выбрать:
  //Свойства - закладка "Шрифт" - выбрать шрифт: "Lucida Console".
  SetConsoleCP(1251);
  SetConsoleOutputCP(1251);
// ==================================
  bitboard:=$8000000000000000;//$ - шестнадцатеричное представление числа
  print_bitboard(bitboard);
  // setting some bits
  set_bit(bitboard,a4);set_bit(bitboard,b4);
  print_bitboard(bitboard);
  bitboard:=$FFFFFFFFFFFFFFFF;
  print_bitboard(bitboard);
  // reset bit
  pop_bit(bitboard,a4); pop_bit(bitboard,b4);pop_bit(bitboard,c4); pop_bit(bitboard,d4);
  print_bitboard(bitboard);
  Writeln('Нажмите <ENTER>, чтобы выйти ...');
  Readln;
end.

Bitboard в программировании шахмат №2 20 Янв 2023 14:12 #116

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Жилец
  • Posts: 67
  • Karma: 0
Уроки 3 и 4 и 5
Таблица атак пешек,коня и корля
program bbc;

{$APPTYPE CONSOLE}

uses
  SysUtils,Windows;
type
    U64 = UInt64;
    TBoard_squares = (
    a8, b8, c8, d8, e8, f8, g8, h8,
    a7, b7, c7, d7, e7, f7, g7, h7,
    a6, b6, c6, d6, e6, f6, g6, h6,
    a5, b5, c5, d5, e5, f5, g5, h5,
    a4, b4, c4, d4, e4, f4, g4, h4,
    a3, b3, c3, d3, e3, f3, g3, h3,
    a2, b2, c2, d2, e2, f2, g2, h2,
    a1, b1, c1, d1, e1, f1, g1, h1
    );
    TSide = (white, black);
    //Первый индекс обозначает номер строки в матрице, второй индекс – номер столбца
    TPawn_attacks=array[TSide,TBoard_squares] of U64;
    TChip_attacks=array[TBoard_squares] of U64;
var
 bitboard:U64=0;
 // pawn attacks table [side][square]
 pawn_attacks:TPawn_attacks;
 // knight attacks table [square]
 knight_attacks:TChip_attacks;
 // king attacks table [square]
 king_attacks:TChip_attacks;
const
{/*
        not A file
  8  0 1 1 1 1 1 1 1
  7  0 1 1 1 1 1 1 1
  6  0 1 1 1 1 1 1 1
  5  0 1 1 1 1 1 1 1
  4  0 1 1 1 1 1 1 1
  3  0 1 1 1 1 1 1 1
  2  0 1 1 1 1 1 1 1
  1  0 1 1 1 1 1 1 1
     a b c d e f g h
        not H file
  8  1 1 1 1 1 1 1 0
  7  1 1 1 1 1 1 1 0
  6  1 1 1 1 1 1 1 0
  5  1 1 1 1 1 1 1 0
  4  1 1 1 1 1 1 1 0
  3  1 1 1 1 1 1 1 0
  2  1 1 1 1 1 1 1 0
  1  1 1 1 1 1 1 1 0
     a b c d e f g h
       not HG file
  8  1 1 1 1 1 1 0 0
  7  1 1 1 1 1 1 0 0
  6  1 1 1 1 1 1 0 0
  5  1 1 1 1 1 1 0 0
  4  1 1 1 1 1 1 0 0
  3  1 1 1 1 1 1 0 0
  2  1 1 1 1 1 1 0 0
  1  1 1 1 1 1 1 0 0
     a b c d e f g h
       not AB file
  8  0 0 1 1 1 1 1 1
  7  0 0 1 1 1 1 1 1
  6  0 0 1 1 1 1 1 1
  5  0 0 1 1 1 1 1 1
  4  0 0 1 1 1 1 1 1
  3  0 0 1 1 1 1 1 1
  2  0 0 1 1 1 1 1 1
  1  0 0 1 1 1 1 1 1
     a b c d e f g h
*/}

// not A file constant
not_a_file:U64 = $FEFEFEFEFEFEFEFE;//18374403900871474942;
// not H file constant
not_h_file:U64 = $7F7F7F7F7F7F7F7F;//9187201950435737471;
// not HG file constant
not_hg_file:U64 =$3F3F3F3F3F3F3F3F;//4557430888798830399;
// not AB file constant
not_ab_file:U64 =$FCFCFCFCFCFCFCFC;//18229723555195321596;
//square:TBoard_squares;
{/**********************************\
 ==================================
 
          Bit manipulations
 
 ==================================
\**********************************/}
// set/get/pop
function get_bit(bb:U64;const sq:integer):integer;
begin
get_bit:=(bb shr sq) and 1;
end;
procedure set_bit(var bb:U64;const sq:TBoard_squares);
begin
bb:=bb or ($8000000000000000 shr (63-Ord(sq)));
end;
procedure pop_bit(var bb:U64;const sq:TBoard_squares);
begin
if get_bit(bb,Ord(sq))>0 then bb:=bb xor ($8000000000000000 shr (63-Ord(sq)));
end;
{/**********************************\
 ==================================
 
           Input & Output
 
 ==================================
\**********************************/}
// print bitboard
procedure print_bitboard(bb:U64);
var
rank_,file_,sq:integer;
begin
Writeln('');
  // loop over board ranks
  for rank_ := 0 to 7 do  begin
        // loop over board files
        for file_ := 0 to 7 do  begin
           // convert file & rank into square index
           sq:=rank_*8 + file_;
           //// print ranks
           if file_ = 0 then begin
           Write(8 - rank_);Write(' ');
           end;
           Write(' ');
           // print bit state (either 1 or 0)
           Write(get_bit(bb,sq));
        end;
        // print new line every rank
        Writeln('');
  end;
  // print new line
  Writeln('');
  // print board files
  Writeln('   a b c d e f g h');
  Writeln('');
  // print bitboard as unsigned decimal number
  Write('bitboard = ',bb);
  Writeln('');
end;
{/**********************************\
 ==================================

              Attacks

 ==================================
\**********************************/}
// generate pawn attacks
function mask_pawn_attacks(side:TSide;square:TBoard_squares):U64;
var
attacks,bitboard:U64;
begin
// result attacks bitboard
attacks := 0;
// piece bitboard
bitboard := 0;
// set piece on board
set_bit(bitboard, square);
    // white pawns
    if (side=white) then begin
      if ((bitboard shr 7) and not_a_file)>0 then  attacks:=attacks or (bitboard shr 7);
      if ((bitboard shr 9) and not_h_file)>0 then  attacks:=attacks or (bitboard shr 9);
    end
    // black pawns
    else  begin
      if ((bitboard shl 7) and not_h_file)>0 then  attacks:=attacks or (bitboard shl 7);
      if ((bitboard shl 9) and not_a_file)>0 then  attacks:=attacks or (bitboard shl 9);
    end;
// return attack map
mask_pawn_attacks:=attacks;
end;
// generate knight attacks
function  mask_knight_attacks(square:TBoard_squares):U64;
var
attacks,bitboard:U64;
begin
// result attacks bitboard
attacks := 0;
// piece bitboard
bitboard := 0;
// set piece on board
set_bit(bitboard, square);
    // generate knight attacks
    if ((bitboard shr 17) and not_h_file)>0 then  attacks:=attacks or (bitboard shr 17);
    if ((bitboard shr 15) and not_a_file)>0 then  attacks:=attacks or (bitboard shr 15);
    if ((bitboard shr 10) and not_hg_file)>0 then  attacks:=attacks or (bitboard shr 10);
    if ((bitboard shr 6) and not_ab_file)>0 then  attacks:=attacks or (bitboard shr 6);
    if ((bitboard shl 17) and not_a_file)>0 then  attacks:=attacks or (bitboard shl 17);
    if ((bitboard shl 15) and not_h_file)>0 then  attacks:=attacks or (bitboard shl 15);
    if ((bitboard shl 10) and not_ab_file)>0 then  attacks:=attacks or (bitboard shl 10);
    if ((bitboard shl 6) and not_hg_file)>0 then  attacks:=attacks or (bitboard shl 6);
// return attack map
mask_knight_attacks:=attacks;
end;
// generate king attacks
function  mask_king_attacks(square:TBoard_squares):U64;
var
attacks,bitboard:U64;
begin
// result attacks bitboard
attacks := 0;
// piece bitboard
bitboard := 0;
// set piece on board
set_bit(bitboard, square);
    // generate king attacks
    if (bitboard shr 8)>0 then  attacks:=attacks or (bitboard shr 8);
    if ((bitboard shr 9) and not_h_file)>0 then  attacks:=attacks or (bitboard shr 9);
    if ((bitboard shr 1) and not_h_file)>0 then  attacks:=attacks or (bitboard shr 1);
    if ((bitboard shr 7) and not_a_file)>0 then  attacks:=attacks or (bitboard shr 7);
    if (bitboard shl 8)>0 then  attacks:=attacks or (bitboard shl 8);
    if ((bitboard shl 9) and not_a_file)>0 then  attacks:=attacks or (bitboard shl 9);
    if ((bitboard shl 1) and not_a_file)>0 then  attacks:=attacks or (bitboard shl 1);
    if ((bitboard shl 7) and not_h_file)>0 then  attacks:=attacks or (bitboard shl 7);
// return attack map
mask_king_attacks:=attacks;
end;
// init leaper pieces attacks
procedure init_leapers_attacks();
var
square:TBoard_squares;
begin
    // loop over 64 board squares
    for square := a8 to h1 do  begin
       // init pawn attacks
       pawn_attacks[white][square] := mask_pawn_attacks(white,square);
       pawn_attacks[black][square] := mask_pawn_attacks(black,square);
       // init knight attacks
       knight_attacks[square] := mask_knight_attacks(square);
       // init king attacks
       king_attacks[square] := mask_king_attacks(square);
    end;
end;
{/**********************************\
 ==================================
 
             Main driver
 
 ==================================
\**********************************/}
 begin
  //Переключение окна консоли на кодовую страницу CP1251 (Win-1251).
  //Если после переключения русские буквы показываются неверно,
  //следует открыть системное меню консольного окна - щелчком мыши в левом
  //верхнем углу окна консоли. И выбрать:
  //Свойства - закладка "Шрифт" - выбрать шрифт: "Lucida Console".
  SetConsoleCP(1251);
  SetConsoleOutputCP(1251);
// ==================================
  init_leapers_attacks();
  print_bitboard(king_attacks[d5]);
  Writeln('Нажмите <ENTER>, чтобы выйти ...');
  Readln;
end.
Следующие уроки посвящены атакам дальнобойных фигур.
Идея реализованная данным товарищем - нахождение атак дальнобойных фигур с помощью магических чисел.

У меня расчеты атак прыгющих фигур (пешек,коня и короля) берутся непосредственно из таблицы
//битовая маска атак коня
  KnightAttak: array [0..63]  of  UInt64 =(132096,329728,659712,1319424,2638848,5277696,10489856,4202496,
  33816580,84410376,168886289,337772578,675545156,1351090312,2685403152,1075839008,
  8657044482,21609056261,43234889994,86469779988,172939559976,345879119952,687463207072,275414786112,
  2216203387392,5531918402816,11068131838464,22136263676928,44272527353856,88545054707712,175990581010432,70506185244672,
  567348067172352,1416171111120896,2833441750646784,5666883501293568,
  11333767002587136,22667534005174272,45053588738670592,18049583422636032,
  145241105196122112,362539804446949376,725361088165576704,1450722176331153408,
  2901444352662306816,5802888705324613632,11533718717099671552,4620693356194824192,
  288234782788157440,576469569871282176,1224997833292120064,2449995666584240128,
  4899991333168480256,9799982666336960512,1152939783987658752,2305878468463689728,
  1128098930098176,2257297371824128,4796069720358912,9592139440717824,
  19184278881435648,38368557762871296,4679521487814656,9077567998918656);
  //битовая маска атак короля
  KingAttak: array [0..63]  of  UInt64 =(770,1797,3594,7188,14376,28752,57504,49216,
  197123,460039,920078,1840156,3680312,7360624,14721248,12599488,
  50463488,117769984,235539968,471079936,942159872,1884319744,3768639488,3225468928,
  12918652928,30149115904,60298231808,120596463616,241192927232,482385854464,964771708928,825720045568,
  3307175149568,7718173671424,15436347342848,30872694685696,
  61745389371392,123490778742784,246981557485568,211384331665408,
  846636838289408,1975852459884544,3951704919769088,7903409839538176,
  15806819679076352,31613639358152704,63227278716305408,54114388906344448,
  216739030602088448,505818229730443264,1011636459460886528,2023272918921773056,
  4046545837843546112,8093091675687092224,16186183351374184448,13853283560024178688,
  144959613005987840,362258295026614272,724516590053228544,1449033180106457088,
  2898066360212914176,5796132720425828352,11592265440851656704,4665729213955833856);
  //битовая маска атак белых пешек
  WhitePawnAttak: array [0..63]  of  UInt64 =(0,0,0,0,0,0,0,0,//8
  2,5,10,20,40,80,160,64,512,1280,2560,5120,10240,20480,40960,16384,131072,//17
  327680,655360,1310720,2621440,5242880,10485760,4194304,33554432,83886080,//9
  167772160,335544320,671088640,1342177280,2684354560,1073741824,//6
  8589934592,21474836480, 42949672960,85899345920,171798691840,343597383680,//6
  687194767360,274877906944,2199023255552,5497558138880,10995116277760,//5
  21990232555520,43980465111040,87960930222080,175921860444160,70368744177664,//5
  0,0,0,0,0,0,0,0);//8
  //битовая маска атак черных пешек
  BlackPawnAttak: array [0..63]  of  UInt64 =(0,0,0,0,0,0,0,0,//8
  131072,327680,655360,1310720,2621440,5242880,10485760,4194304,33554432,83886080,//10
  167772160,335544320,671088640,1342177280,2684354560,1073741824,8589934592,21474836480,//8
  42949672960,85899345920,171798691840,343597383680,687194767360,274877906944,//6
  2199023255552,5497558138880,10995116277760,21990232555520,43980465111040,87960930222080,//6
  175921860444160,70368744177664,562949953421312,1407374883553280,2814749767106560,//5
  5629499534213120,11258999068426240,22517998136852480,45035996273704960,18014398509481984,//5
  144115188075855872,360287970189639680,720575940379279360,1441151880758558720,2882303761517117440,//5
  5764607523034234880,11529215046068469760,4611686018427387904,0,0,0,0,0,0,0,0);//11
Но для общего представления, как это работает. надо пройти и этот путь
Last Edit: 21 Янв 2023 11:42 by alexlaw.

Bitboard в программировании шахмат №2 23 Янв 2023 11:30 #117

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Жилец
  • Posts: 67
  • Karma: 0
Уроки 6, 7 атаки слона и ладьи до края доски (края не включены)
Урок 8 атаки слона и ладьи с учетом блокирующих фигур.
program bbc;

{$APPTYPE CONSOLE}

uses
  SysUtils,Windows;
type
    U64 = UInt64;
    TBoard_squares = (
    a8, b8, c8, d8, e8, f8, g8, h8,
    a7, b7, c7, d7, e7, f7, g7, h7,
    a6, b6, c6, d6, e6, f6, g6, h6,
    a5, b5, c5, d5, e5, f5, g5, h5,
    a4, b4, c4, d4, e4, f4, g4, h4,
    a3, b3, c3, d3, e3, f3, g3, h3,
    a2, b2, c2, d2, e2, f2, g2, h2,
    a1, b1, c1, d1, e1, f1, g1, h1
    );
    TSide = (white, black);
    //Первый индекс обозначает номер строки в матрице, второй индекс – номер столбца
    TPawn_attacks=array[TSide,TBoard_squares] of U64;
    TChip_attacks=array[TBoard_squares] of U64;
var
 bitboard:U64=0;
 block:U64=0;
 // pawn attacks table [side][square]
 pawn_attacks:TPawn_attacks;
 // knight attacks table [square]
 knight_attacks:TChip_attacks;
 // king attacks table [square]
 king_attacks:TChip_attacks;
 //square:TBoard_squares;
const
{/*
        not A file
  8  0 1 1 1 1 1 1 1
  7  0 1 1 1 1 1 1 1
  6  0 1 1 1 1 1 1 1
  5  0 1 1 1 1 1 1 1
  4  0 1 1 1 1 1 1 1
  3  0 1 1 1 1 1 1 1
  2  0 1 1 1 1 1 1 1
  1  0 1 1 1 1 1 1 1
     a b c d e f g h
        not H file
  8  1 1 1 1 1 1 1 0
  7  1 1 1 1 1 1 1 0
  6  1 1 1 1 1 1 1 0
  5  1 1 1 1 1 1 1 0
  4  1 1 1 1 1 1 1 0
  3  1 1 1 1 1 1 1 0
  2  1 1 1 1 1 1 1 0
  1  1 1 1 1 1 1 1 0
     a b c d e f g h
       not HG file
  8  1 1 1 1 1 1 0 0
  7  1 1 1 1 1 1 0 0
  6  1 1 1 1 1 1 0 0
  5  1 1 1 1 1 1 0 0
  4  1 1 1 1 1 1 0 0
  3  1 1 1 1 1 1 0 0
  2  1 1 1 1 1 1 0 0
  1  1 1 1 1 1 1 0 0
     a b c d e f g h
       not AB file
  8  0 0 1 1 1 1 1 1
  7  0 0 1 1 1 1 1 1
  6  0 0 1 1 1 1 1 1
  5  0 0 1 1 1 1 1 1
  4  0 0 1 1 1 1 1 1
  3  0 0 1 1 1 1 1 1
  2  0 0 1 1 1 1 1 1
  1  0 0 1 1 1 1 1 1
     a b c d e f g h
*/}

// not A file constant
not_a_file:U64 = $FEFEFEFEFEFEFEFE;//18374403900871474942;
// not H file constant
not_h_file:U64 = $7F7F7F7F7F7F7F7F;//9187201950435737471;
// not HG file constant
not_hg_file:U64 =$3F3F3F3F3F3F3F3F;//4557430888798830399;
// not AB file constant
not_ab_file:U64 =$FCFCFCFCFCFCFCFC;//18229723555195321596;
{/**********************************\
 ==================================
 
          Bit manipulations
 
 ==================================
\**********************************/}
// set/get/pop
function get_bit(bb:U64;const sq:integer):integer;
begin
get_bit:=(bb shr sq) and 1;
end;
procedure set_bit(var bb:U64;const sq:TBoard_squares);
begin
bb:=bb or ($8000000000000000 shr (63-Ord(sq)));
end;
procedure pop_bit(var bb:U64;const sq:TBoard_squares);
begin
if get_bit(bb,Ord(sq))>0 then bb:=bb xor ($8000000000000000 shr (63-Ord(sq)));
end;
{/**********************************\
 ==================================
 
           Input & Output
 
 ==================================
\**********************************/}
// print bitboard
procedure print_bitboard(bb:U64);
var
rank_,file_,sq:integer;
begin
Writeln('');
  // loop over board ranks
  for rank_ := 0 to 7 do  begin
        // loop over board files
        for file_ := 0 to 7 do  begin
           // convert file & rank into square index
           sq:=rank_*8 + file_;
           //// print ranks
           if file_ = 0 then begin
           Write(8 - rank_);Write(' ');
           end;
           Write(' ');
           // print bit state (either 1 or 0)
           Write(get_bit(bb,sq));
        end;
        // print new line every rank
        Writeln('');
  end;
  // print new line
  Writeln('');
  // print board files
  Writeln('   a b c d e f g h');
  Writeln('');
  // print bitboard as unsigned decimal number
  Write('bitboard = ',bb);
  Writeln('');
end;
{/**********************************\
 ==================================

              Attacks

 ==================================
\**********************************/}
// generate pawn attacks
function mask_pawn_attacks(side:TSide;square:TBoard_squares):U64;
var
attacks,bitboard:U64;
begin
// result attacks bitboard
attacks := 0;
// piece bitboard
bitboard := 0;
// set piece on board
set_bit(bitboard, square);
    // white pawns
    if (side=white) then begin
      if ((bitboard shr 7) and not_a_file)>0 then  attacks:=attacks or (bitboard shr 7);
      if ((bitboard shr 9) and not_h_file)>0 then  attacks:=attacks or (bitboard shr 9);
    end
    // black pawns
    else  begin
      if ((bitboard shl 7) and not_h_file)>0 then  attacks:=attacks or (bitboard shl 7);
      if ((bitboard shl 9) and not_a_file)>0 then  attacks:=attacks or (bitboard shl 9);
    end;
// return attack map
mask_pawn_attacks:=attacks;
end;
// generate knight attacks
function  mask_knight_attacks(square:TBoard_squares):U64;
var
attacks,bitboard:U64;
begin
// result attacks bitboard
attacks := 0;
// piece bitboard
bitboard := 0;
// set piece on board
set_bit(bitboard, square);
    // generate knight attacks
    if ((bitboard shr 17) and not_h_file)>0 then  attacks:=attacks or (bitboard shr 17);
    if ((bitboard shr 15) and not_a_file)>0 then  attacks:=attacks or (bitboard shr 15);
    if ((bitboard shr 10) and not_hg_file)>0 then  attacks:=attacks or (bitboard shr 10);
    if ((bitboard shr 6) and not_ab_file)>0 then  attacks:=attacks or (bitboard shr 6);
    if ((bitboard shl 17) and not_a_file)>0 then  attacks:=attacks or (bitboard shl 17);
    if ((bitboard shl 15) and not_h_file)>0 then  attacks:=attacks or (bitboard shl 15);
    if ((bitboard shl 10) and not_ab_file)>0 then  attacks:=attacks or (bitboard shl 10);
    if ((bitboard shl 6) and not_hg_file)>0 then  attacks:=attacks or (bitboard shl 6);
// return attack map
mask_knight_attacks:=attacks;
end;
// generate king attacks
function  mask_king_attacks(square:TBoard_squares):U64;
var
attacks,bitboard:U64;
begin
// result attacks bitboard
attacks := 0;
// piece bitboard
bitboard := 0;
// set piece on board
set_bit(bitboard, square);
    // generate king attacks
    if (bitboard shr 8)>0 then  attacks:=attacks or (bitboard shr 8);
    if ((bitboard shr 9) and not_h_file)>0 then  attacks:=attacks or (bitboard shr 9);
    if ((bitboard shr 1) and not_h_file)>0 then  attacks:=attacks or (bitboard shr 1);
    if ((bitboard shr 7) and not_a_file)>0 then  attacks:=attacks or (bitboard shr 7);
    if (bitboard shl 8)>0 then  attacks:=attacks or (bitboard shl 8);
    if ((bitboard shl 9) and not_a_file)>0 then  attacks:=attacks or (bitboard shl 9);
    if ((bitboard shl 1) and not_a_file)>0 then  attacks:=attacks or (bitboard shl 1);
    if ((bitboard shl 7) and not_h_file)>0 then  attacks:=attacks or (bitboard shl 7);
// return attack map
mask_king_attacks:=attacks;
end;
//урок 6-masking relevant bishop occupancy bits to form a key for MAGIC BITBOARDS
// mask bishop attacks
function   mask_bishop_attacks(square:TBoard_squares):U64;
var
attacks,n:U64;
r,f,tr,tf:integer;
begin
n:=1;
// result attacks bitboard
attacks := 0;
    // init target rank & files
    tr := Ord(square) div 8;//целочисленное деление
    tf := Ord(square) mod 8;//остаток от деления
    // mask relevant bishop occupancy bits
    f:=tf+1;
    for r:=tr+1 to 6 do begin
       if f>6 then break;
       attacks := attacks or (n shl (r*8+f));
       Inc(f);
    end;
    f:=tf+1;
    for r:=tr-1 downto 1 do begin
       if f>6 then break;
       attacks := attacks or (n shl (r*8+f));
       Inc(f);
    end;
    f:=tf-1;
    for r:=tr+1 to 6 do begin
       if f<1 then break;
       attacks := attacks or (n shl (r*8+f));
       Dec(f);
    end;
    f:=tf-1;
    for r:=tr-1 downto 1 do begin
       if f<1 then break;
       attacks := attacks or (n shl (r*8+f));
       Dec(f);
    end;
// return attack map
mask_bishop_attacks:=attacks;
end;
//урок 7-masking relevant ROOK OCCUPANCY BITS to form a key for MAGIC BITBOARDS
// mask rook attacks
function   mask_rook_attacks(square:TBoard_squares):U64;
var
attacks,n:U64;
r,f,tr,tf:integer;
begin
n:=1;
// result attacks bitboard
attacks := 0;
    // init target rank & files
    tr := Ord(square) div 8;//целочисленное деление
    tf := Ord(square) mod 8;//остаток от деления
    // mask relevant bishop occupancy bits
    for r:=tr+1 to 6 do attacks := attacks or (n shl (r*8+tf));
    for r:=tr-1 downto 1 do attacks := attacks or (n shl (r*8+tf));
    for f:=tf+1 to 6 do attacks := attacks or (n shl (tr*8+f));
    for f:=tf-1 downto 1 do attacks := attacks or (n shl (tr*8+f));
// return attack map
mask_rook_attacks:=attacks;
end;
//урок 8-generating SLIDER PIECES ATTACKS on the fly for MAGIC BITBOARD purposes
// generate bishop attacks on the fly
function  bishop_attacks_on_the_fly(square:TBoard_squares;blk:U64):U64;
var
attacks,n:U64;
r,f,tr,tf:integer;
begin
n:=1;
// result attacks bitboard
attacks := 0;
    // init target rank & files
    tr := Ord(square) div 8;//целочисленное деление
    tf := Ord(square) mod 8;//остаток от деления
    // generate bishop atacks
    f:=tf+1;
    for r:=tr+1 to 7 do begin
       if f>7 then break;
       attacks := attacks or (n shl (r*8+f));
       if ((n shl (r*8+f)) and blk)>0 then  break;
       Inc(f);
    end;
        f:=tf+1;
    for r:=tr-1 downto 0 do begin
       if f>7 then break;
       attacks := attacks or (n shl (r*8+f));
       if ((n shl (r*8+f)) and blk)>0 then  break;
       Inc(f);
    end;
    f:=tf-1;
    for r:=tr+1 to 7 do begin
       if f<0 then break;
       attacks := attacks or (n shl (r*8+f));
       if ((n shl (r*8+f)) and blk)>0 then  break;
       Dec(f);
    end;
    f:=tf-1;
    for r:=tr-1 downto 0 do begin
       if f<0 then break;
       attacks := attacks or (n shl (r*8+f));
       if ((n shl (r*8+f)) and blk)>0 then  break;
       Dec(f);
    end;
// return attack map
bishop_attacks_on_the_fly:=attacks;
end;
// generate rook attacks on the fly
function  rook_attacks_on_the_fly(square:TBoard_squares;blk:U64):U64;
var
attacks,n:U64;
r,f,tr,tf:integer;
begin
n:=1;
// result attacks bitboard
attacks := 0;
    // init target rank & files
    tr := Ord(square) div 8;//целочисленное деление
    tf := Ord(square) mod 8;//остаток от деления
    // generate rook attacks
    for r:=tr+1 to 7 do begin
    attacks := attacks or (n shl (r*8+tf));
    if ((n shl (r*8+tf)) and blk)>0 then  break;
    end;
    for r:=tr-1 downto 0 do begin
    attacks := attacks or (n shl (r*8+tf));
    if ((n shl (r*8+tf)) and blk)>0 then  break;
    end;
    for f:=tf+1 to 7 do begin
    attacks := attacks or (n shl (tr*8+f));
    if ((n shl (tr*8+f)) and blk)>0 then  break;
    end;
    for f:=tf-1 downto 0 do begin
    attacks := attacks or (n shl (tr*8+f));
    if ((n shl (tr*8+f)) and blk)>0 then  break;
    end;
// return attack map
rook_attacks_on_the_fly:=attacks;
end;
// init leaper pieces attacks
procedure init_leapers_attacks();
var
square:TBoard_squares;
begin
    // loop over 64 board squares
    for square := a8 to h1 do  begin
//урок 3-generating pre-calculated PAWN ATTACK tables
       // init pawn attacks
       pawn_attacks[white][square] := mask_pawn_attacks(white,square);
       pawn_attacks[black][square] := mask_pawn_attacks(black,square);
//урок 4-generating pre-calculated KNIGHT ATTACK table
       // init knight attacks
       knight_attacks[square] := mask_knight_attacks(square);
//урок 5-generating pre-calculated KING ATTACK tables
       // init king attacks
       king_attacks[square] := mask_king_attacks(square);
    end;
end;
{/**********************************\
 ==================================

             Main driver
 
 ==================================
\**********************************/}
 begin
  //Переключение окна консоли на кодовую страницу CP1251 (Win-1251).
  //Если после переключения русские буквы показываются неверно,
  //следует открыть системное меню консольного окна - щелчком мыши в левом
  //верхнем углу окна консоли. И выбрать:
  //Свойства - закладка "Шрифт" - выбрать шрифт: "Lucida Console".
  SetConsoleCP(1251);
  SetConsoleOutputCP(1251);
// ==================================
  init_leapers_attacks();
  set_bit(block,b5);set_bit(block,f3);set_bit(block,g5); set_bit(block,f7);
  print_bitboard(rook_attacks_on_the_fly(c5,block));
  Writeln('Нажмите <ENTER>, чтобы выйти ...');
  Readln;
end.
Освоенные уроки
2. Bitboard CHESS ENGINE in C: creating comfortable conditions for development
3. Bitboard CHESS ENGINE in C: generating pre-calculated PAWN ATTACK tables
4. Bitboard CHESS ENGINE in C: generating pre-calculated KNIGHT ATTACK table
5. Bitboard CHESS ENGINE in C: generating pre-calculated KING ATTACK tables
6. Bitboard CHESS ENGINE in C: masking relevant bishop occupancy bits to form a key for MAGIC BITBOARDS
7. Bitboard CHESS ENGINE in C: masking relevant ROOK OCCUPANCY BITS to form a key for MAGIC BITBOARDS
8. Bitboard CHESS ENGINE in C: generating SLIDER PIECES ATTACKS on the fly for MAGIC BITBOARD purposes

Кому интересно можете смотреть уроки переведенные на русский язык
Bitboard CHESS ENGINE in C
Last Edit: 23 Янв 2023 11:45 by alexlaw.

Bitboard в программировании шахмат №2 23 Янв 2023 13:48 #118

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Жилец
  • Posts: 67
  • Karma: 0
Сегодня узнал что-то новое и важное для себя. из урока - №9 - implementing BIT COUNT routine (Brian Kernighan's way).
А именно - Алгоритм Брайана Кернигана для подсчета установленных бит в целом числе.
Супер алгоритм.
Реализация на Делфи
// count bits within a bitboard (Brian Kernighan's way)
function count_bits(bb:U64):integer;
var
count:integer;
begin
    // bit counter
    count := 0;
    // consecutively reset least significant 1st bit
     while bb>0
     do  begin
         // increment count
         Inc(count);
         // reset least significant 1st bit
         bb := bb and (bb - 1);
         end;
count_bits:=count;
end;

Bitboard в программировании шахмат №2 23 Янв 2023 14:18 #119

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Жилец
  • Posts: 67
  • Karma: 0
Странно.
Этот алгоритм работает в два раза медленне, чем я ожидал.

39.jpg


У меня такая реализация подсчета битов
//Подсчет количества установленных бит в integer
function CountBits(const Value: integer): integer;
asm
mov ECX,EAX
xor EAX,EAX
test ECX,ECX
jz @@ending
@@counting:
shr ECX,1
adc EAX,0
test ECX,ECX
jnz @@counting
@@ending:
end;
//Подсчет количества установленных бит в Int64
function CountBitsInt64(const integer64:UInt64):integer;
begin
result:=CountBits(integer64)+CountBits(integer64 shr 32);
end;

Bitboard в программировании шахмат №2 23 Янв 2023 17:50 #120

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Жилец
  • Posts: 67
  • Karma: 0
В принципе Алгоритм Брайана Кернигана работает не плохо, в случае, когда число установленных бит не велико.
Пример - установлен самый старший бит - $8000000000000000.
В данном случаи он работает в 2 раза быстрее, чем тот, который использовал я.
40.jpg

Поэтому оставлю его.
Замеры делал так
function RDTSC: UInt64;
{
 rdtsc (англ. Read Time Stamp Counter) — ассемблерная инструкция
 для платформ x86 и x86_64, читающая счётчик TSC (Time Stamp Counter)
 и возвращающая в регистрах EDX:EAX 64-битное количество тактов
 с момента последнего сброса процессора.
}
//t1,t2:UInt64;
//t1:=RDTSC;
//t2:=RDTSC-t1;
//ShowMessage(IntToStr(t2));
asm
 rdtsc
end;
print_bitboard($8000000000000000);
  t1:=RDTSC;
  count_bits($8000000000000000);
  t2:=RDTSC-t1;
  Writeln('count_bits = ',count_bits($8000000000000000));
  Writeln('Brian Kernighan s way - ',t2);
  t1:=RDTSC;
  CountBitsInt64($8000000000000000);
  t2:=RDTSC-t1;
  Writeln('count_bits = ',CountBitsInt64($8000000000000000));
  Writeln('CountBitsInt64 - ',t2);
  Writeln('Нажмите <ENTER>, чтобы выйти ...');
  Readln;
Last Edit: 23 Янв 2023 17:54 by alexlaw.
Moderators: Grigoriy
Рейтинг@Mail.ru

Научно-шахматный клуб КвантоФорум