КвантоФорум :: Bitboard в программировании шахмат №2 (2/10)

Welcome, Guest

Page:
1
2
3
4
5
...
10

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

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

Vladimirovich
OFFLINE
Инквизитор
Posts: 106862
Thank you received: 2079
Karma: 105

У Воблы вот...

github.com/official-stockfish/Stockfish/...aster/src/bitboard.h

constexpr Bitboard AllSquares = ~Bitboard(0);
constexpr Bitboard DarkSquares = 0xAA55AA55AA55AA55ULL;

constexpr Bitboard FileABB = 0x0101010101010101ULL;
constexpr Bitboard FileBBB = FileABB << 1;
constexpr Bitboard FileCBB = FileABB << 2;
constexpr Bitboard FileDBB = FileABB << 3;
constexpr Bitboard FileEBB = FileABB << 4;
constexpr Bitboard FileFBB = FileABB << 5;
constexpr Bitboard FileGBB = FileABB << 6;
constexpr Bitboard FileHBB = FileABB << 7;

constexpr Bitboard Rank1BB = 0xFF;
constexpr Bitboard Rank2BB = Rank1BB << (8 * 1);
constexpr Bitboard Rank3BB = Rank1BB << (8 * 2);
constexpr Bitboard Rank4BB = Rank1BB << (8 * 3);
constexpr Bitboard Rank5BB = Rank1BB << (8 * 4);
constexpr Bitboard Rank6BB = Rank1BB << (8 * 5);
constexpr Bitboard Rank7BB = Rank1BB << (8 * 6);
constexpr Bitboard Rank8BB = Rank1BB << (8 * 7);

constexpr Bitboard QueenSide   = FileABB | FileBBB | FileCBB | FileDBB;
constexpr Bitboard CenterFiles = FileCBB | FileDBB | FileEBB | FileFBB;
constexpr Bitboard KingSide    = FileEBB | FileFBB | FileGBB | FileHBB;
constexpr Bitboard Center      = (FileDBB | FileEBB) & (Rank4BB | Rank5BB);

Каждому - своё.

Reply Quote

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

alexlaw
OFFLINE
Дьяк
Posts: 183
Thank you received: 8
Karma: 1

Ruslan73 wrote:

Если битовые доски как тут

Совершенно верно, доски такие.
На самом деле сначала я тоже шёл по пути который вы предложили, но он не эффективен, и вот почему.
Представьте: генератор ходов выдал нам массив 0...63 ходов из каждого поля. Мы перебираем этот массив и делаем ход. После хода мы должны обновить массивы AllPiece,White или Black, и массив типа фигуры.
Для этого надо прошерстить кучу массивов.Это занимает много времени.
Я сейчас пошел по пути, хранить в двух массивах 0...63 тип и цвет фигур.
В принципе мне кажется это быстрее.
Но не уверен, что это правильный путь.

Reply Quote

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

alexlaw OFFLINE Дьяк Posts: 183 Thank you received: 8 Karma: 1	Vladimirovich wrote: У Воблы вот Не очень понятно для чего эти маски
	Last Edit: 28 Нояб 2022 05:47 by Vladimirovich. Reply Quote

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

Ruslan73
OFFLINE
Администратор
Posts: 35578
Thank you received: 757
Karma: 56

alexlaw wrote:

Представьте: генератор ходов выдал нам массив 0...63 ходов из каждого поля.

Не очень понимаю, о чем Вы. Зачем для полей ходы считать. Играют же фигурами и пешками а не полями. У каждой стороны при её очереди не более 16 фигур и пешек. При разменах число сокращается. Т.е. при каждом ходе 16 массивов максимум. И фигуры и пешки мешают друг другу. В начальной позиции например только 10 массивов с ходами по 2 варианта хода.

Всего 20 возможных ходов. У соперника тоже 20. 20х20=400 вариантов после 2х полуходов. Если Вы их все будете считать всё время без отбрасывания с любыми алгоритмами захлебнетесь в количестве.

Свободу Джулиану Ассанжу!

Last Edit: 27 Нояб 2022 10:31 by Ruslan73.

Reply Quote

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

Vladimirovich
OFFLINE
Инквизитор
Posts: 106862
Thank you received: 2079
Karma: 105

alexlaw wrote:

Не очень понятно для чего эти маски

Ну как...

DarkSquares все черные поля

FileABB вертикаль А

Далее там

constexpr Bitboard QueenSide = FileABB | FileBBB | FileCBB | FileDBB;
Ферзевый фланг

