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

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

Bitboard в программировании шахмат №2 26 Нояб 2022 09:53 #1

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 199
  • Thank you received: 10
  • Karma: 1
Здравствуйте.
Когда то я пробовал свои силы в шахматном программировании.
Но так и не довел дело до приемлемого решения этого вопроса.
Я решил снова вернуться к этому вопросу и наконец добиться результата.
Я хочу использовать подход "bitboard".
Просто мне это нравится.
Я буду использовать среду Delphi.
На самом деле меня прежде всего интересуем математическая модель.
Я подготовил для себя «UI»-пользовательский интерфейс. Для проверки и отладки программы.


pos1.jpg



Для отображения всей шахматной позиции будем использовать набор из 12 BitBoard.
Взависимости от цвета и типа фигур


1.jpg



Нумерация битов.



2.jpg



Итак вопрос.

Как компактно представить шахматную позицию (bitboard) в памяти компа для передачи ее в качестве параметра рекурсивной функции поиска?

Мое "UI" - cloud.mail.ru/public/CEy5/nc64vPM3A
Last Edit: 26 Нояб 2022 14:13 by Vladimirovich.

Bitboard в программировании шахмат 26 Нояб 2022 10:23 #2

  • Ruslan73
  • Ruslan73's Avatar
  • OFFLINE
  • Администратор
  • Posts: 36502
  • Thank you received: 825
  • Karma: 58
alexlaw wrote:
Как компактно представить шахматную позицию (bitboard) в памяти компа для передачи ее в качестве параметра рекурсивной функции поиска?
А цель вашей программы какая, что она будет делать, для чего создаётся?
Если это игровая программа то кмк компактность кодирования позиции это не 1й приоритет. Важно чтобы обрабатывать удобнее было.
Я буду использовать среду Delphi.
А почему не на Lazarus+FPC они кроссплатформенные.

Вот вроде уже есть готовый движок на паскале. Правда там с комментариями мягко говоря плохо.
github.com/rchastain/open-critter

en.wikipedia.org/wiki/Critter_(chess)
Last Edit: 26 Нояб 2022 10:29 by Ruslan73.

Bitboard в программировании шахмат 26 Нояб 2022 11:45 #3

  • Ruslan73
  • Ruslan73's Avatar
  • OFFLINE
  • Администратор
  • Posts: 36502
  • Thank you received: 825
  • Karma: 58
6 вариантов фигур и пешка + цвет это 4 бита. Положение надо доске +64 бита.
Всего до 32 фигур и пешек на доске максимум, т.е. 32х68=2176 бит = 272 байта на позицию.
А ещё очередь хода, были рокировки нет, взятие на проходе доступно нет, сколько ходов с последнего взятия прошло (для правила 50 ходов) и в итоге изобретём свой FEN.
en.m.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_Notation
Last Edit: 26 Нояб 2022 11:47 by Ruslan73.

Bitboard в программировании шахмат 26 Нояб 2022 12:55 #4

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 199
  • Thank you received: 10
  • Karma: 1
и в итоге изобретём свой FEN.
Стоп,стоп,стоп)))
Давайте по порядку.
Начнем с атак фигур.
Король, конь и пешки - атаки рассчитаем заранее.
Вопрос для дальнобойных фигур.
Я иду таким путем. Провожу луч из поля с фигурой, нахожу на пересечении все фигуры, затем нахожу старший или младший бит, провожу встречный луч, Пересечение лучей и есть атака дальнобойной фигуры в заданном направлении.
Но есть более быстрый метод - Магические битбоарды, С этим пока не разобрался.
Буду признателен, если есть простое и понятное объяснение.

Bitboard в программировании шахмат 26 Нояб 2022 13:07 #5

  • Ruslan73
  • Ruslan73's Avatar
  • OFFLINE
  • Администратор
  • Posts: 36502
  • Thank you received: 825
  • Karma: 58
С битбордами незнаком и названия наглосаксонские мне лично не нравятся.
Бит ладно, а борд слова нет в русском. Битовые доски тогда.

Я бы для каждой клетки доски хранил заранее просчитанные структуры диагоналей и вертикалей которые её пересекают.
И если на клетках соотв. вертикалей/диагоналей (для клетки где стоит фигура) что-то есть, определял бы фигуру с минимальным расстоянием от текущей и всё. Если она такого же цвета как текущая, значит защищаем, если другого нападаем.
Last Edit: 26 Нояб 2022 13:10 by Ruslan73.

Bitboard в программировании шахмат 26 Нояб 2022 14:13 #6

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 109799
  • Thank you received: 2227
  • Karma: 108
Битборды это лишь удобный подход к организации операций на доске

