Я

Алиса

Разберу пример реализации битбордов с магическими числами для атак слона в шахматной программе.

Основы нумерации полей

Поля нумеруются от 0 до 63:

0 → A1, 7 → H1;
56 → A8, 63 → H8.

Структура данных

cpp
// Предварительно вычисленные таблицы
uint64_t bishopAttacks[64][512]; // 32 KB: 64 поля × 512 вариантов

// Магические данные для каждого поля
struct Magic {
    uint64_t mask;   // Маска релевантных полей для слона
    uint64_t magic;  // Магическое число
    int shift;       // Величина сдвига
};

Magic bishopMagics[64];

Алгоритм расчёта атак

Функция для получения битборда атак слона:

cpp
uint64_t getBishopAttacks(int square, uint64_t occupancy) {
    // 1. Применяем маску к занятости — оставляем только релевантные поля
    occupancy &= bishopMagics[square].mask;
    
    // 2. Умножаем на магическое число — хешируем состояние занятости
    occupancy *= bishopMagics[square].magic;
    
    // 3. Сдвигаем вправо — получаем индекс в таблице
    occupancy >>= bishopMagics[square].shift;
    
    // 4. Берём готовый битборд атак из таблицы по индексу
    return bishopAttacks[square][occupancy];
}

Как это работает

Маска (mask). Для каждого поля слона заранее вычисляется маска, которая выделяет только те поля на диагоналях, которые могут повлиять на его атаки (без крайних полей). Например, для поля E4 (позиция 36) маска будет содержать биты для всех полей на двух диагоналях через E4.
Магическое число (magic). Это 64‑битное число, подобранное так, чтобы умножение на него «перемешивало» биты занятости и минимизировало коллизии при хешировании.
Сдвиг (shift). После умножения результат сдвигается вправо на фиксированное число бит (обычно 64 − N, где N — количество релевантных битов), чтобы получить компактный индекс.
Таблица атак (bishopAttacks). Предварительно вычисленная таблица, где для каждой комбинации занятости (после хеширования) хранится готовый битборд всех полей, которые слон может атаковать с данного квадрата.

Пример для конкретного поля

Рассмотрим слона на поле D4 (индекс 28):

Маска. Содержит биты для полей на диагоналях C3–A1 и E3–H6 (исключая крайние поля, которые не влияют на атаки).
Магическое число. Например, 0x123456789ABCDEF0 (значение подбирается алгоритмически).
Сдвиг. Допустим, 53 (т. е. оставляем 11 старших бит: 64 − 53 = 11).
Индекс. После умножения и сдвига получаем число от 0 до 511.
Битборд атак. В bishopAttacks[28][index] хранится 64‑битное число, где биты 1 соответствуют полям, атакуемым слоном с D4 при текущей занятости.

Предварительные вычисления

На этапе инициализации программы:

Для каждого из 64 полей:
- генерируются все возможные комбинации занятости релевантных полей (например, 2¹¹ = 2048 вариантов для центральных полей);
- для каждой комбинации вручную рассчитывается битборд атак (с учётом блокирующих фигур);
- подбираются magic и shift, чтобы хеширование не вызывало коллизий;
- заполняются bishopAttacks[square][...].
Результаты сохраняются в статических таблицах.

Преимущества подхода

Скорость. Расчёт атак занимает несколько процессорных инструкций (AND, MUL, SHR, MOV).
Эффективность. Вместо перебора всех диагоналей и проверки на блокирующие фигуры используется одно обращение к памяти.
Масштабируемость. Аналогичная схема применяется для ладьи и ферзя (с другими масками и магическими числами).

Ограничения

Память. Требуется ~32 KB для слонов и ~256 KB для ладей.
Сложность инициализации. Подбор магических чисел — ресурсоёмкая задача (обычно выполняется заранее и «зашивается» в код).

Хотите, я уточню какой‑то этап подробнее или приведу дополнительные примеры?

Я

Алиса

Вы правы — формулировка «все поля кроме крайних» слишком упрощена. Разберу подробно, как на самом деле строится маска релевантных полей для слона.

Что такое «релевантные поля»

Это не просто «все кроме крайних», а только те поля на диагоналях слона, которые могут влиять на дальность его атаки при наличии фигур. Крайние поля (на границах диагоналей) обычно не включаются, потому что:

они не блокируют движение слона дальше (за ними уже нет клеток);
их занятость не меняет набор атакуемых полей.

Как формируется маска

Для каждого квадрата доски маска вычисляется индивидуально — она зависит от положения слона. Маска включает только те биты, где занятость фигур может изменить атаку слона.

Шаги построения маски:

Берём исходное поле слона (например, e4 — индекс 28).
Проходим по всем четырём диагоналям от этого поля.
На каждой диагонали включаем в маску все поля между исходным полем и краем доски, исключая само исходное поле и крайние поля диагонали.
Полученная совокупность полей и есть маска.

Примеры масок

Пример 1. Слон на e4 (индекс 28)
Диагонали:

a8–h1: поля d5, c6, b7 (не включаем a8 и e4);
a2–b1: поля f3, g2 (не включаем h1 и e4);
h4–e1: поля f2, g3 (не включаем h4 и e4);
a4–d1: поля b3, c2 (не включаем a4 и e4).

Маска для e4: биты для полей d5, c6, b7, f3, g2, f2, g3, b3, c2.

Пример 2. Слон на a1 (индекс 0)
Диагонали:

a1–h8: поля b2, c3, d4, e5, f6, g7 (не включаем a1 и h8);
других диагоналей нет.

Маска для a1: биты для b2, c3, d4, e5, f6, g7.

Пример 3. Слон на d4 (индекс 27)
Диагонали:

a1–g7: c3, b2, a1 (крайнее) — берём c3, b2;
h1–a8: e3, f2, g1 (крайнее) — берём e3, f2;
a4–d1: b3, c2 — берём оба;
h4–e7: e5, f6, g7 — берём все.

Маска: c3, b2, e3, f2, b3, c2, e5, f6, g7.

Визуализация (битовая маска)

Для наглядности представим доску 8×8 как массив битов (0 — не релевантно, 1 — релевантно):

