Как найти волшебные битборды?

const int BitTable[64] = {
  63, 30, 3, 32, 25, 41, 22, 33, 15, 50, 42, 13, 11, 53, 19, 34, 61, 29, 2,
  51, 21, 43, 45, 10, 18, 47, 1, 54, 9, 57, 0, 35, 62, 31, 40, 4, 49, 5, 52,
  26, 60, 6, 23, 44, 46, 27, 56, 16, 7, 39, 48, 24, 59, 14, 12, 55, 38, 28,
  58, 20, 37, 17, 36, 8
};

int pop_1st_bit(uint64 *bb) {
  uint64 b = *bb ^ (*bb - 1);
  unsigned int fold = (unsigned) ((b & 0xffffffff) ^ (b >> 32));
  *bb &= (*bb - 1);
  return BitTable[(fold * 0x783a9b23) >> 26];
}

uint64 index_to_uint64(int index, int bits, uint64 m) {
  int i, j;
  uint64 result = 0ULL;
  for(i = 0; i < bits; i++) {
    j = pop_1st_bit(&m);
    if(index & (1 << i)) result |= (1ULL << j);
  }
  return result;
}

Это из Wiki по программированию шахмат:
https://www.chessprogramming.org/Looking_for_Magics

Это часть некоторого кода для поиска магических чисел.

Аргумент uint64 m - это битборд, представляющий возможные блокированные квадраты для хода ладьи или слона. Пример ладьи на поле е4:

0 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 
0 0 0 0 1 0 0 0 
0 0 0 0 1 0 0 0 
0 1 1 1 0 1 1 0 
0 0 0 0 1 0 0 0 
0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 0

Квадратные ребра равны нулю, потому что они всегда блокируют, и уменьшение количества необходимых битов, по-видимому, полезно.

/* Bitboard, LSB to MSB, a1 through h8:
 * 56 - - - - - - 63
 *  - - - - - - - -
 *  - - - - - - - -
 *  - - - - - - - -
 *  - - - - - - - -
 *  - - - - - - - -
 *  - - - - - - - -
 *  0 - - - - - - 7
 */

Таким образом, в приведенном выше примере index_to_uint64 принимает индекс (от 0 до 2 ^ бит), а также количество битов, установленных в битовой доске (10) и битовой доске.

Затем это pops_1st_bit для каждого количества битов, за которым следует еще один сдвинутый бит кода. pops_1st_bit XOR - это битборд с самим собой минус один (почему?). Затем он с полными 32-битными битами, и где-то здесь мой мозг исчерпывает ОЗУ. Каким-то образом задействовано магическое шестнадцатеричное число 0x783a9b23 (это последовательность чисел из Lost?). И есть этот нелепый загадочный массив случайно упорядоченных чисел от 0 до 63 (BitTable[64]).

Ответы

Ответ 1

Хорошо, я понял.

Во-первых, некоторая терминология:

блокирующая маска. Битовая панель, содержащая все квадраты, которые могут блокировать кусок, для данного типа куска и квадрата. Он исключает завершающие квадраты краев, поскольку они всегда блокируются.

панель блокировщика. Битовая плата, содержащая занятые квадраты. Он имеет только квадраты, которые также находятся в маскировке блока.

панель перемещения. Битовая доска, содержащая все квадраты, на которые может перемещаться кусок, с учетом типа куска, квадрата и блокатора. Он включает в себя завершающие краевые квадраты, если кусок может двигаться туда.

Пример для ладью на квадрате e4, и на e2, e5, e7, b4 и c4 есть некоторые случайные фрагменты.

 The blocker mask        A blocker board         The move board
 0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0         0 0 0 0 1 0 0 0         0 0 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0         0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0         0 0 0 0 1 0 0 0         0 0 0 0 1 0 0 0 
 0 1 1 1 0 1 1 0         0 1 1 0 0 0 0 0         0 0 1 1 0 1 1 1 
 0 0 0 0 1 0 0 0         0 0 0 0 0 0 0 0         0 0 0 0 1 0 0 0 
 0 0 0 0 1 0 0 0         0 0 0 0 1 0 0 0         0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0

Некоторые примечания:

