0

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

https://rhysre.net/fast-chess-move-generation-with-magic-bitboards.html#:~:text=A%20bitboard%20is%20simply%20a,and%20bit%2063%20%3D%20h8 )

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

  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”数组？我不明白如何在给定每个正方形的攻击掩码和幻数的情况下生成该二维数组。提前谢谢你的帮助。

4

1 回答 1

1

对于每个正方形，您需要在主教掩码内生成每个块的排列。例如，将此掩码用于正方形 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) 是全掩码。

这是一个方法，它采用置换数和主教掩码并返回相应的阻塞位板：

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

使用它，我们可以计算带有幻数和拦截器的密钥，我们可以创建它们对应的值，即攻击掩码。

对于每个阻塞块的排列，创建相应的攻击掩码并将其存储在表中。在面罩中包括挡块和板侧面的方块。方块#28 上的拦截器#339 的攻击掩码为：

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 个主教查找表的 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。普通的魔法位板为 rooks 占用 2Mib 的内存，为主教占用 256Kib 的内存，使用花式魔法位板可以将总数减少到 ~800Kib。但它并不是真正需要的，2.25Mib 的内存很小。

于 2021-05-17T04:45:24.537 回答