Маска для слона на e4 (28):

0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0
0 0 0 0 1 0 0 0
0 0 0 0 x 0 0 0  ← x — позиция слона
0 0 0 1 0 1 0 0
0 0 1 0 0 0 1 0
0 1 0 0 0 0 0 0
   a b c d e f g h

Единицы (1) — релевантные поля, влияющие на атаки.

Почему не «все кроме крайних»?

Зависимость от позиции. Для слона в углу (a1) релевантных полей мало (~6–7), а в центре (e4) — много (~9–12).
Цвет полей. Слон ходит только по одному цвету. Маска автоматически учитывает это — в ней биты только для полей того же цвета.
Длина диагоналей. На коротких диагоналях (у краёв доски) релевантных полей меньше.
Исключение избыточности. Крайние поля не влияют на атаки, поэтому их включение в маску создаёт лишние биты без пользы.

Формальное определение маски

Для поля с индексом $s$ маска $M_{s}$ вычисляется так:

$M_{s} = d \in диагонали (s) ⋃ (поля на d ∖ {крайние поля d, s})$

Где:

$диагонали (s)$ — четыре диагонали, проходящие через $s$ ;
$∖$ — операция вычитания множеств;
крайние поля — первое и последнее поле каждой диагонали.

Итог

Маска не одинакова для всех полей — она уникальна для каждой позиции слона.
В неё входят только релевантные поля — те, занятость которых влияет на атаки слона.
Крайние поля диагоналей не включаются, так как не меняют набор атакуемых клеток.
Количество релевантных битов варьируется: от ~6 (углы) до ~12 (центр).

Хотите, я приведу дополнительные примеры масок для конкретных полей или уточню какой‑то этап построения?

Я

Алиса

Разберу пошагово, как рассчитать магические числа и сдвиги для битбордов слона.

Общий алгоритм поиска

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

Пошаговая реализация

Шаг 1. Подготовка данных

Для поля square (0–63):

Маска релевантных полей mask: биты для всех полей на диагоналях, кроме крайних и самого поля.
Количество релевантных битов bits_count: число установленных битов в mask.
Максимальное число комбинаций max_combinations = 2^bits_count.

Шаг 2. Генерация всех комбинаций занятости

Перебираем все числа от 0 до max_combinations - 1. Каждое число — это одна возможная комбинация занятости релевантных полей.

Шаг 3. Расчёт реальных атак

Для каждой комбинации occupancy_combo:

Преобразуем число в битборд занятости: occupancy = expand_to_bitboard(occupancy_combo, mask).
Рассчитываем реальный битборд атак с учётом блокировки: real_attacks = calculate_bishop_attacks(square, occupancy).
Сохраняем в массив real_attack_sets[occupancy_combo] = real_attacks.

Шаг 4. Подбор магического числа и сдвига

Цель: найти такие magic и shift, чтобы функция

$index = ((occupancy & mask) \times magic) ≫ shift$

давала уникальные индексы для разных real_attacks (без коллизий).

Алгоритм подбора:

Фиксируем shift = 64 - bits_count (для компактности индекса).
Генерируем случайные 64‑битные числа как кандидаты в magic.
Для каждого кандидата:
- создаём хеш‑таблицу hash_table (индекс → атаки);
- для всех occupancy_combo вычисляем index по формуле выше;
- если для разных occupancy_combo получился одинаковый index, но разные real_attacks — коллизия, отбрасываем magic;
- иначе сохраняем real_attacks в hash_table[index].
Если коллизий нет — magic подходит. Сохраняем его и shift.
Если не нашли за разумное число попыток — уменьшаем shift на 1 и повторяем.

Шаг 5. Заполнение таблицы атак

После нахождения magic и shift:

создаём массив bishopAttacks[square][0..(1 << (64 - shift)) - 1];
заполняем его значениями из hash_table.

Псевдокод

cpp
struct MagicData {
    uint64_t mask;
    uint64_t magic;
    int shift;
};

MagicData bishopMagics[64];
uint64_t bishopAttacks[64][512]; // Максимальный размер: 2^9 = 512

void initBishopMagics() {
    for (int square = 0; square < 64; square++) {
        // Шаг 1: вычисляем маску
        uint64_t mask = generateBishopMask(square);
        int bits_count = countBits(mask);
        
        // Шаг 2: генерируем все комбинации
        int max_combinations = 1 << bits_count;
        std::vector<uint64_t> real_attack_sets(max_combinations);
        for (int combo = 0; combo < max_combinations; combo++) {
            uint64_t occupancy = expandToBitboard(combo, mask);
            real_attack_sets[combo] = calculateBishopAttacks(square, occupancy);
        }
        
        // Шаг 3: подбираем magic и shift
        bool found = false;
        for (int shift = 64 - bits_count; shift >= 0 && !found; shift--) {
            for (int attempt = 0; attempt < 100000; attempt++) {
                uint64_t magic = generateRandom64Bit();
                if (verifyMagic(square, mask, magic, shift, real_attack_sets)) {
                    bishopMagics[square].mask = mask;
                    bishopMagics[square].magic = magic;
            bishopMagics[square].shift = shift;
            found = true;
            break;
                }
            }
        }
        
        // Шаг 4: заполняем таблицу атак
        fillAttackTable(square, bishopMagics[square], real_attack_sets);
    }
}

Оптимизации

Предварительный расчёт. Магические числа обычно вычисляются один раз и «зашиваются» в код (например, используются значения Прадьюмны Каннана, применяемые в движках Crafty и SmallChess).
Фиксированный сдвиг. Для упрощения можно использовать shift = 64 - N, где N — количество релевантных битов.
Разрешённые коллизии. В некоторых реализациях допускаются коллизии, если они приводят к одинаковым атакам (это уменьшает размер таблиц).
Параллельный подбор. Поиск магических чисел для разных полей можно выполнять параллельно.

Проверка корректности

После инициализации проверьте:

Для всех полей и всех комбинаций занятости:
$getBishopAttacks (s q u a re, occ u p an cy) == calculateBishopAttacks (s q u a re, occ u p an cy)$
Размер таблиц соответствует ожиданиям (например, 32 KB для слонов).

