Сдвижное поколение поколений с использованием магической доски

Question

Это вопрос относительно большой картины того, как проверять перемещение кулака в шахматы с помощью магических битов. Чтобы уточнить, я не спрашиваю , как магические биты работают внутри.

Теперь, более подробную информацию о запросе. Я пишу представление шахматной доски с помощью битовой платы, и я хочу проверить подвижные куски с использованием магических битов. Может ли кто-нибудь изложить основные шаги по достижению этого? В качестве примера рассмотрим следующую позицию платы:

Предположим, у нас есть все магические функции 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); 
    } 
} 

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; 

Answer 2

Хаха никогда не слышал о «волшебной доске». Google это, и это именно то, что я ожидал. Хотя я не вижу в этом никакой магии. В любом случае, чтобы ответить на ваш вопрос, вам нужно создать доступную позицию битов перемещения выбранной вами части. Не уверен, что еще нужно.

Что касается псевдо кода что-то вроде, так что я предполагаю:

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 
    } 

Я имею в виду не что иное, трудно об этом, вы просто должны убедиться, что вы получаете и установить позицию таким образом, совместимым с внутренней структурой вы используются.

EDIT:

пример королевы:

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

Таким образом, вы можете спросить себя, да 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;)).

Плата перехода является результирующими доступными ходами для вашей части для данной блокирующей доски. Это включает в себя возможность захвата вашей пьесы. Обратите внимание, что это также включает в себя захват ваших собственных произведений (но вы можете просто И это с НЕ из ваших мест кусочков, чтобы удалить их).

Итак, в основном вам нужно создать маску блокировщика на всех квадратах, как для ладьи, так и для слона. И вам также нужно создать все возможные блокираторы на каждом квадрате, как для ладьи, так и для слона. Когда вы создаете доски блокаторов, вы также должны генерировать результирующие платы перемещения. Храните все это в массивах для последующего использования.

Теперь, когда вы сделали это, для каждой комбинации квадратов/частей вы производите случайные 64-битные номера и видите, являются ли они волшебными. Вы узнаете, являются ли они волшебными, используя магическую формулу, return ((blockerboard*magic) >> (64-bits));, которая создаст магический индекс из 0..2^бит (0..1024 в случае ладьи e4). Для определенного куска/квадрата, если две блокирующие доски когда-либо генерируют один и тот же магический индекс , но, эти две платы-доски имеют разные доски для перемещения, тогда это номер магглов, и вы должны попробовать новый.

Как только вы получите это, у вас будет 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]; 
}