Нумеровать их совсем не нужно.
Главное удобство, что их 64 для 64-битных ASM операций и полей в шахматах тоже 64.

Тогда, чтобы например определить все поля, которые может бить ладья, вместо двух пионерских циклов по вертикали и горизонтали, можно наложить на поле битмаску ходов ладьи для заданного поля. И т.д. Накладываются все нужные маски или "битбоарды" и оп-ля.
Быстродействие повышает кардинально.

Теме присвоен №2 как дополнение к quantoforum.ru/mathematics/98-shakhmaty-i-programmirovanie
Каждому - своё.

Bitboard в программировании шахмат 26 Нояб 2022 14:31 #7

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 109799
  • Thank you received: 2227
  • Karma: 108
alexlaw wrote:
Я буду использовать среду Delphi.
А вот это глобальный тупик.
Каждому - своё.

Bitboard в программировании шахмат 26 Нояб 2022 14:38 #8

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 199
  • Thank you received: 10
  • Karma: 1
Суть не в том Dephi или Си.
Это лишь инструмент.
Могу использовать java.
Короче суть не в этом.
Суть в алгоритмах.

Bitboard в программировании шахмат 26 Нояб 2022 14:40 #9

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 199
  • Thank you received: 10
  • Karma: 1
Ruslan73 wrote:
С битбордами незнаком и названия наглосаксонские мне лично не нравятся.
Бит ладно, а борд слова нет в русском. Битовые доски тогда.

Я бы для каждой клетки доски хранил заранее просчитанные структуры диагоналей и вертикалей которые её пересекают.
И если на клетках соотв. вертикалей/диагоналей (для клетки где стоит фигура) что-то есть, определял бы фигуру с минимальным расстоянием от текущей и всё. Если она такого же цвета как текущая, значит защищаем, если другого нападаем.
На счёт боард согласен.
Доска мне тоже ближе.
Вы описали тот алгоритм который я использую.

Bitboard в программировании шахмат 26 Нояб 2022 16:16 #10

  • Ruslan73
  • Ruslan73's Avatar
  • OFFLINE
  • Администратор
  • Posts: 36502
  • Thank you received: 825
  • Karma: 58
А Вы хотите инвестировать время в переделку алгоритма на битовые доски чтобы ускорить генерацию всех возможных ходов/взятий в позиции?
Думаете это существенно поднимет силу движка?

Мне казалось что инвестиции в алгоритмы выбора хода из возможных/функцию оценки намного больший эффект дают.
И только если там в какой-то потолок уперлись есть смысл из генерации легальных ходов выжимать микросекунды.
Last Edit: 26 Нояб 2022 16:17 by Ruslan73.

Bitboard в программировании шахмат 26 Нояб 2022 16:36 #11

  • Ruslan73
  • Ruslan73's Avatar
  • OFFLINE
  • Администратор
  • Posts: 36502
  • Thank you received: 825
  • Karma: 58
alexlaw wrote:
Я хочу использовать подход "bitboard".
Просто мне это нравится
Понял, просто хочется освоить.
Для отображения всей шахматной позиции будем использовать набор из 12 BitBoard.
Не въехал в диаграмму сразу, да 12 хватает, однотипные фигуры/пешки ведь в одну битовую доску упаковываются. 96 байт на позицию. Плюс признаки рокировок и прочего если нужно.
Last Edit: 26 Нояб 2022 16:50 by Ruslan73.

Bitboard в программировании шахмат 26 Нояб 2022 16:51 #12

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 109799
  • Thank you received: 2227
  • Karma: 108
alexlaw wrote:
Суть не в том Dephi или Си.
Это лишь инструмент.
Могу использовать java.
Короче суть не в этом.
Суть в алгоритмах.
Это не так. Алгоритмам действительно все равно.
Но если речь идет о чем то реальном, то будет критична скорость, а для нее и компилятор.
Java в этом смысле без JIT вообще не вариант.

Хуже другое...
Алгоритмы сами по себе это бня...
Алгоритм должен быть куда-то встроен.
А значит нужны либы для поддержки UCI например хотя бы...
Линковать это с Делфи?... Или писать самому? Гемор.

Сами битборды уже неотъемлемая часть современных движков

Повторю мысль....
Как Вы собираетесь например найти все поля, которые может побить ладья?
Вот все это давно сделано через битборды вместо Ботвинниковского программирования.

В чем новая идея?
Каждому - своё.

Bitboard в программировании шахмат 26 Нояб 2022 17:01 #13

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 109799
  • Thank you received: 2227
  • Karma: 108
Собственно главный смысл битборда в том, что позиция есть набор 64 битовых слов - масок.
Получается некий слоеный торт из бит масок, каждая из которых некий атрибут позиции.