Маска-блокиратор всегда одинакова для заданного квадрата и куска (ладья или слон).
Блокирующие доски включают дружественные и вражеские части, и это подмножество маскирования блока.
Результирующая доска для перемещения может включать в себя перемещения, которые захватывают ваши собственные части, однако эти перемещения легко удаляются впоследствии: moveboard &= ~friendly_pieces)

Цель метода магических чисел заключается в том, чтобы очень быстро просмотреть предварительно рассчитанную плату перемещения для данной блокаторного блока. В противном случае вам придется (медленно) вычислять плату перемещения каждый раз. Это касается только скользящих частей, а именно ладьи и слона. Королева - всего лишь комбинация ладьи и слона.

Магические числа можно найти для каждой комбинации квадратов и кусков. Для этого вам нужно рассчитать все возможные варианты блокатора для каждого квадратного/комбинированного комбо. Это то, что делает этот код. Как он это делает, для меня все еще немного, но что также кажется очевидным для оригинального автора, Мэтта Тейлора. (Спасибо @Pradhan за ссылку)

Итак, я сделал повторный ввод кода для генерации всех возможных вариантов блокаторов. Он использует другую технику, и хотя он немного медленнее, его гораздо легче читать и понимать. Тот факт, что он немного медленнее, не является проблемой, потому что этот код не критичен по скорости. Программа должна выполнить ее только один раз при запуске программы, и для двухъядерного i5 требуется только микросекунды.

/* Generate a unique blocker board, given an index (0..2^bits) and the blocker mask 
 * for the piece/square. Each index will give a unique blocker board. */
static uint64_t gen_blockerboard (int index, uint64_t blockermask) 
{
    /* Start with a blockerboard identical to the mask. */
    uint64_t blockerboard = blockermask;

    /* Loop through the blockermask to find the indices of all set bits. */
    int8_t bitindex = 0;
    for (int8_t i=0; i<64; i++) {
        /* Check if the i'th bit is set in the mask (and thus a potential blocker). */
        if ( blockermask & (1ULL<<i) ) {
            /* Clear the i'th bit in the blockerboard if it clear in the index at bitindex. */
            if ( !(index & (1<<bitindex)) ) {
                blockerboard &= ~(1ULL<<i); //Clear the bit.
            }
            /* Increment the bit index in the 0-4096 index, so each bit in index will correspond 
             * to each set bit in blockermask. */
            bitindex++;
        }
    }
    return blockerboard;
}

Чтобы использовать его, сделайте следующее:

int bits = count_bits( RookBlockermask[square] );
/* Generate all (2^bits) blocker boards. */ 
for (int i=0; i < (1<<bits); i++) {
    RookBlockerboard[square][i] = gen_blockerboard( i, RookBlockermask[square] );
}

Как это работает: Есть 2 ^ бит блокаторов, где bits - это число 1 в маске блокатора, которые являются единственными соответствующими битами. Кроме того, каждое целое число от 0 до 2 ^ бит имеет уникальную последовательность из 1 и 0 длины bits. Таким образом, эта функция просто соответствует каждому биту в данном целочисленном значении соответствующему биту в маске блокатора и отключает его/в соответствии с созданием уникальной панели блокатора.

Он не такой умный или быстрый, но читаемый.

Ответ 2

Хорошо, я попытаюсь пройти через это.

index_to_uint64( 7, 10, m );

7 - это просто случайно выбранное число между 0 и 2 ^ 10, а 10 - количество бит, установленных в m. m может быть представлено четырьмя способами:

bitboard:
0 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 
0 0 0 0 1 0 0 0 
0 0 0 0 1 0 0 0 
0 1 1 1 0 1 1 0 
0 0 0 0 1 0 0 0 
0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 0 
dec: 4521262379438080
hex: 0x1010106e101000
bin: 0000 0000 0001 0000 0001 0000 0001 0000 0110 1110 0001 0000 0001 0000 0000 0000

Перемещение. Это будет называться 10 раз. Он имеет возвращаемое значение и изменяет m.

pop_1st_bit(&m);

В pop_1st_bit, m называется bb. Я поменяю его на m для ясности.

uint64 b = m^(m-1);

Часть m-1 принимает младший значащий бит, который установлен и переворачивает его, и все биты под ним. После XOR все эти измененные биты теперь установлены на 1, а все старшие биты установлены на 0.

