如何为魔术位板生成这个预初始化数组？

Question

我目前正在尝试使我的国际象棋引擎更快，并正在考虑为我的滑块攻击生成实现魔术位板。我使用棋盘的位板表示，a1方格是最右边的位，h8是最左边的位。我正在查看这个网站：

https://rhysre.net/fast-chess-move-generation-with-magic-bitboards.html#:~:text=位板就是一个，位63=h8）

特别是在页面底部找到的代码片段，内容如下：

  U64 getBishopAttacksMagic(int square, U64 blockers) {
  // Mask blockers to only include bits on diagonals
  blockers &= BISHOP_MASKS[square];

  // Generate the key using a multiplication and right shift
  U64 key = (blockers * BISHOP_MAGICS[square]) >> (64 - BISHOP_INDEX_BITS[square]);

  // Return the preinitialized attack set bitboard from the table
  return BISHOP_TABLE[square][key];
}

我已经有了浅蓝色魔法数字（每个数字对应一个正方形），并且我已经有了存储在64长度数组中的毕晓普作品的预初始化攻击掩码（同样，每个数字对应一个正方形）。所以我知道怎么拿到钥匙。但我如何生成最后一个接受密钥的数组，“BISHOP_TABLE”数组呢？我不知道如何在给定攻击面具和每个方块的魔法数的情况下生成2d阵列。提前感谢您的帮助。

Answer 1

对于每一个方块，你需要在bishop掩模中生成每一个块的排列。例如，将此遮罩用于方形e4（#28）：

8 | 0 0 0 0 0 0 0 0
7 | 0 1 0 0 0 0 0 0
6 | 0 0 1 0 0 0 1 0
5 | 0 0 0 1 0 1 0 0
4 | 0 0 0 0 0 0 0 0
3 | 0 0 0 1 0 1 0 0
2 | 0 0 1 0 0 0 1 0
1 | 0 0 0 0 0 0 0 0
    ---------------
    a b c d e f g h

由于有9个集合位，因此有2^9=512个不同的阻塞块模式。排列号339（作为二进制=0b101010011）如下所示：

8 | 0 0 0 0 0 0 0 0
7 | 0 1 0 0 0 0 0 0
6 | 0 0 1 0 0 0 0 0
5 | 0 0 0 1 0 0 0 0
4 | 0 0 0 0 0 0 0 0
3 | 0 0 0 0 0 0 0 0
2 | 0 0 1 0 0 0 1 0
1 | 0 0 0 0 0 0 0 0
    ---------------
    a b c d e f g h

位在数字中从右（lsb）到左（msb）读取，并在掩码中从a文件设置为h文件，从第1位到第8位。置换0是一个空板，511（0b111111111）是完整掩码。

下面是一个方法，它使用一个置换数和bishop掩码，并返回相应的阻止程序位板：

private static long blockersPermutation(int iteration, long mask) {
    long blockers = 0;

    while (iteration != 0) {
        if ((iteration & 1) != 0) {
            int shift = Long.numberOfTrailingZeros(mask);
            blockers |= (1L << shift);
        }

        iteration >>>= 1;
        mask &= (mask - 1); // used in Kernighan's bit count algorithm
        // it pops out the least significant bit in the number
    }

    return blockers;
}

使用这个，我们可以计算出带有魔法数字和拦截器的密钥，我们可以创建它们相应的值，即攻击掩码。

对于块的每个排列，创建相应的攻击掩码并将其存储在表中。包括遮罩板侧面的挡块和方块。阻挡者#339 on square#28的攻击面具是：

8 | 0 0 0 0 0 0 0 0
7 | 0 0 0 0 0 0 0 1
6 | 0 0 0 0 0 0 1 0
5 | 0 0 0 1 0 1 0 0
4 | 0 0 0 0 0 0 0 0
3 | 0 0 0 1 0 1 0 0
2 | 0 0 1 0 0 0 1 0
1 | 0 0 0 0 0 0 0 0
    ---------------
    a b c d e f g h

下面是初始化64个bishop查找表的Java方法：

private final long[][] BISHOP_LOOKUP = new long[64][512];

private static int getFile(int square) {
    return square % 8;
}

private static int getRank(int square) {
    return square / 8;
}

private static int getSquare(int rank, int file) {
    return rank * 8 + file;
}

// just like the code snippet, generates the key
private static int transform (long blockers, long magic, int shift) {
    return (int) ((blockers * magic) >>> (64 - shift));
}

private void initBishopLookup() {
    for (int square = 0; square < 64; square++) {
        long mask = BISHOP_MASKS[square];
        int permutationCount = (1 << Long.bitCount(mask));

        for (int i = 0; i < permutationCount; i++) {
            long blockers = blockersPermutation(i, mask);
            long attacks = 0L;
            int rank = getRank(square), r;
            int file = getFile(square), f;

            for (r = rank + 1, f = file + 1; r <= 7 && f <= 7; r++, f++) {
                attacks |= (1L << getSquare(r, f));
                if ((blockers & (1L << getSquare(r, f))) != 0) {
                    break;
                }
            }

            for (r = rank - 1, f = file + 1; r >= 0 && f <= 7; r--, f++) {
                attacks |= (1L << getSquare(r, f));
                if ((blockers & (1L << getSquare(r, f))) != 0) {
                    break;
                }
            }

            for (r = rank - 1, f = file - 1; r >= 0 && f >= 0; r--, f--) {
                attacks |= (1L << getSquare(r, f));
                if ((blockers & (1L << getSquare(r, f))) != 0) {
                    break;
                }
            }

            for (r = rank + 1, f = file - 1; r <= 7 && f >= 0; r++, f--) {
                attacks |= (1L << getSquare(r, f));
                if ((blockers & (1L << getSquare(r, f))) != 0) {
                    break;
                }
            }

            int key = transform(blockers, BISHOP_MAGICS[square], Long.bitCount(mask));

            BISHOP_LOOKUP[square][key] = attacks;
        }
    }
}

这使用了带有固定大小查找表的普通魔术位板，当设置位较少的掩码可以容纳较少的空间时，所有长度都为512。与正方形b1一样，遮罩在对角线上使用5位，表格可以放入长度为2^5=32的数组中。我们在浪费（512-32）*（每64位数字8字节）/1024字节/Kio=3.75Kio的空间。普通魔法比特板为Rook占用2MB内存，为Bishop占用256Kib内存，使用奇特的魔法比特板可以将总内存减少到~800Kib。但实际上并不需要，2.25Mib的内存很小。