这是有关使用神奇位板验证国际象棋滑动棋子移动的大局观问题。为了澄清，我并不是在问神奇位板的内部工作原理。
现在，关于问题的更多细节。我正在使用位板编写国际象棋棋盘表示，并且希望使用神奇位板来验证滑动棋子的移动。能否有人列出实现这一点的主要步骤？ 以以下位置为例：
假设我们已经初始化并准备好使用所有神奇位板函数和数据结构。因此，仅使用神奇位板的函数签名，您能否列出验证g3白色战车的特定移动的步骤（伪代码或任何语言）？
3个回答
45
简单来说，魔幻位棋盘是一种有效的方法，可以对一个位置进行操作并获得滑动棋子的合法移动。
首先，你需要找到一些魔数。你编写代码以查找魔数时，一些代码也会在你使用魔数时被重复使用。
首先，你需要编写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);
所以你可能会问：什么是阻挡器面罩、移动板和阻拦板？好吧，这些术语是我刚刚编出来的，但是我是这样理解它们的：
/* 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个1，因此可以将阻挡e4车的棋子排列成2^10（1024）种可能。
阻挡板是其中之一排列。在这个例子中，b4、c4、e2、e5和e7上有棋子。它们既是敌方的，也是友方的。阻挡板始终是阻挡掩码的子集（不必显示其他位置上的棋子（例如
blockers = occupancy & blockermask;））。移动板是给定阻挡板的棋子可用的结果，包括棋子的可能捕获。请注意，它还包括捕获您自己的棋子（但您可以使用您自己的棋子位置的NOT与之AND以移除这些）。
因此，基本上您需要为车和象在所有位置上生成所有方块的阻挡掩板。您还需要为每个位置上的车和象生成所有可能的阻挡板。当您生成阻挡板时，应该同时生成结果移动板，并将所有这些东西存储在数组中以备后用。
现在，对于每个方块/棋子组合，您需要尝试随机64位数字并查看它们是否是神奇数字。通过使用神奇公式
return ((blockerboard*magic) >> (64-bits));，您将从0..2^bits（在e4 rook的情况下是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];
}
- paulwal222
7
1这是一个非常好的答案，对我来说确实让事情清晰很多。现在唯一让我困惑的是索引到底是什么，以及为什么它能正确地指向moveboard数组中的正确位置。您是否有任何可以帮助我更清楚理解这一点的地方？我已经查阅了所有通常的地方，例如国际象棋编程维基、各种博客文章等。 - abarax
2这是魔法，伙计。说真的，去年夏天写答案的时候我把一切都弄清楚了，现在我却难以回忆起来。所以通过魔法公式返回的索引总是小于封锁板块（BB）的总数。每个BB都有相应的移动板（MB）。当搜索魔法时，你正在使用一种慢算法计算每个MB，并将其存储在由候选魔法数字计算出的索引上。在引擎启动时，MB会重新计算，然后只需将它们存储在由预设好的魔法数字计算出的索引上。 - paulwal222
3即使您有1024个BB，每个BB都对应一个MB，但最终可能存储的MB数量会少于1024个。例如，对于两个具有相同MB的不同BB，魔术计算可能会计算出两个不同的索引，也可能会为两个BB计算相同的索引。只要MB相同，索引冲突就可以了。因此，直接回答您的问题，我们之所以能找到一个数字，它恰好能够为唯一的MB计算出唯一的索引，这只是运气/概率问题。然后，我们在引擎启动时使用魔法公式和我们已知的魔法故意将MB存储在正确的索引位置上。 - paulwal222
1@paulwal222 这个答案对我很有帮助，而且会继续帮助其他查找魔术位板的人！ - user14248283
1感谢您详细的回答。每个句子都是非常有价值的信息。 - chindirala sampath kumar
显示剩余2条评论
6
很好，我们可以假设魔术位棋盘函数可用，但是通常位棋盘移动生成函数可以接受任何产生给出可移动方格的位棋盘的技术。例如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);
}
}
Bit.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;
- Zong
4
非常感谢您，Zong Zheng Li，这回答了我的问题。虽然我目前采取了更简单的方法（http://chessprogramming.wikispaces.com/Classical+Approach），但一旦我理解了整个过程，包括搜索和评估，我会立即回到魔法棋盘上。 - bytefire
@bytefire 是的，在我的引擎中，我也使用了经典的方法，因为它很容易作为一个临时组件实现。我发现它足够快（
perft(6)只需2秒），切换到魔术生成所获得的收益几乎可以忽略不计，所以我就保留了它。 - Zong这非常有帮助，因为它为我当前正在实现的内容增加了更多的含义。顺便说一下，当我遇到更多障碍时，我将在 SO 上发布带有“chess”标签的问题。期待更多的帮助 :) - bytefire
@ZongZhengLi 2秒内完成6次Perft？你能帮我吗？请看我的问题：http://chess.stackexchange.com/questions/15705/c-vs-java-engine-move-generation-performance。 - Fernando
-15
哈哈，从来没听说过“魔术位棋盘”。谷歌一下，果然和我预想的一样。虽然我没看出有什么神奇的地方。不管怎样，回答你的问题，你需要生成当前选定棋子的可移动位位置。不确定还需要什么其他信息。
至于伪代码，大概是这样吧：
至于伪代码，大概是这样吧：
Positions KingChessPiece::getMovablePositions(){
(x,y) = current bit position in the bitboard
availablePosition = [ (x+1,y),(x-1,y),(x,y+1),(x,y-1) ]
for each position in availablePosition
if p_i is occupied then remove it from list
return availablePosition
}
我的意思是这个并不难，你只需要确保以与你使用的内部结构兼容的方式获取和设置位置。
编辑：
一个皇后的例子：
Position QueenChessPiece::getMovablePosition(){
(x,y) = queens current position
availablePosition = []; //empty list
//check diagonal positions
//move top left diagonal
availablePosition.concat( this.generateAvailablePosition(x,y,-1,1);
//move top right diagonal
availablePosition.concat( this.generateAvailablePosition(x,y,1,1);
//move bottom right diagonal
availablePosition.concat( this.generateAvailablePosition(x,y,1,-1);
//move bottom left diagonal
availablePosition.concat( this.generateAvailablePosition(x,y,-1,-1);
//move straight up
availablePosition.concat( this.generateAvailablePosition(x,y,0,1) )
//move straight down
availablePosition.concat( this.generateAvailablePosition(x,y,0,-1) )
//move left
availablePosition.concat( this.generateAvailablePosition(x,y,-1,0) )
//move right
availablePosition.concat( this.generateAvailablePosition(x,y,1,0) )
return availablePosition;
}
Position QueenChess::generateAvailablePosition(x,y,dx,dy){
availPosition = [];
while( !isSpaceOccupied(x + dx , y + dy))
availPosition.add( position(x + dx ,y + dy) );
x += dx;
y += dy;
endWhile
return availPosition;
}
- dchhetri
7
谢谢您的回复。这对于国王来说还可以，但车怎么办？对于滑动棋子（如车、象和后），情况并不简单。阻挡者会阻挡它所占据的方格以及移动方向上之后的任何方格。 - bytefire
1不，魔术位板只在移动生成之前生成攻击地图一次。当它涉及到生成时，它只是一个表查找。这是一个天真的实现，根本没有利用位板的优势。 - Zong
它预先生成攻击地图吗？你能解释一下吗？ - dchhetri
因此，查找表基本上为每个在位置（x，y）的棋子预生成移动位置吗？ - dchhetri
请查看以下链接了解有关神奇位板的内容：https://chessprogramming.wikispaces.com/Magic+Bitboards - techcraver
显示剩余2条评论
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接