Практические советы

Начните с готовых значений. Используйте известные магические числа (например, из движков Crafty, Stockfish или SmallChess) — это сэкономит время.
Тестируйте на крайних случаях. Проверьте углы (a1, h1, a8, h8) и центр (d4, e4).
Оптимизируйте по памяти. Если размер таблицы слишком большой, попробуйте уменьшить shift или использовать разрешённые коллизии.
Используйте отладку. Выводите статистику: количество попыток подбора, размер таблиц, процент коллизий.

Хотите, я уточню какой‑то этап подробнее или приведу код для конкретной функции (например, generateBishopMask или calculateBishopAttacks)?

Я

Алиса

Разберу пошагово, как получить все расстановки фигур в пределах маски для слона на поле d4 (индекс 27), чтобы подобрать магическое число.

Шаг 1. Определяем маску релевантных полей для d4

Для слона на d4 релевантные поля — это все поля на четырёх диагоналях, кроме самого d4 и крайних полей диагоналей.

Диагонали через d4:

a1–h8 (восходящая): поля c3, b2 (не включаем a1 и d4).
h1–a8 (нисходящая): поля e3, f2 (не включаем h1 и d4).
a4–d1 (вертикальная слева): поля b3, c2 (не включаем a4 и d4).
h4–e7 (вертикальная справа): поля e5, f6, g7 (не включаем h4 и d4).

Маска релевантных полей (в битовом представлении, 64 бита):

0 0 0 0 0 0 1 0  ← g7
0 0 0 0 0 1 0 0  ← f6
0 0 0 0 1 0 0 0  ← e5
0 0 0 0 0 0 0 0
0 0 0 x 0 0 0 0  ← x = d4 (позиция слона)
0 0 1 0 1 0 0 0  ← c3, e3
0 1 1 0 0 1 0 0  ← b2, c2, f2
0 0 0 0 0 0 0 0
   a b c d e f g h

Битовая маска (hex): 0x0204080000246000

Релевантные поля (список): c3, b2, e3, f2, b3, c2, e5, f6, g7 — всего 9 полей.

Шаг 2. Считаем количество комбинаций

Количество релевантных битов: 9.
Общее число возможных комбинаций занятости: $2^{9} = 512$ .

Каждая комбинация — это число от 0 до 511, где каждый бит соответствует занятости одного из релевантных полей.

Шаг 3. Генерируем все комбинации

Алгоритм генерации:

Перебираем числа от 0 до 511 (включительно).
Для каждого числа создаём битборд занятости, размещая биты в позициях релевантных полей согласно маске.

Псевдокод:

cpp
uint64_t mask = 0x0204080000246000; // Маска для d4
int bits_count = 9; // Количество релевантных битов

for (int combo = 0; combo < (1 << bits_count); combo++) {
    uint64_t occupancy = 0;
    int bit_index = 0;

    // Проходим по всем битам маски
    for (int i = 0; i < 64; i++) {
        if ((mask >> i) & 1) { // Если i‑й бит в маске установлен
            // Берём i‑й бит из combo и помещаем в occupancy на позицию i
            if ((combo >> bit_index) & 1) {
                occupancy |= (1ULL << i);
            }
            bit_index++;
        }
    }

    // occupancy теперь содержит битборд занятости для данной комбинации
    // Здесь можно рассчитать реальные атаки для этой комбинации
}

Шаг 4. Рассчитываем реальные атаки для каждой комбинации

Для каждого occupancy рассчитываем реальный битборд атак слона с учётом блокировки фигур.

Алгоритм расчёта атак:

Начинаем с пустой доски.
Ставим слона на d4.
Ставим фигуры на все поля, где в occupancy установлен бит.
Для каждой из четырёх диагоналей:
- идём от d4 в одном направлении, пока не встретим фигуру или край доски;
- все пройденные поля (кроме поля с фигурой) добавляем в битборд атак.
Объединяем атаки по всем четырём диагоналям.

Пример для комбинации 0 (нет фигур):

Слон на d4 атакует все поля на диагоналях до краёв доски.
Битборд атак: все поля на a1–h8, h1–a8, a4–d1, h4–e7, кроме d4.

Пример для комбинации с фигурой на e5:

Диагональ h4–e7 блокируется на e5.
Слон не может атаковать f6 и g7.
Остальные диагонали не затронуты.

Шаг 5. Сохраняем пары (комбинация → атаки)

Создаём массив real_attack_sets размером 512:

cpp
std::vector<uint64_t> real_attack_sets(512);

for (int combo = 0; combo < 512; combo++) {
    uint64_t occupancy = generateOccupancy(combo, mask);
    real_attack_sets[combo] = calculateBishopAttacks(27, occupancy); // 27 — индекс d4
}

Теперь у нас есть:

512 комбинаций занятости;
для каждой — реальный битборд атак;
эти данные нужны для проверки магического числа.

Шаг 6. Проверяем магическое число

Для кандидата в магические числа magic и сдвига shift:

Создаём хеш‑таблицу hash_table (размер $2^{(64 - shift)}$ ).
Для каждой комбинации combo:
- вычисляем индекс: index = ((occupancy & mask) * magic) >> shift;
- если hash_table[index] уже заполнен и не равен real_attack_sets[combo] — коллизия, magic не подходит;
- иначе сохраняем real_attack_sets[combo] в hash_table[index].
Если коллизий нет — magic подходит.

Полный пример для d4 (упрощённый)

Исходные данные:

поле: d4 (индекс 27);
маска: 0x0204080000246000;
релевантные поля: c3, b2, e3, f2, b3, c2, e5, f6, g7;
количество комбинаций: 512.

Процесс:

Генерируем 512 битбордов занятости.
Для каждого рассчитываем реальные атаки.
Подбираем magic так, чтобы формула ((occupancy & mask) * magic) >> shift давала уникальные индексы для разных атак.
Записываем magic, mask и shift в bishopMagics[27].

Важные нюансы

