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

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

Bitboard в программировании шахмат №2 15 Апр 2023 08:49 #181

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 107222
  • Thank you received: 2097
  • Karma: 105
alexlaw wrote:
А как назвать такую позицию, если это не связка?
Никак не назвать.

Связка, это когда в тройке средняя фигура ограничена в движениях.
По разным причинам.

Если за ней король, то очень сильно.
А если это притом конь, то абсолютно.

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

Вот это связка черной пешки. Она не может двигаться абсолютно







8/7k/6p1/8/8/3B4/2K5/8 w - - 2 1

А это не абсолютно. Пешка может пойти, но потеряется ладья







8/5k1r/6p1/8/8/3B4/2K5/8 w - - 2 1

А это мифическая связка. Пешка может пойти, ладья потеряется, но пешка станет ферзем







8/5k2/8/8/8/3R2pr/2K5/8 w - - 2 1

Поэтому Вам придется двинуться тут очень глубоко с программой. Это сложно. Нужна оценка позиции и граф ходов.
Без этого понятие связки смысла не имеет.
Каждому - своё.

Bitboard в программировании шахмат №2 15 Апр 2023 09:30 #182

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 194
  • Thank you received: 10
  • Karma: 1
Vladimirovich wrote:
Нужна оценка позиции и граф ходов.

Все это потом ...
Vladimirovich wrote:
Без этого понятие связки смысла не имеет

:glasses: Это нужно для правильной генерации легальных ходов

Bitboard в программировании шахмат №2 15 Апр 2023 12:55 #183

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 194
  • Thank you received: 10
  • Karma: 1
alexlaw wrote:
Сейчас я использую такой алгоритм
1. Убираем свои фигуры
2. Ставим ферзя на место своего короля
3. Находим атаки этого ферзя (из таблиц атак)
4. Находим атакуемых врагов.
5. Подставляем на место своего ферзя (короля) тип врага
6. Находим его атаки
7. Пересечение атак - это луч атаки между врагом и своим королем
8. Ставим свои фигуры на место
9. Если на зтом луче есть одна своя фигура, то она связана

Алгоритм в коде
Warning: Spoiler! [ Click to expand ]


Конечно хотел бы его оптимизировать, может быть есть идеи? :idea:

Bitboard в программировании шахмат №2 17 Апр 2023 19:23 #184

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 194
  • Thank you received: 10
  • Karma: 1
Мои 2 млн позиций в сек просто детский лепет в сравнение с этими ребятами и похоже, что и девчатами. :|
Их код написанный на си++ даёт 16 млрд в сек, это просто очуметь %-)
github.com/ankan-ban/perft_gpu?utm_source=pocket_mylist

Bitboard в программировании шахмат №2 22 Апр 2023 03:36 #185

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 194
  • Thank you received: 10
  • Karma: 1
Немного причесал функции шахов и связок

Лучи шахов

Warning: Spoiler! [ Click to expand ]


Warning: Spoiler! [ Click to expand ]


связки


Warning: Spoiler! [ Click to expand ]


P=1, N=2, K=3, B=5, R=6 и Q=7.
При анализе этих чисел проверяется результат piece_type&4,
и если результат ненулевой, это дальнобойная фигура.
Далее, если результат piece_type&1 отличен от нуля, эта фигура ходит по диагонали,
а если результат piece_type&2 ненулевой, то фигура может двигаться вдоль горизонталей/вертикалей.

Warning: Spoiler! [ Click to expand ]


Принципиального прорыва нет, надо хотя бы на порядок увеличить скорость. :nope:

Warning: Spoiler! [ Click to expand ]
Last Edit: 22 Апр 2023 03:41 by alexlaw.

Bitboard в программировании шахмат №2 22 Апр 2023 07:25 #186

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

Вот эта позиция :O







3Q4/1Q4Q1/4Q3/2Q4R/Q4Q2/3Q4/1Q4Rp/1K1BBNNk w - - 0 1

Warning: Spoiler! [ Click to expand ]








3Q4/1Q4Q1/4Q3/2Q4Q/Q4Q2/3Q4/1Q4Rp/1K1QQQBk w - - 0 1
nodes=230
Last Edit: 22 Апр 2023 07:43 by alexlaw.