И ассемблерные операции над 64-бит словами супер заменяют всякие древние безмозглые циклы.
Вот и вся главная идея

Отсюда ответ
alexlaw wrote:
Итак вопрос.

Как компактно представить шахматную позицию (bitboard) в памяти компа для передачи ее в качестве параметра рекурсивной функции поиска?

Позиция есть набор 64 битных слов.
Размерность то ли 6, то ли больше, но это уже не суть.
Каждому - своё.
Last Edit: 26 Нояб 2022 17:06 by Vladimirovich.

Bitboard в программировании шахмат 26 Нояб 2022 17:20 #14

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 109799
  • Thank you received: 2227
  • Karma: 108
Чисто для иллюстрации...

2022_rook_moves.png


Для позиции ладьи на d4 записана маска-битбоард, где все поля гипотетические помечены крестиками. Они же 1 в 64 битовом числе. Все остальное 0.
Места неважны. Главное, чтобы раз и навсегда определить.
Такие же маски записаны для всех полей и всех фигур.
И вообще куча других масок.

Алгоритм юзает это через ассеблерные операции типа ADD AX, BX (OR, XOR) и пр.
Во много раз быстрее, чем через циклы.
Каждому - своё.
Last Edit: 26 Нояб 2022 17:52 by Vladimirovich.

Bitboard в программировании шахмат 26 Нояб 2022 17:21 #15

  • Ruslan73
  • Ruslan73's Avatar
  • OFFLINE
  • Администратор
  • Posts: 36502
  • Thank you received: 825
  • Karma: 58
Vladimirovich wrote:
Как Вы собираетесь например найти все поля, которые может побить ладья?
Поля или фигуры?
Список, ходов и список взятий обычно разделяют.

Для взятий видимо найти все возможные ходы и пересечения этих битов с битами вражеских и своих фигур, определить ближайшие к ладье по каждой линии. Там 12 вариантов всего на каждой полулинии либо своя фигура либо чужая либо край доски.

Ходы ладьи на пустой доске довольно просто искать сдвигом битов - ходы по вертикали это сдвиги на 8ки бит вперед и назад, по горизонтали - +/- 1-7 в рамках своей 8ки бит.
Last Edit: 26 Нояб 2022 17:24 by Ruslan73.

Bitboard в программировании шахмат 26 Нояб 2022 17:25 #16

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 109799
  • Thank you received: 2227
  • Karma: 108
Ruslan73 wrote:
Поля или фигуры?
Список, ходов и список взятий обычно разделяют.
Неважно. Я привел схему.
64 битное число ладьи (маска) накладывается на остальые маски, откуда появляется результирующее 64-число, где бит это поле разрешенное

Отдельная маска 64-число это взятие или просто ход. Например
Каждому - своё.
Last Edit: 26 Нояб 2022 17:28 by Vladimirovich.

Bitboard в программировании шахмат 26 Нояб 2022 17:28 #17

  • Ruslan73
  • Ruslan73's Avatar
  • OFFLINE
  • Администратор
  • Posts: 36502
  • Thank you received: 825
  • Karma: 58
Ну да можно масок наделать на все возможные ходы из каждой позиции для каждой фигуры. Потом только применять. А сами эти маски генерить сдвигами.
Last Edit: 26 Нояб 2022 18:05 by Хайдук.

Bitboard в программировании шахмат 26 Нояб 2022 17:30 #18

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 109799
  • Thank you received: 2227
  • Karma: 108
Ruslan73 wrote:
А сами эти маски генерить сдвигами.
Полей не так много :)
Можно просто сгенерить заранее для всех фигур и полей
Несколько килобайт будет максимум думаю :)
Каждому - своё.

Bitboard в программировании шахмат 26 Нояб 2022 17:40 #19

  • Ruslan73
  • Ruslan73's Avatar
  • OFFLINE
  • Администратор
  • Posts: 36502
  • Thank you received: 825
  • Karma: 58
alexlaw wrote:
Вопрос для дальнобойных фигур.
Я иду таким путем. Провожу луч из поля с фигурой, нахожу на пересечении все фигуры, затем нахожу старший или младший бит, провожу встречный луч, Пересечение лучей и есть атака дальнобойной фигуры в заданном направлении.
Но есть более быстрый метод - Магические битбоарды, С этим пока не разобрался.
Тут вопрос как из маски всех потенциальных ходов ладьи оставить только реально возможные с учётом чужих и своих фигур.