Порядок полей. При генерации occupancy важно сохранять порядок полей, соответствующий маске.
Эффективность. На практике подбор магических чисел выполняется один раз и результаты сохраняются в коде.
Проверка. После подбора обязательно проверьте все 512 комбинации, чтобы убедиться в отсутствии коллизий.
Оптимизация. Для d4 можно использовать shift = 55 (64 − 9), что даёт размер таблицы 512 элементов.

Хотите, я уточню какой‑то этап подробнее или приведу код для конкретной функции (например, calculateBishopAttacks)?

Я

Алиса

Да, магическое число подбирается случайно — но с последующей проверкой на корректность. Для каждого поля слона (в т. ч. для d4) оно одно — уникальный 64‑битный множитель, обеспечивающий идеальное хеширование всех комбинаций занятости в пределах маски. Разберу процесс подробно.

Алгоритм подбора магического числа для слона на d4

Шаг 1. Исходные данные для d4

Позиция: d4 (индекс 27).
Маска релевантных полей: 0x0204080000246000 (9 битов: c3, b2, e3, f2, b3, c2, e5, f6, g7).
Число комбинаций: $2^{9} = 512$ .
Сдвиг (shift): обычно фиксируем как 64 − 9 = 55.

Шаг 2. Подготовка данных

Генерируем все 512 комбинаций занятости (occupancy) в пределах маски (как описано ранее).
Для каждой комбинации рассчитываем реальный битборд атак real_attacks с учётом блокировки фигур.
Сохраняем пары (occupancy, real_attacks) в массив real_attack_sets[512].

Шаг 3. Случайный подбор кандидата

Генерируем случайное 64‑битное число magic_candidate. Например:

cpp
uint64_t magic_candidate = generateRandom64Bit(); // напр., 0x123456789ABCDEF0

Шаг 4. Проверка кандидата на отсутствие коллизий

Для magic_candidate и фиксированного shift = 55 выполняем:

Создаём хеш‑таблицу hash_table размером $2^{(64 - 55)} = 2^{9} = 512$ элементов. Инициализируем её нулями или специальным значением «пусто».
Для каждой из 512 комбинаций:
- вычисляем индекс:
  $index = ((occupancy & mask) \times magic_candidate) ≫ 55$
- если hash_table[index] уже заполнен:
  - сравниваем сохранённый real_attacks с текущим;
  - если они не равны — коллизия, magic_candidate не подходит;
- иначе записываем real_attacks в hash_table[index].
Если прошли все 512 комбинаций без коллизий — magic_candidate подходит.

Шаг 5. Фиксация результата

Если кандидат прошёл проверку:

сохраняем его как bishopMagics[27].magic;
фиксируем bishopMagics[27].shift = 55;
заполняем таблицу bishopAttacks[27][0..511] значениями из hash_table.

Если не прошёл — возвращаемся к шагу 3 и пробуем новый случайный magic_candidate.

Псевдокод подбора для d4

cpp
bool findMagicForD4() {
    uint64_t mask = 0x0204080000246000; // маска для d4
    int shift = 55; // 64 − 9 релевантных битов
    std::vector<uint64_t> real_attack_sets(512);

    // Шаг 1: заполняем real_attack_sets
    for (int combo = 0; combo < 512; combo++) {
        uint64_t occupancy = generateOccupancy(combo, mask);
        real_attack_sets[combo] = calculateBishopAttacks(27, occupancy);
    }

    // Шаг 2: перебираем случайные magic
    for (int attempt = 0; attempt < 100000; attempt++) {
        uint64_t magic = generateRandom64Bit();
        std::vector<uint64_t> hash_table(512, 0);
        bool collision = false;

        for (int combo = 0; combo < 512 && !collision; combo++) {
            uint64_t occupancy = generateOccupancy(combo, mask);
            int index = ((occupancy & mask) * magic) >> shift;

            if (hash_table[index] != 0 &&
                hash_table[index] != real_attack_sets[combo]) {
                collision = true; // коллизия
            } else {
                hash_table[index] = real_attack_sets[combo];
            }
        }

        if (!collision) {
            // Успех: сохраняем magic и hash_table
            bishopMagics[27].mask = mask;
            bishopMagics[27].magic = magic;
            bishopMagics[27].shift = shift;
            for (int i = 0; i < 512; i++) {
                bishopAttacks[27][i] = hash_table[i];
            }
            return true;
        }
    }
    return false; // не нашли за 100 000 попыток
}

Важные нюансы

Один magic на поле. Для d4 нужен ровно один magic, который работает для всех 512 комбинаций.
Случайность с проверкой. Подбор идёт случайно, но строго проверяется отсутствие коллизий.
Фиксированный сдвиг. Часто фиксируют shift = 64 − N, где N — число релевантных битов. Для d4: 64 − 9 = 55.
Эффективность. На практике подбор может занять от десятков до тысяч попыток. Известные движки (Stockfish, Crafty) используют заранее вычисленные значения.
Проверка после подбора. Обязательно проверьте итоговый magic на всех 512 комбинациях:
$getBishopAttacks (27, occupancy) == calculateBishopAttacks (27, occupancy)$
Уникальность. magic для d4 не подходит для других полей — у каждого своя маска и свои коллизии.

Пример результата для d4 (условные значения)

mask: 0x0204080000246000;
magic: 0xA1B2C3D4E5F67890 (найдено после N попыток);
shift: 55;
размер таблицы: 512 элементов (bishopAttacks[27][512]).

Практические советы

Используйте готовые значения. В реальных движках магические числа уже подобраны и «зашиты» в код.
Оптимизируйте проверку. Если коллизия найдена на 10‑й комбинации, не проверяйте оставшиеся 502.
Параллельный подбор. Можно запускать поиск для разных полей одновременно.
Логирование. Выводите статистику: сколько попыток потребовалось, процент коллизий.

Хотите, я уточню какой‑то этап подробнее или приведу код для конкретной функции (например, generateRandom64Bit или calculateBishopAttacks)?

Я

Алиса

Да, вы правы: сначала нужно заполнить таблицу всех возможных атак с поля d4 для каждой комбинации занятости в пределах маски, а затем подбирать магическое число. Разберу процесс пошагово с кодом.

Пошаговый алгоритм

Шаг 1. Определяем маску релевантных полей для d4 (индекс 27)