Bitboard в программировании шахмат №2 22 Апр 2023 07:49 #187

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 107222
  • Thank you received: 2097
  • Karma: 105
Вторая точно нелегальна. Пешек не хватит на все

А первая очень очень сомнительна. У черных два хода пешкой всего легальных последних. Жрать ей нечего, у белых весь комплект
Король на h1 под пулями попасть не сможет там.
Каждому - своё.

Bitboard в программировании шахмат №2 22 Апр 2023 08:18 #188

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 194
  • Thank you received: 10
  • Karma: 1
Vladimirovich wrote:
А первая очень очень сомнительна.

А мне кажется, что такую позицию очень даже можно получить из начальной.

Bitboard в программировании шахмат №2 22 Апр 2023 08:20 #189

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 107222
  • Thank you received: 2097
  • Karma: 105
alexlaw wrote:
А мне кажется, что такую позицию очень даже можно получить из начальной.
Ну какие последние ходы были черных?
Каждому - своё.

Bitboard в программировании шахмат №2 22 Апр 2023 08:47 #190

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 194
  • Thank you received: 10
  • Karma: 1
Vladimirovich wrote:
alexlaw wrote:
А мне кажется, что такую позицию очень даже можно получить из начальной.
Ну какие последние ходы были черных?
Конечно пешкой h3-h2, а перед ней какой нибудь черной фигурой
Last Edit: 22 Апр 2023 08:48 by alexlaw.

Bitboard в программировании шахмат №2 22 Апр 2023 09:26 #191

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 194
  • Thank you received: 10
  • Karma: 1
Last Edit: 22 Апр 2023 09:28 by alexlaw.

Bitboard в программировании шахмат №2 22 Апр 2023 09:27 #192

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 107222
  • Thank you received: 2097
  • Karma: 105
alexlaw wrote:
Конечно пешкой h3-h2, а перед ней какой нибудь черной фигурой
И все?
Такие позиции всегда раскручиваются от конца. На много може ходов. Называется ретроанализ.

Как король попал на h1?
Вот главный вопрос. Он под таким огнем не пройдет. Но пасаран :)
Каждому - своё.
Last Edit: 22 Апр 2023 09:27 by Vladimirovich.

Bitboard в программировании шахмат №2 22 Апр 2023 09:32 #193

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 194
  • Thank you received: 10
  • Karma: 1
Vladimirovich wrote:
alexlaw wrote:
Конечно пешкой h3-h2, а перед ней какой нибудь черной фигурой
И все?
Такие позиции всегда раскручиваются от конца. На много може ходов. Называется ретроанализ.

Как король попал на h1?
Вот главный вопрос. Он под таким огнем не пройдет. Но пасаран :)

Все получилось - :)
The following user(s) said Thank You: Vladimirovich

Bitboard в программировании шахмат №2 22 Апр 2023 09:45 #194

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 107222
  • Thank you received: 2097
  • Karma: 105
Надо же :)
Каждому - своё.

Bitboard в программировании шахмат №2 30 Апр 2023 20:37 #195

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 194
  • Thank you received: 10
  • Karma: 1
alexlaw wrote:
Конечно хотел бы его оптимизировать, может быть есть идеи? :idea:

Поизучав код
alexlaw wrote:
понял, что мои вычесления линий атак между клетками, необходимо свеси в таблицу.
В таблицы будет находится линия атаки между двумя клетками.
Получается таблица 64 на 64, и ее надо инициализировать в начале программы.
Об этом же написано в CPW

Посмотрим, что выйдет из этого :glasses:
Last Edit: 30 Апр 2023 20:40 by alexlaw.

Bitboard в программировании шахмат №2 01 Май 2023 08:34 #196

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 194
  • Thank you received: 10
  • Karma: 1
alexlaw wrote:
Посмотрим, что выйдет из этого :glasses:
B Шахматной википедии описано, как это сделать.
Я сделал по своему :) , т.к. эта таблица будет заполнена при запуске проги, то скорость не критична.
1.Сначала заполняем массивы лучей из каждой клетки во все 8 направлений

Warning: Spoiler! [ Click to expand ]


Буквы в названии Line - указывают направление.

2.Далее перебираем все пары клеток и находим лучи между ними

