¿Cómo encontrar bitboards mágicos?

bit-manipulation chess (3)

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; }

Es de la Wiki de Programación de Ajedrez:
https://www.chessprogramming.org/Looking_for_Magics

Es parte de algún código para encontrar números mágicos .

El argumento uint64 m es un bitboard representa los posibles cuadrados bloqueados para un movimiento de torre o alfil. Ejemplo para una torre en el cuadrado e4:

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

Los cuadrados de borde son cero porque siempre se bloquean, y reducir la cantidad de bits necesarios parece ser útil.

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

Entonces, en el ejemplo anterior, index_to_uint64 toma un índice (0 a 2 ^ bits), y la cantidad de bits establecidos en el bitboard (10), y el bitboard.

Luego pops_1st_bit para cada número de bits, seguido de otro bit de código shifty. pops_1st_bit XORs el bitboard consigo mismo menos uno (¿por qué?). Luego lo hace con un total de 32 bits, y en algún lugar por aquí mi cerebro se queda sin memoria RAM. De alguna manera, el número hexadecimal mágico 0x783a9b23 está involucrado (¿es esa la secuencia numérica de Perdido?). Y hay una matriz de misterio ridícula de números ordenados al azar de BitTable[64] ( BitTable[64] ).

Cuando vi una serie de videos sobre motores de ajedrez en youtube, tuve exactamente las mismas preguntas que paulwal222. Parece que hay algunas matemáticas de alto nivel involucradas. Los mejores enlaces que explican los antecedentes de este tema difícil son https://chessprogramming.wikispaces.com/Matt+Taylor y https://chessprogramming.wikispaces.com/BitScan . Parece que Matt Taylor en 2003 en un google.group ( groups.google.com/forum/#!topic/comp.lang.asm.x86/3pVGzQGb1ys ) (también encontrado por pradhan) llegó a algo que ahora se llama truco de plegado de Matt Taylor, una implementación fácil de 32 bits para encontrar el índice de bits de LS1B ( https://en.wikipedia.org/wiki/Find_first_set ). El truco de plegado de Taylor aparentemente es una adaptación de los bitscan De Bruijn ( https://en.wikipedia.org/wiki/Nicolaas_Govert_de_Bruijn ), ideada en 1997, según Donald Knuth por Martin Läuter para determinar el índice LS1B por hash mínimo perfecto ( https://en.wikipedia.org/wiki/Perfect_hash_function ). Los números de BitTable (63, 30, ..) y el pliegue en PopBit (0x783a9b23) son probablemente los llamados números mágicos (¿de forma única?) Relacionados con el truco de plegado de Matt Taylor de 32 bits. Este truco de plegado parece ser muy rápido, ya que muchos motores han copiado este enfoque (fi stockfish).

Muy bien, lo tengo resuelto.

Primero, alguna terminología:

Máscara bloqueadora : un bitboard que contiene todos los cuadrados que pueden bloquear una pieza, para un tipo de pieza determinado y el cuadrado en el que se encuentra la pieza. Excluye cuadrados de borde de terminación porque siempre se bloquean.

Tablero bloqueador : un bitboard que contiene cuadrados ocupados. Solo tiene cuadrados que también están en la máscara bloqueadora.

mover tablero : un bitboard que contiene todos los cuadrados a los que se puede mover una pieza, dado un tipo de pieza, un cuadrado y un tablero bloqueador. Incluye cuadrados de borde de terminación si la pieza puede moverse allí.

Ejemplo para una torre en el cuadrado e4, y hay algunas piezas aleatorias en e2, e5, e7, b4 y 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

Algunas cosas a tener en cuenta:

La máscara de bloqueo es siempre la misma para un cuadrado y tipo de pieza dados (ya sea torre o alfil).
Los tableros bloqueadores incluyen piezas amigas y enemigas, y es un subconjunto de la máscara bloqueadora.
El tablero de movimientos resultante puede incluir movimientos que capturen tus propias piezas, sin embargo, estos movimientos se eliminan fácilmente después: moveboard &= ~friendly_pieces)