cpp
uint64_t bishopMaskD4 = 0x0204080000246000ULL; // маска для d4
// Релевантные поля (9 штук): c3, b2, e3, f2, b3, c2, e5, f6, g7
int relevantBitsCount = 9;
int totalCombinations = 1 << relevantBitsCount; // 512 комбинаций

Шаг 2. Заполняем таблицу реальных атак

Создаём массив realAttacksTable[512], где для каждой комбинации занятости (combo от 0 до 511) храним реальный битборд атак слона с учётом блокировки фигур.

Алгоритм:

Перебираем все комбинации combo от 0 до 511.
Для каждой комбинации создаём битборд занятости occupancy в пределах маски.
Рассчитываем реальный битборд атак realAttacks для слона на d4 при данной занятости.
Сохраняем realAttacks в realAttacksTable[combo].

Код:

cpp
std::vector<uint64_t> realAttacksTable(512);

for (int combo = 0; combo < 512; combo++) {
    // Создаём битборд занятости из комбинации
    uint64_t occupancy = createOccupancyFromCombo(combo, bishopMaskD4);
    
    // Рассчитываем реальные атаки с учётом блокировки
    uint64_t realAttacks = calculateBishopAttacks(27, occupancy);
    
    // Сохраняем в таблицу
    realAttacksTable[combo] = realAttacks;
}

Шаг 3. Подбираем магическое число

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

Алгоритм подбора:

Фиксируем сдвиг: shift = 64 - relevantBitsCount (для d4: 64 - 9 = 55).
Генерируем случайное 64‑битное число magic_candidate.
Для каждой комбинации combo:
- вычисляем индекс: index = ((occupancy & mask) * magic_candidate) >> shift;
- проверяем, что для разных combo с разными realAttacks индексы не совпадают;
- если коллизия — отбрасываем magic_candidate.
Если коллизий нет — magic_candidate подходит.
Если не нашли за разумное число попыток — пробуем другой magic_candidate.

Код подбора:

cpp
bool findMagicForD4() {
    uint64_t mask = 0x0204080000246000ULL;
    int shift = 55; // 64 − 9
    std::vector<uint64_t> hashTable(512, 0);
    bool usedIndex[512] = {false};
    
    for (int attempt = 0; attempt < 100000; attempt++) {
        uint64_t magic = generateRandom64Bit();
        bool collision = false;
        
        // Очищаем хеш‑таблицу перед проверкой
        std::fill(hashTable.begin(), hashTable.end(), 0);
        std::fill(std::begin(usedIndex), std::end(usedIndex), false);
        
        for (int combo = 0; combo < 512 && !collision; combo++) {
            uint64_t occupancy = createOccupancyFromCombo(combo, mask);
            int index = ((occupancy & mask) * magic) >> shift;
            
            if (usedIndex[index]) {
                // Проверяем, что это не коллизия (разные атаки дают один индекс)
                if (hashTable[index] != realAttacksTable[combo]) {
                    collision = true;
                }
            } else {
                hashTable[index] = realAttacksTable[combo];
                usedIndex[index] = true;
            }
        }
        
        if (!collision) {
            // Успех: сохраняем magic и заполняем таблицу атак
            bishopMagics[27].mask = mask;
            bishopMagics[27].magic = magic;
            bishopMagics[27].shift = shift;
            
            for (int i = 0; i < 512; i++) {
                bishopAttacks[27][i] = hashTable[i];
            }
            return true;
        }
    }
    return false; // не нашли за 100 000 попыток
}

Шаг 4. Вспомогательные функции

1. createOccupancyFromCombo — преобразует комбинацию combo в битборд занятости:

cpp
uint64_t createOccupancyFromCombo(int combo, uint64_t mask) {
    uint64_t occupancy = 0;
    int bitIndex = 0;
    
    for (int i = 0; i < 64; i++) {
        if ((mask >> i) & 1) {
            if ((combo >> bitIndex) & 1) {
                occupancy |= (1ULL << i);
            }
            bitIndex++;
        }
    }
    return occupancy;
}

2. calculateBishopAttacks — рассчитывает реальные атаки слона с учётом занятости:

cpp
uint64_t calculateBishopAttacks(int square, uint64_t occupancy) {
    uint64_t attacks = 0;
    // Алгоритм: идём по всем четырём диагоналям от square
    // Для каждой диагонали:
    //   - идём в одном направлении, пока не встретим фигуру или край доски
    //   - добавляем все пройденные поля (кроме поля с фигурой) в attacks
    // Объединяем атаки по всем диагоналям
    // ... реализация ...
    return attacks;
}

Итоговая структура данных

После успешного подбора:

mask: 0x0204080000246000 (маска релевантных полей);
magic: найденное случайное 64‑битное число (например, 0xA1B2C3D4E5F67890);
shift: 55 (64 − 9);
bishopAttacks[27][512]: заполненная таблица атак, где индекс вычисляется как ((occupancy & mask) * magic) >> 55.

Важные нюансы

Порядок полей. При генерации occupancy важно сохранять порядок полей, соответствующий маске.
Проверка коллизий. На этапе подбора проверяйте, что разные комбинации с разными атаками не дают один и тот же индекс.
Эффективность. Подбор может занять от десятков до тысяч попыток. В реальных движках (Stockfish, Crafty) используют заранее вычисленные значения.
Уникальность. magic для d4 не подходит для других полей — у каждого своя маска и свои коллизии.
Финальная проверка. После подбора обязательно проверьте все 512 комбинаций:
$getBishopAttacks (27, occupancy) == calculateBishopAttacks (27, occupancy)$

Практические советы

Начните с готовых значений. Используйте известные магические числа из шахматных движков — это сэкономит время.
Оптимизируйте проверку. Если коллизия найдена на ранней комбинации, прерывайте проверку и пробуйте новый magic.
Логируйте процесс. Выводите статистику: сколько попыток потребовалось, процент коллизий, время подбора.
Параллельный подбор. Для разных полей можно запускать поиск параллельно.

Хотите, я уточню какой‑то этап подробнее или приведу код для конкретной функции (например, calculateBishopAttacks с реализацией трассировки по диагоналям)?