Надо маску возможных ходов ладьи на пустой доске наложить на маску текущего положения своих фигур, ближайшие к ладье по каждой полу-линии пересечения дадут потолки движения ладьи, возможные ходы за этими своими фигурами по полу-линии и на поля где стоят другие фигуры отбрасываются, получается маска возможных ходов с учетом положения своих фигур.
Эту маску потом накладывать на маску положения фигур противника. Из пересечений на одной полу-линии оставлять только ближайшие.
Плюс учесть связки ладьи с королем например, связанная ограничена в передвижениях.
Last Edit: 26 Нояб 2022 17:40 by Ruslan73.

Bitboard в программировании шахмат 26 Нояб 2022 17:48 #20

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 109799
  • Thank you received: 2227
  • Karma: 108
В целом битборды абсолютно несовместимы с подходом лучей
Каждому - своё.

Bitboard в программировании шахмат 26 Нояб 2022 20:11 #21

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 199
  • Thank you received: 10
  • Karma: 1
В первом посте есть ссылка на мое UI с облака.
Как раз там использую я подход лучей.
Я конечно понимаю, чтобы получить ответ на вопрос, надо правильно задать вопрос.
Я позже сформулирую вопрос.

3.jpg

Вот код для дальнобойных фигур
procedure maskLine ();-лучи из каждого поля доски до края доски в разных направлениях
function ForwardReverseLine - пересечение лучей от фигуры до ближней фигуры на доске
procedure AttakTo(); - атака фигуры из данной клетки
procedure AttakFrom(); - какие фигуры атакуют данное поле
unit MaskBit;

interface
procedure maskLine ();
procedure init ();
procedure AttakTo();
procedure AttakFrom();
var
  LineA1A8: array [0..63]  of  UInt64;
  LineA8A1: array [0..63]  of  UInt64;
  LineA1H1: array [0..63]  of  UInt64;
  LineH1A1: array [0..63]  of  UInt64;
  LineA1H8: array [0..63]  of  UInt64;
  LineH8A1: array [0..63]  of  UInt64;
  LineA8H1: array [0..63]  of  UInt64;
  LineH1A8: array [0..63]  of  UInt64;
  BishopAttak: array [0..63]  of  UInt64;
  RookAttak: array [0..63]  of  UInt64;
  QweenAttak: array [0..63]  of  UInt64;
implementation

uses Windows,Dialogs,SysUtils,fun, VisualBoard, Base, MoveGenerator, Stack;
procedure init ();
  var
i: Integer;
begin
for i := 0 to 63 do  begin
  LineA1A8[i]:=0;
  LineA8A1[i]:=0;
  LineA1H1[i]:=0;
  LineH1A1[i]:=0;
  LineA1H8[i]:=0;
  LineH8A1[i]:=0;
  LineA8H1[i]:=0;
  LineH1A8[i]:=0;
  BishopAttak[i]:=0;
  RookAttak[i]:=0;
  QweenAttak[i]:=0;
end;
end;
procedure maskLine ();
 var
i,j,z,k: Integer;
begin
  for i := 0 to 63 do  begin
  z:=i div 8;
       for j := 0 to z do  begin
           k:=i-j*8;
             LineA1A8[i]:= LineA1A8[i] or Base.MaskOneBit[k];
           if j<=(7 - k mod 8) then  begin
             LineA1H8[i]:=LineA1H8[i] or (Base.MaskOneBit[k] shl j);
           end;
           if j<=(k mod 8) then begin
             LineH1A8[i]:=LineH1A8[i] or (Base.MaskOneBit[k] shr j);
           end;
       end;
   z:=7 - i div 8;
       for j := 0 to z do  begin
           k:=i+j*8;
             LineA8A1[i]:= LineA8A1[i] or Base.MaskOneBit[k];
           if j<=(7 - k mod 8) then  begin
             LineA8H1[i]:=LineA8H1[i] or (Base.MaskOneBit[k] shl j);
           end;
           if j<=(k mod 8) then begin
             LineH8A1[i]:=LineH8A1[i] or (Base.MaskOneBit[k] shr j);
           end;
       end;
    z:=7 - i mod 8;
        for j := 0 to z do  begin
            LineA1H1[i]:=LineA1H1[i] or (Base.MaskOneBit[i+j]);
        end;
    z:=i mod 8;
        for j := 0 to z do  begin
            LineH1A1[i]:=LineH1A1[i] or (Base.MaskOneBit[i-j]);
        end;
  end;
end;
function ForwardReverseLine(ForwardLine,ReverseLine:array of  UInt64;Pos,Flag: Integer):UInt64;
var
Temp64:UInt64;
k:Integer;
begin
Temp64:=ForwardLine[Pos] and Base.AllPieceU64 xor Base.MaskOneBit[Pos];
if Temp64>0 then begin
        case Flag  of
          1: begin
            k:=fun.SeniorBit(Temp64,Temp64 shr 32)-1;
          end;
          0: begin
            k:=fun.JuniorBit(Temp64,Temp64 shr 32);
          end;
        end;
        result:=ForwardLine[Pos] and ReverseLine[k] xor Base.MaskOneBit[Pos] or Base.MaskOneBit[k];