constexpr Bitboard Center = (FileDBB | FileEBB) & (Rank4BB | Rank5BB);
4 центральные клетки

И т.д.

Т.е сразу определяются группы полей, которые интересны движку

Каждому - своё.

Reply Quote

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

Ruslan73 OFFLINE Администратор Posts: 35578 Thank you received: 757 Karma: 56	Для алгоритмов выбора хода наверняка (занимай пешками центр, ладьи на открытые линии и т.п.)
	Свободу Джулиану Ассанжу! Last Edit: 27 Нояб 2022 10:40 by Хайдук. Reply Quote

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

alexlaw
OFFLINE
Дьяк
Posts: 183
Thank you received: 8
Karma: 1

Ruslan73 wrote:

Не очень понимаю, о чем Вы

Чуть выше я написал немного кода.
Правда пока это не генератор ходов, а лишь массив атак фигур.
Примем, что атаки - это массив ходов.
Движку нужно сделать все эти ходы и ответные ходы на какую-то глубину.
Я это имел ввиду.
Вот и надо перебрать всю доску и есть ходы из данного поля то сделатьих все, и сделать ответные ходы.
Как-то так.
Надеюсь не очень запутал)))

Reply Quote

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

alexlaw OFFLINE Дьяк Posts: 183 Thank you received: 8 Karma: 1	Ruslan73 wrote: Для алгоритмов выбора хода наверняка (занимай пешками центр, ладьи на оикрытые линии и т.п.) Вы слишком оптимистичны. Я только в начале пути. Ещё даже нет генератора ходов
	Reply Quote

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

Ruslan73
OFFLINE
Администратор
Posts: 35578
Thank you received: 757
Karma: 56

alexlaw wrote:

Чуть выше я написал немного кода.

Я видел, но поглядев, что нет комментов и названия массивов непонятные бросил.

После прочтения книжки Боба Мартина "Чистый код" и еще парочки по этой теме - только по работе могу непонятный код заставить себя разбирать. В свободное время не могу уже себя заставить. Обленился жутко. Хочется теперь читать код который как детектив читается.
Понятный набор классов, лаконичные, но ёмкие комментарии только по делу, понятные названия методов и т.п..

Свободу Джулиану Ассанжу!

Last Edit: 27 Нояб 2022 19:43 by Ruslan73.

Reply Quote

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

alexlaw
OFFLINE
Дьяк
Posts: 183
Thank you received: 8
Karma: 1

Ruslan73 wrote:

Я видел, но поглядев, что нет комментов и названия массивов непонятные бросил.

Признаю)))
Есть такой грех, иногда не пишу комментариев.
Кстати тоже не могу заставить себя разбирать чужой код.
Тоже лень))
Вот сегодня вроде переборол себя и начал разбирать суть магических квадратов.
Когда соберу мысли попробую воплотить этот метод.
Суть метода понятна, реализация пока не очень понятна.
Суть этого метода у том, что заранее просчитывается и заполняются массивы атак дальнобойных фигур.
А потом просто берется атака из этого массива в зависимости от положения фигур на доске

Reply Quote

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

Ruslan73
OFFLINE
Администратор
Posts: 35578
Thank you received: 757
Karma: 56

Виноват, но я просто не понимаю, что такое "атака фигуры". Меня уже это в ступор вводит.
Понимаю, что такое разрешённые правилами ходы. Ход может сопровождаться взятием либо нет. Взятие -частный случай хода. Один из видов. У пешек исключение- часть ходов обязано быть взятием (удар наискосок и на проходе), часть не может быть взятием (ходы вперед).

Свободу Джулиану Ассанжу!

Last Edit: 27 Нояб 2022 20:32 by Ruslan73.

Reply Quote

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

alexlaw
OFFLINE
Дьяк
Posts: 183
Thank you received: 8
Karma: 1

Ruslan73 wrote:

я просто не понимаю, что такое "атака фигуры"

Попробую объяснить.
Ладья на f7 связана и ходить не может, но в тоже время атакует все поля в соответствии со своим свойством ладьи.
Например она атакует поле f8 и черный король не может туда ходить.
Кстати и свои фигуры она тоже может атаковать.
Т.е. атаку ограничивает только наличие на линии атаки другая фигура. Атак слона на a2 ограничена наличием ладьи на f7.

6k1/5R2/6K1/8/8/8/b7/8 w 0 1

Last Edit: 27 Нояб 2022 21:00 by alexlaw.

