2

I've been trying to understand magic bitboards, but everywhere I've read failed to explain how edge pieces are handled.

The pieces at the borders are ignored to save space.

So for a bishop at D3, the move mask would be:

00000000
00000000
00000010
01000100
00101000
00000000
00101000
00000000

instead of:

00000000
00000001
10000010
01000100
00101000
00000000
00101000
01000100

checking if a piece at C4 can be attacked by the bishop can be easily done by anding the move mask and a bitboard representing C4.

But, you wouldn't be able to do that for a piece at the border?

for example, you wouldn't be able to determine if a piece at A6 can be attacked by anding since it wasn't included in the move mask in the first place.

How would you determine attacks at borders that have been ignored?

2
  • 3
    That's not how magic bitboards work. The algorithm to obtain bishop attacks doesn't involve just ANDing the "move mask" with the occupiers bitboard. The reason the borders are ignored for this "move mask" is because a piece on the border has no effect on whether a bishop/rook can attack other squares. Jun 26 at 11:01
  • 1
    Hi Foder, see if my comments here help you at all: github.com/algerbrex/blunder/blob/develop/engine/magic.go Jun 28 at 21:27

2 Answers 2

1

The method of magic bitboards basically applies a hash function to the important occupancy, or in other words, all the pieces that could potentially block the currently moving piece.

For example, let's suppose that we have a rook on e4.

. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . 1 . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .

and that our occupancy looks like this:

. . . . 1 . . .
. . . . . . . .
. . . . 1 . . .
. . . . . . . .
. . . . R . . 1
. . . . 1 . . .
. . . . . . . .
. . . . . . . .

After hashing, we get an index into our table, and by accessing that index we should obtain the move-mask.

Our move mask, i.e. the squares that the rook can move to (without considering squares our pieces currently occupy), should look like this:

. . . . . . . .
. . . . . . . .
. . . . 1 . . .
. . . . 1 . . .
1 1 1 1 R 1 1 1
. . . . 1 . . .
. . . . . . . .
. . . . . . . .

The closest occupancies to the rook are registered as legal squares. They have to be AND'd with NOT our pieces. This way, we register captures as legal squares.

Note that the occupancy on h4 does not affect the movemask at all. Regardless of whether the h4 piece is there, we are still generating the same attackmask. So, the h4 piece isn't really a blocker.

The reason why removing the edges reduces memory is because to store the bitboards, we have to check through every possible permutation of relevant blockers for a rook or bishop on a given square, generate the attack mask, and apply the magic hashing to it generate an index into our hash table, which contains all of the corresponding attack masks. By removing redundant bits that don't affect the generated move-mask we can significantly reduce the size of our table.

2

The move mask is only used to obtain the pieces that will block the Bishop. Edge pieces will never block any diagonal moves.

Given the blockers and the Bishop's location the algorithm then looks up the set of unblocked moves. Under the assumption that all blockers are foes. So to get actual pseudo-legal moves you would still have to ANDNOT with the friendly pieces. But usually you want to generate captures and non-captures separately, so for the captures you would AND with enemy pieces, and for non-ceptures ANDNOT with the 'occupied' (all pieces) bitboard.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.