使用魔术位板滑动移动生成

Question

这是关于如何使用魔术位板在国际象棋中验证滑动棋子移动的大图片的问题.只是为了澄清,我不是在问魔术比特板如何在内部工作.

现在,关于这个问题的更多细节.我正在使用位板编写棋盘表示,我想使用魔术位板验证滑动棋子移动.有人可以列出如何实现这一目标的主要步骤吗？作为一个例子,考虑以下董事会职位:

假设我们已经初始化并准备好使用所有魔术位板功能和数据结构.因此,仅使用魔术位板的功能签名,您是否可以列出步骤(伪代码或任何语言)来验证g3上白车的给定移动？

Answer 1

简而言之,魔术位板是一种有效的方式来获取位置并获得滑动件的合法移动.

首先,你需要找到一些神奇的数字.当您使用幻数时,您编写的用于查找幻数的一些代码也将被重复使用.

首先,您需要编写5个函数.这些不需要特别快,因为你只会在寻找魔术数字时使用它们,并且在你使用魔法数字之前在程序启动时使用它们.您可以在这些功能中使用任何旧技术.

uint64_t blockermask_rook   (int square);
uint64_t blockermask_bishop (int square);
uint64_t moveboard_rook     (int square, uint64_t blockerboard);
uint64_t moveboard_bishop   (int square, uint64_t blockerboard);
uint64_t blockerboard       (int index, uint64_t blockermask);

所以你可能会问自己,da f%q是阻挡面罩,移动板和阻挡板？好吧,我刚刚提出了条款,但这就是我的意思:

/* Example, Rook on e4:
 *  
 *    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 
 */

该拦截面膜是所有可以占用的平方和进一步移动阻止你的作品.边缘正方形不需要是其中的一部分,因为无论如何你的棋子都不能越过那个正方形.此位块中的1的数量决定了此块和方块组合所需的查找表的大小.在这种情况下,有10个,所以有2 ^ 10(1024)个可能阻止e4车的排列.

阻挡板是这些排列中的一种.在这个例子中,在b4,c4,e2,e5和e7上有片段.这些是敌人和友善的作品.阻挡板始终是阻挡掩模的子集(它不需要在其他方块上显示碎片(例如 blockers = occupancy & blockermask;)).

对于给定的阻挡板,移动板是您的作品的最终可用移动.这包括您作品的可能捕获.请注意,它还包括捕获您自己的碎片(但您可以使用NOT自己的碎片位置来除去它们).

因此,基本上你需要在所有方块上为车和主教生成阻挡掩码.而且你还需要为每个方块生成所有可能的阻挡板,用于车和主教.在生成阻挡板时,还应生成生成的移动板.将所有这些东西存储在数组中供以后使用.

现在你已经完成了,对于每个方块/件组合你尝试随机的64位数字,看看它们是否是魔法.你会通过使用魔法公式来了解它们是否具有魔力return ((blockerboard*magic) >> (64-bits));,这将创建一个从0..2 ^位(在e4车的情况下为0..1024)的神奇索引.对于某一块/方块,如果两个阻挡板产生相同的魔法指数,但这两个阻挡板有不同的移动板,那么这是一个麻瓜牌号,你应该尝试一个新的.

一旦你失败了,你将拥有64个魔法车号码和64个魔法主教号码.要使用它们,在程序启动时,您将初始化所有阻挡掩模,阻挡板和移动板.现在你的程序可以有效地查找任何广场上的主教和车的移动板(因此也是皇后).代码看起来像这样:

/* Retrieves the move board for the given square and occupancy board. */
uint64_t magic_move_rook  (int8_t square, uint64_t occupancy)
{
    /* Remove occupants that aren't in the blocker mask for this square. */
    occupancy &= Rook.blockmask[square];
    /* Calculate the magic move index. */
    int index = (occupancy*Rook.magic[square]) >> (64-Rook.bits[square]);
    /* Return the pre-calculated move board. */
    return Rook.moveboard[square][index];
}

Answer 2

我们可以假设魔术位板功能可用是很好的，但通常位板移动生成函数可以接受任何生成位板的技术，该位板提供可能的方块移动。说RookMoves是这样一个函数，那么你将按如下方式填充移动列表：

UInt64 pieceBitboard = Bitboard[SideToMove | Piece.Rook];
UInt64 targetBitboard = ~Bitboard[SideToMove | Piece.All];

while (pieceBitboard != 0) {
   Int32 from = Bit.Pop(ref pieceBitboard);
   UInt64 moveBitboard = targetBitboard & RookMoves(from, OccupiedBitboard);

   while (moveBitboard != 0) {
       Int32 to = Bit.Pop(ref moveBitboard);
       moveList[index++] = Move.Create(this, from, to);
   }
}

whereBit.Pop(ref x)返回最低有效位，x同时从x.

要验证移动（我将其解释为确认移动有效性），您可以检查移动是否在移动列表中，或者执行移动并查看它是否让您处于检查状态。当然，您可能需要检查它是否符合乐曲的移动规则，但这很简单。

if ((RookRays[move.From] & Bit.At[move.To]) == 0)
   return false;

Int32 side = SideToMove;
position.Make(move);
Boolean valid = position.InCheck(side);
position.Unmake(move);

return valid;