El objetivo del método de los números mágicos es buscar rápidamente un tablero de movimientos precalculado para un tablero bloqueador determinado. De lo contrario, tendrías que (lentamente) calcular el tablero de movimientos cada vez. Esto solo se aplica a las piezas deslizantes, a saber, la torre y el alfil. La reina es solo una combinación de la torre y el obispo.

Se pueden encontrar números mágicos para cada combo de tipo cuadrado y pieza. Para hacer esto, tienes que calcular cada variación posible de la tabla del bloqueador para cada combo cuadrado / pieza. Esto es lo que hace el código en cuestión. Cómo lo hace todavía es un misterio para mí, pero groups.google.com/forum/#!topic/comp.lang.asm.x86/3pVGzQGb1ys . (Gracias a @Pradhan por el enlace)

Entonces, lo que he hecho es volver a implementar el código para generar todas las posibles variaciones de la placa bloqueadora. Utiliza una técnica diferente y, aunque es un poco más lento, es mucho más fácil de leer y comprender. El hecho de que sea un poco más lento no es un problema, porque este código no es crítico para la velocidad. El programa solo tiene que hacerlo una vez al inicio del programa, y solo toma microsegundos en un i5 de doble núcleo.

/* 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''s 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; }

Para usarlo, haz algo como esto:

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] ); }

Cómo funciona: Hay 2 ^ tablas de bloqueadores de bits, donde bits es el número de 1 en la máscara de bloqueo, que son los únicos bits relevantes. Además, cada entero de 0 a 2 ^ bits tiene una secuencia única de 1 y 0 de bits de longitud. Por lo tanto, esta función simplemente corresponde cada bit en el entero dado a un bit relevante en la máscara del bloqueador, y lo activa / desactiva en consecuencia para generar una placa de bloqueador única.

No es tan inteligente o rápido, pero es legible.

Muy bien, voy a tratar de pasar por esto.

index_to_uint64( 7, 10, m );

7 es solo un número elegido al azar entre 0 y 2 ^ 10, y 10 es el número de bits establecido en m. m se puede representar de cuatro maneras:

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

Seguir adelante Esto se llamará 10 veces. Tiene un valor de retorno y modifica m.

pop_1st_bit(&m);

En pop_1st_bit, m es referido por bb. Voy a cambiarlo por claridad.

uint64 b = m^(m-1);

La parte m-1 toma el bit menos significativo que se establece y lo voltea y todos los bits debajo de él. Después del XOR, todos esos bits modificados ahora se establecen en 1, mientras que todos los bits más altos se establecen en 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));

La parte (b & 0xffffffff) b con 32 bits más bajos establecidos. Así que esto esencialmente borra cualquier bit en la mitad superior de 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

La parte ... ^ (b >> 32) desplaza la mitad superior de b a la mitad inferior, luego la retorna con el resultado de la operación anterior. Así que básicamente XORs la mitad superior de b con la mitad inferior de b. Esto no tiene efecto en este caso porque, para empezar, la mitad superior de b estaba vacía.

>> :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

No entiendo el punto de ese "plegado", incluso si hubiera bits establecidos en la mitad superior de b.

De todos modos, seguir adelante. La siguiente línea en realidad modifica m al desactivar el bit más bajo. Eso tiene algún sentido.

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

La siguiente parte multiplica el fold por algún número hexadecimal (¿primo?), La derecha desplaza el producto 26 y lo utiliza como un índice en BitTable, nuestra misteriosa variedad de números ordenados al azar 0-63. En este punto, sospecho que el autor podría estar escribiendo un generador de números pseudoaleatorios.

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

Eso concluye pop_1st_bit. Eso se hace 10 veces (una vez por cada bit establecido originalmente en m). Cada una de las 10 llamadas a pop_1st_bit devuelve un número 0-63.

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

En las dos líneas anteriores, i es el bit actual en el que estamos, 0-9. Entonces, si el número de index (los 7 pasados originalmente como un argumento a index_to_uint64) tiene establecido el bit i''th, entonces establezca el bit j''th en el resultado, donde j fue el valor de retorno de 0-63 de pop_1st_bit.

¡Y eso es! Todavía estoy confundido :(