Warning: Spoiler! [ Click to expand ]


3.Важно, при нахождении луча между клетками, в виде пересечений двух лучей LineXY - выбрать правильное направление

Warning: Spoiler! [ Click to expand ]


Лучи должны быть направлены друг к другу, иначе пересечение будет равно нулю.

Warning: Spoiler! [ Click to expand ]


Для вертикалей и горизонталей не составит труда узнать, равны или нет они для дух клеток.

Для диагоналей и антидиагоналей алгоритм такой.

Всего на доске 15 диагоналей и 15 антидиагоналей

Warning: Spoiler! [ Click to expand ]


Для наглядности повернем доску влево на 45 градусов

Warning: Spoiler! [ Click to expand ]


Warning: Spoiler! [ Click to expand ]


Для быстрого нахождения нужных диагоналей введем два массива

letRotateLeft45Indx: array [0..63] of Integer =(0, 1,2,3,4,5,6,7,1,2, 3, 4,5,6, 7,8,2,3,4,5, 6, 7,8,9,3,4,5,6,7,8, 9, 10,4,5,6,7,8,9,10, 11, 5, 6,7,8,9,10,11,12,6, 7, 8, 9,10,11,12,13,7,8,9, 10, 11, 12,13,14);
numRotateLeft45Indx: array [0..63] of Integer =(7, 6,5,4,3,2,1,0,8,7, 6, 5,4,3,2,1,9,8,7,6, 5, 4,3,2,10,9,8,7,6,5,4, 3,11,10,9,8,7,6,5,4, 12, 11,10,9,8,7,6,5,13, 12, 11, 10,9,8,7,6,14,13,12,11, 10, 9,8,7);

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

Выше на рисунке один слон на c6 (поле - 18), слон на g2 (поле - 54)
Warning: Spoiler! [ Click to expand ]


Оба слона находятся на 7 антидиагонали

numRotateLeft45Indx[18]=7
numRotateLeft45Indx[54]=7

Как то так :)

Bitboard в программировании шахмат №2 05 Май 2023 17:13 #197

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 194
  • Thank you received: 10
  • Karma: 1
alexlaw wrote:
Посмотрим, что выйдет из этого :glasses:
Нет - это не тот путь :nope:
Пробовал разные оптимизации участков кода, но хочется скачка, а его пока нет.
Из последнего попробовал последовательность товарища де Брейна (он же де Бройн,он же де Брюйн,он же де Брюин,он же Гоша) :)
для нахождения самого младшего бита
function  get_ls1b_index(bb:UInt64):integer;
const
index64: array [0..63]  of  integer = (
		0, 1, 48, 2, 57, 49, 28, 3,
		61, 58, 50, 42, 38, 29, 17,  4,
		62, 55, 59, 36, 53, 51, 43, 22,
		45, 39, 33, 30, 24, 18, 12,  5,
		63, 47, 56, 27, 60, 41, 37, 16,
		54, 35, 52, 21, 44, 32, 23, 11,
		46, 26, 40, 15, 34, 20, 31, 10,
		25, 14, 19, 9, 13, 8, 7, 6
		);
debruijn64:UInt64 = $03f79d71b4cb0a89;
begin
 result:=index64[((bb and -bb) * debruijn64) shr 58];
end;

В принципе я представляю где слабое место, это место, где есть ветвление (if), значит есть куда рыть.
Я все же хочу добится 20 млн позиций в секунду.

Bitboard в программировании шахмат №2 12 Май 2023 10:16 #198

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 194
  • Thank you received: 10
  • Karma: 1
Шахматный движок С++ #1 | Магические битборды, PEXT, PDEP
Last Edit: 12 Май 2023 11:01 by Vladimirovich. Reason: link corrected

Bitboard в программировании шахмат №2 21 Май 2023 06:19 #199

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 194
  • Thank you received: 10
  • Karma: 1