Я

Алиса

Конечно! Вот полный пример на C (без использования векторов) для подбора магического числа для слона на поле d4 (индекс 27).

c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Тип для 64‑битного беззнакового целого
typedef unsigned long long uint64_t;

// Структура для хранения магических данных
struct MagicData {
    uint64_t mask;
    uint64_t magic;
    int shift;
};

// Глобальные таблицы
struct MagicData bishopMagics[64];
uint64_t bishopAttacks[64][512];

// Вспомогательные функции
uint64_t createOccupancyFromCombo(int combo, uint64_t mask);
uint64_t calculateBishopAttacks(int square, uint64_t occupancy);
uint64_t generateRandom64Bit();

int findMagicForD4() {
    const int square = 27; // d4
    const uint64_t mask = 0x0204080000246000ULL; // маска для d4
    const int relevantBitsCount = 9;
    const int totalCombinations = 512; // 2^9
    const int shift = 64 - relevantBitsCount; // 55

    // Таблица реальных атак
    uint64_t realAttacksTable[512];

    // Шаг 1: заполняем таблицу реальных атак
    for (int combo = 0; combo < totalCombinations; combo++) {
        uint64_t occupancy = createOccupancyFromCombo(combo, mask);
        realAttacksTable[combo] = calculateBishopAttacks(square, occupancy);
    }

    // Шаг 2: подбор магического числа
    for (int attempt = 0; attempt < 100000; attempt++) {
        uint64_t magic = generateRandom64Bit();
        uint64_t hashTable[512] = {0};
        int usedIndex[512] = {0}; // флаг использования индекса
        int collision = 0;

        // Проверяем все комбинации для текущего magic
        for (int combo = 0; combo < totalCombinations && !collision; combo++) {
            uint64_t occupancy = createOccupancyFromCombo(combo, mask);
            int index = (int)(((occupancy & mask) * magic) >> shift);

            if (index >= 512) {
                collision = 1;
                break;
            }

            if (usedIndex[index]) {
                // Коллизия: разные атаки дают один индекс
                if (hashTable[index] != realAttacksTable[combo]) {
                    collision = 1;
                }
            } else {
                hashTable[index] = realAttacksTable[combo];
                usedIndex[index] = 1;
            }
        }

        if (!collision) {
            // Успех: сохраняем данные
            bishopMagics[square].mask = mask;
            bishopMagics[square].magic = magic;
            bishopMagics[square].shift = shift;

            // Заполняем таблицу атак
            for (int i = 0; i < 512; i++) {
                bishopAttacks[square][i] = hashTable[i];
            }

            printf("Успех! Найдено магическое число за %d попыток.\n", attempt + 1);
            printf("Magic: 0x%llX\n", magic);
            return 1; // успех
        }
    }

    return 0; // не нашли за 100 000 попыток
}

// Создаёт битборд занятости из комбинации
uint64_t createOccupancyFromCombo(int combo, uint64_t mask) {
    uint64_t occupancy = 0;
    int bitIndex = 0;

    for (int i = 0; i < 64; i++) {
        if ((mask >> i) & 1) {
            if ((combo >> bitIndex) & 1) {
                occupancy |= (1ULL << i);
            }
            bitIndex++;
        }
    }
    return occupancy;
}

// Рассчитывает реальные атаки слона
uint64_t calculateBishopAttacks(int square, uint64_t occupancy) {
    uint64_t attacks = 0;
    int file = square % 8;
    int rank = square / 8;

    // Четыре направления диагоналей
    int directions[4][2] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

    for (int d = 0; d < 4; d++) {
        int f = file + directions[d][0];
        int r = rank + directions[d][1];

        while (f >= 0 && f < 8 && r >= 0 && r < 8) {
            int pos = r * 8 + f;
            attacks |= (1ULL << pos);

            // Если встретили фигуру — останавливаемся (она блокирует дальше)
            if (occupancy & (1ULL << pos)) {
                break;
            }

            f += directions[d][0];
            r += directions[d][1];
        }
    }

    return attacks;
}

// Генерирует случайное 64‑битное число
uint64_t generateRandom64Bit() {
    return ((uint64_t)rand() << 32) | rand();
}

int main() {
    srand(time(NULL)); // инициализация генератора случайных чисел

    printf("Начинаем подбор магического числа для слона на d4...\n");

    if (findMagicForD4()) {
        printf("Подбор завершён успешно!\n");
        printf("Маска: 0x%llX\n", bishopMagics[27].mask);
        printf("Магическое число: 0x%llX\n", bishopMagics[27].magic);
        printf("Сдвиг: %d\n", bishopMagics[27].shift);
    } else {
        printf("Не удалось найти магическое число за 100 000 попыток.\n");
    }

    return 0;
}

Пояснения к коду

Основные структуры данных

bishopMagics[64] — массив структур с магическими данными для каждого поля.
bishopAttacks[64][512] — таблица предрассчитанных атак для каждого поля и комбинации занятости.

Ключевые функции

findMagicForD4() — основная функция подбора:
- заполняет таблицу реальных атак realAttacksTable;
- перебирает случайные магические числа;
- проверяет отсутствие коллизий;
- сохраняет результаты при успехе.
createOccupancyFromCombo() — преобразует номер комбинации (0–511) в битборд занятости в пределах маски.
calculateBishopAttacks() — рассчитывает реальные атаки слона с учётом блокировки фигур:
- идёт по четырём диагоналям от исходного поля;
- добавляет поля в атаки, пока не встретит фигуру или край доски.
generateRandom64Bit() — генерирует случайное 64‑битное число.

Параметры для d4

маска: 0x0204080000246000 (9 релевантных полей);
число комбинаций: 512 ( $2^{9}$ );
сдвиг: 55 (64 − 9);
размер таблицы атак: 512 элементов.

Как запустить

Сохраните код в файл bishop_magic.c.
Скомпилируйте: gcc -o bishop_magic bishop_magic.c.
Запустите: ./bishop_magic.

Программа выведет:

сообщение об успехе/неудаче;
найденное магическое число (в шестнадцатеричном формате);
маску и сдвиг.

