Данная статья — иллюстрация, каким образом битовые трюки могут быть использованы не только в задачах на собеседованиях, но и при решении реальных задач. В статье дано описание одного метода быстрой генерации ходов в русских шашках на основе магических битбордов (magic bitboard). Битборды — представление позиции в виде нескольких беззнаковых целых чисел, каждый бит которого отвечает за состояние некоторого элемента игры, например клетки. Обычно использование битбордов даёт выигрыш по производительности и по объёму используемой памяти, но связано с более изощрённым программированием. При этом часто возникает задача получения значения определённых бит в битборде, например, для последующего обращения к таблице. Есть два основных подхода к решению этой задачи. Первый — использование и поддержка избыточного представления в виде дополнительных битбордов с перенумерацией битов. Такие битборды асто называют вращаемые. Второй способ — умножение на магическую константу, сдвиг и обращение к таблице. О таких магических битбордах и пойдёт речь в этой статье.

Введение

Допустим у нас есть некоторое множество, которое состоит из N элементов. Будем считать, что элементы пронумерованы от нуля до N-1. Набор k-элементных подмножеств данного множества (сочетаний) можно представить либо в виде массива индексов длины k. Либо в виде последовательности из N бит, в которой установлено ровно k из них. У Дональда Кнута в его TAoCP приводится алгоритм генерации сочетаний в лексикографическом порядке, когда сочетания заданы в виде массива индексов. Мы попробуем перенести этот алгоритм на случай битовых масок.