Sliding generation using magic

Question

This is a relatively large picture of how to check the movement of a fist in chess using magic bits. To clarify, I am not asking how the small bits inside work.

Now, a few more details about the question. I am writing a chessboard representation using a bit board, and I want to test moving pieces using magic bits. Can someone outline the basic steps to achieve this? As an example, consider the following position of the board:

Suppose we have all the magic functions and data structures initialized and ready to use. Therefore, using only function signatures for magic bits, can you list the steps (pseudo-code or any language) to check this step for the white rook on g3?

Answer 1

It’s good that we can assume that the functions of magic may be available, but in general, the functions for generating bitbit movements can take any methods that produce a billboard that gives a possible square for moving. Let's say RookMoves is such a function, then you will populate the list of movements as follows:

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

where Bit.Pop(ref x) returns the least significant bit in x , at the same time "jumping out" (removing) it from x .

To check the course (I interpret this as confirmation of the correct movement), you either check to see if the movement has been moved in the movement list, or do the movement and see if it leaves you in control. Of course, you may need to check if it obeys the rules of motion for the piece, but this is trivial.

 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

Simply put, small bits are an effective way to take a position and get legal steps for the moving part.

First, you need to find magic numbers. Some of the code you write to search for magic numbers will also be reused when using magic numbers.

To get started, you need to write 5 functions. They do not have to be particularly fast, because you will only use them when searching for magic numbers and once when starting the program before using your magic numbers. You can use any old technique in these functions.

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

So, you may ask yourself: da f% q is a blocking mask, a movement board and a blocker panel? Well, I just made the conditions, but here is what I mean:

 /* 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 */ 

A blocking mask is all the squares that can be occupied and so that your part moves further. The extreme squares do not have to be part of this, because your piece cannot move beyond this square. The number 1 in this board determines how many large search tables you need for this partial and square combination. In this case there are 10 of them, therefore there are 2 ^ 10 (1024) possible permutations of pieces that can block the rook e4.

The blocker board is one of these permutations. In this example, there are fragments on b4, c4, e2, e5 and e7. These are enemy and friendly things. The blocker board is always a subset of the blocker mask (it does not need to display shapes on other squares (for example, blockers = occupancy & blockermask; )).

The movement board is the available available moves for your unit, for this blocking board. This includes the ability to capture your play. Note that it also includes capturing your own parts (but you can just And this with NOT pieces in their places to remove them).

So, basically you need to create a blocker mask on all squares, both for the rook and for the bishop. And you also need to create all the possible blockers on each square, both for the rook and for the bishop. When you create blocker boards, you must also generate resulting displacement boards. Store all this in arrays for later use.

Now that you have it, for each combination of squares / parts you produce random 64-bit numbers and see if they are magical. You will find out how magical they are using the magic formula, return ((blockerboard*magic) >> (64-bits)); , which will create a magic index of 0..2 ^ bits (0..1024 in the case of the rook e4). For a certain part / square, if two blocker panels ever generate the same magic index , but these two blocker boards have different displacement boards, then this is a Muggle number, and you should try a new one.

Once you get this, you will have 64 magic rook numbers and 64 magic bishops numbers. To use them, when you start the program, you will initialize all blocking masks, blocking boards and move the boards. And now your program can effectively look for boards for bishops and rooks on any square (and therefore also the queen). The code for this will look something like this:

 /* 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 3

Haha never heard of the "magic board." Google is, and this is exactly what I expected. Although I do not see any magic in it. In any case, in order to answer your question, you need to create an accessible position of the movement bits of the part you have selected. Not sure what else is needed.

As for the psuedo code, I think:

 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 } 

I mean, there is nothing complicated about it, you just need to make sure that you get and set the position in a way that is compatible with the internal structure that you use.

EDIT:

Queen example:

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