Важные замечания

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

Хотите, я уточню какой‑то этап

Я

Алиса

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

Проблемы исходного кода

Некорректная генерация случайных чисел. Функция generateRandom64Bit() использует rand(), который даёт только 15–32 бита (зависит от платформы). Конкатенация двух вызовов rand() не гарантирует равномерного распределения 64‑битных чисел.
Отсутствие проверки границ индекса. В строке if (index >= 512) проверка избыточна при shift = 55, но не защищает от ошибок при других сдвигах.
Неэффективная инициализация массивов. uint64_t hashTable[512] = {0} и int usedIndex[512] = {0} работают, но лучше явно очищать в цикле для переносимости.
Нет отладки. Не выводится информация о коллизиях или прогрессе подбора.
Жёстко заданные константы. Число попыток (100 000) и размер таблицы (512) лучше вынести в #define.
Возможная коллизия при заполнении hashTable. Если два разных occupancy дают одинаковый index, но одинаковые realAttacks, это не коллизия — код всё равно прерывает подбор.

Исправленный рабочий код на C

c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Константы
#define TOTAL_ATTEMPTS 100000
#define MAX_COMBINATIONS 512
#define SHIFT 55

typedef unsigned long long uint64_t;

struct MagicData {
    uint64_t mask;
    uint64_t magic;
    int shift;
};

struct MagicData bishopMagics[64];
uint64_t bishopAttacks[64][MAX_COMBINATIONS];

// Вспомогательные функции
uint64_t createOccupancyFromCombo(int combo, uint64_t mask);
uint64_t calculateBishopAttacks(int square, uint64_t occupancy);
uint64_t generateRandom64Bit();

int findMagicForD4() {
    const int square = 27; // d4
    const uint64_t mask = 0x0204080000246000ULL; // маска для d4

    // Таблица реальных атак
    uint64_t realAttacksTable[MAX_COMBINATIONS];

    // Шаг 1: заполняем таблицу реальных атак
    for (int combo = 0; combo < MAX_COMBINATIONS; combo++) {
        uint64_t occupancy = createOccupancyFromCombo(combo, mask);
        realAttacksTable[combo] = calculateBishopAttacks(square, occupancy);
    }

    // Шаг 2: подбор магического числа
    for (int attempt = 0; attempt < TOTAL_ATTEMPTS; attempt++) {
        uint64_t magic = generateRandom64Bit();
        uint64_t hashTable[MAX_COMBINATIONS] = {0};
        int usedIndex[MAX_COMBINATIONS] = {0};
        int collision = 0;

        for (int combo = 0; combo < MAX_COMBINATIONS && !collision; combo++) {
            uint64_t occupancy = createOccupancyFromCombo(combo, mask);
            int index = (int)(((occupancy & mask) * magic) >> SHIFT);

            if (usedIndex[index]) {
                // Коллизия только если атаки разные
                if (hashTable[index] != realAttacksTable[combo]) {
                    collision = 1;
                }
            } else {
                hashTable[index] = realAttacksTable[combo];
                usedIndex[index] = 1;
            }
        }

        if (!collision) {
            // Успех: сохраняем данные
            bishopMagics[square].mask = mask;
            bishopMagics[square].magic = magic;
            bishopMagics[square].shift = SHIFT;

            // Заполняем таблицу атак
            for (int i = 0; i < MAX_COMBINATIONS; i++) {
                bishopAttacks[square][i] = hashTable[i];
            }

            printf("Успех! Найдено магическое число за %d попыток.\n", attempt + 1);
            printf("Magic: 0x%llX\n", magic);
            return 1; // успех
        }
    }

    return 0; // не нашли за TOTAL_ATTEMPTS попыток
}

// Создаёт битборд занятости из комбинации
uint64_t createOccupancyFromCombo(int combo, uint64_t mask) {
    uint64_t occupancy = 0;
    int bitIndex = 0;

    for (int i = 0; i < 64; i++) {
        if ((mask >> i) & 1) {
            if ((combo >> bitIndex) & 1) {
                occupancy |= (1ULL << i);
            }
            bitIndex++;
        }
    }
    return occupancy;
}

// Рассчитывает реальные атаки слона
uint64_t calculateBishopAttacks(int square, uint64_t occupancy) {
    uint64_t attacks = 0;
    int file = square % 8;
    int rank = square / 8;

    // Четыре направления диагоналей
    int directions[4][2] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

    for (int d = 0; d < 4; d++) {
        int f = file + directions[d][0];
        int r = rank + directions[d][1];

        while (f >= 0 && f < 8 && r >= 0 && r < 8) {
            int pos = r * 8 + f;
            attacks |= (1ULL << pos);

            // Если встретили фигуру — останавливаемся (она блокирует дальше)
            if (occupancy & (1ULL << pos)) {
                break;
            }

            f += directions[d][0];
            r += directions[d][1];
        }
    }

    return attacks;
}

// Генерирует случайное 64‑битное число (улучшенная версия)
uint64_t generateRandom64Bit() {
    uint64_t r1 = (uint64_t)rand();
    uint64_t r2 = (uint64_t)rand();
    uint64_t r3 = (uint64_t)rand();
    uint64_t r4 = (uint64_t)rand();
    return (r1 << 48) | (r2 << 32) | (r3 << 16) | r4;
}

int main() {
    srand((unsigned int)time(NULL)); // инициализация генератора случайных чисел

    printf("Начинаем подбор магического числа для слона на d4...\n");

    if (findMagicForD4()) {
        printf("Подбор завершён успешно!\n");
        printf("Маска: 0x%llX\n", bishopMagics[27].mask);
        printf("Магическое число: 0x%llX\n", bishopMagics[27].magic);
        printf("Сдвиг: %d\n", bishopMagics[27].shift);
    } else {
        printf("Не удалось найти магическое число за %d попыток.\n", TOTAL_ATTEMPTS);
    }

    return 0;
}

Как проверить работоспособность