Попытался поразбираться c PEXT и PDEP
а именно програмно определить поддерживает процессор или нет.
Как следует из Набор инструкций битовой манипуляции - Bit manipulation instruction set эти инструкции входят в набор - BMI2 (набор команд управления битами 2).
POPCNT - подсчет бит - это ABM (Advanced Bit Manipulation), Intel считает POPCNTчастью SSE4.2, а LZCNT- частью BMI1.
Сразу столкнулся с непоняткой - первым делом нужно определить поддерживает ли процессор cpuid.
Для этого нужно проверить бит 21
function TestCPUID: Boolean;
begin
  asm
    mov Result, 0
         Pushfd // Press EFLAGS Stack
         POP EAX // Remove EFLAGS
    mov ecx, eax
         XOR EAX, 200000H // Modify 21st
    push eax
         POPFD // Put the changed EFLAGS in the extension flag
    pushfd
         POP EAX // Remove EFLAGS again
         XOR EAX, ECX // Judgment Whether
    jz @end
    mov Result, 1
    @end:
  end;
end;

Итак у меня поддерживает.

Дальше проверяем поддержку POPCNT - бит 23 и опа ...
Вроде у меня не поддерживает, но протестил вышеупомянутых девочек и мальчиков (у них есть скомпилированные проги в гитхаб)


perft_64bit_plain_no_popcnt.jpg



perft_64bit_plain_popcnt.jpg


Видно что у меня поддерживат POPCNT.

Пока не понял, что с этим делать.

Кстати кому интересно можете почитать диссертацию одного товарища, как обойтись без PEXT и PDEP

Диссертация

Bitboard в программировании шахмат №2 21 Май 2023 06:25 #200

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 107222
  • Thank you received: 2097
  • Karma: 105
alexlaw wrote:
Видно что у меня поддерживат POPCNT.

Пока не понял, что с этим делать.
Вообще разработчики движков разные релизы выкладывают для разных процессоров
Например stockfishchess.org/download/
Так проще, полагаю.
Каждому - своё.

Bitboard в программировании шахмат №2 25 Май 2023 20:20 #201

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 194
  • Thank you received: 10
  • Karma: 1
Побеседовал я тут немного с ChatGPT.

pdep.jpg


Warning: Spoiler! [ Click to expand ]



popcnt.jpg


Warning: Spoiler! [ Click to expand ]



popcnt1.jpg


Warning: Spoiler! [ Click to expand ]



popcnt2.jpg

Bitboard в программировании шахмат №2 30 Май 2023 05:09 #202

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 194
  • Thank you received: 10
  • Karma: 1
Fancy Magic и Magic Bitboard являются двумя разными подходами к нахождению атак скользящих фигур в шахматах. Оба метода используют принцип "магических чисел" для эффективного вычисления атаки фигуры на определенные позиции на шахматной доске.

Основное отличие между Fancy Magic и Magic Bitboard заключается в способе организации магических чисел и их применении.

Magic Bitboard:
Magic Bitboard основан на использовании магических чисел и таблицы сдвигов (shift table). Каждая клетка шахматной доски имеет связанный с ней битовый набор (bitboard), где биты представляют наличие или отсутствие фигуры на данной клетке. Затем для каждой скользящей фигуры (такой как ладья, слон или ферзь) вычисляются магические числа, которые позволяют эффективно определить атаки фигуры на различные позиции на доске. При помощи таблицы сдвигов и магических чисел производится быстрое и эффективное вычисление возможных атак фигуры.

Fancy Magic:
Fancy Magic, с другой стороны, представляет собой более совершенный и продвинутый метод для вычисления атак скользящих фигур. Он использует несколько более сложные алгоритмы и структуры данных, чтобы достичь более высокой производительности. Fancy Magic применяет понятие "разорванных индексов" (disjoint indices), которое позволяет эффективно разбить таблицу атаки на несколько меньших таблиц и применять к ним вычисления с помощью битовых операций. Это улучшает кэширование и уменьшает необходимое количество памяти для хранения таблицы атак.

В обоих случаях использование магических чисел и таблиц сдвигов позволяет существенно ускорить вычисления атак скользящих фигур. Fancy Magic может предоставить еще большую эффективность и производительность по сравнению с Magic Bitboard за счет использования более сложных алгоритмов и структур данных.

Вот пример псевдокода, демонстрирующего применение Fancy Magic для вычисления атаки скользящих фигур (например, ладьи) на шахматной доске:

Warning: Spoiler! [ Click to expand ]