Reply Quote

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

Ruslan73
OFFLINE
Администратор
Posts: 35578
Thank you received: 757
Karma: 56

Т.е. это множество полей возможных ходов фигуры Х, которые могут сопровождаться взятием, появись на них вражеская фигура (с игнорированием возможной нелегальности взятия из-за связки фигуры Х со своим королем), плюс множество полей, на которых стоят фигуры или пешки того же цвета, что и Х, "защищаемые" этой фигурой Х?

Свободу Джулиану Ассанжу!

Last Edit: 27 Нояб 2022 21:15 by Ruslan73.

Reply Quote

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

alexlaw
OFFLINE
Дьяк
Posts: 183
Thank you received: 8
Karma: 1

Небольшая ремарка.
Все так как вы описали, только свои фигуры также атакуются.
Простой пример.
Черного слона атакуют обе ладьи.
Это важно например при размене.

8/8/8/8/6B1/8/8/r2b2R1

Last Edit: 27 Нояб 2022 21:29 by alexlaw.

Reply Quote

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

Ruslan73
OFFLINE
Администратор
Posts: 35578
Thank you received: 757
Karma: 56

alexlaw wrote:

свои фигуры также атакуются.

Я про это и написал

плюс множество полей, на которых стоят фигуры или пешки того же цвета, что и Х, "защищаемые" этой фигурой Х

Того же цвета это свои.

Плюс, фигуры и пешки противника, уже находящиеся под ударом (которые можно взять при своём ходе).

Итого
"Множество полей возможных ходов фигуры Х, которые могут сопровождаться взятием, появись на них вражеская фигура (с игнорированием возможной нелегальности взятия из-за связки фигуры Х со своим королем), плюс множество полей, на которых стоят фигуры или пешки того же цвета, что и Х, "защищаемые" этой фигурой Х, плюс поля, на которых стоят пешки и фигуры противника, которые фигура Х может взять при своём ходе."

Свободу Джулиану Ассанжу!

Last Edit: 28 Нояб 2022 05:10 by Ruslan73.

Reply Quote

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

Ruslan73 OFFLINE Администратор Posts: 35578 Thank you received: 757 Karma: 56	Теперь понятней, хотя я бы обозвал это как зона контроля фигуры или поля под контролем или область активности фигуры. FieldsUnderControlOfRook или RookControlArea или RookActivityArea и расписал бы определение в комментах или readme.
	Свободу Джулиану Ассанжу! Last Edit: 28 Нояб 2022 05:35 by Ruslan73. Reply Quote

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

alexlaw OFFLINE Дьяк Posts: 183 Thank you received: 8 Karma: 1	Ruslan73 wrote: Я про это и написал Я просто затупил)))
	Reply Quote

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

Ruslan73
OFFLINE
Администратор
Posts: 35578
Thank you received: 757
Karma: 56

Как её определить - я бы так делал
1) сначала (до всего) создаём битовые доски для всех легальных ходов ладьи например для все 64 полей.
RookLegalMovesFBB[0..63], заполняем их сохраняем.
2) во время хода у нас есть поле N на котором ладья стоит и цвет, 23 например и белый.
Наша битовая доска значит RookLegalMovesFBB[23]. Находим RookLegalMovesFBB[23] AND AllPieces; получаем все фигуры свои и чужие на полях куда может пойти эта ладья. AllPieces это маска где все фигуры и пешки вообще.
Находим все номера полей пересечений, группируем по 2-4м полулиниях лежащих на горизонталях и вертикалях проходящих через 23.
На каждой полулинии находим поле ближайшее к 23му (фигуры под боем или под защитой)
3) отсекаем на полулиниях поля за найденными полями и сами поля и получаем RookPossibleMovesFBB.
4) получаем маски RookPossibleMovesFBB, RookDefendingFBB, RookPossibleCapturesFBB.
RookActivityAreaBB = RookPossibleMovesFBB OR RookDefendingFBB OR RookPossibleCapturesFBB.
F= Fields (поля), BB - bitboard.

Свободу Джулиану Ассанжу!

Last Edit: 28 Нояб 2022 06:13 by Ruslan73.

Reply Quote

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

Vladimirovich
OFFLINE
Инквизитор
Posts: 106862
Thank you received: 2079
Karma: 105

Еще из Воблы может быть интересно и полезно...

Как происходит сдвиг позиции и вообще любой маски-битборда в любом направлении на 1 или 2 клетки (последнее для пешек начальных видимо)

