Получение битовых масок для битбордов

Question

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

8 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 0 0 
6 0 0 0 0 0 0 0 0 
5 0 0 0 0 0 0 0 0 
4 0 0 R 0 0 0 0 0 
3 0 0 0 0 0 0 0 0 
2 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 
  a b c d e f g h

Учитывая битборд, который представляет пустые квадраты (или занятые квадраты, что проще) и псевдодействующий ход Rf4 (ладья может перемещаться с c4 на f4), как получить маску для квадратов d4-e4 (исключая источник и квадраты назначения)?

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

РЕДАКТИРОВАТЬ: битборд представлен ulong / unsigned int64, с каждой пачкой из 8 бит, представляющих ранг / строку фактической платы.

Answer 1

Я собираюсь сделать некоторые предположения здесь: плата хранится в виде 64-битного числа, каждый 8-байтовый блок представляет строку. Каждый бит в строке представляет столбец (a..h). У вас есть начальная и конечная позиции в виде нулевых координат. т.е.: start = "C4" = [2,3]; end = "F4" = [5,3]

Для горизонтальных перемещений с увеличивающимися столбцами вы можете рассчитать пройденное расстояние: d = (F4-C4 = 3). Вычтите 1, чтобы исключить пункт назначения, затем "след" t битов d-1 равен t = (1<<(d-1))-1. Сдвиньте след рядом с исходной частью, чтобы получить маску M: M = t<<(start.row*8 + start.column+1).

Это эквивалентно M = ((1<<d)-2)<<(start.row*8 + start.column)

Для горизонтальных перемещений в другую сторону:

 d = (C4-F4 = -3)
 t = (1<<(-d-1))-1
 M = (t<<dest.column+1)
 //-or-
 M = ((1<<-d)-2)<<(dest.row*8 + dest.column)

Для вертикально увеличивающихся ходов:

 d = (C7-C4 = 3)
 t=(1<<8)
 (d-1) times: { t |= (t<<8)}
 M = t << (start.row*8 + start.column)

Для вертикально уменьшающихся ходов:

 d = (C4-C7 = 3)
 t=(1<<8)
 (d-1) times: { t |= (t<<8)}
 M = t << (dest.row*8 + start.column)

Для вертикальных перемещений вы можете заменить петлю над d, сохранив максимальный «вертикальный след» VT = 0x0101010101010101 = 72340172838076673. Затем замаскируйте правильное количество бит для фактического хода.

Это уменьшает накопление до M = (VT & ((1<<(d*8)) - 2)) << (row*8+column).

Возможно, вы могли бы сделать что-то подобное для диагональных ходов. Начните с максимального диагонального следа DT = 0x0102040810204080, примените маску, чтобы уменьшить ее до d установленных бит, и перейдите к начальной или конечной позиции, в зависимости от того, что ближе к краю. Это потребует тщательного тестирования, чтобы убедиться, что не было краевых случаев, которые обернуты в неправильный ряд.

Отредактировано для исключения источника и получателя и исправления разовых ошибок

Answer 2

Если не считать предварительных расчетов и генерации всех возможных масок для ходов фигур (определенная вероятность), я ожидаю, что создание масок во время выполнения, скорее всего, будет столь же дорогим по времени, как и простой 'поиск каждого квадрата 'подход.

Answer 3

Получите вектор направления (dx, dy) / dx

В этом случае (1,0)

Затем увеличивайте текущую позицию с этим вектором до тех пор, пока не достигнете места назначения. В процессе увеличения / присвоения соответствующих ячеек матрицы.