Главная » Алгоритмы, Игры » BitBoard

0

— это изощренная битовая техника генерации перемещений и оценки позиции. Она использует следующее понятие: массив игры в шахма­тах представлен 64 клетками. Взяв 64-битовое число без знака, можно полу­чить некоторое битовое представление позиции, если биты, соответствую­щие фигурам позиции, установить в 1. Например, все белые пешки в бито­вой нотации можно представить одним числом:

00000000 00000000 00000000 00000000 00000000 00000000 11111111 00000000

Первый ход е2-е4 будет выглядеть так:

00000000 00000000 00000000 00000000 00001000 00000000 11110111 00000000

Перед началом счета у нас есть инициализированные следующие структуры данных:

?    списки фигур для белых и черных;

?    64-битовые числа-маски:

•        AiiBiack — все черные фигуры;

•        Aliwhite — все белые фигуры;

•         BiackPawns — черные пешки;

•        whitePawns — белые пешки;

?    массив вычисленных заранее битовых масок для возможных перемеще­ний коня и короля для каждой клетки доски;

?    четыре массива для каждой стороны, содержащие данные, сколько на каждой горизонтали, вертикали, восходящей и нисходящей диагоналях находится фигур.

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

Исходный массив игры выглядит как’следующий:

Пешки бьют по диагонали. Сдвинув это число влево на 9, мы получим все поля, битые пешками налево. Самый левый столбец (х = о) при таком сдви­ге может стать самым правым (х = 7). Для этого мы должны к результату применить поразрядное логическое И со следующей маской:

Назовем эту маску Rout. Аналогичная маска для левой стороны будет Lout. Тогда, чтобы получить поля, битые белыми пешками, нужно:

( (WhitePawn «9) & (~ROut)) | ( (WhitePawn « 7) & (~LOut))

Применив эту маску с операцией И со всеми черными фигурами, мы полу­чим все взятия белых пешек:

PawnCap = (

( (WhitePawn « 9) & (~ROut)) | ( (WhitePawn « 7) & (~LOut)) ) & AllBlack;

Допустим, это число:

Оно может содержать несколько взятий. Как их извлечь? Это целая область двоичной казуистики. Рассмотрим самый простой способ:

X & -X

Эта операция возвращает самый младший (самый правый) бит числа х. Для иллюстрации этого попробуем вычислить вручную:

0010 1000 исходное число

1101 0111 NOT

1101 1000 +1

      И с исходным числом

0000 1000 результат

Чтобы получить двоичное представление отрицательного числа, нужно взять инвертированное число (1 меняется на 0) и добавить к нему 1.

Чтобы извлечь из PawnCap младший бит (одно взятие), нужно

move = PawnCap & -PawnCap;

Мы получим число:

00000000 00000000 00000000 00000100 00000000 00000000 00000000 00000000

Если нужно убрать полученное перемещение из исходной маски, можно

PawnCap = PawnCap & (-move);

Может возникнуть необходимость не только в маске целевой клетки, но и в ее индексе. Извлечение его усложняет задачу на порядок. Самый простой способ — использовать массив перекодировки от 0 до 65 535. В каждой клетке массива задано, какой индекс соответствует числу с данным единст­венным установленным битом. Исходная маска 64-разрядная. Это число следует декодировать в четыре приема, т. к. в 64-битовом числе содержится четыре 16-битовых.

Значение клеток массива перекодировки:

Номер бита Индекс массива Значение

0             1           15

1             2           14

2             4           13

3             8                12

4             16         11

5             32         10

6             64         9

7             128       8

8             256       7

9             512       6

10            1024      5

11            2048      4

12            4096      3

13            8192      2

14            16384     1

15            32768     0

#define BITBOARD unsigned      int64

fdefine MASK 65535

int Index0_63(BITBOARD move) {

BITBOARD bank;

bank = (move » 48) & MASK; if(bank) return hlat[bank] ; bank = (move » 32) S MASK; if(bank) return hlat[bank] + 16; bank = (move » 16) S MASK; if(bank) return hlat[bank] + 32; bank = move & MASK; if(bank) return hlat[bank] + 48; _ASSERT(0); return …;

}

Просто, не правда ли?!

Если нам нужно получить взятия короля или коня, мы просто делаем опе­рацию поразрядного И маски перемещений этой фигуры для конкретной клетки и маски всех фигур противника. Для получения перемещений даль­нобойных фигур используются повернутые (в прямом и переносном смыс­ле) битовые доски. В данном примере используется упрощенный прием. У нас перед началом вычисления инициализированы 4 массива для каждого цвета фигур. В них содержится информация, сколько фигур в каждой вер­тикали, горизонтали и диагоналях. Если диагональ восходящая, то сумма координат всех клеток одинакова. Если нисходящая — разность XY одна для всех клеток диагонали. Массивы корректируются пошагово. Например, пошла белая пешка е2—е4. Ее целевые координаты X = 4, Y = 4. В первом массиве в клетке с индексом X увеличим значение на 1. Во втором масси­ве—в клетке с индексом Y. Остальные два массива нужно корректировать в клетках (X+Y) и (X—Y+8). Соответствующим образом нужно корректиро­вать массивы клеток, откуда переместилась фигура. Далее, например, берем взятия королевы, сканируем вертикаль, только если в первом массиве в клетке X не равно 0. Все остальные лучи берем, если в соответствующих массивах в клетках Y, X+Y, XY+8 не нули. Это просто и достаточно эффек­тивно.

Литература:

Корнилов Е. Н.  Программирование шахмат и других логических игр. — СПб.: БХВ-Петербург, 2005. – 272 е.: ил.

По теме:

  • Комментарии