template<Direction D>
constexpr Bitboard shift(Bitboard b) {
  return  D == NORTH      ?  b             << 8 : D == SOUTH      ?  b             >> 8
        : D == NORTH+NORTH?  b             <<16 : D == SOUTH+SOUTH?  b             >>16
        : D == EAST       ? (b & ~FileHBB) << 1 : D == WEST       ? (b & ~FileABB) >> 1
        : D == NORTH_EAST ? (b & ~FileHBB) << 9 : D == NORTH_WEST ? (b & ~FileABB) << 7
        : D == SOUTH_EAST ? (b & ~FileHBB) >> 7 : D == SOUTH_WEST ? (b & ~FileABB) >> 9
        : 0;
}

Каждому - своё.

Reply Quote

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

alexlaw
OFFLINE
Дьяк
Posts: 183
Thank you received: 8
Karma: 1

Ruslan73 wrote:

я бы так делал

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

8/8/8/8/8/8/8/3R4
Берём массив
Array[i,j];i=64,j=64
Где i-,это номер поля 0...63
j-заранее просчитанная маска расположения фигур на горизонтали a1-h1.
Почему 64 различные комбинации, потамучто используем только 6 бит,
Биты a1 и h1 исключаем, т.к. они атакуются всегда, где бы ладья не стояла на первой горизонтали(если нет блокирующих фигур)
Итак индекс i - это местоположение ладьи.
Индекс j-,это различны комбинации блокирующих фигур
А в ячейке массива хранится заранее просчитанная линия атаки.
Теперь достаточно знать расположение ладьи и целочисленную маску расположения других фигур на этой горизонтали и опа- атаки у нас в кармане.
Просто обращением к массиву

Last Edit: 28 Нояб 2022 06:50 by alexlaw.

Reply Quote

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

Vladimirovich
OFFLINE
Инквизитор
Posts: 106862
Thank you received: 2079
Karma: 105

Это была не моя цитата

Вы прочитайте меню Информаци наверху.
alexlaw wrote:

Берём массив
Array[i,j];i=64,j=64
Где i-,это номер поля 0...63
j-заранее просчитанная маска расположения фигур на горизонтали a1-h1.

Биты a1 и h1 исключаем, т.к. они атакуются всегда, где бы ладья не стояла на первой горизонтали(если нет блокирующих фигур)

Здесь, увы, уже массивы не нужны, это полный уход от идеи битбордов.
Исключать что-то это все ненужно.

Маска фигур должна быть одна.
Поле это 1 бит. А всего 64-битное слово для любой маски

typedef uint64_t Bitboard;

Все операции это битовые операции (AND, OR, сдвиги) для минимизации циклов. Они выполняются процессором аппаратно.

Т.е. в самом первом приближении (потом можно улучшить) это предопределенный массив для ладьи BitboardR[64], т.е одномерный, а не двумерный.
Доступ к элементу двумерного гораздо дольше.

Тогда, если у нас есть маска запрещенных полей (1 - разрешено) Bitboard Mask, то определить все поля для ладьи будет

// d1 константа для индекса поля d1. Это неправильно :) индекс надо брать из позиции, но тут для ясности
Bitboard MovesR = BitboardR[d1] & Mask;

Все! Атомарная операция над двумя 64-числами.
Самое сложное посчитать маску Mask, там посложнее, но суть, надеюсь понятна.

Каждому - своё.

Last Edit: 28 Нояб 2022 07:13 by Vladimirovich.

Reply Quote

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

Хайдук OFFLINE Наместник Posts: 49379 Thank you received: 130 Karma: 16	откуда у ув. админов столько знаний о компьютерных шахматах? нервно курит в сторонке бедный чучхе
	Reply Quote

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

Ruslan73
OFFLINE
Администратор
Posts: 35578
Thank you received: 757
Karma: 56

alexlaw wrote:

Теперь посчитайте сколько нужно будет операций, чтобы найти атаки в реальной позиции.

Понятность и простота алгоритма тоже важные параметры. Сначала кмк надо сделать что-то работающее, пусть и не идеальное и только потом оптимизировать узкие места. Не факт что именно это будет узким местом, а не оценка позиции например.

Свободу Джулиану Ассанжу!

Last Edit: 28 Нояб 2022 07:30 by Ruslan73.

Reply Quote

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