end else result:=ForwardLine[Pos] xor Base.MaskOneBit[Pos];
end;
procedure AttakTo();
var
i:integer;
begin
  for i := 0 to 63 do  begin
  Base.AttakToArray[i]:=0;
    if not fun.IsBit64(Base.AllPieceU64,i) then continue;
       case Base.PosPieceArray[i]  of
          0,6:begin
          Base.AttakToArray[i]:=Base.KingAttak[i];
          end;
          1,7:begin
          QweenAttak[i]:=ForwardReverseLine(LineA1A8,LineA8A1,i,1)
          or ForwardReverseLine(LineH1A1,LineA1H1,i,1)
          or ForwardReverseLine(LineA1H1,LineH1A1,i,0)
          or ForwardReverseLine(LineA8A1,LineA1A8,i,0)
          or ForwardReverseLine(LineA1H8,LineH8A1,i,1)
          or ForwardReverseLine(LineH1A8,LineA8H1,i,1)
          or ForwardReverseLine(LineH8A1,LineA1H8,i,0)
          or ForwardReverseLine(LineA8H1,LineH1A8,i,0);
          Base.AttakToArray[i]:=QweenAttak[i];
          end;
          2,8:begin
          RookAttak[i]:=ForwardReverseLine(LineA1A8,LineA8A1,i,1)
          or ForwardReverseLine(LineH1A1,LineA1H1,i,1)
          or ForwardReverseLine(LineA1H1,LineH1A1,i,0)
          or ForwardReverseLine(LineA8A1,LineA1A8,i,0);
          Base.AttakToArray[i]:=RookAttak[i];
          end;
          3,9:begin
          BishopAttak[i]:=ForwardReverseLine(LineA1H8,LineH8A1,i,1)
          or ForwardReverseLine(LineH1A8,LineA8H1,i,1)
          or ForwardReverseLine(LineH8A1,LineA1H8,i,0)
          or ForwardReverseLine(LineA8H1,LineH1A8,i,0);
          Base.AttakToArray[i]:=BishopAttak[i];
          end;
          4,10:begin
          Base.AttakToArray[i]:=Base.KnightAttak[i];
          end;
          5,11:begin
          if Base.ColorPieceArray[i]=0 then  Base.AttakToArray[i]:=Base.WhitePawnAttak[i];
          if Base.ColorPieceArray[i]=1 then    Base.AttakToArray[i]:=Base.BlackPawnAttak[i];
          end;
       end;  
if Base.PosPieceArray[i]>5 then  Base.PosPieceArray[i]:=Base.PosPieceArray[i] - 6;

  end;
end;
procedure AttakFrom();
var
i,j:integer;
begin
   for i := 0 to 63 do  begin
   Base.AttakFromArray[i]:=0;
       for j := 63 downto 0 do  begin
         if fun.IsBit64(Base.AttakToArray[j],i)
         then Base.AttakFromArray[i]:=Base.AttakFromArray[i] or Base.MaskOneBit[j];
       end;
   end;
end;
end.
Last Edit: 26 Нояб 2022 20:25 by alexlaw.

Bitboard в программировании шахмат 26 Нояб 2022 20:29 #22

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 199
  • Thank you received: 10
  • Karma: 1
Так вот вопрос в том, чтобы уйти от расчетов атак, а заранее их расчитать используя магические квадраты.
Примерно как написано тут
https://www.pvsm.ru/game-development/17378?utm_source=pocket_saves&ysclid=l9zgbf9nj6679415818

Это нужно для того , чтобы сократить время.
Т.к. сделав ход фигурой мне приходиться пересчитывать AttackFrom и AttackTo, что плюс вспомогательные массивы.
Это съедает мног времени.
Last Edit: 26 Нояб 2022 21:31 by alexlaw.

Bitboard в программировании шахмат 26 Нояб 2022 22:40 #23

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 199
  • Thank you received: 10
  • Karma: 1
Vladimirovich wrote:
alexlaw wrote:
Суть не в том Dephi или Си.
Хуже другое...
Алгоритмы сами по себе это бня...
Алгоритм должен быть куда-то встроен.
А значит нужны либы для поддержки UCI например хотя бы...
Линковать это с Делфи?... Или писать самому? Гемор.

