마법의 비트 보드를 사용하여 슬라이딩 이동 생성

Question

이것은 마법의 비트 보드를 사용하여 체스에서 슬라이딩 피스의 이동을 검증하는 방법에 대한 큰 그림과 관련한 질문입니다. 분명히하기 위해, 나는 마법의 bitboards가 내부적으로 어떻게 작동하는지 묻지 않고있다.

이제 질문에 대해 자세히 설명합니다. 나는 체스 보드 표현을 비트 보드를 사용하여 쓰고 있는데, 나는 마법의 비트 보드를 사용하여 슬라이딩 조각 동작을 검증하려고합니다. 누군가 그것을 달성하는 방법의 주요 단계를 열거 할 수 있습니까?

우리가 모든 마법 bitboard 기능과 데이터 구조를 초기화하고 사용할 준비가 가정 : 예를 들어 다음과 같은 보드의 위치를 ​​고려한다. 따라서 마법의 비트 보드에 대한 기능 서명 만 사용하면 g3에있는 흰색 루크의 특정 이동을 검증하기 위해 단계 (유사 코드 또는 다른 언어)를 나열 할 수 있습니까?

Answer 1

우리가 마법 bitboard 기능을 사용할 수 있다고 가정 할 수 있지만, 일반적으로 bitboard으로 이동 생성 기능이 bitboard을 생산하고 어떤 기술을 수용 할 수있는 좋은 그 이동 가능한 사각형을 제공합니다. 다음과 같이 당신이 이동 목록을 채우는 것, 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); 
    } 
} 

곳 x에서 Bit.Pop(ref 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; 

Answer 2

하하는 '마법의 간판'에 대해 들어 본 적이 없습니다. 구글 그것과 그것이 내가 예상했던 정확하게 것이다. 나는 그것에 대해 어떤 마법도 보지 못한다. 어쨌든 귀하의 질문에 대답, 당신은 현재 선택한 조각의 사용 가능한 이동 비트 위치를 생성해야합니다. 그 밖의 무엇이 필요한지 확신 할 수 없습니다. 사이비 코드를 뭔가로

그래서 같은 것 같아요 :

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

Answer 3

간단히 말하면, 마법의 비트 보드는 위치를 차지하고 슬라이딩 조각에 대한 법적 이동을 얻는 효율적인 방법입니다.

먼저 마법 번호를 찾아야합니다. 에 쓰는 코드 중 일부는 마법 번호를 사용하면 마법 번호가 다시 사용됩니다.

시작하려면 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 개가 있으므로 e4 루크를 차단할 수있는 조각의 2^10 (1024) 개의 가능한 순열이 있습니다.

차단기 보드는 이러한 순열 중 하나입니다. 이 예에서는 b4, c4, e2, e5 및 e7에 조각이 있습니다. 이들은 적 과 친화적 인 조각입니다. 차단기 보드는 항상 차단기 마스크의 하위 집합입니다 (다른 사각형에 조각을 표시 할 필요가 없습니다 (예 : blockers = occupancy & blockermask;)).

이동 보드는 주어진 차단기 보드에 대해 사용 가능한 이동 결과입니다. 여기에는 조각에 가능한 캡처가 포함됩니다. 자신의 조각을 캡처하는 것도 포함됩니다 (단, 자신의 조각 위치를 NOT으로 제거하면됩니다).

기본적으로 루크와 비숍 모두를 위해 모든 사각형에 차단제 마스크를 생성해야합니다. 그리고 루크와 비숍 모두를 위해 각 광장에 가능한 차단기 보드를 모두 만들어야합니다. 블로커 보드를 생성 할 때 결과 이동 보드도 생성해야합니다. 나중에 사용하기 위해 모든 것을이 배열에 저장하십시오.

이제 각 사각형/조각 콤보에 대해 임의의 64 비트 숫자를 시도하고 마술인지 확인하십시오. magic formula 인 return ((blockerboard*magic) >> (64-bits));을 사용하여 마술인지 알 수 있습니다.이 마술은 0..2 비트 (e4 루크의 경우 0..1024)의 마법 인덱스를 만듭니다. 특정 조각/정사각형의 경우, 두 개의 차단기 보드가 동일한 마법 색인 을 생성하지만 인 경우 두 개의 차단기 보드는 서로 다른 이동 보드를 가지고 있으며, 이는 머글 (muggle) 번호이므로 새로운 것을 시도해야합니다.

당신이 그것을 얻으면, 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]; 
}