Magic Bitboards: Finding all valid bishop moves in a 64-bit multiply (2008)

The code I'd like to highlight in this example is as follows:

    U64 bishopAttacks(U64 occ, enumSquare sq) {
       occ &= mBishopTbl[sq].mask;
       occ *= mBishopTbl[sq].magic;
       occ >>= 64-9;
       return mBishopAttacks[sq][occ];
    }

Two bit-operations and one Multiply are all that is needed to "perfect hash" a bishop's position + all of the possible combinations of pieces which might block it. From there, the "occ" variable serves as a lookup-table's index, providing a pre-calculated bitmask of all of the locations a bishop can attack.

It seems like the "occ" bitboard represents the occupancy of the board. (A bitmask of 1 for every piece that could block the bishop's movement). While "enumSquare" seems to be the square the bishop is actually on.

In effect, this is a time-space tradeoff, with every single bishop (or rook) attack being precomputed in a lookup table. Then, during runtime, two-bit operations + one multiply are all that is needed to use the table.

---------------

Some notes to help decipher what is going on:

* Because a chessboard is 64 squares, a 64-bit long integer is all that's needed to represent true/false values across a board. These "true-false" collections across a chessboard are called "bitboards", and can represent anything from board state (Ex: a bitboard that represents all black pawns), to "potential moves a bishop can make" that the AI should iterate against.

* The general problem to solve here is called the Sliding Piece Attack: https://chessprogramming.wikispaces.com/Sliding+Piece+Attack... . Bishops and Rooks are complicated, because they may be blocked by enemy and/or friendly pieces. Other pieces (Knights, Pawns, or Kings) have much simpler movement patterns.

That's what makes this so magnificent: the calculation in runtime is calculated in something like ~15 clock cycles on a modern machine. (2 cycles for the two bitwise operations, 5 cycles for the multiply, and 5 cycles for an L2 lookup)

Using bit manipulation to calculate chess piece movements is really quite satisfying. If magic bitboards are too confusing, the precursor - "kindergarten bitboards" - are a bit easier to understand. I have a description here if anyone is curious: https://github.com/cglouch/snakefish#sliding-pieces

I think once you understand the principle behind kindergarten bitboards, magic bitboards start to make more sense. It's basically a more clever way of indexing into a precomputed move table, that takes advantage of the redundancy in occupancy states, and requires even fewer instructions to determine the index. Although it does still feel kinda magic!

Bitboards also work fabulously on connect-4, encoding a 7x6 position in 7x(6+1)=49 bits [1] and allowing for a win test with 8 shifts/ands:

    // return whether newboard includes a win
    final boolean haswon(long newboard)
    {
      long y = newboard & (newboard>>HEIGHT);
      if ((y & (y >> 2*HEIGHT)) != 0) // check diagonal \
        return true;
      y = newboard & (newboard>>H1);
      if ((y & (y >> 2*H1)) != 0) // check horizontal -
        return true;
      y = newboard & (newboard>>H2); // check diagonal /
      if ((y & (y >> 2*H2)) != 0)
        return true;
      y = newboard & (newboard>>1); // check vertical |
      return (y & (y >> 2)) != 0;
    }

Dominikus Herzberg offers a more detailed explanation [2] for the benefit of his students.

[1] http://tromp.github.io/c4/Connect4.java

[2] https://github.com/denkspuren/BitboardC4/blob/master/Bitboar...

I found a notice in wikispaces that they're closing, with as reason that "it's too expensive to bring it to modern standards"

So, they're going to delete all that useful information presented on a perfect fast loading and fast scrolling website?!?!

Wikispaces, hosting this and many other invaluable wikis, is shutting down soon. It would be great if TES would open the source. There is also, it seems to me, a need for a modern alternative to MediaWiki.

I found that this answer on stack exchange was the best resource for understanding magic bitboards and how/why they work. A really well written answer: https://stackoverflow.com/a/30862064/1056032

Not just bishops, also rooks (and queens).

Magic bitboards are awesome. Here's my implementation:

https://github.com/fogleman/MisterQueen/blob/master/src/bb.c...

I remember all the time searching through here when implementing my own chess AI a few years back. Good memories. Sad to hear wikispaces is closing.