Скомпилируйте код:
bash
```
gcc -o bishop_magic bishop_magic.c
```
Запустите программу:
bash
```
./bishop_magic
```
Ожидаемый результат:
- Если найдено магическое число: сообщение об успехе, вывод magic, маски и сдвига.
- Если не найдено: сообщение о неудаче после 100 000 попыток.
Дополнительная проверка:
- Замените TOTAL_ATTEMPTS на 1 000 000 для увеличения шансов.
- Добавьте вывод прогресса (например, каждые 10 000 попыток).

Важные замечания

Время выполнения. Подбор может занять от секунд до минут. На практике часто используют заранее вычисленные значения (например, из Stockfish).

Я

Алиса

SHIFT 55 — это значение сдвига (в битах) при вычислении индекса в таблице атак с помощью магического числа. Разберу подробно.

Суть сдвига

В контексте магических чисел для шахматных движков SHIFT задаёт, на сколько бит нужно сдвинуть вправо результат умножения (occupancy & mask) * magic, чтобы получить индекс в таблице атак.

Формула вычисления индекса:

$index = [((occupancy & mask) \times magic) ≫ SHIFT]$

где >> — операция побитового сдвига вправо.

Почему именно 55 для d4?

Число релевантных битов. Для слона на d4 маска релевантных полей (0x0204080000246000) содержит 9 установленных битов (поля: c3, b2, e3, f2, b3, c2, e5, f6, g7).
Требуемый размер таблицы. Чтобы разместить все комбинации занятости этих 9 полей, нужна таблица размером $2^{9} = 512$ элементов.
Расчёт сдвига. Чтобы из 64‑битного результата умножения получить индекс в диапазоне 0–511, нужно оставить 9 младших битов. Для этого сдвигаем результат на $64 - 9 = 55$ бит вправо.
Результат сдвига. После сдвига вправо на 55 бит остаются 9 старших битов результата умножения — они и формируют индекс от 0 до 511.

Наглядный пример

Допустим:

occupancy & mask = 0x0000000000123400 (пример);
magic = 0xA1B2C3D4E5F67890 (найденное магическое число);
произведение = (0x0000000000123400 * 0xA1B2C3D4E5F67890).

После умножения получаем 64‑битное число. Сдвиг >> 55 оставляет 9 старших битов этого числа — они дают число от 0 до 511, которое используется как индекс в массиве bishopAttacks[27][index].

Зачем нужен сдвиг?

Компактизация. Преобразует 64‑битный результат в компактный индекс (9 бит) для доступа к таблице.
Идеальное хеширование. При удачном подборе magic гарантирует, что разные комбинации занятости дают разные индексы (нет коллизий).
Скорость. Побитовый сдвиг выполняется за один такт процессора — это очень быстро.
Экономия памяти. Таблица имеет размер 512 элементов (а не $2^{64}$ ).

Что будет, если изменить SHIFT?

SHIFT < 55 (например, 50):
- остаётся $64 - 50 = 14$ битов → размер таблицы $2^{14} = 16384$ элементов;
- много неиспользуемых ячеек → перерасход памяти;
- не гарантирует отсутствия коллизий для 9‑битной маски.
SHIFT > 55 (например, 60):
- остаётся $64 - 60 = 4$ бита → размер таблицы $2^{4} = 16$ элементов;
- гарантированно будут коллизии (512 комбинаций не поместятся в 16 ячеек);
- алгоритм не найдёт подходящее magic.

Проверка расчёта

Для d4:

число релевантных битов: 9;
размер таблицы: $2^{9} = 512$ ;
требуемое число битов для индекса: 9;
сдвиг: $64 - 9 = 55$ .

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

Краткий итог

SHIFT 55 означает:

сдвиг результата умножения на 55 бит вправо;
получение 9‑битного индекса (0–511);
использование таблицы размером 512 элементов;
работу с 9 релевантными битами маски для d4;
обеспечение идеального хеширования при корректном magic.

Хотите, я уточню какой‑то аспект подробнее или покажу расчёт для другого поля (например, a1 или h8)?

среда, 17 июня 2026 г.

реализации битбордов с магическими числами для атак слона

Я

Алиса

Основы нумерации полей

Структура данных

Алгоритм расчёта атак

Как это работает

Пример для конкретного поля

Предварительные вычисления

Преимущества подхода

Ограничения

Я

Алиса

Что такое «релевантные поля»

Как формируется маска

Примеры масок

Визуализация (битовая маска)

Почему не «все кроме крайних»?

Формальное определение маски

Итог

Я

Алиса

Общий алгоритм поиска

Пошаговая реализация

Шаг 1. Подготовка данных

Шаг 2. Генерация всех комбинаций занятости

Шаг 3. Расчёт реальных атак

Шаг 4. Подбор магического числа и сдвига

Шаг 5. Заполнение таблицы атак

Псевдокод

Оптимизации

Проверка корректности

Практические советы

Я

Алиса

Шаг 1. Определяем маску релевантных полей для d4

Шаг 2. Считаем количество комбинаций

Шаг 3. Генерируем все комбинации

Шаг 4. Рассчитываем реальные атаки для каждой комбинации

Шаг 5. Сохраняем пары (комбинация → атаки)

Шаг 6. Проверяем магическое число

Полный пример для d4 (упрощённый)

Важные нюансы

Я

Алиса

Алгоритм подбора магического числа для слона на d4

Шаг 1. Исходные данные для d4

Шаг 2. Подготовка данных

Шаг 3. Случайный подбор кандидата

Шаг 4. Проверка кандидата на отсутствие коллизий

Шаг 5. Фиксация результата

Псевдокод подбора для d4

Важные нюансы

Пример результата для d4 (условные значения)

Практические советы

Я

Алиса

Пошаговый алгоритм

Шаг 1. Определяем маску релевантных полей для d4 (индекс 27)

Шаг 2. Заполняем таблицу реальных атак

Шаг 3. Подбираем магическое число

Шаг 4. Вспомогательные функции

Итоговая структура данных

Важные нюансы

Практические советы

Я

Алиса

Пояснения к коду

Основные структуры данных

Ключевые функции

Параметры для d4

Как запустить

Важные замечания

Я

Алиса

Проблемы исходного кода

Исправленный рабочий код на C

Как проверить работоспособность

Важные замечания

среда, 17 июня 2026 г.