Кстати абсолютно никакого гемора.
Идею я подчерпнул еще когда входу были кнопочные телефоны и рулил JAVA2ME.
Декомпилировал прогу CHESSMASTER и понял принцип UI.
Идея такая

4.jpg

Из изображений фигур формируется изображение всей позиции на доске.
Рисуем на КАНВЕ(Холст)
unit VisualBoard;   //30102022

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, ExtCtrls, Menus;

type
  TFormBoard = class(TForm)
    ChessBoard: TImage;//изображение шахматной доски
    Desk: TImage;//изображение клеток шахматного поля
    Piece: TImage;//изображение всех фигур
    SelectBox: TImage;//изображение рамки выбора
    PieceMirror: TImage;
    MainMenu1: TMainMenu;
    N1: TMenuItem;
    N20: TMenuItem;
    N12: TMenuItem;
    N22: TMenuItem;
    N32: TMenuItem;
    N42: TMenuItem;
    N52: TMenuItem;
    N62: TMenuItem;
    FEN1: TMenuItem;
    procedure FEN1Click(Sender: TObject);
    procedure NClick(Sender: TObject);
    procedure ChessBoardClick(Sender: TObject);
    procedure ChessBoardMouseMove(Sender: TObject; Shift: TShiftState; X,
      Y: Integer);//перевернутое изображение фигур
    procedure FormCreate(Sender: TObject);

  private
    { Private declarations }
  public
    { Public declarations }
  end;
var
  Board: TFormBoard;
  //дата
  ProgrammDate:String = '09.11.2022';
  //измерение времени
  Start, Stop: cardinal;
  Elapsed: cardinal;
  t1,t2,t:UInt64;
  // начальная позиция
  WPieceStart: array [0..5]  of  UInt64 = (1152921504606846976,576460752303423488,9295429630892703744,2594073385365405696,4755801206503243776,71776119061217280);
  BPieceStart: array [0..5]  of  UInt64 = (16,8,129,36,66,65280);
  AllPiece:UInt64 = 0;
  PosStart: String='rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR';
  //PosStart: String='2N1N3/K7/6B1/4kPb1/b2p4/6P1/5P2/7Q';
  //размеры игрового поля доски
  DescHeight:Integer=480;
  DescWidth:Integer=480;
  //смещение игрового поля доски от начала координат
  dX:Integer=24;
  dY:Integer=20;
  //размер клетки игрового поля
  cell:Integer=60;
  Xmouse,Ymouse,NumPos:Integer;
implementation

uses fun, MaskBit;

{$R *.dfm}
procedure ClearDesk ();
var
bmp: tbitmap;
begin
try
 bmp := tbitmap.Create;
 bmp.Height:=DescHeight;
 bmp.Width:=DescWidth;
 bmp.Canvas.CopyRect(rect(0,0,bmp.Width,bmp.Height),Board.Desk.Canvas,rect(0,0,DescWidth,DescHeight));
 Board.ChessBoard.Canvas.CopyMode:=cmSrcCopy;
 Board.ChessBoard.Canvas.Draw(dX, dY, bmp);
finally
 bmp.free;
end;
end;
procedure DrawPiece(Pos,NumP,ColorP: Integer);
var
bmp: tbitmap;
a,b: Integer;
begin
try
 bmp := tbitmap.Create;
 bmp.Height:=cell;
 bmp.Width:=cell;
a:=Pos and 7;
b:=Pos shr 3;
bmp.Canvas.CopyRect(rect(0,0,bmp.Width,bmp.Height),Board.Piece.Canvas,rect(cell*NumP,cell*ColorP,cell*NumP+cell,cell*ColorP+cell));
bmp.TransparentColor:=clYellow;
bmp.Transparent:=true;
Board.ChessBoard.Canvas.Draw(dX+cell*a, dY+cell*b, bmp);
finally
 bmp.free;
end;
end; 

 procedure DrawPieceBoard(APiece:array of  UInt64;ColorPiece: Integer);
var
NumPiece: Integer;
i,j: Integer;
begin
NumPiece:=0;
                          while NumPiece<6 do begin
                                  for i:=63 downto 0 do  begin
                                  j := (APiece[NumPiece] shr i) and 1;
                                       case j  of
                                                 1:begin
                                                   DrawPiece(i,NumPiece,ColorPiece);
                                                  end;
                                       end;
                                   end;
                            NumPiece:=NumPiece+1;
                            end;

end;

 procedure DrawMoveBox(u:UInt64);
var
bmp: tbitmap;
a,b,i,j: Integer;
begin
try
 j:=0;
 bmp := tbitmap.Create;
 bmp.Height:=cell;
 bmp.Width:=cell;
