Магические битборды

Сделал генератор на магических битбордах. Копировать готовое решение от Pradu не хотелось, поэтому - полтора часа медитаций над PDF-ом, столько же на написание кода, и две ночи на самые сложные поля - A1 и H1 для ладьи (штук по 5 миллиардов псевдослучайных проб на каждое). Множители для остальных полей сгенерировались в течение минут.

Вроде работает. Прирост скорости порядка 10%.

Магия происходит. Простым смертным лучше не соваться.

Да всё просто. В двух словах, алгоритм такой.

Надо найти по битборду с занятыми полями битборд с атаками ладьи (слона) с заданного поля.
Для этого:

1) Делаем AND битборда занятости с только теми полями, которые влияют на атаки. Для ладьи на любом поле битборд-маска состоит из 12 единиц. Например, для a1 это поля a2...a7, b1...g1 (поля a8 и h1 не входят, т.к. их атакованность ладьёй с a1 не зависит от того, стоит ли на них какая-нибудь фигура)
2) Умножаем маскированный битборд на МАГИЧЕСКОЕ ЧИСЛО ДЛЯ ЛАДЬИ НА А1.
3) Берём от произведения 12 старших разрядов (сдвигом).
4) Получаем 12-разрядное число, которое используем как индекс в предвычисленной таблице атак.

МАГИЧЕСКОЕ ЧИСЛО для каждого поля доски находим методом Монте-Карло, чтобы не было коллизий. Будет два массива, 64 числа для ладьи и 64 для слона. Маски для атак - тоже предвычисленные константы.

Процедура умножения и сдвига имеет название "perfect hashing". Она тесно связана с одним из алгоритмов для поиска LSB.

А почитать можно много где.
Ключевые слова: Pradu, magic bitboards, de Bruijn, perfect hashing.

Начать лучше всего вот с этой статьи: http://www.prism.gatech.edu/~gtg365v/Buzz/research/magic/Bitboards.pdf

> LSB = Bb & -(long long)Bb;

Это выражение даст только 64-БИТНОЕ число, хотя и весьма специального вида. А нужно - НОМЕР установленного бита. В диапазоне от 0 до 63. Т.е. нужно эти 64 специальных 64-битных числа захэшировать в диапазон таблицы. Вот для этого и нужен множитель и сдвиг.

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

Например, rotated bitboards у меня уменьшают скорость perft, но увеличивают скорость анализа.

Уверен, что не Греко. Perft у меня вообще очень медленный (см. соответствующую ветку).
А knps большие частично из-за того, что в ФВ отсечений мало.

Всё по-простому, без преждевременных оптимизаций.
64 * (2^12) для ладей и 64 * (2^10) для слонов.
Знаю, что можно меньше, но нет времени на долгий поиск коэффициентов. Готовые брать не хочу принципиально

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