Это примерный псевдокод, который демонстрирует основные шаги Fancy Magic: инициализацию магических чисел и таблиц сдвигов, генерацию релевантной занятости для каждой позиции, вычисление магического индекса, вычисление атаки фигуры с учетом занятости клеток и, наконец, использование Fancy Magic для получения возможных атак. Обратите внимание, что детали реализации Fancy Magic могут отличаться в зависимости от конкретной реализации и используемого языка программирования.

Bitboard в программировании шахмат №2 01 Июнь 2023 10:37 #203

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 194
  • Thank you received: 10
  • Karma: 1
Поколдовал с разными магиями

test_perft.jpg

Bitboard в программировании шахмат №2 01 Июнь 2023 10:39 #204

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 194
  • Thank you received: 10
  • Karma: 1
Магия
Warning: Spoiler! [ Click to expand ]


Warning: Spoiler! [ Click to expand ]

Bitboard в программировании шахмат №2 01 Июнь 2023 20:56 #205

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 194
  • Thank you received: 10
  • Karma: 1
Постарался убрать ненужные для моего компилятора директивы препроцессора.
Препроцессор C/C++ (англ. pre processor, предобработчик) — программа, подготавливающая код программы на языке C/C++ к компиляции.
Хочу код (C) 2007 Pradyumna Kannan использовать в своей проге на делфи.
Так легче преобразовать с одного языка на другой.

magicmoves.c

Warning: Spoiler! [ Click to expand ]


magicmoves.h

Warning: Spoiler! [ Click to expand ]


Посмотрим, что выйдет из этого

Bitboard в программировании шахмат №2 03 Июнь 2023 06:58 #206

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 194
  • Thank you received: 10
  • Karma: 1
alexlaw wrote:
Посмотрим, что выйдет из этого

Реализовал у себя код (C) 2007 Pradyumna Kannan.

Метод - #define VARIABLE_SHIFT


test030623.jpg


Пока не очень ясно, лучше он или нет стандартного метода

Стандартный метод
// get bishop attacks
function get_bishop_attacks(square:TBoard_squares;occupancy:UInt64):UInt64;
begin
occupancy:=occupancy and bishop_masks[square];
occupancy:=occupancy * bishop_magic_numbers[square];
occupancy:=occupancy shr (64 - bishop_relevant_bits[square]);
// return bishop attacks
result:=bishop_attacks[square][occupancy];
end;

VARIABLE_SHIFT
// get bishop attacks  Copyright (C) 2007 Pradyumna Kannan.
function get_bishop_attacks(square:TBoard_squares;occupancy:UInt64):UInt64;
begin
occupancy:=occupancy and bishop_masks[square];
occupancy:=occupancy *  magicmoves_b_magics[Integer(square)];
occupancy:=occupancy shr magicmoves_b_shift[Integer(square)];
// return bishop attacks
result:=bishop_attacks[square][occupancy];
end;

Тут ребята пишут о более быстрой генерации на основе код (C) 2007 Pradyumna Kannan

A Faster Magic Move Bitboard Generator?

Bitboard в программировании шахмат №2 03 Июнь 2023 07:11 #207

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 194
  • Thank you received: 10
  • Karma: 1
Или я туплю :)
Смотрю и непойму -, а в чем между этими подходами разница разница? :dontknow:
Только разные магические числа и сдвиги :(

Bitboard в программировании шахмат №2 03 Июнь 2023 08:16 #208

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 49494
  • Thank you received: 132
  • Karma: 17
давно программеры прошли через всё это, лучшего не придумаете (скорее худшее) - комп давно побил гроссов :tired:

Bitboard в программировании шахмат №2 03 Июнь 2023 08:31 #209

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Дьяк
  • Posts: 194
  • Thank you received: 10
  • Karma: 1
Хайдук wrote:
лучшего не придумаете
На самом деле, я не пытаюсь изобрести что-то новое.
Как раз и хочу взять и реализовать у себя, лучшее из того, что придумали умные люди за 50-70 лет.
И вообще, я получаю от этого удовольствие :)
The following user(s) said Thank You: Andralex

Bitboard в программировании шахмат №2 03 Июнь 2023 08:33 #210

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 49494
  • Thank you received: 132
  • Karma: 17
:cool:
Moderators: Grigoriy
Рейтинг@Mail.ru

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