bmp.TransparentColor:=clWhite;
bmp.Transparent:=true;
bmp.Canvas.CopyRect(rect(0,0,bmp.Width,bmp.Height),Board.Piece.Canvas,rect(cell*6,0,cell*7,cell));
                                  for i:=63 downto 0 do  begin
                                  j := (u shr i) and 1;
                                       case j  of
                                                 1:begin
                                                  a:=i and 7;
                                                  b:=i shr 3;
                                                  Board.Canvas.Draw(dX+cell*a, dY+cell*b, bmp);
                                                  end;
                                       end;
                                   end;
finally
  bmp.free;
end;
end;

procedure lightPiece (Pos: Integer);
var
a,b: Integer;
begin
 a:=Pos and 7;
 b:=Pos shr 3;
 Board.SelectBox.Top:=dY+cell*b;
 Board.SelectBox.Left:=dX+cell*a;
 Board.SelectBox.Transparent:=true;
 Board.SelectBox.Visible:=true;
end;

 procedure View();
begin
 Board.SelectBox.Visible:=false;
 ClearDesk ();
 DrawPieceBoard(WPieceStart,0);
 DrawPieceBoard(BPieceStart,1);
end;
 function SelectPiece(): integer;
var
i: Integer;
begin
   result:=-1;
   if (AllPiece and fun.MaskOneBit[NumPos])>0 then  begin
     for i := 4 downto 0 do  begin
         if ((WPieceStart[i] or BPieceStart[i]) and fun.MaskOneBit[NumPos])>0 then  begin
             result:=i;exit;
         end;
     end;
     if (WPieceStart[5] and fun.MaskOneBit[NumPos])>0 then  begin
             result:=5;exit;
     end else begin
             result:=6;exit;
     end;
   end;
end;
procedure TFormBoard.ChessBoardClick(Sender: TObject);
begin
if NumPos>63 then exit;
if NumPos<0 then exit;
View();
end;

procedure TFormBoard.ChessBoardMouseMove(Sender: TObject; Shift: TShiftState; X,
  Y: Integer);
begin
Xmouse:=X+Board.Left;Ymouse:=Y+Board.Top;
NumPos:= ((X-dX) div cell)+8*((Y-dY) div cell);
end;

procedure TFormBoard.FEN1Click(Sender: TObject);
 var pos : string;
begin
 pos:= InputBox('Установить позицию', 'Введите FEN строку', 'rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR');
 if not fun.FenToU64(pos)  then ShowMessage('Ошибка FEN строки');
View();
end;

procedure TFormBoard.FormCreate(Sender: TObject);
begin
//заставляет выполнить все задачи которые накопились в данный момент
Application.ProcessMessages;
if not fun.FenToU64(PosStart) then ShowMessage('Ошибка FEN строки');
Board.Caption := ProgrammDate;
MaskBit.init();
MaskBit.maskLine();
View();
end;

procedure TFormBoard.NClick(Sender: TObject);
begin
 //ShowMessage('Кликнули по '+IntToStr((Sender as TMenuItem).Tag));
 case (Sender as TMenuItem).Tag of
	1 : fun.FenToU64('rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR');
	2 : fun.FenToU64('r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R');
	3 : fun.FenToU64('8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8');
	4 : fun.FenToU64('r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1');
  5 : fun.FenToU64('rnbq1k1r/pp1Pbppp/2p5/8/2B5/8/PPP1NnPP/RNBQK2R');
	6 : fun.FenToU64('r4rk1/1pp1qppp/p1np1n2/2b1p1B1/2B1P1b1/P1NP1N2/1PP1QPPP/R4RK1');
 end;
View();
end;

end.
Last Edit: 26 Нояб 2022 22:41 by alexlaw.

Bitboard в программировании шахмат 27 Нояб 2022 05:24 #24

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 109799
  • Thank you received: 2227
  • Karma: 108
alexlaw wrote:
Примерно как написано тут
Ну там все в целом нормально описано
Есть массивы предопределенных битбордов для фигур.
Есть доска, чужие поля, свои поля занятые... Тоже массивы
Вычисления через битовые операции...
Vladimirovich wrote:
Алгоритм юзает это через ассеблерные операции типа ADD AX, BX (OR, XOR) и пр.
Во много раз быстрее, чем через циклы.
Каждому - своё.

Bitboard в программировании шахмат 27 Нояб 2022 05:27 #25

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 109799
  • Thank you received: 2227
  • Karma: 108
alexlaw wrote:
Кстати абсолютно никакого гемора.
Идею я подчерпнул еще когда входу были кнопочные телефоны и рулил JAVA2ME.
Декомпилировал прогу CHESSMASTER и понял принцип UI.
Ну UCI это не UI
Это протокол передачи данных между движком и UI
Он один для всех. Изобретать его заново?
UCI_(протокол)