m  : 0000 0000 0001 0000 0001 0000 0001 0000 0110 1110 0001 0000 0001 0000 0000 0000 
m-1: 0000 0000 0001 0000 0001 0000 0001 0000 0110 1110 0001 0000 0000 1111 1111 1111
b  : 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 1111 1111 1111

unsigned int fold = (unsigned) ((b & 0xffffffff) ^ (b >> 32));

Часть AND (b & 0xffffffff) с более низкими 32 установленными битами. Таким образом, это по существу очищает любые биты в верхней половине b.

(b & 0xffffffff)
b: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 1111 1111 1111
&: 0000 0000 0000 0000 0000 0000 0000 0000 1111 1111 1111 1111 1111 1111 1111 1111
=: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 1111 1111 1111

Часть ... ^ (b >> 32) сдвигает верхнюю половину b в нижнюю половину, затем XOR выводит результат предыдущей операции. Таким образом, в основном XOR составляет верхнюю половину b с нижней половиной b. Это не имеет никакого эффекта в этом случае, потому что верхняя половина b была пуста для начала.

>> :0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 
^  :0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 1111 1111 1111 

uint fold = 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 1111 1111 1111

Я не понимаю смысла этого "складывания", даже если в верхней половине b были бит.

В любом случае, двигайтесь дальше. Эта следующая строка фактически изменяет m, снимая младший бит. Это имеет смысл.

m &= (m - 1);
m  : 0000 0000 0001 0000 0001 0000 0001 0000 0110 1110 0001 0000 0001 0000 0000 0000 
m-1: 0000 0000 0001 0000 0001 0000 0001 0000 0110 1110 0001 0000 0000 1111 1111 1111
&  : 0000 0000 0001 0000 0001 0000 0001 0000 0110 1110 0001 0000 0000 0000 0000 0000

Эта следующая часть умножает fold на какое-либо шестнадцатеричное число (простое?), справа сдвигает произведение 26 и использует его как индекс в BitTable, наш таинственный массив случайно упорядоченных чисел 0-63. На данный момент я подозреваю, что автор может писать генератор псевдослучайных чисел.

return BitTable[(fold * 0x783a9b23) >> 26];

Это завершает pop_1st_bit. Все это делается 10 раз (один раз для каждого бит, первоначально установленного в м). Каждый из 10 вызовов pop_1st_bit возвращает число 0-63.

j = pop_1st_bit(&m);
if(index & (1 << i)) result |= (1ULL << j);

В приведенных выше двух строках i - текущий бит, на котором мы находимся, 0-9. Поэтому, если число index (7, первоначально переданное как аргумент index_to_uint64), имеет бит i-го бита, затем установите j-й бит в результате, где j было возвращаемым значением 0-63 из pop_1st_bit.

И это! Я все еще смущен: (

Ответ 3

Когда вы смотрели серию видео на шахматных машинах на YouTube, у меня были те же вопросы, что и paulwal222. Кажется, что есть некоторые математики высокого уровня. Лучшие ссылки, объясняющие предысторию этого сложного вопроса, https://chessprogramming.wikispaces.com/Matt+Taylor и https://chessprogramming.wikispaces.com/BitScan. Похоже, что Мэтт Тейлор в 2003 году в google.group(https://groups.google.com/forum/#!topic/comp.lang.asm.x86/3pVGzQGb1ys) (также найденный pradhan) придумал что-то, что сейчас называемый складной трюк Мэтта Тейлора, 32-битная дружественная реализация, чтобы найти бит-индекс LS1B (https://en.wikipedia.org/wiki/Find_first_set). Тейлор складной трюк, по-видимому, является адаптацией De Bruijn (https://en.wikipedia.org/wiki/Nicolaas_Govert_de_Bruijn), который был разработан в 1997 году, согласно Дональду Кнуту Мартином Ляутером определите индекс LS1B минимальным совершенным хешированием (https://en.wikipedia.org/wiki/Perfect_hash_function). Числа BitTable (63, 30,..) и складки в PopBit (0x783a9b23), вероятно, являются так называемыми магическими числами (уникально?), Связанными с 32-битным трюком для Matt Taylor. Этот складной трюк кажется очень быстрым, потому что многие двигатели скопировали этот подход (f.i Stockfish).