Данная статья — иллюстрация, каким образом битовые трюки могут быть использованы не только в задачах на собеседованиях, но и при решении реальных задач. В статье дано описание одного метода быстрой генерации ходов в русских шашках на основе магических битбордов (magic bitboard). Битборды — представление позиции в виде нескольких беззнаковых целых чисел, каждый бит которого отвечает за состояние некоторого элемента игры, например клетки. Обычно использование битбордов даёт выигрыш по производительности и по объёму используемой памяти, но связано с более изощрённым программированием. При этом часто возникает задача получения значения определённых бит в битборде, например, для последующего обращения к таблице. Есть два основных подхода к решению этой задачи. Первый — использование и поддержка избыточного представления в виде дополнительных битбордов с перенумерацией битов. Такие битборды асто называют вращаемые. Второй способ — умножение на магическую константу, сдвиг и обращение к таблице. О таких магических битбордах и пойдёт речь в этой статье.
Представление позиции в игре — ответственный шаг, который влияет на все последующие. Когда я был студентом, то не долго думая, выбрал самое напрашивающееся представление в виде массива из 32 байт, по одному на каждую клетку. Это оказалось неэффективным решением. И если на шашках оно худо-бедно работало, то в случае шахмат результаты были плачевны.
Позже я узнал, что одни из самых быстрых алгоритмов получения списка всех ходов используют битборды. В случае шахмат это представление позиции в виде 64-х битных чисел, где каждый бит отвечает за одну клетку доски. Всего используется несколько битбордов, один для хранения расположения белых пешек, другой для хранения расположения черных коней и т. д. Для генерации всех ходов в шахматах используются два основных метода: «вращаемых битбордов» и «магических битбордов». Использование метода «вращаемых битбордов» описано в статье «Вращаемые битборды: новый виток старой идеи». Использование метода «магических битбордов» можно найти на английском языке на сайте chessprogramming wiki. Кого же интересует реализация на языке программирования C, то я советую смотреть код шахматного движка Crafty, который доступен на сайте craftychess.com. Автор движка, профессор Роберт Хайат (Robert Hyatt) много внимания уделил читабельности кода, многие места снабжены пояснениями. Также он является автором нескольких интересных статей по шахматному программированию.
В случае шахмат использование битбордов выглядит естественным. 64 клетки — 64 бита. Не возникает вопроса о нумерации бит. Допустим, мы ходим сгенерировать все передвижения белых пешек на одно поле. Для этого нам надо взять битовую маску всех пешек, сдвинуть на восемь бит влево (черные пешки сдвигаются соответственно вправо), сделать AND с битбордом всех свободных клеток, и мы моментально получаем битовую маску полей, куда могу двинуться пешки. Осталось только сформировать список ходов.
С русскими шашками всё немного сложнее. Каким должно быть соответствие между битами и полями доски? Один из вариантов взять как можно больше от шахмат — использовать представление доски в виде 64-х битного целого числа, где бы использовались только 32 бита, которые ответственны за чёрные поля. Да, вариант, но меня угнетает тот факт, что ровно половина всех бит не будет использоваться. Если для игры используется только 32 чёрные клетки, то почему бы не использовать в качестве битбордов 32-х битные числа?
Итак, позиция в русских шашках описывается целым числом, которое будет показывать очередь хода, и четырьмя 32-битными битбордами. Вопрос про соответствие полей и битов оставим пока на потом. Какие четыре битборда надо выбрать для представления доски? Я остановился на варианте, когда для каждой стороны используется два битборда: все простые шашки, и все шашки как простые, так и дамки. В этом случае мы можем одной операцией получить все интересующие нас битборды. Итак,
Важным вопросом является нумерация битов. Проще всего рассмотреть задачу генерации ходов простых шашек. Для каждого способа нумерации битов нам надо найти простое выражение, которое бы позволило нам получить битовую маску возможных перемещений простой. Начнём, пожалуй, с самого очевидного варианта нумерации битов:
Выглядит красиво, но несколько неудобно. Дело в том, количество бит, на которое нам надо сдвинуть битовую маску простых, зависит от чётности ряда. Что заставляет писать нас более сложное выражение.
Пока что будем держать такой вариант как запасной парашют, и постараемся найти такую нумерацию, при которой номера битов на одной диагонали образовывали арифметическую прогрессию. Немного поигравшись, возникает такой вариант нумерации:
Если брать диагонали, идущие вверх-влево, то тут всё замечательно, для генерации ходов простых можно использовать простой сдвиг влево [вправо] для белых [чёрных]. Если брать диагонали, идущие параллельно диагонали a1-h8 (большаку), то тут у нас арифметическая прогрессия, где используется сложение по модулю 32, что соответствует операции циклического сдвига. Данная операция должна быть достаточно эффективной, так как содержится в наборе инструкций некоторых процессоров, в частности семейства x86. На этом и остановимся.
В реальности не все простые могут ходить вперёд-влево. Поэтому в реальной программе придётся перед сдвигом выполнить ещё операцию AND, оставив только те шашки, которые имеют данную возможность. Если исключить техническую трудность с тем, что за один ход можно взять несколько шашек противника, то взятия простых рассматриваются аналогично, только нам надо будет выполнить два последовательных сдвига, на первом из которых делать AND с битбордом шашек противника, а на втором с битбордом свободных полей. Ниже приведён пример для случае проверки взятия вверх-влево:
Мы получили достаточно эффективное решение, но оно работает только для доски 8x8. В случае международных шашек (доска 10x10) на доске 50 чёрных клеток. Используя схожий тип нумерации мы наступаем на грабли, что необходимо выполнить циклический сдвиг для 50-ти бит. Такой одной инструкции нет, так что придётся выполнять получения битовой маски за три операции: сдвиг влево, сдвиг вправо и OR. В случае шашек Спаринцети, которые ничем не отличаются от русских шашек, за исключением того, что используется доска 8x10, сложно придумать даже аналог подобной нумерации, так что скорее всего придётся использовать представление доски в виде подмножества 10x10.
Теперь рассмотрим вопросы, которые касаются взятия дамками. Может ли дамка осуществить взятие, какая шашка будет убита, куда может стать дамка после взятия? Кажется, что для ответа на эти вопросы не обойтись без нудного цикла. Но если присмотреться внимательно, то для ответа на эти вопросы используются только биты одной диагонали. Диагонали, которые параллельны двойнику (диагоналям g1-a7 и h2-b8) имеют последовательную нумерацию бит. Что приводит нас к довольно простой идее: битборд всех шашек надо сдвинуть вправо таким образом, чтобы все биты диагонали занимали самые младшие позиции. А потом просто обратиться к некоторой заранее составленной таблице. А это минимум операций!
Для диагоналей, которые параллельны большаку, получить ответы на эти вопросы несколько сложнее. Один из способов, это поддерживать одновременно две нумерации, одна из которых была бы более удобна для проверки взятий по диагоналям, параллельных большаку, а другая — по диагоналях, параллельных двойнику. Такая нумерация выглядит как бы повёрнутой на угол 90º. Отсюда и название — вращаемые битборды. Когда я в своё время реализовывал генератор ходов в шахматах на основе этой идее, то всякий раз читая в шестнадцатиричном виде битборды, повёрнутые на 90º градусов, непроизвольно и сам поворачивал голову. Вот возможная нумерация для вращаемых битвордов:
Но есть ещё и более красивая идея! Итак, рассмотрим большак. В нашем битборде это биты 0, 7, 14, 21, 28, 3, 10, 17. Нам надо придумать такую функцию, которая бы эти биты переставила на места с нулевого по седьмой, в любом порядке. Тогда бы мы смогли воспользоваться заранее подготовленой таблицей.
Как по мне, такая операция была бы очень полезна в наборе инструкций процессора, особенно который предназначен для реализации логики в разных играх. Сама инструкция могла бы иметь виде SUBBITS a, v, где a — некоторое число, v — битовая маска, которая указывает на то, какие биты следует оставить и перенести в младшие разряды. Например, SUBBITS 0xFF00FF, 0x111111 должна дать на выходе 1100112: оставляем биты с номерами 0, 4, 8, 12, 16, 20 и переносим нулевой бит в нулевую позиции, четвёртый — в первую, восьмой — во вторую,…
Ну это лирическое отступление. В большинстве случаем такую операцию несложно эффективно реализовать и имеющимися командами. Перенос битов вправо — это деление. На практике оказалось, что проще перенести все биты в самые левые позиции (умножение), а потом сделать большой сдвиг вправо. Каким образом?
Рассмотрим один бит. Допустим у нас есть число x, и мы хотим 10-й бит этого числа в 31-ю позицию, что станется с остальными битами нам неинтересно. Это достаточно простая задача, поскольку 31 — 10 = 21, то получаем x << 21. Предположим, что у нас есть не только 10-й бит, но еще и 20-й, который бы мы хотели перенести в 30-ю позицию. Сделать это не сложно:
А теперь попробуем взглянуть на эту последовательность по-другому. Во-первых, операцию OR в последней строке мы можем безболезненно заменить сложением: никакие переполнения нам жизнь не испортят. Во-вторых, после замены знака OR на плюс, выражение в последней строке подозрительно напоминает умножение. Действительно,
mask10 и mask20 получаются из одного x, поэтому мы можем привести наш пример к виду:
Если не обращать внимание, что в других битах может остаться мусор, это будет работать.
Подведём итоги. Если звёзды на небе стоят удачно, то перенести заданные биты в старшие позиции может получится операцией AND и умножением. А может и не получиться. В нашем случае биты с номерами 10 и 20 расположены далеко друг от друга, и результат сложения никак не может затронуть 31-й и 30-й биты результата.
Когда-же наш метод будет давать сбой? Пусть мы хотим перенести 4-й бит на 7-е место, 2-й бит на 6-е, а 0-й на 5-е. В данном случае наша магическая константа примет вид 0x38, в ней установлены три бита: пятый (сдвиг на пять), пятый и третий. Но проблема в том, что когда мы попробуем осуществить наше умножение, то биты наложатся один на другой:
Как обойти такую неприятность? Выход состоит в том, что мы можем попробовать другую перестановку бит. Например, 4→6, 2→7, 0→5. В этом случае наша магическая константа примет вид 0x24, в ней установлено только два бита, потому что второй и нулевой биты должны сдвинуться на одно и то же значение.
Что это обозначает применительно к битбордам в шашках? У нас есть семь диагоналей, и если нам повезёт, но мы сможем найти такую перестановку битов, что умножение на магическую константу перенесёт каждый бит в нужное место, и ничего не испортит. Но для этого нам необходимо будет написать отдельную программу поиска, которая бы не только нашла такие константы, сформировала бы магические массивы, хранящие ответы на вопросы, можно ли осуществить взятие, какая шашка убивается, на какие поля дамка может перейти после взятия (или продолжить бой).
Конечно, при генерации списка ходов ещё могут возникнуть технические трудности. Например, надо не забыть про турецкий удар, когда убитые шашки снимаются с доски только после завершения удара. Но все они носят технический характер. Для этой статьи я реализовал небольшой учебный пример, в котором представлена реализация генератора ходов с использование магических битовых масок. Его можно сказать по ссылке checkers-0.1.tar.bz2.
Представление позиции
Представление позиции в игре — ответственный шаг, который влияет на все последующие. Когда я был студентом, то не долго думая, выбрал самое напрашивающееся представление в виде массива из 32 байт, по одному на каждую клетку. Это оказалось неэффективным решением. И если на шашках оно худо-бедно работало, то в случае шахмат результаты были плачевны.
Позже я узнал, что одни из самых быстрых алгоритмов получения списка всех ходов используют битборды. В случае шахмат это представление позиции в виде 64-х битных чисел, где каждый бит отвечает за одну клетку доски. Всего используется несколько битбордов, один для хранения расположения белых пешек, другой для хранения расположения черных коней и т. д. Для генерации всех ходов в шахматах используются два основных метода: «вращаемых битбордов» и «магических битбордов». Использование метода «вращаемых битбордов» описано в статье «Вращаемые битборды: новый виток старой идеи». Использование метода «магических битбордов» можно найти на английском языке на сайте chessprogramming wiki. Кого же интересует реализация на языке программирования C, то я советую смотреть код шахматного движка Crafty, который доступен на сайте craftychess.com. Автор движка, профессор Роберт Хайат (Robert Hyatt) много внимания уделил читабельности кода, многие места снабжены пояснениями. Также он является автором нескольких интересных статей по шахматному программированию.
В случае шахмат использование битбордов выглядит естественным. 64 клетки — 64 бита. Не возникает вопроса о нумерации бит. Допустим, мы ходим сгенерировать все передвижения белых пешек на одно поле. Для этого нам надо взять битовую маску всех пешек, сдвинуть на восемь бит влево (черные пешки сдвигаются соответственно вправо), сделать AND с битбордом всех свободных клеток, и мы моментально получаем битовую маску полей, куда могу двинуться пешки. Осталось только сформировать список ходов.
С русскими шашками всё немного сложнее. Каким должно быть соответствие между битами и полями доски? Один из вариантов взять как можно больше от шахмат — использовать представление доски в виде 64-х битного целого числа, где бы использовались только 32 бита, которые ответственны за чёрные поля. Да, вариант, но меня угнетает тот факт, что ровно половина всех бит не будет использоваться. Если для игры используется только 32 чёрные клетки, то почему бы не использовать в качестве битбордов 32-х битные числа?
Итак, позиция в русских шашках описывается целым числом, которое будет показывать очередь хода, и четырьмя 32-битными битбордами. Вопрос про соответствие полей и битов оставим пока на потом. Какие четыре битборда надо выбрать для представления доски? Я остановился на варианте, когда для каждой стороны используется два битборда: все простые шашки, и все шашки как простые, так и дамки. В этом случае мы можем одной операцией получить все интересующие нас битборды. Итак,
typedef int square_t;
typedef uint32_t bitboard_t;
typedef int side_t;
enum side_t { WHITE, BLACK };
enum position_bitboard_index_t {
IDX_ALL_0 = 0, // Все шашки белых
IDX_ALL_1 = 1, // Все шашки чёрных
IDX_SIM_0 = 2, // Все белые простые
IDX_SIM_1 = 3 // Все чёрные простые.
};
struct position
{
bitboard_t bitboards[4];
side_t active;
};
// Пример получения интересующих нас битбордов:
uint32_t /* Все занятые клетке доски */ all_bb = bitboards[IDX_ALL_0] | bitboards[IDX_ALL_1];
uint32_t /* Все свободные клетки доски */ empty_bb = ~all_bb;
uint32_t /* Белые дамки */ mam_bb = bitboards[IDX_ALL_0] ^ bitboards[IDX_SIM_0];
Нумерация битов
Важным вопросом является нумерация битов. Проще всего рассмотреть задачу генерации ходов простых шашек. Для каждого способа нумерации битов нам надо найти простое выражение, которое бы позволило нам получить битовую маску возможных перемещений простой. Начнём, пожалуй, с самого очевидного варианта нумерации битов:
+--+--+--+--+--+--+--+--+ | |28| |29| |30| |31| 8 +--+--+--+--+--+--+--+--+ |24| |25| |26| |27| | 7 +--+--+--+--+--+--+--+--+ | |20| |21| |22| |23| 6 +--+--+--+--+--+--+--+--+ |16| |17| |18| |19| | 5 +--+--+--+--+--+--+--+--+ | |12| |13| |14| |15| 4 +--+--+--+--+--+--+--+--+ | 8| | 9| |10| |11| | 3 +--+--+--+--+--+--+--+--+ | | 4| | 5| | 6| | 7| 2 +--+--+--+--+--+--+--+--+ | 0| | 1| | 2| | 3| | 1 +--+--+--+--+--+--+--+--+ a b c d e f g h
Выглядит красиво, но несколько неудобно. Дело в том, количество бит, на которое нам надо сдвинуть битовую маску простых, зависит от чётности ряда. Что заставляет писать нас более сложное выражение.
// Ход белых вверх вправо, чётные горизонтали надо сдвигать на пять, нечётные — на четыре:
uint32_t up_right_bb = 0
| ((bb & RANK_1357) >> 4
| ((bb & RANK_2468) >> 5
;
Пока что будем держать такой вариант как запасной парашют, и постараемся найти такую нумерацию, при которой номера битов на одной диагонали образовывали арифметическую прогрессию. Немного поигравшись, возникает такой вариант нумерации:
+--+--+--+--+--+--+--+--+ | |31| | 5| |11| |17| 8 +--+--+--+--+--+--+--+--+ |24| |30| | 4| |10| | 7 +--+--+--+--+--+--+--+--+ | |23| |29| | 3| | 9| 6 +--+--+--+--+--+--+--+--+ |16| |22| |28| | 2| | 5 +--+--+--+--+--+--+--+--+ | |15| |21| |27| | 1| 4 +--+--+--+--+--+--+--+--+ | 8| |14| |20| |26| | 3 +--+--+--+--+--+--+--+--+ | | 7| |13| |19| |25| 2 +--+--+--+--+--+--+--+--+ | 0| | 6| |12| |18| | 1 +--+--+--+--+--+--+--+--+ a b c d e f g h
Если брать диагонали, идущие вверх-влево, то тут всё замечательно, для генерации ходов простых можно использовать простой сдвиг влево [вправо] для белых [чёрных]. Если брать диагонали, идущие параллельно диагонали a1-h8 (большаку), то тут у нас арифметическая прогрессия, где используется сложение по модулю 32, что соответствует операции циклического сдвига. Данная операция должна быть достаточно эффективной, так как содержится в наборе инструкций некоторых процессоров, в частности семейства x86. На этом и остановимся.
В реальности не все простые могут ходить вперёд-влево. Поэтому в реальной программе придётся перед сдвигом выполнить ещё операцию AND, оставив только те шашки, которые имеют данную возможность. Если исключить техническую трудность с тем, что за один ход можно взять несколько шашек противника, то взятия простых рассматриваются аналогично, только нам надо будет выполнить два последовательных сдвига, на первом из которых делать AND с битбордом шашек противника, а на втором с битбордом свободных полей. Ниже приведён пример для случае проверки взятия вверх-влево:
all = bitboards[IDX_ALL_0] | bitboards[IDX_ALL_1];
enemy = bitboards[IDX_ALL_1 ^ active];
bitboard_t empty = ~all;
bitboard_t singles = bitboards[IDX_SIM | active];
bitboard_t try_left_up = ((((singles & possible_left_up) << 1) & enemy) << 1) & empty;
Мы получили достаточно эффективное решение, но оно работает только для доски 8x8. В случае международных шашек (доска 10x10) на доске 50 чёрных клеток. Используя схожий тип нумерации мы наступаем на грабли, что необходимо выполнить циклический сдвиг для 50-ти бит. Такой одной инструкции нет, так что придётся выполнять получения битовой маски за три операции: сдвиг влево, сдвиг вправо и OR. В случае шашек Спаринцети, которые ничем не отличаются от русских шашек, за исключением того, что используется доска 8x10, сложно придумать даже аналог подобной нумерации, так что скорее всего придётся использовать представление доски в виде подмножества 10x10.
Магия
Теперь рассмотрим вопросы, которые касаются взятия дамками. Может ли дамка осуществить взятие, какая шашка будет убита, куда может стать дамка после взятия? Кажется, что для ответа на эти вопросы не обойтись без нудного цикла. Но если присмотреться внимательно, то для ответа на эти вопросы используются только биты одной диагонали. Диагонали, которые параллельны двойнику (диагоналям g1-a7 и h2-b8) имеют последовательную нумерацию бит. Что приводит нас к довольно простой идее: битборд всех шашек надо сдвинуть вправо таким образом, чтобы все биты диагонали занимали самые младшие позиции. А потом просто обратиться к некоторой заранее составленной таблице. А это минимум операций!
// sq - поле, на котором расположена дамка
const struct square_info * sm = square_infos + sq;
// Получаем инфрмацию о поле, в частности нам надо значение shift - на сколько нам надо сдвинуть битовую маску всех шашек
uint32_t index = (all >> sm->shift) & 0x7F;
// Получаем индекс в нашей заранее вычисленной магической таблице
const struct mam_take_magic * mtm = mam_take_magic[sq] + index;
// mtm должна дать ответы на вопросы, можно ли совершить взятие, кто будет убит, и откуда можно продолжить ход
Для диагоналей, которые параллельны большаку, получить ответы на эти вопросы несколько сложнее. Один из способов, это поддерживать одновременно две нумерации, одна из которых была бы более удобна для проверки взятий по диагоналям, параллельных большаку, а другая — по диагоналях, параллельных двойнику. Такая нумерация выглядит как бы повёрнутой на угол 90º. Отсюда и название — вращаемые битборды. Когда я в своё время реализовывал генератор ходов в шахматах на основе этой идее, то всякий раз читая в шестнадцатиричном виде битборды, повёрнутые на 90º градусов, непроизвольно и сам поворачивал голову. Вот возможная нумерация для вращаемых битвордов:
+--+--+--+--+--+--+--+--+ | |25| |19| |13| | 7| 8 +--+--+--+--+--+--+--+--+ |24| |18| |12| | 6| | 7 +--+--+--+--+--+--+--+--+ | |17| |11| | 5| |31| 6 +--+--+--+--+--+--+--+--+ |16| |10| | 4| |30| | 5 +--+--+--+--+--+--+--+--+ | | 9| | 3| |29| |23| 4 +--+--+--+--+--+--+--+--+ | 8| | 2| |28| |22| | 3 +--+--+--+--+--+--+--+--+ | | 1| |27| |21| |15| 2 +--+--+--+--+--+--+--+--+ | 0| |26| |20| |14| | 1 +--+--+--+--+--+--+--+--+ a b c d e f g h
Но есть ещё и более красивая идея! Итак, рассмотрим большак. В нашем битборде это биты 0, 7, 14, 21, 28, 3, 10, 17. Нам надо придумать такую функцию, которая бы эти биты переставила на места с нулевого по седьмой, в любом порядке. Тогда бы мы смогли воспользоваться заранее подготовленой таблицей.
Как по мне, такая операция была бы очень полезна в наборе инструкций процессора, особенно который предназначен для реализации логики в разных играх. Сама инструкция могла бы иметь виде SUBBITS a, v, где a — некоторое число, v — битовая маска, которая указывает на то, какие биты следует оставить и перенести в младшие разряды. Например, SUBBITS 0xFF00FF, 0x111111 должна дать на выходе 1100112: оставляем биты с номерами 0, 4, 8, 12, 16, 20 и переносим нулевой бит в нулевую позиции, четвёртый — в первую, восьмой — во вторую,…
Ну это лирическое отступление. В большинстве случаем такую операцию несложно эффективно реализовать и имеющимися командами. Перенос битов вправо — это деление. На практике оказалось, что проще перенести все биты в самые левые позиции (умножение), а потом сделать большой сдвиг вправо. Каким образом?
Рассмотрим один бит. Допустим у нас есть число x, и мы хотим 10-й бит этого числа в 31-ю позицию, что станется с остальными битами нам неинтересно. Это достаточно простая задача, поскольку 31 — 10 = 21, то получаем x << 21. Предположим, что у нас есть не только 10-й бит, но еще и 20-й, который бы мы хотели перенести в 30-ю позицию. Сделать это не сложно:
bit10 = 1 << 10;
bit20 = 1 << 20;
mask10 = x & bit10;
mask20 = x & bit20;
result = (mask10 << 21) | (mask20 << 10);
А теперь попробуем взглянуть на эту последовательность по-другому. Во-первых, операцию OR в последней строке мы можем безболезненно заменить сложением: никакие переполнения нам жизнь не испортят. Во-вторых, после замены знака OR на плюс, выражение в последней строке подозрительно напоминает умножение. Действительно,
(x << 21) + (x << 10) == x * 0x00100400
mask10 и mask20 получаются из одного x, поэтому мы можем привести наш пример к виду:
bit10 = 1 << 10;
bit20 = 1 << 20;
mask = x & (bit10 | bit20);
result = mask * 0x00100400;
Если не обращать внимание, что в других битах может остаться мусор, это будет работать.
Подведём итоги. Если звёзды на небе стоят удачно, то перенести заданные биты в старшие позиции может получится операцией AND и умножением. А может и не получиться. В нашем случае биты с номерами 10 и 20 расположены далеко друг от друга, и результат сложения никак не может затронуть 31-й и 30-й биты результата.
Когда-же наш метод будет давать сбой? Пусть мы хотим перенести 4-й бит на 7-е место, 2-й бит на 6-е, а 0-й на 5-е. В данном случае наша магическая константа примет вид 0x38, в ней установлены три бита: пятый (сдвиг на пять), пятый и третий. Но проблема в том, что когда мы попробуем осуществить наше умножение, то биты наложатся один на другой:
* 10101
111000
--------
10101000
101010000
1010100000
-----------
???
Как обойти такую неприятность? Выход состоит в том, что мы можем попробовать другую перестановку бит. Например, 4→6, 2→7, 0→5. В этом случае наша магическая константа примет вид 0x24, в ней установлено только два бита, потому что второй и нулевой биты должны сдвинуться на одно и то же значение.
* 10101
100100
--------
1010100
1010100000
----------
..111.....
Что это обозначает применительно к битбордам в шашках? У нас есть семь диагоналей, и если нам повезёт, но мы сможем найти такую перестановку битов, что умножение на магическую константу перенесёт каждый бит в нужное место, и ничего не испортит. Но для этого нам необходимо будет написать отдельную программу поиска, которая бы не только нашла такие константы, сформировала бы магические массивы, хранящие ответы на вопросы, можно ли осуществить взятие, какая шашка убивается, на какие поля дамка может перейти после взятия (или продолжить бой).
Заключение
Конечно, при генерации списка ходов ещё могут возникнуть технические трудности. Например, надо не забыть про турецкий удар, когда убитые шашки снимаются с доски только после завершения удара. Но все они носят технический характер. Для этой статьи я реализовал небольшой учебный пример, в котором представлена реализация генератора ходов с использование магических битовых масок. Его можно сказать по ссылке checkers-0.1.tar.bz2.