Vladimirovich OFFLINE Инквизитор Posts: 106862 Thank you received: 2079 Karma: 105	Иллюстрация Маска BitboardR[d1] (короли поставлены, а то движок не хочет позу ставить) Желтый единички Маска запрещений - Красный 0, остальное 1 (при белом коне d6 тоже красное будет) И вот просто операция AND битовая
	Каждому - своё. Reply Quote The following user(s) said Thank You: Ruslan73

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

Ruslan73 OFFLINE Администратор Posts: 35578 Thank you received: 757 Karma: 56	Хайдук wrote: откуда у ув. админов столько знаний о компьютерных шахматах? нервно курит в сторонке бедный чучхе Вы ув.Хайдук так хорошо про нас думаете, что даже не хочется Вас разочаровывать.
	Свободу Джулиану Ассанжу! Reply Quote

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

Ruslan73
OFFLINE
Администратор
Posts: 35578
Thank you received: 757
Karma: 56

Vladimirovich wrote:

Маска BitboardR[d1] (короли поставлены, а то движок не хочет позу ставить)
Желтый единички

Я так понимаю автора как раз интересует как битовыми операциями найти этого ближайшего к ладье коня на линии d и отсечь оставшиеся поля. На этой линии может ведь не одна фигура и пешка стоять, а много. Я предлагал на каждой полулинии расстояния считать до каждой фигуры и выбирать минимальное, но говорят мол долго.

Свободу Джулиану Ассанжу!

Reply Quote

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

Ruslan73
OFFLINE
Администратор
Posts: 35578
Thank you received: 757
Karma: 56

alexlaw wrote:

j-заранее просчитанная маска расположения фигур на горизонтали a1-h1.

Ничего не понял, что это за маски, зачем они нужны? Я в коде Вашем на этом сразу и сломался, было непонятно нафига эти массивы нужны по каким-то фиксированным горизонталям и что это. Ладья в любой точке доски может оказаться в партии. При чем тут а1-h1?

Свободу Джулиану Ассанжу!

Last Edit: 28 Нояб 2022 07:56 by Ruslan73.

Reply Quote

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

Ruslan73 OFFLINE Администратор Posts: 35578 Thank you received: 757 Karma: 56	Я бы взял всего 1 массив RookLegalMovesFBB[0..63] 64битных чисел. В каждом элементе n лежит 1 64 битная битовая доска которая битами показывает, куда может пойти ладья из поля с номером n. 1 массив и все возможные ходы ладьи покрыты.
	Свободу Джулиану Ассанжу! Last Edit: 28 Нояб 2022 08:00 by Ruslan73. Reply Quote

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

alexlaw
OFFLINE
Дьяк
Posts: 183
Thank you received: 8
Karma: 1

www.pvsm.ru/game-development/17378?utm_s...=l9zgbf9nj6679415818
Если вы внимательно читали эту статью то поймете о чем я говорю.
Цитата:
"Мы повторяем это для всех четырех направлений с той лишь разницей, что для минусовых направлений мы не используем FirstOne(), так как нам нужно находить последнюю блокирующую фигуру. Вмето этого мы переключаемся на LastOne(). Теперь код для подсчета атак слона во всех четырех направлениях выглядит так:

diag_attacks=plus7[F5];
	blockers=diag_attacks & occupied_squares;
	blocking_square=FirstOne(blockers);
	bishop_attacks=diag_attacks^plus7[blocking_square];
	diag_attacks=plus9[F5];
	blockers=diag_attacks & occupied_squares;
	blocking_square=FirstOne(blockers);
	bishop_attacks|=diag_attacks^plus9[blocking_square];
	diag_attacks=minus7[F5];
	blockers=diag_attacks & occupied_squares;
	blocking_square=LastOne(blockers);
	bishop_attacks|=diag_attacks^minus7[blocking_square];
	diag_attacks=minus9[F5];
	blockers=diag_attacks & occupied_squares;
	blocking_square=LastOne(blockers);
	bishop_attacks|=diag_attacks^minus9[blocking_square];

Цитата:
"Это выливается в большое количество операций с AND и OR и необходимостью маскирования, плюс использование функций FirstOne()/LastOne() для обнаружения блокирующего поля. Это весьма дорого, но раз уж с булевыми операторами большая часть работы делается параллельно, это все же может себя оправдать. Однако есть лучший путь, который позволяет избавиться от вызовов FirstOne()/LastOne() и который обрабатывает всю диагональ/горизонталь/вертикаль за один шаг, а не за два, как в этом методе."

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

Last Edit: 28 Нояб 2022 08:08 by alexlaw.

Reply Quote