Притом UI вообще не нужен на первом этапе.
Можно использовать оболочки типа Арены или Чессбейз и через этот UCI гнать данные

www.playwitharena.de/
Каждому - своё.
Last Edit: 27 Нояб 2022 05:33 by Vladimirovich.

Bitboard в программировании шахмат 27 Нояб 2022 06:33 #26

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 199
  • Thank you received: 10
  • Karma: 1
Vladimirovich wrote:
Притом UI вообще не нужен на первом этапе.
Проги как таковой ещё нет, есть концепция.
Поэтому визуализация важна.
Можно контролировать процесс и не допустить ошибок, которые потом обнаружить невозможно.
UI по сути визуализация и очень помогает.
Кусок кода подключить к внешней проге невозможно.

Bitboard в программировании шахмат 27 Нояб 2022 06:37 #27

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 109799
  • Thank you received: 2227
  • Karma: 108
alexlaw wrote:
Кусок кода подключить к внешней проге невозможно.
Если все сделать по протоколу, то и можно
Все нонешние движки так и делают
У Воблы вообще никакого UI нет, кроме текстового вывода бесполезного
Каждому - своё.

Bitboard в программировании шахмат 27 Нояб 2022 06:37 #28

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 199
  • Thank you received: 10
  • Karma: 1
Аот мы научились тем или иным способом находить атаки всех фигур.
Встает вопрос хранения дополнительной инфы с возможностью быстрого доступа.
Поле - какая фигура, цвет.
Рокеровка, взятия на проходе, превращения,
От этого много зависит.
Что можете посоветовать?

Bitboard в программировании шахмат 27 Нояб 2022 06:51 #29

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 109799
  • Thank you received: 2227
  • Karma: 108
Ну поля все едино наверно

Есть 64-битное число, по биту на поле.
Их много, каждая маска или массив масок отвечает за свою функцию

Например 6 масок для фигур - 6 бит на поле - 2 бита цвет - 00 пусто, 01 - белые, 10- черные (как пример) - типов фигур K,Q,R,B,N,p - еще 3 бита, резерв на что нибудь
Есть маска поля, например 0x01ULL это a1. Вот по ней AND и имеем все данные конкретно для a1.
Но это я так, как пример. Если подумать, то можно и получше :)

Посмотрите у Воблы код для примерных деталей
github.com/official-stockfish/Stockfish
github.com/official-stockfish/Stockfish/...ter/src/bitboard.cpp
Каждому - своё.
Last Edit: 27 Нояб 2022 06:54 by Vladimirovich.

Bitboard в программировании шахмат 27 Нояб 2022 07:12 #30

  • Ruslan73
  • Ruslan73's Avatar
  • OFFLINE
  • Администратор
  • Posts: 36502
  • Thank you received: 825
  • Karma: 58
alexlaw wrote:
Аот мы научились тем или иным способом находить атаки всех фигур.
Встает вопрос хранения дополнительной инфы с возможностью быстрого доступа.
Поле - какая фигура, цвет.
Если битовые доски как тут
pages.cs.wisc.edu/~psilord/blog/data/chess-pages/physical.html
struct ChessBoard
{
	/* The white piece positions */
	Bitboard WhitePawns;
	Bitboard WhiteRooks;
	Bitboard WhiteKnights;
	Bitboard WhiteBishops;
	Bitboard WhiteQueens;
	Bitboard WhiteKing;

	/* The black piece positions */
	Bitboard BlackPawns;
	Bitboard BlackRooks;
	Bitboard BlackKnights;
	Bitboard BlackBishops;
	Bitboard BlackQueens;
	Bitboard BlackKing;

	/* Commonly derived positions */
	Bitboard AllWhitePieces;
	Bitboard AllBlackPieces;
	Bitboard AllPieces;
};
Функция "какая фигура на поле N" ( N- номер поля от 1 до 64) довольно просто пишется.
1) N переводим в битовую доску: bb_n = 1 << N; (битовый сдвиг, синтаксис С)
2) Затем ищем цвет проверяем bb_n & AllWhitePieces если 1 значит белый. если 0 значит проверяем bb_n & AllBlackPieces
3) выяснив цвет знаем какой набор затем масок проверять дальше bb_n & WhitePawns для выявления не пешка ли это и т.п. пока не найдем нужную маску. Как в результате 1 значит нашли тип фигуры.
Функция из полдюжины if. Не очень быстро но это как понимаю обратная сторона битовых досок. Они не для ускорения этого.
Last Edit: 27 Нояб 2022 07:16 by Ruslan73.
Moderators: Grigoriy
Рейтинг@Mail.ru

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